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 be. It could for example be better to pass around a mountain (which would be a longer path) than to go over it.

What you can find here, is an ActionScript 3 (AS3) implementation of A*. It’s primary goal is stability. It should be able to find the path on a 10×10 map as well as on a 1000×1000 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. It still uses v1.1, but it gives a good first look at what is possible.

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 (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)
  • Supports 3D


Download

Latest version
Version 1.3.1

Beta
Version 1.4

Older versions
Version 1.3
Version 1.2
Version 1.1
Version 1.0

Documentation

I’ve created a few pages with some examples and of course there’s also ASDoc documentation. If you think something is unclear or if you want some more examples, just send me an email (or comment) and I’ll update these pages.

The ASDoc documentation is available both online and as a download:
Online
Download

Changelog

V1.1

  • Added AstarPath.toArray();

V1.2

  • Fixed some memory leaks thanks to Mario Benedek

V1.3
I forgot to write down every single change, so I’ll list the biggest changes. Please see the documentation for more information.

  • Analyzers can now be added to a PathRequest
  • Moved heuristic to IMap
  • Moved goal condition to PathRequest
  • Added Astar.safety, Astar.NORMAL_CHECK, Astar.NO_CHECK
  • Moved classes and packages around
  • Removed Analyzer.implementsInterface()
  • Added a static map option. See the Astar constructor for more information

V.1.3.1

  • Fixed a bug in the basic2d.Map class.

Planned

  • Add cooperative searching (multiple agents that are aware of each other)

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. How I understand this license, is that you can use this library in any project you want (including commercial), as long as you keep the copyright notice in the files intact. You also can’t sue me if anything goes wrong ;).

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

