**This is a four part series:**

- Part 1 – Electronics
- Part 2 – Display Driver
**Part 3 – Algorithms**- Part 4 – Programming

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) { return tourToNumber[x + ARENA_WIDTH*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; } } while(number != ARENA_SIZE); //Loop until we return to the start } #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; }

Pingback: [C++ nâng cao] – Thiết kế AI tự chơi game rắn săn mồi – Con trỏ vl

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

LikeLike

Yes, ARENA_SIZE = ARENA_HEIGHT * ARENA_WIDTH

LikeLiked by 1 person

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

LikeLike

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

LikeLike

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

LikeLike

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?

LikeLike

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.

LikeLike

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..?

LikeLike

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.

LikeLike

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! 🙂

LikeLike

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.

LikeLike

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?

LikeLike

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

LikeLike

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.

Thanks for your great tutorial

LikeLike

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.

LikeLike