Starting a Snakes Game

Fri, Aug 5, 2011

Earlier in the year I started experimenting with very simple HTML5 games like Pong and Breakout.

Next up on my list is a snakes game.

The underlying mechanics of a snakes game is very simple, wander around a two dimensional grid, eating food to grow larger, avoid colliding with obstacles, grow as large as possible.

Implementing the raw mechanics of this is quite easy (see below the fold for details), so this time around I want to focus on the polish that will make the game feel ‘finished’, for example:

It will probably take a fair amount of time and effort to provide all this polishing, even with a simple game like snakes. In fact the effort to provide the polish far outweighs the effort to build the raw game mechanics.

So, before I dive into ‘finishing’ the game. I thought I would take some time out to show how to build the simple, raw unpolished, snakes mechanics using javascript and the HTML5 <canvas> element.

Demo

Before I get started, here is the raw game itself in its simplest form. It’s keyboard controlled so hit <space> to start the game and use the arrow keys to move the snake around.

Sorry, this example cannot be run because your browser does not support the <canvas> element

<space> to start, arrow keys to change direction

Data Structure

There are a couple of approaches for the data structure for a snakes game. Some prefer to use a large 2 dimensional array for the grid and maintain the position (and direction) for the head and the tail of the snake.

I found this approach to be a little messy, particularly around maintaining the correct direction for the tail, having to update the old and the new head positions, and for dealing with multi-player collision detection if only a single object can live in each cell at any one time.

I found that the code came out a lot cleaner if I maintained a simple queue of snake segments (x,y coordinates) and a single direction for the snake’s head. That way it became almost trivial to pop off the tail of the snake and push on a new head.

There is an interesting trade off here. The 2 dimensional array might take up more memory and lead to slightly messier code but has constant O(1) time collision detection. While the queue implementation uses less memory and leads to simpler and more flexible code, but might have performance implementations since we have to do a linear O(n) walk through the queue to perform collision detection checks.

In reality, for a game played on a 64x64 grid, with a total of 4096 cells, neither of these approaches really causes a problem. A 4096 item array should not trouble the memory consumption of a modern browser, but neither should a linear walk through a queue of only a few hundred items.

All things being equal, I would prefer to choose the simpler queue implementation.

To verify the performance of a linear pass though a queue, I created a jsperf.com test case that performs simple x/y coordinate checks on a (worse-case) 4096 segment snake.

It tests for 4 cases

And even in the worse case, when the match is made late (or not at all), in the worse performing browser for this test (firefox), on a fairly underpowered laptop, it could scan the entire 4096 segment queue over 8000 times a second. So at 60 frames per second we can check for a collision against a snake over 100 times in each and every frame… and that is worse case.

In the optimistic case where the collision is within the first 100 segments of the snake, on the fastest browser (chrome) we could perform that collision check over 600,000 times per second.

So, having to do a linear scan over a queue for collision detection is not going to be a problem for this simple game. If we had a much bigger playing area, or the collision detection was more complex than single point collisions we might need to rethink this and implement a spatial index, or revisit the 2 dimensional array, but I think we can be pretty safe that, for our purposes, this is not going to be a problem.

Now that we know that our data structure will be a simple queue, we can move on to implementation…

Game State

The javascript source for the game can be found here.

Remembering that this is just an example of the mechanics, and not production ready code, we don’t need to over-engineer any kind of complicated OO class design. So lets start off by declaring our game state as simple variables:

var KEY     = { ESC:27, SPACE:32, LEFT:37, UP:38, RIGHT:39, DOWN:40  },
    DIR     = { UP:0, DOWN:1, LEFT:2, RIGHT:3, OPPOSITE:[1, 0, 3, 2] },
    canvas  = document.getElementById('canvas'),
    width   = canvas.width  = canvas.offsetWidth,
    height  = canvas.height = canvas.offsetHeight,
    ctx     = canvas.getContext('2d'),
    nx      = 44,
    ny      = 33,
    dx      = width  / nx,
    dy      = height / ny,
    playing = false,
    dstep, dt, length, moves, dir, growth, head, tail, food;

For this particular example I ended up making the grid even smaller at 44 x 33 cells (to fit this blog article) and we make the <canvas> logical size equal to its physical size to avoid rendering scaling artifacts.

We declare some other variables that need to be re-initialized with every new game:

function reset() {
  dstep  = 0.06,
  dt     = 0;
  moves  = [];
  dir    = DIR.LEFT;
  head   = tail = { x: 40, y: 5 };
  length = 1;
  growth = 10;
  while(--growth)
    increase();
  food = unoccupied();
};

The Game Loop

Our game loop is a traditional update/draw loop using setTimeout

function timestamp() { return new Date().getTime(); };

var start, last = timestamp();
function frame() {
  start = timestamp();
  update((start - last) / 1000.0);
  draw(ctx);
  last = start;
  setTimeout(frame, 1);
}

reset(); // reset the game state
frame(); // and start the loop

A more robust HTML5 game loop would want to use requestAnimationFrame instead of setTimeout.

Handling Keyboard Input

We allow user input via keyboard by binding a global key down event handler that allows us to stop and start the game and also record any snake moves to be used during our update method.

For keydown events that we want to handle ourselves, we must ensure we preventDefault to stop the default action from, for example, scrolling the page up and down when we change the snakes direction up or down.

document.addEventListener('keydown', onkeydown, false);

