# Nokia 6110 Part 3 – Algorithms

This is a four part series:

We need an AI that can play a perfect game of Snake.  To collect the food without crashing into itself.

But it needs to run in real time on an 8Mhz processor, and use around 1 KB of memory.  The extreme memory and speed restrictions means that we do not want to allocate any heap memory, and should run everything on the stack.

None of the conventional path finding algorithms would work here, so we need a new approach.  The trick here is to realise that in the end part of the game, the snake will be following a planar Hamiltonian Cycle of a 2D array:

So what we can do is precompute a random hamiltonian cycle at the start of each game, then have the snake follow that cycle.  It will thus pass through every point, without risk of crashing, and eventually win the game.

There are various way to create a hamiltonian cycle, but one way is to use Prim’s Algorithm to generate a maze of half the width and half the height.  Then walk the maze by always turning left when possible.  The resulting path will be twice the width and height and will be a hamiltonian cycle.

Now, we could have the snake just follow the cycle the entire time, but the result is very boring to watch because the snake does not follow the food, but instead just follows the preset path.

To solve this, I invented a new algorithm which I call the pertubated hamiltonian cycle.  First, we imagine the cycle as being a 1D path.  On this path we have the tail, the body, the head, and (wrapping back round again) the tail again.

The key is realising that as long as we always enforce this order, we won’t crash.  As long as all parts of the body are between tail and the head, and as long as our snake does not grow long enough for the head to catch up with the tail, we will not crash.

This insight drastically simplifies the snake AI, because now we only need to worry about the position of the head and the tail, and we can trivially compute (in O(1)) the distance between the head and tail since that’s just the difference in position in the linear 1D array:

Now, this 1D array is actually embedded in a 2D array, and the head can actually move in any of 3 directions at any time.  This is equivalent to taking shortcuts through the 1D array.  If we want to stick to our conditions, then any shortcut must result in the head not overtaking the tail, and it shouldn’t overtake the food, if it hasn’t already.  We must also leave sufficient room between the head and tail for the amount that we expect to grow.

Now we can use a standard shortest-path finding algorithm to find the optimal shortcut to the food.  For example, an A* shortest path algorithm.

However I opted for the very simplest algorithm of just using a greedy search.  It doesn’t produce an optimal path, but visually it was sufficiently good.  I additionally disable the shortcuts when the snake takes up 50% of the board.

To test, I started with a simple non-random zig-zag cycle, but with shortcuts:

What you can see here is the snake following the zig-zag cycle, but occasionally taking shortcuts.

We can now switch to a random maze:

And once it’s working on the PC, get it working on the phone:

Code

The code is remarkably simple.  First, the code to pre-generate the hamiltonian circuit at the start of each game and provide some helper functions:

