moyuta

网格寻路的对角穿角：目标格可走，不代表这条边可走

· 5 分钟阅读 · 1852 字

给角色一张五乘五的占用网格，把起点设在 (1,1)，终点设在 (3,3)。两格障碍分别位于 (2,1) 和 (1,2)。寻路器返回 (1,1) → (2,2) → (3,3)，总代价约为 2.828427：路径上的每个节点都是空地，第一段却恰好穿过两块障碍相接的角点。若移动控制器禁止接触障碍，角色根本走不出这一步。

障碍角附近的直穿候选与外围绕行示意

这里把格宽定为 1，整数坐标表示格索引，节点位于各格中心；X 向右，Y 向下。# 占满对应的闭合方格，接触其边或角都算阻挡。研究对象是沿相邻格中心连线移动的点；这些前提决定了什么叫合法通路，不能等到最短路返回后才补充。

.....
..#..
.#...
.....
.....

错的是图中的边，换搜索算法无济于事

八邻接搜索通常枚举四个正交方向和四个对角方向。正交步长为 1，对角步长为 √2。只判断目标节点开放，会把空格中心之间所有对角线都放进图里，包括上面的穿角边。Dijkstra 或 A* 会认真寻找这张图的最短路；搜索结果短，并不说明建图时允许的运动真实可执行。

从 (x,y) 走向 (x+dx,y+dy)，当 dx、dy 都非零时，中心连线在中点经过四格共用的顶点。除了起点和终点，另外两格是 (x+dx,y) 与 (x,y+dy)。在闭障碍约定下，只要其中任意一格阻挡，这个顶点就属于障碍边界，因此两个侧格必须同时开放。将条件写成“至少一个侧格开放”，只能堵住两障碍夹角，仍会擦过单个障碍的角。

这也解释了一个容易误用的修补：给对角线增加代价，只会让它较少被选择；当其他方向全部封闭时，搜索仍会返回这条非法边。合法性应当决定边是否存在，代价才决定合法边之间的优先级。

把判断放在邻接入口

GridPath.cs 的 Find → CanStep → Open 是唯一扩展路径。下面保留完整核心实现，forbidCorner 默认开启，关闭分支只用于复现反例。地图在构造时复制，搜索读取同一份占用快照；队列使用递增序号打破等代价排序，便于固定输入重复核对。

namespace GridPathLab;

public readonly record struct Cell(int X, int Y);
public sealed record Route(Cell[] Cells, double Cost);

public sealed class GridPath
{
    private readonly string[] rows;
    private static readonly Cell[] Steps =
    [new(1, 0), new(0, 1), new(-1, 0), new(0, -1),
     new(1, 1), new(-1, 1), new(-1, -1), new(1, -1)];

    public GridPath(string[] map)
    {
        if (map.Length == 0 || map[0].Length == 0 ||
            map.Any(row => row.Length != map[0].Length || row.Any(c => c != '.' && c != '#')))
            throw new ArgumentException("Expected a rectangular grid of . and #.");
        rows = (string[])map.Clone();
    }

    public bool Open(Cell p) => p.Y >= 0 && p.Y < rows.Length &&
        p.X >= 0 && p.X < rows[0].Length && rows[p.Y][p.X] == '.';

    public bool CanStep(Cell from, Cell to, bool forbidCorner = true)
    {
        int dx = to.X - from.X, dy = to.Y - from.Y;
        if (!Open(from) || !Open(to) || Math.Abs((long)dx) > 1 ||
            Math.Abs((long)dy) > 1 || (dx == 0 && dy == 0)) return false;
        if (dx == 0 || dy == 0) return true;
        return !forbidCorner ||
            (Open(new Cell(from.X + dx, from.Y)) &&
             Open(new Cell(from.X, from.Y + dy)));
    }

