Asteroids: Drawing Objects

Recently I’ve started mentoring a local high school student a bit on implementing a video game, and this is a technical note toward that.

Drawing basic shapes out of polygons to represent game objects is straightforward and requires just a bit of trigonometry, outlined here.

Shapes

The core idea is that the polygon is located around the object’s current position. So, a standard looking Asteroids ship might be defined as four points about the origin as in this diagram:

Four coordinates defining a fairly standard Asteroids player ship.

Four coordinates defining a fairly standard Asteroids player ship.

The polygon is captured by a list (array) of points in order around the shape. Caveat other restrictions in the game’s code, it doesn’t really matter if they’re clockwise or counter-clockwise. In this case the ship is defined as follows, proceeding counter-clockwise:

  1. (0, 24)
  2. (-18, -24)
  3. (0, -18)
  4. (18, -24)

One cute trick that’s often done in Asteroids is to randomly generate the polygons for the asteroids themselves. The points list needs to be in order though or else the lines will overlap and the shape look funny. There are several ways to do this, but one is to go around in a circle, picking a random angle within that arc of the circle, picking a random distance from the origin for that tip of the rock, and computing the x & y value for that polygon point using that angle and distance.

Drawing

In most polygon graphics APIs, drawing starts by starting a new shape if necessary (i.e., newpath) and moving the cursor to the first point in the list (i.e., moveto). It then loops over each of the other points and draws a line from the previous position to the current point (i.e., lineto). The path is then either closed by drawing a line to the first point in the list from the last, or using a specific function to close the path if the API has one (i.e., closepath).

Rotation and Placement

Of course, in the game the object typically has to rotate and move. Rotation is simple because we’re taking the object’s current position as the origin of the polygon representing it. Each point to draw just needs to be calculated through the basic rotation formula:

x' = (x * cos(angle)) - (y * sin(angle))
y' = (x * sine(angle)) + (y * sin(angle))

In these formulas, x and y are the current point in the polygon list while x' and y' are the actual points to draw. The direction the object is currently rotated to, i.e.,which way the player is facing, is in angle.

This will draw the polygon around the origin, but of course the object is actually somewhere else on screen. This is a simple translation, effectively moving the polygon’s origin to the object’s actual position. In other words, just adding the object’s x and y coordinates to the point to draw:

x' = x' + objectx
y' = y' + objecty

Minor Complications

Although the ship above has somewhat naturally been modeled facing up, angle 0 in trigonometry is actually facing to the right. So, the polygon should instead be modeled with its natural direction facing that way.

Adding just a small detail, essentially all modern computer displays and most software use a slightly different coordinate system from what’s typically used in mathematics: The origin is at the top left of the screen, and the y axis increases going down the screen, not up. Note that this means the 90 degree angle is actually facing down and 270 degrees points straight up.

A wide variety of ways to work with these facts can be applied, but the easiest is just to model the polygon facing to the right and to keep that coordinate scheme in mind. So, the example polygon above would actually be modeled as follows:

The ship actually facing angle 0.

The ship actually facing angle 0.

The counter-clockwise ordering of points would then be:

  1. (24, 0)
  2. (-24, -18)
  3. (-18, 0)
  4. (-24, 18)

Another small detail to keep in mind is that nearly all trigonometry functions in software libraries are based on radians rather than degrees, though most people work more easily in the latter. Converting between the two just requires a simple formula based on the identity relationship between them:

radians = pi * degrees / 180

Code

A simple demonstration of this is in the box below. Pressing the left and right arrow keys make the ship rotate, and it’s being drawn in the center of the screen rather than the origin (you may have to click on the box first to focus the keyboard on it):

The code snippets for this below are in Javascript, but should be easily applicable to most platforms.

The polygon for the ship has been defined as follows:

var playershape = [
  { x: 24,  y: 0},
  { x: -24, y: -18},
  { x: -18, y: 0},
  { x: -24, y: 18},
]

It’s just an array of points, each a Javascript object with an x and y value. There is also a player object that has its own x, y, and angle, representing the player’s position and orientation on screen.

A couple trigonometry helper functions are defined, to convert degrees to radians, and to rotate x and y values:

function degtorad(angle) {
  return 3.1415926 * angle / 180;
}

function rotx(x,y,angle) {
  return (x*Math.cos(angle)) - (y*Math.sin(angle));
}

function roty(x,y,angle) {
  return (x*Math.sin(angle)) + (y*Math.cos(angle));
}

Note that each of the x and y rotations take as input x, y, and angle, because the rotation formula requires each of those values.

