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

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!