Shortest path search using tiles and piecewise linear cost propagation

In this paper we propose a new algorithm for finding shortest paths in a tile connection graph. This algorithm uses an exact piecewise linear cost model to guide our search of the compact tile graph. Unlike previous tile search algorithms, this algorithm always rinds a shortest path. Unlike the grid graph algorithms (which do find shortest paths), this algorithm searches the tile graph which is much smaller than the grid graph. The efficiency of our new approach is confirmed by our experiments comparing our new algorithm with the grid graph algorithms.