A* (Astar)

About

According to WikiPedia, A* (pronounced A Star) is

a best-first, graph search algorithm that finds the least-cost path from a given initial node to one goal node (out of one or more possible goals).

In other words, A* finds the best path from point A to point B. This can be the shortest path but it doesn’t have to. It could for example be better to pass arround a mountain (which would be a longer path) than to go over it.

What you can find here, is an AS3 implementation of A*. It’s primary goal is stability. It should be able to find the path on a 1000×1000 map as well as on a 10×10 map. I will probably create a Lite edition which will focus entirely on speed and ignore stability and be less dynamic/extensible.

Demo

Enough with the chit-chat! Since a picture (or movie) says more than a thousand words, I’ve created this little test application / demo:

Demo

Why use this implementation?

I have tried my best to add a lot of extensibility and flexibility to this implementation:

  • Any type of map you like (square tiles, hexagonal tiles, octagonal, …)
  • Add restrictions to tiles (fe. max numbers of chars on 1 tile, maximum height of a tile, …)
  • Add restrictions to movement (fe. maximum height difference between two tiles)
  • Specify the intensity of the algorithm (the number of iterations per interval & the time between intervals)
  • Asynchronous with search queue (You can add search requests to the Astar instance without worrying about other requests. They will be handled as First Come First Serve)


Download

Version 1.0
Version 1.1

Changelog

V1.1

  • Added AstarPath.toArray();


Documentation

The documentation is available both online and as a download:
Online
Download
The documentation isn’t that good, but I hope it’s clear enough to use. (Feel free to help documenting :-) )

Examples

The most basic example:

package
{
	import flash.text.TextFieldAutoSize;
	import flash.text.TextField;
	import flash.geom.Point;
	import flash.display.Sprite;
	import be.dauntless.astar.*;
	import be.dauntless.astar.analyzers.WalkableAnalyzer;
 	public class Application extends Sprite
	{
		private var map : IMap;
		private var astar : Astar;
		private var dataMap:Array;
		public function Application()
		{
			dataMap = [ [2,2,1,1,1,2],
						[2,2,2,2,1,2],
						[2,1,1,2,2,2],
						[2,2,2,2,1,2],
						[2,1,1,2,1,2],
						[1,1,2,2,2,2] ];
			map = new Map(dataMap[0].length, dataMap.length);
			for(var y:Number = 0; y< dataMap.length; y++)
			{
				for(var x:Number = 0; x< dataMap[y].length; x++)
				{
					map.setTile(new BasicTile(1, new Point(x, y), (dataMap[y][x]==2)));
				}
			}
			astar = new Astar();
			astar.addAnalyzer(new WalkableAnalyzer());
			astar.addEventListener(AstarEvent.PATH_FOUND, onPathFound);
			astar.addEventListener(AstarEvent.PATH_NOT_FOUND, onPathNotFound);
			astar.getPath(new PathRequest(new Point(0, 0), new Point(5, 5), map));
		}
 
		private function onPathNotFound(event : AstarEvent) : void
		{
			trace("path not found");
		}
 
		private function onPathFound(event : AstarEvent) : void
		{
			trace("Path was found: " + event.getPath().toString());
		}
	}
}

This will return

Path was found: AstarPath: (0,0),(0,1),(0,2),(1,3),(2,3),(3,4),(4,5),(5,5)

Make sure you remember to add the WalkableAnalyzer if you don’t want your path to go through walls. Just like the WalkableAnalyzer, you can add other analyzers like the HeightAnalyzer, FullClippingAnalyzer, etc. For example, if you don’t want to go diagonally, you have to add the FullClippingAnalyzer:

astar.addAnalyzer(new FullClippingAnalyzer());

If you want to go diagonally, but only if the adjacent tiles are empty, add the SmartClippingAnalyzer. You can play around with the standard analyzers in the Demo to see what they do.

You can also create your own analyzers. For example, if you want to find a path from A to B while avoiding C, you could do something like this:

