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 =;
    var starty =;

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

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

    // Set every cell to dark,
                       0, 0,
             ;, startx, starty,;, startx, starty,;

    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)

    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 < &&
                  currentY < ||
                start < rightSlope) {
            } else if (end > leftSlope) {

            if ((deltaX * deltaX) + (deltaY * deltaY) <
                ((radius-3) * (radius-3))) {
      , currentX, currentY,

            if ((deltaX * deltaX) + (deltaY * deltaY) <
                (radius * radius)) {
      , currentX, currentY,

            var tile =, currentY,
            if (blocked) {

                if (tile && tile.canCollide) {
                    newStart = rightSlope;
                } 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!

Line Test Demo

While entangled in the bowels of a diseased telecon I decided to make good use of my time and wrote this simple test:

Click, drag, and release to draw a new line. The text will (should?!) indicate whether or not the two points are on the same side of the line or not.

The demo uses some basic Phaser features for the interaction and drawing. Really though it’s just quadruple checking a basic calculation:

(Bx – Ax) * (Cy – Ay) – (By – Ay) * (Cx – Ax)

Where the line is defined by (Ax,Ay)–(Bx,By) and a point is (Cx, Cy). The value will be 0 if the point is on the line, and otherwise negative or positive depending on which side of the line it is on. The specific sign depends on the orientation of the line, but you can compare the sign for two points to determine if they’re on the same side or not. That can be boiled down into a single calculation. However, testing if four points are on the same side is a key part of a simple line/rectangle intersection test. For that use it seemed simpler to just calculate each separately.

The full Javascript code is:

var game = new Phaser.Game(530, 300, Phaser.AUTO, 'gamecontainer',
                           { create: create, update: update, render: render });

var line;
var setting = false;

var point1;
var point2;

var textSame;
var textDiff;

function create() {

  line = new Phaser.Line(,,
                         3*, 3*;

  point1 = new Phaser.Point(,;
  point2 = new Phaser.Point(, 3*;

  textSame = game.add.text(4, 0, "Same Side", { fill: '#ffffff' });
  textSame.visible = false;

  textDiff = game.add.text(0, 0, "Different Side", { fill: '#ffffff' });
  textDiff.visible = false;

  game.input.onDown.add(click, this);

  setting = true;


function update() {

  if (setting) {
    if (game.input.activePointer.isDown) {
      line.end.set(game.input.activePointer.x, game.input.activePointer.y);
    } else {
      setting = false;

        var sign1 =
            (line.end.x - line.start.x) * (point1.y - line.start.y) -
            (line.end.y - line.start.y) * (point1.x - line.start.x);

        var sign2 =
            (line.end.x - line.start.x) * (point2.y - line.start.y) -
            (line.end.y - line.start.y) * (point2.x - line.start.x);

        console.log("Signs are " + sign1 + "  " + sign2);

        if ((sign1<0 && sign2<0) ||
            (sign1>0 && sign2>0) ||
            (sign1==0 && sign2==0)) {

            textSame.visible = true;
            textDiff.visible = false;

        } else {
            textSame.visible = false;
            textDiff.visible = true;

function click(pointer) {
  setting = true;
  line.start.set(pointer.x, pointer.y);

function render() {
  game.debug.geom(point1, '#ff0000');
  game.debug.geom(point2, '#ff0000');

JavaScript Cookies

People of Earth!  Cookies will not be saved by your browser when operating from a local file:// URL!  Do not waste time writing your own little cookie functions out of the forlorn, astounded believe that everyone else out there, e.g., jQuery, is somehow just crazy and doing something wrong!

function getCookie(get)
  var cookies = document.cookie.split(";");
  var i, name;
  for (i = 0; i < cookies.length; i++) {
    name = cookies[i].substr(0,cookies[i].indexOf("="))
    if (name == get) {
      return unescape(cookies[i].substr(cookies[i].indexOf("=")+1));
  return null;

function setCookie(name, value, days)
  var expDate = new Date();
  expDate.setDate(expDate.getDate() + days);
  var cookie = escape(value) +
               ((days==null) ? "" : "; expires="+expDate.toUTCString());
  document.cookie = name + "=" + cookie;

function deleteCookie(name)
  setCookie(name, null, -1);