Mar
30
A* pathfinding
Filed Under AS3, Demo, Flash & Flex
Path-finding is really an interesting topic and luckily there is loads of information available on the Internet. Implementing the algorithm, however, is a different thing. Don’t get me wrong. The algorithm itself is pretty easy to digest. Making it fast and efficient is a bit harder. That would involve advanced data structures,  some pre calculations and probably more. Anyway, here’s what I managed to put together. It uses Vector class so FP10 is needed.
Notes about the settings
Map mode:
In this mode you can modify the tiles. White tile equals to “walkable“. Click on a tile to toggle its state.
Path mode:
In this mode you can select the starting and ending points of the path.
Use Manhattan method:
Manhattan method is a fast (thus more inaccurate) method for calculating the distance between two points. It is the total number of squares moved horizontally and vertically to reach the target square from the current square, ignoring diagonal movement and any obstacles that may be in the way. If this option is unchecked Euclidean Method will be used instead. It is slower but better.
Use diagonal paths:
Using diagonal paths increases the calculation time but results in “more realistic paths”.
Allow cutting corners:
This is probably not acceptable in most cases. If diagonal paths are disabled this setting will have no effect.
SOURCE FILES: astar
Useful links:
- A* Path-finding for Beginners
If you are new to Astar this is the place to start with.
- Amit’s A* Pages
More advanced and in depth information on A*
Comments
3 comments to “A* pathfinding”
Leave a comment
Some Rights Reserved
Nice Work!
The paths are very accurate. I’ve ported baseoneonline.com’s A* code to haXe to test any speed improvements.
I think i’ll update my tests and port your code, since yours is more accurate than my examples.
yours is showing an average of 40ms
while my haXe example is 0-4ms
http://remixtechnology.com/view/AStar-haXe
The source file is not loading properly.
I found the following errors
1084: Syntax error: expecting identifier before lessthan.
Hey nice work, but what’s Array2?