```
UTourNumber tourToNumber[ARENA_SIZE];

/* Take an x,y coordinate, and turn it into an index in the tour */
TourNumber getPathNumber(Coord x, Coord y) {
}

Distance path_distance(Coord a, Coord b) {
if(a<b)
return b-a-1;
return b-a-1+ARENA_SIZE;
}

struct Maze {
struct Node {
bool visited:1;
bool canGoRight:1;
bool canGoDown:1;
};
Node nodes[ARENA_SIZE/4];
void markVisited(Coord x, Coord y) {
nodes[x+y*ARENA_WIDTH/2].visited = true;
}
void markCanGoRight(Coord x, Coord y) {
nodes[x+y*ARENA_WIDTH/2].canGoRight = true;
}
void markCanGoDown(Coord x, Coord y) {
nodes[x+y*ARENA_WIDTH/2].canGoDown = true;
}
bool canGoRight(Coord x, Coord y) {
return nodes[x+y*ARENA_WIDTH/2].canGoRight;;
}
bool canGoDown(Coord x, Coord y) {
return nodes[x+y*ARENA_WIDTH/2].canGoDown;
}
bool canGoLeft(Coord x, Coord y) {
if(x==0) return false;
return nodes[(x-1)+y*ARENA_WIDTH/2].canGoRight;
}

bool canGoUp(Coord x, Coord y) {
if(y==0) return false;
return nodes[x+(y-1)*ARENA_WIDTH/2].canGoDown;
}

bool isVisited(Coord x, Coord y) {
return nodes[x+y*ARENA_WIDTH/2].visited;
}

void generate() {
memset(nodes, 0, sizeof(nodes));
generate_r(-1,-1,0,0);
generateTourNumber();
#ifdef LOG_TO_FILE
writeMazeToFile();
writeTourToFile();
#endif
}
void generate_r(Coord fromx, Coord fromy, Coord x, Coord y) {
if(x < 0 || y < 0 || x >= ARENA_WIDTH/2 || y >= ARENA_HEIGHT/2)
return;
if(isVisited(x,y))
return;
markVisited(x,y);

if(fromx != -1) {
if(fromx < x)
markCanGoRight(fromx, fromy);
else if(fromx > x)
markCanGoRight(x,y);
else if(fromy < y)
markCanGoDown(fromx, fromy);
else if(fromy > y)
markCanGoDown(x,y);

//Remove wall between fromx and fromy
}

/* We want to visit the four connected nodes randomly,
* so we just visit two randomly (maybe already visited)
* then just visit them all non-randomly.  It's okay to
* visit the same node twice */
for(int i = 0; i < 2; i++) {
int r = rand()%4;
switch(r) {
case 0: generate_r(x, y, x-1, y); break;
case 1: generate_r(x, y, x+1, y); break;
case 2: generate_r(x, y, x, y-1); break;
case 3: generate_r(x, y, x, y+1); break;
}
}
generate_r(x, y, x-1, y);
generate_r(x, y, x+1, y);
generate_r(x, y, x, y+1);
generate_r(x, y, x, y-1);
}

SnakeDirection findNextDir(Coord x, Coord y, SnakeDirection dir) {
if(dir == Right) {
if(canGoUp(x,y))
return Up;
if(canGoRight(x,y))
return Right;
if(canGoDown(x,y))
return Down;
return Left;
} else if(dir == Down) {
if(canGoRight(x,y))
return Right;
if(canGoDown(x,y))
return Down;
if(canGoLeft(x,y))
return Left;
return Up;
} else if(dir == Left) {
if(canGoDown(x,y))
return Down;
if(canGoLeft(x,y))
return Left;
if(canGoUp(x,y))
return Up;
return Right;
} else if(dir == Up) {
if(canGoLeft(x,y))
return Left;
if(canGoUp(x,y))
return Up;
if(canGoRight(x,y))
return Right;
return Down;
}
return (SnakeDirection)-1; //Unreachable
}
void setTourNumber(Coord x, Coord y, TourNumber number) {
if(getPathNumber(x,y) != 0)
return; /* Back to the starting node */
tourToNumber[x + ARENA_WIDTH*y] = number;
}

void generateTourNumber() {
const Coord start_x = 0;
const Coord start_y = 0;
Coord x = start_x;
Coord y = start_y;
const SnakeDirection start_dir = canGoDown(x,y)?Up:Left;
SnakeDirection dir = start_dir;
TourNumber number = 0;
do {
SnakeDirection nextDir = findNextDir(x,y,dir);
switch(dir) {
case Right:
setTourNumber(x*2,y*2,number++);
if(nextDir == dir || nextDir == Down || nextDir == Left)
setTourNumber(x*2+1,y*2,number++);
if(nextDir == Down || nextDir == Left)
setTourNumber(x*2+1,y*2+1,number++);
if(nextDir == Left)
setTourNumber(x*2,y*2+1,number++);
break;
case Down:
setTourNumber(x*2+1,y*2,number++);
if(nextDir == dir || nextDir == Left || nextDir == Up)
setTourNumber(x*2+1,y*2+1,number++);
if(nextDir == Left || nextDir == Up)
setTourNumber(x*2,y*2+1,number++);
if(nextDir == Up)
setTourNumber(x*2,y*2,number++);
break;
case Left:
setTourNumber(x*2+1,y*2+1,number++);
if(nextDir == dir || nextDir == Up || nextDir == Right)
setTourNumber(x*2,y*2+1,number++);
if(nextDir == Up || nextDir == Right)
setTourNumber(x*2,y*2,number++);
if(nextDir == Right)
setTourNumber(x*2+1,y*2,number++);
break;
case Up:
setTourNumber(x*2,y*2+1,number++);
if(nextDir == dir || nextDir == Right || nextDir == Down)
setTourNumber(x*2,y*2,number++);
if(nextDir == Right || nextDir == Down)
setTourNumber(x*2+1,y*2,number++);
if(nextDir == Down)
setTourNumber(x*2+1,y*2+1,number++);
break;
}
dir = nextDir;

switch(nextDir) {
case Right: ++x; break;
case Left: --x; break;
case Down: ++y; break;
case Up: --y; break;
}

}
#ifdef LOG_TO_FILE
void writeTourToFile() {
FILE *f = fopen("maps.txt", "w+");
for(Coord y = 0; y < ARENA_HEIGHT; ++y) {
for(Coord x = 0; x < ARENA_WIDTH; ++x)
fprintf(f, "%4d", getPathNumber(x,y));
fprintf(f, "\n");
}
fclose(f);
}
void writeMazeToFile() {
FILE *f = fopen("maze.txt", "w+");
for(Coord y = 0; y < ARENA_HEIGHT/2; ++y) {
fprintf(f, "#");
for(Coord x = 0; x < ARENA_WIDTH/2; ++x)
if(canGoRight(x,y) && canGoDown(x,y))
fprintf(f, "+");
else if(canGoRight(x,y))
fprintf(f, "-");
else if(canGoDown(x,y))
fprintf(f, "|");
else
fprintf(f, " ");
fprintf(f, "#\n");
}
fclose(f);
}
#endif
};

void aiInit() {
Maze maze;
maze.generate();
}

```

