そこで、タワー ディフェンス ゲーム用に A* を最適化する方法について質問したところ、50 以上の敵の最短距離を計算する代わりにダイクストラまたはブレッドスを最初に使用する必要があるといういくつかの回答が得られました。
私の質問は
幅優先とダイクストラのどちらを使用しますか? ダイクストラは A* より速いですか? A* と同じくらい正確ですか? ダイクストラを学ばなくても A* を使用してパスを計算できるように、A* をバイナリ ヒープ以上に最適化する方法はありますか?
現在、バイナリ ヒープを使用して A* を使用して 30* 30 グリッドで長いパスを計算するには、平均で約 0.003 秒かかりますが、十分な速さではないと思います。
DJikstraは、不活性なヒューリスティック関数を使用した A* の別のケースです。すべての問題は、適切なヒューリスティック関数を提案できるかどうかに要約されます。できれば、A* のパフォーマンスが向上することは間違いありません。
タワーディフェンスゲームの場合、通常、出口ごとに最短パスツリーを保存し、その出口に向かうすべてのMobに再利用する必要があります。そうすれば、接続が変更されるたびに（つまり、タワーが構築または破壊されたときに）1回だけ再計算する必要があります。
とにかく完全な最短経路ツリーを計算したいので、より複雑なA *の代わりに、単純な古いダイクストラのアルゴリズムを使用する方がよいでしょう。
ただし、必要に応じて「インクリメンタルA*」を使用して最短経路ツリーを構築することもできます。基本的に、ゴールから暴徒までA *を実行し、ターゲットに到達したときにアルゴリズムの状態（これまでに構築された部分的な最短パスツリーを含む）を保存してから、（別のターゲットとヒューリスティックで）再開します。次に、ツリーでまだカバーされていないポイントからその目標へのパスを見つける必要がある場合。タワーが追加または削除されたときにツリーを段階的に更新することもできますが、それはまだ少し複雑になります。