Path finder
From FlashPHPWiki
We want to make a function which find for us the shortest way to go to a certain position in a grid. This is a common problem programming games (such as WarCraft for example..). we have a grid with some obstacles and we need to find a way to from the starting point "a" to the final position "b"
In this tut I will use the A* algorithm to make our function. It is not really complicated to understand, but an introduction is needed: First, what is the A* (called "a star") path finder?
I suggest you to take a look at these links about A*:
* http://www.policyalmanac.org/games/aStarTutorial.htm * http://theory.stanford.edu/%7Eamitp/GameProgramming/AStarComparison.html
Now that you're introduced to the argument, let's begin.
Table of contents |
1. Build the Grid dynamically
I wanted to make the grid we will use completely dynamic, this is i will create every box by loading an external xml file. Think to a grid of 10x10. This means my xml file will have 10 nodes with every node containing a string of 10 bytes (0 or 1). Here an example of how i made the xml file:
<?xml version="1.0"?>
<GRID>
<GRID>
<ROW>0010000100</ROW>
<ROW>0000001100</ROW>
<ROW>0001010100</ROW>
<ROW>0000010000</ROW>
<ROW>0101010000</ROW>
<ROW>0001000111</ROW>
<ROW>0101010100</ROW>
<ROW>0111000110</ROW>
<ROW>0000000000</ROW>
<ROW>0000000000</ROW>
</GRID>
<INIT>8,5</INIT>
</GRID>
Ok, we are.. the GRID node contains the informations to build the grid, then the INIT node tells flash where to place the starting point. This is not really difficult, but just as introduction to what we're looking for. I will not explain to you how to make the grid using this xml file (it will make too long thi tut, i want to focus the attention to the path finder...) Just say one important thing. the grid coordinates are representated in flash using a bi-dimensional array. the first dimension will represent the "rows", while the second dimension will be the "columns" so:
_array[0][0]
will be the (0,0) coordinates into the grid (the upper left corner)
2. Where to go?
Now we are in this situation. The arrow represent our starting point (0,0) in the grid, while the second grey box the final position.
The best and easiset way to find the "shortest" path from the point 0 to the point 1 in the grid is to use the A* ( a star ) algorithm. 3. The A star algorithm
The A* can be summarized as:
setup the openlist (an array)
setup the closedlist (an array)
push the starting node to the open list (node is a square in our grid)
while the openlist is not empty
Look for the lowest 'f' cost node on the open list and pop from the openlist and name it 'current'
if the current node is the goal then we found the solution, exit the while loop
for each of the node adjacent to the current node (8 is we allow diagonal movement)
set the parent of this adjacent to 'current'
if a node with the same position as the adjacent node is in the open list /
and its 'f' is lower than the node adjacent
then skip current adjacent node
if a node with the same position is in closedlist /
and its 'f' is lower
then skip current adjacent node
otherwise push the current node to the open list
remove occurences of adjacent node from OPEN and CLOSED list
Add adjacent node to the OPEN list
end for
add the current node to the closed list
end while
and here a demo swf of this algorithm working: http://www.sephiroth.it/phpwiki/uploads/path.finder.swf Ok, easy.. but what is f ?
f is a value which we assign to every adjacent node while analyzing every node. basically f is the result of this equation:
f = g + h
g is the the movement cost to move from the starting point a to a given node on the grid (number of movements to that node) h is an heuristic value. heuristic because it can't be a true value. the estimated movement cost to move from that given square on the grid to the final destination, point B.
4. Create the Class in Flash
Now we would like to implement that algorithm in Flash. A consideration about f = g + h Let see this image:
As you can see the adjacent nodes to our current node (in this case the starting node), which value is not '1', are represented with different numbers The 'top' number is "f", left one is "g" (which for the first time is always 1), and the right one is the "h" heuristic value. In these ways we only take the most promising nodes, using the A* algorithm, and we will make operations on those nodes.. The struc node.
To take informations about the visited (by the algorithm) nodes i don't need only their position in the grid, but I also need to know their f,g,h and their corresponding parent node. For this reason I will make a new object which represent a node:
function structNode (pos, f, g, h, parent) {
this.pos = pos.slice ();
this.f = f;
this.g = g;
this.h = h;
this.parent = parent;
// convert its coordinates to string
// to improve performance in comparing
this.pos_str = this.pos.toString ();
}
// ** get the struct node in string format object ** //
structNode.prototype.toString = function(){
return "[" + this.pos_str + "], f=" + this.f + ", g=" + this.g + ", h=" + this.h;
}
Ok, now the real path finder class in Flash:
// **************************
// PathFinder Class
// Alessandro Crugnola
// based on A* PathFinder
// **************************
function PathFinder (ar) {
this.__init__ (ar);
}
// ** init variables and list ** //
PathFinder.prototype.__init__ = function (ar) {
this._array = ar;
this.finalPosition = new Array()
this.startPosition = new Array()
this.openList = new Array()
this.closedList = new Array()
};
// ** Find the successors ** //
PathFinder.prototype.getSuccessors = function (pos) {
var r = Number (pos[0]);
var c = Number (pos[1]);
// put all the successors in this array...
var ret = new Array ();
if (this._array[r - 1][c] == 0) {
ret.push ([r - 1, c]);
}
if (this._array[r][c + 1] == 0) {
ret.push ([r, c + 1]);
}
if (this._array[r + 1][c] == 0) {
ret.push ([r + 1, c]);
}
if (this._array[r][c - 1] == 0) {
ret.push ([r, c - 1]);
}
// ** disabling the diagonal movement ** //
/*
if (this._array[r + 1][c + 1] == 0 && this._array[r][c + 1] == 0 && this._array[r + 1][c] == 0) {
ret.push([r + 1, c + 1]);
}
if (this._array[r + 1][c - 1] == 0 && this._array[r][c - 1] == 0 && this._array[r + 1][c] == 0) {
ret.push([r + 1, c - 1]);
}
if (this._array[r - 1][c - 1] == 0 && this._array[r][c - 1] == 0 && this._array[r - 1][c] == 0) {
ret.push([r - 1, c - 1]);
}
if (this._array[r - 1][c + 1] == 0 && this._array[r][c + 1] == 0 && this._array[r - 1][c] == 0) {
ret.push([r - 1, c + 1]);
}
*/
return ret;
};
// ** Initialize the search ** //
PathFinder.prototype.init = function () {
trace ("PathFinder.init()");
var startingNode = new structNode (this.startPosition, 0, 0, 0);
this.openList.push (startingNode);
};
// ** get the distance between 2 positions ** //
PathFinder.prototype.getDistance = function (pos1, pos2) {
var d1 = Math.abs (pos2[0] - pos1[0]);
var d2 = Math.abs (pos2[1] - pos1[1]);
return d1 + d2;
};
// ** Find best path from start to end ** //
PathFinder.prototype.findPath = function () {
while (this.openList.length > 0) {
var _max = 5000;
var _selected = -1;
for (var a = 0; a < this.openList.length; a++) {
if (this.openList[a].f < _max) {
_max = this.openList[a].f;
_selected = a;
}
}
var node = this.openList.splice (_selected, 1);
node = node[0];
if (node.pos_str == this.finalPosition.toString ()) {
this.closedList.push(node)
var cur = this.closedList[this.closedList.length - 1]
var ret = new Array();
while(cur.parent != undefined){
ret.push(cur)
cur = cur.parent
}
return ret
}
var successors = this.getSuccessors (node.pos);
for (var a = 0; a < successors.length; a++) {
var _skip = false;
var struct = new structNode (successors[a]);
struct.parent = node;
struct.g = node.g + this.getDistance (struct.pos, node.pos);
struct.h = this.getDistance (struct.pos, this.finalPosition);
struct.f = struct.g + struct.h;
for (var b in this.openList) {
if (this.openList[b].pos_str == struct.pos_str && this.openList[b].f < struct.f) {
_skip = true;
break;
}
}
for (var b in this.closedList) {
if (this.closedList[b].pos_str == struct.pos_str && this.closedList[b].f < struct.f) {
_skip = true;
break;
}
}
if (_skip == false) {
for (var c in this.openList) {
if (this.openList[c].pos_str == struct.pos_str) {
this.openList.splice (c, 1);
}
}
for (var c in this.closedList) {
if (this.closedList[c].pos_str == struct.pos_str) {
this.closedList.splice (c, 1);
}
}
this.openList.push (struct);
}
}
this.closedList.push (node);
}
trace('IMPOSSIBLE TO FIND A PATH')
return new Array();
};
It's finish. We have translated the A* algorithm in Flash in few lines... If the patrh finder class find a valid path it will return an array of structNodes, otherwise it will return an empty array.
5. End...
For more informations about A* refer to the links at the beginning of this document. I also insert the fla file for this tutorial in my download section.
--Sephiroth 3 December 2005 17:31 (PST)
