Back to Details

game-ai

Compare original and translation side by side

🇺🇸

Original

English
🇨🇳

Translation

Chinese

Game AI: decisions, steering, and pathfinding

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

Build believable NPC behavior from three separable layers: decide (what to do), steer (how to move there), and path (how to route around the map). Keep them decoupled — a behavior tree picks a target, the pathfinder produces waypoints, steering follows them. This skill teaches the engine-neutral algorithms; bind them to your engine via the related skills below.
从三个可分离的层面构建逼真的NPC行为：决策（要做什么）、转向（如何移动到目标）和路径规划（如何绕开地图障碍）。保持三者解耦——行为树选定目标，寻路器生成路径点，转向模块沿着路径点移动。本技能教授与引擎无关的算法；可通过下方相关技能将其绑定到你的游戏引擎中。

When to use

适用场景

  • Use when implementing enemy/NPC logic: patrols, chase/flee, guard states, group movement, or "find a path to the player".
  • Use to choose between an FSM (few clear states), a behavior tree (many reactive behaviors with priorities), or steering (smooth local movement).
  • Use when integrating pathfinding: A* on a grid/graph, or driving an engine navmesh agent.
When not to use: for the engine's concrete navmesh/agent API and baking, use 
unity-navmesh
, 
unreal-behavior-trees
, or Godot's 
NavigationAgent2D/3D
(see that engine skill). For movement/collision feel, use 
physics-tuning
. For spawning waves along lanes, see the 
tower-defense
genre skill.
  • 适用于实现敌人/NPC逻辑：巡逻、追逐/逃跑、警戒状态、群体移动，或“寻找通往玩家的路径”等场景。
  • 适用于在FSM（少量清晰状态）、行为树（大量带优先级的响应式行为）或转向行为（流畅的局部移动）之间进行选择。
  • 适用于集成寻路功能：网格/图上的A*算法，或驱动引擎的navmesh agent。
不适用场景：若需使用引擎具体的navmesh/agent API及烘焙功能，请使用
unity-navmesh
、
unreal-behavior-trees
，或Godot的
NavigationAgent2D/3D
（查看对应引擎技能）。若需调整移动/碰撞手感，请使用
physics-tuning
。若需沿路线生成波次敌人，请查看
tower-defense
类型技能。

Core workflow

核心工作流程

  1. Pick the decision model by complexity. 2–5 states with obvious transitions → FSM. Many behaviors, priorities, interruption, reuse → behavior tree. Continuous "how strongly do I want each option" → utility scoring.
  2. Separate decision from motion. The decision layer outputs an intent (target position, action). Steering or pathfinding turns intent into motion.
  3. Path on the right graph. Grid tiles, waypoint graph, or a baked navmesh. Fewer nodes = faster A*. Prefer the engine's navmesh for 3D; A* on a grid for tile games.
  4. Steer along the path, not straight to the goal — follow the next waypoint, advancing when close, so agents round corners.
  5. Recompute paths sparingly. Pathfind on a timer or when the goal moves a tile, not every frame. Cache the path; only the waypoint index advances.
  6. Verify by observation. Watch the agent: does it reach the goal, get stuck on corners, oscillate between states? Draw the path and current state on screen while tuning.
  1. 根据复杂度选择决策模型。2-5个带有明显转换的状态 → FSM。大量行为、优先级、中断、复用需求 → 行为树。持续评估“对每个选项的需求程度” → 效用评分。
  2. 将决策与运动分离。决策层输出一个意图（目标位置、动作）。转向或寻路模块将意图转化为运动。
  3. 选择合适的图进行路径规划。网格瓦片、路径点图，或烘焙好的navmesh。节点越少 → A运算速度越快。3D场景优先使用引擎的navmesh；瓦片游戏优先使用网格上的A算法。
  4. 沿着路径转向，而非直接朝向目标——跟随下一个路径点，当接近时切换到下一个，这样角色能平滑绕过拐角。
  5. 尽量减少路径重计算。按时间间隔重新寻路，或仅当目标移动到新瓦片时重新计算，而非每帧都计算。缓存路径；仅更新路径点索引即可。
  6. 通过观察验证效果。观察角色：是否能到达目标？是否会卡在拐角？是否会在状态间来回切换？调试时可在屏幕上绘制路径和当前状态。

Patterns

模式

1. Finite state machine (one state object, explicit transitions)

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

gdscript
undefined
gdscript
undefined

Each state is a small object with enter/update/exit. The machine owns "current".

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
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 ---

--- 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
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 ---

--- 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

Keep transition logic *inside* states (or in a table), never as a growing pile
of `if` flags. One state owns one behavior; that is what keeps an FSM readable.
func tick(dt): var next = current.update(self, dt) if next != null: current.exit(self); next.enter(self); current = next

将转换逻辑放在*状态内部*（或状态表中），不要写成一堆不断增长的`if`判断。一个状态对应一种行为，这是保持FSM可读性的关键。

2. Behavior tree tick (composite nodes return a status)

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

gdscript
undefined
gdscript
undefined

