この前、図書館をテキトーにうろついていると、DLAというものについて書かれた本を見つけました。
DLA(Diffusion-Limited-Aggregationの略)とは、
動き回っている大量の粒子がお互いにくっついていって大きくなることで、
DLAによって作られた大きな塊のことを凝集体(ぎょうしゅうたい)というそうです。

凝集体の画像を見てみると、小さな粒がたくさんくっついて何度も枝分かれをしながら
大きな形を作っていて、面白そう！と思ったのでProcessingでプログラムを作ってみました。

---

---

ネットで調べてみたところ、凝集体の作り方としては
一度に大量の粒子を動かしてくっつけていく方法と、
粒子を一つずつ飛ばしてくっつける方法があるようなのですが、
今回は後者の一つずつ飛ばしてくっつけるやり方でやってみます。

図にするとこんな感じです。

緑色の線がくっついている粒子で、赤色の線が粒子の動きです。
今使っているパソコンがそこまで良いスペックのものではないので、
一つずつ飛ばしたほうが時間はかかりそうだけど処理が軽いかな？と思い選びました。

---

ここからはプログラムを組んでいきます。

基本は画面の端から粒子を飛ばしていき、
ほかの粒子にぶつかるまで待つという方法なのですが、
そうすると、大きい画面で凝集体を作るときにかなり時間がかかってしまうので、
凝集体の大きさに合わせて少しずつ粒子を飛ばす範囲を広げるような感じにしました。

図はこんな感じです。

飛ばしている粒子は凝集体の大きさに合わせて作られた青い枠の中だけで飛ぶことで
大きな画面で始めたときに中々ほかの粒子にぶつからず、
計算時間が長くなるということが起こらないようにします。

また、粒子が他の粒子と衝突したかどうかの判定は画素の値を用いて行います。
あらかじめ背景を黒色にしておき、そこに黒以外の色の粒子を設置し、粒子を飛ばします。

飛ばされた粒子が移動した先の画素が黒色でなければ、
そこには凝集体があるということになるので、後ろに下がって凝集体にくっつくようにします。

---

今回のプログラムでは、粒子が他の粒子とぶつからないとくっつかず、
粒子は一つずつ飛ばしていくため、
初めに動かない粒子を最低一つは置いておかなければいけません。

また、凝集体の大きさに合わせて粒子が飛ぶ範囲が広がっていくため、粒子がくっつく度に
粒子の飛ぶ範囲を広げていきます。

int fieldEdge[] = {100000, 100000, 0, 0};
int padding = 10;

// 粒子が飛ぶ範囲の更新
void updateEdge(int x, int y){
  fieldEdge[0] = Math.min(fieldEdge[0], x - padding);
  fieldEdge[1] = Math.min(fieldEdge[1], y - padding);
  fieldEdge[2] = Math.max(fieldEdge[2], x + padding);
  fieldEdge[3] = Math.max(fieldEdge[3], y + padding);
}

// 粒子の設置
void setPoint(int x, int y, color c){
  stroke(c);
  point(x, y);
  updateEdge(x, y);
}

プログラムはこんな感じになりました。

粒子が飛ぶ範囲についてですが、凝集体とぴったりくっついた範囲にしてしまうと
新しく飛ばした粒子が全然飛び回らずに凝集体と衝突してしまう恐れがあるので
paddingという変数を用いて
凝集体とはある程度離れた場所から新しい粒子が出てくるようにします。

---

粒子を設置した後は、飛ばす粒子の初期化を行います。

プログラムは以下のようになりました。

int x, y;
				
void dotInit(){
  switch((int)random(4)){
    case 0:
      x = Math.max(fieldEdge[0] - padding, 0);
      y = (int)random(fieldEdge[3] - fieldEdge[1] + 2 * padding) + fieldEdge[1] - padding;
      break;
    case 1:
      x = Math.min(fieldEdge[2] + padding, width - 1);
      y = (int)random(fieldEdge[3] - fieldEdge[1] + 2 * padding) + fieldEdge[1] - padding;
      break;
    case 2:
      x = (int)random(fieldEdge[2] - fieldEdge[0] + 2 * padding) + fieldEdge[0] - padding;
      y = Math.max(fieldEdge[1] - padding, 0);
      break;
    case 3:
      x = (int)random(fieldEdge[2] - fieldEdge[0] + 2 * padding) + fieldEdge[0] - padding;
      y = Math.min(fieldEdge[3] + padding, height - 1);
      break;
  }
}

