More than 5 years have passed since last update.

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

Last updated at 2019-04-14Posted at 2019-04-11

スイミーって？

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

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

Boids 概要

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

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

Rule1 : 分離(Separation)
群れの仲間に近づきすぎてぶつからないようにする．

Rule2: 整列(Alignment)
群れの仲間と進行方向を合わせようとする．

Rule3: 結合(Cohension)
群れの仲間の近くにいたい．群れの中心方向に向かう．

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

疑似コードもどき

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

ルール１（分離）

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

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

ルール２（整列）

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

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

ルール３（結合）

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

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