AAAI Publications, Sixth Annual Symposium on Combinatorial Search

Font Size: 
The Hierarchy in Grid Graphs (Extended Abstract)
Sabine Storandt

Last modified: 2013-06-19


Many speed-up techniques developed for accelerating the computation of shortest paths in road networks, like reach or contraction hierarchies, are based on the property that some streets are ’more important’ than others, e.g. on long routes the usage of an interstate is almost inevitable. In grids there is no obvious hierarchy among the edges, especially if the costs are uniform. Nevertheless we will show that contraction hierarchies can be applied to grid graphs as well. We will point out interesting connections to speed-up techniques shaped for routing on grids, like swamp hierarchies and jump points, and provide experimental results for game maps, mazes, random grids and rooms.


route planning; grid graph; contraction hierarchies

Full Text: PDF