Thursday, February 7, 2013

Line Of Sight (LOS) in ActionScript

One of the simplest algorithms in any roguelike is line of sight (LOS). It's basically drawing a line from one point to another and seeing if anything obscures it. Here's an Actionscript implementation of the Bresenham line algorithm (invented in 1962!).

// https://gist.github.com/4704144
package
{
import flash.geom.Point;
public class Line
{
public var points:Array = [];
public function Line(x0:int, y0:int, x1:int, y1:int) {
calculate(x0, y0, x1, y1);
}
protected function calculate(x0:int, y0:int, x1:int, y1:int):void {
var dx:int = Math.abs(x1 - x0);
var dy:int = Math.abs(y1 - y0);
var sx:int = x0 < x1 ? 1 : -1;
var sy:int = y0 < y1 ? 1 : -1;
var err:int = dx - dy;
while (true){
points.push(new Point(x0, y0));
if (x0==x1 && y0==y1)
break;
var e2:int = err * 2;
if (e2 > -dx) {
err -= dy;
x0 += sx;
}
if (e2 < dx){
err += dx;
y0 += sy;
}
}
}
public static function betweenPoints(p0:Point, p1:Point):Line {
return new Line(p0.x, p0.y, p1.x, p1.y);
}
public static function betweenCoordinates(x0:int, y0:int, x1:int, y1:int):Line {
return new Line(x0, y0, x1, y1);
}
}
}
view raw Line.as hosted with ❤ by GitHub

It's not super obvious what's going on. Basically, figure out which direction the line always goes, and how often it goes in the other axis. Then go.

This is the basis for simple field of view (FOV) algorithms and is a quick and easy way of seeing if a tile, item, monster, or event can be seen by the player or another creature. It can also be used to calculate where a projectile will go, corridor generation, or simple pathfinding in open spaces.

I'm sure there are low-level ways to make this perform faster like bit shifting or breaking each octant into it's own function. It could also return an iterator that calculates points as-needed. This would allow really long lines - or even infinitely long lines - while only calculating what's actually needed.

No comments:

Post a Comment