成果物
シンプルなA*アルゴリズム
二乗距離を使うと速かったです。
迷路を解く
今回は、A*アルゴリズムと迷路生成アルゴリズムを組み合わせて、自動で作った迷路をまた自動で解くプログラムを作りました。どうやら迷路生成アルゴリズムとA*の相性が悪いようで、少ししか高速化できていないです。
仕組み
迷路自動生成についてはこちらをご覧ください。
ただ、今回は、ブロック自体が壁になるので、少々プログラムを変更しました。考え方は同じです。
A*アルゴリズムについては、こちらを参考にしました。Part2,3もありますが、大部分はPart1で作ります。今回は、斜めに進むのは禁止にしています。
ダイクストラ
垂らした水が広がっていくように、探索していくアルゴリズムです。ビジュアライズしてみたの記事が参考になります。ゴールの位置などは、考慮されません。
A*アルゴリズム
A*アルゴリズムは、ダイクストラ法を発展させたもので、スタート地点からの道のりと、その地点の価値を見積るヒューリスティック関数（だとえば、ゴールからの距離）を合わせた数値をもとに評価し、最短経路を求めるアルゴリズムです。そもそも迷路を解くアルゴリズムではないですが、迷路であっても、最短経路、トップレベルの速さで解くことができます。
作り方・コード
今回のA*アルゴリズムの実装方法
ターゲットの周辺のマスを評価します。評価したマスを探索中のリストに入れます。ターゲットを、探索中から削除し、探索済みの中に入れます。ターゲットを探索中の中で評価値が最も低いものに変更します。繰り返します。
たった三行の文で書きましたが、理解して、コードにするのはかなり難しいです。
今回は、リポジトリを作りました。
A_star_Simpleが障害物をよけるシンプルなプログラムで、A_star_MazeSolveが迷路を解くプログラムです。
