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 this gif (!!! Fig 404 !!!) of 'the perfect game' it made me curious how a programmatic solution would work.
Pathfinding
If you're not familiar with the game, the basic explanation of it 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. Graphs, made up of nodes and edges are a common data structure used in pathfinding.
Starting at one node on the graph, using the connected edges to traverse the graph looking for another node for whatever reason. Different methods can be used to find the 'best' path between two nodes, it might be the shortest path, the fastest path, or the path that avoids certain nodes. Depth first search and breadth first search are two common methods of traversing a graph, but they are not guaranteed to find the best path and there's trade-offs depending on the type of graph.
Here, we'll use the A* algorithm to find the best path. A* is a heuristic search algorithm, meaning it uses a heuristic to estimate the distance between two nodes. The heuristic is used to prioritize which nodes to visit first, and the algorithm will visit nodes in order of priority.
Analyzing optimality
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.
- Points: The number of points that the snake collects is an indication to how successful the solution is. The more points, the longer the snake lasted, and so the better the solution is at avoiding crashes while also collecting points.
- Cumulative moving average: Tracking the number of moves from point to point helps to see the efficiency of the solution throughout the game. As the snake gets longer from collecting points, there are less available spaces on the grid for the next point to generate, so the efficiency of the solution is less important towards the end then it is at the beginning. We can use a cumulative moving average here to smooth out the variability that comes from the randomness of the point positioning.
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.
Heuristics
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.
The live runner can be used to play out a game of snake with that solution.
Manhattan Distance
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 heuristic function will be run on every cell, and should return a number. The number that is returned will be used to determine the path of the snake.
*
* @param [number, number] cell Coordinates of the cell to return a value for
* @param number xLength The number of cells across the x axis
* @param number yLength The number of cells across the y axis
* @param [number, number][] snake Coordinates of the position of the snake from head to tail. E.g. [[4, 1], [3, 1]]
* @param [number, number] point Coordinates of the point.
*
* @returns number The value for the cell
*/
function heuristic(cell, xLength, yLength, snake, point) {
return Math.abs(cell[0] - point[0]) + Math.abs(cell[1] - point[1]);
}Euclidean Distance
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
/**
* The heuristic function will be run on every cell, and should return a number. The number that is returned will be used to determine the path of the snake.
*
* @param [number, number] cell Coordinates of the cell to return a value for
* @param number xLength The number of cells across the x axis
* @param number yLength The number of cells across the y axis
* @param [number, number][] snake Coordinates of the position of the snake from head to tail. E.g. [[4, 1], [3, 1]]
* @param [number, number] point Coordinates of the point.
*
* @returns number The value for the cell
*/
function heuristic(cell, xLength, yLength, snake, point) {
return Math.hypot(cell[0] - point[0], cell[1] - point[1]);
}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 404 !!!, because likewise it does nothing to handle the environment, and simply just knows about moving towards the point.
Hamiltonian Cycle
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.
/**
* The heuristic function will be run on every cell, and should return a number. The number that is returned will be used to determine the path of the snake.
*
* @param [number, number] cell Coordinates of the cell to return a value for
* @param number xLength The number of cells across the x axis
* @param number yLength The number of cells across the y axis
* @param [number, number][] snake Coordinates of the position of the snake from head to tail. E.g. [[4, 1], [3, 1]]
* @param [number, number] point Coordinates of the point.
*
* @returns number The value for the cell
*/
function heuristic(cell, xLength, yLength, snake, point) {
const xMax = xLength - 1;
const yMax = yLength - 1;
const [headX, headY] = snake[0];
const dirCell = getDirection(snake[0], cell);
const dirCurrent = getDirection(snake[1], snake[0]);
if (dirCurrent === DIR_R) {
// Continuing sweep movement
if ((headX < xMax - 1 || headY === yMax) && dirCell === dirCurrent) return 0;
// Moving onto the next row when approaching the edge
if (headX >= xMax - 1 && dirCell === DIR_D) return 0;
}
if (dirCurrent === DIR_L) {
// Continuing sweep movement
if ((headX > 1 || headY === yMax) && dirCell === dirCurrent) return 0;
// Moving onto the next row when approaching the edge
if (headX <= 1 && dirCell === DIR_D) return 0;
}
if (dirCurrent === DIR_R || dirCurrent === DIR_L) {
// When at the bounds on the last line, head back up
if ((headX === 0 || headX === xMax) && headY === yMax && dirCell === DIR_U) return 0;
}
if (dirCurrent === DIR_D) {
// After moving onto the next line, get the next direction
if ((headX < xLength / 2 && dirCell === DIR_R)) return 0;
if ((headX > xLength / 2 && dirCell === DIR_L)) return 0;
}
if (dirCurrent === DIR_U) {
// Continue moving back up to the top of the border
if (dirCell === DIR_U) return 0;
// After returning to the top, set the direction to continue sweeping
if ((headY === 0 || headY === yMax) && headX === 0 && (dirCell === DIR_L || dirCell === DIR_R)) return 0;
}
return 999;
}
const DIR_U = 0;
const DIR_R = 1;
const DIR_D = 2;
const DIR_L = 3;
const getDirection = (a, b) =>
(a[1] === b[1] && a[0] === b[0] - 1 && DIR_R) ||
(a[0] === b[0] && a[1] === b[1] - 1 && DIR_D) ||
(a[1] === b[1] && a[0] === b[0] + 1 && DIR_L) ||
(a[0] === b[0] && a[1] === b[1] + 1 && DIR_U);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 404 !!!) and ultimately crashing into itself.
Note: This is not a true Hamiltonian Path or Cycle because of the need to alternate the path and visiting some nodes for a second time before getting back to the start.Tail Escape
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 heuristic function will be run on every cell, and should return a number. The number that is returned will be used to determine the path of the snake.
*
* @param [number, number] cell Coordinates of the cell to return a value for
* @param number xLength The number of cells across the x axis
* @param number yLength The number of cells across the y axis
* @param [number, number][] snakeOrigin Coordinates of the position of the snake from head to tail. E.g. [[4, 1], [3, 1]]
* @param [number, number] point Coordinates of the point.
*
* @returns number The value for the cell
*/
function heuristic(cell, xLength, yLength, snake, point) {
const size = xLength * yLength * 2;
const xMax = xLength - 1;
const yMax = yLength - 1;
if (!includes(adjacencies(snake[0], xMax, yMax), cell)) return 0;
const pathToPoint = search(cell, point, xMax, yMax, snake);
if (pathToPoint) {
const snakeAtPoint = shift(snake, pathToPoint, true);
for (const next of difference(
adjacencies(point, xMax, yMax),
snakeAtPoint
)) {
if (search(next, tail(snakeAtPoint), xMax, yMax, snakeAtPoint)) {
return pathToPoint.length;
}
}
}
const pathToTail = search(cell, tail(snake), xMax, yMax, snake);
if (pathToTail) {
return size - pathToTail.length;
}
return size * 2;
}
const search = (start, end, xMax, yMax, snake) => {
const queue = [start];
const paths = { [start]: [start] };
while (queue.length) {
const current = queue.shift();
const snakeShifted = shift(
snake,
(paths[current] = paths[current] || [start])
);
if (equals(current, end)) {
return paths[current];
}
for (const next of difference(
adjacencies(current, xMax, yMax),
snakeShifted
)) {
if (!(next in paths)) {
queue.push(next);
paths[next] = [next].concat(paths[current]);
}
}
}
};
const adjacencies = (a, xMax, yMax) =>
[
[a[0], a[1] - 1],
[a[0] + 1, a[1]],
[a[0], a[1] + 1],
[a[0] - 1, a[1]],
].filter((b) => b[0] >= 0 && b[1] >= 0 && b[0] <= xMax && b[1] <= yMax);
const equals = ([x1, y1], [x2, y2]) => x1 === x2 && y1 === y2;
const includes = (a, b) => a.some((a) => equals(a, b));
const difference = (a, b) => a.filter((a) => !includes(b, a));
const shift = (a, b, collect) =>
b.concat(a).slice(0, b.length + (a.length - b.length + (collect ? 1 : 0)));
const tail = (a) => a[a.length - 1];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.
- If there is a direct path to the point check that the hypothetical position of the snake once collecting the point has a path back to the end of the tail, then it's a favourable option.
- If there isn't a path to the point but has a path to the tail, then it's still an option, but just less favourable.
- If in both situations there are no paths back to the tail, then the cell is not an option.
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.
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.
However this is the approach that seems to best resemble the behaviour in 'the perfect game' gif in !!! Fig 404 !!!.
- Tail Escape
- Hamiltonian Cycle
- Euclidean Distance
- Manhattan Distance
- Tail Escape
- Hamiltonian Cycle
- Euclidean Distance
- Manhattan Distance