Scaling Analysis of Maze-Solving Algorithms: From BFS And Dijkstra to Heuristic A*

Abstract

The maze solving has long been regarded as a fundamental problem in computer science and artificial intelligence. By modeling a maze as a weighted graph through the skeletonization, the problem can be approached as a path-finding task. This paper presents an empirical study that evaluates the classical search algorithms including BFS, DFS, Dijkstra alongside heuristic search methods (standard A* with Manhattan distance and a turn-penalized A* variant). Using mazes of varying and averaging results across multiple random seeds, the experiments measure performance in terms of expanded nodes, and runtime. Furthermore, log–log regression is applied to characterize the empirical scaling behavior of each algorithm. The results show that all algorithms exhibit near-linear growth in both node expansions and runtime, but differ significantly in constant factors. The turn-penalized A* demonstrates the influence of the heuristic design on search cost and path smoothness, highlighting trade-offs between the human-inspired intuition and the algorithmic optimality.