DLAってアートみたいだよね。綺麗だ。

## はじめに

今年も [明治大学 Advent Calendar](https://qiita.com/advent-calendar/2018/meiji_univ) が始まりました。悲しいぐらいカレンダーが埋まってないですが、**気合いで**二日目やっていきます。

## DLAとは
**DLA** (Diffusion Limited Aggregation) とは、日本語では**「拡散律速凝集」**と言います。ブラウン運動をする粒子が、核となるクラスタに衝突すると、その粒子がクラスタの一部になるという現象のことです。拡散律速凝集だなんて、仰々しい名前ですよね。

![DLA from wiki](https://upload.wikimedia.org/wikipedia/commons/5/55/Lichtenberg_figure_in_block_of_Plexiglas.jpg)
こういう木っぽいような結晶っぽいようなのが DLA によって作られるんです。

今回はそんな DLA をコンピュータシミュレーションしていきたいと思います。

## ブラウン運動をする粒子
DLA のコアとなる原理はブラウン運動です。中学校の理科の授業で聞いたことがあると思います。中学校では、溶液中の粒子が分子との衝突でランダムに動く現象のことと教わりましたね。要するに、粒子がランダムに動いていると考えればよいです。拡散方程式なのどの数理的な説明は面倒なので省きます~~（面倒というか忘れた）~~。

アルゴリズムは簡単ですね。

```ts
type Particle {
  size: number, // 粒子の直径
  x: number,
  y: number
}

const particle: Particle = { size: 1, x: 0, y: 0 }

function brownianMove(particle: Particle) {
  const theta = Math.random() * 2 * Math.PI
  const r = 1
  const direction = {
    x: r * Math.cos(theta),
    y: r * Math.sin(theta)
  }

  particle.x += direction.x
  particle.y += direction.y
}

while (true) {
  brownianMove(particle)
}

```
![brownianMotion.gif](https://qiita-image-store.s3.amazonaws.com/0/183627/6e670fe0-107e-14b0-5f3f-9937a235bd5e.gif)


## たくさんの粒子
DLA ではたくさんの粒子が登場します。$N$個ぐらいはあると考えてください。それら、$N$個の粒子がブラウン運動をするのです。

```ts
const particles: Particle[] = [...]

while (true) {
  particles.forEach(particle => {
    brownianMove(particle)
  })
}

```

![brownianMotion2.gif](https://qiita-image-store.s3.amazonaws.com/0/183627/43b74947-387d-400c-bf88-9af21956f823.gif)

## クラスタ
DLA における粒子には二つの状態があります。それは、その粒子がクラスタの一部であるか、ないかです。ブラウン運動をする粒子は、クラスタと衝突すると、そのクラスタの一部となり自身の運動をやめます。この現象こそが DLA です。

さて、粒子に状態を持たせます。

```ts
type Particle {
  size: number, 
  x: number,
  y: number,
  isCluster: boolean // new attr
}
```

ブラウン運動をしている粒子と、クラスタが衝突したら、その粒子はクラスタの一部になるというアルゴリズムを書きます。

```ts
function collide(particle, cluster) {
  const sub = {
    x: particle.x - cluster.x,
    y: particle.y - cluster.y
  }
  const distSquared = sub.x * sub.x + sub.y * sub.y
  
  // if 衝突, then クラスタ化
  if (distSquared < particle.size * particle.size / 2) {
    particle.isCluster = true
  }
}

while (true) {
  particles.forEach(particle => {
    if (particle.isCluster) return
    brownianMove(particle)
    
    particles.forEach(other => {
      // クラスタ以外を省く
      if (other === particle || !other.isCluster) return
      collide(particle, other)
    })
  })
}

```

初期状態として一つの粒子で形成されているクラスタが一つ存在するとします。今回は、2000個の粒子を使ってみました。どうでしょう？結晶のようなものができました！

![dla.gif](https://qiita-image-store.s3.amazonaws.com/0/183627/f897bdce-a435-a148-d684-d943f76eb679.gif)

## Advanced
今回の粒子はクラスタに衝突した瞬間にクラスタの一部になるように設定しましたが、衝突したときに確率 $p$ でクラスタの一部になるように設定することも可能です。他にも、全ての粒子に対して中心方向の力を加えてあげたりするのもありです。設定によって、形成されるクラスタの形が変化するので、色々と試してみるとおもしろいかもです。

こちら、二年前に書いた DLA Simulator で形成したクラスタになります。

![IMG_SAMPLE.png](https://qiita-image-store.s3.amazonaws.com/0/183627/df58258a-fdd4-ccc9-5d5a-6ea35a936dc0.png)

## さいごに
今回は DLA のコンピュータシミュレーションをしてみました。DLA は僕が大学二年生の時に現象数理学実験という講義にて学んだ内容の一部です。ビジュアル的に Generative Art のようで魅力的に感じませんか？

本記事では擬似コードとして`Typescript`を使いましたが、コンピュータシミュレーションは実は`Processing3`を使っています。本質的なアルゴリズムに関してはどちらも差はないので問題はないと思います。一応、Processingのコードも貼っておきます。[コード](https://gist.github.com/RyosukeCla/e33db770ace53552a7602ad9be7e2abe)

ついでに、二年前に書いた DLA Simulator も載せときます。[DLASimulator](https://github.com/RyosukeCla/DLASimulator)

## 余談
一年以上ぶりに`Java`のコードを書きました（ProcessingはJavaです）。最近は`Typescript`ばっか書いているので、セミコロンを書き忘れたり、配列の作り方を忘れたりって感じで面白かったです。

Advent calendar のコンテンツが何も思いつかなくて二年前のコンテンツを使ってしまったのですが、過去の思い出が蘇る感じで逆によかったなあ。

そういえば、二年前は`git`をまともに使えてなかったな〜。楽天で長期インターンをしたことがあるのですが、そこで`git`を使えるようになってきたんだっけ。これも二年前。懐かしいな〜。