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.

  • 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!

  • awesome – i have only read jobe makars book about ai so this is a great reference to go with it

    thanks a lot

  • mrclay

    Why is it impossible to go just under the anchor (the one which is on the top left of the map)?

  • zeh

    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.

  • José A. Chacón

    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?

  • Great job 🙂

  • Respect……very nice and intelligible

    thanks, good luck

  • Futile

    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).

  • Zeh

    Futile: good find. You’re right. I set that tile to ‘block’, so it works like water instead. 😛

  • putra

    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

  • Zeh

    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.

  • 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

  • tepan

    sorry, i have a problem to apply your code in flash 8
    could you give me a .fla file?
    thank you very much ^^