基本的には、粒子が動くことのできる範囲の境界線上のどこかに
新しい粒子が現れるようになっています。

しかし、凝集体が既に十分大きくなっていて画面の端の方まで来ているときは、
それ以上範囲を広げることが出来ないので、その時は画面の端までで止まるように
Math.maxやMath.minを使って調整しています。

---

新しい粒子を設置出来たら、次は粒子を動かします。
DLAにおける粒子の動きはランダムウォークと呼ばれているそうで、
その名の通り、粒子がただ乱数でいろいろな方向に移動するというものです。

int dx[] = {1, 0, -1, 0, 1, 1, -1, -1};
int dy[] = {0, 1, 0, -1, 1, -1, 1, -1};

/* 
   関数を呼ぶときはこんな感じです
   int tmp = (int)random(8);
   dotMove(dx[tmp], dy[tmp]);
*/

void dotMove(int DX, int DY){
  x += DX;
  y += DY;

  // x座標がはみ出ていないかチェック
  if(x > Math.min(fieldEdge[2] + padding, width - 1)){
    x = Math.max(fieldEdge[0] - padding, 0);
  }
  else if(x < Math.max(fieldEdge[0] - padding, 0)){
    x = Math.min(fieldEdge[2] + padding, width - 1);
  }
  
  // y座標がはみ出ていないかチェック
  if(y > Math.min(fieldEdge[3] + padding, height - 1)){ 
    y = Math.max(fieldEdge[1] - padding, 0);
  }
  else if(y < Math.max(fieldEdge[1] - padding, 0)){
    y = Math.min(fieldEdge[3] + padding, height - 1);
  }
}

プログラムはこんな感じです。

このプログラムでは、上下左右と斜めの８方向に移動するようにしています。
また、粒子の座標が移動するのはこの関数が呼び出された時だけなので
座標が移動可能範囲から出ていないかのチェックも行っています。

粒子の座標がはみ出していたときは、反対側から出てくるようになっています。

---

前の章で粒子が移動するようになったので、次は凝集体と接触した時を考えます。

粒子は今いる座標の色が黒の時は移動を続けて、
座標が黒以外の所に着いたときに移動を終了します。

そのため、凝集体とくっつくようにするには、
今いる座標の一手前の座標に戻り、そこを塗る必要があります。


粒子の初期化、移動の部分と合わせると、下のようなプログラムになります。

// 粒子の初期化
dotInit();
int tmp = -1;

// 粒子の移動
while(get(x, y) == color(0, 0, 0)){
  tmp = (int)random(8);
  dotMove(dx[tmp], dy[tmp]);
}

// 粒子が衝突したので、一手戻り描画する
if(tmp > -1){
  dotMove(-dx[tmp], -dy[tmp]);
  setPoint(x, y, color((int)random(50) + 50, (int)random(100) + 150, (int)random(50) + 50));
}

while文を抜ける前と抜けた後では、変数tmpの値は変わっていないので
dx[tmp]とdy[tmp]に-をつけて移動させると一手前の座標に戻ることができます。

また、新しく飛ばされた粒子の初期位置に既に粒子がいた場合は、
一手前に戻ることが出来ないので、その場合はif文で弾いて無かったことにしています。

14行目のsetPoint()関数で指定している色は適当です。
今回は緑っぽい色にしてみました。

---

最後にプログラムを終了させる処理を作ります。

粒子が画面の端まで到達してしまうと、そこから粒子が一気に横に広がっていって
凝集体がなんとなく汚い感じになってしまうので粒子が端に到達した時点で終了させます。

プログラムは下のようになりました。

void reachToEnd(){
  if((x == 0) || (x == width - 1) || (y == 0) || (y == height - 1)){
    save("result.png");
    exit();
  }
}

