経路探索A*探索アルゴリズムをやってみた
経路探索
経路探索の種類としては以下の通り - ダイクストラ法 - A*探索アルゴリズム
また、探索の仕方や、評価に使う値の例として、以下のようなものがあります。 探索の仕方（どのように、次の場所を確認していくか？） - 幅優先探索（開始地点基準で、離れた距離が同様の箇所を順番に探索していく。） - 深さ優先探索（選択した所が、探索する場所がなくなるまで探索していく）
評価に使う値の例（どれくらい移動にかかるコストがかかるかなどを計るためのもの） - ヒューリスティックコスト（そのマスに対して、移動するためのコスト） - マンハッタン距離（開始位置からゴール位置からの距離） - ユークリッド距離（2点間の直線距離）
ダイクストラ法とは？
候補を順番に確認していく方法。 そのため、確認の仕方によっては、最後の最後まで目的とした場所が見つからない場合がある。
そこで、その検索回数を減らすために後述するA*探索アルゴリズムがあります。
A*探索アルゴリズムとは？
ゲームによって、探索の制限が変化する場合はあるかもしれませんが、検索してよく出てくる基本的な内容としては以下の通りです。
探索の際に、 探索している場所からのゴールの地点との距離 ＋ 探索している場所が、スタート地点から通ってきた距離を通ってきたか？ という評価値を設定して、もっとも低い場所を検索していくというスタイルです。
これを実装した内容が以下のツイートです。
やっとここまで来た。こういう作りなんでしょ。ってとこまでは理解してたんだけど、コードに落とし込むのにどちゃくそ時間かかった。
— へりえる@色々制作中 (@herie270714) 2021年2月27日
A*法 障害物あり pic.twitter.com/ntaBvuRdiK
なお、障害物があったときはこんな感じの探索結果
