A Star Pathfinding Algorithm Heuristic for Cube Surface

Question

I'm building a snake game that plays on the surface of a cube. Currently it uses Dijkstra's algorithm for pathfinding. Despite optimizations with set and priority queue data structures, it is still a bit too slow. You notice the delay when the snake eats a food item and begins searching for a new one.

I'm trying to get it to use A* instead but I can't find a good heuristic. On a flat grid with 4 directions of movement, I would use Manhattan distance. I've tried using 3D Manhattan distance abs(dx) + abs(dy) + abs(dz) which didn't work for good reason: to the snake, the game world is really 6 grids (corresponding to the faces of the cube) with unusual wrap-around properties.

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

Here's the area of game code where the pathfinding happens:

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

Here's 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 to, instead of doing all of the pathfinding as soon as you grab one food item, have the snake move towards the side that has the next food item and then, when it is on that side, use a basic 2D grid A* algorithm to get the food item. In other words:

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

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

This will not guarantee the shortest overall path, but it should usually be close to the shortest path, and it should be faster because it splits the pathfinding up into multiple phases and uses a more efficient algorithm for each phase.