Fast, optimal pathfinding with compressed path databases

Abstract

Most existing pathfinding methods are based on runtime search. Despite an impressive progress achieved in recent years, search-based methods could explore, in bad cases, large portions of a map, leading to an increased running time. We take a significantly different approach from search-based methods. Given a map, our program precomputes all-pairs shortest paths (APSP) information. APSP data are compressed, reducing the size dramatically with no information loss. We call the resulting data a compressed path database (CPD). At runtime, optimal moves are retrieved one by one until a complete (or partial, if desired) optimal path is retrieved. CPDs lead to a fast path computation, eliminating the need for runtime search. The first move lag is very low, as each move is retrieved independently from subsequent moves. The price to pay includes a significant preprocessing time and memory to build and store a CPD.