前回は、とりあえず魚を泳がせました。
今回は、BOIDの基本的な部分を組み込んで、群れをなして泳がせてみます。
今回のソースは、次のものです。
今回のメインは boid.cpp です。
Game Programming Gems を参考にしました（それのシンプルバージョンとも言う）。
関数名なども、なるべくあわせるようにしています。
Craig Raynolds は、1987 年の SIGGRAPH で、
「Flocks, Herds, and Schools : A Distributed Behavioral Model」を発表しました。
この論文は、３つの理解しやすいルールを規定するだけで、動物の群れをシミュレーションできるというものです。
そのルールとは、
| Separation | (引き離し) | ： | 一定距離より近くに間を取らない |
| Alignment | (整列) | ： | 仲間とスピードと方向を合わせる。 |
| Cohesion | (結合) | ： | グループの中心へ向かおうとする。 |
です。
ここで出てくる BOID という単語は、(鳥)バードとアンドロイドを組み合わせた造語で、鳥だけでなく、魚や馬の群れにも
この単語は使われています。
今回のプログラムでは、魚の一匹一匹を表現するクラスを CBoid クラスとします。
われわれは、歩くときや会話するときなど、自然といい感じの距離を取って生活します。
これが『引き離し』です。
プログラムでは、次のように実装します。
関数の返り値が、『引き離し』による速度変化量（力）になります。
// ----------------------------------------------------------------------------
// Rule #1 (Separation) 仲間との距離をある大きさに維持することによって、ぶつかるのを避ける。
//-----------------------------------------------------------------------------
D3DXVECTOR3 CBoid::KeepDistance (void)
{
// 距離によって速さを調整する
float ratio = m_dist_to_nearest_flockmate / SEPARATION_DIST;
if (ratio < MIN_URGENCY) ratio = MIN_URGENCY;
if (ratio > MAX_URGENCY) ratio = MAX_URGENCY;
// もっとも近い仲間の方向を求める（その軸に向かう）
D3DXVECTOR3 change = m_nearest_flockmate->m_pos - m_pos;
D3DXVec3Normalize(&change, &change);
if (m_dist_to_nearest_flockmate < SEPARATION_DIST) {
change *= -ratio; // 非常に(SEPARATION_DISTより)近かったら、遠くへ話す
} else if (m_dist_to_nearest_flockmate > SEPARATION_DIST) {
change *= ratio; // 非常に(SEPARATION_DISTより)遠かったら、近寄る
} else {
change *= 0.0f; // いい感じの位置だったら、調整をしない
}
return (change);
}
m_pos が、各 BOID の位置です。
m_nearest_flockmate が、一番近い位置にいる仲間（のCBoidクラス）です。
基本的には、一番近い仲間への方向(change)を求め、適切な距離(SEPARATION_DIST)よりも近いか遠いかで、
その方向に近づいたり、遠ざかります。
遠くにいればいるほど、群れに戻ろうと必死になるので、一番近い仲間との距離(m_dist_to_nearest_flockmate)
に応じて、速さ(ratio)を変えます。
但し、泳ぐ速さには、限界がありますし、ひとかきで進む大きさがあるので、
力の上限と下限を設けます。
さて、次は、『整列』です。
とりあえず、一番近い仲間の速度を見て、その速度にだんだんあわせるようにします。
// ----------------------------------------------------------------------------
// Rule #2 (Alignment) 仲間とスピードと方向を合わせる。
//-----------------------------------------------------------------------------
D3DXVECTOR3 CBoid::MatchHeading (void)
{
// 一番近い仲間の速さの向きを調べる
D3DXVECTOR3 change = m_nearest_flockmate->m_vel;
D3DXVec3Normalize(&change, &change);
// だんだん速度をあわせるように調整する
change *= MIN_URGENCY;
return (change);
}
最後に、『結合』です。
仲間の中心位置を求めて、そちらに動かします。。
// ----------------------------------------------------------------------------
// Rule #3 (Cohesion) 自分のまわりの群れのグループの中心へ向かおうとする。
//-----------------------------------------------------------------------------
D3DXVECTOR3 CBoid::SteerToCenter (void)
{
D3DXVECTOR3 change;
// 見える仲間の中心位置を求める
D3DXVECTOR3 center = D3DXVECTOR3(0,0,0);
for (int i = 0; i < m_num_flockmates_seen; i++) {
if (VisibleFriendsList[i] != NULL){
center += VisibleFriendsList[i]->m_pos;
}
}
center /= m_num_flockmates_seen;// 位置の合計を見える仲間の数で割って、中心を求める
// 中心への向きを求めて、だんだんそちらによるように動かす
change = center - m_pos;
D3DXVec3Normalize(&change, &change);
change *= MIN_URGENCY;
return (change);
}
m_num_flockmates_seen に、見える仲間の数が入っています。
VisibleFriendsList[] は、線形リストで、見える仲間が納められています。
以上の話は、既に見える範囲の仲間を見つけた後のお話です。
見える範囲の仲間及び、一番近い場所にいる仲間を見つける方法を説明します。
先ずは、仲間を見つける方法です。
下の関数が見つける関数です。
// ----------------------------------------------------------------------------
// 仲間 (ptr) が見えるか？
//-----------------------------------------------------------------------------
float CBoid::CanISee (CBoid *ptr)
{
if (this == ptr) return (INFINITY); // 自分は見えない（はるかかなたにいる）
// 距離の計算
D3DXVECTOR3 d = m_pos - ptr->m_pos;
float dist = D3DXVec3Length(&d);
// 視野の範囲にいたら、その距離を返す
if (m_perception > dist) return (dist);
// 見えなかった
return (INFINITY);
}
仲間(ptr)に対して、距離(dist)を計算します。
目の届く範囲(m_perception)よりも近くにいたら、その距離を返します。
位置が遠くて、見つからなかった場合には、見つからなかったとして、INFINITY を返します。
今回は、視野角による効果（目は前についているので、後ろは見えない）を入れていません。
視野角を入れると、玉突き事故がおきやすくなります。
おそらく、そちらのほうがリアルです。
今のが、一つ一つの可視判定でした。
1つのBOIDに関する可視判定は、全ての BOID に対して、以上の判定を行います。
また、それぞれの判定で、距離が返ってきますので、返ってきた値を調べて、
一番近かったら、一番近いBOIDに設定します。
// ----------------------------------------------------------------------------
// 仲間を探す
//-----------------------------------------------------------------------------
int CBoid::SeeFriends (CBoid *first_boid)
{
// 可視リストを初期化する
ClearVisibleList();
for (CBoid *flockmate = first_boid; flockmate != NULL; flockmate = flockmate->GetNext()) {
float dist;
// 可視判定
if ((dist = CanISee(flockmate)) != INFINITY) {
AddToVisibleList(flockmate);// 見えたら可視リストに追加
// 一番近いのか判定
if (dist < m_dist_to_nearest_flockmate) {
m_nearest_flockmate = flockmate; 一番近い仲間のポインタを保存
m_dist_to_nearest_flockmate = dist; 距離を代入
}
}
}
return (m_num_flockmates_seen);
}
それぞれのBOIDは、線形リストで下のように繋がれています。
GetNext()で、次のBOIDを持ってきて、無ければ (NULLならば) 終了です。
ちなみに、以上の関数の初期化や追加は、次のようになっています。
// ----------------------------------------------------------------------------
// 仲間の可視リスト構造（初期化）
//-----------------------------------------------------------------------------
void CBoid::ClearVisibleList (void)
{
// それぞれのリストを初期化
for (int i = 0; i < MAX_FRIENDS_VISIBLE; i++) {
VisibleFriendsList[i] = NULL;
}
// 他の変数の初期化
m_num_flockmates_seen = 0;
m_nearest_flockmate = NULL;
m_dist_to_nearest_flockmate = INFINITY;
}
// ----------------------------------------------------------------------------
// 可視リストへ追加
//-----------------------------------------------------------------------------
void CBoid::AddToVisibleList (CBoid *ptr)
{
if (MAX_FRIENDS_VISIBLE <= m_num_flockmates_seen) return;// バッファがいっぱいで追加できない
VisibleFriendsList[m_num_flockmates_seen++] = ptr; // リストの最後に追加
}
では、以上を組み合わせて、一フレームでの BOID の動きにまとめます。
先ほど解説した、SeeFriends で、視界に入る仲間を見つけます。
仲間が入れば、Raynolds のルールに従って、移動をします。
移動量から、向きや速度を決定して、最後に世界から飛び出たら、修正します。
// ----------------------------------------------------------------------------
// フレームごとのアップデート
//-----------------------------------------------------------------------------
void CBoid::FlockIt (int flock_id, CBoid *first_boid)
{
// Step 1: 前の時間に決定した速度を使って位置の更新
m_oldpos = m_pos; // 前の座標を保存しておく
m_pos += m_vel; // 移動
// Step 2: 仲間を探す
this->SeeFriends (first_boid);
D3DXVECTOR3 acc = D3DXVECTOR3(0,0,0);
// Step 3: 群れの動作
if (m_num_flockmates_seen) {
// Step 4: Rule #1 (Separation)
// 仲間との距離をある大きさに維持することによって、ぶつかるのを避ける。
acc += KeepDistance();
// Step 5: Rule #2 (Alignment)
// 仲間とスピードと方向を合わせる。
acc += MatchHeading();
// Step 6: Rule #3 (Cohesion)
// 自分のまわりの群れのグループの中心へ向かおうとする。
acc += SteerToCenter();
}
// Step 7: 巡航
acc += Cruising();
// Step 8: 加速の制限 (MAX_CHANGEより強い力は出せません)
if (D3DXVec3Length(&acc) > MAX_CHANGE) {
D3DXVec3Normalize(&acc, &acc);
acc *= MAX_CHANGE;
}
// Step 9: 速度変化
m_oldvel = m_vel; // 前の速さを取っておく
m_vel += acc; // 加速
// Step 11: 速すぎたときに、速度を制限する(MAX_SPEEDより速く泳げません)
if ((m_speed = D3DXVec3Length(&m_vel)) > MAX_SPEED) {
D3DXVec3Normalize(&m_vel, &m_vel);
m_vel *= MAX_SPEED;
m_speed = MAX_SPEED;
}
this->ComputeRPY(); // Step 12: 回転の計算
this->WorldBound(); // Step 13: 世界の境界の処理
}
最終的に速度変化を求めた後に、MAX_CHANGE や、MAX_SPEED を使って、速度変化や、速度に制限をつけています。
筋力の限界や、水の抵抗があるので、何らかの方法で限界を入れなければなりません。
おそらく、この方法が簡単でしょう。
Cruising という、紹介していない速度変化があります。
これは、一人で泳いでいるときの魚の運動です。
ここでは、一定の速度(巡航速度：DESIRED_SPEED)で泳ぐようにします。
また、以上の動きではつまらないので、首振りを入れます。
これは、巡航速度に近づけるときに、ランダムに少し行き過ぎさせ、不安定にすることによって、ユラユラとした動きを作ります。
// ----------------------------------------------------------------------------
// 通常巡航
//-----------------------------------------------------------------------------
D3DXVECTOR3 CBoid::Cruising (void)
{
// 巡航速度(DESIRED_SPEED)にちかづける
float diff = (m_speed - DESIRED_SPEED)/ MAX_SPEED;
float urgency = (float) fabs(diff);
if (urgency < MIN_URGENCY) urgency = MIN_URGENCY;
if (urgency > MAX_URGENCY) urgency = MAX_URGENCY;
// ランダム性を入れて、首振り運動をさせる.
float jitter = RAND();
if (jitter < 0.45f) {
change.x += MIN_URGENCY * SIGN(diff);
} else if (jitter < 0.90f) {
change.z += MIN_URGENCY * SIGN(diff);
} else {
change.y += MIN_URGENCY * SIGN(diff);// あまり縦にはゆれない
}
// 速度変化を力に追加する
D3DXVECTOR3 change = m_vel;
D3DXVec3Normalize(&change, &change);
change *= (urgency * SIGN(-diff));
return (change);
}
最後に向きの変更です。
pitch と yaw は、速度の経度及び緯度として求められます。
roll は、速度変化の速度に直行する部分の大きさを見て、横に大きく動くようなら、大きく傾くようにしました。
// ----------------------------------------------------------------------------
// Roll Pitch Yaw の回転の計算
//-----------------------------------------------------------------------------
void CBoid::ComputeRPY (void)
{
float roll, pitch, yaw;
// 受けた力を計算する
D3DXVECTOR3 d = m_vel - m_oldvel;
D3DXVECTOR3 lateralDir;
D3DXVec3Cross(&lateralDir, &m_vel, &d);
D3DXVec3Cross(&lateralDir, &lateralDir, &m_vel);// 受けた力の速度に直交する成分（回転成分）
D3DXVec3Normalize(&lateralDir, &lateralDir);
// トルク計算
float lateralMag = D3DXVec3Dot(&d, &lateralDir);
// roll
if (lateralMag == 0) {
roll = 0.0f;
} else {
roll = (float) -atan2(GRAVITY, lateralMag) + PI/2.0f;
}
// pitch
pitch = (float) -atan(-m_vel.y / sqrt((m_vel.z*m_vel.z) + (m_vel.x*m_vel.x)));
// yaw
yaw = (float) atan2(-m_vel.x, -m_vel.z);
// 出力
m_ang.x = pitch;
m_ang.y = yaw;
m_ang.z = roll;
}
あと、今回は、水槽に関して、周期的な境界条件を使っています。
理由は、そうしないとぶつかるからで、次の回でちゃんと水槽の中を泳がせます。
あと、CBoid の線形リストの説明をしていないですが、これは、基本的なアルゴリズムの本を読んでください。
また、初期化の説明もしていませんが、位置や速度を適当に設定しているだけです。
あと、毎フレーム、各 CBoid に関して、FlockIt をしているということでしょうか。
表示されている魚は CFish クラスとして表現されています。
前回説明したモデル表示の CMyModel クラスと、今回の CBoid の多重継承になっています。
CBoid クラスで、決定した座標を、CMyModel クラスの座標にコピーして、表示します。
そのまま、CBoid クラスの位置を採用しても良いのですが、ゲームなどで用いるときは、
登場シーンやパワーアップシーンなどの、さまざまな演出が入りますので、
分離しておくほうが良いのではないでしょうか？
とりあえず、群れをなして動くものを作れました。
後は、障害物を避けさせたり、『敵』を導入したいと思います。
今回気がついたのですが、BOID一個一個がモデルを読みにいくので、非常な無駄が発生しています。
これを回避する、リソース管理もしたいです。
魚にアニメも入れたいですし、fps に依存したい動きもさせたいです。
あと、足りないの在ったら、いってください。