Search code examples
artificial-intelligencepath-findinga-star

Jump-Point searching in detail


I have been trying to implement jump-point search to my already implemented A* pathfinding code, but I don't fully understand how it works. The website here (which is all that I could find on it) doesn't really explain much about how to prune or how to determine a jump-point successor. Could anyone explain these two things in detail?


Solution

  • The technical details are in the research paper, which can be found on Alban Grastien's web page.

    There is also a tutorial on aigamedev.com.

    It appears that an improved paper will appear at ICAPS 2014, but I don't believe the papers are online yet.

    If these resources are insufficient, a more directed question (what don't you understand) will be easier to answer. But, one thing important to note is that JPS scans the state space looking for obstacles. In doing so it may look at far more states than A* does. But, its time savings come from not putting most states in the OPEN list.