A node's tick() returns SUCCESS, FAILURE, or RUNNING (still working this frame).

A node's tick() returns SUCCESS, FAILURE, or RUNNING (still working this frame).

enum Status { SUCCESS, FAILURE, RUNNING }
enum Status { SUCCESS, FAILURE, RUNNING }

Sequence: run children in order; stop at the first non-SUCCESS (logical AND).

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
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).

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

A guard AI reads top-down: `Selector[ Sequence[CanSeePlayer?, Chase], Patrol ]`
— chase if visible, otherwise patrol. See `references/behavior-trees.md` for
leaf nodes, decorators (Inverter, Cooldown), and a blackboard.
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 ]`——如果能看到玩家就追逐，否则巡逻。查看`references/behavior-trees.md`了解叶子节点、装饰器（Inverter、Cooldown）和黑板的相关内容。

3. Steering: seek and arrive (smooth, frame-rate independent)

3. 转向行为：追踪与抵达（流畅、帧率无关）

gdscript
undefined
gdscript
undefined

Seek: accelerate toward a target at full speed. Steering = desired - current.

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
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.

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)
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)

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

undefined
undefined

4. A* heuristic must not overestimate (or paths stop being shortest)

4. A*启发函数不得高估（否则无法得到最短路径）

python
undefined
python
undefined

Match the heuristic to the movement. An ADMISSIBLE heuristic (never larger

Match the heuristic to the movement. An ADMISSIBLE heuristic (never larger

than the true remaining cost) keeps A* optimal.

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
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.

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.

Overestimating h is faster but no longer guarantees the shortest path.


The full A* loop (priority queue, `came_from` reconstruction, grid + waypoint
graphs) is in `references/pathfinding.md`.

完整的A*循环（优先队列、`came_from`路径重建、网格+路径点图）可查看`references/pathfinding.md`。

Pitfalls

常见陷阱

  • Pathfinding every frame tanks the frame rate. Recompute on a timer or only when the target moves to a new tile; follow the cached waypoints in between.
  • Steering straight to the goal instead of to the next waypoint makes agents hug walls and corners. Follow the path; advance the waypoint when within radius.
  • Inadmissible A* heuristic (e.g. Euclidean distance scaled up, or Manhattan on a diagonal grid) returns fast but non-shortest paths. Pick the heuristic that matches your allowed moves.
  • Behavior tree leaves that never return RUNNING for multi-frame actions (walking, playing an animation) cause the tree to restart the action every tick. Return RUNNING until the action completes.
  • FSM transition spaghetti: scattering 
    if state == ...
    checks everywhere recreates the mess an FSM exists to prevent. Keep transitions in the state.
  • No line-of-sight or stuck check → agents grind into walls forever. Add a timeout that forces a repath or a state change.
  • 每帧都进行寻路会严重降低帧率。按时间间隔重新计算，或仅当目标移动到新瓦片时重新计算；中间阶段跟随缓存的路径点即可。
  • 直接朝向目标转向而非朝向下一个路径点，会导致角色紧贴墙壁和拐角。应沿着路径移动；当进入路径点范围时切换到下一个路径点。
  • 不可行的A*启发函数（例如放大的欧几里得距离，或在对角网格上使用曼哈顿距离）运算速度快，但返回的不是最短路径。选择与允许移动方式匹配的启发函数。
  • 行为树叶子节点从不返回RUNNING处理多帧动作（行走、播放动画），会导致树每帧都重新启动该动作。动作完成前应返回RUNNING。
  • FSM转换逻辑混乱：到处散布
    if state == ...
    判断，会重现FSM本应避免的混乱。将转换逻辑放在状态内部。
  • 没有视线检测或卡住检查→角色会一直卡在墙上。添加超时机制，强制重新寻路或切换状态。

References

参考资料

  • references/pathfinding.md
    — complete A* (priority queue, reconstruction), grid vs waypoint graphs, when to defer to an engine navmesh.
  • references/behavior-trees.md
    — node taxonomy, leaf/decorator implementations, blackboard, and FSM-vs-BT selection.
  • references/pathfinding.md
    — 完整的A*算法（优先队列、路径重建）、网格与路径点图对比、何时使用引擎navmesh。
  • references/behavior-trees.md
    — 节点分类、叶子/装饰器实现、黑板、以及FSM与行为树的选择。

Related skills

相关技能

  • unity-navmesh
    , 
    unreal-behavior-trees
    — concrete engine AI/navigation APIs.
  • physics-tuning
    — movement, collision response, and agent radius.
  • procedural-gen
    — generating the graph/level the AI navigates.
  • tower-defense
    , 
    fps-shooter
    — genres that compose this skill.
  • unity-navmesh
    , 
    unreal-behavior-trees
    — 具体的引擎AI/导航API。
  • physics-tuning
    — 移动、碰撞响应、角色半径调整。
  • procedural-gen
    — 生成AI导航的地图/关卡。
  • tower-defense
    , 
    fps-shooter
    — 需用到本技能的游戏类型。