[disc] which pathfinding algorithm?

hi,

I wanted to get some feedback on which pathfinding algorithms you're using.

I'd implemented a breadth-first pathfinder, based on Tonypa's comments on this thread, which I liked because of the simple way to count the number of steps taken. I used this in my rpg to see if the hero character was close enough to an NPC for it to react and move towards the hero.

I then implemented an A* algorithm (based on this code) for longer distances, but there is a visible delay while the path is calculated.

I was then reading another thread last night and someone said that Robust Tracing was the quickest to implement in flash.

any views/thoughts?

It all depends what kind of game are you making. Is it turn based or real time? Do you only need pathfinding for 1 char or are you having many chars moving around? Do you have different terrains with different movement points? Is it more important to get shortest path or any path will do?

Generally speaking, better pathfinding means slower game.

The best path is found by A* algorithm, but it is slow and you cant do much about it. This is also your only option if you have multiple terrain, like roads to move faster and swamps to slow you down.

For real time game with many chars moving A* might be too slow. You might need to reduce the amount of steps pathfinding will look for in each frame. Or create some super-tiles for large maps or even precalculate the paths and save them with the game. Even the big studious spend lots of time creating better pathfinding and reducing the time wasted.

Robust Tracing is good and simple algorithm, but it doesnt give you BEST path. It might choose the path, that looks stupid.

If you havent already, read the good article from gamasutra:
http://www.gamasutra.com/features/19990212/sm_01.htm
(try the PathDemo program from there so you can see yourself how different algorithms work).

the game I'm working on at the moment is a real-time rpg.
I'll have a lot of NPCs walking around a town, and I've pre-calculated the paths for these, but for the enemy soldiers, and the occassional NPC who I want to walk up to the hero, they will need to find paths. (so up to 5 or 6 pathfinders at once - or is this just too many?)

different terrain types won't be important, but I don't want to have a non-realistic path.

would a sequence of breadth-first searches over small areas be more efficient do you think?

You could make the enemies and NPC's to find the new path only after certain time has passed.

For 30 fps you could run the pathfinder only after 2 seconds have passed:

Frame 1: find path.
Frames 2...60: move along the path found, checking if hero is next to him.
Frame 61: find new path if hero has moved.
And so on.

yeah, that's a really helpful idea. At the moment I'm trying to pathfind all of them every frame, which, as you point out, isn't necessary.

just to compare the different paths generated/times taken, is there a good site with Robust Tracing theory (or even an open source flash code) available?

The theory you can look up from the gamasutra article I posted above. And you can compare the times with the program from there too.

But I havent seen any open source Flash examples with robust tracing.

Grant Skinner has a really fast opensource pathfinder, you can find it at http://www.gskinner.com/site1/ (look in the shortcuts at the bottom)

another
http://www.antimodal.com/astar/

The only open source robust tracing demo I've ever seen is found on Jobe Makar's Cd (the cd comes with the book) and it is made by Klas Kroon:D

Klas Kroon has a demo up on his site but that isn't open source.

I have used grantskinners pathfinder before, very easy to use and works a treat :) Infact, i think i will use an incarnation of it in felony for the police...

I couldnt remember the site though so i was waiting for someone else to mention it :) - cheers trickman.

I just want to share my new Pathfinder, which uses Agents to find the target. The new thought about it is to set a maximun time for each calculation step. So it won't delay your application and you have full control about your player performance.

It's written in AS2, but can be published in Flash6.

AndreMichelle - that sounds perfect. I'll have a look through that now.
Just an initial thought though - what happens if it runs out of time for the calculation - does it completely abandon the path, or does it return the most promising path it had found so far?

Tonypa - I went through the GamaSutra link, and also found some other pathfinding articles, so that's a great help

If you think about it, there are two high-level options for pathfinding; pre-computed or real-time. The type of the game should dictate which is the best option.

For a game where the map is static and doesn't change dramatically, then pre-computed paths can give you perfect results almost instantly. I have another thread here that discusses this concept and implementation in detail. Using MX (not 2004) on my machine, I was able to generate the path denoted by the orange line here in 10 milliseconds. I promised that I would finish up the tutorial soon, sorry that it's not done but real world stuff got in the way.

If the map changes a lot, then real-time is pretty much the only way to go. Jobe Makar's new game book has a VERY fast implementation of A* in it. I don't know if it's the fastest out there in Flash, but I do know that it's probably close. It's the most flexible and robust A* implementation I've seen in Flash as it has full support for multiple terrains, is fully OO, and is easy to implement in your own code. You could probably make it a touch faster if you were to make it less generic. He uses some tricks to reduce garbage collection and object churn too.

