Star trajectory search algorithm heuristic for cube surface

Question

I create one that plays on the surface of the cube. He currently uses Dijkstra's algorithm to find paths. Despite optimizing the data structure with established and priority queues, it is still too slow. You notice a delay when the snake eats food and starts looking for a new one.

I am trying to get him to use A *, but I cannot find a good heuristic. On a flat grid with four directions of movement, I would use the Manhattan distance. I tried using 3D Manhattan distance abs(dx) + abs(dy) + abs(dz) , which did not work for a good reason: for a snake, the game world really has 6 meshes (corresponding to the edges of the cube) with unusual wrapper properties.

In the code, each square is stored in the grid[15][15] 2D array. There are 6 such arrays for storing each face. Therefore, each square has a triple (arrayX, arrayY, d) to describe the offset in the 2D array and indicate which array. In addition, each square has a triple (x, y, z) describing the spatial position.

Here is the area of ​​the game code where the path is searched:

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

Here is the library code for A *:

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

What is a suitable, concise heuristic for this game world?

Answer 1

One way to solve this is, instead of doing all the ways, as soon as you take one food item, make the snake move to the side that has the next food product, and then when it is on that side, use the basic 2D mesh algorithm A * for food. In other words:

Whenever a snake grabs a food product or moves to a new side of the cube, do the following:

• If the battery is on the current side of the cube, find the path to it using the A * algorithm with a 2D Manhattan heuristic distance
• If the food is on the adjacent side of the cube, find the path to the edge of the cube bordering the current side and the target side using the same path search algorithm.
• If the food product is on the opposite side of the cube, find the path from the current side with the same path search algorithm.

This does not guarantee the shortest common path, but usually it should be close to the shortest, and it should be faster because it splits the path into several phases and uses a more efficient algorithm for each phase.