游戏 AI / 系统课时
节点对象该保存哪些状态
节点对象该保存哪些状态
A* 的循环并不难,真正容易失控的是节点状态:坐标、代价、父节点和“是否已经处理过”如果混在一起更新,很快就会出现路径断裂或评分不一致。本节把节点拆成职责清晰的字段,并用一个可运行对象验证它们如何协作。
学习目标
- 区分坐标、搜索评分、父节点和搜索状态各自解决的问题
- 理解
g、h、f的更新关系,以及为什么f更适合作为派生值 - 能设计一个可复用、可重置的 A* 节点对象
节点状态其实分成三类
一个网格节点通常同时承载三类信息。第一类是地图固有信息,例如行列坐标、是否可通行;第二类是本次搜索产生的信息,例如 g、h、父节点;第三类是搜索流程状态,例如未发现、已进入开放集合、已经关闭。
g 表示从起点走到当前节点的已知最小代价,h 表示从当前节点到目标的启发式估计,f 用于开放集合排序,并满足 f = g + h。父节点则记录“当前最优代价是从谁更新来的”,搜索结束后正是靠它反向恢复整条路径。

设计一个可复用节点对象
下面用 Python 建一个最小节点模型。这里不单独保存 f,而是通过属性实时计算,避免更新了 g 或 h 却忘记同步 f。
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)预期输出:
(1, 2)
10 14 24
(1, 1)
open实际项目里的代价可以是整数或浮点数,也可以使用“直走 10、斜走 14”这样的缩放值。关键不是具体单位,而是一次搜索中的所有代价使用同一套尺度。
父节点如何恢复路径
当检查邻居并发现一条更便宜的路径时,不只是更新它的 g,还要把 parent 改成产生这次更优代价的当前节点。到达目标后,从目标不断读取 parent 直到起点,再反转节点序列,就得到起点到终点的路径。
父节点保存的是当前搜索中最优路径的来源,不是地图上的永久父子关系。因此同一个节点在下一次搜索中完全可能拥有不同父节点。若复用节点对象却没有清空旧 parent,失败搜索甚至可能残留上一轮路径信息。
哪些状态不要混在节点里
开放集合和关闭集合属于搜索器的数据结构。通用节点对象没有必要保存“位于堆数组的第几个位置”“被弹出多少次”之类容器内部信息,除非你明确实现了支持索引更新的特殊优先队列。
如果地图长期存在而搜索会反复执行,最重要的边界就是:地图属性长期保存,搜索属性按轮次重置,排序分数保持单一真相源。守住这三个约束,后面的优先队列、邻居更新和路径回溯都会简单很多。