dontCrossCorners/diagonale and obstacle

[KoriaLL]

Greetings,

I use you algorithm to make a shortcut in my software. The option “opt.dontCrossCorners = false;” allows me to manage the diagonals in the corners without any issues (cf. picture 1 & 2)

On the other hand when I add an obstacle inside of a corner on the way of the diagonal has to go, the path is not best anymore (cf. picture 3). Would you have a solution for this issue ?

Thanks a lot. Kind Regards,

[xaguzman]

Hey! Thanks for sending your issue.

Hmm....I am not sure I follow....how is picture 3 not the shortest route? From what I understand just by looking at the screens and the "pointer" (I assume this pointer indicates the traveled path to destination) it does look to me like the shortest path....

Could you please elaborate?

[KoriaLL]

Hi, thanks for you quick answer.

Please find attached two extra pictures with the details in red. For me the shortest path on picture 2 is 1 move diagonaly, here tough it does 3 moves going around the character (which is blocking). Maybe the algoryth doesn't manage this occurence ?

Thanks for you answer. Kind Regards,

[xaguzman]

I see...Just out of curiosity, did you override the isWalkable method in the NavigationGrid?

Wondering because in your picture, obviously the cell to the right is not walkable. For the diagonal to work, at least one cell must be walkable, either the top or the right (for the top-right diagonal movement).

My first assumption is that you mark the top cell as "not walkable" since a unit is already there?

See this code:

            // up
        if (isWalkable(x, y + yDir)) {
            neighbors.add(nodes[x][y  + yDir]);
            s0 = true;
        }
        // right
        if (isWalkable(x+1, y)) {
            neighbors.add(nodes[x + 1][y]);
            s1 = true;
        }
        // down
        if (isWalkable(x, y - yDir)) {
            neighbors.add(nodes[x][y - yDir]);
            s2 = true;
        }
        // left
        if (isWalkable(x - 1, y)) {
            neighbors.add(nodes[x - 1][y]);
            s3 = true;
        }

        if (!allowDiagonal) {
            return neighbors;
        }

        if (dontCrossCorners) {
            d0 = s3 && s0;
            d1 = s0 && s1;
            d2 = s1 && s2;
            d3 = s2 && s3;
        } else {
            d0 = s3 || s0;
            d1 = s0 || s1;
            d2 = s1 || s2;
            d3 = s2 || s3;
        }

see the last part ....here we are interested that d1 = true, which depends on either, the top cell being walkable OR the right cell being walkable...Please let me know if this helps you

[KoriaLL]

I see, want I would like to do is be able to move diagonally even in this case (cf: picture) But from what I can see the algorithm is not meant to do this.

Thanks

[xaguzman]

Indeed it's not meant to do this...However, according to the rules you are implenting in your game, you could probably make a difference between a "walkable" and a "destination-able" cell.

You can walk past the other unit, but you cant stand right on top of it :). Before you allow a unit to move to a destination, see if it is actually a "standable / destination-able" cell, rather than checking if it's walkable, this should solve your issue.

The library will already take care of the iswalkable property for the whole path (including the destination path).