プログラムを終了する際に、その時の画面を画像に出力するようにしました。

---

上の方で書いてきたプログラムを繋ぎ合わせると、
最終的なソースコードは下のようになりました。

int fieldEdge[] = {100000, 100000, 0, 0};
int padding = 10;
int dx[] = {1, 0, -1, 0, 1, 1, -1, -1};
int dy[] = {0, 1, 0, -1, 1, -1, 1, -1};
int x, y;

void setup(){
  size(600, 600);
  background(0, 0, 0);
  setPoint(width / 2, height / 2, color(0, 150 ,0));
}

void draw(){
  for(int i = 0; i < 20; i++){
    dotInit();
    int tmp = -1;
    while(get(x, y) == color(0, 0, 0)){
      tmp = (int)random(8);
      dotMove(dx[tmp], dy[tmp]);
    }
    if(tmp > -1){
      dotMove(-dx[tmp], -dy[tmp]);
      reachToEnd();
      setPoint(x, y, color((int)random(50) + 50, (int)random(100) + 150, (int)random(50) + 50));
    }
  }
}

void reachToEnd(){
  if((x == 0) || (x == width - 1) || (y == 0) || (y == height - 1)){
    save("result.png");
    exit();
  }
}

void updateEdge(int x, int y){
  fieldEdge[0] = Math.min(fieldEdge[0], x - padding);
  fieldEdge[1] = Math.min(fieldEdge[1], y - padding);
  fieldEdge[2] = Math.max(fieldEdge[2], x + padding);
  fieldEdge[3] = Math.max(fieldEdge[3], y + padding);
}

void setPoint(int x, int y, color c){
  stroke(c);
  point(x, y);
  updateEdge(x, y);
}

void dotInit(){
  switch((int)random(4)){
    case 0:
      x = Math.max(fieldEdge[0], 0);
      y = (int)random(fieldEdge[3] - fieldEdge[1] + 2 * padding) + fieldEdge[1] - padding;
      break;
    case 1:
      x = Math.min(fieldEdge[2], width - 1);
      y = (int)random(fieldEdge[3] - fieldEdge[1] + 2 * padding) + fieldEdge[1] - padding;
      break;
    case 2:
      x = (int)random(fieldEdge[2] - fieldEdge[0] + 2 * padding) + fieldEdge[0] - padding;
      y = Math.max(fieldEdge[1], 0);
      break;
    case 3:
      x = (int)random(fieldEdge[2] - fieldEdge[0] + 2 * padding) + fieldEdge[0] - padding;
      y = Math.min(fieldEdge[3], height - 1);
      break;
  }
}

void dotMove(int DX, int DY){
  x += DX;
  y += DY;
  if(x > Math.min(fieldEdge[2], width - 1)){
    x = Math.max(fieldEdge[0], 0);
  }
  else if(x < Math.max(fieldEdge[0], 0)){
    x = Math.min(fieldEdge[2], width - 1);
  }
  
  if(y > Math.min(fieldEdge[3], height - 1)){
    y = Math.max(fieldEdge[1], 0);
  }
  else if(y < Math.max(fieldEdge[1], 0)){
    y = Math.min(fieldEdge[3], height - 1);
  }
}

基本的にはそれぞれの章で書いたものを繋げただけですが、
特筆すべき点として、draw()関数全体をfor文でくくっています。
for文でくくらない場合は、１ドットずつしか描画出来ませんが、
ループの回数だけまとめて描画できるようになります。
ただ、その分だけ処理も重たくなるので、
そのあたりは自分のパソコンと相談かなあと思います。

---

作ったプログラムを実際に動かした結果は、以下のようになりました。


とりあえずはちゃんと動いてそうな感じです。

---

ただの一発ネタですが、上のプログラムを少し変更して作ってみました。

闇の力を欲してみました pic.twitter.com/qXTIjKYS5o

— とえら (@mizzsig) 2016年7月30日

読み込んだ画像をエッジ抽出して、エッジの部分で粒子の衝突判定が起こるようにしています。

微妙にエッジが取れていない部分があって、少しはみ出しているのが残念ですが……