Hurly - 1 year ago 73
C# Question

Pathfinding - Index out of Bounds

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;
foreach (Vector3 direction in map.GetDirections())
{
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.

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` 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.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download