【ゲームAI】ポテンシャル関数

概要

ゲームAIに関して勉強し始めたので，その備忘録．
本記事ではポテンシャル関数について記述する．

ポテンシャル関数に関する説明は，使用される分野によって多種多様である．
本記事では，分子動力学で用いられる，原子間距離に応じた相互作用力を求める関数を指す．
実装する関数はレナード・ジョーンズ・ポテンシャル関数である．

なお，本記事では連続的なゲームを想定したサンプルを示す．
離散的なゲームでのポテンシャル関数も，考え方は同じである．

参考書

ありきたりではあるが以下の書籍を用いた．
ゲーム開発者のためのAI入門

(どうでもいいが，この本のサンプルを取得する方法がわからない)
(書籍中に記述されているURLに飛んでもダメだった)
(できることならサンプルがほしいので，何か知っている方は教えてほしい．)

レナード・ジョーンズ・ポテンシャル関数

概要

以下の式を用いてることで，原子間のポテンシャルを計算できる．
(実際にはもっと複雑な式だが，ここではパラメータを少なくするために，ある程度まとめてある．)
U = -( A / r^n ) + ( B / r^m )
Uはポテンシャル，Aは引力の大きさ，Bは斥力の大きさ，
rは原子間距離，nは引力の減衰度合い，mは斥力の減衰度合い.

この式は，ポテンシャル曲線を表す簡易的なものであるため，
厳密な結果は得られない．しかし，大抵の場合はこの式だけで事足りるらしい．

調整するパラメータはA，B，n，mである．
AとBは各力の大きさである．目標に近づきたければAを大きくして，離れたければBを大きくする．
nとmは各力が影響を及ぼす範囲である．小さくすれば範囲は広がり，大きくすれば範囲は狭くなる．

事前準備

ベクトル計算用の構造体，便利関数の準備と，
角度計算用のマクロの準備を行う．

//角度計算用マクロ.
#define L_PI        (3.1415f)
#define L_2PI       (6.2830f)
#define L_H_DEG     (180.0000f)
#define L_DEG       (360.0000f)
#define DEG2RAD(e) ((e)*(L_PI)/(L_H_DEG))
#define RAD2DEG(e) ((e)*(L_H_DEG)/(L_PI))
#define ADJUST_RAD(e) (((e)<(0.0000f))?(e)+(L_2PI):((e)>(L_2PI))?(e)-(L_2PI):(e))
#define ADJUST_DEG(e) (((e)<(0.0000f))?(e)+(L_DEG):((e)>(L_DEG))?(e)-(L_DEG):(e))

//ベクトル構造体.
#define VECTOR SVector2D<float>
template <class T>
struct SVector2D
{
    typedef T DataType;
    T x;
    T y;
    SVector2D(){ Init(); }
    void Init()
    {
        x = T();
        y = T();
    }
    SVector2D   operator +  ( const SVector2D& e ) const { SVector2D tmp; tmp.x = x + e.x; tmp.y = y + e.y; return tmp; }
    SVector2D&  operator += ( const SVector2D& e ){ x += e.x; y += e.y; return (*this); }
    SVector2D   operator -  ( const SVector2D& e ) const { SVector2D tmp; tmp.x = x - e.x; tmp.y = y - e.y; return tmp; }
    SVector2D&  operator -= ( const SVector2D& e ){ x -= e.x; y -= e.y; return (*this); }
    T           operator *  ( const SVector2D& e ) const { return ( x * e.x ) + ( y * e.y ); }
    SVector2D&  operator *= ( const int e ){ x *= e; y *= e; return (*this); }
    SVector2D&  operator *= ( const float e ){ x *= e; y *= e; return (*this); }
    SVector2D&  operator /= ( const int e ){ x /= e; y /= e; return (*this); }
    SVector2D&  operator /= ( const float e ){ x /= e; y /= e; return (*this); }
};

//数学関連の関数群.
namespace LMath
{
    VECTOR::DataType GetScalar( VECTOR vec )
    {
        return sqrtf( vec.x * vec.x + vec.y * vec.y );
    }

    VECTOR Normalize( VECTOR vec )
    {
        const VECTOR::DataType vecLen = GetScalar( vec );
        vec.x /= vecLen;
        vec.y /= vecLen;
        return vec;
    }

