Breaking Path Symmetries on 4-Connected Grid Maps

Abstract

Pathfinding systems that operate on regular grids are common in the AI literature and often used in real-time video games. Typical speed-up enhancements include reducing the size of the search space using abstraction, and building more informed heuristics. Though effective each of these strategies has shortcomings. For example, pathfinding with abstraction usually involves trading away optimality for speed. Meanwhile, improving on the accuracy of the well known Manhattan heuristic usually requires significant extra memor

We present a different kind of speedup technique based on the idea of identifying and eliminating symmetric path segments in 4-connected grid maps (which allow straight but not diagonal movement). Our method identifies rectangular rooms with no obstacles and prunes all interior nodes, leaving only a boundary perimeter. This process eliminates many symmetric path segments and results in grid maps which are often much smaller and consequently much faster to search than the original. We evaluate our technique on a range of different grid maps including a well known set from the popular video game Baldur's Gate II. On our test data, A* can run up to 3.5 times faster on average. We achieve this without using any significant extra memory or sacrificing solution optimality.