寻路 - 索引越界

Question

大家好，我正在写我自己的寻路脚本，先写在纸上然后开始编码，让我告诉你，实践比理论难得多。所以，我运行遇到了一个问题，我当然无法解决。

问题如下图所示：1) 在这张照片中，航路点设置为 (6,6)，returns 没有错误。 2) 注意右上角的2个点，一个没有方向，一个没有方向。错误是指向上方的节点。在这个镜头中，航路点移动到 (7,5)，此时它从最后一个索引开始抛出错误。我将航点移得越靠近右下角，Y 轴下方 X=13 处的点就越多。

相关代码：

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

            }
        }
    }

此 Index out of Bounds 错误仅在我添加检查以查看朝向该方向的点是否可通过时才会抛出。另一件需要注意的事情是，我使用 direction.y，其中方向实际上存储在 x 和 z 中。出于某种原因，如果我使用 z 而不是 y，它会完全停止工作。

Answer 1

如有疑问，请尝试遍历测试用例以查看问题所在。

假设我们在第二张图片中，x = 13, y = 12

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

(13, 12) 不是我们的目标点，是可以通过的，所以我们通过这个测试并继续下一行...

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

heading 在这里最终变成类似于 (0.659, 0, 0.753) 的东西，但如果你有一些 y 偏移量，它可能会更短，因为你在将 y 归零之前对其进行了归一化。

foreach (Vector3 direction in map.GetDirections())

我不知道你的路线是按什么顺序存储的，所以我就在这里猜测：

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

从 (0, 0, 1) 开始然后...

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

dot 仍然是 1，dot2 是 0.753 所以我们通过了这个测试，检查上面的单元格是否可以通过（即使它指向远离我们想要去的方向！稍后会详细介绍），设置 dot = dot2 并尝试下一个方向：

(1, 0, 1) 标准化为 (0.707, 0, 0.707)。 dot 是 0.753 而 dot2 是 0.466 + 0.532 = 0.998 所以我们没有通过 dot > dot2 测试并跳过这个。

这是杀手：(1, 0, 0)

dot仍然是0.753，dot2是0.659，所以我们通过了dot > dot2测试，继续检查那个方向的单元格：

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

不开玩笑，抛出了一个错误！我们已经 at x = 13（即。map.sizeX - 1），我们加了 1，所以我们离开了棋盘的边缘！

所以，只要遍历问题案例就很容易检测到这个错误。

可能的修复（从最老到最不老）：

每当您尝试访问相邻单元格时进行边界检查，如果它会导致离开地图则跳过它。
在您的地图周围添加一个未使用的网格单元格边界，因此检查一个单元格离开边缘永远不会造成问题。
考虑切换到更传统的、经过充分研究的寻路算法，如广度优先搜索（所有移动成本相同）或 Djikstra 算法（不同的移动成本），如果你想填充整个带有路径信息的网格，如果您想要最短的点对点路径，则为 A*。

Answer 2

制作一个简单的函数，在执行 if (map.grid[x + (int)direction.x, y + (int)direction.y].passable).

之前检查您是否在 map.grid 二维数组的范围内

检查 map.grid[x + (int)direction.x 是否小于 map.sizeX-1

然后检查 map.grid[ y + (int)direction.y] 是否小于 map.sizeY-1。

如果两个条件都满足，则继续if (map.grid[x + (int)direction.x, y + (int)direction.y].passable)。

这里有一个简单的函数来简化：

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

现在你只需要做：

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

寻路 - 索引越界

Pathfinding - Index out of Bounds

c#

unity3d

path-finding