Research indexConference paper
Computing Geodesic Path Distances in Toggleable Regular Grid
Noh
26 May 2025Open access
NobleIDark:/48914/w1/20261105/AB960B17DOI10.1145/3769872.3769901
Computing Geodesic Path Distances in Toggleable Regular Grid
Noh · 2025
NobleIDark:/48914/w1/20261105/AB960B17DOI10.1145/3769872.3769901
Free to read at the publisher
You can read the abstract here, or the full text at the publisher.
Abstract
Computation of geodesics is one of the fundamental problems in computational geometry. This can be applied to games and robot navigation for finding the optimal path in environments with obstacles. The heat method provides an efficient approach for approximating geodesics with efficient runtime performance. However, its adoption in path-finding in dynamic environment has been limited due to expensive precomputation. This paper proposes a modified heat method to accommodate dynamic environmental changes in interactive rates. The formulation is based on the regular grid domain commonly used in path-finding algorithms. Through extensive numerical analysis of the heat method, suitable numerical conditions are established for closed regular grid domains. The performance of the matrix modification approach is then evaluated both quantitatively and qualitatively. The results demonstrate that the proposed method enables interactive adaptation to environmental changes.