Benchmarking Incremental Replanning vs. Naive Recomputation: An Empirical Evaluation of A* and D* Lite Across Dynamic Weighted Terrains

Real-time autonomous navigation systems and video game engines frequently require pathfinding agents to navigate heterogeneous terrain cost surfaces subject to sudden environmental mutations. While Classic A* provides optimal paths on static topologies, repeatedly computing routes de novo under dynamic hazard conditions imposes substantial CPU latency. Incremental replanning architectures, most notably D* Lite, mitigate this by repairing existing search trees via localized consistency updates. However, the theoretical benefits of incremental repair are offset by priority queue maintenance overhead and reverse consistency propagation. This paper presents an empirical benchmarking study comparing Full Recomputation (A*) against Incremental Repair (D* Lite) across discrete 2D grid graphs parameterized by non-uniform traversal costs (c in [1.0, 5.0]) and dynamic mid-transit hazards. Across 20 randomized trials per configuration at resolutions N in {16, 32, 64}, we quantify replanning latency, vertex expansion volumes, and variance profiles. Our empirical findings identify a distinct operational crossover envelope: while D* Lite reduces search space exploration by up to 97% and achieves a 5.4x latency reduction at intermediate scales (32x32), Classic A* exhibits superior wall-clock performance and bounded variance on large grids (64x64) where underconsistency cascade repair penalizes the incremental engine.