Structural and Computational Analysis of A* and Backtracking for Deterministic Offline Grid-Based Path Planning

Offline path planning in deterministic grid environments requires balancing shortest-path optimality with computational scalability as structural branching complexity increases. This study presents a controlled simulation-based analysis of two search paradigms: the heuristic-guided A* algorithm and the exhaustive Backtracking method. The main contribution is a unified multi-criteria evaluation framework that enables systematic structural comparison under identical movement constraints, allowing transparent assessment of path optimality, turning behavior, and computational search effort. Twelve deterministic grid maps were constructed, including six maps of size 6×6 and six maps of size 12×12, with fixed start and goal positions to investigate the impact of structural complexity. Both algorithms were implemented in C using four-directional unit-cost movement and evaluated using multiple metrics, including path length, number of turns, movement score, expanded nodes, neighbor checks, and backtracking operations. Simulation results show that both algorithms consistently achieve shortest-path optimality, producing paths of 10 steps in 6×6 maps and 22 steps in 12×12 maps. However, substantial differences appear in computational effort. In the 12×12 maps, A* expanded between 27 and 70 nodes, whereas Backtracking expanded up to 943 nodes and required up to 3740 neighbor checks and more than 900 backtracking operations in highly branched configurations. These results demonstrate exponential growth in exhaustive exploration compared with polynomial growth under heuristic guidance, highlighting the structural trade-off between exhaustive completeness and heuristic-guided computational scalability in deterministic offline grid planning.