游戏 AI / 系统课时

扩展邻居时如何更新代价

扩展邻居时如何更新代价

A*真正决定路径质量的地方,不是“找到邻居”,而是判断这次到达邻居是否更便宜。实现时要把不可走节点过滤掉,计算暂定代价,并在发现更优路线时同时更新 g、f 和父节点,否则最终可能得到绕路甚至断裂的路径。

学习目标

  • 能按“过滤 → 计算暂定代价 → 比较 → 更新”的顺序扩展邻居
  • 理解为什么只有更小的 g 才能替换父节点
  • 能验证一次更优路径更新是否正确生效

一次邻居扩展到底要做什么

设当前节点为 current,邻居为 neighbor。A*会先算“如果从当前节点走到邻居,总代价是多少”:

gnew=g(current)+cost(current,neighbor)g_{new}=g(current)+cost(current,neighbor)

如果邻居不可通行,直接跳过;如果 g_new 不小于邻居已经记录的 g,说明旧路线不差,也不用改。只有 g_new 更小时,才把邻居的父节点改成 current,并重新计算:

f(neighbor)=g(neighbor)+h(neighbor)f(neighbor)=g(neighbor)+h(neighbor)

这里最容易犯的错误是只更新 g,却忘了同步父节点。g 决定搜索优先级,父节点则决定最后怎样把路径串回来,两者必须对应同一条更优路线。

邻居扩展时的过滤、比较与更新流程

用一个可运行例子验证更新规则

下面的 Java 示例只抽取“松弛一个邻居”这件事。第一次从 A 到 B 的成本较高,第二次经过 C 再到 B 更便宜,因此 B 的父节点应从 A 改成 C。

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

预期输出:

text
B.g = 5
B.f = 7
B.parent = C

这说明第二条路线把 B 的已知代价从 8 降到了 5,并且父节点同步变成了 C。如果这里只改 g 不改 parent,后续重建路径时仍会错误地得到 A -> B。

过滤邻居时先排除哪些情况

真正接入网格地图后,通常先排除三类邻居:越界、不可通行、已经确认不需要再处理的节点。是否允许重新打开 Closed Set 中的节点取决于实现策略;如果启发式函数一致,常见实现可以在节点出队并进入 Closed Set 后不再重新打开。

移动代价要与地图规则一致。例如四方向移动可把每步成本设为 10;八方向移动时,直走可设 10、斜走设 14,用整数近似 2\sqrt{2},可以避免大量浮点计算。重要的不是具体取值,而是 g、h 和移动成本必须使用同一套尺度。

更新后怎样检查实现是否可靠

调试时至少观察三个量:邻居更新前后的 g、新的父节点,以及最终 f=g+h 是否同步变化。若发现 Open Set 中节点顺序异常,先确认优先队列在节点 f 改变后是否会重新排序;某些优先队列并不会因为对象字段变化自动调整位置,需要删除后重新插入,或改用支持 decrease-key 的结构。

邻居扩展的核心可以归结为一句话:先算这条新路线的 g,只有更便宜时才接管这个邻居,并让代价与父节点一起更新。这样搜索阶段记录下来的关系,才足以在终点命中后重建出真正的最短路径。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

扩展邻居时如何更新代价

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通