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!
Answer
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*.
No comments:
Post a Comment