概要

TypeScriptとAnime.js（jsのアニメーションライブラリ）を用いてBoidsアルゴリズムを実装してみたので、勉強したことや、設計内容をメモ。
目的はアルゴリズムの大まかな流れを理解することだったので、実装したアルゴリズムは簡易的で、本来いくつか実装すべき点を端折っている。

実装したコード

デモ

Boids アルゴリズムとは

Wikipedia 先生曰く

ボイド(Boids)は、アメリカのアニメーション・プログラマ、クレイグ・レイノルズが考案・作製した人工生命シミュレーションプログラムである。名称は「鳥もどき(bird-oid)」から取られている。
ボイド (人工生命) - Wikipedia https://ja.wikipedia.org/wiki/%E3%83%9C%E3%82%A4%E3%83%89_(%E4%BA%BA%E5%B7%A5%E7%94%9F%E5%91%BD)

元の論文はこちら

Reynolds C. W. (1987) Flocks, Herds, and Schools: A
Distributed Behavioral Model. Computer Graphics
https://team.inria.fr/imagine/files/2014/10/flocks-hers-and-schools.pdf

ざっと読んでみると、厳密に生物学的な運動を再現しようというよりは、アニメーション用に応用でき、みている者が楽しくなるようなシミュレーションを目指したとのこと。

実装上特に参考にしたコードはこちら

正直コードは以下のものの方が非常に綺麗に実装出来ているし、動きも申し分無いと思う。ただ、写景になってはつまらないので、アルゴリズムの計算の部分だけ参照した。
https://github.com/beneater/boids

上記著者のBen Eaterさんはちょうど最近以下のYoutubeでこのBoidsアルゴリズムについてのインタビューを受けていた。どうやらスーパーハッカーらしい。欧米の方がYoutubeでのTech系チャンネルは充実しているように感じる。
https://www.youtube.com/watch?v=4LWmRuB-uNU

道具

TypeScript
Anime.js

設計メモ

上記Wikipediaを引用すると、Boidsアルゴリズムは各鳥オブジェクトで以下の計算を行っていき、群れの動きを再現する。

分離（Separation）鳥オブジェクトが他の鳥オブジェクトとぶつからないように距離をとる。
整列（Alignment）鳥オブジェクトが他の鳥オブジェクトと概ね同じ方向に飛ぶように速度と方向を合わせる。
結合（Cohesion）鳥オブジェクトが他の鳥オブジェクトが集まっている群れの中心方向へ向かうように方向を変える。

まず鳥オブジェクトは「方向」と「速度」を持つ必要があることが分かる。今回はアルゴリズムの動きを、大まかに掴むことが目的だったので、「速度」は固定とした。また、各力の及ぼす割合は均等とした。

鳥オブジェクトを1つのBoidクラスとして表現し、その中に方向（ラジアン（座標を計算するための三角関数で扱いやすいため））と速度（1固定）を持たせた。

main.ts(抜粋)

class Boid {
  public drads: Array<number>;
  constructor(
    public id: number,
    public coordinate: Coordinate,
    public rad: number,
    public distance?: number // Speed
  ) {
    this.id = id;
    this.coordinate = coordinate;
    this.rad = rad;
    this.distance = distance === undefined ? 1 : distance;
    this.drads = [];
  }
...

ちなみに上記のBen Eaterさんは方向と速度をDx/Dyと座標の微分値で表現し、Boidに持たせている。実装上はその方がベターだと思う。というか、計算するときはどちらにしろ一度X成分、Y成分に分けて計算する必要がある（後述）ため、角度としてデータを持ってしまうとそれだけ計算量が増えてしまい、わざわざ方向と速度を別に持つメリットは多分無い。

ただ、Ben Eaterさんと同じ実装方法ではコピペしてしまいそう、かつ、方向と速度を分解して持つことも直感的には分かりやすいかと考え、今回はあえて上記のようにデータを持つようにした。

以下ではアルゴリズムは比較的単純だが、実装上いくつか手こずった点をメモしておこうと思う。

方向の計算

上述のように分離、整列、結合それぞれ加わる力を最終的には計算して、鳥オブジェクトをある方向に動かすことになる。基本的にはそれぞれのベクトル成分に係数を掛けた上で、各ベクトルの平均を取る、もしくは足し合わせるようなアプローチになると思う（上記Ben Eaterさんはそのように実装しているようだ）。

ただ今回は実装は簡単にするため、

スピードは一定
各分離、整列、結合に係数は加えない（それぞれ等しく力を加える）

とした。ということは、それぞれの力の平均、すなわち、各方向に加わる角度の平均を計算する必要がある。

しかし、角度の平均というのはやっかいで、例えば、10°と350°の平均は方向的には0°となってほしいのだが、単純に足して2で割ると180°になってしまい、真反対となってしまう。
こういう場合は、ベクトル成分に分解してからベクトルの平均を取って角度を算出すると簡単らしいので今回そのようなアプローチとした（参考リンク）。

壁に近づいたとき

他の鳥オブジェクトに近づいたときと同様に、壁から離れる力を働かせることにした。
例えば、45°で移動していた時に右側の壁に近づいたらX方向成分を反転し、135°に力を加える、といった処理を行う。

その他端折った処理

本来、整列や結合処理は、その鳥オブジェクトの近い鳥オブジェクトのみ、要はその鳥オブジェクトが見える範囲、とする必要があるようだが、今回はすべての鳥オブジェクトを対象にしている。したがって、群れが1つしか生成されない

言語、ライブラリの選定等

TypeScript
- 動くものを作りやすいブラウザで動作する言語が良いと思った
- jsもそんなに詳しくないが、とりあえず実装にあたり、ベクトルやら角度やらいくつかの値を扱うこともあり、型がほしいと思ったので、勉強も兼ねて初めてTypeScriptを使ってみることにした
Anime.js
- 今回はアルゴリズムの大まかな流れを理解することが目的なので、描画部分にはあまり労力を掛けたくないと思った
- Ben Eaterさんの実装ではCanvas APIを用いているが、図形描画の際の座標の計算や、動画にする時の処理の実装が若干面倒そうだったので簡単に動かせるライブラリを採用した

感想

動かすまでそれっぽく動くか分からなかったが、単純な実装でも案外それっぽく動いでびっくり。

（事後追記）↓ラズパイカーに組み込んだ
Boidsアルゴリズムでラズパイカーを動かす - memo.log https://kure.hatenablog.jp/entry/2020/10/12/191938

参考

角度の平均を求める方法 - Qiita https://qiita.com/koyo-miyamura/items/37d555ae150047ebefde

おいふぉりーのぶろぐ角度の平均の計算方法 http://tm86eublog.blog42.fc2.com/blog-entry-212.html

Boids アルゴリズムで鳥の群れを作ってみた

概要