私は現在、HTML5 <キャンバス>要素を使用してJavascriptで2Dゲームを作成しています。それは非常にきれいに来ているが、私は問題に遭遇した。良い2Dグリッドベースのパス探索アルゴリズムとは何ですか?
グリッド内のさまざまな場所を占めるさまざまな障害物を持つ私のゲームのレベルデザインはグリッドです(1セルから北/南/東/西セルへのパスコストは1です)–多くの場合、しかし、より多くの揺れ部屋。個々のレベルは、400細胞のオーダーである。
私はどこにいるかにかかわらずプレイヤーを探し出す敵を実装しようとしていますが、私の状況に合わせてさまざまなパス探索アルゴリズムを翻訳しようとしています。 (A *やDijkstraのような)私が見つけたもののほとんどは、3Dやはるかに複雑な2Dの状況に最も適しているようです。私は自分の目的に合わせてこれらのアルゴリズムを劇的に簡略化することが可能かどうか、または深さ優先探索のようなものがレベルサイズよりも効率的な選択肢になるかどうか疑問に思っていました。
マップを既知の接続性のあるセグメントに分割するなど、可能なパスについて何らかの事前知識を与えることなく、A *を上回ることはありません。深さはまず最初に幅よりもはるかに遅くなります。 – Dave
これは実際にStackoverflow/Stack Exchangeについてのものではありません。ショッピングに関する質問ではなく、明確な答えで質問してください。是非、人々が提案するものを使用してください。しかし、プログラミング上の問題が発生したときに復帰してください。 – Amelia
@Dave:グリッドに拘束されている場合は、簡単に[plain-ol 'A \ *](http://programmers.stackexchange.com/questions/197894)よりも優れています。しかし、JPS + A \ *はA \ *より複雑で、通常は必要ありません。 –