Snake: Making The Game

Snake as I know it, is a game where the player controls a snake that is always in motion in a given direction where the goal is to eat apples that are randomly scattered around the play area. If the snake leaves the play area or comes in contact with itself, it will die. As the snake eats, it grows longer, and planning ahead becomes more important to prevent the snake from trapping itself and dying.

That basically sums up the game. For my implementation, I will also include the ability to add walls to create mazes for the snake to navigate.

Table Of Contents

Custom Classes

Node

A Node is the base object used for every most objects that interact in the play area. Aside from just storing its own x and y coordinates, it also contains a few useful methods:

1. Check if the node is still within the boundaries of the game.

node.inBounds = (nx, ny) => node.x>=0 && node.x<nx && node.y>=0 && node.y<ny

2. Check if two nodes are in the same position.

node.eq = n => node.x == n.x && node.y == n.y

3. Sums the x and y values with their counterparts from a given node. Used in generating nodes in a given direction.

node.sum = n => Node(node.x + n.x, node.y + n.y)

4. Subtracts the x and y values with their counterparts from a given node. Used for calculating the direction a given node is in.

node.sub = n => Node(node.x - n.x, node.y - n.y)

Node Set and Map

The NodeSet and NodeMap objects are wrappers around the Javascript Map object. They encode the given x and y coordinates of a node as a string to function as the key for Node using the following function:

ns.encXY = (x, y) => `${x},${y}`

In comparison with a plain Map object, this method lets us use the location as a key instead, providing more flexibility by only only requiring the passed nodes have the same x and y coordinates as opposed to needing to use the exact same Node object on a get() call.

Game Components

Directions

This game has four possible moves from each location, North, South, East and West. These directions are vectors represented as Nodes:

NORTH: Node(0,-1),
SOUTH: Node(0,1),
EAST: Node(1,0),
WEST: Node(-1,0),

When a node at a given location is summed with a given direction, it will return its neighbor, a new Node that is displaced by 1 in that direction. When a node is subtracted by one of its neighbors, it will result in the returned Node being a direction.

Initially, a snake was allowed to use any of these directions at any time. If a snake is moving North, and then was commanded to move South, it will essentially backtrack into itself and die. While that's not a problem on its own, it makes the exploration phase for algorithms like Q-Learning extremely inefficient as one in four moves at any point in time will be fatal. Thus, I decided to filter out these moves in the game itself.

const isValidDir = (snake, dir) => dir==null ? false : !game.nextHead(snake, dir).eq(snake[1]),

Walls

Each wall segment can simply be thought of as a Node that the snake's head must not land on. This is achieved simply by implementing the walls variable as a NodeSet for fast collision detection.

Apples

Apples are just plain Node objects, and are generated and placed into random unoccupied coordinates.

const nextApple = (nx, ny, snake, walls) => {
  if (snake.length + walls.size() >= nx*ny) return null
  let apple = null
  while(apple==null || snake.some(node => node.eq(apple)) || walls.has(apple.x, apple.y)) {
    apple = Node(utils.randInt(0, nx-1), utils.randInt(0, ny-1))
  }
  return apple
}

This function will start to become a problem on large grids that are close to being fully occupied as it has to basically luck into an empty space. But until I implement a player that can get to that stage in the game, it's good enough for now.

Snakes

A snake is an array of Node objects, where the head is at index 0.

In order for the snake to advance a step, we'd need to know the position it's head is going to end up at. This is achieved simply by summing the node of the current head with a given direction.

const nextHead = (snake, dir) => snake[0].sum(dir)

With the new head, we can run the checks needed to determine the snake's status following the move.

The first is whether it will collide with an apple, thereby eating it.

const willEat = (head, apple) => head.eq(apple)

Second, will it leave the bounds of the game, collide with itself or a wall?

const willLive = (nx, ny, head, snake, walls) => {
  return head.inBounds(nx, ny) && !snake.some(node => node.eq(head)) && !walls.has(head.x, head.y)
} 

If a snake eats an apple it will grow and we simply just append the new head to the array. If it moves into an empty space, the head is still added, but the old tail segment also has to be removed to maintain the correct length.

const nextSnake = (snake, head, grow) => [head].concat(grow ? snake : snake.slice(0,-1))

State Object

A State object holds all information needed to reconstruct the game at that particular point in time. It contains:

1. isAlive: True when a snake has not collided with itself or any obstacles.
2. justEaten: True when a snake had just eaten an apple and grown during the evaluation that produced this state object.
3. snake: Snake array.
4. direction: The direction the snake is currently moving in.
5. apple: Apple Node object.
6. walls: Walls NodeSet object.
7. nx and ny: The number of cells in the X and Y axis of the play area.

This object is initialized by calling next() after the function has been initialized with nx, ny and walls. The next() function is also responsible for advancing the state ahead by one time step.

const next = (nx, ny, walls) => (state=null, update=null) => {
  if (state==null) {
    const yStart = Math.floor(ny/2)
    const snake = [Node(1,yStart), Node(0,yStart)]
    return {
      isAlive: true,
      justEaten: true,
      snake: snake,
      direction: game.EAST,
      apple: game.nextApple(nx, ny, snake, walls),
      walls: walls,
      nx: nx,
      ny: ny
    }
  } else {
    const isValidDir = game.isValidDir(state.snake, update ? update.direction : null)
    const direction = isValidDir ? update.direction : state.direction 
    const head = game.nextHead(state.snake, direction)
    const willEat = game.willEat(head, state.apple)
    const willLive = game.willLive(state.nx, state.ny, head, state.snake, state.walls)
    const snake = willLive ? game.nextSnake(state.snake, head, willEat) : state.snake
    return {
      isAlive: willLive,
      justEaten: willEat,
      snake: snake,
      direction: direction,
      apple: willEat? game.nextApple(state.nx, state.ny, snake, state.walls) : state.apple,
      walls: state.walls,
      nx: state.nx,
      ny: state.ny
    }
  }
}

When a state is supplied, it advances the state, otherwise it returns a brand new initialized one. When it advances the state, it uses all the functions that were mentioned before to update the information provided by the state object.

When a snake leaves the play area, its head goes out of bounds which causes issues for policy based agents. Thus, I made it so when the snake leaves and dies, it just does not move, as the death status is already captured by the isAlive variable.