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: 428
c++
|collision-detection
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