从 Grid 中检索节点时发生 IndexOutOfRange

Question

我正在实施呼吸优先搜索并尝试获取邻居节点，但是在从网格（网格为 100x100）获取邻居节点时我运行遇到 IndexOutOfRange 错误。我理解这个错误，但我不明白它为何以及如何超出网格范围。当运行ning Dijkstra 路径查找时，这种查找邻居的实现非常有效，但是当我运行 BFS 时，它似乎给了我一个 IndexOutOfRange.

我已经尝试检查当前节点的 x、z 位置以确保其在边界内，然后在网格中执行查找邻居，但这似乎对我也不起作用，产生了同样的错误。希望能深入了解我可能会在哪里出错。

网格classGrid.cs

BFS BFS.cs

邻居功能

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;
}

我试过在获取网格邻居之前检查边界，但这也不起作用，奇怪地给我同样的错误。

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]
        };
   //...
}

建议

动态查找当前点周围的邻居

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]);
        }
    }
}

Answer 1

我相信你面临的问题是你没有考虑边缘情况，例如当你处于 x 极限时，就不会有 x+1 的可能性，所以你的组合应该只是：

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],
    };

或者如果你在角落里，那么唯一可能的邻居是 [x - 1, z]，grid[x, z - 1]，grid[x - 1, z - 1]。您当前的节点创建始终试图找到该点周围的 8 个邻居，但您必须记住，情况并非总是如此。

您可以找到动态查找此问题的算法 here 或者您可以根据自己的情况尝试添加边缘情况组合，如果您愿意的话。

Answer 2

x - 1 .. z - 1 .. x + 1 .. z + 1 .. 没有检查这些是否真的可能

您只查看您当前的位置

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

但是您需要检查每个邻居是否存在，例如蛮力方式

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]);

您的 IsIndexInBounds 并不完全正确，顺便说一句，c# 中的索引以 0 开头，因此您实际上需要 >= 0 而不是 > 0。你也可以简单地做到

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

从 Grid 中检索节点时发生 IndexOutOfRange

IndexOutOfRange occuring when retrieving nodes from Grid

c#

breadth-first-search

unity3d

建议