I posted this question on stack overflow first, but I guess no one is very interested in video games there...
What are some path finding algorithms used in games of all types? (Of all types where characters move, anyway) Is Dijkstra's used a whole lot? I would think not, as it doesn't actually trace out the steps to take to get somewhere, right? If I'm understanding it right, it only determines which object is the closest. I'm not really looking to code anything; just doing some research, though if you paste pseudocode or something, that would be fine (I can understand Java and C++). I'm basically looking for a quick overview of path finding in general.
I know A* is like THE algorithm to use in 2D games. That's great and all, but what about 2D games that are not grid-based? Things like Age of Empires, or Link's Awakening. There aren't distinct square spaces to navigate to, so what do they do?
What do 3D games do? I've read this thingy http://www.ai-blog.net/archives/000152.html, which I hear is a great authority on the subject, but it doesn't really explain HOW, once the meshes are set, the path finding is done. IF A* is what they use, then how is something like that done in a 3D environment? And how exactly do the splines work for rounding corners?
Answer
Too many questions at once, so it's hard to give a concrete answer but to discuss a few of these topics. I'll divide the answer in two and try to address it as best as I can. I don't claim any of these lists to be complete, but they're some of the different methods I could remember.
For starters, there are many ways to implement pathfinding, but not all of them return the shortest path, or are efficient or even reliable. For instance:
Primitive methods that don't "look ahead" and take one step at a time:
Random backstepping - Take one step at a time in the direction of the goal. If an obstacle is encountered try to work around it by backstepping a bit in a random direction and then trying again. Not reliable at all and will get stuck in a multitude of situations.
Obstacle tracing - Other approach, similar to random backstepping but instead of moving back randomly, start tracing around the object once a collision is found, as if you had the right hand stuck to the wall and had to move touching it. Once there's no collision continue moving in the goal's direction. Once again can get stuck in many situations.
Methods that look ahead to find the entire path at once:
Breadth First Search - Simple graph traversal by visiting each layer of children at a time, stop when path is found. If the graph is unweighted (i.e. the distance between each adjacent node is always the same) it finds the shortest path although not too efficiently. For weighted graphs it might not return the shortest path, but will always find one if it exists.
Depth First Search - Another way to traverse a graph, but instead of taking it layer by layer, the algorithm tries to search deep into the graph first. This method can have problems if the depth of the search is not limited, especially when using a recursive implementation, which may lead to a stack overflow, so it is usually safer to implement it iteratively using a stack.
Best First Search - Similar to Breadth First Search but uses an heuristic that chooses the most promising neighbor first. The path returned may not be the shortest, but it's faster to run than breadth first search. A* is a type of Best First Search.
Dijkstra's Method - Keeps track of the total cost from the start to every node that is visited, and uses it to determine the best order to traverse the graph. Works with weighted graphs and returns the shortest path, but might involve a lot of searching.
A* - Similar to Dijkstra but also uses an heuristic to estimate how likely each node is close to the goal, in order to make the best decision. Because of this heuristic, A* finds the shortest path in a weighted graph in a much more timely manner.
Then there are variations of A* (or pathfinding optimizations in general) that make it faster or more adapted to certain circunstances, such as (see related answer and a comprehensive list on cstheory.SE):
- LPA* - Similar to A* but can more quickly recalculate the best path when a small change to the graph is made
- D* Lite - Based on LPA*, it does the same thing, but assumes the "start point" is a unit moving towards the finish while graph changes are being made
- HPA* (Hierarchical) - Uses several layers at different abstraction levels to speed up the search. For instance, an higher level layer may simply connect rooms, while a lower level layer takes care of avoiding obstacles.
- IDA* (Iterative Deepening) - Reduces memory usage in comparison with regular A* by using iterative deepening.
- SMA* (Simplified Memory-Bounded) - Only makes use of available memory to carry out the search.
- Jump Point Search - Credits to Eric in the comments for mentioning it! Speeds up pathfinding on uniform-cost grid maps (link).
And finally to address this question:
I know A* is like THE algorithm to use in 2D games. That's great and all, but what about 2D games that are not grid-based?
Two big misconceptions here! In fact:
- A* doesn't care if the game is 2D or 3D, and is equally appropriate for both cases.
- A* works under any graph representation, so it doesn't care whether the world is a grid or not.
So if the world doesn't need to be a grid, in what other ways can you represent it? Here's a brief overview of ways to partition the world space for pathfinding, and most of these work both for 2D and 3D alike:
Rectangular grid - Partition world into regular grid of squares with each cell in the grid being one node in the graph, and the connection between two unobstructed nodes is an edge.
Quadtree - Another way to partition the space, but instead of partitioning into a grid of regular sized cells, partition in four, then recursively divide each of these in four again. Adding a third dimension makes it an octree.
Convex polygons - Partitioning the walkable area into a mesh of interconnected convex polygons. Each polygon becomes a node, and shared edges are the edges of the graph. These can be triangles for instance, and sometimes even be a mesh created by an artist when creating the level assets. Often referred to as a navigation mesh. See this link. Here's a very popular navigation mesh construction toolset: Recast.
Points of visibility - The most common way is to place a node just outside each of the obstacle's convex vertices, and then connect each pair of nodes that can see each other. Check this link. The nodes don't have to be the vertices though, and can be placed manually by the designer in the map. In that case, the system is frequently referred to as a waypoint graph.
No comments:
Post a Comment