While there have been many papers published on path planning in grids, there has not been significant work on comparing existing approaches, and it is difficult to evaluate new work in comparison to existing work. After creating a public repository of grid-based path planning problems we created the grid-based planning competition (GPPC) to facilitate these comparisons. This article describes the motivation and design of the competition, as well as plans for the future of the competition.

Grids are often used to represent maps in video games. In this paper, we propose a method for preprocessing eightneighbor grids to generate subgoal graphs and show how subgoal graphs can be used to find shortest paths fast. We place subgoals at the corners of obstacles (similar to visibility graphs) and add those edges between subgoals that are necessary for finding shortest paths, while ensuring that each edge connects only subgoals that are easily reachable from one another. We describe a method for finding shortest paths by first finding high-level paths through subgoals and then shortest low-level paths between consecutive subgoals on the highlevel path. Our method was one of ten entries in the Grid-Based Path Planning Competition 2012. Among all optimal path planners, ours was the fastest to find complete paths and required the least amount of memory.