Boidsの布教 - 3つの規則で群れを作る

はじめに

この記事はSystemiアドベンドカレンダー17日目です。
社会人3年目になり仕事でも色々とできるようになってきましたが、その分やらなくなってきたことなども増えてきたので、今回は気分転換にBoidsというアルゴリズムをテーマに挙げてみました。

Boidsとは

Boidsとは鳥や魚などの群れの行動をシミュレーションするためのアルゴリズムです。
Boidsという名称は「鳥もどき(bird-oid)」から取られているそうです
このアルゴリズムは各個体が3つの規則に従って行動を行うだけで指示を出すリーダーがいなくても群れとしての複雑な動きを実現するものです。
実際にこのアルゴリズムはさまざまな分野で使用されており、研究目的以外にも映画やゲーム開発で使用されていたりします。

この記事を書く前にBoidsを調べたらGoogleが面白いことをしていたので良かったら一度Google検索でBoidsを検索してみてください

3つの規則

紹介のところで書いた3つの規則である、分離、整列、結合について説明します。

分離(Separation)

分離は各個体が他の個体との衝突を避けるために距離をとる規則です。

整列(Alignment)

整列は近隣の個体と概ね同じ方向に飛ぶように速度と方向を合わせる規則です。

結合(Cohesion)

結合は各個体が群れの中心の方向に向かって進むように方向を変える規則です。

この3つを使用するだけで鳥や魚の動きを模倣することができます。

実際作るとどうか

実際作るのはそこまで難しくはありません
上に記載した3つの規則が大事ではありますが、それぞれで行わなければいけないことは明確かつ難しい話ではないからです。
3つの規則について実装を見ながら少し紹介したいと思います。

注意：5年くらい前にC++で実装したものを読み替えて書いているので漏れがあったり、ざっくりと書いているので最適化されていないなどありますがご了承ください

前提

以下のコードでは、各個体(Boid)が持つ情報として:

• pos: 現在位置 {x, y}
• vel: 現在速度 {x, y}
  全体として共通の情報として：
• maxSpeed: 最大速度
• maxForce: 最大の力（急激な方向転換を防ぐ）
• nearBoids: 認識範囲内の他Boidの配列
  を使用します

分離の実装

separation() {
	// 近くに個体が存在しなければ分離を行う必要がないのでxy共に0
	if (nearBoids.length === 0) return { x: 0, y:0 }
	
	let forceX = 0; 
	let forceY = 0;
	
	for (let near of nearBoids) {	
		// 距離が近ければ近いほど強く反発させるための計算
		const distanceSquared = Math.max(near.distance * near.distance, 1.0);
		
		// 離れる方向
		const dirX = -near.dx / near.distance; 
		const dirY = -near.dy / near.distance;
		
		// 反発力を加算（距離が近いほど大きい）
		forceX += dirX / distanceSquared; 
		forceY += dirY / distanceSquared;
	}
	 
	// 平均を取って返す 
	return { 
		x: forceX / nearBoids.length, 
		y: forceY / nearBoids.length 
	};
}

分離で行うことは、近くにいる個体から離れる方向と力を計算することです。
処理の流れ:

1. 近くの各個体について、離れる方向ベクトルを計算
2. 距離が近いほど強い反発力を設定（1/距離²）
3. すべての反発力を合計し、個体数で平均化

この平均化により、近くの個体からは強く影響を受け、 遠くの個体からは弱く影響を受けるようになります。

整列の実装

alignment() {
	// 近くにboidがいなければ、何もしない 
	if (nearBoids.length === 0) { return { x: 0, y: 0 }; } 
	
	// 周囲の個体の速度の平均を計算
	let avgVelX = 0; 
	let avgVelY = 0; 
	
	for (let near of nearBoids) { 
		avgVelX += near.velX; 
		avgVelY += near.velY; 
	} 
	
	avgVelX /= nearBoids.length; 
	avgVelY /= nearBoids.length; 
	
	// 平均速度に合わせる力を計算 
	// 目標速度に正規化
	const targetSpeed = maxSpeed; 
	const length = Math.hypot(avgVelX, avgVelY) || 1; 
	avgVelX = (avgVelX / length) * targetSpeed; 
	avgVelY = (avgVelY / length) * targetSpeed; 
	
	// 現在の速度との差分 = 必要な力
	// velは現在の速度
	const steeringX = avgVelX - vel.x;
	const steeringY = avgVelY - vel.y;
	
	// 力を制限 
	const steeringLength = Math.hypot(steeringX, steeringY); 
	if (steeringLength > maxForce) { 
		return { 
			x: (steeringX / steeringLength) * maxForce, 
			y: (steeringY / steeringLength) * maxForce 
		}; 
	}
	
	return { x: steeringX, y: steeringY };
}

整列で行うことは、周囲の個体と同じ方向・速度で移動するための力を計算することです。

処理の流れ:

1. 近くの各個体の速度ベクトルを収集
2. 速度ベクトルの平均を計算
3. 平均速度と自分の現在速度の差分を求める

この差分が、周囲と速度を合わせるために必要な力で、群れとして同じ方向に揃って移動するようになります。

結合の実装

cohesion() {
	// 近くにboidがいなければ、何もしない 
	if (nearBoids.length === 0) { return { x: 0, y: 0 }; } 
	
	// 周囲のboidの重心（中心位置）を計算 
	let centerX = 0; 
	let centerY = 0; 
	
	for (let near of nearBoids) { 
		centerX += near.posX; 
		centerY += near.posY; 
	} 
	
	centerX /= nearBoids.length; 
	centerY /= nearBoids.length; 
	
	// 重心に向かう力を計算 
	// posは現在の座標
	const towardX = centerX - pos.x; 
	const towardY = centerY - pos.y; 
	
	// 目標速度に正規化 
	const targetSpeed = maxSpeed; 
	const length = Math.hypot(towardX, towardY) || 1; 
	const desiredX = (towardX / length) * targetSpeed; 
	const desiredY = (towardY / length) * targetSpeed; 
	
	// 現在の速度との差分 = 必要な力 
	// velは現在の速度
	const steeringX = desiredX - vel.x;
	const steeringY = desiredY - vel.y; 
	// 力を制限 
	const steeringLength = Math.hypot(steeringX, steeringY); 
	if (steeringLength > maxForce) { 
		return { 
			x: (steeringX / steeringLength) * maxForce, 
			y: (steeringY / steeringLength) * maxForce 
		}; 
	} 
	return { x: steeringX, y: steeringY }; }
}

結合で行うことは、群れの中心に向かって移動するための力を計算することです。

処理の流れ:

1. 近くの各個体の位置を収集
2. 位置の平均（重心）を計算
3. 重心と自分の現在位置の差分を求める

この差分が、群れの中心に向かうのに必要な力となり、個体がバラバラにならず、まとまった群れを形成することができます。

あとがき

近くの個体の探索など端折った内容もありますがBoidsとして大事な要素は以上になります。
やっていること自体はそれぞれ実際にやってみると案外簡単にできたり、3つの規則にそれぞれ重みを持たせてその重みをパラメータ化したりすると動きが全然変わったりして面白いので、興味があれば一度ぜひやってみてください。