    VECTOR Normalize( VECTOR from, VECTOR to )
    {
        VECTOR tmp = to - from;
        return Normalize( tmp );
    }

    float GetRotateRad( const float from, const float to )
    {
        //角度候補1.
        const float dir1st      = ( to - from );
        const float dir1stVal   = fabsf( dir1st );

        //角度候補2.
        const float dir2ndVal   = ( L_2PI - dir1stVal );
        const float dir2nd      = ((dir1st>=0.0f)?-1.0f:1.0f) * dir2ndVal;

        //絶対値が小さい方を採用.
        return ( dir1stVal > dir2ndVal ) ? dir2nd : dir1st;
    }

    bool IsCollisionCircle( const VECTOR& pos1, const VECTOR& pos2, const float r )
    {
        VECTOR tmp = pos1 - pos2;
        return ( GetScalar( tmp ) < r );
    }
};

サンプル

//ポテンシャル関数のタイプ.
enum POTENTIAL_TYPE
{
    POTENTIAL_TYPE_TRACK = 0,
    POTENTIAL_TYPE_ESCAPE,
    POTENTIAL_TYPE_INTERCEPT,
    POTENTIAL_TYPE_SWARMING,
    POTENTIAL_TYPE_OBS_AVOID,
    POTENTIAL_TYPE_NUM,
    POTENTIAL_TYPE_INVALID = -1,
};
static bool IsValid( POTENTIAL_TYPE e ){ return ( 0 <= e && e < POTENTIAL_TYPE_NUM ); }

//ポテンシャル関数用パラメータ.
struct SParam
{
    float attraction;
    float repulsion;
    float atDamping;
    float reDamping;
};

//各ポテンシャル関数の具体的なパラメータ.
SParam g_param[POTENTIAL_TYPE_NUM] = 
{
    { 50000.0f, 750000.0f, 2.0f, 3.0f },
    { 0.0f, 40000.0f, 2.0f, 2.0f },
    { 10000.0f, 40000.0f, 2.0f, 3.0f },
    { 10000.0f, 50000.0f, 1.0f, 2.0f },
    { 0.0f, 75000.0f, 1.0f, 2.0f },
};

/*
    レナード・ジョーンズ・ポテンシャル関数.

    物理学において，原子間の引力，斥力，ポテンシャルの関係を示す，
    以下の式がある．

    U = -( A / r^n ) + ( B / r^m )

    Uはポテンシャル，Aは引力の大きさ，Bは斥力の大きさ，
    rは原子間距離，nは引力の減衰度合い，mは斥力の減衰度合い.

    これらのパラメータを調整することで，
    追跡，逃避，迎撃，群れ行動，障害回避などを実現できる．

    迎撃，群れ行動，障害回避については，書籍にあるような，
    なめらかな動きにはならなかった．どこか間違いがあるらしい．

*/

#define VEL_BORDER              (0.01f)
#define SWARMING_RANGE_BORDER   (30.0f)
#define OBS_AVOID_RANGE_BORDER  (40.0f)

//レナード・ジョーンズ・ポテンシャル関数.
float GetPotensial( const SParam& param, const float r )
{
    return -( param.attraction / (float)pow( r, param.atDamping ) ) + ( param.repulsion / (float)pow( r, param.reDamping ) );
}

//パラメータ更新.
void UpdateParam( 
    POTENTIAL_TYPE type, 
    float& selfNextDir, 
    float& selfNextVel,
    const float& selfNowDir,
    const float& selfNowVel,
    const VECTOR& selfNowPos,
    const VECTOR& targetPos,
    const float border
    )
{
    //方向が自分向きであることに注意.
    VECTOR dirVec = selfNowPos - targetPos;
    const float r = LMath::GetScalar( dirVec );

    if( ( border >= 0.0f ) && ( r > border ) ){ return; }

    //ポテンシャル計算.
    const float potensial = GetPotensial( g_param[type], r );

    //ポテンシャルが閾値以上なので，方向と速度に影響を与える.
    if( fabsf( potensial ) >= VEL_BORDER ){
        float dir = ADJUST_RAD( atan2f( -dirVec.y, dirVec.x ) );
        if( potensial < 0.0f ){
            //引力が強いので目標に近づくように角度を反転.
            dir = ADJUST_RAD( dir + L_PI );
        }

        selfNextDir += LMath::GetRotateRad( selfNowDir, dir );
        selfNextVel += potensial - selfNowVel;
    }
}

