3D search using A* JPS

Question

How can I generalize Jump Point Search to a 3D search volume?

So far, I have defined pruning rules for a 3D cube involving each of the three movements- straight (0,0,1), first-order diagonal (0,1,1) and second-order (1,1,1).

What I'm mostly concerned about is the optimal turning points defined in the paper. I've been unable to ascertain exactly how they were derived, and therefore how to derive my own for three dimensions.

Any suggestions as to how this can be done?

Answer 1

Rather than attempting to derive turning points, it helps to use an intuitive understanding of the algorithm in 2D.

Because the shortest distance between two locations is a straight line, we know that moving diagonally is fastest because it's equivalent to two steps in 1D. In 3D, this means a diagonal is equivalent to three steps. (in reality, these values are sqrt(2) and sqrt(3)). With this, we choose to optimize by moving across as many axis as possible... Turning to move along a 2D axis is worse than turning to move along a 3D axis. Likewise, moving along 1D (straight) is even worse than 2D movement. This is the core assumption jump-point makes.

There is, in the culling algorithm, the assumption that if you are jumping on the least optimal axis (1D), then there are no optimal turns of a higher axis order (turning onto a 2D axis) until there is a parallel wall on the same axis order. For example, look at figure 2(d), where the code sees a parallel wall in 1D and adds a 2D movement back into the list.

As a Heuristic

Evaluate forward until one space is left open (and a wall is 2 spaces away), and add this point to the jumplist. For any point on the jumplist, jump in a new direction. goal > 2D movements forward > 1D movements forward > 1D movements backward > 2D movements backward. We can generalize this heuristic to any n dimension...

Evaluating the next direction, with + being towards the goal, and n being the amount of dimensions incremented gives us the equation... +nD > +n-1 D > ... +1D > 0D > -1D > ... > -n-1 D > -nD

The order of best->worst turning points in 3D

1. 3D+ = [1, 1, 1]
2. 2D+ = [1, 1, 0], [1, 0, 1], [0, 1, 1]
3. 1D+ = [1, 0, 0], [0, 1, 0], [0, 0, 1], [-1, 1, 1], [1, -1, 1], [1, 1, -1]

(suboptimals below; [0, 0, 0] is useless, so I didn't include it)

4. 0D = [1, -1, 0], [1, 0, -1], [-1, 1, 0], [-1, 0, 1], [0, -1, 1], [0, 1, -1]
5. 1D- = [-1, 0, 0], [0, -1, 0], [0, 0, -1], [-1, -1, 1], [1, -1, -1], [-1, 1, -1]
6. 2D- = [-1, -1, 0], [-1, 0, -1], [0, -1, -1]
7. 3D- = [-1, -1, -1]

phew typing that was a pain, but it should solve your problem.

Just remember that as you 'jump', keep track of which order of axis you are jumping; you need to find parallel walls in the same axis. Therefore, moving in the direction [1, 0, 1], you want to find walls that are at [1, 1, 0] and [0, 1, 1] in order to 'unlock' a jump point in the direction [1, 1, 1].

With the same logic, if you move in 1D [1, 0, 0], you check [0, 1, 0] for a wall to add [0, 1, 1] and [1, 1, 0]. You also check [0, 0, 1] in order to add [1, 0, 1] and [0, 1, 1] as jump points.

Hopefully you get what I mean, because it's really difficult to visualize and calculate, but easy to grasp once you have the mathematics of it.

Conclusion

Use the A* heuristics...

• Dijkstra = distance from start
• Greedy First = distance from goal

Then add our new heuristics!

• +nD > +n-1 D > ... +1D > -1D > ... > -n-1 D > -nD
• if any point nD has a parallel obstruction, you may add a jump point for each open n+1 D direction.

EDIT: The definition of 'parallel' for your code

• any point that is the same order as the direction you are moving
• not the next point in that direction
• has the same amount of positive and negative dimensional moves as the next point (e.g, [1, 1, -1] is parallel to [1, -1, 1] and [-1, 1, 1], but not to [1, 0, 0]