The D* algorithm is a pathfinding algorithm used in video games to plan routes for AI NPCs to follow. The D* algorithm behaves similarly to the A* algorithm, with the major difference being that the D* algorithm calculates its search for an optimal path at the end of a path rather than the beginning. Its goal is the same as the A* algorithm, however, in finding the shortest path for the AI to follow.
The D* algorithm is a popular pathfinding algorithm in video game development because of its efficiency and easier implementation, especially compared to the A* algorithm. Developers who are considering using D* pathfinding over A* pathfinding must know what D* is and how it behaves. Learn the definition of the D* pathfinding algorithm and the difference between pathfinding and path planning.
What is the definition of the D* pathfinding algorithm?
The D* pathfinding algorithm is a pathing algorithm used in video games with the purpose to find the shortest distance between a starting and ending point, similar to A* pathfinding, except it begins its calculation from the ending point to the starting point. The benefit of using D* over A* is that the D* algorithm updates the existing path when obstacles are encountered instead of starting a new path from scratch, making the algorithm run faster and more efficiently. The algorithm is used both for AI route planning in video games and mobile robotic pathfinding.
The original D* pathfinding algorithm was developed by Anthony Stentz in 1994, which he called an informed incremental search algorithm. The term D* comes from the name Dynamic A* because the algorithm behaves similarly to A* but with different cost behavior. D* is designed for maps that aren’t fully known or that change over time since the algorithm is able to dynamically update the path when it encounters new obstacles. Over time, new variants of the D* pathfinding algorithm were invented, such as Focused D* and D* Lite.
Focused D* combines A* pathfinding and D* pathfinding after Stentz further developed the original D* algorithm. Focused D* aims to focus the algorithm on spreading its search based on raise and lower nodes. The algorithm uses a heuristic to accomplish this search, which ensures that only the nodes that matter are updated. This method is similar to how A* pathfinding works in that A* only computes the cost of a few nodes instead of an entire grid of nodes.
D* Lite was created by Sven Koenig and Maxim Likhachev. Koenig and Likhachev built D* Lite off of Lifelong Planning A*, which is an incremental heuristic search algorithm that combines the A* algorithm and the Dynamic SWSF-FP algorithm. Despite being called D* Lite, the algorithm isn’t based on the original D* or Focused D* algorithm. It does, however, have the same behavior. D* Lite is an easier algorithm to implement since it requires fewer lines of codes and provides better performance than Focused D*. Many game developers use D* Lite over D* for their pathfinding needs.
Understanding how the D* algorithm works requires an understanding of the terms outlined below.
- Node: Location on a graph or map that the algorithm, and later the AI, is moving to.
- New: The node has never been placed on the open list.
- Open: Data structure with nodes that have been discovered but not evaluated for cost efficiency yet.
- Closed: Data structure that refers to nodes that have been discovered and evaluated for cost efficiency. Node information is placed on the closed list to prevent the algorithm from re-evaluating the same nodes repeatedly.
- Cost: Distance from the end or goal node to the starting node, with the goal of finding the path through the available nodes that costs the least.
- Raise: Informs the algorithm that the node has a higher cost than the last time the algorithm placed it on the open list.
- Lower: Indicates that the node has a lower cost than the last time the algorithm placed it on the open list.
D* pathfinding searches work by having the algorithm begin at the end or goal node, and then selecting a node from the open list and evaluating it. The algorithm performs an action called expansion, which is when it spreads its search to all neighboring nodes and evaluates their cost from the goal node to the starting node. As the algorithm evaluates the cost of each node, focusing on the nodes with the smallest cost, or distance, from the end to start node, it creates a finalized path based on the cheapest, or shortest, distance.
The D* pathfinding algorithm is able to handle obstacles by detecting them along the intended path and tagging the nodes in the affected obstacle region as raised. When the nodes are placed on the open list and the algorithm reads that they’re raised, it tells the algorithm that it’s costlier to navigate through that area. Since the algorithm is seeking the cheapest route, its final path ignores the obstacle, avoiding it. In a video game, this means that the AI encounters a wall in its way and instead of walking through it, the algorithm tells it to walk around the wall since it’s the cheapest route.
What is the difference between pathfinding and path planning?
The difference between pathfinding and path planning is path planning finds all the possible paths while considering different aspects such as speed, obstacles, efficiency, and radius, while pathfinding searches for the shortest path amidst all the various paths that path planning generates. Pathfinding relies on information provided by path planning. Other differences between pathfinding and path planning include the type of constraints and algorithms they use to generate paths.
Constraints play a role in differentiating between pathfinding and path planning. Pathfinding is restricted to map geometry, such as avoiding collisions with walls or other obstacles. The major question pathfinding asks itself is the route that it needs to take. Path planning has several other constraints, such as physical dynamics. Physical dynamics such as speed, acceleration, and turning radius are important for it to consider. Path planning asks itself about both the route and movement strategy it needs to navigate the environment with the constraints present.
Pathfinding and path planning use different algorithms. Pathfinding uses A*, D*, D* Lite, Dijkstra’s, and Breadth-First Search to determine the most optimal path from its starting point to its end point. Each algorithm behaves differently, but its goal of finding the shortest distance is the same across them. Path planning uses Rapidly-exploring Random Trees, and Trajectory Optimization algorithms to generate all the paths in an environment.
