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!

[Ihoss]

let me get this straight. it finds all paths and stores them in somoe sort of array, and then at runtime it just looks them up in the array?

edit: and do u need to calculate the path before each movement, or could the paths be saved as an array and u only needed to look into it? that is if the map doesent change...

[webgeek]

it finds all paths and stores them in somoe sort of array, and then at runtime it just looks them up in the array?

Yes, thats right.

do u need to calculate the path before each movement

No, you need to calculate the path only once. As soon as you finish designing the map, you can calculate it once and no one ever has to calculate it again.

u only needed to look into it? that is if the map doesent change...

That's how it works. Go ahead and get to the final step. Lay down a start and end position, find the path. Then click on the start or end position and move it (just click on it to make it go away, click again to set it down somewhere else) you can do that all day long without recalculating. That's the whole point

This is a cleaned up version of the same tool I used to solve the attached map. In the Flash IDE, it took only 10 milliseconds to walk the entire path. Have fun!

Edit: Doh! It didn't save the attachment, here it is...

[Ihoss]

so the array, is it 2 dimensional then? like:

path[x+":"+y][x2+":"+y2] where the first is the starting position and the second is the ending position, and then the value of that is all the cells it has to pass throught?

[webgeek]

Nah, it's a little trickier then that. Once the array is populated properly, you use it something like this:

walkPath = new Array();
currentPosition = startingPosition;
while(true) {
     newPosition = pathArray[currentPosition][endingPosition];
     if(newPosition == endingPosition) {
          break;
     }
     walkPath.push(newPosition);
     currentPosition = newPosition;
}
// All done, start walking the walkPath

As for populating the array, that will have to wait till the article is done.

[Ihoss]

so pathArray[currentPosition][endingPosition]=nextDirection?
wouldnt a 3d array also work, where the first two r like urs and the last one is the cells it has to pass.

(i hope ur getting that im trying to get u to reveale a little bit before the article is done )

[webgeek]

Not nextDirection, but the next tile you need to go to. The trick is that the array contains data you have to loop over an unknown number of times to get your final path. You couldn't realistically store every single path in an array as we are talking about a LOT of them. By using a 100% accurate pathfinding engine (Dijkstras in this case) then you only need to store what the next correct step should be. Make sense?

This way you are storing only gridWidth * gridHeight total pieces of data. You just use a simple algorithm to build any given path at runtime. All the hard work is done for you. In a 25x25 sized grid, you are storing 625*625 total entries (~390k). You are trading off memory usage for CPU load. For performance reasons, I keep these as raw numbers rather then a object references. It works great and is very fast and simple to implement once you get the array building properly.

The way to reduce memory load is to simply use many grids of different sizes laid on top of each other. This allows you to use small grids to get to waypoints of bigger grids.

Edit: BAD mistake on the numbers, sorry.

[Ihoss]

aha, i get it.

but creating the array means u have to go through every path possible, right?

code:

---

for(i=0;i<_root.width;i++){

for(p=0;p<_root.height;i++){

if(_root.map[i][p]=="0"){//not a wall

//some stuff i cant come up with at the moment but will probalby 

//be cleare when u make ur tutorial.

}

}

}

---

[webgeek]

Yes, that's the precalculation part that takes the longest but only has to be done once. You don't code it the way you have it though, it's not solved by simply looping over all the nodes.

[Ihoss]

oh, ok. ill wait for the article then. give me a pm when its finished

[Mad-Sci]

oooo excellent...very good this realy got me inspired let me post my pathfind..

how about if the end point moves ?

ms

[webgeek]

Thanks. To answer your question, the entire path is found for you before you even start moving. If the endpoint moved before you got to it, you would simply run the path again. It's so fast, it wouldn't matter. I probably ought to update the demo so you can drag the endpoint around to illustrate that.

[RipX]

A good idea would be to output the array and then save it in a txt file, load it into your game on the relavant level and the array would be ready o use already without needing to compile on the users machine!!

RipX

[webgeek]

