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 Martin

    Thank you 🙂

    It is actually not a huge problem for me, because it occurs very rarely. However it may be good addition to your framework 🙂

  2. 2 Martin

    Regarding the situation I mentioned in the previous post – I now believe it is some kind of failure in either the algorithm, or the implementation.

    Imagine a map, of some size, where there is some tile that is walkable, and it is all surrounded by occupied tiles. Something like this:

    1 1 1 1 1 1 1
    1 • • • 1 1 1
    1 • 1 • 1 1 1
    1 • • • 1 1 1
    1 1 1 1 1 1 1
    etc..

    where dots are occupied tiles and ones are walkable (free) tiles.
    Guess a scenario where you click on the free tile that is all surrounded by occupied tiles. In a normal scenario, the algorithm would reach the dots, surround all of them and conclude that it cannot shorten the distance to the destination any more. In that case it should fire path not found. Instead, I suspect the framework to continue the search algorithm and expand throughout all the map which causes big amount of unnecessary iterations until all the edges of the map are reached. I don’t know if this problem is by design of the algorithm, or a problem in the implementation. Please take a look…

    Best regards,
    Martin

  3. 3 Dauntless

    Hi Martin,

    A* will indeed continue searching the entire map. There is no mechanism that detects if a certain tile is unreachable. In this current implementation, you can dismiss the heuristic (so A* becomes breadth-first) and add ‘teleport tiles’ to your map. That way, it would be pretty hard to decide if a certain tile is unreachable.

    It would of course be possible to add a check to see if the immediate neighbors of the target tile have all been visited, but if the tile is on a little island, it’s still unreachable, and its immediate neighbors will never be visited.

    Like I said, the only “good” way to fix is is to start two astar intances and have them go toward each other. However, a bidirectional search often has the problem that the two search paths miss each other all together and you end up calculating the path twice (and end up with two equally valid paths)

    Depending on your game, you can maybe find a few optimizations yourself. If the islands are fixed, you could perform a flood-fill on a few tiles so that you know which tiles can be generally reached, and which can not. If your map only changes sporadically, you could still use this technique (maybe even using bitmap operations for a faster flood-fill). If you are certain that you will never have a situation where you would have to first move further away from the target in order to get closer, you could probably add a check for that and stop the algorithm if this happens. A possible situation where you have to move further away before getting closer is of course when you have to move around a wall or something.

  4. 4 Martin

    Understood. As I said it’s not a big issue. I notice another strange thing however. Sometimes, when pathfinding is initiated, even for very simple routes (that would result in 4-5 tiles path found) I get the very same thing – lag and 5-6 seconds of delay. Very strange, since the destination is very near and it is supposed to be resolved very quickly. If you don’t mind I could send you a link to the demo of the game so that you can see yourself what the issue is…

  5. 5 Dauntless

    Sure, you can send me a link to the demo. And preferably a situation where you get the delay (if you can reproduce it?)

  6. 6 Martin

    I sent you a personal message. Thank you

  7. 7 clement

    Where can I find an example with height tiles? ( hills & valleys )
    I’ve been through the doc but can’t understand how to implement that…

  8. 8 Dauntless

    What exactly are you looking for? There’s a HeightAnalyzer in be.dauntless.astar.basic2d.analyzers. That analyzer can make sure your path wont go above a certain height or below a certain height. It can also make sure that there’s a max (or min) difference between the current tile and the next tile. (Fe: Your hero can only jump 3 high, so maxDiff should be 3).

    For this to work, your tiles need to implement the IHeightTile, which just makes sure that each tile has a certain height.

  9. 9 Mateusz

    Hi. I wonder if there is a way to implemetacje methods Jump Point Search for your library.

  10. 10 Kuba

    Hey! I’m trying to implement your code to a game, but it works only once – i click on the destination, hero reaches is and when i click again it responses with “Path not found”. It finds path again only if i click on hero’s location. Do you know why it happens?

  11. 11 Dauntless

    Hi Kuba,

    Could you post some code? (Preferably on a site such as pastebin?) Or you can email it to me at jeroen@.be. (But please only include the relevant code)

  12. 12 Kuba

    I’ve sent it to you. I’m looking forward for your response.

  1. 1 길찾기 알고리즘 :: A*(star)
  2. 2 Thoughts on Pathfinding – 实现(上) | Forever Loop.

Leave a Reply

*