SIDE-ALICE Ver.5

Pathfinder was developed by Grant Skinner. Visit http://gskinner.com/ for more source, updates, FlashOS and other good stuff. All code, graphics and intellectual property is coypright 2002, Grant Skinner.

*Contents:
Contents
Description
Legal Information
* License
* Distribution
* Disclaimer
Usage
* Instantiation
* Properties
* Methods
* Path objects
Version info

*Description:
The Pathfinder class was developed to be a flexible, happy medium for pathfinding in Flash. To that end, it is much more accurate than simple “move towards” algorithms, and vastly faster than A* (~1ms per step on highest level on 500mhz system). Also, it’s speed scales in a linear fashion with the length of the path, rather than exponentially as with A*, and speed is unaffected by map size.

It uses a ranked movement algorithm (move towards, move laterally, move away), paired with backtrack avoidance and looping detection. It also utilizes up to 4 different pathfinding approaches (forwards or reverse, favouring horizontal or vertical movement).

It offers a fair amount of flexibility, with the ability to set the maximum path length, and to scale the number of different approaches the system will attempt. You can also change any parameter at any time, and re-run the pathfinding routine (which allows for characters changing direction at any time), etc.

If you have any feedback, questions, or ideas, you can contact me through my site at http://gskinner.com/ .

*Legal Information:

License:
The Pathfinder class is free for use in non-commercial projects, all that I ask is that you fire me an email and let me know what you’re using for, and what you think of it (hearing back from you makes developing and releasing code for free worthwhile). I would also really appreciate credit and/or a link back to my site at http://gskinner.com/ , if possible.

If you would like to use it in commercial contracts, please contact me for license information. Often, it will be as simple and inexpensive as giving due credit.

You may NOT sell the Pathfinding path as it is,  in a modified format, or as part of a derivative work without prior written consent.

The Pathfinding class is copyright 2002, Grant Skinner, all rights reserved.

Distribution:
You may upload this FLA to any online service, bulletin board, network, or the Internet, as long as the FLA is not modified and the Read Me file is included. You may NOT make copies of this FLA, or it’s included source code for any commercial purpose. You must get permission to include this program on CD-ROM, floppy disk or other removable storage.

Disclaimer:
THIS SOFTWARE IS PROVIDED ON AN “AS IS” BASIS. GRANT SKINNER MAKES NO WARRANTIES WHATSOEVER, EITHER EXPRESS OR IMPLIED, REGARDING THIS PRODUCT, INCLUDING WARRANTIES WITH RESPECT TO ITS MERCHANTIBILITY OR ITS FITNESS FOR ANY PARTICULAR PURPOSE. IN NO EVENT SHALL GRANT SKINNER BE LIABLE FOR ANY SPECIAL, CONSEQUENTIAL, INDIRECT OR SIMILAR DAMAGES, INCLUDING ANY LOST DATA ARISING OUT OF THE USE OR INABILITY TO USE THE SOFTWARE OR ANY DATA SUPPLIED THEREWITH. USE THIS SOFTWARE AT YOUR OWN RISK.

*Usage:

Instantiation:
myPathfinder = new Pathfinder(map,startPoint,endPoint,depth,level);

Properties:
myPathfinder.map
A two dimensional array containing boolean values, indicating whether a particular point in the map can be moved through.

myPathfinder.startPoint
an object with an x and y property corresponding to the coordinates in map from which to start the path.

myPathfinder.endPoint
a point object indicating the goal coordinates on the map.

myPathfinder.depth
a positive integer indicating the maximum path length. The Pathfinder will give up if it exceeds this length. This number does not include the start point. A larger number will increase the chance of finding a path over a longer distance, but will also increase the time requires to find the path.

myPathfinder.level
an integer between 0 and 3 inclusive that indicates the number of different approaches the Pathfinder should attempt to find a path (the different approaches are forwards or reverse, favouring horizontal or vertical movement). A larger number will increase the chance of finding a path, and will usually result in shorter path lengths (as it will choose the shortest path), but it will increase the amount of time required to find a path.

myPathfinder.path
bestPath returns the path object that was found, or null if findPath has not been executed. See notes on path objects below.

Methods:
myPath = myPathfinder.findPath();
Runs the pathfinding routine, and returns a path object.

Path objects:
Paths are returned as path objects. The path object has three properties: weight, xPath and yPath.

Weight indicates the length of the found path. A weight of 10000 indicates that the path does not reach it’s end point.

