Boulder Dash Part 1: Implementing Sprite AI

One of the projects I've had on the back-burner for over a year now was a Boulder Dash clone. While I was working on this clone I written a basic game engine using GDI, another using managed DirectX, editing tools, and even a conversion tool for the BDCFF. Everything but the game itself.

After working pretty much nonstop on the Sitemap Creator and WebCopy tools recently, I wanted to take things a bit easy between releases and wanted to resurrect this project.

If you haven't heard of Boulder Dash you're missing out on some classic gaming of yesteryear. Basically, it involved collecting a given number of diamonds in a cave, and there were various enemies (butterflies and fireflies) and game elements (diamonds, boulders, various types of walls, slime, amoeba) which you use to beat each cave. There's lots more than this basic synopsis of course, but it covers the essential elements you will see.

This series of articles will describe some of the design of the game using sample projects to demonstrate the different elements, starting with the AI of the enemies.

In Boulder Dash, enemies don't follow a specific path, nor do they chase you as such. Instead, they are governed by a series of rules.

Firefly Movement Rules

if the space to the firefly's left is empty then turn 90 degrees to firefly's left and move one space in this new direction
otherwise if the space ahead is empty then move one space forwards
otherwise turn to the right, but do not move

This pattern means a firefly can instantly turn left, but takes double the time when turning right.

Butterfly Movement Rules

The butterfly shares the same basic rules as the firefly, the exception being that the directions are reversed. For the butterfly, the preferred turning direction is right rather than left. So the butterfly can instantly turn right, but is slower at moving left.

The sample project

The sample project (available to download from the link below) creates a basic testing environment. A map is randomly generated to which you can add fireflies or butterflies. A directional arrow displays the current facing of the sprites. Each second the sprites will be updated.

In this first article we aren't interested in further topics such as collision detection, we just want to make sure our sprites move according to the rules above.

The basic logic for each sprite is:

can I move in my preferred direction?
can I move straight ahead?

If the answer to either of these questions is "Yes", then our sprite will move. If "No", then it will turn in the opposite direction to its preferred direction.

In Boulder Dash, each cave (level) is comprised of a grid of tiles, nothing fancy. The player can move up, down, left or right, but not diagonally. All other game elements are constrained in the same way.

The following snippet shows the movement logic for the Firefly:

csharp

// first see if we can move in our preferred direction, left
tile = this.GetAdjacentTile(this.GetNewDirection(Direction.Left));
if (!tile.Solid)
{
  // we can move here, update our position and also set our new direction
  this.Location = tile.Location;
  this.Direction = this.GetNewDirection(Direction.Left);
}
else
{
  // can't move in our preferred direction, so lets try the direction the sprite is facing
  tile = this.GetAdjacentTile(this.Direction);
  if (!tile.Solid)
  {
    // we can move here, update our position, but not the direction
    this.Location = tile.Location;
  }
  else
  {
    // can't move forwards either, so finally lets just turn right
    this.Direction = this.GetNewDirection(Direction.Right);
  }

The above code relies on two helper methods, one to return a new direction based on the current direction, and a second to return an adjacent cell from a given direction.

GetNewDirection

The GetNewDirection method below calculates a new direction based on the current sprites direction and a new facing of either left or right.

csharp

public Direction GetNewDirection(Direction turnDirection)
{
  Direction result;

  switch (turnDirection)
  {
    case Direction.Left:
      result = this.Direction - 1;
      if (result < Direction.Up)
        result = Direction.Right;
      break;
    case Direction.Right:
      result = this.Direction + 1;
      if (result > Direction.Right)
        result = Direction.Up;
      break;
    default:
      throw new ArgumentException();
  }

  return result;
}

GetAdjacentTile

The GetAdjacentTile method simply returns the text next to the current sprite in a given direction.

csharp

public Tile GetAdjacentTile(Direction direction)
{
  Tile result;

  switch (direction)
  {
    case Direction.Up:
      result = this.Map.Tiles[this.Location.X, this.Location.Y - 1];
      break;
    case Direction.Left:
      result = this.Map.Tiles[this.Location.X + 1, this.Location.Y];
      break;
    case Direction.Down:
      result = this.Map.Tiles[this.Location.X, this.Location.Y + 1];
      break;
    case Direction.Right:
      result = this.Map.Tiles[this.Location.X - 1, this.Location.Y];
      break;
    default:
      throw new ArgumentException();
  }

  return result;
}

Once the sample has gotten a tile, it will check to see if the sprite can move into the tile. For our example, we are just using a bit flag to state if the tile is solid or not, but in future we'll need to add collision detection for all manner of game elements.

If the sprite can move into the first tile into its preferred direction, it will do this. Otherwise, the movement routine will next check to see if the tile in front of the sprite is solid, and if so again it will move. If neither of the two movements were possible then it will update it's current facing to be the opposite of it's preferred direction. The process will be repeated for each "scan" of the game elements.

Using these rules it is quite easy to setup scenarios where the sprites can "guard" a game element by endless circling it. And just as easily the unwary player will be chased mercilessly if they are unwary.

Please let us know if you'd like to see more of this type of article here on cyotek!