As discussed above, the ship is drawn by starting a path at the first point of the polygon, looping through each other point, and then closing it off. At each step the point to draw is rotated about the ship’s position as the origin, and then translated to the ship’s actual position on screen. This function captures that, and is called by the main drawing routine each time the ship needs to be displayed:

function drawplayer() {
  var x, y;  // These will be the point to draw.
  var i = 0;  // i is the current polygon point we're using

  ctx.beginPath(); // ctx is the graphics drawing context in this Javascript program.

  // Calculate the actual draw point by rotating and then translating.
  x = rotx(playershape[i].x, playershape[i].y, player.angle) + player.x;
  y = roty(playershape[i].x, playershape[i].y, player.angle) + player.y;
  ctx.moveTo(x, y); // Start the polygon at this point.

  // Loop through the other points---note that this therefore begins at point 1, not 0!
  for (i = 1; i < playershape.length; i++) {
    x = rotx(playershape[i].x, playershape[i].y, player.angle) + player.x;
    y = roty(playershape[i].x, playershape[i].y, player.angle) + player.y;
    ctx.lineTo(x, y); // Extend the path from the previous point to this new one.
  }
  ctx.closePath(); // Close the path by adding a line back to the start.
  ctx.stroke(); // Draw the path.
}

To initialize the player, its position is set to the middle of the screen and its orientation set as facing straight up:

  player.x = canvas.width / 2;
  player.y = canvas.height / 2;
  player.angle = degtorad(270);

Each time the left or right key is pressed, the ship’s angle is updated like this.

    player.angle -= degtorad(10); // Decrease the angle by 10 degrees, making the
                                  // conversion to radians first before subtracting
                                  // from the current angle.
    while (player.angle < 0) {        // This actually isn't necessary, but just makes sure
      player.angle += 3.1415926 * 2;  // the player's angle is always between 0 and 2*pi.
    }                                 // The drawing routines and other logic will all
                                      // handle that fine, but it can make things easier for
                                      // the programmer in writing other parts of the code.

Conclusion

Those are the basic elements in drawing a simple game like Asteroids. The next complication is having an array or arrays of game objects. That’s necessary to capture all of them that might appear on screen, namely the rocks and bullets. A drawing function like that above then needs to be applied to each game object in the array(s), rather than being just hardcoded to a single game object instance like this example is to the player’s ship.

Recursive Shadowcasting

A GIF recording of me running around in something I’ve been playing with lately:

Recursive shadowcasting in action.

Recursive shadowcasting in action.

The baddies have been removed to focus on the visibility. Note how the map starts off unexplored, then my field of vision reveals the map as I go. The fog of war creeps back in as I move on, however, letting me see the map but obscuring what’s underneath; the bad guys don’t show under the fog.

Unfortunately the mechanism being used here isn’t well suited to the game framework. The visibility is being updated by an algorithm called recursive shadowcasting and displayed using a grid of tiles. Unexpectedly, Phaser is seemingly really slow to update tilemaps, more or less confirmed in testing a vastly simpler algorithm. I think this comes from the array copies it does in manipulating tilemaps, combined with the many different flags, event handlers, and other fields it has to both set on each tile and in some cases propagate to adjacent tiles to enable all the different collision manipulations and so on that it supports. However, this may have literally just been resolved as I wrote this. Either way, this approach doesn’t seem to apply well in a straightforward fashion within that toolkit. Either I need to do my own barebones tile rendering of just the visibility layers, or switch to a whole different approach. I’m probably going to do the latter but it’s a really neat algorithm so I wanted to post this code for posterity.

The main structures are that there’s a tilemap for the ground, a player sprite, and then one overlay of semi-transparent black tiles for the fog, and another of opaque black tiles for the unexplored areas. As the player moves around these visibility layers are updated as follows.

The process is kicked off by checking to see if the robot has moved out of its previous tile cell, and then essentially casting cones of light in eight directions, forming a circle around the robot:

var diagonals = [
    { deltaX: -1, deltaY: -1 },
    { deltaX: 1,  deltaY: -1 },
    { deltaX: -1, deltaY: 1 },
    { deltaX: 1,  deltaY: 1 }
];

RobotGame.PlayerRobot.prototype.updateFOV = function() {

    var startx = this.game.visibility.getTileX(this.body.x+this.body.width/2);
    var starty = this.game.visibility.getTileY(this.body.y+this.body.height/2);

    if (startx == this.tilex && starty == this.tiley)
        return;

    this.tilex = startx;
    this.tiley = starty;

    // Set every cell to dark
    this.game.map.fill(69,
                       0, 0,
                       this.game.map.width, this.game.map.height,
                       this.game.visibility);

    this.game.map.putTile(-1, startx, starty, this.game.visibility);

    this.game.map.putTile(-1, startx, starty, this.game.explored);

    for (var i = 0; i < diagonals.length; i++) {
        this.castLight(1, 1.0, 0.0, 0, diagonals[i].deltaX, diagonals[i].deltaY, 0);
        this.castLight(1, 1, 0, diagonals[i].deltaX, 0, 0, diagonals[i].deltaY);
    }

    // end PlayerRobot#updateFOV
};