xPath and yPath store the x and y coordinates of the path respectively, starting on the start coordinates, and ending on the end coordinates (if successful). So to access the coordinates of the fifth step in myPath, you could use:
xCoord = myPath.xPath[5];
yCoord = myPath.yPath[5];

*Version info:
1.0.1
Fixed a small bug where level 3 & 4 paths would be returned in reverse.
Modified the path drawing routine slightly to show the direction of the path (lighter – at the start, darker at the end)

1.0
This is first release of Pathfinder, and everything appears to be working smoothly. Exciting version info, eh?

Future enhancements:
I’d like to tinker with further optimization, and add a bestFail capability, that will rank the failed paths and choose the best one based on length and proximity to the end point (right now it returns the first approach).

If you find any bugs, have questions, or have ideas for additional features, please contact me through my site athttp://gskinner.com/ .

/**** PathFinder Class
Flash pathfinding engine developed by Grant Skinner. Visit:
http://gskinner.com/
for more source,  updates, FlashOS, and other cool stuff.

All code, graphics and algorithms copyright 2002, Grant Skinner. See the Read Me for usage, distribution and license info.
****************/
PathFinder = function(fMap,fStart,fEnd,fDepth,fLevel) {
this.init(fMap,fStart,fEnd,fDepth,fLevel);
}
PathFinder.prototype.init = function(fMap,fStart,fEnd,fDepth,fLevel) {
this.map = fMap; // the map array (2d)
this.start = fStart; // the starting point object
this.end = fEnd; // the ending point object
this.depth = fDepth;  // the maximum length of the path
this.level = fLevel; // the number of different attempts it will make
}

PathFinder.prototype.findPath = function() {
this.$paths = [];
// get paths based on level:
this.$paths[0] = this.$findPath(this.start,this.end,1,false);
if (this.level > 0) { this.$paths[1] = this.$findPath(this.start,this.end,0,false); }
if (this.level > 1) { this.$paths[2] = this.$findPath(this.end,this.start,1,true); }
if (this.level > 2) { this.$paths[3] = this.$findPath(this.end,this.start,0,true); }

// sort on weight:
this.$paths.sort(this.$pathSort);

// set path and return it;
this.path = this.$paths[0];
return this.path;
}
PathFinder.prototype.$pathSort = function(fVal1,fVal2) {
if (fVal1.weight < fVal2.weight) { return -1; }
else if (fVal1.weight > fVal2.weight) { return 1; }
return 0;
}