Personally, I feel the ideal solution for pathfinding in large-map Flash games can be reached with a technique using both run-time and pre-computed paths. This huge map here shows a path that was partially generated via pre-computation (the blue line) and partially via run-time (the green lines). If you were to couple this with a LOD-style AI (Level Of Detail), you could have your characters walking around in the background without sucking all your CPU pretty easily.

For reference, I BELIEVE it's the "AI Game Wisdom" book that has an article from BioWare about how they do pathfinding for all the thousands of characters in their "Never Winter Nights" game. It's LOD based and very clever. Basically, the distance from the main character dictates the "accuracy" of the walk path. They then switch from pre-computed to real-time as needed.

Feel free to let me know if you have any questions. Thanks!

AndreMichelle, that's super smooth. Two questions:

what exactly are Agents?
Does the maximun time for each calculation step compromise the time taken to find the path? I've just slotted in my aStar class to your file and it can cut about .35 ms off yours, but there is a noticable pause while finding the path? - http://www.token3.com/path.swf

Quote:

---

Just an initial thought though - what happens if it runs out of time for the calculation - does it completely abandon the path, or does it return the most promising path it had found so far?

---

The limitation on time is meant by each calculation step. If you watch the example swf, you can see, that the pathfinder needs more than the giving limitation. It continues the finding on the next onEnterFrame (in this example).

webgeek - I like the idea of combining pre-computed and realtime paths.

It would suit my game perfectly as the NPCs could move around the static buildings, going about their business, but then just making small detours that were generated in realtime as needed.

I'm been reading an interesting article on an interesting approach to precalculating paths at Gamedev, if it's a help to anyone else

andremichelle - I think I'm going to need some time to go through your code properly. But it looks incredible! That's going to be very powerful to be able to find paths over several frames. As Tonypa pointed out, I only need to pathfind every few seconds, so that would allow plenty of time for a complex path to be calculated.

hey there andré,will look into your thingy longer on weekend,just wanted to drop in and wish you a nice time during your game seminar :)
(or is it already over?,if so,let me know how it turned out =))

webgeek - I was thinking your pre-calculated path idea last night (couldn't sleep...), how do you store the path data?
I've been using a string with absolute directions in (ie. NNNENWS for go north 3 times, then go to the east once etc.) - and there's bound to be a better way!

The pre-computed data is stored in a 2d array. If you look at the thread I linked to in my first post, you can see how it works in a lot of detail. I explain it in various posts on there. Let me know if you need more information. Have fun!

sorry - I'd printed that thread to read later on, but I've just gone through it. It sounds similar in theory to the GameDev article, though you've gone way beyond by generating the results through pathfinding (they seemed to be creating the contents of the array manually).
I'll have to have a look at your examples when I get home though, as we have an IT department that George Orwell would be proud of, and it's denying me access to it...

BTW, did you post the tutorial that was mentioned in the other thread - if so, where can I read it? cheers!

Sorry, I never got around to making the tutorial. I need to, but life (and more interesting projects) always seem to get in the way.

The technique I outlined isn't actually my own. It's from an article by Smith Surasmith I believe. I posted the details in the other thread. I just implemented it in Flash using Brandon Hall's Dijkstra implementation.

Have fun!

Hello,

Sounds like you guys are figuring this out pretty well! I just wanted to throw one more piece of information at you.

It is common in games to use multiple pathfinding algorithms. As someone else mentioned, A* can be pretty expensive CPU-wise. So you don't want to load it down on 20 npcs or anything. But you could use A* or some other "smart" algorithm on your main character and the occasional Boss npc. But your run-of-the-mill idiot npcs can just bop around using a very light algo. This is a common technique.

which algorithm would you recommend for the run of the mill NPCs then?

LittleRed,

Well, that just depends on what you want to do. I'd probably just come up with my own from scratch for little npcs. I'd just have them walk in random directions and at some time in the future choose a new path. I might do something like if a NPC happens to be within a certain range of the hero then the NPC gets a little smarter and will move toward the hero.

There is no single algo that I'd recommend. Tracing and robust tracing are pretty easy and light weight. If you have my book then check out the AI chapter, I have a little fuzzy logic AI algo that allows npcs to chace the hero. They just hit walls and then turn toward the hero.

yeah, I think buying your book would help immensely.
right - I'm off to Amazon...!

I made little example of the best-first search, which in my example map is more then 10 times faster compared to the A*.

http://www.tonypa.pri.ee/test/best_first1.html

http://www.tonypa.pri.ee/test/astar2.html

Astar from zeh uses free A* published by zeh.
Other search is from the Jobe's book (MX version).
And robust tracing version is from Klas Kroon.

Hi tonypa,

Nice job :)

Yeah, A* isn't known for its speed at all. There are a couple of things I'd like to point out here. Choosing a search algorithm is a very custom task for every situation.

