Menu
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?
351
The heuristic function provides an estimate of the minimum cost between a given node and the target node. The algorithm will combine the actual cost from the start node - referred to as g(n) - with the estimated cost to the target node - referred to as h(n) - and uses the result to select the next node to evaluate.
Normally when a pathfinding search is made, a heuristic is used. The heuristic is something which gives a rough estimate on how far it is at least to the target. Usually the distance to the target is used directly since this is fast and usually gives relatively good results.
You can use A* with explicit paths/connections between the nodes such as a country road map. In the case of a 3D grid, you apply the same method as a 2D grid but now you can move in the 3rd dimension as well.
A* algorithm A* assigns a weight to each open node equal to the weight of the edge to that node plus the approximate distance between that node and the finish. This approximate distance is found by the heuristic, and represents a minimum possible distance between that node and the end.
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:
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.
132
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
