· 5 分钟阅读 · 2073 字
八方向 A* 寻路：曼哈顿估价会让可走路线提前胜出
角色确实能走到点击位置，路线上的每一步也都合法，但换掉寻路器的一行估价后，路程却缩短了。这样的错误很容易藏在“找到路径”的验收里：没有穿墙，没有断路，目标也到了，只有绕行的选择不对。若移动耗时、体力消耗或战术距离直接采用这条路线，偏差就进入了玩法规则。
这里检查一个八方向网格：水平和垂直各走一格花费 1，斜走一格花费 sqrt(2)，障碍角不能穿过。问题集中在 A* 的结束条件：目标从优先队列取出时，凭什么认为它已经足够好，可以立即返回？
估价只差一条对角线，返回条件就变了
把起点与终点在两个轴上的距离记为 dx、dy。曼哈顿距离 dx + dy 适合只能正交移动、每步成本为 1 的网格；允许廉价斜行后，相邻对角格实际只需约 1.414214，它却估成了 2。这个估价已经超过真实最小代价。
A* 按 f = g + h 排队，g 是已走的真实成本，h 是剩余成本估价。若某条尚未展开的更短路线被高估，它的队列优先级可能落到一条较长的完整路线之后。目标先出队只能说明它的 f 最小，不能自动说明它的 g 最小；目标处 h=0，其他节点处却混进了虚高的余量。
当前运动规则下，可以先去掉所有障碍。没有障碍时，先走 min(dx,dy) 次对角，再走两个轴差值对应的正交步数，得到八方向距离，也常称 octile 距离：
h = max(dx, dy) + (sqrt(2) - 1) * min(dx, dy)
去掉障碍只会增加可选路线，不会使最短路变长。因此这个值不大于有障碍地图的最优成本，是可采纳的下界。禁止穿角同样是在删边，仍保留这个下界关系。它还满足每条合法边上的 h(u) <= cost(u,v) + h(v)：无障碍最短距离满足三角不等式。这份一致性让搜索过程中的优先级具有明确含义。
我更倾向把这条公式与邻接成本放在同一个评审范围。若地图后来加入传送门、低于 1 的地形成本或更便宜的斜行，原先的证明就失效；只改邻接生成、不复核估价，会让同一段“正确的 A*”再次返回次优结果。
用同一张图，把较长路线留在回归里
最小探针位于 PathLab。源码文件 GridSearch.cs 的 GridSearch.Find 同时接受零估价、曼哈顿估价与八方向估价；零估价就是本次比较使用的 Dijkstra。以下是完整搜索实现，使用 .NET 9，不依赖引擎 API。调用期间地图必须保持不变，坐标采用左上角原点、X 向右、Y 向下。
namespace PathLab;
public enum Estimate { Zero, Manhattan, Octile }
public readonly record struct Cell(int X, int Y);
public sealed record Route(double Cost, Cell[] Path);
public static class GridSearch
{
public static double Heuristic(Cell a, Cell b, Estimate kind)
{
double dx = Math.Abs(a.X - b.X), dy = Math.Abs(a.Y - b.Y);
return kind switch
{
Estimate.Zero => 0,
Estimate.Manhattan => dx + dy,
_ => Math.Max(dx, dy) + (Math.Sqrt(2) - 1) * Math.Min(dx, dy)
};
}
public static Route Find(string[] map, Cell start, Cell goal, Estimate kind)
{
bool Walk(Cell p) => p.Y >= 0 && p.Y < map.Length &&
p.X >= 0 && p.X < map[p.Y].Length && map[p.Y][p.X] != '#';
if (!Walk(start) || !Walk(goal)) return new(double.PositiveInfinity, []);
var best = new Dictionary<Cell, double> { [start] = 0 };
var parent = new Dictionary<Cell, Cell>();
var queue = new PriorityQueue<(Cell Cell, double Cost), (double F, long Order)>();
long order = 0;
queue.Enqueue((start, 0), (Heuristic(start, goal, kind), order++));
while (queue.TryDequeue(out var entry, out _))
{
var current = entry.Cell;
if (entry.Cost != best[current]) continue;
if (current == goal)
{
var path = new List<Cell> { current };
while (parent.TryGetValue(current, out var previous))
{
current = previous;
path.Add(current);
}
path.Reverse();
return new(entry.Cost, path.ToArray());
}
for (int dy = -1; dy <= 1; dy++)
for (int dx = -1; dx <= 1; dx++)
{
if (dx == 0 && dy == 0) continue;
var next = new Cell(current.X + dx, current.Y + dy);
if (!Walk(next)) continue;
if (dx != 0 && dy != 0 &&
(!Walk(new(current.X + dx, current.Y)) ||
!Walk(new(current.X, current.Y + dy)))) continue;
double cost = entry.Cost + (dx == 0 || dy == 0 ? 1 : Math.Sqrt(2));
if (best.TryGetValue(next, out var old) && cost >= old) continue;
best[next] = cost;
parent[next] = current;
queue.Enqueue((next, cost), (cost + Heuristic(next, goal, kind), order++));
}
}
return new(double.PositiveInfinity, []);
}
}
队列项同时保存入队时的成本。某个节点后来被找到更短路径时，旧项仍留在队列里，必须通过 entry.Cost != best[current] 跳过；不能让旧项触发返回。相同优先级再按入队序号排序，固定邻居遍历顺序后，同一输入具有稳定的路线选择。这里没有永久关闭集合，成本改善时仍可重新入队。
八方向估价为最优性提供依据，队列与回溯实现负责执行它。两层不能互相代替：只换公式不能修复错误的邻接边，允许重新入队也不能挽救高估情况下的目标提前返回。
固定反例是一张八乘八地图，点号可通行，井号是障碍；起点 (0,0)，终点 (7,7)。Program.cs 保留了这张地图和对应断言，而不只依赖随机搜索找到反例。
string[] fixedMap = ["........", "...#....", "........", "..#.....",
"...#.#..", "..#...#.", "........", ".#......"];
Check(Equal(Run(fixedMap,start,goal,Estimate.Manhattan).Cost,
6+4*Math.Sqrt(2)), "fixed suboptimal");
Check(Equal(Run(fixedMap,start,goal,Estimate.Octile).Cost,
4+5*Math.Sqrt(2)), "fixed optimum");
曼哈顿版本走了 6 次正交、4 次对角，八方向版本走了 4 次正交、5 次对角。后者少了一次总成本 2-sqrt(2) 的绕行。两条路线都通过逐边合法性与成本重算检查，所以这不是把穿角捷径误当成优化；图中的障碍、节点和路线全部读取本次 run.json。
对照结果还需要一个证明边界
2026-10-16 在 .NET 9 Release 下运行，命令从文章研究目录执行，构建和运行退出码均为 0。耗时是整个断言批次的进程内计时，包含地图创建和多种搜索，不是寻路性能基准。
dotnet build PathLab.csproj -c Release --no-restore --nologo
dotnet run --project PathLab.csproj -c Release --no-build
Build succeeded. 0 warnings, 0 errors
passed=15 failed=0 skipped=0
randomMaps=400 exhaustivePairs=41472
elapsedMs=438.1965
Manhattan: 11.656854249492381
Octile: 11.071067811865477
Dijkstra: 11.071067811865477
正常样本先检查空白三乘三地图的对角路线成本为 2*sqrt(2)。边界样本 .# / #. 的两个空格互不连通，搜索返回正无穷成本和空路径；相同端点只返回一个节点，阻挡或越界端点也返回空路径。本接口有意把坏端点与不可达统一为“没有可用路线”，若调用层需要区分输入错误，应增加明确的结果分类。
其余检查覆盖固定种子 731 的 400 张八乘八地图，以及三乘三地图全部 512 种障碍布局的全部 81 组有序端点，共 41,472 组比较。八方向估价与零估价的可达性和成本全部一致；成本比较容差为 1e-10，不要求等价最短路采用同一条节点序列。
这两种搜索共用邻接生成与松弛代码，因此一致结果不能独立证明整套网格实现。空白地图解析值、禁止穿角样本和返回路径逐边重算补上了不同方向的检查；推广到任意当前规则地图的依据，仍然是无障碍下界和合法边上的一致性推导，有限样本只是回归保护。
角色最终该走多宽的通道、路径如何平滑、搜索期间地图变化如何处理，都不在这个静态点网格探针内。接入 Unity 或 Godot 的移动层之前，应先固定通行图与成本单位，再确定启发式和结束条件。如果产品允许近似路径，可以明确选择另一套近似质量与预算合同；当接口仍承诺最短路时，“找到了合法路线”就不应成为唯一验收标准。