Each cone is essentially scanned left to right within its expanding scope until it hits an obstruction in the ground tilemap. At that point a new cone is computed and recursively cast out to account for what’s visible around the blockage, and then the scan proceeds to the other side. As they scan they update the visibility grids.

RobotGame.PlayerRobot.prototype.castLight = function(row, start, end, xx, xy, yx, yy) {

    var radius = 15;

    var newStart = 0;
    if (start < end)
        return;

    var blocked = false;
    for (var distance = row; distance < radius && !blocked; distance++) {
        var deltaY = -distance;
        for (var deltaX = -distance; deltaX <= 0; deltaX++) {
            var currentX = this.tilex + deltaX * xx + deltaY * xy;
            var currentY = this.tiley + deltaX * yx + deltaY * yy;

            var leftSlope = (deltaX - 0.5) / (deltaY + 0.5);
            var rightSlope = (deltaX + 0.5) / (deltaY - 0.5);

            if (!(currentX >= 0 && currentY >= 0 &&
                  currentX < this.game.map.width &&
                  currentY < this.game.map.height) ||
                start < rightSlope) {
                continue;
            } else if (end > leftSlope) {
                break;
            }

            if ((deltaX * deltaX) + (deltaY * deltaY) <
                ((radius-3) * (radius-3))) {
                this.game.map.putTile(-1, currentX, currentY,
                                      this.game.visibility);
            }

            if ((deltaX * deltaX) + (deltaY * deltaY) <
                (radius * radius)) {
                this.game.map.putTile(-1, currentX, currentY,
                                      this.game.explored);
            }

            var tile = this.game.map.getTile(currentX, currentY,
                                             this.game.ground);
            if (blocked) {

                if (tile && tile.canCollide) {
                    newStart = rightSlope;
                    continue;
                } else {
                    blocked = false;
                    start = newStart;
                }

            } else {

                if (tile && tile.canCollide && distance < radius) {
                    blocked = true;
                    this.castLight(distance+1, start, leftSlope,
                                   xx, xy, yx, yy);
                    newStart = rightSlope;
                }

            }

            // end for deltaX
        }
        // end for distance
    }

    // end PlayerRobot#castLight
};

There is a more detailed explanation in the RogueBasin Wiki. This implementation is basically a few minor tweaks on that in SquidLib, a roguelike library. The changes incorporate the two levels of visibility with different radii, and switch a couple ≤ comparisons on the radius to strict < in order to eliminate weird single-cell artifacts.

I’m bummed this isn’t working out as it makes a couple things very simple, like waking up bad guys when the player sees them and updating their visibility. It’s also just a cool algorithm. I really like the discrete scanning within the grid defined by recursive splits into diagonal cones. On the other hand, a more polygonal approach will yield more intuitive results. This recursive shadowcasting is really more suited for roguelikes with movement in discrete grid steps and their own conventions and traditions on visibility. The polygonal approach is also much more aligned with the pathfinding used by the bad guys. Details on that to come!

RocketHaxe 2.0: Gettin’ All JRPG Up In Here

A new demo from tonight; arrow keys to move (click first to focus), and mouse-drag to move the viewport around:

This is another demo of RocketHaxe 2.0’s simple tile engine, here using the physics engine and collisions for basic moving around in a top down view rather than platforming. Note that the guy sometimes gets hung up on corners and doesn’t walk right up to the water because the tiles are fairly large and not filled by the water. The map is a simple CSV file autotiled against some nice tiles from OpenGameArt by Robotality:

Tiles by Robotality.

Tiles by Robotality.

The big recent progress here though is showing off sprite animations, ported over fairly directly from RocketHaxe 1.0. The character here is from an RPG character pack by Antifarea and also released on OpenGameArt:

RPG townfolk character by Antifarea.

RPG townfolk character by Antifarea.

Code

Ignoring the imports, this is the entirety of the code for that demo right now:

