A* Pathfinding With AS3

When I earned my degree as a designer, I never thought I’d end up writing a blog post about AI. However, I took a crack at writing an A* (A-star) pathfinding algorithm about five years ago for the avatar movement system in the first generation of the Lassie Engine (built using Macromedia Director and Lingo). My entire source of reference for that first implementation was The Beginner’s Guide to Pathfinding Algorithms. If you’re interested in pathfinding theory, that article is an absolute gold mine. I won’t even pretend that I could do a better job of explaining the algorithm’s nuts and bolts, so I’ll just stick to what an AS3 implementation looks like.

First, we need a data structure of a grid to run searches across. I’m generally drawn to XML for raw data structures like this since it’s easy to compose and maintain by hand. Here’s a simple XML grid of points:

Save as: grid.xml

<nodes>
    <node id="n1" x="25" y="25" join="n2,n3"/>
    <node id="n2" x="110" y="110" join="n1,n3,n4"/>
    <node id="n3" x="50" y="180" join="n1,n2,n5,n6"/>
    <node id="n4" x="225" y="90" join="n2,n5,n6"/>
    <node id="n5" x="190" y="160" join="n3,n4"/>
    <node id="n6" x="230" y="170" join="n3,n4"/>
</nodes>

The above XML creates a grid that looks like this:

demo grid of points

That XML structure is extremely simple. Each node is given an ID, an X and Y coordinate, and has a comma-separated list of other node ID’s that it connects to.

Next, we move on to the simple geometry structures that we’ll feed into our pathfinder. First is the Node object. While we’ll load our grid data as XML, we’ll want to parse that into typed Objects to give our implementation compile-time validation. So, we’d load our XML and then parse the nodes into this structure:

Save as: com/lassie/player/geom/Node.as

package com.lassie.player.geom
{
    import flash.geom.Point;

    public final class Node extends Point
    {
        // public
        public var id:String = "";

        // private
        private var _neighbors:Array;

        public function Node(key:String="", x:int=0, y:int=0):void
        {
            super(x, y);
            id = key;
            _neighbors = new Array();
        }

        /*
        * Returns all current data as a new Node object.
        */
        public function cloneNode():Node
        {
            var node:Node = new Node(id, x, y);
            node.parseNeighbors(_neighbors.join(","));
            return node;
        }

        /*
        * Parses a list of comma-seperated node id's into the array of neighbors.
        */
        public function parseNeighbors(csv:String):void
        {
            for each (var j:String in csv.split(",")) addNeighbor(j);
        }

        /*
        * Adds a new neighbor Id.
        */
        public function addNeighbor(id:String):void
        {
            if (!containsNeighbor(id) && id != "") _neighbors.push(id);
        }

        /*
        * Gets a neightbor Id by numeric index.
        */
        public function getNeighbor(index:int):String
        {
            if (index >= 0 && index < _neighbors.length) return _neighbors[index];
            return null;
        }

        /*
        * Gets the number of neighbors assigned to this node.
        */
        public function get numNeighbors():int
        {
            return _neighbors.length;
        }

        /*
        * Tests if the specified node id is among this node's neighbors.
        */
        public function containsNeighbor(id:String):Boolean
        {
            return _neighbors.indexOf(id) > -1;
        }

        /*
        * Appends an additional namespace key onto all Node references. Avoids conflicts during Grid unions.
        */
        public function expandNamespace(key:String):void
        {
            id += key;
            for each (var j:String in _neighbors) j += key;
        }

        /*
        * Trace object to string.
        */
        public override function toString():String
        {
            return "[Node] id:"+ id +", x:" + x + ", y:" + y + ", neighbors:(" + _neighbors + ")";
        }
    }
}

Now we need a Path object. Paths will be the actual search routes that our A* algorithm will create, branch, prioritize, and purge as it works. Here’s the Path class:

Save as: com/lassie/player/geom/Path.as

package com.lassie.player.geom
{
    public final class Path
    {
        // public
        public var length:int = -1;
        public var bestCase:int = -1;
        public var nodes:Array;

        // private
        private var _path:Array;

        public function Path($length:Number=-1, $bestCase:Number=-1, $path:Array=null):void
        {
            length = $length;
            bestCase = $bestCase;
            _path = ($path != null) ? $path : new Array();
        }

        public function destroy():void
        {
            _path = null;
            nodes = null;
        }

        /*
        * Returns all current data as a new Path object.
        */
        public function clone():Path
        {
            return new Path(length, bestCase, _path.slice());
        }

        /*
        * Tests if path has been initialized with actual pathing data.
        */
        public function get hasLength():Boolean
        {
            return length + bestCase >= 0;
        }

        /*
        * Returns the last node id contained within the path.
        */
        public function get lastElement():String
        {
            return _path.slice(-1)[0];
        }

        /*
        * Tests if this path contains a node Id.
        */
        public function containsNode($id:String):Boolean
        {
            return _path.indexOf($id) > -1;
        }

        /*
        * Adds a node to the path if not already present.
        */
        public function addNode($id:String):void
        {
            if (!containsNode($id)) _path.push($id);
        }

        /*
        * Trace object to string.
        */
        public function toString():String
        {
            return "[Path] length:"+ length +", nodes:("+ _path +")";
        }
    }
}

