6

立方体の表面で遊ぶスネーク ゲームを作成しています。現在、経路探索にはダイクストラのアルゴリズムを使用しています。セットおよびプライオリティ キュー データ構造の最適化にもかかわらず、まだ少し遅すぎます。ヘビが食べ物を食べて、新しいものを探し始めるときの遅れに気づきます。

代わりに A* を使用しようとしていますが、適切なヒューリスティックが見つかりません。4 方向の移動があるフラット グリッドでは、マンハッタン距離を使用します。私はabs(dx) + abs(dy) + abs(dz)正当な理由で機能しなかった 3D マンハッタン距離を使用してみました: ヘビにとって、ゲームの世界は実際には6 つのグリッド (立方体の面に対応)であり、異常なラップアラウンド プロパティを備えています。

コードでは、各正方形がgrid[15][15]2D 配列に格納されます。各面を格納する 6 つの配列があります。したがって、各正方形には(arrayX, arrayY, d)、2D 配列のオフセットを記述し、どの配列を指定するかを示すトリプルがあります。また、各正方形には、(x, y, z)空間位置を表すトリプルがあります。

パスファインディングが発生するゲーム コードの領域は次のとおりです。

https://github.com/mhluska/Snakeception/blob/master/src/js/game.coffee#L105

A* のライブラリ コードは次のとおりです。

https://github.com/mhluska/Stimpack/blob/master/src/js/graph.coffee#L60

このゲームの世界に適した簡潔なヒューリスティックは何ですか?

4

1 に答える 1

3

これを解決する 1 つの方法は、1 つの食品をつかむとすぐにすべての経路探索を行うのではなく、ヘビを次の食品がある側に移動させ、その側にいるときに基本的な方法を使用することです。食品を取得するための 2D グリッド A* アルゴリズム。言い換えると：

ヘビが食べ物をつかむか、キューブの新しい面に移動するたびに、次のことを行います。

  • 食品が現在の立方体側にある場合、A* アルゴリズムと 2D マンハッタン距離ヒューリスティックを使用して、食品へのパスを見つけます。
  • 食品が立方体の隣接する面にある場合、同じ経路探索アルゴリズムを使用して、現在の面とターゲット面に接する立方体の端への経路を見つけます。
  • 食品が立方体の反対側にある場合は、同じ経路探索アルゴリズムを使用して、現在の側から離れた経路を見つけます。

これは全体の最短経路を保証するものではありませんが、通常は最短経路に近く、経路探索を複数のフェーズに分割し、各フェーズでより効率的なアルゴリズムを使用するため、高速になるはずです。

于 2012-12-07T07:40:39.597 に答える