package
{
	import be.dauntless.astar.IMap;
	import be.dauntless.astar.IPositionTile;	
 
	import flash.geom.Point;	
 
	import be.dauntless.astar.Analyzer;
 
	/**
	 * @author Jeroen
	 */
	public class AvoiderAnalyzer extends Analyzer
	{
		private var toAvoid : Point;
		private var distance:Number;
		public function AvoiderAnalyzer(toAvoid:Point, distance:Number)
		{
			this.toAvoid = toAvoid;
			this.distance = distance;
			super();
		}
 
		override public function analyzeTile(tile: *):Boolean
		{
			var pos:Point = (tile as IPositionTile).getPosition();
			return (Math.abs(pos.x - toAvoid.x) + Math.abs(pos.y - toAvoid.y) &gt; distance);
		}
 
		override protected function analyze(mainTile : *, allNeighbours:Array, neighboursLeft : Array, map : IMap) : Array
		{
			var newLeft:Array = new Array();
			for(var i:Number = 0; i< neighboursLeft.length; i++)
			{
				var currentPos : Point = (neighboursLeft[i] as IPositionTile).getPosition();
				var currentDistance:Number = Math.abs(toAvoid.x - currentPos.x) + Math.abs(toAvoid.y - currentPos.y);
				if(currentDistance > distance) newLeft.push(neighboursLeft[i]);
			}
			return newLeft;
		} 
 
		public function getToAvoid() : Point
		{
			return toAvoid;
		}
 
		public function setToAvoid(toAvoid : Point) : void
		{
			this.toAvoid = toAvoid;
		}
 
		public function getDistance() : Number
		{
			return distance;
		}
 
		public function setDistance(distance : Number) : void
		{
			this.distance = distance;
		}
	}
}

Add it to the analyzer chain:

astar.addAnalyzer(new AvoiderAnalyzer(new Point(1,4), 2));

And this would return the following path:

Path was found: AstarPath: (0,0),(1,0),(2,1),(3,1),(4,2),(5,3),(5,4),(5,5)


Bugs

No bugs so far, but if you do find one, please let me know! Feature requests are also appreciated.


License

AS3 A* is free of charge and available under the MIT License.

AS2 A*

A while back, I created an AS2 version of A*. It’s still online, though not under active development.
Documentation: Offline or Online
Source Files: AS2 Astar
SWC Component: SWC AS2 A*
Demo .fla: AS2 A* Example FLA

20 Responses to “A* (Astar)”

