A* Jump Point Search - how does pruning really work?
- by DeadMG
I've come across Jump Point Search, and it seems pretty sweet to me. However, I'm unsure as to how their pruning rules actually work. More specifically, in Figure 1, it states that
we can immediately prune all grey neighbours as these can be reached optimally from the parent of x without ever going through node x
However, this seems somewhat at odds. In the second image, node 5 could be reached by first going through node 7 and skipping x entirely through a symmetrical path- that is, 6 -> x -> 5 seems to be symmetrical to 6 -> 7 -> 5. This would be the same as how node 3 can be reached without going through x in the first image. As such, I don't understand how these two images are not entirely equivalent, and not just rotated versions of each other.
Secondly, I'd like to understand how this algorithm could be generalized to a three-dimensional search volume.
