The paper introduces Key-Interval A* (KIA*), an exact pathfinding algorithm for 4-connected grids. It represents free space as maximal contiguous runs of traversable cells, identifies key intervals where structural boundaries change, and connects them through contiguous non-key regions. A* search is then performed on a compact key-interval graph, followed by constructive reconstruction of a grid path from interval chains without cell-level local search. The authors prove completeness and optimality, and report the fastest runtime in seven of eight benchmark groups while preserving exact shortest-path lengths.
No heat snapshots are available in the last 24 hours.