If all you need is blazing speed and you don't care much for the path used, then some sort of tracing is great.

If on the other hand you need the "lowest cost" path over a multi-terrain environment taking just all possible environmental concern into account, then you need to use the swiss army knife of the pathfinding world: A*

Most successfull retail games that make use of pathfinding use several different algorithms for different characters. If you are playing a game like Diablo and you click on the other side of a puddle or river, then A* will attempt to find a bridge for you to cross. If there is no bridge close enough then you'll swim across.

On the other hand, if a dumb enemy see's you on the other side of the river it might walk toward you till it hits the water, and then stop, or turn in a random direction.

Anyway, I also wanted to point out that it looks as if there is an error in those A* algorithms or they were implimented improperly. They both return the same number of steps, which is good. But both of them failed to return the shortest path, which is guaraneed. The shortest path uses diagonals. (Note: if 'diagonals' were marked as illegal in the algo, then this probably is the shortest legal path)

Moving diagonal is a distance of 1.41. But moving over and then down is a distance of 2.

Anyway, if you ever get a hold of my latest game book I have greatly improved on the A* algorithm. Although it probably would still take 200-300 ms to calculate the path you have in this grid.

As always, just use the right algo for the right situation! If you have two robots going at it in an empty room. Don't waste CPU with A*. If you have your hero running through the ruins of Pompei, you might want to consider A* :)

Quote:

---

Originally posted by jobemjobem
Anyway, I also wanted to point out that it looks as if there is an error in those A* algorithms or they were implimented improperly. They both return the same number of steps, which is good. But both of them failed to return the shortest path, which is guaraneed. The shortest path uses diagonals. (Note: if 'diagonals' were marked as illegal in the algo, then this probably is the shortest legal path)

---

Thanks, Jobe, for comments :)

I did turn off the diagonal moves to compare them.

I absolutely agree on the multi-terrain feature, which best-first search cant handle.

I am also aware that if the possible path would lead long time in one direction, but actually should go around the corner, then best-first search is wasting more time.

Im sure your new A* is much faster, but I suppose its also created using AS2. Would you say code compiled using AS2 runs somehow faster? Or it doesnt matter until you run it in the Flash player 7?

tonypa,

I'd say it's mostly related to the Flash 7 player. But my latest version is a little faster than the previous for other reasons as well (removed inefficiencies).

Anyway, nice work on creating the algo. I'm sure it will come in handy!

Hey! No one showed the speed of pre-computed pathfinding techniques! I personally feel that pre-computed pathfinding is the superior choice in static maps like this.

Number crunching time! In general, the best way to compare overall performance is to establish a base line and then use all other times as a percentage of the base line. It sounds much harder then it is.

I have run three tests of each algorithm presented in this thread on my machine. I marked the results in milliseconds of each of the tests below. The Avg. column indicates these three tests averaged together. I used "Best First" as the base line and set it to 100%. I then computed the percentage of difference for the other algorithms by dividing their average time by the average time of "Best First" and multipling by 100.

The percentage is used to illustrate differences in performace across machines better then straight milliseconds. This means that if something is 50%, then it is 2x faster then the base line. Specifically, it will take 50% LESS time then the base line took.

Without further delay, here are the results:

Code:

---

Algo.                1st        2nd        3rd        Avg        Percentage
Best First        43        40        38        40.33        100%
Precomputed        1        1        1        1.00        2.48%
Klas RT                10        10        11        10.33        25.62%
Zeh A*                415        408        410        411.00        1019.01%
Jobe A* (MX)        675        675        681        677.00        1678.51%

---

Pre-computed is dramatically faster on every run. I attached a picture to show this test. Intersting to note that pre-computed also generated the most "accurate" path of all the ones listed. In fact, it generated a "perfect" path in that it is the shortest possible solution. There might be multiple solutions as short, but none shorter. If the A* algos were allowed to support diagonals, then they would have had as short solutions.

The whole point of this is that there are many different options when pathfinding and it's doubtful that you will find a perfect one for any game. Leveraging several at once is almost certainly the best option. I know for a fact that most commercial games do this.

Here is a breakdown of some high-level algorithms.

A*
Pros - Can be tuned many ways to be usably fast. Handles multiple terrain types. Guarantees shortest paths. Will adapt to ANY situation
Cons - Can be slow so needs to be used sparingly. The map needs to have lots of costing data for the search algorithm to use

Tracing
Pros - Pretty fast. Works on dynamic maps.
Cons - Paths are not "perfect". No terrain handling

Precomputed
Pros - Blazing speed, no technique is faster. Guarantees shortest paths (based on the implementation used to pre-compute)
Cons - Doesn't handle dynamic maps. Storing the search data might be difficult or cumbersome.

Have fun!