2
\$\begingroup\$

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.

Improve this question
\$\endgroup\$
7
  • \$\begingroup\$ It sounds like you want to combine RSR with HPA*. I don't see any reason you couldn't do that. Treat the entrance/exit of every rectangle as a (single) node, and create edges between all nodes within a rectangle. To prevent the "open field" issue, you could limit the size of the rectangles. Or at that point, just use HPA* itself. \$\endgroup\$ – BlueRaja - Danny Pflughoeft Jan 3 '20 at 1:31
  • \$\begingroup\$ @BlueRaja-DannyPflughoeft Figures you'd show up, given I'm using some of your code in this project, hey? :) Your suggestion is intriguing, and has given me some ideas. To be clear, though, HPA* has nothing to do with caching, correct? \$\endgroup\$ – Raven Dreamer Jan 3 '20 at 1:50
  • \$\begingroup\$ I mean, you could call it caching if you want? You're creating a new graph where every "entrance" is a node, and there's a single edge between entrances, so to find the distance between entrances you only need to traverse a single edge. The suggestion here is, instead of breaking the graph into constant sized squares, you break it into variable-sized rectangles using RSR, then apply HPA*. IIRC there's another algorithm based on a similar idea, which called the entrances "portals", but I can't find it... \$\endgroup\$ – BlueRaja - Danny Pflughoeft Jan 3 '20 at 2:17
  • 1
    \$\begingroup\$ Hm. I think I remember a reference to that as well. Perhaps this one Looks relevant, at least. Though at that point, we're not using much "RSR" other than the "decompose things into rectangles" bit, which is left as an exercise to the reader in the first place. Hm. \$\endgroup\$ – Raven Dreamer Jan 3 '20 at 2:34
  • \$\begingroup\$ I will add as a comment (because it doesn't seem fair to change the question at this point), that one of the principle benefits of my implementation-at-current is that I've got it so that dynamic updates are possible. (More pathfinding cost than if you re-ran the decomposition, but still better than raw A*) Integrating other techniques which require pre-computation might make things faster, but will lose the possibility for dynamic pathfinding. \$\endgroup\$ – Raven Dreamer Jan 3 '20 at 21:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.