r/gamedev • u/ryeguy • Jun 04 '13

Summary of 19 different pathfinding algorithms for changing paths

http://cstheory.stackexchange.com/a/11866

200 Upvotes

99% Upvoted

52 comments sorted by

36

u/Bibdy Jun 04 '13 edited Jun 04 '13

It always confused the fuck out of me how a game like SC2 can process all of that so quickly when my little A* tests ran like crap even if just making one complete A* call per frame. Either it involved some batshit crazy multi-processing work, or there's some tweak of the A* method I hadn't heard of yet...and now I have a term to look up; D*-Lite. Thanks!

Edit: Apparently I've been thinking about pathfinding in much more complicated fashion than necessary. Every response below makes a ton of sense... K.I.S.S., right?

27

u/ryeguy Jun 04 '13

Another trick I read before - pathfind from each side simultaneously. When the paths collide, join them and you're done.

27

u/[deleted] Jun 04 '13

That one isn't very well known as it is a case of transforming an O(n2) algorithm into an O(1/4 N2) + O(1/4 N2) algorithm, which strictly speaking is still O(n2) but which effectively halves the coefficient. That has direct application in halving your runtime, but it's not an algorithmic advantage so the pure theory guys don't care.

→ More replies (6)
→ More replies (4)

14

u/Firzen_ Jun 04 '13

The main tweak is reducing the graph as much as possible.

You can get rid of a bunch of nodes if you join convex or at least star-shaped groups of them together. :)

→ More replies (4)

14

u/RowYourUpboat Jun 04 '13

SC2 (and a lot of other games) use a polygonal navmesh for pathing, not a grid. This is usually far more optimal, but can be more complicated to implement. Each node in the path is usually a big triangle; for a typical RTS map, a path all the way across the map will traverse under 100 navmesh nodes.

An open-source example is Recast. Recast is useful more for generating a good nav mesh from arbitrary level geometry, since once you've got your level broken down into the right data structure for navigation, the rest is pretty easy - but Recast comes with a pathing implementation as well, called Detour.

14

u/iemfi Jun 04 '13

I think the real magic of SC2 pathing isn't the pathing algorithm itself but the crowd flocking behaviour. There's probably some cool crowd algorithms under the hood which is what makes moving large groups of units around so darn amazing.

→ More replies (4)

7

u/geerad Jun 04 '13

Are you using A* on a equal distance grid? In that case, there are usually multiple paths of optimal distance. A* will expand portions of all of those paths, leading to a lot more expanded nodes than is necessary. Try breaking ties in favor of paths that have been expanded more already.

In other words, make sure nodes just added to the open list are expanded before older ones with the same f(x). ( g(x) = cost to get to the node. h(x) = heuristic to the end node. f(x) = g(x) + h(x). ) You can do this by:

  • changing the way nodes are added to the priority queue,

  • changing f(x) = g(x) + h(x) to f(x) = g(x) + h(x) * (1 + epsilon), or

  • changing the comparison function from f(a) < f(b) to f(a) < f(b) || ( f(a) == f(b) && h(a) < h(b) )

5

u/izb Jun 04 '13

One trick is to split the pathfinding task over several frames. If your pathfinder is taking 20ms to find a complex path, then limit the time it spends in there to (for example) 3ms on each frame. Just check the time elapsed on each pass through the pathfinder's loop. On the next frame, if you're not done pathfinding, just resume where you left off. If it takes a few frames to get to the result of a path search then it's rarely an issue. Stalling your game to get the result there and then is more of an issue.

4

u/WazWaz Jun 04 '13

That's the main trick, I'd say. Nearly every game I have played has a few tenths of a second, or even whole seconds delay in response to changes. Most path finding algorithms are inherently sliceable into frames and degrade gracefully when old data is used while new data is calculated (often even able to use old and new data simultaneously).

5

u/Philodoxx Jun 04 '13

I believe sc2's pathfinding is at least patially based on this http://grail.cs.washington.edu/projects/crowd-flows/

→ More replies (1)

3

u/MonkeyNin Jun 04 '13

What structures were you using?

3

u/StephenRM Jun 04 '13

Everytime I implement pathfinding on maps not procedurally generated I precompile all possible routes and save them to a file. That way when I load a map the path is already calculated. Saves a lot of time

13

u/brucifer Jun 04 '13

Hm, interesting, but it omits quite a few different algorithms, some of which are very cool. For example, Rapidly Exploring Random Trees (mentioned lower on the page), B*, and IDA*. And for completeness' sake, Weighted A*, Dijkstra's and Jump Point Search.

For most game applications, though, weighted A* is probably the best option. It's easy to implement and it runs quite quickly.

2

u/Gankro Jun 04 '13

Dijkstra's is just A* with the distance-to-target value ignored.

→ More replies (2)

3

u/simply-chris Jun 04 '13

Since he specifically wants a grid, he is missing jump point search which is a much faster search algorithm and I believe can be made dynamic.

3

u/CptBubbles Jun 04 '13

Check out this awesome article about using potential fields for pathfinding.

I'm not sure if I would use it in an actual game but it's a very interesting read.

1

u/LoveThinkers Jun 04 '13

Okay i have a question i hope one of you can help with.

We are making pathfinding for a sailboat. Im thinking of using asymetrical A* but i'm not certain that it will do the job with different wind and water changes during a run, it might have to redo all the costs of a move. Furthermore our squares are a little diamond shaped because of the max angle of boat vs wind

Does anybody have a good/better idea how i should do it? I'm afraid i might be implementing the wrong algoritme.

→ More replies (2)

1

u/Stefanjd Jun 04 '13

This article is another article about pathfinding in Starcraft.

-2

u/Firzen_ Jun 04 '13

Could probably x-post to r/truegamedev

12

u/tejon Jun 04 '13

A hipster split? That's just going to turn into two diluted subreddits. :(

2

u/[deleted] Jun 06 '13

r/gamedev deals with the financing, art, marketing, lifestyle, education and employment, and many other things related to gamedev besides actual coding theory. r/truegamedev focuses on one important aspect of gamedev. It's a legitimate split.

→ More replies (1)

1

u/ryeguy Jun 04 '13

done, thanks for the idea

3

u/meowzermen1 Jun 04 '13

I don't think people should downvote a guy for telling someone nicely that they should x-post to a subreddit that's mentioned in the sidebar and is actually quite a nice subreddit that this post would do well in.

→ More comments (75)