大半のゲームでは敵キャラが登場するが、
主人公に迫ってくるときに
障害物に引っかかってしまうと不細工なので
適切なルートを判断させる処理が必要になる。
そういったルート探索処理について調べるとまず挙がるのが
「A*（エースター）」と呼ばれるアルゴリズムだ。
かなり古くから存在する手法とはいえ
いまだに有益なのでぜひ理解しておきたいが、
普通に調べると「ダイクストラ」とか「ヒューリスティクス」とか
「f(n)=g(n)+h(n)」のような難しそうな言葉が出てきて挫折しやすい。
そこで今回は専門的・数学的な言葉は一切使わず、
単純に理屈だけが理解できる解説記事を書いてみた。
今回は簡略化のため、マップをマス目で区切り、
キャラクターは前後左右の４方向移動とする。
目的地に向かって単純に接近するような処理だと
障害物を回り込むことができないので
引っかかったまま動けない状態になってしまうが、
A*アルゴリズムならこれを解決することができる。
まずキャラクターの周辺にあるセルを調べる。
調査途中のセルを「オープンセル」と呼ぶ。
オープンセルには「現在地からそのセルまでの距離(=1)」と
「ゴールからそのセルまでの距離(=8)」の合計(=9)を格納する。
これがそのセルを経由するときのコストとなる。
このコスト計算には精度の異なるいろいろな方法があるが、
今回はA*アルゴリズムの理解を優先するため、
縦方向と横方向の移動量を単純に合計したものとする。
（そのぐらい簡易なやり方でも割とちゃんと動く）
同時に「どのセルからここに来たか」という親セルの情報も記録する。
今回はキャラクターが立っている場所が親セルだ。
キャラクターが隣接しているセルについて
それぞれ同様の処理をしていくとこのようになる。
この４つはまだ調査途中なのでオープンセルのまま。
■=オープンセル ■=クローズセル
次に、すべてのオープンセルの中から
一番コストの低いものを「クローズセル」に切り替え、
そこを基準に隣接したセルをオープンセルに変えて
「コスト計算と親セル情報の記録」を行う。
ただし、たとえ隣接していても
オープンセルやクローズセルや障害物セルなら除外し、
まだチェックしたことがないセルに限定して作業を行う。
■=オープンセル ■=クローズセル
隣接したセルをすべて調べ終わったら
そのクローズセルは作業終了となる。
ぞして再びすべてのオープンセルの中から
一番コストの低いものを基準に、同じ処理を繰り返す。
■=オープンセル ■=クローズセル
そうなると次はこのセルだが、隣接しているものが
オープンセルとクローズセルと障害物セルばかりなので
何も作業せずクローズセルに切り替わるだけで終了。
■=オープンセル ■=クローズセル
次はこのセルなので、未着手のセル（白色）に限定して
これまで同様の作業を行う。
■=オープンセル ■=クローズセル
そうやって作業を繰り返していると
「隣接したセルがゴール」となる場面が来る。
コスト計算した各セルには親セルの情報が格納されているので
どのセルからゴールに到達したのか明らかだし、
さらにその前のセルがどこだったかもわかる。
それらが「ルートとして確定したセル」となる。
つまり、ゴール側から逆に親セルをたどっていけば
キャラクターのいる場所までのルートが確定するのだ。
この考え方がA*アルゴリズムの基本で、
あとはコスト計算の精度アップや
処理負荷の軽減などを工夫する程度だ。
3Dゲームの場合はマス目状とは違う滑らかな地形になるが、
チェックポイントのようなものを定期的に置いて
行き来できるポイント間をつなぐようにすれば
理屈的には同じ考え方で作ることができる。
これを手作業で設定するのが大変なら、
マップ全体に一定間隔でポイントを配置したあと
障害物と重なっている部分を除去する処理を作って
ゲーム開始前にあらかじめ実行しておくようにすればいい。
味方キャラでも敵キャラでも
障害物をうまく避けながら移動すると非常に賢く見えるし、
学生作品に取り入れるとアピール材料にもなるので
ぜひ実装にチャレンジしてみて欲しい。
