はじめに

NPCの移動処理などに使う探索ルーチンを勉強。


障害物の向こうのキャラを目指して歩けるようにします。

サンプルコードダウンロード：
Search.zip
releaseフォルダの中に実行ファイルがあります。
使い方が書いてませんが、ポチポチ押していればなんとなくわかるかなーという期待をこめて。
いろいろ試してみていただければ。探索中の様子は見ていてなかなかおもしろいです。

解説 

今回は開始地点から現在位置、最終地点から現在位置の歩数を元にスコアを割り出し、そのスコアが最小となる経路を進んでいくことで最短ルートを割り出そうという方法です。


わかりやすいようにこの小さなマップで検証します。
画面左のヒヨコが右のニワトリ目指して進んでいきます。


まず、上下左右、動ける場所を特定します。今回は障害物が無いので４方向共有効です。


次にスコアを算出します。
�@の場合だと、ヒヨコから１歩、ニワトリから５歩（障害物は考慮しない）なので、スコアは６となります。
また、後から開始位置への経路を導き出せるように開始位置への方向も記録しておきます。
これを�@〜�Cまで繰り返します。

４方向算出したので次へ進みます。
次の１歩はスコアが小さいところへ進みます。右側が４で最小ですので、右へ進みます。
進んだ後は最初と同じように進める場所を特定します。今回は上と下の２方向です。
そして、一度処理した場所は印をつけておきます（この図では黒字を印としています）。

最初と同じようにスコアを算出します。
そして次の１歩へ。

同じスコアの場合はどれを進むのが一番効率がいいのかよくわかりませんのでとりあえず順番に進みます。

今回最高の８が出ました。他の６の場所からも進めてみます。

この５種類です。

すべて８になったようです。
次は８の場所から順番に調べていきます。

今度は４箇所見つかりました。
スコアを算出します。

左側の２つはスコアが１０になりました。右側が８ということでそちらへ進みます。


後は同じように進める方向を探す→スコアを求める→スコアの小さい場所へ進む…
を繰り返していきます。
何度か繰り返しているうちにニワトリへ到着することができました。


最後に最短ルートを求めるということで、ニワトリからヒヨコまで、記録していた向きを逆にしながらたどっていきます。
そしてできあがったのが図のルートです。

一度探索した場所を覚えておくというだけでも、いつかはたどり着けますね（道があれば）。
後は最終地点が頻繁に移動する場合にどう対処するかが問題になります。毎回この探索をしていると調べ続けてしまって全然進まないという状態に…
ですので、障害物にぶつかるまでは最終地点の方向へ無条件に進ませてしまって、ぶつかってから検索するようにするというのが良いのではないかなと思います。