Yup, that's the basic idea of how it should be used. Ideally a map will be either a SWF file or an XML document. Either way, you could use this to generate your pathfinding data beforehand.

[PMX]

Wow your Engine is Great i hope you will release the tutorial and maybe the source file this week!

man great work!

i looking forward to it!

thanks

[lapo73]

Originally posted by RipX
A good idea would be to output the array and then save it in a txt file, load it into your game on the relavant level and the array would be ready o use already without needing to compile on the users machine!!

RipX

If for a 25x25 grid you get roughly 390kb of data I don't know if it would be that great to have it as an external file...
Maybe it could work wonders for standalone games but downloading nearly 400kb of data at every level change does not sound good to me

[webgeek]

downloading nearly 400kb of data at every level change does not sound good to me

That's 390k of RAW data. It will compress down pretty dramatically.

This is where things get tricky. No single pathfinding solution is perfect. This one is a direct compromise of memory in exchange for CPU performance. But if you were to use this along with some others, you have a very real and workable solution. This technique is not actually designed to be used on a grid at all, it's actually designed for open terrain where the number of nodes can be dramatically reduced. I put it on a grid to just show what can be done. I have another example where you simply place nodes and it can tell you the fastest route between them.

So if you have a nice pretty game (tile-based or otherwise) you could use this technique to help people find their way down long twisty halls and between rooms, and you could use robust pathfinding to get you to the nearest node. Make sense? This is what a lot of commercial games do. So from room to room could use this (long paths that would rape most pathfinders) then use the real-time pathfinders like A*, etc. for the intra-room stuff.

[ArrowFlash]

definately finish it up asap, would love to see it.

[tonypa]

Originally posted by webgeek
Here is an example of pathfinding in Flash that is quite quick. It uses Dijkstra's Algorithm to precompute perfect paths and then stores them in a clever format using a 2d array.

May I ask why you use Dijkstra's Algorithm? Unless the different terrains with different times to cross them, exist, I dont see how that would be better then Breadth-first search.

I still dont understand what information is saved in the 2d array. Paths from any point to any other point? Allowed directions from one tile to its neighbour tiles?

[webgeek]

Any search algorithm that returns perfect paths (as in the guaranteed shortest path) from point a to point b could be used. I just happened to have an implementation of Dijkstra's algorithm from Brandon Hall's book so I used it.

Lots of people have asked about the array so I will try and make it more clear. The basic idea is that you find the path from node a to all other nodes on the map. Then you store the first step of each of those nodes in the array. Then you do the same for node b and so on through all nodes in the map. All of this occurs during the pre-computation step. This is the ONLY place that the "real" searching algorithm is used.

Lets do a real example. If I have a map that is 1x4 tiles and looks like this:

_________________
|   |   |   |   |
| 1 | 2 | 3 | 4 |
|   |   |   |   |
-----------------

Then the to break down the paths, I could say that:

starting --> destination = next step
1 --> 1 = 1
1 --> 2 = 2
1 --> 3 = 2
1 --> 4 = 2
2 --> 1 = 1
2 --> 2 = 2
2 --> 3 = 3
2 --> 4 = 3
3 --> 1 = 2
3 --> 2 = 2
3 --> 2 = 3
3 --> 4 = 4
4 --> 1 = 3
4 --> 2 = 3
4 --> 3 = 3
4 --> 4 = 4

Now, if you think about it, you could store that in an array in just that format. In fact, thats exactly what you do...

pathArray[start][destination] = nextStep

Then, when you want to do your actual search at runtime, you need only loop over that array and find the next step. You keep repeating that process by replacing the starting point as the next step. Each loop gets you one node closer to your goal until starting and destination are equal. All that make sense? It's really not that complicated, but it's a different way to think about it. Like I said in my first post; I dont get credit for coming up with it I just implemented it in Flash to see how it would do. Thanks!

P.S. The really clever of you out there might have noticed that the engine DOES support one way paths. So from 1 --> 4 = 2, 3, 4 but 4 --> 1 might involve a completely different path.