/*** PathFinder.$findPath
searches for a path from start point to end point.
dir is a boolean, and specifies the search direction (true = favour x, false = favour y)
rev indicates whether the path should be reversed after it is found.
***/
PathFinder.prototype.$findPath = function(fStart,fEnd,fDir,fRev) {
// set up:
var curx = fStart.x;
var cury = fStart.y;
var pathWeight = 0;
var pathx = [];
var pathy = [];
var endx = fEnd.x;
var endy = fEnd.y;

// try to find a path:
while(true) {
if ((curx == pathx[pathWeight-4])&&(cury == pathy[pathWeight-4])) { pathWeight=10000; break; }
oldx = pathx[pathWeight-1];
oldy = pathy[pathWeight-1];
pathx.push(curx);
pathy.push(cury);
pathWeight++;
if (endx == curx && endy == cury) { break; }
if (pathWeight > this.depth) { pathWeight = 10000; break; }

if (fDir) { // favour x movements
// move towards end:
if ((curx < endx)&&(oldx != curx+1)&&(this.map[curx+1][cury])) { curx++; continue; }
if ((curx > endx)&&(oldx != curx-1)&&(this.map[curx-1][cury])) { curx–; continue; }
if ((cury < endy)&&(oldy != cury+1)&&(this.map[curx][cury+1])) { cury++; continue; }
if ((cury > endy)&&(oldy != cury-1)&&(this.map[curx][cury-1])) { cury–; continue; }
// can’t move towards try lateral:
if (curx == endx) {
if ((oldx != curx+1)&&(this.map[curx+1][cury])) { curx++; continue; }
if ((oldx != curx-1)&&(this.map[curx-1][cury])) { curx–; continue; }
} else if (cury == endy) {
if ((oldy != cury+1)&&(this.map[curx][cury+1])) { cury++; continue; }
if ((oldy != cury-1)&&(this.map[curx][cury-1])) { cury–; continue; }
}
// can’t move lateral, try away:
if ((curx > endx)&&(oldx != curx+1)&&(this.map[curx+1][cury])) { curx++; continue; }
else if ((oldx != curx-1)&&(this.map[curx-1][cury])) { curx–; continue; }
if ((cury > endy)&&(oldy != cury+1)&&(this.map[curx][cury+1])) { cury++; continue; }
else if ((oldy != cury-1)&&(this.map[curx][cury-1])) { cury–; continue; }
} else { // favour y movements
// move towards end:
if ((cury < endy)&&(oldy != cury+1)&&(this.map[curx][cury+1])) { cury++; continue; }
if ((cury > endy)&&(oldy != cury-1)&&(this.map[curx][cury-1])) { cury–; continue; }
if ((curx < endx)&&(oldx != curx+1)&&(this.map[curx+1][cury])) { curx++; continue; }
if ((curx > endx)&&(oldx != curx-1)&&(this.map[curx-1][cury])) { curx–; continue; }
// can’t move towards try lateral:
if (cury == endy) {
if ((oldy != cury-1)&&(this.map[curx][cury-1])) { cury–; continue; }
if ((oldy != cury+1)&&(this.map[curx][cury+1])) { cury++; continue; }
} else if (curx == endx) {
if ((oldx != curx-1)&&(this.map[curx-1][cury])) { curx–; continue; }
if ((oldx != curx+1)&&(this.map[curx+1][cury])) { curx++; continue; }
}
// can’t move laterally, try away:
if ((cury < endy)&&(oldy != cury-1)&&(this.map[curx][cury-1])) { cury–; continue; }
else if ((oldy != cury+1)&&(this.map[curx][cury+1])) { cury++; continue; }
if ((curx < endx)&&(oldx != curx-1)&&(this.map[curx-1][cury])) { curx–; continue; }
else if ((oldx != curx+1)&&(this.map[curx+1][cury])) { curx++; continue; }
} // end if

// darn, we’re stuck.
pathWeight = 10000;
break;
} // end while
// flip the path if it is reversed, and if we were successful
if (fRev && pathWeight < 10000) {
pathx.reverse();
pathy.reverse();
}
return {xPath:pathx,yPath:pathy,weight:pathWeight,$dir:fDir};
}

// create the map randomly:
myMap = [];
for (var x=0;x<25;x++) {
myMap[x] = [];
for (var y=0;y<25;y++) {
if (x>2 || y>1) { myMap[x][y] = (random(20) > 2); } else { myMap[x][y] = true; }
}
}

// clear the end:
myMap[10][10] = true;
myMap[10][9] = true;

// draw the map;
var xl = myMap.length;
var yl = myMap[0].length;
for (var x=0;x
for (var y=0;y
t = this.attachMovie(“tile”,”t_”+x+”_”+y,x*25+y);
t.gotoAndStop(1+1*myMap[x][y]);
t.x = x;
t.y = y;
t._x = x*t._width;
t._y = y*t._height;
}
}

// a bunch of hacked together code to handle the demo. Not too pretty.
start = {x:0,y:0}
myPath = new PathFinder(myMap,start,end,50,2);

rollOverTile = function(fX,fY) {
findPath(start,{x:fX,y:fY});
}

findPath = function(fStart,fEnd) {
var t = getTimer();

start = myPath.start = fStart;
end = myPath.end =  fEnd;
thePath = myPath.findPath();

ttltime = getTimer()-t;
drawPath(thePath);
setValues();

}

releaseTile = function(fX,fY) {
start = {x:fX,y:fY}
drawMC.clear();
}

drawPath = function(fPath) {
var lineColor = 0xFF0000;
var pl = thePath.xPath.length;
drawMC.clear();
if (fPath.weight < 10000) { lineColor = 0x0044FF; }
var tile = this["t_"+fPath.xPath[0]+”_”+fPath.yPath[0]];
drawMC.moveTo(tile._x+8.5,tile._y+8.5);
for (var i=1;i
drawMC.lineStyle(15,lineColor,16+25*(i/pl));
tile = this["t_"+fPath.xPath[i]+”_”+fPath.yPath[i]];
drawMC.lineTo(tile._x+8.5,tile._y+8.5);
}
}

setValues = function() {
var cr = chr(10);
values.text = myPath.depth+cr+myPath.level+cr+myPath.start.x+”,
“+myPath.start.y+cr+myPath.end.x+”,
“+myPath.end.y+cr+thePath.weight+cr+ttlTime+”ms”;
}

drawMC = this.createEmptyMovieClip(“drawMC”,15000);
findPath(start,{x:10,y:10});
stop();