And now the AI code:

```
SnakeDirection aiGetNewSnakeDirection(Coord x, Coord y) {
const TourNumber pathNumber = getPathNumber(x,y);
const Distance distanceToFood = path_distance(pathNumber, getPathNumber(food.x, food.y));
const Distance distanceToTail = path_distance(pathNumber, getPathNumber(snake.tail_x, snake.tail_y));
Distance cuttingAmountAvailable = distanceToTail - snake.growth_length - 3 /* Allow a small buffer */;
const Distance numEmptySquaresOnBoard = ARENA_SIZE - snake.drawn_length - snake.growth_length - food.value;
// If we don't have much space (i.e. snake is 75% of board) then don't take any shortcuts */
if (numEmptySquaresOnBoard < ARENA_SIZE / 2)
cuttingAmountAvailable = 0;
else if(distanceToFood < distanceToTail) { /* We will eat the food on the way to the tail, so take that into account */
cuttingAmountAvailable -= food.value;
/* Once we ate that food, we might end up with another food suddenly appearing in front of us */
if ((distanceToTail - distanceToFood) * 4 > numEmptySquaresOnBoard) /* 25% chance of another number appearing */
cuttingAmountAvailable -= 10;
}
Distance cuttingAmountDesired = distanceToFood;
if(cuttingAmountDesired < cuttingAmountAvailable)
cuttingAmountAvailable = cuttingAmountDesired;
if(cuttingAmountAvailable < 0)
cuttingAmountAvailable = 0;
// cuttingAmountAvailable is now the maximum amount that we can cut by

bool canGoRight = !check_for_collision(x+1, y);
bool canGoLeft =  !check_for_collision(x-1, y);
bool canGoDown =  !check_for_collision(x, y+1);
bool canGoUp =    !check_for_collision(x, y-1);

SnakeDirection bestDir;
int bestDist = -1;
if(canGoRight) {
Distance dist = path_distance(pathNumber, getPathNumber(x+1, y));
if(dist <= cuttingAmountAvailable && dist > bestDist) {
bestDir = Right;
bestDist = dist;
}
}
if(canGoLeft) {
Distance dist = path_distance(pathNumber, getPathNumber(x-1, y));
if(dist <= cuttingAmountAvailable && dist > bestDist) {
bestDir = Left;
bestDist = dist;
}
}
if(canGoDown) {
Distance dist = path_distance(pathNumber, getPathNumber(x, y+1));
if(dist <= cuttingAmountAvailable && dist > bestDist) {
bestDir = Down;
bestDist = dist;
}
}
if(canGoUp) {
Distance dist = path_distance(pathNumber, getPathNumber(x, y-1));
if(dist <= cuttingAmountAvailable && dist > bestDist) {
bestDir = Up;
bestDist = dist;
}
}
if (bestDist >= 0)
return bestDir;

if (canGoUp)
return Up;
if (canGoLeft)
return Left;
if (canGoDown)
return Down;
if (canGoRight)
return Right;
return Right;
}
```

## 20 thoughts on “Nokia 6110 Part 3 – Algorithms”

1. Auto Didact

Hi, what exactly is ARENA_SIZE? Is it ARENA_HEIGHT * ARENA_WIDTH? Or is it an adjacency matrix?

Like

• Yes, ARENA_SIZE = ARENA_HEIGHT * ARENA_WIDTH

Liked by 1 person

2. Hi, is ARENA_SIZE and adjacency matrix or is it just height x width?

Like

3. Ivan Gomis

Hi What exactly check_for_collision does? Check the positions in the 1D array?

Like

• Yes – it checks if there’s a snake body at that position. It also checks the x,y isn’t out of bounds.

Like

4. Hi John, thank you so much for creating this amazing guide! I’ve tried to create the snake AI myself (not on an old Nokia though), but I have some difficulty – particularly in selecting the correct square to go next.

From all adjacent squares, I exclude the ones that are in between the head and the tail index (of the H-cycle) if the head index is bigger than the tail index. If the tail index is bigger than the head index I exclude squares that are smaller than the head index or bigger than the tail index. From the remaining squares, I select the one that is closest to the apple. My snake doesn’t die, but it ends up going in small loops pretty quickly. Am I doing the selection process right?

Like

• That exclusion sounds good. “I select the one that is closest to the apple” – to be clear, closest here should mean the smallest index that is larger than the index of the apple.

Like

• How can you guarantee that every adjacent node to the head has an index greater than the apple’s? That won’t always be the case..?

