Asteroids Available for Hackvision

I’m very happy to announce Asteroids for Hackvision. This arcade classic gives you real arcade action written completely using Arduino. You can download it from the Hackvision games page, or order it pre-loaded on a Hackvision.

Game play is just like you remember:

• Shoot the asteroids and they break into smaller asteroids. Large asteroids are worth 20 points, medium 50 points, and small 100 points.
• Press the thrust button to move your ship forward. Unlike in real space, there is drag which slows your ship to a stop over time.
• Watch out for the flying saucer — it shoots in random directions and can crash into you. Shoot it for 500 points.
• If you are in real trouble, press the hyperspace button. This transports you to a different location, but that location may be very dangerous, too!
• When all the asteroids on a level are destroyed, a new level starts. Higher levels have more asteroids.
• You start with 3 ships, and get an extra ship every 10,000 points.
• At the end of the game you can enter your initials if you got one of the top 10 high scores. High scores are stored in EEPROM so they are not erased when power is off. Also, different games use different high score “files” in EEPROM, so your Asteroids scores won’t interfere with your Space Invaders scores, etc.

Here’s how the controls work:

Controls for Asteroids

Programming Details

Most of the objects drawn on the screen are defined as bitmaps. An asteroid is simply a bitmap defined in asteroid_bitmaps.h. Other files define bitmaps for the ship, flying saucer, explosions, etc. A customized version of TVout’s bitmap function allows bitmaps to be overlayed on each other without erasing the pixels underneath. This allows asteroids to overlap without overwriting each other.

The main loop of the game looks basically like this. Some details are omitted, but this is the basic idea:

void loop() {
  moveAsteroids();
  moveShots();
  getInput();
  moveShip();
  drawShip();
  drawSaucer();
  killed = detectCollisions();
  if (killed) {
    // pause and reset the ship...
  }
  drawExplosions();
  if (nAsteroids == 0) {
    // reset variables...
    newLevel();
  }
  if (remainingShips == 0) {
    gameOver();
    if (score > 0) {
      enterHighScore(1);
    }
  }
}

This game is all about collision detection. While the game is running, the code needs to detect the following collisions:

• collisions between your ship and asteroids
• collisions between the shots you fire and asteroids
• collisions between the saucer and your ship
• collisions between the saucer’s fired shot and your ship
• collisions between the shots you fire and the saucer

This sounds like a lot of work, but the ATmega328 has more than enough speed to perform all these computations many times per second. The key to these collision detections is using a “point in polygon” algorithm which determines whether a point is within the bounds of a polygon defined as a set of vertices.

Each object displayed on the screen is defined by a set of vertices for the purpose of detecting collisions. The vertices define a polygon which let us detect if a point is in the polygon. For example, the code needs to detect if any of the shots fired by our ship are within any of the polygons that define the asteroids. This point-in-polygon algorithm is used for all collision detection in the game. Polygons are defined in the vertices source files, e.g. asteroid_vertices.cpp and saucer_vertices.cpp.

The point-in-polygon algorithm is surprisingly short, but not very easy to understand. Here’s the function inPolygon which takes as arguments the number of vertices, an array of the X coordinates of the vertices, an array of the Y coordinates of the vertices, and the (x,y) coordinates of the point we are testing.

/*                                                                                                 
 * This is the point-in-polygon algorithm adapted from                                             
 * http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html                          
 */
boolean inPolygon(byte nvert, byte *xvert, byte *yvert, int x, int y) {
  char i, j;
  byte xvi, xvj, yvi, yvj;
  boolean inside = false;
  for (i=0, j=nvert-1; i<nvert; j=i++) {
    xvi = pgm_read_byte(xvert + i);
    xvj = pgm_read_byte(xvert + j);
    yvi = pgm_read_byte(yvert + i);
    yvj = pgm_read_byte(yvert + j);
    if ( ((yvi > y) != (yvj > y)) &&
         (x < (xvj - xvi) * (y - yvi) / (yvj - yvi) + xvi) )
       inside = !inside;
  }
  return inside;
}

Notice that the vertices are read from the AVR flash memory using the function pgm_read_byte(prog_uchar *pointer). I stored all the bitmaps and vertices in flash memory to conserve SRAM. This is critical when developing games on the ATmega328 since it only has 2K of SRAM. For more info on using flash memory, see the Arduino page on this subject.

Sound Design

With this game I took the sound design to a new level. The TVout library provides a simple tone(frequency, duration) function for generating tones using PWM on Arduino pin 11. This mechanism is very limiting when trying to create sounds for games. It’s easy to start a tone and have it play for a specified duration, but it’s difficult to create sound effects that require the rapid changing of frequency while still allowing the game to continue forward.

I needed a more dynamic mechanism to create the laser shot sound effect which requires the frequency to drop rapidly at a fixed rate of change so it didn’t sound too choppy. The solution was to take advantage of the VBI hook feature of TVout. VBI means Vertical Blanking Interval, and it’s the time period between the end of one screen frame and the beginning of the next frame. TVout draws at 60 frames per second (with NTSC), so there are 60 VBIs per second. The TVout function set_vbi_hook(void (*func)()) allows you to specify a function to be called at the end of every frame. This means you can specify some code to run 60 times per second at a perfectly uniform rate.

I created a function soundISR() to run at each VBI. This function checks to see if there is a sound playing, and a flag tells it whether the sound is the FIRE sound (laser shot) or EXPLOSION sound. Then the frequency is changed accordingly (e.g. for laser shot, decrement the frequency by 100 Hz) and the pin 11 PWM registers adjusted accordingly by the function setPWMFreq(unsigned int f). The sound effect is still initiated by calling tv.tone(freq, duration) and terminated by the TVout library, but my function modifies the frequency 60 times a second as needed. This led to a much better way of generating sound effects without interrupting game play.

Hacking Ideas

• Give yourself more lives. Find the line of code that sets remainingShips = 3 and change it.
• Enable “autofire” so you can hold the fire button down. Find the line in the code that says “uncomment for autofire”.
• Define your own bitmaps for the asteroids. What would you like to shoot? Also define vertices that define the bounding poloygon.
• Change the sound effects.
• Wire up an alternate controller using some awesome arcade buttons.