A* algoritm in ActionScript

Want to know the shortest path from one point to another? If you're making a roguelike then you probably do. You could use Dijkstra's algorithm, but there's an alternative that finds the result much faster. It's the A*, or A Star, algorithm. It's a lot like Dijkstra's algorithm except instead of checking the neighbors of all the currently visited cells, it just checks the neighbor of the visited cell that's the closest to the target. Of course if you already know which one is closest then you don't need to pathfind. Instead you just estimate which one is closest. Even if your estimates are a bit off, you'll still find the shortest path in much less time.

Here's an ActionScript implementation.

	package
	{
	import flash.geom.Point;
	public class AStar
	{
	private var open:Array = null;
	private var closed:Array = null;
	private var canEnter:Function;
	private var start:Point;
	private var checkEnding:Boolean;
	public function AStar(canEnter:Function, start:Point, checkEnding:Boolean)
	{
	this.canEnter = canEnter;
	this.start = start;
	this.checkEnding = checkEnding;
	}
	public function pathTo(end:Point):Array
	{
	if((checkEnding && !canEnter(end.x, end.y)) || (start.x == end.x && start.y == end.y))
	return [];
	var startNode:AStarNode = new AStarNode(start.x, start.y, null);
	startNode.g = 0;
	startNode.h = getHCost(start, end);
	startNode.f = startNode.g + startNode.h;
	open = [startNode];
	closed = [];
	while(open.length > 0)
	{
	var current:AStarNode = open[0];
	closed.push(current);
	open.splice(0,1);
	if(current.x == end.x && current.y == end.y)
	break;
	for each (var offset:Array in [[-1,-1],[-1,0],[-1,1],[0,-1],[0,1],[1,-1],[1,0],[1,1]])
	{
	var neighbor:Point = new Point(current.x + offset[0], current.y + offset[1]);
	var newG:int = getGCost(current, neighbor);
	if (!checkEnding && neighbor.x == end.x && neighbor.y == end.y)
	{
	var endNode:AStarNode = new AStarNode(neighbor.x, neighbor.y, current);
	endNode.g = newG;
	endNode.h = getHCost(neighbor, end);
	endNode.f = endNode.g + endNode.h;
	open.unshift(endNode);
	break;
	}
	if (!canEnter(neighbor.x, neighbor.y) || getFromList(closed, neighbor) != null)
	continue;
	var visited:AStarNode = getFromList(open, neighbor);
	if(visited == null)
	{
	var newNode:AStarNode = new AStarNode(neighbor.x, neighbor.y, current);
	newNode.g = newG;
	newNode.h = getHCost(neighbor, end);
	newNode.f = newNode.g + newNode.h;
	open.push(newNode);
	}
	else if(newG < visited.g)
	{
	visited.parentNode = current;
	visited.g = newG;
	visited.f = visited.g + visited.h;
	}
	}
	open.sort(sortOnFCost);
	}
	return walkBackToStart(end);
	}
	private function walkBackToStart(end:Point):Array
	{
	var thisStep:AStarNode = getFromList(closed, end);
	if (thisStep == null)
	return [];
	var steps:Array = [];
	while(thisStep.x != start.x || thisStep.y != start.y)
	{
	steps.push(new Point(thisStep.x, thisStep.y));
	thisStep = thisStep.parentNode;
	}
	steps.reverse();
	return steps;
	}
	private function getGCost(from:Point, to:Point):int
	{
	return Math.max(Math.abs(from.x - to.x), Math.abs(from.y - to.y));
	}
	private function getHCost(from:Point, to:Point):int
	{
	return Math.abs(from.x - to.x) + Math.abs(from.y - to.y);
	}
	private function getFromList(list:Array, loc:Point):AStarNode
	{
	for each (var other:AStarNode in list)
	{
	if (other.x == loc.x && other.y == loc.y)
	return other;
	}
	return null;
	}
	private function sortOnFCost(n1:AStarNode, n2:AStarNode):Number
	{
	if (n1.f < n2.f)
	return -1;
	else if (n1.f > n2.f)
	return 1;
	else
	return 0;
	}
	public static function pathTo(canEnter:Function, start:Point, end:Point, checkEnding:Boolean):Array
	{
	return new AStar(canEnter, start, checkEnding).pathTo(end);
	}
	}
	}
	class AStarNode extends flash.geom.Point
	{
	public var g:int = 0;
	public var h:int = 0;
	public var f:int = 0;
	public var parentNode:AStarNode = null;
	public function AStarNode(x:int, y:int, parent:AStarNode)
	{
	super(x, y);
	this.parentNode = parent;
	}
	}

view raw AStar.as hosted with ❤ by GitHub

This algorithm needs some explanation since it was made by mathematicians - who generally suck at naming variables. That's why there's a g, h, and f cost. The H cost is the heuristic or estimated cost from a point to the end point. The G cost is the actual cost from the start point to a point. There's no need to estimate that because you only calculate this on points that you've visited. The F cost is the total of the two. By only checking the neighbors of the point with the lowest F cost, you end up - in the best case - only checking the points that are in the shortest path. You can change the getGCost and getHCost methods to cause different behavior. Maybe some points cost more to travel through? Maybe moving diagonal cost more than moving in the cardinal directions? Try it and see what happens.

The checkEnding boolean is because in my game people sometimes can pathfind to walls and obstacles that block movement.

It's mostly used for pathfinding but can also be used for carving rivers, roads, or caves during worldgen. You could also use it to tell where someone is probably going to go - useful for placing traps I suppose. Have you seen any interesting uses for this algorithm?