here you go, here is a implantation of the A* in Action script 3, i wrote this a few years ago, there are a few things such as grid, grid view and node classes that i'm using which really don't have anything to do with the A* algorithm itself, and are all used for the graphic and visual side of the work, still if you are interested i can put them here so you can use them,
please read the codes very carefully, this class, finds the nearest and shortest path inside a grid! exactly what you need, so spend sometime reading it and if you still have problem understanding it, ask and i will help you.
package
{
public class AStar
{
private var _open: Array;
private var _closed: Array;
private var _startNode: Node;
private var _endNode: Node;
private var _grid: Grid;
private var _path: Array;
//private var _heuristic: Function = manhattan;
//private var _heuristic: Function = euclidian;
private var _heuristic: Function = diagonal;
private var _straightCost: Number = 1.0;
private var _diagCost: Number = Math.SQRT2;
public function AStar()
{
}
public function findPath(grid: Grid):Boolean
{
_grid = grid;
_open = new Array();
_closed = new Array();
_startNode = _grid.startNode;
_endNode = _grid.endNode;
_startNode.g = 0;
_startNode.h = _heuristic(_startNode);
_startNode.f = _startNode.g + _startNode.h;
return search();
}
public function search():Boolean
{
var node: Node = _startNode;
while (node != _endNode)
{
var startX: int = Math.max(0, node.x - 1);
var endX: int = Math.min(_grid.numCols - 1, node.x + 1);
var startY: int = Math.max(0, node.y - 1);
var endY: int = Math.min(_grid.numRows - 1, node.y + 1);
for (var i: int = startX; i <= endX; i++)
{
for (var j: int = startY; j <= endY; j++)
{
var test: Node = _grid.getNode(i, j);
if (test == node || !test.walkable || !_grid.getNode(node.x, test.y).walkable || !_grid.getNode(test.x, node.y).walkable) continue;
var cost: Number = _straightCost;
if (!(test.x == node.x) || (test.y == node.y))
{
cost = _diagCost
}
var g: Number = node.g + cost;
var h: Number = _heuristic(test);
var f: Number = g + h;
if ((isOpen(test) || isClosed(test)))
{
if (test.f > f)
{
test.f = f;
test.g = g;
test.h = h;
test.parent = node;
}
}
else
{
test.f = f;
test.g = g;
test.h = h;
test.parent = node;
_open.push(test);
}
}
}
_closed.push(node);
if (_open.length == 0)
{
trace("No Path Found");
return false;
}
_open.sortOn("f", Array.NUMERIC);
node = _open.shift() as Node; // takeing the first element of array(which is the lowest cost!)
}
buildPath();
return true;
}
private function buildPath():void
{
_path = new Array();
var node: Node = _endNode;
_path.push(node);
while (node != _startNode)
{
node = node.parent;
_path.unshift(node); // add to the begining of array
}
}
public function get path():Array
{
return _path;
}
private function isOpen(node: Node):Boolean
{
for (var i: int = 0; i < _open.length; i++)
{
if (node == _open[i])
return true;
}
return false;
}
private function isClosed(node: Node):Boolean
{
for (var i: int = 0; i < _closed.length; i++)
{
if (node == _closed[i])
return true;
}
return false;
}
private function manhattan(node: Node):Number
{
return Math.abs(node.x - _endNode.x) * _straightCost +
Math.abs(node.y + _endNode.y) * _straightCost;
}
private function euclidian(node: Node):Number
{
var dx: Number = node.x - _endNode.x;
var dy: Number = node.y - _endNode.y;
return Math.sqrt(dx * dx + dy * dy) * _straightCost;
}
private function diagonal(node: Node):Number
{
var dx: Number = Math.abs(node.x - _endNode.x);
var dy: Number = Math.abs(node.y - _endNode.y);
var diag: Number = Math.min(dx, dy);
var straight: Number = dx + dy;
return _diagCost * diag + _straightCost * (straight - 2 * diag);
}
public function get visited():Array
{
return _closed.concat(_open);
}
}
}
i think i should explain this, inside the codes, in class declaration
you see
//private var _heuristic: Function = manhattan;
//private var _heuristic: Function = euclidian;
private var _heuristic: Function = diagonal;
these are cost functions! each uses a different method, for example one uses,
if its left or right or top or bottom cell, it will cost 1 and if its topLeft, topRight, bottomLeft, bottomRight Cells it will cost 1.5 point, and it will uses these point to find the nearest path!
there is also custom costing as well ! why ? , for example every where is ground and some parts are water cells, you can say ground cells worth 1 point and water cells worth 3 point, meaning if you pass 3 ground cells it equals passing one water cell, and all these also will be considered in your nearest path Algorithm ,
and using it, you can easily make a game with different fields and paths
there is also
if (test == node || !test.walkable || !_grid.getNode(node.x, test.y).walkable || !_grid.getNode(test.x, node.y).walkable) continue;
this part which has walkable variable for each node, if its true, the node can be used as a path! and if its false that node IS NOT WALKABLE this way you can even build walls and impossible to walk objects in some cells
here is a link to my Final project that uses this class (it's swf file which is uploaded online, so you can simply watch the output as long as you have flash player)
Make sure you watch this :
http://www.fastswf.com/HIa1W9M
hopefully what i said helps you.
Good luck.
