K. Lee, M. A. Bin Marih, K. Wang, X. Fu, X. Li, Z. Qin, Hierarchical Routing on Adaptive Quadtree Graphs for Efficient Large-Scale Pathfinding
Abstract:
Efficient pathfinding in large and complex spatial networks is a fundamental challenge across many
domains, including urban transportation and maritime navigation. To address this, we develop a
hierarchical routing algorithm based on adaptive quadtree grids, with a focus on long-distance ma-
rine vessel routing as a case study. This task typically involves computing shortest paths across
discretized representations of the Earth’s surface. While uniform-resolution grids are commonly
used, they produce extremely large graphs that incur high computational and memory costs. We
propose an adaptive quadtree-based grid structure with higher resolution near coastlines and nar-
row passages while remaining coarse in open-ocean regions to significantly reduce the total number
of nodes and edges. We detail the construction of a quadtree grid to represent navigable waters,
define graph connectivity across variable-resolution cells, and apply standard shortest-path meth-
ods such as A*. To further improve efficiency, we incorporate hierarchical routing on the quadtree
grid, enabling fast search in a two-stage process. Experimental evaluations on representative global
routes demonstrate that the quadtree approach reduces graph size by several orders of magnitude,
lowers computation time substantially, and preserves route accuracy. Additional efficiency gains
are achieved through hierarchical routing on the quadtree grid. The proposed method provides a
scalable and effective foundation for global pathfinding applications and can be extended to incor-
porate dynamic, environment-dependent travel costs in future work.
License type:
Publisher Copyright
Funding Info:
This research / project is supported by the Singapore Maritime Institute - SMI-2025-MTP-02
Grant Reference no. : NA