And finally we need a grid class. A Grid will hold Nodes, keyed by their respective Id’s, and will have the actual A* implementation within it to do the heavy lifting of grid searches.

Save as: com/lassie/player/geom/Grid.as

package com.lassie.player.geom
{
    import flash.geom.Point;

    public final class Grid extends Object
    {
        private var _nodes:Object;

        public function Grid():void
        {
            super();
            _nodes = new Object();
        }

        /*
        * Parses an XML structure into the grid object.
        */
        public function parseXML($xml:XML):void
        {
            // loop through all <node> XML items
            for each (var $nodeXML in $xml.children())
            {
                // create a new Node object for each XML item
                var $node:Node = new Node($nodeXML.@id, $nodeXML.@x, $nodeXML.@y);
                $node.parseNeighbors($nodeXML.@join);

                // register node by Id within the grid
                _nodes[$node.id] = $node;
            }
        }

        /*
        * Gets a node object by ID name
        */
        public function getNodeById($id:String):Node
        {
            if (_nodes[$id] != undefined) return _nodes[$id] as Node;
            return null;
        }

        /*
        * Finds the shortest path between two nodes.
        */
        public function findPath($startId:String, $goalId:String):Path
        {
            // queue of paths to search
            var $stack:Array = new Array(new Path(0, 0, [$startId]));
            // best path to goal
            var $best:Path = new Path();
            // shortest distance to each node reached thus far
            var $reachedNodes:Object = new Object();
            // cycle counter (for debug and optimization)
            var $cyc:int = 0;

            // UNTIL ALL SEARCH PATHS HAVE BEEN ELIMINATED
            while ($stack.length > 0)
            {
                // pull the first path out from the search stack
                var $searchPath:Path = $stack.shift() as Path;

                // pull the last node element from the path
                var $searchNode:Node = getNodeById($searchPath.lastElement);

                // EXTEND PATH ONE STEP TO ALL NEIGHBORS
                // creating X new paths
                for (var j:int=0; j < $searchNode.numNeighbors; j++)
                {
                    // Branch: duplicate current search path as a new branch
                    var $branch:Path = $searchPath.clone();

                    // Pull and expand upon each of searchNode's neighbor Id's.
                    var $expandNode:String = $searchNode.getNeighbor(j);

                    // REJECT PATHS WITH LOOPS
                    // if branch does NOT already contain next search node
                    if (!$branch.containsNode($expandNode))
                    {
                        // get coordinates of previous, current, and goal nodes
                        var $prevCoord:Node = getNodeById($branch.lastElement);
                        var $currentCoord:Node = getNodeById($expandNode);
                        var $goalCoord:Node = getNodeById($goalId);

                        // extend branch after having referenced last end-point.
                        $branch.addNode($expandNode);

                        // UPDATE BRANCH LENGTH AND UNDERESTIMATE
                        $branch.length += Point.distance($prevCoord, $currentCoord);
                        $branch.bestCase = $branch.length + Point.distance($currentCoord, $goalCoord);

                        // TRACK SHORTEST DISTANCE TO EACH NODE REACHED
                        // attempt to pull a distance-to-node from the register of reached nodes.
                        // if node has not yet been reached, register it with the current branch length.
                        var $shortest:Number = $reachedNodes[$expandNode];
                        if (isNaN($shortest)) $shortest = $branch.length;

                        // TEST IF PATH IS WORTH KEEPING (keep if:)
                        // - if branch is as short or shorter than the best distance to the current expansion node
                        // - and if a best-path has not been found yet, OR if this branch's best case scenario is still shorter than the best path.
                        if ($branch.length <= $shortest && (!$best.hasLength || $branch.bestCase < $best.length))
                        {
                            // log as best path to current search node
                            $reachedNodes[$expandNode] = $branch.length;

                            // If the expansion node is the goal, save branch as the parth to beat.
                            // Otherwise, add the branch back into the search stack.
                            if ($expandNode == $goalId) $best = $branch;
                            else $stack.push($branch);
                        }
                    }
                }

                // PRIORITIZE SEARCH PATHS
                // sort paths by best-case scenario so that most likely paths are searched first.
                var $priority:Function = function($a:Path, $b:Path):int
                {
                    if ($a.bestCase < $b.bestCase) return -1;
                    else if ($a.bestCase > $b.bestCase) return 1;
                    else return 0;
                }
                $stack.sort($priority);
                $cyc++;
            }
            return $best;
        }
    }
}

