Comment by tavianator

You may want to look into improvements to A* for grids, like Rectangular Symmetry Reduction.