Using something like this will on average get pathfinding for something like O(LogN) time. May sound strange or impossible at first - this is less than the number of squares the path goes through, but works and does not need huge space overhead. This is because the CH algorithm selectively adds shortcuts to the graph essentially making it completely skip many squares. Also this is not a heuristic, but a provably correct algorithm (no provable time complexity for arbitrary graph, but I think logN or maybe log^2(N) can be established for the simple graph in this pathfinding).
Using something like this will on average get pathfinding for something like O(LogN) time. May sound strange or impossible at first - this is less than the number of squares the path goes through, but works and does not need huge space overhead. This is because the CH algorithm selectively adds shortcuts to the graph essentially making it completely skip many squares. Also this is not a heuristic, but a provably correct algorithm (no provable time complexity for arbitrary graph, but I think logN or maybe log^2(N) can be established for the simple graph in this pathfinding).