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 see relatedrelated answer and a comprehensive list on cstheory.SE):
- D (Dynamic)*LPA* - Dynamic inSimilar to A* but can more quickly recalculate the sense thatbest path when a small change to the graph is made
- D* Lite - Based on LPA*, it works underdoes the assumption thatsame thing, but assumes the terrain can change even while you're still looking for"start point" is a unit moving towards the path.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).
- 8.1k
- 2
- 38
- 41
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* that make it faster or more adapted to certain circunstances, such as (see related answer):
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):
- D (Dynamic)* - Dynamic in the sense that it works under the assumption that the terrain can change even while you're still looking for the path.
- 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.
- DIDA (DynamicIterative Deepening)* - DynamicReduces memory usage in the sense that it works under the assumption that the terrain can change even while you're still looking for the pathcomparison with regular A* by using iterative deepening.
- HPASMA (HierarchicalSimplified Memory-Bounded)* - Uses several layers at different abstraction levelsOnly makes use of available memory to speed upcarry out the search. For instance, an higher level layer may simply connect rooms, while a lower level layer takes care of avoiding obstacles
- Jump Point Search - Credits to Eric in the comments for mentioning it! Speeds up pathfinding on uniform-cost grid maps (link).
- IDA (Iterative Deepening)* - Reduces memory usage in comparison with regular A* by using iterative deepening.
- 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.
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.
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.
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.
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.
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.
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* that make it faster or more adapted to certain circunstances, such as (see related answer):
- D (Dynamic)* - Dynamic in the sense that it works under the assumption that the terrain can change even while you're still looking for the path.
- 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.
- 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.
- 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.
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):
- D (Dynamic)* - Dynamic in the sense that it works under the assumption that the terrain can change even while you're still looking for the path.
- 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).
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.