Rectangle expansion A∗ pathfinding for grid maps

Search speed, quality of resulting paths and the cost of pre-processing are the principle evaluation metrics of a pathfinding algorithm. In this paper, a new algorithm for grid-based maps, rectangle expansion A∗ (REA∗), is presented that improves the performance of A∗ significantly. REA∗ explores maps in units of unblocked rectangles. All unnecessary points inside the rectangles are pruned and boundaries of the rectangles (instead of individual points within those boundaries) are used as search nodes. This makes the algorithm plot fewer points and have a much shorter open list than A∗. REA∗ returns jump and grid-optimal path points, but since the line of sight between jump points is protected by the unblocked rectangles, the resulting path of REA∗ is usually better than grid-optimal. The algorithm is entirely online and requires no offline pre-processing. Experimental results for typical benchmark problem sets show that REA∗ can speed up a highly optimized A∗ by an order of magnitude and more while preserving completeness and optimality. This new algorithm is competitive with other highly successful variants of A∗.