3D search using A * JPS

Question

How can I summarize the search for a transition point in the scope of a 3D search?

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

Mostly I am concerned about the optimal turning points defined in paper . I could not determine exactly how they were obtained, and therefore how to get my own for three dimensions.

Any suggestions on how to do this?

Answer 1

Instead of trying to get turning points, it helps to use an intuitive understanding of the algorithm in 2D.

Since the shortest distance between two points is a straight line, we know that moving diagonally is faster because it is equivalent to two steps in 1D. In 3D, this means that the diagonal is equivalent to three steps. (actually these values ​​are sqrt(2) and sqrt(3) ). At the same time, we choose optimization by moving along the maximum possible axis ... A rotation along a two-dimensional axis is worse than a rotation for moving along a three-dimensional axis. Similarly, moving along 1D (straight) is even worse than 2D moving. This is the key transition point to the assumption does .

The rejection algorithm assumes that if you jump on the least optimal axis (1D), then there are no optimal rotations of a higher axis order (rotation on a two-dimensional axis) until there is a parallel wall in the same axis order. For example, see Figure 2 (d) , where the code sees a parallel wall in 1D and adds 2D movement back to the list.

Like heuristic

Evaluate ahead until one place is left open (and the wall is 2 places), and add this point to the jumplist. For any point on the jumplist, jump in a new direction. target> 2D forward motion> 1D forward motion> 1D reverse motion> 2D reverse motion. We can generalize this heuristic to any n dimension ...

Evaluation of the next direction, at + + to the target, and n - the number of sizes to be increased gives us the equation ... + nD> + n-1 D> ... + 1D> 0D> -1D> ...> -n-1 D> -nD

Order of the best-> worst turning points in 3D

• 3D + = [1, 1, 1]
• 2D + = [1, 1, 0], [1, 0, 1], [0, 1, 1] <1> 1 = 1, 1, 1, 1, 1, 1, -1]

(suboptimal below, [0, 0, 0] is useless, so I did not enable 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 is a pain, but it should solve your problem.

Just remember that when you “jump,” keep track of the order of the axis you jump; You need to find parallel walls on the same axis. Therefore, moving in the direction [1, 0, 1], you want to find the walls that are in [1, 1, 0] and [0, 1, 1] in order to “unlock” the transition point in the direction [1, 1, 1].

With the same logic, if you move to 1D [1, 0, 0], you check [0, 1, 0] for the wall to add [0, 1, 1] and [1, 1, 0], you also check [0, 0, 1] to add [1, 0, 1] and [0, 1, 1] as transition points.

I hope you understand what I mean, because it is very difficult to visualize and calculate, but it is easy to understand once you have the math.

Conclusion

Use the heuristic A * ...

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

Then add new heuristics!

• + nD> + n-1 D> ... + 1D> -1D> ...> -n-1 D> -nD
• if any point nD has a parallel obstacle, you can add a transition point for each open direction n + 1 D.

EDIT: Definition of "parallel" for your code

• any point that is in the same order as the direction of movement.
• not the next point in this direction
• has the same number of positive and negative dimensional movements as the next point (for example, [1, 1, -1] is parallel to [1, -1, 1] and [-1, 1, 1]), but not up to [1 , 0, 0]