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:
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
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) > 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
great stuff you made man!!!
so if I understand the MIT licence correctly I can use it?
i’ll be sure to credit you
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.
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!
Thank you for such an extensible implementation! I’ve never seen one quite so useful before. I appreciate it!
Thanks Aaron
. “Be sure to tell your friends” 
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
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!
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
. 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
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!
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 =)
Hi DooM McQ,
You’re right, something went wrong there … I’ve edited the code and it should work now.
Thanks for reporting!
great job,
hi.
how can i use Hex map?
is any body know?
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
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.
Many thanks!
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 !
The example gives some errors trying to compile?
http://yfrog.com/3oerrorxpdj
Ah nevermind I see already.. the code blocks are not working.. it converts html entities
hi,
I see the demo,so good.can I get the demo source? I think its help for me. my English is so bad,
,My mail:c.sx@hotmail.com. many tks.
crazedwood
Really nice implementation.
Maybe you can guide me.
I’m trying to add an analyser that would prefer straight line even if it’s cost a little more. I already changed the diagonal const to avoid diagonal move.
I was thinking maybe changing the cost in the map, but it didn’t seem right like the full proof approach.
ex:
map
1111E
11111
11111
S1111
should do
1111E
11110
11110
S0000
instead of
1110E
11001
10011
S0111
Thx in advance
Martin
Hi !
I’m looking for an algorithm that could allow to search for the closest tile when no path has been found. Does someone knows how this could be managed ?
Hello,
I have used your code and it was great help. I only thought it would be great if it can work with negative coordinates like x:-5,y-1.
Is there some easy way how to make it work with negative numbers?
Hi,
That would require some tweaking. Why do you need that exactly? It would probably be easier to create a mapping function that (fe) adds 1000 to every coordinate, hence making them positive.
Thanks for your reply!
I am trying to make MMO with huge maps. I am using negative values because I want to make sure I can expand maps in the future. So I am not limited to starting point 0,0 and can expand in both ways.
I am using negative values in all system, so I didnt thought about your solution (add +1000). But as map will be separated into smaller parts anyway, your solution will work I beleive
Shame I didnt thought about that, because in my solution I still added +13, but I had to recreate separate pathfinding map on every avatar move
So thank you for your tip, but you can still take it as suggestion for future release
! Also thank you for your AStar implementation, it saved me a lot of time!
Thanks a lot for the AStar. But I’m having troubles runing the example. I get this error:
C:\… .as:130: 1046: No se encontró el tipo o no es una constante en tiempo de compilación: AstarEvent.
Mmmh. Is really strange, because I imported the AstarEvent. Do you know what can be the problem?
Rod
I just tried it here and it worked.
Try recreating your project and maybe clear out your ASO cache.
You sir are a coding god.
Your implementation was the second I tried and it was far far better.
My map is approximately 1500 tiles and I am requesting 10 paths pretty much simultaneously.
No sweat at all! Thank you
Thanks for the compliments
Thank you so much! I tried implementing psuedocode from Wikipedia and several other tutorials to no avail. You really should have a donate button!
You’re welcome
. If you can’t help yourself, you can always donate on http://www.airdoc.be , one of my application sites.