游戏 AI / 系统课时

节点对象该保存哪些状态

节点对象该保存哪些状态

A* 的循环并不难,真正容易失控的是节点状态:坐标、代价、父节点和“是否已经处理过”如果混在一起更新,很快就会出现路径断裂或评分不一致。本节把节点拆成职责清晰的字段,并用一个可运行对象验证它们如何协作。

学习目标

  • 区分坐标、搜索评分、父节点和搜索状态各自解决的问题
  • 理解 g、h、f 的更新关系,以及为什么 f 更适合作为派生值
  • 能设计一个可复用、可重置的 A* 节点对象

节点状态其实分成三类

一个网格节点通常同时承载三类信息。第一类是地图固有信息,例如行列坐标、是否可通行;第二类是本次搜索产生的信息,例如 g、h、父节点;第三类是搜索流程状态,例如未发现、已进入开放集合、已经关闭。

g 表示从起点走到当前节点的已知最小代价,h 表示从当前节点到目标的启发式估计,f 用于开放集合排序,并满足 f = g + h。父节点则记录“当前最优代价是从谁更新来的”,搜索结束后正是靠它反向恢复整条路径。

A*节点对象中的地图属性、评分与搜索状态关系

设计一个可复用节点对象

下面用 Python 建一个最小节点模型。这里不单独保存 f,而是通过属性实时计算,避免更新了 g 或 h 却忘记同步 f。

python
from __future__ import annotations

from dataclasses import dataclass
from enum import Enum
import math


class SearchState(Enum):
    UNSEEN = "unseen"
    OPEN = "open"
    CLOSED = "closed"


@dataclass
class Node:
    row: int
    col: int
    walkable: bool = True
    g: float = math.inf
    h: float = 0.0
    parent: Node | None = None
    state: SearchState = SearchState.UNSEEN

    @property
    def f(self) -> float:
        # f 只由当前 g、h 派生,避免出现三份评分不同步。
        return self.g + self.h

    def reset_search(self) -> None:
        # 地图属性保留,只清空一次搜索产生的状态。
        self.g = math.inf
        self.h = 0.0
        self.parent = None
        self.state = SearchState.UNSEEN


if __name__ == "__main__":
    start = Node(1, 1)
    current = Node(1, 2)

    start.g = 0
    current.g = 10
    current.h = 14
    current.parent = start
    current.state = SearchState.OPEN

    print((current.row, current.col))
    print(current.g, current.h, current.f)
    print((current.parent.row, current.parent.col))
    print(current.state.value)

预期输出:

text
(1, 2)
10 14 24
(1, 1)
open

实际项目里的代价可以是整数或浮点数,也可以使用“直走 10、斜走 14”这样的缩放值。关键不是具体单位,而是一次搜索中的所有代价使用同一套尺度。

父节点如何恢复路径

当检查邻居并发现一条更便宜的路径时,不只是更新它的 g,还要把 parent 改成产生这次更优代价的当前节点。到达目标后,从目标不断读取 parent 直到起点,再反转节点序列,就得到起点到终点的路径。

父节点保存的是当前搜索中最优路径的来源,不是地图上的永久父子关系。因此同一个节点在下一次搜索中完全可能拥有不同父节点。若复用节点对象却没有清空旧 parent,失败搜索甚至可能残留上一轮路径信息。

哪些状态不要混在节点里

开放集合和关闭集合属于搜索器的数据结构。通用节点对象没有必要保存“位于堆数组的第几个位置”“被弹出多少次”之类容器内部信息,除非你明确实现了支持索引更新的特殊优先队列。

如果地图长期存在而搜索会反复执行,最重要的边界就是:地图属性长期保存,搜索属性按轮次重置,排序分数保持单一真相源。守住这三个约束,后面的优先队列、邻居更新和路径回溯都会简单很多。

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

目录与阅读设置

阅读设置

17

记录一个想法

节点对象该保存哪些状态

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

登录哪都通