Search code examples
c#algorithmxnaa-star

Need help modifying existing A* Algorithm to disallow diagonal movement in specific scenario

I'm currently using this pathfinding algorithm found here on GitHub written by Gustavo Franco in 2006 (specifically PathFinderFast.cs). It's wicked fast and works fantastic. The only issue is that I need to disallow diagonal movement when the path sneaks diagonally between two obstacles (see picture) enter image description here

In this case, this path should be considered obstructed, however normal diagonal movement along obstacles, or out in an open area should still be allowed.

There's a field "mDiagonals" which when enabled, changes the "mDirection" checks from four-way to eight-way. I've tried toying around with those, but to no success.

Here is a detailed explanation of how the code works, by the author himself

Worse comes to worst, I'll end up writing my own A*, but the current implementation is so crazy optimized and easy to use I'd be sad having to do that. If anyone was able to show me how to modify the existing code, I'd be eternally grateful.

Solution

  • It looks like if after the following lines:

        if (mGrid[mNewLocationX, mNewLocationY] == 0)
        continue;

    you add

        if (i > 3 && mGrid[mLocationX, mNewLocationY] == 0 && mGrid[mNewLocationX, mLocationY] == 0)
        continue;

    should be all you need. It just checks the cell in the new row and old column, and then the cell in the old row and new column, which are the two cells that block on the diagonal, and doesn't evaluate the cell if they are both blocked.