106 Responses to “A* (Astar)”


  1. 1 Dauntless

    If you want to implement path-finding, you have to have points on your map that you can use to navigate. In my A* example/implementation every tile in a 2D grid is a point. In navigation software, every ramp, crossroads, freeway exit, etc is a point.

    Then you need information about those points. Fe: What is the cost of going from point A to point B?

    If you’ve got that, you could actually use my classes. (Although I don’t think your professor would like that?) You would have to override the Map class to be able to get the correct neighbors and you would have to hack DataTile.as to get a proper H. (I should really improve my implementation…)

    By the way, if you really want to implement some sort of navigation throughout fe a country, you would use 2 pathfinding algorithms: One to do high level pathfinding (going from city to city) and one to do low level pathfinding (navigating in the cities itself)

  2. 2 James

    ahh ok sir.. we cud use low level path finding then.. does google maps include the costs of every point in a map? thank u so much

  3. 3 Dauntless

    I doubt it. But if your professor says you can do it, there will probably be a way.

  4. 4 Konrad

    Can you tell how your algoritm behave withing a grid graph of size 500×500? It takes about 5 seconds from the very first node to last. I would like to compare it. Can you please extend your demo application with setting grid graph feature?

  5. 5 Konrad

    Can you please extend your demo to change total grid size?

  6. 6 James

    ok sir.. thank u so mch.. god bless..

  7. 7 suraj

    how can i define a unwalkabale tile??

  8. 8 Dauntless

    The BasicTile class has a third argument in its constructor that does exactly that. See the example above for an… example πŸ˜‰

  9. 9 wyemun

    i noticed that when :
    AstarPath.toArray(), it is not an numeric indexed array, rather a string+associative array like such:

    astarpath[“1”] = …
    astarpath[“2”] = …
    astarpath[“3”] = …

    rather than
    astarpath[1] = …
    astarpath[2] = …
    astarpath[3] = …

    other than that, good job!

  10. 10 Josh

    You should also implement space-time A*. I’m new to this aspect of game design or else I’d do it myself. I think a lot of people would use it, I know I would. This would be ideal for RTS games, or maps with a lot of units moving about. I’d even donate to see this done πŸ˜‰

  11. 11 Dauntless

    Hi Josh,

    Thanks for the suggestion and the information you sent me.

    I’m pretty busy right now, but I’ll take a look at it when some time frees up.

    Jeroen

  12. 12 Ivan Andonov

    I needed hex grid and your sample helped me alot.
    Here how i do it.
    (there is a minor performance change when adding the neighbours)

    [code]
    package com.dauntless.astar {

    import flash.geom.Point;

    import com.dauntless.astar.*;

    public class MapHex extends Map {

    public function MapHex(width:Number, height:Number) {
    super(width, height);
    };

    override public function getNeighbours(position:Point):Array {
    var x:Number = position.x;
    var y:Number = position.y;

    var neighbours:Array = new Array();

    addNeighbour(new Point(x-1, y), neighbours);
    addNeighbour(new Point(x+1, y), neighbours);

    addNeighbour(new Point(x, y-1), neighbours);
    addNeighbour(new Point(x, y+1), neighbours);

    if(y % 2 == 0) {
    addNeighbour(new Point(x-1, y-1), neighbours);
    addNeighbour(new Point(x-1, y+1), neighbours);
    } else {
    addNeighbour(new Point(x+1, y-1), neighbours);
    addNeighbour(new Point(x+1, y+1), neighbours);
    }

    return neighbours;
    };

    override public function isDiagonal(from:Point, to:Point):Boolean {
    return from.y != to.y;
    };

    private function addNeighbour(neighbour:Point, neighbours:Array):void {
    var tile:IPositionTile = getTileAt(neighbour);
    if (tile != null) {
    neighbours.push(tile);
    }
    };

    };

    };

    // there is a small change in Astar.as as well
    // replacing
    _map = new Map(this._currentRequest.getMap().getWidth(), this._currentRequest.getMap().getHeight());
    // with
    var MapClass:Object = getDefinitionByName(getQualifiedClassName(this._currentRequest.getMap()));
    _map = new MapClass(this._currentRequest.getMap().getWidth(), this._currentRequest.getMap().getHeight());
    [/code]

  13. 13 Dauntless

    Thanks Ivan! I’ll take a look at it when I have some spare time.

    I also think I changed that last part (getDefByName) in the latest internal.

    For those who are interested: I’m working on making it 3D compatible which turns out to be a little more tricky than I thought.

  14. 14 Ivan Andonov

    I did complete it and here you can see the working demo:
    http://iconcept.bg/HexGrid.htm

  15. 15 iMain

    Hey,
    Thanks for great implementation,

    How to find a way in map with the obstacles as with WalkableAnalyzer but without the diagonals in the ways?

  16. 16 iMain

    need to add new analyzer.
    thanks!

  17. 17 Alexis

    Very nice work Dauntless, I found the post on Kirpua forums for 2005. It’s great to find it here in AS3. I’ve been looking at Tonypa’s AS1 A* code and converting it πŸ™‚

  18. 18 Jclaine

    Love the work, but I did notice that with the cost analyzer that even if all the values are the same, if it is over 1 it requires a significant amount calculation. I haven’t dug to the code yet to see if this is fixable yet. You can recreate in your example by setting all the tiles to 100 and watch the MS go up.

  19. 19 keulu

    Hi ! i’m very impressive by your works. really nice πŸ˜‰

    But i try to use waypoints on my project with this pathfinding and i don’t succeed.

    does anybody can help me ?

    i try to go A to C via B.

    thanks a lot.

    a good job again πŸ˜‰

    (sorry for my English, I’m french ^^)

  20. 20 Dauntless

    Bonsoir Keulu!

    The easiest way to do that is to just calculate a path from A to B and then from B to C. Is there a reason why you can’t do it like that?

  21. 21 keulu

    waaahhhhh. speedy answer ^^

    not at all, it was just to see if it was possible to do so.
    I suspected it was going to end up like that.

    thanks and good job again πŸ˜‰

  22. 22 Dauntless

    You’re welcome πŸ™‚

    By the way, I’ve got v1.3 ready to release. I’m finishing up the documentation & creating some demo’s, so be sure to check back here soon!

  23. 23 Jclaine

    Looking forward to implementing v1.3, might I suggest that you swap out the math.abs() for a bitwise operation? IE i = (x ^ (x >> 31)) – (x >> 31); (code from http://lab.polygonal.de/2007/05/10/bitwise-gems-fast-integer-math/)

  24. 24 Alexander

    Hi, I can’t get how to make tiles unwalkable. Maybe I’m doing something wrong? =)

    So, here’s how I’m using your system:

    1. creating new Astar instance
    2. making new Map
    3. filling map with BasicTile –
    y x loops here {
    var des:Boolean (random true or false here for a test)
    var bt:BasicTile = new BasicTile(1,new Point(x, y),des);
    myMap.setTile(bt);
    }
    4. creating new PathRequest
    5. adding AstarEvent listener to Astar instance
    6. using getPath on Astar instance
    7. catching a path

    everything works fine, but path is ignoring unwalkable tiles =(

  25. 25 Dauntless

    Hi Alexander,

    I was updating the documentation for v1.3 and I accidentally removed the documentation for v1.2 and I don’t have a backup. This page was way longer with an example of how you should use the analyzers.

    Answer: you have to add the WalkableAnalyzer: astar.addAnalyzer(new WalkableAnalyzer());

  26. 26 Alexander

    Thanks, now I think I’ve got how it all works together πŸ™‚
    (You are responding so fast %)

  27. 27 Joeri

    Looking good, will try it out.
    The thing is that I have a 3d terrain, with uphill and downhill.
    Does your A* handle that as well?
    Not sure how to define a height map for it.

    I guess I better read the docs first.
    Thanks.

  28. 28 Dauntless

    Hi Joeri,

    I didn’t notice your post, sorry for that. In case you’re still wondering (or anyone else), it should support full 3D. You can have bridges, gravity, inclines, etc. If your map doesn’t have bridges or overhangs (ie, any place where there are multiple possible positions on one (x,y) location), you can use a regular 2D approach with a HeightAnalyzer (or similar).

  29. 29 drag0n

    great work!
    wondering if u have considered multi-points like point 1 to 2, 2 to 3, 3 ta 4, ect

  30. 30 Dauntless

    I dont really understand what you mean. Could you please ellaborate and/or give an example?

  31. 31 drag0n

    as in a tower defense having multipull points to go to. have staring point then 2 other points to get to and then go to the finish point, im guessing basically just running it to find best path between each point.

  32. 32 Dauntless

    If you want to hit them in a specific order, you can easily do this yourself. Every time you end up at a specific point, you just look up the path for the following point. This way your path will also be more up-to-date than if you calculate it at the start (and the user changes map while your enemies are walking)

    If you don’t care about the order and want them to just find the shortest path between all of the possibilities, you will have to calculate a path for each possible combination and compare the path lengths yourself. This is actually the same problem as the traveling salesman problem (http://en.wikipedia.org/wiki/Traveling_salesman_problem) and it’s considered a very hard (=time consuming) problem to solve. I would suggest you avoid it πŸ™‚

    A lot of tower defense games also use a fixed path (or a number of fixed paths and choose one at random), but that only works for TD games where you can only place your towers at fixed locations along the path.

    If you want any more advice, please tell me what kind of TD game you are building πŸ™‚

  33. 33 Electrolyte

    Hi,

    This is great! Thank you so much for sharing this.

    I have a question about the default walkable tiles, I would like to flip the data so that tiles in the mapdata of ‘0’ are considered walls and then number 1 upwards are walkable. Is this possible?

    I’m quite new to using classes and I’ve read though the documents but cant seem to find it, apologies if I’ve missed it. Any help would be great.

    Thank you again for some great code πŸ˜€

  34. 34 Dauntless

    The third argument of the BasicTile constructor is a boolean that tells the tile if it’s walkable or not. So in stead of doing this:

    map.setTile(new BasicTile(1, new Point(x, y), (dataMap[y][x]==0)));

    You could do this:

    map.setTile(new BasicTile(1, new Point(x, y), (dataMap[y][x]>0)));

  35. 35 Electrolyte

    Thank you! Sorry yes I worked that out in the end. Its a great function and have got it integrated into the game, works a treat. Will be putting you in credits πŸ˜€

  36. 36 Renofox

    This is exactly what I need for my game! I have managed to create a map and place walkable and nonwalkable tiles on it, but I’m stuck trying to create a PathRequest. Is it possible to get the code for the demo to see how it works?

  37. 37 Dauntless

    Hi Renofox,

    There’s a small example on the overview page (http://www.dauntless.be/astar/overview/). I could give you the source for the demo, but it’s written with v1.0 and the library has changed a lot since then. It’s also pretty much hacked together so it would just get really confusing.

    I also intended to add a few demo’s to the .rar, but apparently I forgot/misplaced them.

  38. 38 eKimiya

    Hi !
    I think there is a problem with your Map class. The function calcIndex doesn’t seems to work if you use it with a map witch is
    longer than wide…

    Anyway, it’s a great job !!

    See ya

  39. 39 bruceb

    hey first thanks for your time and effort on this!

    I’m getting stack overflow errors… no idea what’s really going on but here’s what I”m doing:

    I have a maze, and I need to find (any) two tiles that have a path length that’s between two values

    so I choose two tiles at random, loop on astar.getPath() till a path is found that has right number of steps, then I break

    sometimes this happens in maybe 5 iterations, sometimes more. when it takes more than maybe 10 iterations it blows up w/ a stack overflow error

    here by iterations I mean iterations of my loop, not the iterations internal to your A* classes

    thoughts? suggestions? thanks

  40. 40 Dauntless

    Hi Bruce,

    I think that’s a really inefficient way of finding the right tiles!

    A better way would be to maybe choose one random tile and have A* search until a path with the correct length is available. If you implement the IMap.getHeuristic function so that it always returns 0, you have a Breadth-first search that expands in all directions equally fast.

    You can’t use the PathRequest.isTarget method since you don’t have any information about the path there, only the tile.

    If you give me some more information, I can probably help you hack it together (= making a few private methods/properties public). What does your map look like? Is it just a binary map (walkable/non-walkable) or are there also costs involved?

    And what’s the overall idea behind your problem? It seems like this is a sub problem of a bigger problem that could maybe be handled differently?

    If you want to keep some information private, you can always email me using the contact form πŸ™‚

  41. 41 Niclas

    Hey!

    Awesome work! Works really well!

    Thanks a lot!

  42. 42 kevin

    Hi Bruce,
    There were some problem in my program.I wrote the code like the example which you wrote.But even that the data of map were all allow through,When i want get the path for any two point.That were warning me “path was no found”,I can’t find the reason.

  43. 43 Dauntless

    Hi Kevin,

    Are you addressing me, or Bruce?

    If you can’t make it work, feel free to e-mail me your test project.

    Jeroen

  44. 44 Martin

    I encounter a problem; don’t know where it comes from exactly (it may be misconfiguration on my side, or some kind of problem in the framework)

    it happens in the following scenario:

    I have a initialized map 160×160 grid units;
    I click on a grid unit that is walkable; but it is all surrounded by unwalkable grid units;

    it then generates huge amount of iterations because I receive lag and path not found after 5-6 seconds.

    I think this happens because the algorithm can’t figure out the tile is all blocked and it tries to iterate over the whole map to find a way to it.

    Please give feedback πŸ™‚

    Thank you

  45. 45 Dauntless

    Hi Martin,

    You’re right that the current library can’t recognize this situation. A solution to this would be to have two A* instances running side by side (one going from start to end and one going from end to start) where you would stop the other instance if one instance can’t find a path. I don’t think the current implementation supports stopping calculations halfway, so I’d have to look into that. When I find some time, I’ll see if I can fix something up to help in your situation :).

  1. 1 newb.to.pro(grammer) » A*Star Pathfinding
  2. 2 PathFinder A* | howdoflash
  3. 3 Polygonal map generation and pathfinding | Wired Vagrant
  4. 4 Find a path from point A to B in X steps. (A* ish) | Software development support, software risk,bugs for bugs, risk analysis,
  5. 5 Optimization – Choosing the right algorithm - selene tan

Leave a Reply

*