|
Algorithms for finding paths on grid graphs play a key role in modern information systems.
They are widely used in areas such as navigation systems, computer games, robotics, and even
the planning of optimal evacuation routes during emergencies. These algorithms help find
the shortest or most efficient path between two points in a structured environment, and their
performance can significantly affect the overall efficiency of the system.
This study focuses on how different algorithms handle spatial data and how various factors
influence their performance. The main goal is to understand how map structure, size, and spatial
configurations affect the speed and accuracy of pathfinding algorithms.
To ensure fair and consistent testing, a custom simulator was developed. It can generate and
analyze maps with different spatial patterns. Experiments were conducted on 300 unique grid
maps of five sizes and three layout types: Perlin noise, random, and maze.
Each map (except mazes) was tested with two types of movement costs: uniform and varied.
In addition, the start and goal points were positioned either horizontally/vertically or diagonally
across the map. The study also examined what happens when an obstacle appears on a path
that had already been planned. In total, over 225,000 tests were run, making the results very
reliable.
The study showed that an algorithm’s efficiency depends on the map’s layout, size, and
structure, as well as the positions of the start and end points. The results show that there is no
one best algorithm – each works better in different conditions and for various goals.
|
