#概要
ゲームAIに関して勉強し始めたので，その備忘録．
この記事ではLOS(Line Of Sight)アルゴリズムについて示す．
LOSアルゴリズムは，追跡や逃亡に使用する経路探索アルゴリズムで，
目標地点に向けて直線的な動きをするものを指す．(まんま照準的な)
実装内容は多種多様だと思うが，ここではブレゼンハムアルゴリズムを取り上げる．
この記事では離散的なゲームを想定したサンプルを示す．
連続的なゲームでの直線運動は，物理法則を用いない場合，
方向を表す単位ベクトルに速度を掛けあわせて，自分の位置ベクトルに加算するだけである．
物理法則を用いる場合は，用いる式による．
(無論，障害物がある場合はこの限りではない．)
#参考書
ありきたりではあるが以下の書籍を用いた．
ゲーム開発者のためのAI入門
#ブレゼンハムアルゴリズム
##概要
ブレゼンハムアルゴリズムは，元々はディスプレイに近似的な直線を描画するアルゴリズムである．
加減算やシフト演算のみで計算可能であることから，高速に動作するとされている．
離散的なゲームは，フィールドをグリッドで管理するため，このアルゴリズムをそのまま適用できる．
##サンプル
/*
---------------------------------------
|(a, b) | | | | |
|-------+-------+-------+-------+-------|
| |(a+i, |(a+i+1,| | |
| | b+j) | b+j) | | |
|-------+-------+-------+-------+-------|
| | |(a+i+1,| | |
| | | b+j+1)| | |
|-------+-------+-------+-------+-------|
| | | | |(a+dx, |
| | | | | b+dy) |
---------------------------------------
直線の方程式は以下
y = ( dy / dx )( x - a ) + b
a+i+1の状況において，理想的な直線は以下
y = ( dy / dx )( (a+i+1) - a ) + b
= ( dy / dx )( i+1 ) + b
a+i+1の状況において，一つ下のセルとの境界線は以下
y = ( (b+j) + (b+j+1) ) / 2
= b+j+0.5
a+i+1の状況において，b+jを選択するかb+j+1を選択するかを決める式は以下
計算結果が0よりも大きければb+j+1を選択することになる．
( b+j+0.5 ) <= ( dy / dx )( i+1 ) + b
0 <= ( dy / dx )( i+1 ) + b - ( b+j+0.5 )
0 <= ( dy / dx )( i+1 ) - ( j+0.5 )
除算を排除する
0 <= dy( i+1 ) - dx( j+0.5 )
小数を排除する
0 <= 2dy( i+1 ) - dx( 2j+1 )
上記式を用いて位置を計算する．
ただし，目的位置への距離がX軸方向に長い場合のみ有効．
毎フレームiを増やしていき，上記式の計算結果が0を超えた時点でjを増やす．
なお，目的位置との距離がY軸方向に長い場合の式は以下になる．
(計算方法は上記と同じ考え．)
0 <= 2dx( j+1 ) - dy( 2i+1 )
*/
#define NEXT_POS_MAX 100
POINT g_prevTargetPos; //1フレーム前の目標地点.
POINT g_nextStepPos[NEXT_POS_MAX];//移動経路.
int g_stepCount; //ステップ数.
void UpdateBresenham( POINT& now, POINT &target )
{
if( ( g_prevTargetPos.x == target.x ) && ( g_prevTargetPos.y == target.y ) ){
//目標地点が変わっていない場合は，前もって計算しておいたものを使う.
if( g_stepCount >= NEXT_POS_MAX ){ return; }
if( g_nextStepPos[ g_stepCount ].x < 0 && g_nextStepPos[ m_stepCount ].y < 0 ){
return;
}
}
else{
//目標地点が変わったので経路を再計算する.
g_stepCount = 0;
for( int i = 0; i < NEXT_POS_MAX; ++i ){
g_nextStepPos[i].x = g_nextStepPos[i].y = -1;
}
POINT pos = now;
int deltaX = target.x - pos.x;
int deltaY = target.y - pos.y;
const int stepX = ( deltaX >= 0 ) ? 1 : -1;
const int stepY = ( deltaY >= 0 ) ? 1 : -1;
deltaX = abs( deltaX );
deltaY = abs( deltaY );
if( deltaY > deltaX ){
//Y方向が長い.
int f = ( deltaX << 1 ) - deltaY; //条件式初期値.
for( int i = 0; i < deltaY; ++i ){
if( f >= 0 ){
pos.x += stepX; //X方向更新.
f -= ( deltaY << 1 ); //X方向の移動を加味.
}
pos.y += stepY; //Y方向更新.
f += ( deltaX << 1 ); //Y方向の移動を加味.
g_nextStepPos[ i ] = pos;
}
}
else{
//X方向が長い.
int f = ( deltaY << 1 ) - deltaX; //条件式初期値.
for( int i = 0; i < deltaX; ++i ){
if( f >= 0 ){
pos.y += stepY; //Y方向更新.
f -= ( deltaX << 1 ); //Y方向の移動を加味.
}
pos.x += stepX; //X方向更新.
f += ( deltaY << 1 ); //X方向の移動を加味.
g_nextStepPos[ i ] = pos;
}
}
g_prevTargetPos = target; //探索時の目標地点は保存しておく.
}
now = g_nextStepPos[ g_stepCount++ ];
}
上記サンプルはそのままだと正しく動かないはず．変数の初期化とかしてないので．
例えば，敵用戦略クラスを作成して，グローバル変数をメンバ変数に置き換えて，
クラスの初期化時に変数を初期化する，というようなことをすれば，ある程度ちゃんと動くはず．
##解説
基本的に，考え方はサンプル上に書いてある通りである．
注意点として，以下の二点がある．
###dxやdyがマイナスだった時も0 <= 2dy( i+1 ) - dx( 2j+1 )を使用して良いのか？
使用して良い．
というのも，上記式は数学でいう第一象限に絞った式だが，
式とは無関係な，セル選択時の移動方向の＋ーを変えるだけで，
全象限に対応できてしまうからである．
すなわち，この計算式を用いて取得したい情報は
【どのタイミングでX方向の移動，Y方向の移動を行うか】という情報である．
(個人的な考察の結果そう思っただけなので，間違っていたらごめんなさい．)
ただし，上記に示した通り，0 <= 2dy( i+1 ) - dx( 2j+1 )は第一象限に絞った式なので，
実際にコードに落としこむ際には，
dxがマイナスだった時はX方向の移動をマイナスに，
dyがマイナスだった時はY方向の移動をマイナスに設定して，
dxやdyは絶対値にする必要がある．
###目標地点が変わったら全経路更新，ではなく，毎フレーム一歩先を計算すればいいのでは？
実はそれだと上手く行かない．
図で書いてみればわかるが，始点→終点の直線の位置が毎フレーム変わってしまい，
その上を辿る形になるため，直線というよりは若干弧を描く形になってしまう．
##参考サイト
ブレゼンハムアルゴリズムの原理はここがとてもわかり易かった．
#総括
スパロボなどの戦略シミュレーションゲームや，
広大なフィールドをグリッドで分割して大雑把な経路探索を行う，
といったケースで使えるかもしれない．