java - A* パスファインディングに関する質問

Question

さて、単純なタイルマップ配列に A* パスファインディングを実装しようとしていますが、いくつか質問があります。

開いた/閉じたリストの場合、arrayList を使用して、見つかったすべてのポイントを格納する必要がありますか、それともそれらを格納するためのより良い方法がありますか?

次に、隣人をチェックするにはどうすればよいですか? 開始タイルを取り、上下左右をチェックして、コストが最も低いタイルが格納されているかどうかを確認します。

Answer 1

私は過去にPriorityQueueオープンリスト用にこれを実装しました。コンパレーターは、A* ヒューリスティック値で機能します。これは非常にクリーンで、挿入ごとに O(log n) のパフォーマンスが得られ、最悪のケースがポーリングされます。標準の実装よりも優れているため、ポーリングを償却して O(1) に改善できます。リストについてはvisited、タイルでフラグを使用するか、別のHashSet. 後者には、初期化コストがなく、挿入とメンバーシップの漸近コストが同じであるという利点があります。ただし、定数係数は、ブール マップ値をチェックする場合よりもハッシュの方が大きくなります。

Answer 2

ゲーム、つまり高 fps ビデオ ゲームにこれを実装していない限り、ArrayList として使用することでパフォーマンスが大幅に低下することはないと思いますが、問題はありません。

質問の 2 番目の部分については、各ノードに 4 方向の接続しかないと仮定すると、はい、各ネイバーの単純な順次チェックが機能します。

Answer 3

「タイルマップ配列」が何であるかはわかりませんが、「見つけた点」とは、検索ツリー内のノードを意味していると思います。まだ調べていないノードを格納するデータ構造は、ダイクストラのアルゴリズムから継承された 2 つの重要なプロパティを満たす必要があります。

1. 最低コストのノードのフェッチは、少なくとも O( n )高速である必要があります
2. より短いパスを見つけたら、ノードのコストを下げたいと思うでしょう。

前者は、ヒープを使用して実現できます。バイナリ ヒープはかなり簡単に実装できます。フィボナッチ ヒープは漸近的なパフォーマンスを向上させますが、ほとんどのアプリケーションでは必要ありません。私がこれまでに見たライブラリのほとんどのヒープは、後者の要件をサポートしていません。これは、キーの減少と呼ばれることがよくあります。これを実装するには、ノードはヒープ内の現在の位置に関する情報を保持する必要があります。そうすれば、ノードがそのコストを変更したときに、O(1) で現在の位置を取得し、O(log n ) で位置を調整できます。また、同じ変数を使用して、アイテムがヒープにあるかどうかを判断できます。

では、2 番目の質問です。通常、ヒープから最小要素を削除してコストをチェックします。つまり、各ナイトバーについて、それをヒープに挿入するか、すでにヒープにある場合は、新しいコストの方が優れている場合はそのコスト (およびそのヒープ位置)を調整します。