In this thesis we implemented and compared four pathfinding
algorithms on 4-way connected grid graphs: A*, ALT, HPA*, and JPS4.
The algorithms were tested on eight maps consisting of 512 × 512 nodes —
six from the game Baldur’s Gate 2, a maze, and a randomly generated map
with 10% obstacle density. For each algorithm, we measured preprocessing
time, pathfinding time, number of expanded nodes, and path length.
JPS4 proved to be the best algorithm on most metrics. It achieved an
average speedup factor of 23.38 over A* and expanded 79.54% fewer nodes
while maintaining optimal path length. Since it requires no preprocessing, it
is suitable for both static and dynamic graphs.
HPA* with 8 ×8 regions achieved a speedup factor of 15.22 and a low
break-even point, but found paths that are on average 1.52% longer. ALT
with 8 landmarks yielded a speedup factor of 1.85 and performed best on
maze-like maps, but could be slower than A* on open maps with sparse
obstacles.
For most practical applications, JPS4 is the best choice. HPA* becomes
competitive when the number of queries on a static graph is large, while ALT
is recommended for pathfinding in maze-like environments.
|
