キューブ表面の発見的なPathfindingアルゴリズムヒューリスティック

Question

私はキューブの表面上で再生するsnake gameを構築しています。現在は、経路探索のためのDijkstraのアルゴリズムを使用しています。セットと優先順位キューのデータ構造による最適化にもかかわらず、それはまだ少し遅いです。蛇が食べ物を食べて新しいものを探し始めると、あなたは遅れを感じます。

代わりにA *を使用しようとしていますが、優れたヒューリスティックは見つかりません。 4方向の動きのあるフラットグリッドでは、マンハッタンの距離を使用します。私は良い理由のために働かなかった3Dマンハッタン距離abs(dx) + abs(dy) + abs(dz)を使用してみました：蛇に、ゲーム世界は実際には珍しいラップアラウンドプロパティを持つ6 grids (corresponding to the faces of the cube)です。

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

ここで経路探索が発生したゲームコードのエリアです：

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

はここ*のためのライブラリのコードです：

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

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

Answer 1

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

ヘビは、次の手順を実行し、キューブの新しい側面に食品や移動をつかむたび：

• 食品が現在のキューブ側にある場合は、パスを見つけます2Dマンハッタン距離ヒューリスティックでA *アルゴリズムを使用する
• 食品アイテムが立方体の隣接辺にある場合は、同じパスファインディングアルゴリズムを使用して、現在の辺とターゲット辺の境界にある立方体のエッジまでのパスを見つけます。
• 食品がキューブの反対側にある場合は、同じ経路探索アルゴリズムを使用して、現在の側面の経路を探します。

これはパス全体の最短パスを保証するものではありませんが、通常は最短パスに近いものでなければなりません。パスファインディングを複数のフェーズに分割し、各フェーズでより効率的なアルゴリズムを使用するため、