Feed for this Entry Trackback Address
  1. 1 Karim
    April 17, 2009 at 10:24

    great stuff you made man!!!

    so if I understand the MIT licence correctly I can use it?
    i’ll be sure to credit you :)

  2. 2 admin
    April 17, 2009 at 12:22

    How I understand the MIT license, is that you can use/sell/modify/copy any part of it, as long as you keep the original comments at the start of the classes intact.

  3. 3 Jesse
    May 14, 2009 at 21:50

    Wow, great job man!
    At school, we are building a little game in Java, and we are also implementing the A* algorithm.
    This can be a great resource, for finding out the inner workings of the algorithm.

    I will keep track of your site, hopeful to see more nice things. Keep up the good work!

  4. 4 Aaron
    June 30, 2009 at 02:21

    Thank you for such an extensible implementation! I’ve never seen one quite so useful before. I appreciate it!

  5. 5 admin
    June 30, 2009 at 09:24

    Thanks Aaron :). “Be sure to tell your friends” ;)

  6. 6 Stephen
    September 4, 2009 at 19:43

    Hi

    This is a very useful extensible implementation. It plugs very nicely into something I am building at the moment. It’s a shame that this page doesn’t rank high on a Google search - I found this site because I had your AS2 implementation from years back.

    I have a feature request. I would find it useful to be able to have access to an ‘AstarSearchedPath’, as well as the AstarPath. Essentially a collection of all the searched DataTile’s that could then be used to visualise the algorithms search strategy.

    Anyways, once again excellent work. I will spread the word about this :D

  7. 7 admin
    September 5, 2009 at 00:05

    Hi Stephen,

    Thanks for your comment! I’m doing my best to get it high on the google rankings, but I don’t really feel like spamming all the AS fora just to promote myself. Just be sure to blog about me and I’ll rise to the top :).

    I could get an AstarSearchedPath for you, but it should only be used @ development time as it would obviously slow down the algorithm. Why do you want it exactly? Is it because you want to know why your character takes a certain path when you expected another?

    But your suggestion actually makes sense, even it if would only come in handy for myself while debugging it. (It would be a lot clearer than the Flex debugger)

    I’ve also had some other suggestions (like a toArray() method for the AstarPath and the ability to bind analyzers to a request so that different types of players can share the same instance) and I will be adding yours, probably as a separate release.

    Greets!

  8. 8 Stephen
    September 7, 2009 at 19:01

    Hi

    Thanks for the response :)
    The project I am working on is a set of modules that simulate various aspects of computer games. For pathfinding/AI we are attempting to visualise the computation that goes on behind the scenes when a computer searches for a path using A Star. So, I am not particularly interested in speed, but instead want to be able to access information about searched tiles. I needed to get something spiked quickly and so have hacked a quick solution - apologies :D. I have set Astar Iterations to 1 and modified inspectNeighbours in Astar to dispatch an AstarSearchedEvent as each open neighbour tile is analysed:

    this.dispatchEvent(new AstarSearchedEvent(AstarSearchedEvent.TILE_SEARCHED, cN.getPosition(), cN.getParent().getPosition()));

    I’ve created a SearchCountTile class and associated ISearchCountTile interface with an incrementSearchCount method. The method that catches the AstarSearchedEvent uses position to retrieve and increment the associated SearchCountTile from the map. With this I can visually show how many times a tile has been searched, and I can also visualise in some way the route from parent tile to tile. This allows me to animate in various ways the search as it happens and seems to be working fine. Tiles with different costs appear to be correctly analysed, and final found paths seem correct. However, I’m still thinking about ways to visualise this so it’s got a long way to go yet!!!

    Anyways - that will give you an idea of where I am going with this. You are right though - something could be integrated into your code to help with debugging. Cheers

    Stephen

  9. 9 Michel
    September 15, 2009 at 09:16

    I love this! it works really great! so thanks :)
    Only “bug”, “thing” i found was when i uses the smartClippingAnalyzer it has some duplicate veriable definition errors on line 46, 47, 55, 56, 61 and 62 nothing big.

    Again, thank you!

  10. 10 DooM McQ
    September 22, 2009 at 05:41

    Wow, indeed a very extensible library, i’m just downloading and getting ready to test it, but i did noticed these in your analyzer example

    I think here is where you r going to avoid jumping on the avoidable tile, but not sure xD

    override protected function analyze(mainTile : *, allNeighbours:Array, neighboursLeft : Array, map : IMap) : Array
    {
    var newLeft:Array = new Array();
    for(var i:Number = 0; i distance)<<<<<<<<
    newLeft.push(neighboursLeft[i]);
    } <<<<<<<<
    return newLeft;
    }

    Again congratulations, a fine implementation =)

  11. 11 admin
    September 22, 2009 at 10:59

    Hi DooM McQ,

    You’re right, something went wrong there … I’ve edited the code and it should work now.

    Thanks for reporting!

  12. 12 OnurG.
    October 28, 2009 at 15:05

    great job,

  13. 13 pento
    November 4, 2009 at 14:51

    hi.
    how can i use Hex map?
    is any body know?

  14. 14 Tim
    November 8, 2009 at 18:32

    Hi and thanks for this amazing pathfinding engine!
    I only have one problem, i can not access the AstarPath like an array and “event.getPath() as Array” doesen’t worked for me. I only recieved a string with the path info. Is there a way to get the path as an array?
    Thanks

  15. 15 admin
    November 8, 2009 at 23:36

    The AstarPath class implements the IIterator class, so you can loop through it like this:

    while(path.hasNext()) path.getNext();

    But since a lot of people have asked for a simple array, I’ve updated the AstarPath class to include a toArray() method.

  16. 16 Tim
    November 10, 2009 at 01:53

    Many thanks!

  17. 17 B.Riché
    November 30, 2009 at 09:23

    Hey,
    that’s a very good job, this is the first as3 A* implementation I see that includes the heights and max occupation of the tiles !!

    This is a very good implementation, great work !

  18. 18 Chris
    January 15, 2010 at 04:47

    The example gives some errors trying to compile?

    http://yfrog.com/3oerrorxpdj

  19. 19 Chris
    January 15, 2010 at 04:50

    Ah nevermind I see already.. the code blocks are not working.. it converts html entities

  20. 20 crazedwood
    January 21, 2010 at 03:35

    hi,

    I see the demo,so good.can I get the demo source? I think its help for me. my English is so bad, :P ,My mail:c.sx@hotmail.com. many tks.

    crazedwood

Leave a Reply