A*アルゴリズムで最短経路を探索してみます。長くなったのでまずは理論編のみ。
下準備
A*の考え方を説明するうえで、まずは下図のようなグリッドを考えます。
Wall以外のセルを通ってStartからGoalまで到達するための最短経路を求めます。
隣接セルを取得してweightを計算する
まずStartセルに隣接するセルを取得します。
取得セルごとにStartからの道のりとGoalまでの距離を求め、それらを加算してweightとします。
weightが低いものを「採用」とし、次のセルを検索する際の起点とします。
また、前のセルをpreviousとして保存しておきます。
計算を1セル進めて末端セルを比較する
次に、前回「採用」となったセルに隣接するセルを取得します。
ただしすでに計算済みのセルは除きます。
計算は前回と同様に行い、まだ隣接するセルを取得していないセル、
つまり末端のセルのうち、weightが最も低いものを「採用」とします。
末端セルの最低weightが同じ場合はどちらかを「採用」する
同様に、「採用」セルから隣接するセルを取得して進めます。
下図のように末端セルのweightが同じになった場合には適当にどちらかを「採用」とします。
今回は(0, 1)のセルを「採用」としてみます。
さらに計算を進める
同様に計算を進めます。
今度は末端セルのうち(1, 1)と(3, 0)のweightが4で最低となりました。
今回は(3, 0)のセルを「採用」とします。
Goalを発見したら探索完了とする
「採用」セルの隣接セルを取得したところ、Goalが見つかりました。
Goalが見つかったらその時点で探索完了とします。
GoalからStartまでの道のりを逆に辿る
Goalを発見したら後はpreviousのセルを辿っていきます。
それらのセルが最短経路となります。
以上で最短経路が求められました。
