COMPARATIVE STUDY OF PATHFINDING ALGORITHM PERFORMANCE ON MAZE AND GRID-BASED ENVIRONMENTS

Abstract

Introduction. Pathfinding tasks on two-dimensional grid structures arise in a wide
range of applied domains, including navigation systems, robotics, telecommunications, and video
game development. The computational efficiency of pathfinding algorithms directly affects software
performance, particularly under constrained resources and real-time processing requirements.
Despite the availability of numerous well-known algorithms, their practical efficiency varies
substantially depending on the structural properties of the search space, including obstacle topology,
obstacle density, and graph connectivity. The selection of an appropriate algorithm for a given
environment type remains an open practical problem.
Purpose. The purpose of this work is to conduct a comparative performance analysis of widely
used pathfinding algorithms – Dijkstra's algorithm, the A* algorithm, and the Jump Point Search
(JPS) algorithm – on two-dimensional grid environments of varying structure and obstacle density,
and to formulate evidence-based recommendations for algorithm selection.
Results. The study was implemented in Python using the Pillow library for grid representation
and BMP image generation. Two maze generation methods were employed: the Binary Tree
algorithm, which produces mazes with predominantly linear corridor structures, and the randomized
Prim's algorithm, which yields more complex, uniformly distributed topologies. Map environments of
varying obstacle density were derived from both maze types through iterative dead-end removal and
corridor expansion procedures, producing four distinct map configurations. Experimental evaluation
was performed on 255×255 grids using 1000 randomized start–goal pairs per environment. Total
accumulated execution time served as the primary performance metric. The results demonstrate that
A* reduces execution time by 42-47% relative to Dijkstra's algorithm across all tested environments,
owing to heuristic-guided search. The Jump Point Search algorithm achieved the highest performance
in all scenarios, reducing total execution time by 65-88% relative to Dijkstra's algorithm and by 37- 79% relative to A*. The advantage of JPS was most pronounced on map environments with large open
areas and low obstacle density, where symmetry pruning and jump point identification most effectively
reduce the number of explored nodes. In high-density obstacle environments, the performance gain of
JPS remained substantial, with A* also showing improved relative efficiency due to more focused
heuristic guidance.
Conclusion. The experimental study confirms that heuristic and symmetry-based approaches
substantially outperform classical graph traversal in grid pathfinding tasks. JPS is recommended for
applications with high performance requirements and frequent re-planning between arbitrary node
pairs. A* provides an effective compromise when JPS applicability is constrained by environmental
conditions. Dijkstra's algorithm remains appropriate for scenarios requiring full shortest-path trees
from a fixed source node or in the absence of a valid heuristic function. Future research directions
include analysis of suboptimal but faster algorithms, extension to dynamic environments, and
adaptation to three-dimensional search spaces.