Pathfinding Essentials: A* and Dijkstra for 2D Games Quiz Quiz

This quiz explores fundamental principles of A* and Dijkstra algorithms, emphasizing their applications and differences in 2D game pathfinding scenarios. Enhance your understanding of heuristics, cost management, and optimal routing methods with relevant examples.

1. Heuristic Functions in A* Pathfinding

   Which statement best describes the role of the heuristic function in the A* algorithm when navigating a grid-based 2D map?

   1. It guarantees the shortest path by increasing the actual cost arbitrarily.
   2. It only tracks back the visited nodes after the goal is reached.
   3. It estimates the remaining cost from the current node to the goal.
   4. It disables consideration of diagonal moves within the grid.

   Explanation: The heuristic in A* provides an estimate of the remaining distance or cost from a node to the goal, guiding path selection efficiently toward the end target. Increasing the actual cost arbitrarily does not guarantee optimality and can make the algorithm inefficient. Tracking back visited nodes is a separate process related to reconstructing the path, not the heuristic itself. Disabling diagonal moves is unrelated to heuristics and is typically handled by movement rules.

2. Comparing Dijkstra and A* Algorithms

   When navigating an open 2D world with many obstacles, how does Dijkstra's algorithm fundamentally differ from A* in the way it explores paths?

   1. Dijkstra’s algorithm requires the grid to be completely obstacle-free to function.
   2. Dijkstra's ignores all node costs, seeking a random path to the goal.
   3. Dijkstra’s only allows diagonal moves, whereas A* permits only orthogonal movement.
   4. Dijkstra’s explores equally in all directions without using a heuristic, while A* prioritizes paths using both actual and estimated costs.

   Explanation: Dijkstra’s algorithm searches evenly around the start point, since it does not use a heuristic and evaluates all available nodes based on actual cost. In contrast, A* utilizes a heuristic to guide its search more directly toward the goal, combining actual and estimated costs. Both algorithms can handle orthogonal and diagonal moves depending on implementation, so the second option is incorrect. Dijkstra does not ignore costs nor does it require a grid without obstacles, as suggested by the last two distractors.

3. Impact of Heuristic Choice in A*

   If the heuristic function in A* for 2D pathfinding always returns zero for every node, what search behavior does the algorithm exhibit?

   1. It produces infinitely looping paths until all nodes are visited.
   2. It prefers horizontal over vertical paths due to the zero heuristic.
   3. It behaves identically to Dijkstra’s algorithm by relying solely on actual path costs.
   4. It skips potential paths, making it faster but less accurate than Dijkstra’s.

   Explanation: With a zero-valued heuristic, A* ignores estimated distances and bases decisions entirely on previously accumulated costs, effectively turning into Dijkstra’s algorithm. The second option is incorrect—A* remains accurate and complete, just less directed. The third distractor incorrectly claims a preference for path direction, which would require a biased heuristic. An infinite loop or full node visitation only occurs in pathological cases, not as a direct result of a zero heuristic.

4. Handling Impassable Tiles in 2D Grids

   Which technique ensures that A* or Dijkstra’s algorithm avoids selecting impassable tiles, such as walls, on a grid-based map?

   1. Including impassable tiles in the open list but skipping them at the end.
   2. Assigning extremely high movement costs or marking those tiles as non-traversable in the search.
   3. Randomly shuffling the order of node exploration each iteration.
   4. Reducing the heuristic value for these tiles so they stand out.

   Explanation: A* and Dijkstra avoid impassable nodes by either giving them prohibitively high movement costs or excluding them from consideration (non-traversable), ensuring paths never go through walls. Lowering the heuristic for such tiles does not prevent their selection and may have undesirable effects. Random exploration order does not address the fundamental problem and could decrease efficiency. Adding impassable tiles to the open list is wasteful and risks errors even if skipped later.

5. Choosing A* vs. Dijkstra in Game AI

   Under which condition is Dijkstra’s algorithm likely to be less efficient than A* for finding a shortest path between two distant points in an open 2D map?

   1. When all heuristic values in A* overestimate the true cost by a large margin.
   2. When the start and goal are far apart and a suitable heuristic is available for A*.
   3. When the map consists only of a single straight path without branches.
   4. When there is only a single possible path between start and finish.

   Explanation: A* uses a heuristic to guide its search, making it especially efficient when the start and goal are distant, as it avoids exploring irrelevant nodes. In contrast, Dijkstra’s examines all possible routes equally, leading to unnecessary exploration in large spaces. The other options either describe scenarios where both algorithms perform similarly or where an inappropriate heuristic impairs A*’s optimality. Thus, Dijkstra is not less efficient in those cases.