Fast Flash Pathfinding Example

[webgeek]

Hi all. As promised, (although VERY late, sorry about that) here is an example of pathfinding in Flash that is quite quick. It uses Dijkstra's Algorithm to precompute perfect paths (no heuristic guesses are allowed with this trick) and then stores them in a clever format using a 2d array. The main idea came from "AI Game Programming Wisdom", chapter 4.2: Preprocessed Solution for Open Terrain Navigation by Smith Surasmith. I simply changed it to support grid-based paths as opposed to open terrain you get in lots of 3d games.

The basic concept is that for most applications real-time pathfinding is unnecessary. You designed your maps manually and they don't change everytime someone plays so why not just include your pathfinding information inside of them and save everyone the CPU time. That's the basic idea of this sample.

Here it is:
http://www.electrotank.com/junk/mike...hTutorial.html

It's still a bit buggy but not too bad. The precomputation code is TERRIBLE, which is why precomputing takes so much longer then it should. Basically, it works expontentially harder then it needs to and the bigger the map the worse it is. This could be corrected if I were to write my own Dijkstra implementation (I'm using Brandon Hall's from his OO book). His is very good, but not designed for the way I'm using it. As this is just a prototype, I'm not concerned about that and don't really plan on correcting it. Also, this is all MX, in 2004, it would be much faster.

If someone were to use this in a game (not this version, but their own) you would just need to save the 2d array of paths (which is always sized at array[numtiles][numtiles]) in some format where you could load it back in. I have another program that will actually generate actionscript code you can cut and paste for a given map. I used it as a test before I even wrote this one to see if the idea was valid.

Anyways, I have a big tutorial on how all this works and if people are interested in this little sample application, I can finish up the tutorial this week. Please let me know though, otherwise it might wait on the back-burner indefinately. Thanks!