How to fix cutting corner problem in A-star pathfinding

Question

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?

Answer 1

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.

Answer 2

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. :)

Answer 3

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.