Brigitte, a Bridge-Based Grid Path-Finder

Proceedings of the International Symposium on Combinatorial Search, 12

Volume

Vol. 12 No. 1 (2019): Twelfth Annual Symposium on Combinatorial Search

Extended Abstracts

We present BRIGITTE, a new path-finding algorithm for 8-connected grids. It is based on the notion bridge that we define here, i.e., a high-level description of paths between all pairs of points from two convex regions that allows fast distance query and fast generation of the prefix and suffix of these paths. BRIGITTE uses a pre-processing step to first partition the map into convex regions and then compute a sufficient set of bridges between every pair of regions. Path-finding is then performed by looking up the regions of the source and target cells and then iterating over the bridges of the pair of regions to determine which one yields the shortest path. BRIGITTE competes favourably compared to CH-SG-R and Copp, although this currently comes at a price of an extensive pre-processing.

10.1609/socs.v10i1.18478