I have a working implementation of Rectangular Symmetry Reduction (see here and here for more information on RSR).
I'm interested in further improving performance over raw A* by implementing caching of paths. My assumptions are as follows:
- We're working on a 4-connect square grid
- The Destination position is more important than the start position.
- Because RSR is made possible via contiguous rectangular regions, the fastest path between two points in the same region is likely to be the same (but not always)
It's at this point that I get stuck -- I'm unsure how best to use those assumptions and the information generated by a path calculation to better future path calculations.
I've considered storing the path cost from the final waypoint (that is, where the resultant path leaves the first rectangle), but as far as I've been able to consider, that is only useful if I have the path cost from every other potential waypoint on the rectangle's edge -- so good if you've got a lot of rectangular rooms separated by doors (few open edges), less so if you're pathing around wide open fields with a few scattered rocks (many open edges).
Essentially, my intuition is that going that route would potentially necessitate a lot of pathfinding before caching could provide any returns, so I'm looking for someone else's opinion on whether I'm on the right track, or if I'm missing a simpler way of implementing a performance-boosting caching algorithm.
Thoughts? I'm more than happy to discuss more of what I understand of the algorithm or share specific code if requested.