Path Planning on Grids: The Effect of Vertex Placement on Path Length

Abstract

Video-game designers often tessellate continuous 2-dimensional terrain into a grid of blocked and unblocked square cells. The three main ways to calculate short paths on such a grid are to determine truly shortest paths, shortest vertex paths and shortest grid paths, listed here in decreasing  order of computation time and increasing order of resulting path length. We show that, for both vertex and grid paths on both 4-neighbor and 8-neighbor grids, placing vertices at cell corners rather than at cell centers tends to result in shorter paths. We quantify the advantage of cell corners over cell centers theoretically with tight worst-case bounds on the ratios of path lengths, and empirically on a large set of benchmark test cases. We also quantify the advantage of 8-neighbor grids over 4-neighbor grids.