游戏 AI / 系统课时
扩展邻居时如何更新代价
扩展邻居时如何更新代价
A*真正决定路径质量的地方,不是“找到邻居”,而是判断这次到达邻居是否更便宜。实现时要把不可走节点过滤掉,计算暂定代价,并在发现更优路线时同时更新 g、f 和父节点,否则最终可能得到绕路甚至断裂的路径。
学习目标
- 能按“过滤 → 计算暂定代价 → 比较 → 更新”的顺序扩展邻居
- 理解为什么只有更小的
g才能替换父节点 - 能验证一次更优路径更新是否正确生效
一次邻居扩展到底要做什么
设当前节点为 current,邻居为 neighbor。A*会先算“如果从当前节点走到邻居,总代价是多少”:
如果邻居不可通行,直接跳过;如果 g_new 不小于邻居已经记录的 g,说明旧路线不差,也不用改。只有 g_new 更小时,才把邻居的父节点改成 current,并重新计算:
这里最容易犯的错误是只更新 g,却忘了同步父节点。g 决定搜索优先级,父节点则决定最后怎样把路径串回来,两者必须对应同一条更优路线。

用一个可运行例子验证更新规则
下面的 Java 示例只抽取“松弛一个邻居”这件事。第一次从 A 到 B 的成本较高,第二次经过 C 再到 B 更便宜,因此 B 的父节点应从 A 改成 C。
import java.util.HashSet;
import java.util.Set;
public class AStarNeighborUpdateDemo {
static class Node {
final String name;
final int h;
int g = Integer.MAX_VALUE;
int f = Integer.MAX_VALUE;
Node parent;
Node(String name, int h) {
this.name = name;
this.h = h;
}
}
static void relax(Node current, Node neighbor, int moveCost, Set<Node> openSet) {
if (current.g == Integer.MAX_VALUE) {
throw new IllegalStateException("current node has no known g cost");
}
int tentativeG = current.g + moveCost;
if (tentativeG >= neighbor.g) {
return; // 旧路线更好或相同,不替换父节点
}
neighbor.g = tentativeG;
neighbor.f = tentativeG + neighbor.h;
neighbor.parent = current;
openSet.add(neighbor);
}
public static void main(String[] args) {
Node a = new Node("A", 5);
Node b = new Node("B", 2);
Node c = new Node("C", 3);
Set<Node> openSet = new HashSet<>();
a.g = 0;
a.f = a.h;
relax(a, b, 8, openSet); // A -> B,g=8
relax(a, c, 3, openSet); // A -> C,g=3
relax(c, b, 2, openSet); // C -> B,g=5,优于原来的8
System.out.println("B.g = " + b.g);
System.out.println("B.f = " + b.f);
System.out.println("B.parent = " + b.parent.name);
}
}预期输出:
B.g = 5
B.f = 7
B.parent = C这说明第二条路线把 B 的已知代价从 8 降到了 5,并且父节点同步变成了 C。如果这里只改 g 不改 parent,后续重建路径时仍会错误地得到 A -> B。
过滤邻居时先排除哪些情况
真正接入网格地图后,通常先排除三类邻居:越界、不可通行、已经确认不需要再处理的节点。是否允许重新打开 Closed Set 中的节点取决于实现策略;如果启发式函数一致,常见实现可以在节点出队并进入 Closed Set 后不再重新打开。
移动代价要与地图规则一致。例如四方向移动可把每步成本设为 10;八方向移动时,直走可设 10、斜走设 14,用整数近似 ,可以避免大量浮点计算。重要的不是具体取值,而是 g、h 和移动成本必须使用同一套尺度。
更新后怎样检查实现是否可靠
调试时至少观察三个量:邻居更新前后的 g、新的父节点,以及最终 f=g+h 是否同步变化。若发现 Open Set 中节点顺序异常,先确认优先队列在节点 f 改变后是否会重新排序;某些优先队列并不会因为对象字段变化自动调整位置,需要删除后重新插入,或改用支持 decrease-key 的结构。
邻居扩展的核心可以归结为一句话:先算这条新路线的 g,只有更便宜时才接管这个邻居,并让代价与父节点一起更新。这样搜索阶段记录下来的关系,才足以在终点命中后重建出真正的最短路径。