なおしのこれまで、これから

学んだこと・感じたこと・やりたいこと

【Boidsアルゴリズム】球体の障害物を回避させるアルゴリズムを考える

目次

始めに

過去のBoidsに関する記事です。Boidsに関してはここではあまり触れないのでご了承ください。

過去記事



障害物から"逃げる"

始めに障害物から逃げる実装について簡単にお話します。

  1. 障害物の中心座標から個体へのベクトル  \vec{p} を求めて、ベクトルの長さが障害物から逃げる範囲の半径  r_e 以下であるかをチェック
  2. 個体が範囲内である場合はベクトル  \vec{p} を使って斥力を求めて、個体の速度ベクトルに加算する


結果

こちらを実装した結果が次のgifになります。見て分かる通り、この実装だけでは"避ける"ではなく"逃げる"となり、障害物へ向かってくる個体はそのままぶつかって跳ね返る挙動をします。


この方法でパラメータを調整したり、斥力を距離に反比例するようにしても避けるような挙動を作るのは難しかったです。



障害物を"回避する"

"逃げる"とは別に"回避する"をBoidsに実装します。

障害物を回避する方法は次のようになります。

  1. 障害物を回避する範囲内にいる、かつ逃げる範囲外にいるかチェック
  2. 前方向に障害物があるかをチェック
  3. 個体の速度ベクトル  \vec{v} を延長して、障害物の中心点との距離  d を求めて障害物から逃げる範囲の半径  r_e 以下であるかをチェック
  4. 1~3の条件を満たした個体の速度ベクトル  \vec{v} と、個体から障害物の中心点へのベクトル  \vec{o} との外積を計算して回転軸を求める。
  5. 回転軸と各速度を組み合わせて、速度ベクトルを回転させる。


1. 障害物を回避する範囲内にいる、かつ逃げる範囲外にいるか

こちらは個体から障害物への距離  d を求めて、それが  r_e <  d <=  r_a であるかをチェックします。( r_e : 逃げる範囲、 r_a : 回避範囲 )範囲外の個体は回避処理は適用させません。


2. 前方向に障害物があるかをチェック

個体の速度ベクトル  \vec{v} と個体から障害物へのベクトル  \vec{o} との内積  dot(\vec{v}, \vec{o}) を求めます。(内積を求める前に2つのベクトルを正規化する。) 内積が0以下の場合は  \vec{v} \vec{o} がなす角が鈍角になり、前方に障害物がない状態になります。なので、この場合は回避処理は行いません。


3. 個体の速度ベクトル  \vec{v} を延長して、障害物の中心点との距離  d を求めて障害物から逃げる範囲の半径  r_e 以下であるかをチェック

個体の速度ベクトルをまっすぐ延ばして直線を作ります。次に、障害物の中心点Oから直線に向けて垂直な線分OPを作って、その線分の距離  d を求めます。

この距離  d が逃げる範囲  r_e 以下であるかをチェックします。


こちらの計算は次のように行います。

  1. 個体の速度ベクトル  \vec{v} と 個体から障害物の中心点へのベクトル  \vec{o} との外積  cross(\vec{v}, \vec{o}) を求める
  2. 求めた外積のベクトルの長さ  length を計算して、速度ベクトルの長さ  |\vec{v}| で割って距離  dを求める
  3. 距離  d r_e 以下であるかチェックする

上記を1つの式にまとめますと次にようになります。


d =  \displaystyle\frac{ |cross(\vec{v}, \vec{o})| }{|\vec{v}|}

