[disc] which pathfinding algorithm?

[LittleRed]

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?

[tonypa]

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

[LittleRed]

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?

[tonypa]

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.

[LittleRed]

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.

[LittleRed]

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?

[tonypa]

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.

[Trickman]

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/

[mr_shotgun_2000]

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

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

[random10122]

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.

[AndreMichelle]

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.

[LittleRed]

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

[webgeek]

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!

[token 3]

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

[AndreMichelle]

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

[LittleRed]

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.

[tomsamson]

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

[LittleRed]

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!

[webgeek]

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!

[LittleRed]

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!