Pathfinding - Index out of Bounds

Question

Good day everyone, I'm writing my own pathfinding script, first had it on paper then started coding and let me tell you, it's much harder in practice than in theory. So, I've ran into a problem, which I of course can't solve.

The problem presents itself in the following images:1) In this shot, the waypoint is set to (6,6) and returns no errors. 2) Note the 2 points in the upper right corner, one shows no direction the other shows up. Error is the node that points upwards. In this shot, the waypoint is moved to (7,5) at which point it starts throwing errors starting from the last index. The more I move the waypoint closer to the bottom-right corner, the more points at X=13 down the Y axis throws exceptions.

Relevant code:

 for (int x = 0; x < map.sizeX; x++)
    {
        for (int y = 0; y < map.sizeY; y++)
        {
            if (!(x == pVal.x && y == pVal.y) && map.grid[x, y].passable )
            {
                float dot = 1;
                var heading = (grid[x, y].position - t.position).normalized;
                heading.y = 0;
                foreach (Vector3 direction in map.GetDirections())
                {
                    var dot2 = Vector3.Dot(heading, direction.normalized);
                    if (dot > dot2 )
                    {
                        if (map.grid[x + (int)direction.x, y + (int)direction.y].passable)
                        {  // Error thrown when it reaches this if-statement \\
                            grid[x, y].direction = direction;
                            dot = dot2;
                        }
                    }
                }

            }
        }
    }

This Index out of Bounds error is only thrown when I add the check to see if the point towards the direction is passable or not. Another thing to note is that I use direction.y where the directions are actually stored in x and z. For some reason if I use the z instead of y, it stops working completely.

Answer 1

Make a simple function that checks if you are within the bounds of the map.grid 2D array before doing if (map.grid[x + (int)direction.x, y + (int)direction.y].passable).

Check if map.grid[x + (int)direction.x is less than map.sizeX-1

then check if map.grid[ y + (int)direction.y] is less than map.sizeY-1.

If both conditions are met, go ahead with the if (map.grid[x + (int)direction.x, y + (int)direction.y].passable).

Here is a simple function to simplify that:

bool isWithinBound(Vector3 direction, int sizeX, int sizeY, int x, int y)
{
    return ((x + (int)direction.x < sizeX - 1) && (y + (int)direction.y < sizeY - 1));
}

Now you can just do:

for (int x = 0; x < map.sizeX; x++)
{
    for (int y = 0; y < map.sizeY; y++)
    {
        if (!(x == pVal.x && y == pVal.y) && map.grid[x, y].passable)
        {
            float dot = 1;
            var heading = (grid[x, y].position - t.position).normalized;
            heading.y = 0;
            foreach (Vector3 direction in map.GetDirections())
            {
                var dot2 = Vector3.Dot(heading, direction.normalized);
                if (dot > dot2)
                {
                    //Check if we are within bounds
                    if (isWithinBound(direction, map.sizeX, map.sizeY, x, y))
                    {
                        if (map.grid[x + (int)direction.x, y + (int)direction.y].passable)
                        {  // Error thrown when it reaches this if-statement \\
                            grid[x, y].direction = direction;
                            dot = dot2;
                        }
                    }
                }
            }
        }
    }
}

Answer 2

When in doubt, try walking through a test case to see what goes wrong.

Let's say we're in the second image, x = 13, y = 12

if (!(x == pVal.x && y == pVal.y) && map.grid[x, y].passable )

(13, 12) is not our target point, and is passable, so we pass this test and proceed to the next line...

float dot = 1;
var heading = (grid[x, y].position - t.position).normalized;
heading.y = 0;

heading ends up being something like (0.659, 0, 0.753) here, though if you have some y offsets it might be shorter since you normalize it before zeroing the y.

foreach (Vector3 direction in map.GetDirections())

I don't know what order your directions are stored in, so I'll just guess here:

{(0, 0, 1), (1, 0, 1), (1, 0, 0), (1, 0, -1)...}

Starting with (0, 0, 1) then...

var dot2 = Vector3.Dot(heading, direction.normalized);
if (dot > dot2 )

dot is still 1, and dot2 is 0.753 so we pass this test, check that the cell above is passable (even though that points wildly away from the direction we want to go! More on that soon), set dot = dot2 and try the next direction:

(1, 0, 1) normalizes to (0.707, 0, 0.707). dot is 0.753 and dot2 is 0.466 + 0.532 = 0.998 so we fail the dot > dot2 test and skip this one.

Here's the killer: (1, 0, 0)

dot is still 0.753 and dot2 is 0.659, so we pass the dot > dot2 test, and proceed to check the cell in that direction:

if (map.grid[x + (int)direction.x, y + (int)direction.y].passable)
{  // Error thrown when it reaches this if-statement \\

No kidding an error is thrown! We were already at x = 13 (ie. map.sizeX - 1) and we added 1, so we're off the edge of the board!

---

So, this error is easy to detect just by walking through the problem case.

Possible fixes (from most to least hacky):

• Do bounds checking whenever you try to access an adjacent cell, and skip it if it would lead off the map.

• Add a border of unused grid cells around your map, so checking one cell off the edge never poses a problem.

• Consider switching to a more conventional, well-studied pathfinding algorithm, like Breadth-first search (all moves cost the same) or Djikstra's algorithm (distinct move costs) if you want to populate the entire grid with pathing information, or A* if you want the shortest point-to-point path.