4
\$\begingroup\$

enter image description here

So this is a problem when doing diagonal jumps (checking diagonal neighbor nodes). In 2d it can be prevented by doing some checks, like if up and right is blocked, don't take up-right neighbor for calculations. But in 3d thous check become a bit to much and to tedious.. so if I still want diagonal paths, what could be a good solution?

\$\endgroup\$
  • \$\begingroup\$ Just to be clear, when a character is following that path, do they move in real-time? Or do they move one tile at a time? If the latter, the character still takes the same amount of movement to reach the exit. \$\endgroup\$ – TomTsagk Sep 25 at 9:29
  • 4
    \$\begingroup\$ Your screenshot shows another problem. A* should not make that zigzag shape we see in the bottom-left corner of the map, when it could take a more direct route straight up instead. Are you treating diagonal hops as the same cost as orthogonal moves? \$\endgroup\$ – DMGregory Sep 25 at 9:39
  • \$\begingroup\$ 1) Yes, first the path is calculated and then it moves trough the point in real-time, 2) This screenshot is not even from my project, I just wanted to show the problem at the point. :) Diagonal hops are SQRT2 and others as 1. \$\endgroup\$ – Janis Taranda Sep 25 at 10:48
  • 3
    \$\begingroup\$ Given your description I do not understand the difference between the 2D and 3D case. What is the actual problem? You say for 2D it is easy to check for such cases, so what does not work in 3D? What is the difference in map presentation /movement? \$\endgroup\$ – Mailerdaimon Sep 25 at 10:58
  • \$\begingroup\$ 2d it's Grid, 3d it's voxels, what adds complexity (+1 dimension). The checks like "if top and left is blocked, don't allow top-left", become bit to much of a struggle and sausage of if's and then's. So I thought maybe there is a more intelligent way to solve it. \$\endgroup\$ – Janis Taranda Sep 25 at 12:03
4
\$\begingroup\$

You have to solve this by fixing your logic for determining the possible edges between two nodes. This means that if you want to check a diagonal transition in 3d you need to check up to 6 different voxels for being passable.

If doing all the checks for every single diagonal edge transition becomes a performance bottleneck, then it can be a good idea to pre-compute all edges of your map once. Add a list of neighbors to each node. Do one pass where you determine all the neighbor nodes which can be reached from each node and put those in their lists. Your route finding algorithm then just needs to iterate that list of neighbors.

Another nice side-effect of this architecture is that it also becomes trivial to have your route finding algorithm account for unconventional movement methods like teleporters, jumps or one-way connections. You just need to add another edge to the list and the algorithm will handle it without you having to do anything. You don't even need to check anymore if the neighbor is out-of-bounds.

\$\endgroup\$
3
\$\begingroup\$

If a diagonal move is only valid when the orthogonal path is clear, then a simple way to avoid invalid diagonals is to never take a diagonal at all. Consider only orthogonal moves.

You don't exclude any valid solution paths that way: if an unobstructed diagonal is indeed the shortest path to your destination, then taking it as two (or three) orthogonal steps is also a valid solution path, and will be selected as the shortest out of the available orthogonal-only paths.

This also has the side benefit of reducing the branching factor of your search from 25 in 3D (26 cells to go to from here, at least one of them explored by the path we took to get here), down to 5.

Now, the obvious objection here is that this introduces unsightly stair-step kinks into the resulting path. But unnecessary kinked paths is a problem you already have with grid-based pathfinding, even when diagonals are allowed.

(Imagine your target is 30 tiles over and 10 tiles up in open space: we'd expect to go over 2, then diagonally 1, repeating to approximate the straight diagonal line to the target. But a pathfinder will typically return a kinked path that goes 20 over, then turns a corner to do the last 10 tiles diagonally. This is equivalently short, but doesn't look like the path a human would take)

So we usually apply a string pulling algorithm as a post process after the pathfinding has been done, to flatten out unnecessary corners and dead-reckon across spaces where we have line of sight to the next step of the path. In addition to flattening out deep corners like the 20-10 example above, this will also collapse our orthogonal pathing around a diagonal into a direct diagonal jump.

You still have to do equivalent neighbour-checking in the string-pulling algorithm to verify when it's valid to pull this little snag out of the path, but the savings is that you deal with this complexity only a linear number of times, where there are corners in your solution path, not a quadratic number of times for every cell you visit during your pathfinding search.

You can even do this string-pulling incrementally, as the agent follows the path: have it scan forward through the waypoints until it reaches one that's out of sight, then just dead-reckon to the point where it lost sight of the path. This spreads the cost and complexity over multiple frames. :)

\$\endgroup\$
0
\$\begingroup\$

From the comments you want to avoid a tangle of ifs in your neighbour generation and avoid the corner squeeze.

You can do that by keeping track of all possible neighbours and only generate neighbours using orthogonal movement but then generate extra neighbours based on the new neighbours but only keep those that are 1 set away:

generateNeighbours(node){
    neighbours = [];

    for(dim in {X,Y,Z}){
        newNode = node.move(dim, 1)
        if(newNode.isWalkable && !neighbours.contains(newNode)){
            neighbours.add(newNode);
        }
        newNode = node.move(dim, -1)
        if(newNode.isWalkable && !neighbours.contains(newNode)){
            neighbours.add(newNode);
        }
    }
    for(i in {1,2}) { //repeat dim-1 times.
        for(n in neighbours){
            for(dim in {X,Y,Z}){
                if(node.dist(dim) !=0) break; //already moved on this axis
                newNode = n.move(dim, 1)
                if(newNode.isWalkable && !neighbours.contains(newNode) && node.kingsDistance(n)==1){
                    neighbours.add(newNode);
                }
                newNode = node.move(dim, -1)
                if(newNode.isWalkable && !neighbours.contains(newNode) && node.kingsDistance(n)==1){
                    neighbours.add(newNode);
                }
            }
        }
    }
}

kingsDistance is the max of the difference on each axis.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.