ABSTRACT
The code from this chapter, along with a full source demo, can be found on the book’s website (https://www.gameaipro.com).
JPS gets its tremendous speed from pruning the search space at runtime. This exploit exists because open areas in grids can be visited multiple times through equivalent paths. Consider a uniform cost grid space of 2 × 5 that contains no walls, as in Figure 14.1. Now consider how many optimal paths exist from the bottom left to the top right of this search space. Figure 14.1 shows that there are four identical cost paths. In many problems, traditional A* will redundantly check the same nodes along these paths to verify that a shorter path cannot be found. This is wasted work; with the ideas behind JPS+, we can avoid it.
