Snake Bot

Table of Contents

1. The Inspiration
   1. The Algorithm
2. The Implementation
   1. Maze Generation
   2. Maze Traversal
3. Conclusion

   _________         _________
  /         \       /         \
 /  /~~~~~\  \     /  /~~~~~\  \
 |  |     |  |     |  |     |  |
 |  |     |  |     |  |     |  |
 |  |     |  |     |  |     |  |         /
 |  |     |  |     |  |     |  |       //
(o  o)    \  \_____/  /     \  \_____/ /
 \__/      \         /       \        /
  |         ~~~~~~~~~         ~~~~~~~~
  ^

The Inspiration

Initially, I hadn’t set out to solve the classic Snake game. I was just messing around with the SDL2 library in C. While looking for tutorials on SDL, I came across a youtube video in which the person was working towards creating a Neural Network that played Snake. I was only interested in the SDL stuff, so I followed along with the relevant parts of the video.

I disagreed with how they had implemented the game logic. They had gone with a linked list implementation while I chose to represent the snake as a circular array.

typedef struct {
  int x, y;
  Dir d;
} Point;

Point snake[MAX_SNAKE_SIZE];
int snake_begin_index = 0;
int snake_size = 1;
Dir snake_dir = UP;

I borrowed from my previous experience while making this choice of data structure. Here, Dir is an Enum representing the four possible directions. After writing the render code, adding checks for game-over situations, and writing code for handling controls, I had a fully functioning Snake game in my hands written entirely using the SDL2 library.

In the video, I’d heard a mention of algorithmic solutions to Snake. It was only mentioned in passing, but it caught my interest and sent me down a rabbit hole of snake playing algorithms. And then I stumbled upon this article. It’s part of a great series of articles on programming for the Nokia 6110 by John Tapsell.

The big insight in the article is that to play a perfect game of Snake, the snake needs to follow a Hamiltonian Cycle of the 2D Array that represets the game space.

The Algorithm

The Algorithm by itself is pretty simple. We just need to calculate a random Hamiltonian Cycle every game, we can treat it like a Maze and have the snake traverse the maze until the game is complete.

1. Use BFS to generate a spanning tree(the Maze) half the width and half the height of the grid.
2. Traverse the Maze ( following the Hand on Wall Rule ).

John optimizes this algorithm so that the snake takes shortcuts to the fruit within the Maze when possible, calling it the Pertubated Hamiltonian Cycle. One important restriction for this algorithm is that while recalculating the shortcut, the order of the snake i.e. the head, the body, and the tail must remain intact. This is required because, as the snake body becomes larger, the chance of it hitting its own body increases. Enforcing the order, makes sure that that it doesn’t collide with itself. I recommend reading his article to better understand the algorithm.

The Implementation

Now that I had understood the algorithm, it was time for me to implement it for my own Snake game. It’d be an understatement to say that it was challenging. This was the first time that I had undertaken a substantial project in C and my lack of experience was apparent, right from the get go.

But enough of my complains, let’s dive into how I implemented the algorithm. I’ve broadly divided the process into two parts.

Maze Generation

We start by generating a Spanning Tree half the dimensions of the grid. I must mention that I am considering each of the cells in the grid to be a node in a graph and the spanning tree is a subgraph that contains all the nodes in the graph but not all the edges. After generating the Spanning Tree, we scale it two times to obtain the Maze.

The gen_tree() function performs the actual task of generating the Spanning Tree. It works in the following way:

1. Start at a random point on the tree (half the grid).
2. Add all the adjacent points(4 in our case) to the Frontier queue that haven’t been visited.
3. Choose a random edge to include in the Spanning Tree
4. Dequeue a node from the Frontier and repeat steps 2 to 4 until all nodes are visited.

Maze Traversal

A simple Right Hand Rule is used to traverse the maze, which means that we make the snake turn right wherever possible until the path traced by snake completes a Hamiltonian Cycle which, of course, is guaranteed because of the earlier step.

This cycle is pre-calculated and stored in the maze_path array as a set of cell indices ( The unique cell index of cells in the 2D Space array is calculated as x * GRID_SIZE + y, where x,y is the cell coordinate ).

A distance_to_fruit() function is used to find the distance between next possible head position (try_head, representing either of three next positions the head can be in) and the fruit position within the maze_path. The head position with the shortest distance is chosen such that the order of the snake is maintained, as stated before.

With the Hamiltonian Cycle path i.e. maze_path calculation complete and a way for taking shortcuts in place, a traverse_maze() function is used to actually make the snake follow the path and take shortcuts when possible. It specifies which direction the snake must move to and the move_snake() function handles moving the snake to that direction. The shortcut calculation occurs continuously as the snake moves along the path and stops when the snake has grown to fill half the grid, so as to avoid self-collision. The Snake Bot is now complete.

Following is a video demonstrating the algorithm in action.

Conclusion

While the algorithm I implemented in this project reliably plays a complete game of Snake, it still isn’t the most efficient algorithm. If you’ve watched the video, you can see how the path the snake takes is repetitive. Despite its inefficiency, this project was a great learning experience for me and I had a lot of fun applying some of the theoretical concepts I had learnt in my Discrete Maths class in practice.

I hope you liked the article!

The full source code for this project is available here.