game-ai

游戏 AI：决策、转向与寻路

通过三个可分离的层构建可信的 NPC 行为：决策（做什么）、转向（如何移动到那里）和路径（如何绕过地图）。保持层间解耦——行为树选择目标，寻路器生成路径点，转向逻辑沿路径点移动。本技能介绍与引擎无关的算法；请通过下方的相关技能将其绑定到你的引擎。

适用场景

• 实现敌人/NPC 逻辑时使用：巡逻、追逐/逃跑、守卫状态、群体移动，或“寻找通往玩家的路径”。
• 在 FSM（少量明确状态）、行为树（许多具有优先级的响应式行为）或 转向（平滑的局部移动）之间进行选择时使用。
• 集成寻路时使用：在网格/图上运行 A*，或驱动引擎导航网格 Agent。

**不适用场景：**需要使用引擎具体的导航网格/Agent API 和烘焙功能时，请使用 unity-navmesh、unreal-behavior-trees 或 Godot 的 NavigationAgent2D/3D（参见对应的引擎技能）。调整移动/碰撞手感时，请使用 physics-tuning。沿路线生成波次时，请参见 tower-defense 类型技能。

核心工作流

1. 根据复杂度选择决策模型。 2–5 个状态且转换明显 → FSM。许多行为、优先级、中断和复用需求 → 行为树。连续判断“我有多想选择每个选项” → 效用评分。
2. 将决策与移动分开。 决策层输出一个 意图（目标位置、动作）。转向或寻路将意图转化为移动。
3. 在合适的图上寻路。 网格图块、路径点图或烘焙后的导航网格。节点越少，A* 越快。3D 场景优先使用引擎的导航网格；图块游戏使用网格上的 A*。
4. 沿路径转向，不要直奔目标——跟随下一个路径点，并在接近时前进，这样 Agent 就能绕过拐角。
5. 谨慎地重新计算路径。 按计时器寻路，或在目标移动一个图块时寻路，而不是每帧都计算。缓存路径；只推进路径点索引。
6. 通过观察验证。 观察 Agent：它能到达目标吗？会卡在拐角吗？会在不同状态间来回切换吗？调试时在屏幕上绘制路径和当前状态。

模式

1. 有限状态机（单个状态对象，显式转换）

# Each state is a small object with enter/update/exit. The machine owns "current".
class_name State
func enter(agent): pass
func update(agent, dt) -> State: return null   # return a new state to transition
func exit(agent): pass

# --- Chase state: returns Patrol when the player escapes sight range ---
class Chase extends State:
    func update(agent, dt) -> State:
        if not agent.can_see(agent.target):
            return Patrol.new()                 # transition by returning next state
        agent.move_toward(agent.target.position, dt)
        return null                             # null = stay in this state

# --- Driver: call once per frame ---
func tick(dt):
    var next = current.update(self, dt)
    if next != null:
        current.exit(self); next.enter(self); current = next

将转换逻辑 放在 状态内部（或表中），不要让 if 标志越积越多。一个状态负责一种行为，这正是 FSM 易于阅读的原因。

2. 行为树 tick（复合节点返回状态）

# A node's tick() returns SUCCESS, FAILURE, or RUNNING (still working this frame).
enum Status { SUCCESS, FAILURE, RUNNING }

# Sequence: run children in order; stop at the first non-SUCCESS (logical AND).
func sequence_tick(children, agent, dt) -> int:
    for child in children:
        var s = child.tick(agent, dt)
        if s != Status.SUCCESS:
            return s                 # FAILURE or RUNNING short-circuits the sequence
    return Status.SUCCESS

# Selector: try children until one succeeds or is RUNNING (logical OR / fallback).
func selector_tick(children, agent, dt) -> int:
    for child in children:
        var s = child.tick(agent, dt)
        if s != Status.FAILURE:
            return s                 # SUCCESS or RUNNING stops the search
    return Status.FAILURE

守卫 AI 从上到下读取：Selector[ Sequence[CanSeePlayer?, Chase], Patrol ] ——如果能看到玩家就追逐，否则巡逻。叶节点、装饰器（Inverter、Cooldown）和黑板请参见 references/behavior-trees.md。

3. 转向：seek 和 arrive（平滑且与帧率无关）

# Seek: accelerate toward a target at full speed. Steering = desired - current.
func seek(pos, vel, target, max_speed, max_force) -> Vector2:
    var desired = (target - pos).normalized() * max_speed
    return (desired - vel).limit_length(max_force)   # a force, not a teleport

# Arrive: like seek, but ramp speed down inside slow_radius so it stops cleanly.
func arrive(pos, vel, target, max_speed, max_force, slow_radius) -> Vector2:
    var offset = target - pos
    var dist = offset.length()
    if dist < 0.001: return -vel                      # already there: kill drift
    var ramped = max_speed * min(dist / slow_radius, 1.0)
    var desired = offset / dist * ramped
    return (desired - vel).limit_length(max_force)

# Per frame: vel += steering * dt; pos += vel * dt   (always scale by dt)

4. A* 启发函数不得高估（否则路径就不再是最短路径）

# Match the heuristic to the movement. An ADMISSIBLE heuristic (never larger
# than the true remaining cost) keeps A* optimal.
def heuristic(a, b):
    dx, dy = abs(a.x - b.x), abs(a.y - b.y)
    # return dx + dy             # Manhattan: 4-direction grids (no diagonals)
    return (dx + dy) + (1.414 - 2) * min(dx, dy)   # octile: 8-direction grids
# f(n) = g(n) + h(n): g = cost from start, h = heuristic to goal.
# Overestimating h is faster but no longer guarantees the shortest path.

完整的 A* 循环（优先级队列、came_from 路径重建、网格图和路径点图）见 references/pathfinding.md。

常见问题

• 每帧都寻路会严重降低帧率。使用计时器重新计算，或仅在目标移动到新格子时重新计算；其间沿缓存的路径点移动。
• 直接朝目标移动而不是朝下一个路径点移动，会让 Agent 紧贴墙壁和拐角。沿路径移动；进入半径范围后再切换到下一个路径点。
• A* 启发式不可采纳（例如放大后的欧几里得距离，或在对角网格上使用曼哈顿距离）虽然能快速返回结果，但路径不是最短路径。选择与允许的移动方式相匹配的启发式。
• 行为树中用于跨帧操作（行走、播放动画）的叶节点从不返回 RUNNING，会导致行为树每个 tick 都重新启动该操作。操作完成前应返回 RUNNING。
• FSM 转换逻辑一团乱：到处散布 if state == ... 检查，会重现 FSM 本来要避免的混乱。将转换逻辑放在状态中。
• 没有视线检查或卡住检查 → Agent 会一直撞墙。添加超时机制，强制重新寻路或切换状态。

参考资料

• references/pathfinding.md — 完整的 A*（优先级队列、路径重建）、网格与路径点图，以及何时交由引擎导航网格处理。
• references/behavior-trees.md — 节点分类、叶节点与装饰器实现、黑板，以及 FSM 与行为树的选择。

相关技能

• unity-navmesh、unreal-behavior-trees — 具体引擎的 AI / 导航 API。
• physics-tuning — 移动、碰撞响应和 Agent 半径。
• procedural-gen — 生成 AI 要导航的图 / 关卡。
• tower-defense、fps-shooter — 会组合使用此技能的游戏类型。