function onkeydown(ev) {
  var handled = false;
  if (playing) {
    switch(ev.keyCode) {
      case KEY.LEFT:   move(DIR.LEFT);  handled = true; break;
      case KEY.RIGHT:  move(DIR.RIGHT); handled = true; break;
      case KEY.UP:     move(DIR.UP);    handled = true; break;
      case KEY.DOWN:   move(DIR.DOWN);  handled = true; break;
      case KEY.ESC:    lose();          handled = true; break;
    }
  }
  else if (ev.keyCode == KEY.SPACE) {
    play();
    handled = true;
  }
  if (handled)
    ev.preventDefault(); // prevent arrow keys from scrolling the page
};

function move(where) {
  var previous = moves.length ? moves[moves.length-1] : dir;
  if ((where != previous) && (where != DIR.OPPOSITE[previous]))
    moves.push(where);
};

function play() { reset(); playing = true;  };
function lose() {          playing = false; };

We do not do any work during the key event handler, we simply record the move for use during our update method.

Updating the Game

Our update method increments dt and if past dstep it will move the snake by increasing its head (potentially in a different direction) and decreasing its tail.

Once the snake has moved, if the new head is a cell that is occupied by the snake then the game is over, otherwise if the cell contains food then the snake grows and a new food item is placed.

function update(idt) {
  if (playing) {
    dt = dt + idt;
    if (dt > dstep) {
      dt = dt - dstep;
      increase(moves.shift());
      decrease();

      if (snakeOccupies(head, true)) {
        lose();
      }
      else if (foodOccupies(head)) {
        growth += 10;
        food = unoccupied();
      }
    }
  }
};

Rendering the Game

Our draw method consists of simple canvas drawing commands to render the food, the snake head, all of the snake body segments and the ‘score’.

function draw(ctx) {
  ctx.clearRect(0, 0, width, height);
  ctx.globalAlpha = playing ? 1.0 : 0.5;
  ctx.fillStyle = 'green';
  ctx.fillRect(food.x * dx, food.y * dy, dx, dy);
  ctx.fillStyle = 'black';
  ctx.fillRect(head.x * dx, head.y * dy, dx, dy);
  var segment = head, n = 0;
  while(segment = segment.next) {
    ctx.fillStyle = '#1080F0';
    ctx.fillRect(segment.x * dx + 1, segment.y * dy + 1, dx - 2, dy - 2);
  }
  ctx.fillStyle = 'green';
  ctx.font = 'bold 18pt arial';
  ctx.fillText(length.toString(), 10, 30);
};

Rendering everything, for each frame at 60fps can be a performance problem. In this simple case, with a few hundred snake segments, the draw method can take about 4 or 5ms which is less than the 16ms limit (1000/60) we need to hit for a 60fps game. So this looks like it should be ok.

Another quick jsperf.com test case shows us that in a worse case scenario, where we need to render every cell of a 64x64, in the worse performing browser (IE) we would struggle to render at 60fps, but if we only need to render about 100 cells then 60fps should be no problem.

We dont expect to get near this worse case scenario in our simple version, and so can be somewhat confident that we wont hit problems.

If rendering does become more complex and slows down, we can easily improve the performance by recognizing that we only really need to redraw the new head and the old tail, so we could maintain a cached offscreen canvas that is rerendered incrementally (this is likely what I will need to do in the final game, so I’ll talk more about that in a future article).

Managing Snake Growth

We manage snake growth by using a simple queue data structure with push and pop methods:

function push(segment) {
  length++;
  if (head) {
    head.prev = segment;
    segment.next = head;
  }
  head = segment;
};

function pop() {
  length--;
  if (tail.prev) {
    tail = tail.prev;
    tail.next = null;
  }
};

We made the snake step during update by increasing its head and decreasing its tail.

Increasing the head, we need to account for change of direction, and some simple math to allow the snake to wrap around to the other side of the play field.

function increase(changeDir) {
  dir  = (typeof changeDir != 'undefined') ? changeDir : dir;
  switch(dir) {
    case DIR.LEFT:  push({x: head.x == 0    ? nx-1 : head.x-1, y: head.y                           }); break;
    case DIR.RIGHT: push({x: head.x == nx-1 ? 0    : head.x+1, y: head.y                           }); break;
    case DIR.UP:    push({x: head.x,                           y: head.y == 0    ? ny-1 : head.y-1 }); break;
    case DIR.DOWN:  push({x: head.x,                           y: head.y == ny-1 ? 0    : head.y+1 }); break;
  }
};

Decreasing the tail is trivial, if we are growing then do nothing, otherwise pop off the tail.

function decrease() {
  if (growth)
    growth--;
  else
    pop();
};

Collision Detection

The remaining code is some simple collision detection logic.

function occupies(a, b) {
  return a && b && (a.x == b.x) && (a.y == b.y);
};

function foodOccupies(pos) {
  return occupies(food, pos);
};

function snakeOccupies(pos, ignoreHead) {
  var segment = ignoreHead ? head.next : head;
  do {
    if (occupies(segment, pos))
      return true;
  } while (segment = segment.next);
  return false;
};

function unoccupied() {
  var pos = {};
  do {
    pos.x = Math.round(random(0, nx-1));
    pos.y = Math.round(random(0, ny-1));
  } while (foodOccupies(pos) || snakeOccupies(pos));
  return pos;
};

function random(min, max) {
  return (min + (Math.random() * (max - min)));
};

What Next ?

Ok, so we can build the underlying structure for a snakes game in just a few hours with less than 200 lines of javascript code… but that does not make a finished game.

Over the next few weeks, I hope to spend some time on all the things that might turn this into a real game:

Hopefully I’ll have some progress to report next time!

Enjoy!