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