Now let’s put all that together. Create a new Flash document in the root of your class path and put that “grid.xml” file in with it. Then in frame-1 actions of the root timeline, just add the following:

import com.lassie.player.geom.Grid;
var $xmlLoader:URLLoader = new URLLoader();
$xmlLoader.addEventListener(Event.COMPLETE, this._onXMLLoaded);
$xmlLoader.load(new URLRequest("grid.xml"));

function _onXMLLoaded($event:Event):void
{
    // retrieve the loaded XML data
    var $xml:XML = new XML($event.target.data);

    // create a new grid and parse the loaded XML into it.
    var $grid:Grid = new Grid();
    $grid.parseXML($xml);

    // find a path between two node Id's
    trace($grid.findPath("n1", "n5"));
    trace($grid.findPath("n1", "n6"));
}

If you run that script as is, you should get the following output:

[Path] length:298, nodes:(n1,n3,n5)
[Path] length:316, nodes:(n1,n2,n4,n6)

Those are traces of two separate path searches run across the grid. The first search connected n1 and n5 to one another through their common neighbor of n3. The second search took a dramatically different route from n1 to n6 that branched through n2 and n4. Why? Because it was slightly shorter to run through two connections rather take the single connection through n3.

Advertisements

22 comments so far

  1. Matt on

    This is awesome – probably the cleanest pathfinding routine I’ve seen for AS3. Also happens to be the first AS3 pathfinding routine I’ve been able to successfully put into a movie and test.

    How would I return the available spaces given a set range of nodes? For instance, I ask your pathfinder for all nodes that are 3 or less nodes away? Instead of finding a path, I just want it to tell me an array of all nodes within the range.

    Thanks! Great work!

    • bigmac on

      Matt, thanks for the feedback. Glad it was helpful. As for putting in node count restriction, you’d just have to add in some rules in the later part of the algorithm. That would be some very specific logic custom to your program (given that it generally goes against the goals of pathfinding to stop the process before a complete path has been found). I guess I could see the practicality of that feature though in a case like wanting a player to move toward a goal, but limiting their move per turn to X spaces…

      If that’s what you have in mind, then I’d suggest adding in some logic to look at the number of nodes stored in each path toward the end of the cycle, and start forking all working paths out to a secondary queue once they reach your node count limit. This will halt the A* algorithm in its typical manner, given that A* runs until all search paths have been exhausted. If you retain your omitted search paths in a secondary queue, then you could run a post process that would compare all of those search paths and yield the path with the shortest length estimate.

  2. Matt on

    I’m pretty much just looking to add a function into the pathfinder that: given node-x, return an array of all nodes within 3 positions from the origin, including the origin itself. I really don’t even need it to show me the best option, or really even find a best path at all. I’ll mess around with holding the path data in a second private array and do some condition to return it instead of the path. Maybe if there is no destination node, it will fork and just spit back all the nodes within the range. This would all go in the Path.as file I imagine. Thoughts?

  3. Matt on

    Bah, I’ve worked on this for the last 15 hours and haven’t come up with the solution. The recursion is just killing me. Can you write a function for me in the Grid.as class called getRadius(origin, radius) that will return all the spaces within range of the origin? The best I’ve been able to do is to return all the origin’s neighbor nodes (which was pretty easy), but I can’t seem to figure out how to loop that to get the neighbors of those neighbors and so on up to x steps out. Thanks a million!

  4. Matt on

    Figured out how to create a radius search and add it to your pathfinder script. If you have any suggestions on ways to improve it I’m all ears, but it works and that’s good enough for me.

    Instead of calling findPath(start, end) I added another class function called findRadius(start, distance). It returns an array of all nodes within 5 (or x or whatever) nodes distance from the starting point.

    Add the following to the Grid.as:

    // RADIUS SEARCH GIVEN A STARTING NODE
    		// this will expand outward and return connected nodes
    		// -----------------------------------------------------------------------------------------------------
    		public function findRadius($startId:String, $radius:Number):Array {
    			
    			trace("\nCalculating path:");
    			
    			// arrays for keeping track of the path and distances from the origin
    			var $workArray:Array = new Array(new Path(0, 0, [$startId]));
    			var $tempArray:Array = new Array();
    			var $masterArray:Array = new Array();
    			
    			// put the point of origin into the results array
    			$masterArray.push($startId);
    			
    			// init inner recursive loop counter
    			var k:int = 0;
    			
    			// outer loop for the number of steps to take from origin
    			for (var i:int = 0; i < $radius; i++) {
    				
    				// reset the contents of the temp array for each step loop
    				$tempArray = [];
    				
    				// find the length of the work array (all neighbors of current point)
    				var $mainLength:int = $workArray.length;
    				
    				// loop through all connected points
    				for (var j:int = 0; j < $mainLength; j++) {
    					
    					// take the current point as the search point to iterate
    					var $searchPath:Path = $workArray[j] as Path;
    					
    					// pull the last node element from the path
    					var $searchNode:Node = getNodeById($searchPath.lastElement);
    					trace("$searchNode = " + $searchNode.id);
    					
    					// find all the neighbor nodes from the current node and loop all
    					k = 0;
    					while (k < $searchNode.numNeighbors) {
    						
    						// make this node a path piece to conform to the code rules
    						var $simplePath:Path = new Path(0, 0, [($searchNode.getNeighbor(k))]);
    						
    						// if this node isn't in master results array, add it
    						// run the same check for the temp array into the work array
    						var checkThis:String = $searchNode.getNeighbor(k);
    						var isDupe:int = $masterArray.indexOf(checkThis);
    						if (isDupe == -1) {
    							$masterArray.push($searchNode.getNeighbor(k));
    							$tempArray.push($simplePath);
    						}
    						
    						// increment the neighbor nodes and recurse
    						k++;
    					}
    
    				}
    				
    				// copy the new temp array over the the work array for the next loop
    				$workArray = $tempArray.concat();
    			}
    			
    			// return all the possible path nodes
    			return $masterArray;
    
    		}
    
  5. K-Man on

    that’s too cool.

    although i am still having a bit hard time to make your code work, i will try it again. it will be great if you can provide the source files, zip it, change the extension from ‘.zip’ to ‘.jpg’ and upload it to wordpress.com.

  6. Matt on

    This is really great, but I have absolutely no idea how to give the path to another game object to actually follow.

    • bigmac on

      LOL… well, that is always the pickle, isn’t it? For what it’s worth though, you’ve got the hard part done… animating a graphic along a path is –technically– far easier to do, but HOW you do it is entirely dependent on the goals of your game. For a really quick start, I’d suggest using an existing tween engine like TweenLite or Tweener. Both of those engines support queued tweens as I recall, so a dirt simple way to follow the path would just be to loop through the returned nodes and configure a Tween engine call to move the object to each point, then you can just let the tween queue play out. It’s quick and dirty, but it should give some instant gratification!

  7. Kexi on

    This code snippet looks promising, but I have some problem with it. I hope someone can help.
    I tried to pass two string parameters to the function findPath from two input textfields but it just wouldn’t work. Here’s how I tried it:

    ON FRAME1:
    
    var s1:String
    var s2:String
    button.addEventListener(MouseEvent.MOUSE_DOWN,
    function():void
    {
    	s1=input1.text
    	s2=input2.text
    	gotoAndStop(2)
    }
    	)
    
    
    ON FRAME 2:
    
    import com.lassie.player.geom.Grid;
    var $xmlLoader:URLLoader = new URLLoader();
    $xmlLoader.addEventListener(Event.COMPLETE, this._onXMLLoaded);
    $xmlLoader.load(new URLRequest("grid.xml"));
    
    function _onXMLLoaded($event:Event):void
    {
        // retrieve the loaded XML data
        var $xml:XML = new XML($event.target.data);
    
        // create a new grid and parse the loaded XML into it.
        var $grid:Grid = new Grid();
        $grid.parseXML($xml);
    
        // find a path between two node Id's
        trace($grid.findPath(s1, s2));
    
    }				
    

    Thanks for your reply in advance.

    • bigmac on

      Hmmm… dunno, that looks okay, although I can’t guarantee that the “s1” and “s2” vars aren’t being lost during the timeline transition. For what it’s worth, I’ve found the Flash timeline to be notoriously unreliable within AS3 programming… things that used to work reliably in AS2 between timeline frames are now hit-or-miss in AS3. However, that’s also not really a bad thing because you can do so much more with the display architecture within AS3, so the timeline becomes fairly useless for anything save for good old fashion timeline animation.

      So, in RE: to your question… just instantiate the grid and run the search in response to the button click on frame-1. Otherwise, I’d start debugging the problem by tracing the values both at the point that they’re set and at the point that they’re fed into the “findPath” method.

  8. Badim on

    Hey Greg,
    tnx for sharing this. if you`d like to see game that use this, just email me or pm me.

    PS: here is addition to use this class without xml:
    (extends main class)
    public function purge_all():void{
    _nodes = {};
    }
    public function addNode($id:String,$x:Number,$y:Number){
    var $node = new Node($id, $x, $y);
    _nodes[$node.id] = $node;
    return $node;
    }
    public function addNeighbor(node_id,n_id):void{
    _nodes[node_id].addNeighbor(n_id);
    }

  9. Jay on

    This code is going to be a life saver for me. I’m working on an isometric diner dash style game and this is exactly the path finding I need. I got everything working except for:

    var path:Path = grid.findPath(“belt1”, “belt4”);
    trace(path);
    results in: [Path] length:155, nodes:(belt1,belt2,belt4)

    trace(path.length);
    results in (belt1,belt2,belt4)

    but trace(path.nodes);
    results in null

    I can’t figure out how to access the actual nodes.

  10. munnos on

    Hy, i saw your script and is one of the most accurate and clean. It works, but i have a question. How do i implement it visually? I want do i import the graphics, like buttons or the red line, within this code.

    Waiting for your answer. I would be so grateful for this.

  11. Epic428 on

    Hey this seems pretty good. I’m not very fluent on pathfinding and A* but I know enough that pathfinding provides a more intelligent AI.

    In any case, I notice that these classes basically require everything to follow on the grid. Unfortunately, for what I’m looking to create, I can’t always be “on the grid.”

    So to solve this problem, I see the code above that allows adding of nodes without XML. I’m wondering how I can get that to create dynamic nodes?

    For example, instead of having everything go based on grid movement I want my objects to be able to move as fast/slow as they want and as freely as they want. This means that their node relative to the static nodes are constantly changing.

    How would I go about dynamically changing their node so that it always retains the closest neighbors? If I can solve that aspect, then I can get say enemies to always move towards a player but with a more intelligent AI.

    Any ideas on how to solve this? I would be greatly appreciative of any help offered. Thanks again!

  12. Epic428 on

    It appears your path class is missing something. I can comment out public var nodes:Array; and nodes = null; and the class will still compile.

    Apparently you are not setting nodes to anything at any point, which makes that variable useless. It would also explain why jay was having problems. I suggest this be corrected as soon as possible so others do not have the same issues.

    Perhaps it would just be best to return _path by use of a function and eliminate that variable altogether.

  13. radiochecker on

    awesome and helpful post, thank you very much

  14. fmanuv on

    Hi,

    I was looking for A* in AS3, and your site was one of the first on Google. Nice achievement.

    Got one problem, if the node name are not linear (p1, p2, p4, p7), then it crash in the findPath main loop. I need it to be that way as I’m making a game on top of an existing application that have the nodes id named that way.

    Try to find a quick solution, but haven’t figure it out yet. Any idea beside a lookup table?

    Thanks

  15. Mike G. on

    This is by far the most comprehendable explanation of A*pathfinding that I have found. Kudos sir. This has helped me tremendously to move my own project further; but more so to ferment my own understanding of pathfinding which will be useful for all of my future endeavors. Many thanks and God bless!

  16. Artsystems on

    Thankyou Greg. Great work.

    The following section in Grid.as seems to be orphaned:

    // PRIORITIZE SEARCH PATHS
    // sort paths by best-case scenario so that most likely paths are searched first.
    var $priority:Function = function($a:Path, $b:Path):int
    {
    if ($a.bestCase $b.bestCase) return 1;
    else return 0;
    }
    $stack.sort($priority);

    Where is this inline function called and which 2 parameters is it passed?

    The search still works when it is removed.

  17. Gabe on

    Wow! Thanks a million so much for this incredible snippet.

  18. phpguy on

    nice … job well done.

  19. Paul on

    Thanks for this AMAZING piece of work. Just one problem though – how do I get the resulting node set as an Array which I can do Array-things to ?

    For example

    trace($grid.findPath(“n1”, “n5”));

    returns

    (n1,n3,n5)

    But how can I get access to say element 1 of this “Array” being the n3 ?

    If I could assign;

    myArray = trace($grid.findPath(“n1”, “n5”));

    then myArray[1] = “n5”

    I know the elements are strings so I would need to convert to integers.

    Paul


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: