Dynamic environments require path planners that incorporate time-varying obstacle costs without sacrificing optimality guarantees. This work presents a low-level C implementation of the A* algorithm where each grid cell carries a mutable traversal cost. The design stores nodes in a contiguous array and maintains an open-list as a binary min-heap, thereby preserving the balanced-search invariant of logarithmic insertion and extraction. We formalize two invariants: (i) the heap order property on the f-value ( f = g + h ) and (ii) monotonic non-decrease of g-costs along any explored path. Proofs show that these invariants guarantee that the first time a goal node is closed, the associated path is cost-optimal despite dynamic penalties. Asymptotic analysis yields O(N log N) time and O(N) space, where N is the number of traversable cells. Static analysis of the source yields 138 source-lines of code and a single function block.
Manuscript Attribution: This manuscript is an empirical research preprint synthesized via agentic autonomous systems engineering pipelines adhering to academic two-column preprint conventions under the direction of Mateus Yonathan.
Hardware & Algorithmic Provenance: Algorithmic complexity bounds, execution profiles, and memory models cite verified static AST analysis and compiler toolchains evaluated by autonomous agent feedback loops.
Limitation of Liability & Scholarly Purpose: Disseminated solely for scholarly inquiry, peer discussion, and reproducible empirical comparison. It does not constitute formal peer-reviewed accreditation. Any reliance upon the mathematical proofs or complexity bounds herein is strictly at the reader's own legal and technical risk.
@article{yonathan2026_2026_10_12_a_heuristic_pathfinding_with_dynami,
title={Algorithmic Correctness Invariants and Execution Bounds of A* Heuristic Pathfindin...},
author={Yonathan, Mateus},
journal={Polyglot Systems Lab Research Preprints},
year={2026},
publisher={Polyglot Systems Lab},
url={https://myonathanlinkedin.github.io/papers/2026-10-12_a_heuristic_pathfinding_with_dynami/},
howpublished={\url{https://raw.githubusercontent.com/myonathanlinkedin/mini-papers/main/papers/2026-10-12_a_heuristic_pathfinding_with_dynami/2026-10-12_a_heuristic_pathfinding_with_dynami.pdf}}
}