水族館を作ろう:BOIDの基本


~群れをつくって泳ぎます~




■はじめに

前回は、とりあえず魚を泳がせました。
今回は、BOIDの基本的な部分を組み込んで、群れをなして泳がせてみます。

今回のソースは、次のものです。

今回のメインは boid.cpp です。
Game Programming Gems を参考にしました(それのシンプルバージョンとも言う)。
関数名なども、なるべくあわせるようにしています。

■基本原理

Craig Raynolds は、1987 年の SIGGRAPH で、 「Flocks, Herds, and Schools : A Distributed Behavioral Model」を発表しました。
この論文は、3つの理解しやすいルールを規定するだけで、動物の群れをシミュレーションできるというものです。
そのルールとは、

Separation(引き離し)一定距離より近くに間を取らない
Alignment(整列)仲間とスピードと方向を合わせる。
Cohesion(結合)グループの中心へ向かおうとする。

です。
ここで出てくる BOID という単語は、(鳥)バードとアンドロイドを組み合わせた造語で、鳥だけでなく、魚や馬の群れにも この単語は使われています。
今回のプログラムでは、魚の一匹一匹を表現するクラスを CBoid クラスとします。

■引き離し(Separation)

われわれは、歩くときや会話するときなど、自然といい感じの距離を取って生活します。

これが『引き離し』です。

プログラムでは、次のように実装します。
関数の返り値が、『引き離し』による速度変化量(力)になります。

// ----------------------------------------------------------------------------
// 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)を変えます。 但し、泳ぐ速さには、限界がありますし、ひとかきで進む大きさがあるので、 力の上限と下限を設けます。

■整列(Alignment)

さて、次は、『整列』です。

とりあえず、一番近い仲間の速度を見て、その速度にだんだんあわせるようにします。

// ----------------------------------------------------------------------------
// Rule #2 (Alignment) 仲間とスピードと方向を合わせる。
//-----------------------------------------------------------------------------
D3DXVECTOR3 CBoid::MatchHeading (void)
{
    // 一番近い仲間の速さの向きを調べる
    D3DXVECTOR3 change = m_nearest_flockmate->m_vel;
    D3DXVec3Normalize(&change, &change);

    // だんだん速度をあわせるように調整する
    change *= MIN_URGENCY;

    return (change);
}

■結合(Cohesion)

最後に、『結合』です。

仲間の中心位置を求めて、そちらに動かします。。

// ----------------------------------------------------------------------------
// 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 の一回の移動

では、以上を組み合わせて、一フレームでの 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 に依存したい動きもさせたいです。

あと、足りないの在ったら、いってください。





もどる

imagire@gmail.com