Like

5. Sorry, I’ve gotten mixed up from the way I numbered it in the post.

Rather, you want the largest index that is less than the index of the apple. And there will always be one adjacent square that fits that (ignoring wrapping around). You don’t need all adjacent nodes to less than the apple’s index, just at least one of them to be.

Like

6. Not sure we have the same understanding of adjacent nodes. My snake analyses all adjacent nodes to the head before moving to the next square. In the image, I’ve linked below the adjacent squares are marked blue and the apple is red. In that scenario, none of the adjacent squares has an index in the H-cycle that is less than the apple’s index.

https://gyazo.com/600a354ff36d9c32931e6b650c00b3dc

Thanks a lot for the help, John! 🙂

Like

• Okay, so this is the case where you need to wrap around. Think of it this way – if any adjacent index or apple index is less than the current head index, add the size of the array to the index.

So, imagine the size of our array is 1000. Our head is at index 50. The apple is at 30, and our adjacent squares options are 42, 80, 20.

So add the ‘1000’ to any indexes which are less than our head (50). So we now have:

The apple is at 1030, and our adjacent squares options are 1042, 80, 1020.

The largest index which is less than the apple index is 1020.

So next snake should move to the 20 square.

We can also use this to determine how large that distance is. The apple is 1030-50 away. The adjacent squares are a distance of 1042-50, 80-50, 1020-50.
So we might decide that jumping to the 20 square is too big of a distance to jump, and might instead prefer to jump to the 80 square.

Like

• Got it, thanks a lot John – my snake is unstoppable now! 🙂 By the way, I’ve made a very boring zig-zag hamilton cycle. Is there an easy way to use that path to create a new, randomized hamilton cycle?

Like

• I don’t know what you mean by “use that path” but you can create a new cycle by generating a maze with all the paths of width 2,and then have the snake walk through that maze, always sticking to the left. As described in the blog

Like

7. joseph

Hey john, great project. I wanted more to know more details about converting the MST to a Hamiltonian cycle. I tried following the code you provided but it didn’t work for me. So can you please elaborate more on converting the MST to the cycle or provide a more detailed commented code.

Like

• Imagine a maze. How could you navigate the entire maze? You put your left (say) hand out and touch the wall. Then you walk, keeping your hand on that wall. In that way, you will navigate the entire maze.

Like the left hand image here: http://datagenetics.com/blog/november22015/sc.png

What didn’t work when you tried the code?

I just had a quick look, and I’m not sure I have the full code any more.

Like

8. Taaha Khan

Hi, I am implementing your algorithm in my own snake game, and I was having some issues when the snake gets a bit bigger. The algorithm seems to be working in the beginning, but towards midgame, the snake starts coiling into itself and getting trapped. I traced the problem back to the end of the algorithm where [if bestDist >= 0: return bestDir]. I found that later in the game, bestDist would stay as the initialized -1, and there wouldn’t be any other direction to travel to. The algorithm would then return any other position that is viable and carry on. This would cause the body to slip out of the range from the tail to the head, and this would cause problems later. Is there another way to get the algorithm to always return a proper direction without just guessing randomly by the end? Also, what exactly is “food.value”?

Thanks for the great tutorial!

Like

• I’m not sure.

Whenever the snake takes a shortcut, there is a risk that that shortcut will lead to its downfall. Imagine a snake taking a shortcut, but then every single square it lands on just happens to have food. It will then continually grow, unable to ever take that path that is had shortcut.

There is no guaranteed way to fix this, other than just never taking shortcuts. As a tradeoff, the code checks if the snake fills more than half the board. If it does, it stops taking shortcuts.

if (numEmptySquaresOnBoard < ARENA_SIZE / 2)
cuttingAmountAvailable = 0;

You could try changing this to:

if (numEmptySquaresOnBoard < 3*ARENA_SIZE / 4)
cuttingAmountAvailable = 0;

Just to see if that fixes it. Just to sanity check, you can even change this to if(true) – in that case it should never take shortcuts, and never crash.

food.value is the how much the food will cause the snake to grow by when it eats the food.

Like

• Taaha Khan

Thanks for the help. I tried fixing some more scenarios to try and optimize the algorithm, but this seems to be an unfixable problem. Thanks for the clarification on food.value, which seemed to also help the algorithm. I thought the growing gain length from food was snake.growth_length. If food.value is the growth amount from food, then what is snake.growth_length and snake.drawn_length?

Like

9. Say the snake is approaching food “4”. So food.value = 4, and snake.growth_length = 0

When it eats the food, snake.growth_length=4, and a new food will be created, so food.value will become 5.

if the snake immediately then ate that food, snake.growth_length=9

If snake.growth_length is bigger than 0, then the snake tail won’t move when the head moves, so snake.drawn_length increases by 1, and snake.growth_length decreases by 1.

Like