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.
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.
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
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.
- Added AstarPath.toArray();
- Fixed some memory leaks thanks to Mario Benedek
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
- Fixed a bug in the basic2d.Map class.
- Add cooperative searching (multiple agents that are aware of each other)
No bugs so far, but if you do find one, please let me know! Feature requests are also appreciated.
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 ;).
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