こんにちは。NUMです。
最近は色々とプライベートがバタバタしていてブログを書けていなかったですが
やっと落ち着いてたので、最近ハマっているモジホコリのアルゴリズムを実装していこうと思います。
Patt Vira さんというクリエイティブコーディングを動画配信している方がきっかけでこのアルゴリズムに出会いました。 英語ですが、非常にわかりやすくサンプルコードもあるので入門者の方にもおすすめです。
モジホコリ
モジホコリは真核生物に属するアメーバ状の粘菌です。以下のような特徴を持ちます。
形態：
粘液状のネットワークを形成し、単一の細胞でありながら、多数の核を持つ多核体です。
移動：
アメーバ運動を行いながら、基質上を移動します。この運動は、化学物質の勾配に応じて進みます。
栄養摂取：
バクテリアや真菌などを捕食することで栄養を摂取します。栄養不足になると、胞子を形成し、生存を図ります。
実はこの生物、最短経路問題の解決やネットワーク最適化のモデルとして使用されるくらい賢い生物です。これはモジホコリが効率よく食物を探すために最短経路を求めるように進化してきたのではと考えられます。
それではモジホコリの移動方法をプログラム化していきます。
概要
採餌行動
モジホコリの採餌行動を単純化すると以下のようになります。
・自身の前左、前、前右のうち一番餌が多い方向を選択する。 そのため、移動方向を決定する3 つのセンサー (前左、前、前右) に用意します。 センサーは、どの方向に移動するかを決定する役割を持っています。
最短経路
モジホコリは餌までの最短経路を求めることができる習性があります。
他の個体が同じ経路を何度も使用しているということは、その経路が餌までの最短経路であると考えられます。移動の痕跡を残すことで、1の習性を使い他個体が集まってくるということですね。
これを実現するには、キャンバスをグリッドで埋め尽くし、その位置に個体が通った痕跡を保持することで実現できます。
また、物質の濃度勾配による移動を再現するために、拡散の仕組みをグリッドに取り入れます。
今回はできる限り単純化するために餌と痕跡の情報を同じ情報にします。
つまりエージェントとグリッドの仕組みを使用したプログラムになりそうですね。
ちなみに、FlowFieldの同じような仕組みを使っていますね。
実装
まず、プログラム全体を以下に記載します。
今回のトピックであるPhysarumが特に重要なので、Physarumクラスをメインで説明していきます。
Main：
ArrayList<Physarum> plist = new ArrayList<Physarum>();
void setup() {
size(500, 500);
background(0);
pixelDensity(displayDensity());
initialize(10000);
}
void draw() {
// 残像
fill(0, 5);
rect(0, 0, width, height);
// モジホコリの移動、描画
for (Physarum p : plist) {
p.boundaryCheck();
p.updateAngle();
p.update();
p.show();
}
// 拡散方程式
diffusion();
}
void initialize(int pSize) {
setKGrid();
for (int i = 0; i < pSize; i++) {
plist.add(new Physarum());
}
}
Physarum：
/**
* Physarumクラス。
*/
class Physarum {
PVector location;
int angle;
/**
* Physarumのコンストラクタ。
* オブジェクトの位置と角度を初期化する。
*/
Physarum() {
angle = 45 * int(random(0, 8));
int x = int(random(10, width - 10));
int y = int(random(10, width - 10));
location = new PVector(x, y);
}
/**
* 描画
*/
void show() {
noStroke();
float alfa = k[int(this.location.x)][int(this.location.y)];
fill(255, alfa*50);
ellipse(this.location.x, this.location.y, 1, 1);
}
/**
* 位置更新、移動の痕跡を残す。
*/
void update() {
float cos = getCos(this.angle);
float sin = getSin(this.angle);
this.location.x = (this.location.x + cos);
this.location.y = (this.location.y + sin);
boundaryCheck();
k[int(location.x)][int(location.y)] += 0.2;
}
/**
* 周囲の拡散値に基づいて新しい角度を決定する。
* @return Physarumオブジェクトの新しい角度
*/
void updateAngle() {
int calcAngle = 0;
float k1 = 0;
float k2 = 0;
float k3 = 0;
int x = int(location.x);
int y = int(location.y);
// 近傍の参照によって配列外参照エラーを防ぐため
if (!(x < 1 || x >= width-1 || y < 1 || y >= height-1)) {
// 角度に応じて参照先の近傍を決定する
switch (this.angle) {
case 0:
k1 = k[x + 1][y - 1];
k2 = k[x + 1][y];
k3 = k[x + 1][y + 1];
break;
case 45:
k1 = k[x + 1][y];
k2 = k[x + 1][y + 1];
k3 = k[x][y + 1];
break;
case 90:
k1 = k[x + 1][y + 1];
k2 = k[x][y + 1];
k3 = k[x - 1][y + 1];
break;
case 135:
k1 = k[x][y + 1];
k2 = k[x - 1][y + 1];
k3 = k[x - 1][y];
break;
case 180:
k1 = k[x - 1][y + 1];
k2 = k[x - 1][y];
k3 = k[x - 1][y - 1];
break;
case 225:
k1 = k[x - 1][y];
k2 = k[x - 1][y - 1];
k3 = k[x][y - 1];
break;
case 270:
k1 = k[x - 1][y - 1];
k2 = k[x][y - 1];
k3 = k[x + 1][y - 1];
break;
case 315:
k1 = k[x][y - 1];
k2 = k[x + 1][y - 1];
k3 = k[x + 1][y];
break;
}
// 前方,右,左の値を比較して一番大きい角度を選択
if (k2 > k1 && k2 > k3) {
calcAngle = this.angle + 0;
} else if (k2 < k1 && k2 < k3) {
if (random(1) < 0.5) {
calcAngle = this.angle + 45;
} else {
calcAngle = this.angle - 45;
}
} else if (k1 > k3) {
calcAngle = this.angle - 45;
} else if (k3 > k1) {
calcAngle = this.angle + 45;
}
// 角度を0~360の範囲内にする
this.angle = (calcAngle + 360) % 360;
}
}
/**
* キャンバス外に移動したオブジェクトを逆側に移動させる
*/
void boundaryCheck() {
this.location.x = (this.location.x + width) % width;
this.location.y = (this.location.y + height) % height;
}
}
Physarumクラスは以下2つの情報を保持します。
位置
自身が向いている角度
updateAngleメソッド
はじめに、モジホコリは移動するために2を使用し、前方3方向（前、左、右）の痕跡のうち一番大きい値を探知します。
探知の結果、移動する角度が決まるので、例として今回は右（45°）に移動するので、2に45°を足し合わせます。
場合によっては一番大きい値が決まらない可能性もあるので、その際はランダムで角度を決める処理を入れています。
updateメソッド
updateAngleメソッドで移動角度が決まったので、位置を角度に合わせて更新します。 boundaryCheckメソッドはエージェントがキャンバス内にとどまるように計算する処理です。
k[int(location.x)][int(location.y)] += 0.2;
上記は移動した経路の痕跡を表現しています。移動経路のみ餌を増加させることで、餌に集まる習性によりその経路が選ばれやすくなります。
Diffusion：
float[][] laplacianXk, laplacianYk;
float[][] k, nextK;
float Dk = 0.001; // 拡散係数
/**
* 拡散方程式で使用する配列を初期化(0埋め)する。
*/
void setKGrid() {
k = new float[width][height];
nextK = new float[width][height];
laplacianXk = new float[width][height];
laplacianYk = new float[width][height];
for (int i = 0; i < width; i++) {
for (int j = 0; j < height; j++) {
k[i][j] = 0;
nextK[i][j] = 0;
}
}
}
/**
* 拡散方程式の計算
*/
void diffusion() {
// ラプラシアンの計算
for (int i = 1; i < width-1; i ++) {
for (int j = 1; j < height-1; j ++) {
laplacianXk[i][j] = k[i+1][j] - 2*k[i][j] + k[i-1][j];
laplacianYk[i][j] = k[i][j+1] - 2*k[i][j] + k[i][j-1];
}
}
// 拡散方程式
for (int i = 1; i < width-1; i++) {
for (int j = 1; j < height-1; j++) {
float laplacianK = laplacianXk[i][j] + laplacianYk[i][j];
// 同じ経路に収束すると同じ模様になることを防ぐため0.9掛けする
nextK[i][j] = (k[i][j] + Dk * (laplacianK))*0.9;
}
}
swap();
}
/**
* 計算結果を入れ替えて配列を使い回す
*/
void swap() {
float[][] temp = k;
k = nextK;
nextK = temp;
}
拡散方程式は以前書いた記事が詳しく解説しているので見てみて下さい。 Processing 自然界の芸術 チューリングパターン
記事と少し異なっている箇所は以下です。 拡散方程式の計算結果に0.9を掛けている点です。
// 同じ経路に収束すると同じ模様になることを防ぐため0.9掛けする
nextK[i][j] = (k[i][j] + Dk * (laplacianK))*0.9;
これは、時間経過ともに、餌が減少していく過程を拡散現象とすることで 物質の濃度勾配による移動を表現しています。これにより有機的なパターンが形成されます。
またコメントにもある通り、拡散しないと個体が同じ箇所にとどまり続けるため パターンの多様性を見たいという目的もあります。笑
TrigonometricFunc：
//0~359°までのcos,sin計算値を配列に格納
ArrayList<float[]> TrigonoArrlist = createsincosArr(0, 360);
/**
* 0~359°までの計算値を配列に格納
* @param1 float cos関数計算値
* @param2 float sin関数計算値
* @return 0~359°までの計算値を配列に格納したList
*/
ArrayList<float[]> createsincosArr(int iStart, int iEnd) {
int Arri = 0;
ArrayList<float[]> sincosList = new ArrayList<float[]>();
float[] cosArr = new float[iEnd-iStart];
float[] sinArr = new float[iEnd-iStart];
for (int i = iStart; i<iEnd; i+=1) {
cosArr[Arri] = cos(radians(i));
sinArr[Arri] = sin(radians(i));
Arri++;
}
sincosList.add(cosArr);
sincosList.add(sinArr);
return sincosList;
}
/**
* cos関数の計算結果を取得
* @param1 int 角度
* @return cos関数の計算結果
*/
float getCos(int Index) {
int index;
if (Index >= 360) {
index = Index%360;
} else {
index = Index;
}
return TrigonoArrlist.get(0)[index];
}
/**
* sin関数の計算結果を取得
* @param1 int 角度
* @return sin関数の計算結果
*/
float getSin(int Index) {
int index;
if (Index >= 360) {
index = Index%360;
} else {
index = Index;
}
return TrigonoArrlist.get(1)[index];
}
これは正直無くても良いのですが、cos、sinメソッドを多用するので 事前に計算結果を取得しておくことで、計算量削減をしています。
エージェントの数が多いので、こういうのもチリツモだと思います。
まとめ
今回はモジホコリのアルゴリズムを実装してみました。
非常に単純なアルゴリズムですが、複雑なパターンが作り出せることに驚きました。
単純な行動を沢山の個体が行うことで、目的を達成したりすることを「群知能」というそうです。
パターン形成に関する群知能を色々と勉強してみるのも楽しそうですね！
この作品は今回のプログラムにチューリングパターンを組み合わせて、藻類をモチーフとして惑星を表現してみました。
[Algae Moon]
最後まで読んでいただきありがとうございました！
参考
Comments