class Main
  extends com.rocketshipgames.haxe.Game
{

  private var game:ArcadeScreen;

  private var spritesheet:SpritesheetContainer;

  //--------------------------------------------------------------------
  public function new():Void
  {

    //------------------------------------------------------------------
    //-- Initialize ----------------------------------------------------

    trace("Tiles Demo");

    // The base Game class sets up the display, mouse, audio, etc
    super();

    // ArcadeScreen is a Screen which drives a game World (entities,
    // mechanics, etc), renders graphics, pauses on unfocus, etc.
    game = new ArcadeScreen();

    // Spritesheets wrap a single bitmap containing multiple frames,
    // which are ultimately used as textures for polygons to draw
    // characters, tiles, etc., with a single memory transfer per
    // frame rather than blitting each one.  This can be just a
    // touch slower on PCs, but is much faster on mobile devices.
    spritesheet = new SpritesheetContainer
      (Assets.getBitmapData("assets/spritesheet.png"));
    game.addGraphicsContainer(spritesheet);


    //------------------------------------------------------------------
    //-- Tilemap -------------------------------------------------------

    // Tile catalogs capture information about map tiles: Size,
    // sprite frame, collision classes, etc.
    var tileCatalog = TileCatalog.load(Assets.getText("assets/tiles.xml"),
                                   spritesheet);

    // A chunk is an array of tiles, here capturing the overhead map.
    var chunk = TileChunk.loadCSV(tileCatalog,
                                  Assets.getText("assets/map.csv"),
                                  TileChunk.autotileRPG);

    // The collider detects and resolves objects colliding with tiles.
    var collider = new ImpulseTileChunkCollider(chunk);
    game.world.mechanics.add(collider);

    // The renderer actually draws the tiles.
    var tiledraw = new TileMapRenderer(chunk);
    spritesheet.addRenderer(tiledraw);

    // Center the viewport over the map to begin with.
    game.viewport.activate({bounds: chunk, drag: true});
    game.viewport.set(((chunk.right()-chunk.left()) - game.viewport.width)/2,
                      ((chunk.bottom()-chunk.top()) - game.viewport.height)/2);


    //------------------------------------------------------------------
    //-- Character -----------------------------------------------------

    // Sprite catalogs collect all of the different sprites on a
    // spritesheet and their information: Size, animations, etc.
    var spriteCatalog =
      GameSpriteCatalog.load(Assets.getText("assets/sprites.xml"), spritesheet);

    // The renderer draws all the sprite instances currently active.
    var sprites = new GameSpriteRenderer();
    spritesheet.addRenderer(sprites);


    // The character is a completely generic RocketHaxe component
    // container to which we'll add functionality.
    var walker = new com.rocketshipgames.haxe.component.ComponentContainer();

    // Get the particular sprite to use in order to pull its dimensions.
    var sprite = spriteCatalog.get("walker");

    // Add a physical body to the walker, a simple box body and basic
    // kinematics properties for walking around at a reasonable pace.
    walker.add(RigidBody2DComponent.newBoxBody
               (0.75*sprite.pixelWidth/game.viewport.pixelsPerMeter,
                0.75*sprite.pixelHeight/game.viewport.pixelsPerMeter,
                {x: (chunk.right()-chunk.left())/2,
                 y: (chunk.bottom()-chunk.top())/2,
                 xvel: 0, yvel: 0,
                 xvelMax: 5, yvelMax: 5,
                 ydrag: 42, xdrag: 42,
                 collidesWith: 1,
                 restitution: 0.5,
                }));

    // Add a generic keyboard controller to the walker.  Custom
    // controls could of course be written.  This component is
    // inserted after the rigid body representation because it's
    // dependent on the body's kinematics, but it's inserted (front of
    // the walker's component list) rather than added (back of the
    // list) because we want it each loop before the kinematics.
    walker.insert(KeyboardImpulseComponent.create({facing: DOWN}));

    // Instantiate a sprite to display the character on screen.  The
    // component used here is a generic default that uses some
    // conventions on the sprite to make it face left/right/up/down
    // and animate when moving.
    walker.add(new FacingGameSpriteComponent(spriteCatalog.get("walker"), true));

    // Have the viewport install a tracking component into the walker.
    game.viewport.track(walker, {margin: Math.max(tileCatalog.width,
                                                  tileCatalog.height) * 4});

    // Finally, make the walker live by adding to the sprite render,
    // tilemap collider, and overall gameworld.
    sprites.add(walker);
    collider.add(walker);
    game.world.entities.add(walker);


    //------------------------------------------------------------------
    //-- Startup -------------------------------------------------------

    // Add the game to the display.  In a real game this would be
    // done using ScreenManager to transition between menus, etc.
    flash.Lib.current.addChild(game);

    // Display the cursor for dragging the viewport.
    Mouse.enable();

    // end new
  }

  // end Main
}

Tile Physics

The tile physics demo of course also shows off tiles and objects interacting, now with some basic platformer autotiling (this is a GIF recording):

GIF of the tile physics demo.

GIF of the tile physics demo.

Next up: Sound!