A* Jump Point Search - how does pruning really work?

Posted by DeadMG on Game Development See other posts from Game Development or by DeadMG
Published on 2012-04-14T22:28:41Z Indexed on 2012/04/14 23:49 UTC
Read the original article Hit count: 398

Filed under:
|

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.

© Game Development or respective owner

Related posts about c++

Related posts about collision-detection