void Update( VECTOR& pos, float& dir, float& vel )
{
    static const bool bTrack        = false;
    static const bool bEscape       = false;
    static const bool bIntercept    = false;
    static const bool bSwarming     = false;
    static const bool bObsAvoid     = false;

    const VECTOR nowPos = pos;  
    const float nowDir = dir;
    const float nowVel = vel;

    //追跡.
    if( bTrack )
    {
        VECTOR targetPos = /*追い駆けたい対象*/;
        UpdateParam( POTENTIAL_TYPE_TRACK, dir, vel, nowDir, nowVel, nowPos, targetPos, -1.0f );        
    }

    //逃避.
    if( bEscape )
    {
        VECTOR targetPos = /*逃げたい対象*/;
        UpdateParam( POTENTIAL_TYPE_ESCAPE, dir, vel, nowDir, nowVel, nowPos, targetPos, -1.0f );
    }

    //迎撃.
    if( bIntercept )
    {
        VECTOR targetPos = /*迎撃したい対象*/;
        UpdateParam( POTENTIAL_TYPE_INTERCEPT, dir, vel, nowDir, nowVel, nowPos, targetPos, -1.0f );
    }

    //群れ.
    if( bSwarming )
    {
        VECTOR* posArray = /*動的モジュールの位置リスト*/;
        const int posNum = /*動的モジュールのリストサイズ*/;
        for( int i = 0; i < posNum; ++i ){
            VECTOR targetPos = posArray[i];
            UpdateParam( POTENTIAL_TYPE_SWARMING, dir, vel, nowDir, nowVel, nowPos, targetPos, SWARMING_RANGE_BORDER );
        }
    }

    //障害回避.
    if( bObsAvoid )
    {
        VECTOR* posArray = /*障害物の位置リスト*/;
        const int posNum = /*障害物のリストサイズ*/;
        for( int i = 0; i < posNum; ++i ){
            VECTOR targetPos = posArray[i];
            UpdateParam( POTENTIAL_TYPE_OBS_AVOID, dir, vel, nowDir, nowVel, nowPos, targetPos, OBS_AVOID_RANGE_BORDER );
        }
    }

    //0～L_2PIの範囲に入るように調整.
    while( (dir < 0.000f) || (dir > L_2PI) ){
        dir = ADJUST_RAD( dir );
    }

    //最大速度は1.0f.
    vel = min( fabsf( vel ), 1.0f );

    pos.x += vel * cosf( dir );
    pos.y += vel * -sinf( dir );
}

基本的に，公式通りポテンシャルを計算し，
適用するだけである．

ポテンシャルが正である場合は斥力が強く，
負である場合は引力が強い．

今回のサンプルでは，ポテンシャルの絶対値を速度に，
ポテンシャルの符号を向きに反映させている．

ポテンシャル計算を組み合わせることで，色々な動作をさせることができる．

注意

コード上では，各行動をboolで分岐させているが，
実際に使う場合は，外部データに任せる，ステートで管理する，など，
状況に応じて変化するようにした方が良い．

上記サンプルはどこかバグがあるらしく，
参考書籍のように滑らかな動作をしなかった．
上記コードを使用する場合は，しっかり動作を確認してから使用してほしい．

動作状況

手元のビジュアライザで動作確認をしてみた．
障害回避と群れ行動があまり綺麗にできていない．
おそらくバグだとは思うが，書籍通りに実装してみると，
こうなってしまう気はする…

追跡＋逃避

一定以上近づいたら，その距離を保とうとする．
すごい追っかけファンだけど一定の理性はあるファン，みたいなのを
再現する時に使える．

追跡＋障害回避

ちょっと賢いストーカー．
でも，障害物に引っかかる馬鹿なストーカー．

群れ＋障害回避

この群れ行動は，フロッキングではなく，スウォーミングという．
鳥や魚の群れではなく，蜂や蛾の群れに近い運動をする．
二人組ができると安定したり，三人組になるとモニョモニョしたり，
原子感が出ている気もする．

総括

簡単な式で色々な状況に対応できるというのは強力だと思う．
が，直感的ではないパラメータをいじる必要があったり，
求めている動きにするための試行錯誤が大量に必要だったりと，
コストがかさむ可能性は否めない．
使いどころをしっかり考える必要がある．