IndexOutOfRange occuring when retrieving nodes from Grid

Question

I am implementing Breath First Search and trying to obtain the neighbour nodes but I am running into an IndexOutOfRange Error when obtaining neighbours from the Grid (Grid is 100x100). I understand the error but I do not understand why and how it's making its way outside the bounds of the grid. This implementation of finding neighbours works perfectly when running Dijkstra path finding but when I run BFS it seems to give me an IndexOutOfRange.

I have tried checking the current nodes x, z position to make sure its in bounds and then perform finding neighbours in the grid but this did not seem to work for me either, producing the same error. Would appreciate any insight into where I might be going wrong with this.

Grid class Grid.cs

BFS BFS.cs

Neighbours function

public List<Node> GetNeighbours(Node currentNode)
{        
    var x = Convert.ToInt32(currentNode.Position.x);
    var z = Convert.ToInt32(currentNode.Position.z);

    var neighbours = new List<Node>() // Unity mentions error occurring here
    {
        grid[x - 1, z],
        grid[x + 1, z], 
        grid[x, z - 1],
        grid[x, z + 1],
        grid[x + 1, z + 1],
        grid[x - 1, z + 1],
        grid[x - 1, z - 1],
        grid[x + 1, z - 1]
    };

    var walkableNeighbours = new List<Node>();

    foreach (var neighbour in neighbours)
    {
        if (!IsCellOccupied(neighbour) && IsInLevelBounds(neighbour))
            walkableNeighbours.Add(neighbour);
    }

    return walkableNeighbours;
}

I have tried checking the bounds before getting grid neighbours but this did not work either, giving me the same error weirdly.

private bool IsIndexInBounds(int x, int z)
{
    if (x > 0 && x <= Width - 1 && z > 0 && z <= Height - 1)
        return true;

    return false;
}

public List<Node> GetNeighbours(Node currentNode)
{        
    var x = Convert.ToInt32(currentNode.Position.x);
    var z = Convert.ToInt32(currentNode.Position.z);

    if(IsIndexInBounds(x,z) { ... }
    
        var neighbours = new List<Node>()
        {
            grid[x - 1, z],
            grid[x + 1, z], 
            grid[x, z - 1],
            grid[x, z + 1],
            grid[x + 1, z + 1],
            grid[x - 1, z + 1],
            grid[x - 1, z - 1],
            grid[x + 1, z - 1]
        };
   //...
}

Suggestions

Dynamically finding neighbours surrounding the current point

List<Node> neighbours = new List<Node>();
for (int w = Mathf.Max(0, x - 1); w <= Mathf.Min(x + 1, Width); w++)
{
    for (int h = Mathf.Max(0, z - 1); h <= Mathf.Min(z + 1, Height); z++)
    {
        if (w != x || h != z)
        {
            neighbours.Add(grid[w, h]);
        }
    }
}

score 1 · Answer 1 · edited Feb 25 '22 at 14:02

I believe the problem you are facing is that you are not considering the edge cases, when you are in the x limit for example, there will be no x+1 posibility, so your combinations should only be:

var neighbours = new List<Node>()
    {
        grid[x - 1, z],
        grid[x, z - 1],
        grid[x, z + 1],
        grid[x - 1, z + 1],
        grid[x - 1, z - 1],
    };

or if you are in the corner then the only possible neighbours would be [x - 1, z], grid[x, z - 1], grid[x - 1, z - 1]. Your current node creation always tried to find the 8 neighbours sorrounding the point but you have to keep in mind this will not alway be the case.

You can find an algorithm for finding this dynamically here or you can try adding the edge case combinations according to your case, if you prefer.

Thanks for the reply! I have tried the dynamic method you suggested but I seem to get an `OutOfMemory` error when using it. I have edited the post to show my implementation of dynamically finding the neighbours. I believe I have followed the linked post you had correctly but I am facing the Out of Memory error. — Krellex, Feb 25 '22 at 18:50

derHugo · Accepted Answer · 2022-02-25T14:24:16.140

x - 1 .. z - 1 .. x + 1 .. z + 1 .. there is no check whether these are actually possible

You only check your current position

if(IsIndexInBounds(x, z) { ... }

but you would need to check for each of the neighbours whether it exists like e.g. the brute force way

var neighbours = new List<Node>();

var higherX = x + 1;
var lowerX = x - 1;
var higherZ = z + 1;
var lowerZ = z - 1;

if(IsIndexInBounds(lowerX,  z)       neighbours.Add(grid[lowerX,  z]);
if(IsIndexInBounds(higherX, z)       neighbours.Add(grid[higherX, z]);
if(IsIndexInBounds(x,       lowerZ)  neighbours.Add(grid[x,       lowerZ]);
if(IsIndexInBounds(x,       higherZ) neighbours.Add(grid[x,       higherZ]);
if(IsIndexInBounds(higherX, higherZ) neighbours.Add(grid[higherX, higherZ]);
if(IsIndexInBounds(lowerX,  higherZ) neighbours.Add(grid[lowerX,  higherZ]);
if(IsIndexInBounds(lowerX,  lowerZ)  neighbours.Add(grid[lowerX,  lowerZ]);
if(IsIndexInBounds(higherX, lowerZ)  neighbours.Add(grid[higherX, lowerZ]);

Your IsIndexInBounds is not completely correct btw, indices in c# start with 0 so instead of > 0 you would actually want >= 0. You could also simply make it

private bool IsIndexInBounds(int x, int z)
{
    return x >= 0 && x < Width && z >= 0 && z < Height;
}

IndexOutOfRange occuring when retrieving nodes from Grid

Suggestions

2 Answers2