Fast Flash Pathfinding Example

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!

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

Quote:

---

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.

Quote:

---

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.

Quote:

---

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

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?

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

Code:

---

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.

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

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.

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.

}

}

}

---

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.

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

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

how about if the end point moves ?

ms

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.

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

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.

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

Quote:

---

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 :eek: does not sound good to me

Quote:

---

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.

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

Quote:

---

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?

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:

Code:

---

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

hey there,cool stuff,congrats :)
sorry for the rather short feedback but i just came home after a 12 work day (deadline stress..),will look into it longer on weekend =).
you mind if i add the thingy in my editor?

Thanks, I'm glad you like it. I recommend the "AI Game Programming Wisdom" book to anyone trying to do this sort of thing.

You said:

Quote:

---

you mind if i add the thingy in my editor?

---

What editor? I'm sure it would be ok, I'm just curious. Thanks!

i already read several threads,articles and books (also) discussing pathfinding but thanks for the mention,i think i´ll order that one too =)

the ed is v3 of my tile ed,it features (multilayer) topdwon and iso map creation and has drawing tools for drawing (filled)rectangles/lines and circles of tiles and importing tilesets.
you can also load and save the mapoutput in any filetype (hence its a standalone app).

Sure you can add it into the editor. Send me an email and I can hook you up with what you need. Thanks!

Thank you for explaining the saved paths array. Thats very clever :)

Now I understand what you mean by saying the calculation of paths can take long time (I know, its not real-time, only has to be done once), you find every single path from every tile to all the other tiles.

I wonder if its worth to divide map into grids, lets say 3x3 tiles and only save the paths array for each grids center tile. This could reduce the amount of memory (size of the game) quite a lot.

this sounds so cool webgeek! I cant wait to see the article!

Quote:

---

Originally posted by webgeek
Sure you can add it into the editor. Send me an email and I can hook you up with what you need. Thanks!

---

coolies,thanks,i´ll do that (but i won´t have time to get into it before weekend).
i discussed using run length encoding for the map data with pred recently,we haven´t implemented it for the mapdata yet (as our maps aren´t that big and i had to do other parts of the ed first),but wouldn´t it be possible to use run length encoding on the generated pathdata so that it shrinks dramatically in filesize?

Yup, that would work perfectly :) I can't tell you how much effeciency it would gain though as I don't know how many repeats would come up. Thanks!

Is this article still around?

Sounds like what I am looking for....

Was the source ever released for this?

Sorry for diging up an old thread :(

This is just amazing ^^ So incredibly fast. :O

So what you actually save in your precomputed array - is that the list of "parents" you get when running dijkstra's algorithm?

( For each node; you go through the whole list of nodes and gather information and saving this info in an array - like cost, and previous node (or parent node). Is this what you're saving? :P )

Please excuse my crappy english.. : P

I'm sorry, I don't quite understand the question? :(

haha, sorry, I don't completly understand what I wrote either..

But you said that your array looked something like this
path[currentPosition][endingPosition] = {x: x, y: y};

Well, how do you populate this array? I mean how does the precalculation work?
When you use for instance dijkstra's algorithm (isn't that the one you use?) you cycle through every node and sets its previousNode = currentNode..
So when you've found the path you'd have an huge array with all the nodes' previousNodes. Using these you can backtrack to the starting node and thus get your path, right?

And this is the very same array that you save If I've understood it right. It should be... :/
(of course you'd have to repeat this whole proccess for every node)

Haha, sorry, not sure if I'm making myself any clearer.. It's actually a stupid question, I'll go experiment a bit and hopefully I'll find out on my own ^^

Quote:

---

Originally posted by webgeek
That's 390k of RAW data. It will compress down pretty dramatically.

---

Very sorry for bringing up a very old thread, but can you explain what you mean here? Is there some way to compress the data to something smaller than 390k but still make it usable for Flash ?

Thank you

Cool, but wouldn't it be faster using a 1 dimensional array instead? I guess its not :).


EDIT:

Woohoo it is faster :D

here the proof:
http://www.flashdev.ch.vu/tutorials/...e/twotoone.zip

Quote:

---

Originally posted by LeechmasterB
Cool, but wouldn't it be faster using a 1 dimensional array instead? I guess its not :).

---

edit:

The more optimized things are the better it is.
So my answer would be no :D, if you really ask for it. If you make big games, every ms can count. Because if you have lots of things that take 10 ms it gets slower too.
Using a 1 dimensional array is almost double as fast on small arrays (50-100x50-100 elements). And still faster using big arrays 1000x1000).

This works out great if the path can't be blocked. What if you have more than one object and the second object is blocking the other's way? Do you have to save ALL possible paths to get from one tile to another? I suppose a way around this is to implement a standard A* procedure that you can fall back on in this situation, but is there a different way you had in mind in this case?

I've gone ahead and updated the link to the tutorial in the first post. You can click this too if you want:
http://www.electrotank.com/junk/mike...hTutorial.html

LeechmasterB: Using 1 array might be a way to make it slightly faster (going from 5ms to like 3) but to be honest, the drop in readablity and the complexity increase in array creation doesn't really warrant the change unless you REALLY need it. This is a perfect example of premature optimization. Don't dirty things up to make things faster when you don't know if this is the problem in the first place. It's best to make it, then make it work, then make it work fast.

Plecostomus: This technique only works for STATIC maps. It's not designed to be used with dynamic maps. As such, it simply gives the shortest path. It's designed to not care if there are 10 other ways to get there, it only saves the absolute shortest. If there is no way from A to B, it will simply return nothing. Currently that's a bug in my example I never got around to fixing. I'm not sure if that answers your question though, so please let me know if I missed your point.

Yes, this did answer my question. I was hoping this technique was applicable in project, but do to this fallback it is not. Thanks anyways.

It sounds like you simply need to use something like A*. It's terrain aware, flexible and pretty fast. Jobe Makar's game books have an excellent A* implementation.