Here's my wall method.
Every wall in the map is a line segment, load up some walls and do some crazy math and boom. You've got a collision detection thats quite fast.
The walls arent sorted so if theres alot of walls the collision checks might get sluggish.
One way to speed up the collisions would be to skip far away walls alltogether.
Best part of this method is that the pathfinder's speed doesn't change with the distance of the start and end positions, unlike with A* and other tile based pathfinders
ps.
Sucks to not have a good save function in flash.
Trace + copy and paste ftw!
Here's a picture of the pathfinder
Green line is a test path
Blue line is an optimized path
Line.aspackage
{
import flash.geom.Point;
/**
* ...
* @author zamp
*/
public class Line
{
public var start:Point, end:Point;
public function Line(start:Point, end:Point)
{
this.start = start;
this.end = end;
}
public function hitTestPoint(point:Point, radius:Number):Boolean
{
var dist:Number = getClosestPointDistance(point);
if (dist < radius)
return true;
return false;
}
public function getClosestPointDistance(point:Point):Number
{
var closestPoint:Point = getClosestPoint(point);
return zGeom.length(closestPoint,point);
}
// returns the closest point at line segment (not infinite) from point
public function getClosestPoint(point:Point):Point
{
var A:Number = point.x - start.x;
var B:Number = point.y - start.y;
var C:Number = end.x - start.x;
var D:Number = end.y - start.y;
var dot:Number = A * C + B * D;
var len_sq:Number = C * C + D * D;
var param:Number = dot / len_sq;
var xx:Number,yy:Number;
if(param < 0)
{
xx = start.x;
yy = start.y;
}
else if(param > 1)
{
xx = end.x;
yy = end.y;
}
else
{
xx = start.x + param * C;
yy = start.y + param * D;
}
return new Point(xx, yy);
}
// intersects with line and returns a point if any intersection is found, null if not
public function getLineIntersectPoint(line:Line):Point
{
var nx:Number, ny:Number, dn:Number;
var x4_x3:Number = line.end.x - line.start.x;
var y4_y3:Number = line.end.y - line.start.y;
var x2_x1:Number = end.x - start.x;
var y2_y1:Number = end.y - start.y;
var x1_x3:Number = start.x - line.start.x;
var y1_y3:Number = start.y - line.start.y;
nx = x4_x3 * y1_y3 - y4_y3 * x1_x3;
ny = x2_x1 * y1_y3 - y2_y1 * x1_x3;
dn = y4_y3 * x2_x1 - x4_x3 * y2_y1;
nx /= dn;
ny /= dn;
// has intersection
if(nx>= 0 && nx <= 1 && ny>= 0 && ny <= 1){
ny = start.y + nx * y2_y1;
nx = start.x + nx * x2_x1;
return new Point(nx, ny);
}else{
// no intersection
return null;
}
}
}
}
package
{
import flash.display.LineScaleMode;
import flash.display.Shape;
import flash.display.Sprite;
import flash.events.Event;
import flash.geom.Point;
import flash.xml.XMLDocument;
import flash.xml.XMLNode;
import flash.net.URLLoader;
import flash.net.URLRequest;
/**
* ...
* @author zamp
*/
public class Walls extends Sprite
{
public var walls:Array = new Array();
private var fileName:String;
public function Walls()
{
}
public function addWall(start:Point, end:Point):void
{
var line:Shape = new Shape();
line.graphics.lineStyle(1, 0xFF0000);
line.graphics.moveTo(start.x, start.y);
line.graphics.lineTo(end.x, end.y);
addChild(line);
walls.push(new Line(start, end));
}
public function undoLastWall():void
{
removeChild(getChildAt(numChildren-1));
walls.pop();
}
public function getClosestIntersectPointAndLine(line:Line):Array
{
var shortestLength:Number = Number.MAX_VALUE;
var shortestLine:Line = null;
var shortestPoint:Point = null;
for (var i:String in walls)
{
var point:Point = walls[i].getLineIntersectPoint(line);
if (point != null) // intersects
{
// distance from line start location
var length:Number = zGeom.length(new Point(line.start.x, line.start.y), point);
if (length < shortestLength)
{
shortestLine = walls[i];
shortestPoint = point;
shortestLength = length;
}
}
}
if (shortestPoint != null)
return new Array(shortestPoint, shortestLine);
else
return null;
}
public function load(file:String):void
{
fileName = file;
var req:URLRequest = new URLRequest(Config.mapDir + file + ".mwx");
var loader:URLLoader = new URLLoader(req);
loader.addEventListener(Event.COMPLETE, loadComplete);
}
private function loadComplete(e:Event):void
{
var xml:XML = new XML(e.target.data);
xml.ignoreWhite = true;
for (var i:int = 0; i < xml.*.length(); i++)
{
if (xml.wall[i])
{
//trace("Loading layer:", xml.wall[i].@name);
var start:Point = new Point(xml.wall[i].@startx, xml.wall[i].@starty);
var end:Point = new Point(xml.wall[i].@endx, xml.wall[i].@endy);
addWall(start, end);
}
}
trace("Wall load complete");
}
public function save():void
{
var output:String = "<walls>\n";
for (var i:int = 0; i < walls.length; i++)
{
output += "\t<wall startx=\"" + walls[i].start.x + "\" starty=\"" + walls[i].start.y + "\"";
output += " endx=\"" + walls[i].end.x + "\" endy=\"" + walls[i].end.y + "\" />\n";
}
output += "</walls>";
trace(output);
}
}
}
package
{
import flash.geom.Point;
/**
* ...
* @author zamp
* This class needs a better name ASAP :P
* A basic calculator for geometry (add functions when needed)
*/
public class zGeom
{
public function zGeom()
{
}
public static function length(p:Point, p2:Point):Number
{
return Math.sqrt(((p.x - p2.x) * (p.x - p2.x)) + ((p.y - p2.y) * (p.y - p2.y)));
}
}
}
package
{
import flash.display.Shape;
import flash.display.Sprite;
import flash.geom.Point;
import flash.utils.getTimer;
/**
* ...
* @author zamp
*/
public class Pathfinder extends Sprite
{
public function Pathfinder()
{
}
private function drawPath(color:uint, start:Point, end:Point):void
{
/*var d:Shape = new Shape();
d.graphics.lineStyle(1, color);
d.graphics.moveTo(start.x, start.y);
d.graphics.lineTo(end.x, end.y);
addChild(d);
*/
}
public function findPath(start:Point, target:Point):Array
{
//trace("finding path");
var startTick:uint = getTimer();
var testline:Line = new Line(start, target);
var path:Array = new Array(); // add start location to the path
path.push(new Point(start.x, start.y));
var size:Number = 5;
var findingPath:Boolean = true;
var giveUp:uint = 0;
while (findingPath == true && giveUp < 10)
{
giveUp++;
// hit test with walls
var ht:Array = Main.getInstance().walls.getClosestIntersectPointAndLine(testline);
if (ht != null)
{
// hits
// get point X distance from wall
var hp:Point = ht[0]; // hit point in space
// make a vector from start to hitpoint
var vp:Point = new Point(testline.start.x - hp.x, testline.start.y - hp.y);
// normalise vp to X size
vp.normalize(size);
// subtract vp from hitpoint and add this point to path
hp = hp.add(vp);
addPathPoint(path, hp);
// go around the wall
// choose end point that is closer to target
var rwSp:Point = new Point(ht[1].start.x + vp.x, ht[1].start.y + vp.y); // relative wall start point
var rwEp:Point = new Point(ht[1].end.x + vp.x, ht[1].end.y + vp.y); // relative wall end point
var wStartLength:Number = zGeom.length(rwSp, target);
var wEndLength:Number = zGeom.length(rwEp, target);
wStartLength += zGeom.length(rwSp, hp);
wEndLength += zGeom.length(rwEp, hp);
var wcp:Point; // wall collide point
if (wStartLength < wEndLength)
{
wcp = ht[1].start;
// will the new line collide, if does go to the other end of the wall
if (Main.getInstance().walls.getClosestIntersectPointAndLine(new Line(hp, rwSp)) != null)
{
drawPath(0xAA0000, hp, rwSp);
wcp = ht[1].end;
}
} else {
wcp = ht[1].end;
// will the new line collide, if does go to the other end of the wall
if (Main.getInstance().walls.getClosestIntersectPointAndLine(new Line(hp, rwEp)) != null)
{
drawPath(0xAA0000, hp, rwEp);
wcp = ht[1].start;
}
}
// make new path point to wall end point - vp
var newEp:Point = new Point(wcp.x + vp.x, wcp.y + vp.y);
//var newTestline:Line = new Line(hp, newEp);
// add new end point to path
// if the new line collides, return null (there is no path)
if (Main.getInstance().walls.getClosestIntersectPointAndLine(new Line(hp, newEp)) != null)
{
//trace ("no path");
drawPath(0xAA0000, hp, wcp);
return null;
}
addPathPoint(path, newEp);
// make new path point to wall end + X size (go beyond the wall)
vp = new Point(wcp.x - hp.x, wcp.y - hp.y);
// normalize point to X size
vp.normalize(size);
// make new point to wall end + vp
var wEp:Point = new Point(wcp.x + vp.x, wcp.y + vp.y);
// test new line, if it collides return the path currently made
if (Main.getInstance().walls.getClosestIntersectPointAndLine(new Line(newEp, wEp)) != null)
{
// it collides, return path
optimizePath(path);
return path;
} else {
// add point to path list
addPathPoint(path, wEp);
// assign testline start point to wall end point
testline.start.x = wEp.x;
testline.start.y = wEp.y;
}
// repeat
} else {
// wont hit
// add last path point to list
addPathPoint(path, target);
//trace("time taken: ", getTimer() - startTick, "ms");
findingPath = false;
optimizePath(path);
return path;
}
}
// cant find path, thus return null
return null;
}
private function addPathPoint(path:Array, p:Point):void
{
// draw path from last path point to new point
var sp:Point = path[path.length - 1];
drawPath(0x00FF00, sp, p);
// push new path point to list
path.push(new Point(p.x, p.y));
}
private function optimizePath(path:Array):void
{
// TODO: change this to run until fully optimized
for (var i:int = 0; i < path.length; i++)
{
if (i < path.length - 2)
{
var atob:Number = zGeom.length(path[i], path[i + 1]);
var atoc:Number = zGeom.length(path[i], path[i + 2]);
var btoc:Number = zGeom.length(path[i + 1], path[i + 2]);
if (atoc < (atob + btoc)) // a to c is shorter
{
if (Main.getInstance().walls.getClosestIntersectPointAndLine(new Line(path[i], path[i + 2])) == null)
{
// wont collide
// can delete i+1 path point
path.splice(i + 1, 1);
i -= 1;
}
}
}
}
for (i = 0; i < path.length-1; i++)
drawPath(0x0000FF,path[i], path[i + 1]);
}
}
}
Developer
