Edited at

スイミーを再現したい! ~群れアルゴリズム Boids~


スイミーって? :fish:

スイミーTrimTrim_1.gif

小さな魚たちが群れをなして,大きな魚を追い払うシーンが印象的な絵本です.自分もスイミーになりたくて作りました.(おさかなかわいい)

この記事で説明する Boids というアルゴリズムは手軽で楽しいです.python3 での実装例(pyxelを使用)はこちら(GitHub)です.


Boids 概要

群れをシミュレーションするアルゴリズムで,鳥もどき(birdoids)を略して Boids と呼ばれます.このアルゴリズムでは3つのルールだけで群れを表現します. Batman Returns (1992) のワンシーンでは,コウモリの群れが本物みたいに飛んでいます!

Flocking bats in batman scene

ルールは以下の3つ.(2019/04/14追記:図の誤りを訂正しました.)

Rulles.gif

Rule1 : 分離(Separation)

群れの仲間に近づきすぎてぶつからないようにする.

Rule2: 整列(Alignment)

群れの仲間と進行方向を合わせようとする.

Rule3: 結合(Cohension)

群れの仲間の近くにいたい.群れの中心方向に向かう.

各 boid は図の円のような視界(Field Of Vision: FOV)を持っており,視界中にいる仲間を群れと認識します.図は2次元ですが容易に3次元に拡張することができます.


疑似コードもどき

それぞれのルールを詳しく見ていきます.ここでは各 boid は位置(position)・速度(velocity)・加速度(acceleration)をそれぞれ3次元ベクトルで持っているとします.


ルール1(分離)

仲間との距離が遠いときはゆるやかに,近づきすぎると急旋回して避けるようにします.近隣の仲間から遠ざかる方向に,距離に反比例する大きさのベクトルを作ります.すべての近隣の仲間について計算し,その平均値を返します.

function Rule1():

Vector3 vec = (zero vector)
foreach boid in (群れの仲間):
Vector3 dif = self.position - boid.position
vec += dif / (dif.magnitude^2)
return vec / (群れの仲間の数)


ルール2(整列)

群れ全体の速度ベクトルの平均に合わせるようにします.

function Rule2():

Vector3 vel = (zero vector)
foreach boid in (群れの仲間):
vel += boid.velocity
vel /= (群れの仲間の数)
return vel - self.velocity


ルール3(結合)

群れの中心に移動しようとします.群れの重心位置へ向かうベクトルを返します.

function Rule3():

Vector3 pos = (zero vector)
foreach boid in (群れの仲間):
pos += boid.position
pos /= (群れの仲間の数)
return pos - self.position


各 boid の更新

今回は単純に位置ベクトルに速度ベクトルを足すだけの実装にしました.(位置の更新に加速度も使うのが丁寧ですが,これで十分動きました).先に定義したベクトルを係数付きで足しあわせて更新します.

function update():

self.acceralation = COEF_1*Rule1() + COEF_2*Rule2() + COED_3*Rule3()
self.velocity += self.acceralation
self.postion += self.velocity


一歩進んで

壁や障害物に boid を埋め込む

障害物に座標を固定した boid を埋めておくことで,各 boid は障害物を避けて動くようになります(表現がグロい).

flocking_obstacleTrimTrim.gif

群れを操る

スイミーらしくするために「目」となる黒い魚をリーダーにして,群れを操作できるようにしました.群れの魚たちがリーダーの速度・座標に合わせて動くように,ルールを少し変更すればいいです.

実際にコードにする場合は速度に上限を設けたり,頑張って各パラメータを調整して自然な動きを目指したいです.


参考

wikipedia(Boids)

マッチ箱の脳

インタラクティブプログラミング- 群れ(boid)を作る

わかりやすいスライド(English)