The classic game of Snake is a simple concept but it has some interesting problems when it comes to creating a programmatic solution. When I came across the notorious gif of 'the perfect game', it made me curious how a programmatic solution would work.

The concept of Snake is to guide the snake across the map to the point, avoiding collisions with itself or the walls. This general problem of finding a path from a starting point to an endpoint can be applied to lots of other applications like satellite navigation, routing packets across the internet, game AIs, OS file system search, distribution/utility networks and many more.

The domain of all of these problems, including the game of snake, can be solved with graph theory. Each of the places that can be visited and their connections to other places can be represented as nodes and edges/links on a mathematical structure called a graph, similar to that shown in Fig 1.

Graph search algorithms are used to determine the path from node to node, usually looking for a single specific node as the end goal. We'll be looking at two algorithms for the Snake solution, 'Breadth-First Search' and 'Best-First Search'.

The Breadth-First Search algorithm uses a queueing system for exploring all of the nodes depth by depth (the queued cells are sometimes referred to as the frontier ring). It takes the node at the front of the queue and then pushes all of the connecting nodes onto the end of the queue. This ensures that the nodes with the closest links to the starting node are explored first and makes it ideal for finding an endpoint where the direction is unknown or if there are a lot of obstacles.

The Best-First Search algorithm explores a single path by prioritising the next node using a heuristic evaluation. This heuristic usually guides the path towards a known endpoint, though this will depend on what the heuristic function is.

We'll be using a Best-First search as the main searching algorithm and the solutions below will be focused around writing a heuristic function to help decide on the path for the snake.

To determine the optimality of the solution we need a way to analyse them, and for that we can track a couple of metrics and create a scoring system, for example:

The scoring system will be a cumulative score of the current point weighted by the moving average, the current path length and progress into completing the game. The weight of the progress is less impactful towards the end.

The solutions below are all heuristic functions that will be run for each cell on the map. Whichever node around the head of the snake has the lowest value, will be the node the snake will move to next. This will continue to happen until either the snake has crashed or the game is complete.

A live runner with each solution can be used to play out the game of snake with that solution, and is taken from my interactive developer game of writing your own heuristic (in Javascript).

The Manhattan Distance is a taxicab metric of Taxicab geometry. The name comes from the grid layout of streets on the island of Manhattan, and the function is the absolute distance between two points.

The Manhattan Distance is a direct solution but it's completely unaware of the environment so this leads to a low average numbers of moves but also a low number of points collected, as it crashes into itself quite early into the game.

The Euclidean Distance is the straight-line distance between two points in Euclidean space and is given by the Pythagorean formula (a² + b² = c², or in Javascript we can use Math.hypot).

This ultimately leads to just an alternative path of the Manhattan Distance, but a more diagonal route. The analysis is almost identical to the solution shown in Fig 3, because likewise it does nothing to handle the environment, and simply just knows about moving towards the point.

A Hamiltonian Path is a path that visits each node of a graph exactly once, and a Hamiltonian Cycle is where the final node visited connects back to the first node and allows the exact same path to be repeated continuously.

This is a methodical solution but has very poor efficiency towards the start of the game due to the unnecessary number of moves that are not weighted to moving towards the direction of the point.

On an even sided grid this has the consistent behaviour of getting 100% completion, however on an odd sided grid it is almost impossible due to the cycle needing to alternate it's direction (see Fig 5) and ultimately crashing into itself.

Some observations we can make from the previous solutions is that the ideal solution needs to have some awareness of the current environment to prevent crashes, like the cells occupied by the snake and the bounds of the map. It also needs to be weighted to move in the direction of the point to keep the number of moves down to a minimum.

This solution focuses on the idea that as long as the head of the snake has a path back to the tail (similar to the Hamiltonian Cycle), then it can avoid crashing into itself by following the tail.

The randomly positioned points and the positioning of the snake means there will not always be a direct path to the point, so this solution has a few conditions.

A Breadth First Search is ideal for searching for the point and tail because of the snake's body providing an obstacle and thus the path to the point will likely not be a direct one.

However, there are still times where this solution does not complete the game 100%. Towards the end of the game, it is likely that single empty cells are available but cannot be manoeuvered into and when a point gets generated into that available cell the snake gets stuck in an endless loop.

The four heuristic solutions above all range in complexity and approach. The Manhattan and Euclidean distance use a simple distance evaluation to determine which next cell is the closest, while the Hamiltonian Cycle is methodical and aims to get a greater level of completion over efficiency. The Tail Escape is the most complicated and tactful, and also most resembles 'the perfect game' gif.

When plotting the solutions moving averages and scores for better comparison against one another, some observations can be made. The Hamiltonian Cycle, as expected, does initially have a lot of variability in the high average number of moves because the number of moves rests entirely on the random position of the point. But overtime, the average does decrease due to the reducing number of cells that the point can generate in.

The Tail Escape solution starts to follow a similar line to the Manhattan and Euclidean distance solutions, which are as direct as possible. This is a good indication that despite not actually using a distance evaluation, the Tail Escape still moves as direct as possible using a breadth first search.

As pointed out above, the Tail Escape solution is still not consistently perfect, and I suspect there is an optimisation to be made that ensures no unmaneuverable cells are left.