Attention: you're visiting an archived version of this post on my old website. Click here to view this same post on my new website.
Flash pathfinding prototype
After all kinds of tweaking, I’ve finally finished a more or less fast and stable pathfinding algorithm in Flash. It’s a prototype (well, just a function in fact) in which you pass a map, a start point and an end point as parameters and it returns an array containing the best path between the two routes. It takes into consideration terrain costs (terrains that are “cheaper” to travel by) and, of course, walls and obstacles. You can find the function here, along with a syntax explanation.
I’ve always seen pathfinding as being one of the big secrets of gaming AI. I had more or less knowledge of how it was done, but never had to implement it fully. In this case, using a very simple yet complete explanation of an A* algorithm, I was able to build a working prototype (in the old meaning of the word) in no time with cute-looking squares, and after it was complete, decided to start another version from scratch using only arrays and objects and functions and such (and that’s the version which’s linked above). It’s one of those things that, after you actually finish it, you think it’s so simple you didn’t have to spend so much time thinking on how difficult it would be to create it.
I’ve also created a small example using a screenshot from Advance Wars, a popular GBA game and a small addiction of mine sometime ago. In this example, clicking a place on the map will trace the best route the soldier can use to reach that square, taking into consideration that terrains are hard to travel by, roads are easier, and forest or mountains are much more difficult. This background image was stolen from this site which hosts an Advance Wars map editor.
I’m still optimizing the pathfinding routines; actually I’ve managed to save 80% of the execution time on the past few internal versions of the function. Suggestions would be appreciated, though.
Comments (13)
this is a great app and will have many uses in the flash community as cell phones gain GPS abilities… your URL is on my list of developers to stay in touch with. thanks for sharing the ‘how to’ with us!… great work!
Posted by dave matthews on 16/Jul/2003 at 4:01 pm
awesome – i have only read jobe makars book about ai so this is a great reference to go with it
thanks a lot
Posted by overbyte on 7/Jun/2004 at 12:50 pm
Why is it impossible to go just under the anchor (the one which is on the top left of the map)?
Posted by mrclay on 17/Nov/2004 at 8:15 pm
mrclay: because I made the mistake of defining that square as being “impossible to go to” on my flash example. It has the same data of a water square (or a wall).
Thankfully, this is a mistake on the example data, not on the pathfinding prototype itself.
Posted by zeh on 18/Nov/2004 at 1:27 pm
Great!, is the first implementation of A* in flash I find in internet, I thought there wasn’t anybody else, I’ve actually coded the Basic A* using classes in ActionScript 2.0
do you know about others implementations of A* in flash over the web?
how many time did you spend making it?
Posted by José A. Chacón on 10/Feb/2005 at 10:00 am
Great job 🙂
Posted by Nick on 11/Apr/2005 at 4:11 pm
Respect……very nice and intelligible
thanks, good luck
Posted by zoltan on 10/Apr/2006 at 5:54 am
I believe there is an error in the map of you example. The demo can not find a path to the southeast city (the one between two ports at the bottom of the right island).
Posted by Futile on 6/Oct/2006 at 4:20 pm
Futile: good find. You’re right. I set that tile to ‘block’, so it works like water instead. 😛
Posted by Zeh on 6/Oct/2006 at 6:12 pm
have you ever seen real flash map that using a* algorithm?
ihave an idea to combine litle block area in flashearth with a* pathfinding algorithm? because i think its more complicated using if using a large map
Posted by putra on 3/Feb/2008 at 7:10 am
There are plenty of A* examples out there, in games.
But pathfinding is not just A*. There’s no “best solution” for pathfinding. Deciding the best approach depends on a plethora of different paramaters.
Real maps with waypoints – I think that’s what you mean with flashearth – have an approach similar to A*, in that you trace all possible ways until you find the one with shortest distance. But that is done using waypoints (and not grid points), and also taking the distance between waypoints (instead of standard distances) into consideration.
If instead you have a large map with no waypoints, you’ll have to look for other pathfinding solutions. Again, there are many alternatives; the correct solution depend on the specific parameters of the problem.
Posted by Zeh on 3/Feb/2008 at 8:28 am
great work! can i have some tutorials on how to make these? i’m currently making a GIS software using flash and this example would be of great help.
ym: phyreshit
Posted by jeffrey on 8/Jul/2008 at 8:12 pm
sorry, i have a problem to apply your code in flash 8
could you give me a .fla file?
thank you very much ^^
Posted by tepan on 10/Jul/2008 at 8:52 pm