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

Question

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)

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.

I recommend to start with the unoptimized description found in wikipedia. Which moves you allow or not is independent of the way you search the best path, so not really related to A*. — MrSmith42
– MrSmith42, Commented Sep 1, 2022 at 7:43

Yitz · Accepted Answer · 2022-09-01 11:28:05Z

1

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.

edited Sep 1, 2022 at 11:28

answered Sep 1, 2022 at 11:14

Yitz

1,3388 silver badges12 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

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

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related