NobleBlocks

Research indexConference paper

Computing Geodesic Path Distances in Toggleable Regular Grid

Noh

26 May 2025Open access

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.

Read 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.

Discussion

Citations

More

Suggest a correction or report