外積で求められるベクトルの大きさは2つのベクトルが生成する平行四辺形の面積になる性質があります。 (参考 : 「外積の長さ = 平行四辺形の面積」 証明  - 理数アラカルト -

次に底辺をなすベクトル  \vec{v} の大きさで割ることで平行四辺形の高さ = 中心点からの直線への距離を求められます。


4, 5. 回転軸を求めて速度ベクトルを回転させる

これまでの条件を満たした個体に対して障害物を避けるような回転を加えます。

回転軸は3.で求めた外積の単位ベクトル  \vec{A} になります。この回転軸と各速度を組み合わせて回転を生成します。

回転の生成ではロドリゲスの回転公式を使っています。(参考 : 3D数学の復習と実践(ロドリゲスの回転公式) - なおしのこれまで、これから


後は個体の速度ベクトルに回転を適用することで、障害物を避けるような挙動ができます。


コード

以上の実装はComputeShaderで行っております。 参考程度にして頂けると助かります。

inline float3x3 CalcAvoidObstacleTorque(const float3 position, const float3 velocity)
{
    const float3 diff = _ObstaclePosition.xyz - position;
    const float distance = sqrt(dot(diff, diff));
    
    if(distance > _AvoidObstacleRadius || _EscapeObstacleRadius > distance) // 障害物を避ける範囲内にいるか?
    {
        return float3x3(float3(1, 0, 0), float3(0, 1, 0), float3(0, 0, 1));
    }

    const float3 target2ObstacleDirection = normalize(diff);
    const float3 forward = normalize(velocity);
    const float directionDot = dot(target2ObstacleDirection, forward);

    if(directionDot < 0) // 前方向に障害物がないか
    {
        return float3x3(float3(1, 0, 0), float3(0, 1, 0), float3(0, 0, 1));
    }

    const float3 forward2DiffCross = cross(forward, diff);
    const float forward2ObstacleDistance = length(forward2DiffCross);

    if(forward2ObstacleDistance > _EscapeObstacleRadius) // 障害物から逃げる範囲と速度ベクトルの直線が重なっていないか
    {
        return float3x3(float3(1, 0, 0), float3(0, 1, 0), float3(0, 0, 1));
    }

    const float crossElementSum = forward2DiffCross.x + forward2DiffCross.y + forward2DiffCross.z;
    const float3 axis = crossElementSum != 0 ? normalize(forward2DiffCross) : float3(0, 1, 0);
    
    return CalcRotateMatrixByAxis(axis, _AvoidObstacleAngularVelocity);
}


....
....

const float3x3 avoidTorque = CalcAvoidObstacleTorque(boidData.position, velocity);
const float3 avoidVelocity = mul(velocity, avoidTorque);


結果

見やすいようにBoidsの行動範囲を2次元にしています。 分かれずに球体に向かっていく個体は障害物を上下方向に避けようとして詰まっています。


応用

障害物を複数追加して動作するようにした結果は次にようになりました。 (はっきりした方法ではないですが、複数の障害物を回避する場合は回転軸を合成しています。)


障害物で輪っかを作ったら真ん中の穴を通ってくれました。



考察

問題点

この方法で障害物を組み合わせて壁や窪みを作った場合は上手く避けてくれません。(回避先については考慮されていない) この方法で避けられるのは線状のものに限られるでしょう。

壁や窪みが静的なオブジェクトであれば前回のような力場を一度だけ計算して、衝突判定させるのが良いかもしれません。

shitakami.hatenablog.com


複数の障害物に対しての厳密な回避を考える

複数の障害物が接触している場合は、1つの球体に合成して回避する方法もありかもしれません。(しかし、障害物の穴などを塞いでしまうかも)

一番良いと考えているのが、速度ベクトルをずらして複数のRayを飛ばして障害物に当たらないor障害物との交点が最も遠い方向に逃げるようにするのが良いかもしれません。

この方法についてはこちらの動画がとても参考になると思います。

www.youtube.com



最後に

今回は前回できなかったBoidsの回避について実装と考察を行いました。

成果物としては自分の求める要件を満たすものになったので、考察で述べた内容についてはまた遠い将来になると思われます。

これからはこの機能を作りたいコンテンツで使っていく予定です。



参考

今回のBoidsの実装は「Unity Gracphics Programming vol.1」を元にしています。

UnityGraphicsProgramming-vol1.pdf - Google ドライブ


回避のアルゴリズムを考えるうえでこちらの本の計算幾何学の内容を参考にしています。