Circle Intersection Test

Yet another quick test for a geometry function:

Click, drag, and release to draw a line. A point will be drawn at the intersections if there are any. Hit ‘S’ to toggle between treating the drawn segment as a line segments or a line.

The demo uses some basic Phaser features for the interaction and drawing. The Javascript code is:

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

var line;

var setting;

var result1;
var result2;

var circle;

var segment = true;

function create() {

  line = new Phaser.Line(game.world.width/4, game.world.height/4,
                         3*game.world.width/4, 3*game.world.height/4);

  circle = new Phaser.Circle(game.world.width/2, game.world.height/2,
                             Math.min(game.world.height, game.world.width)/2);

  game.input.onDown.add(click, this);
  setting = false;

  result1 = new Phaser.Point();
  result2 = new Phaser.Point();

    game.input.keyboard.addKey(Phaser.Keyboard.S)
        .onDown.add(function() {
            segment = !segment;
        }, this);
}


function update() {

    if (setting) {
        line.end.set(game.input.activePointer.x,
                      game.input.activePointer.y);

        if (!game.input.activePointer.isDown) {
            setting = false;
        }
    }
}


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


function render() {
  game.debug.geom(line);

  game.debug.geom(circle, '#00ff00', false, 2);

  var res = intersection(line, circle, result1, result2, segment);
  if (res) {
    result1.x--;
    result1.y--;
    result2.x--;
    result2.y--;

    game.debug.geom(result1, '#ff0000');

    if (res == INTERSECTION)
      game.debug.geom(result2, '#ff0000');
  }

}


var NO_INTERSECTION = 0;
var INTERSECTION = 1;
var SINGLE_INTERSECTION = 2;
var TANGENT = 3;

function intersection(line, circle, result1, result2, segment) {
  var lx = line.end.x - line.start.x;
  var ly = line.end.y - line.start.y;

  var len = Math.sqrt(lx*lx + ly*ly);

  var dx = lx / len;
  var dy = ly / len;

  var t = dx*(circle.x-line.start.x) + dy*(circle.y-line.start.y);

  var ex = t * dx + line.start.x;
  var ey = t * dy + line.start.y;

  var lec = Math.sqrt((ex-circle.x)*(ex-circle.x) +
                      (ey-circle.y)*(ey-circle.y));

  if (lec < circle.radius) {

    var dt = Math.sqrt(circle.radius*circle.radius - lec*lec);

    var te = dx*(line.end.x-line.start.x) + dy*(line.end.y-line.start.y);

    if (segment) {
      if ((t-dt < 0 || t-dt > te) &&
          (t+dt < 0 || t+dt > te)) {
            return NO_INTERSECTION;
      } else if (t-dt < 0 || t-dt > te) {
          result1.x = (t+dt)*dx + line.start.x;
          result1.y = (t+dt)*dy + line.start.y;
          return SINGLE_INTERSECTION;
      } else if (t+dt < 0 || t+dt > te) {
          result1.x = (t-dt)*dx + line.start.x;
          result1.y = (t-dt)*dy + line.start.y;
          return SINGLE_INTERSECTION;
      }
    }

    result1.x = (t-dt)*dx + line.start.x;
    result1.y = (t-dt)*dy + line.start.y;

    result2.x = (t+dt)*dx + line.start.x;
    result2.y = (t+dt)*dy + line.start.y;

    return INTERSECTION;
  } else if (lec == circle.radius) {

    result1.x = ex;
    result1.y = ey;

    result2.x = ex;
    result2.y = ey;

    return TANGENT;
  }

  return NO_INTERSECTION;
}

Line Intersection Test

Working on another game feature, I now need to compute actual line and rectangle intersections rather than just detecting them. This is a quick test:

Click, drag, and release to draw a line. A point will be drawn at the intersection if there is one. Hit ‘S’ to toggle between treating the geometry as line segments or lines.

The demo uses some basic Phaser features for the interaction and drawing. The calculation is taken straight from Phaser’s Arcade Physics math. The full Javascript code is:

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

var linea;
var lineb;

var setting;

var result;

var segment;

function create() {

    linea = new Phaser.Line(game.world.width/4, game.world.height/4,
                            3*game.world.width/4, 3*game.world.height/4);
    lineb = new Phaser.Line(game.world.width/4, 3*game.world.height/4,
                            3*game.world.width/4, game.world.height/4);

    game.input.onDown.add(click, this);
    setting = false;

    result = new Phaser.Point();

    segment = true;

    game.input.keyboard.addKey(Phaser.Keyboard.S)
        .onDown.add(function() {
            segment = !segment;
        }, this);
}


function update() {

    if (setting) {
        lineb.end.set(game.input.activePointer.x,
                      game.input.activePointer.y);

        if (!game.input.activePointer.isDown) {
            setting = false;
        }
    }
}


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


function render() {
    game.debug.geom(linea);
    game.debug.geom(lineb);

    if (intersection(linea.start.x, linea.start.y,
                     linea.end.x, linea.end.y,
                     lineb.start.x, lineb.start.y,
                     lineb.end.x, lineb.end.y,
                     segment,
                     result)) {
        result.x--;
        result.y--;
        game.debug.geom(result, '#ff0000');
    }
}

function intersection(ax, ay, bx, by, ex, ey, fx, fy, asSegment, result) {

    var a1 = by - ay;
    var a2 = fy - ey;
    var b1 = ax - bx;
    var b2 = ex - fx;
    var c1 = (bx * ay) - (ax * by);
    var c2 = (fx * ey) - (ex * fy);
    var denom = (a1 * b2) - (a2 * b1);

    if (denom === 0) {
        return false;
    }

    result.x = ((b1 * c2) - (b2 * c1)) / denom;
    result.y = ((a2 * c1) - (a1 * c2)) / denom;

    if (asSegment) {
        if ( result.x < Math.min(ax, bx) || result.x > Math.max(ax, bx) ||
             result.y < Math.min(ay, by) || result.y > Math.max(ay, by) ||
             result.x < Math.min(ex, fx) || result.x > Math.max(ex, fx) ||
             result.y < Math.min(ey, fy) || result.y > Math.max(ey, fy) ) {
            return false;
        }
    }

    return true;

}

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!