    public Route? Find(Cell start, Cell goal, bool forbidCorner = true)
    {
        if (!Open(start) || !Open(goal)) throw new ArgumentException("Endpoints must be open.");
        var costs = new Dictionary<Cell, double> { [start] = 0 };
        var previous = new Dictionary<Cell, Cell>();
        var queue = new PriorityQueue<Cell, (double Cost, long Order)>();
        long order = 0;
        queue.Enqueue(start, (0, order++));
        while (queue.TryDequeue(out var current, out var priority))
        {
            if (priority.Cost > costs[current]) continue;
            if (current == goal) return Reconstruct(previous, start, goal, priority.Cost);
            foreach (var step in Steps)
            {
                var next = new Cell(current.X + step.X, current.Y + step.Y);
                if (!CanStep(current, next, forbidCorner)) continue;
                double candidate = priority.Cost + (step.X == 0 || step.Y == 0 ? 1 : Math.Sqrt(2));
                if (costs.TryGetValue(next, out double old) && candidate >= old) continue;
                costs[next] = candidate;
                previous[next] = current;
                queue.Enqueue(next, (candidate, order++));
            }
        }
        return null;
    }

    private static Route Reconstruct(Dictionary<Cell, Cell> previous, Cell start, Cell goal, double cost)
    {
        var path = new List<Cell> { goal };
        while (path[^1] != start) path.Add(previous[path[^1]]);
        path.Reverse();
        return new Route(path.ToArray(), cost);
    }
}

null 表示合法起终点之间没有路径；阻挡端点和越界端点直接拒绝，避免把坏请求混成不可达结果。本实现用 Dijkstra，是为了把验证集中在邻接合同，未引入启发函数。每个节点最多八条边，用优先队列搜索的时间复杂度为 O(V log V)，存储为 O(V)；这里没有进行引擎内寻路性能评测。

相同地图的穿角路径与合法绕行，以及封闭角反例和调用关系

严格规则返回 (1,1) → (0,1) → (0,2) → (0,3) → (1,3) → (2,3) → (3,3)，代价为 6。另一侧存在同代价绕行，固定邻接顺序和队列序号使本次稳定选择图中路径。代价从 2.828427 变成 6 是通行图修正后的结果，不是求解器退化。

更小的反例只有两行：.# 与 #.。朴素图声称两个空格以 √2 的代价连通，严格图返回不可达。Program.cs 中保留的回归同时检查两种结果：

var sealedGrid = new GridPath([".#", "#."]);
Check(sealedGrid.Find(new(0, 0), new(1, 1)) is null,
    "SealedCornerUnreachable");
Check(Near(sealedGrid.Find(new(0, 0), new(1, 1), false)!.Cost, Math.Sqrt(2)),
    "NaiveFalseReachability");

不可达也需要被验证

当天在 .NET 9.0.3 上运行 C# 离线探针。17 项检查包括单侧阻挡、双侧阻挡、开放对角、起终点相同、非法地图和端点拒绝。Exhaustive 枚举全部 512 种三乘三占用图，对其中 11,520 对开放起终点执行搜索；Reference 独立构建邻接矩阵并运行 Floyd–Warshall，比较最短代价及不可达状态。ValidateRoute 另行检查每条返回边的侧格与累计长度，避免只比较一个最终数字。

$ cd $PROBE_PROJECT
$ dotnet build GridPathLab.csproj -c Release
Build succeeded. 0 Warning(s), 0 Error(s).
Time Elapsed 00:00:09.43
Exit code: 0

$ dotnet run --project GridPathLab.csproj -c Release --no-build
passed=17 failed=0 skipped=0 elapsedMs=172.6392
naiveCost=2.828427 strictCost=6
sealedCorner: naiveCost=1.414214 strictReachable=false
exhaustive: maps=512 endpointPairs=11520
Exit code: 0

上述测试摘要取自程序 JSON 输出，代价显示到小数点后六位；耗时只描述这次验证，不代表游戏帧预算。代码与测试位于文章配套探针目录，$PROBE_PROJECT 指向该目录。穷举覆盖的是三乘三二值网格，不包含动态障碍、多代理避让或实际碰撞后端。

如果接入已有 A*，应复用同一个 CanStep 邻接入口，而不是在找到路径后删除非法节点。删除节点会把两段边拼成更长的线段，那条新线段未必合法；同样，路径平滑不能仅检查被跳过的节点是否为空，必须验证整段运动是否碰到障碍边界。

对于有体积的角色，还要先按半径和碰撞形状构建通行空间，或在边上执行扫掠检测。两个侧格开放，仅说明这一步没有擦过闭障碍角，不能承诺一条窄走廊足够容纳角色。地图动态变化时，这个示例的固定快照也需要升级为带版本的路径输入与执行前复核。起点前那条“更短”的对角线已经被正确移除；余下的工程工作，是让建图、路径后处理和实际移动共用同一份通行约定。

相关阅读