Hi,
Ok so, I posted sometime ago about porting my AS2 pathfinder to AS3, and I kind of did just that, along the way I think I made some improvements to it, now I’m looking for more suggestions, so if you’ve got time, please look through the following class
It’s slightly documented, but not completely…
[AS]
package {
import flash.events.Event;
import flash.events.EventDispatcher;
import flash.geom.Point;
public class Pathfinder extends EventDispatcher {
// Direction array, used to check adjacent blocks
private const _dirs:Array = [
{x:0, y:-1},{x:1, y:-1},{x:1, y:0},{x:1, y:1},
{x:0, y:1},{x:-1, y:1},{x:-1, y:0},{x:-1, y:-1}
];
private const cost_diag:int = 14; // Diagonal movement cost
private const cost_orth:int = 10; // Orthagonal movement cost
private var grid:Array; // Holds temporary grid for calculations
private var openList:Array; // Stores references to blocks in the openlist
private var closedList:Array; // Stores references to blocks in the closedlist
private var finalPath:Array; // Contains the finalized path from start to goal
private var start:pathBlock; // Start position
private var goal:pathBlock; // End position
public var available:Boolean = true;
public function Pathfinder():void {
init();
};
public function findPath(s:Point, goal:Point, g:Array):void {
// If the pathfinder is not already running,
// for future implementation of a queue system
if(this.available){
init();
// Set the pathfinder to 'already in use'
this.available = false;
// Set the start position
this.start = new pathBlock(s.x, s.y);
// Set the final position to find a path to
this.goal = new pathBlock(goal.x, goal.y);
// Loop through the Y of the grid
var ilen:int = g.length;
for(var i:uint = 0;i<ilen;i++){
// Make sure the current grid row is a array
grid* = [];
// Loop through the X of the current Y array
var jlen:int = g*.length;
for(var j:uint = 0;j<jlen;j++){
// Set this grid position to a new pathfinding block
grid*[j] = new pathBlock(j, i, 0, 0, null, g*[j].w);
}
}
// Push the start position into the openlist
openList.push(this.start);
// Add a listener for the "nextPath" event
// which occurs once one move has been evaluated
addEventListener("nextPath", nextPathHandler);
// check all adjacent blocks for the highest rated block in the openlist
checkAdjacentBlocks(openList_next());
}
}
/*
** private function: getPath()
** Takes nothing, returns array
** --------
** Desc: returns the calculated path
** between start and goal and sets
** the pathfinder to available
*/
public function getPath():Array {
available = true;
return finalPath;
}
/*
** private function: nextPathHandler()
** Takes Event, returns nothing
** --------
** Desc: Registered eventHandler for the
** "nextPath" event, evaulates the next block
** to be searched and/or calls optimizePath
*/
private function nextPathHandler(evt:Event):void {
var block:pathBlock = openList_next();
if(!block.compare(goal)){
if(openList.length > 0){
checkAdjacentBlocks(block);
}
} else {
optimizePath();
}
}
/*
** private function: init()
** Takes nothing, returns nothing
** --------
** Desc: Initialize and clean variables
** for this pathfinder
*/
private function init():void {
grid = [];
openList = [];
closedList = [];
finalPath = [];
}
/*
** private function: optimizePath()
** Takes nothing, returns nothing
** --------
** Desc: Back-tracks the evaulated path
** and adds it to the final path array (finalPath:Array)
*/
private function optimizePath():void {
var c:pathBlock = goal;
while(c != start){
finalPath.push(new Point(c.x, c.y));
c = grid[c.y][c.x].p;
}
finalPath.reverse();
dispatchEvent(new Event("pathCompleted"));
}
/*
** private function: checkAdjacentBlocks()
** Takes pathBlock, returns nothing
** --------
** Desc: Check all blocks around the passed
** block and evaluate them and add the acceptable
** ones to the openlist
*/
private function checkAdjacentBlocks(block:pathBlock):void {
var dlen:int = _dirs.length;
for(var i:uint = 0;i<dlen;i++){
var x:int = block.x + _dirs*.x;
var y:int = block.y + _dirs*.y;
var g:int = (_dirs*.x == 0 || _dirs*.y == 0)? block.g + cost_orth : block.g + cost_diag;
if(grid[y] != undefined){
if(grid[y][x] != undefined){
if(grid[y][x].w){
if(!closedList_exists(grid[y][x])){
if(!openList_updateCondition(grid[y][x])){
grid[y][x].update(x, y, g, manhatCost(grid[y][x], goal), block);
openList.push(grid[y][x]);
}
}
}
}
}
}
openToClosed(block);
dispatchEvent(new Event("nextPath"));
}
/*
** private function: openToClosed()
** Takes pathBlock, returns nothing
** --------
** Desc: Removes the passed block from
** the openlist and adds it to the closedlist
*/
private function openToClosed(block:pathBlock):void {
var ilen:int = openList.length;
for(var i:uint = 0;i<ilen;i++){
if(block.compare(openList*)){
if(i > 0){
var tmp:pathBlock = openList*;
openList* = openList[0];
openList[0] = tmp;
}
closedList.push(openList.shift());
break;
}
}
}
/*
** private function: closedList_exists()
** Takes pathBlock, returns Boolean
** --------
** Desc: Checks if the passed block
** exists in the closedlist, returns true if found
*/
private function closedList_exists(block:pathBlock):Boolean {
var ilen:int = closedList.length;
for(var i:uint = 0;i<ilen;i++){
if(closedList*.x == block.x && closedList*.y == block.y){
return true;
break;
}
}
return false;
}
/*
** private function: openList_next()
** Takes nothing, returns pathBlock
** --------
** Desc: evaluates which block in the
** openlist which shall be tested next
*/
private function openList_next():pathBlock {
var n:pathBlock = openList[0];
var ilen:int = openList.length;
for(var i:uint = 1;i<ilen;i++){
n = (n.f < openList*.f)? n : openList*;
}
return n;
}
/*
** private function: openList_updateCondition()
** Takes pathBlock, returns Boolean
** --------
** Desc: Looks for the block in the openlist
** and if found, updates the values if the
** passed ones are better
*/
private function openList_updateCondition(block:pathBlock):Boolean {
var ilen:int = openList.length;
for(var i:uint = 0;i<ilen;i++){
if(block.compare(openList*)){
if(openList*.g < block.g){
openList*.p = block.p;
}
return true;
break;
}
}
return false;
}
/*
** private function: manhatCost()
** Takes pathBlock, pathBlock, returns int
** --------
** Desc: Evaluates the cost from start to goal
** and returns the evaluated value
*/
private function manhatCost(start:pathBlock, goal:pathBlock):int {
return cost_orth * ( Math.abs(start.x - goal.x) + Math.abs(start.y - goal.y) );
};
};
};
class pathBlock {
public var x:int;
public var y:int;
public var g:int;
public var h:int;
public var f:int;
public var p:pathBlock;
public var w:Boolean;
public var v:uint;
public function pathBlock(x:int, y:int, g:int = 0, h:int = 0, p:pathBlock = null, w:Boolean = true, v:uint = 0):void {
update(x, y, g, h, p);
this.w = w;
this.v = v;
};
public function update(x:int, y:int, g:int, h:int, p:pathBlock):void {
this.x = x;
this.y = y;
this.g = g;
this.h = h;
this.f = g + h;
this.p = p;
};
public function compare(block:pathBlock):Boolean {
if(block.x == this.x && block.y == this.y) return true;
return false;
}
};
[/AS]
Thank you