【Unity】【理論編】A*で最短経路を探索する

f:id:halya_11:20180725233207p:plain

A*アルゴリズムで最短経路を探索してみます。長くなったのでまずは理論編のみ。

実装編も書きました。

下準備

A*の考え方を説明するうえで、まずは下図のようなグリッドを考えます。
Wall以外のセルを通ってStartからGoalまで到達するための最短経路を求めます。

f:id:halya_11:20180725224742p:plain

隣接セルを取得してweightを計算する

まずStartセルに隣接するセルを取得します。

取得セルごとにStartからの道のりとGoalまでの距離を求め、それらを加算してweightとします。
weightが低いものを「採用」とし、次のセルを検索する際の起点とします。

また、前のセルをpreviousとして保存しておきます。

f:id:halya_11:20180725225442p:plain

計算を1セル進めて末端セルを比較する

次に、前回「採用」となったセルに隣接するセルを取得します。
ただしすでに計算済みのセルは除きます。

計算は前回と同様に行い、まだ隣接するセルを取得していないセル、
つまり末端のセルのうち、weightが最も低いものを「採用」とします。

f:id:halya_11:20180725230924p:plain

末端セルの最低weightが同じ場合はどちらかを「採用」する

同様に、「採用」セルから隣接するセルを取得して進めます。
下図のように末端セルのweightが同じになった場合には適当にどちらかを「採用」とします。
今回は(0, 1)のセルを「採用」としてみます。

f:id:halya_11:20180725231813p:plain

さらに計算を進める

同様に計算を進めます。
今度は末端セルのうち(1, 1)と(3, 0)のweightが4で最低となりました。
今回は(3, 0)のセルを「採用」とします。

f:id:halya_11:20180725231905p:plain

Goalを発見したら探索完了とする

「採用」セルの隣接セルを取得したところ、Goalが見つかりました。
Goalが見つかったらその時点で探索完了とします。

f:id:halya_11:20180725232052p:plain

GoalからStartまでの道のりを逆に辿る

Goalを発見したら後はpreviousのセルを辿っていきます。
それらのセルが最短経路となります。

f:id:halya_11:20180725233207p:plain

以上で最短経路が求められました。

関連

light11.hatenadiary.com