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

NOTE: I have lost the original code, but I’ve recreated it and put it here:

https://github.com/johnflux/snake_game

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;
}