Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

I am writing my term paper about Path finding algorithms in games, and i've got a couple of questions, hopefully you people could help me out with those ;)

So, i've done a little bit of searching around here and stumbled on this question. Now, the things are explained nicely there, but i wonder if anyone got examples of games using those? (obviously A* won't be hard to find, it seems to be quite popular now). I figured that BFS or DFS would probably be found in some older games but I'm not that familiar with those, perhaps someone knows a couple that might be using those algorithms so i could investigate deeper?

Also, i'm having trouble figuring out the strong/weak sides of those algorithms compared to each other, as in when should i use BFS instead of Dijkstra's Method for example, from both efficiency and mechanics point of view? (If amount of available memory isn't the issue). Or is A* an answer to all the prayers and there is no reason not to use it?

Any help would be appreciated!

share|improve this question
    
Newer algorithms to google include "jump point search (A*JPS) and Rectangular Symmetry Reduction (RSR). –  Will May 23 '13 at 23:48

1 Answer 1

up vote 8 down vote accepted

when should i use BFS instead of Dijkstra's Method

BFS applies to unweighted graphs only. Dijksta's is just an extension of BFS to weighted graphs - Dijksta's on an unweighted graph will examine exactly the same nodes as BFS.

So, they can essentially be viewed as the same algorithm.

Or is A* an answer to all the prayers and there is no reason not to use it?

A* is just an extension of Dijkstra's algorithm, which speeds it up by using a distance-heuristic.

Dijkstra's and A* are for much more general problems than just pathfinding on a grid: they can be used to pathfind on any directed, weighted graph. A distance-heuristic for these won't always be possible; that's when Dijkstra's should be used.

However, if you have a heuristic available, there is no reason not to use A* - it will always be as-fast or faster than Dijkstra's. For pathfinding in games, which often just involve units moving through 2D or 3D space, you usually have a distance-heuristic (the actual distance between the points), so A* should be chosen over Dijkstra's.


The reason A* is often chosen over more complicated algorithms for games is that it's simple to understand and implement, yet fast enough for our needs. The biggest mistakes when using A* for games is not using the wrong algorithm, but implementing it incorrectly. For example, it is not well-known that ties must be broken towards the endpoint, and amateurs often incorrectly run the pathfinder every frame.

There are other algorithms that are sometimes used, though. A rather recent algorithm that is gaining popularity is Theta*. It is like A*, but gives the unit freedom to move in all directions (which is common in games). The old approach to do this was using A* + linear interpolation, but Theta* gives better results, with very little cost to speed or complexity.

Another interesting one which I recently wrote a post in is HPA*, which is a useful way of decreasing the search-space to make searches go faster (at the cost of returning non-optimal results)


You can read about more about different pathfinding algorithms here. However, some of them are extremely complicated, and very few of these will actually give much benefit for most games anyhow - as a game programmer, it suffices to just learn and understand A*.

share|improve this answer
    
Big thanks for the links, i'll look into those. I'm mostly looking for those algorithms that are actually widely used in games (doesn't matter if it's indie game or some well know franchise). So far i've only been able to find different variations of A*. Any pointers to where i could find usages of other algorithms? (Not just A* variations) –  Darvex May 23 '13 at 17:26
    
I guess the bigger question would be are there actually any games (widely known), that use anything else rather than A*? I know ghosts in Packman had different path finding algorithms, but those were just own made if i recall correctly. –  Darvex May 23 '13 at 17:57
    
Flow fields are another way that some games do pathing. The game calculates a direction to travel for each point on the map. Agent looks at its location and goes in the direction written there. Depends on the type of game and its needs. –  Sean Middleditch May 23 '13 at 21:14

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.