We present Brigitte, a new path-finding algorithm for 8-connected grids. Brigitte partitions the map into large regions and computes bridges between every pair of regions. At runtime, Brigitte finds the best bridge for the path query and builds the path from the bridge. Brigitte competes favourably compared to ch-sg-r and Copp, although she currently requires extensive pre-processing.
展开▼
