游戏 AI 进阶

概述

游戏 AI 的目标不是"通用智能"，而是在正确的时间做出让玩家觉得合理的决策。本文介绍的四种技术各有分工：

技术	解决的问题	决策粒度
有限状态机（FSM）	角色处于什么状态、何时切换	状态级
行为树（Behavior Tree）	复杂条件下选择做什么	任务级
A* 寻路	在地图上找到最短可达路径	移动级
NavMesh 导航	在任意多边形地形上导航	移动级

四者可以组合成一条完整的 AI 决策链：FSM 管状态 → 行为树管任务 → A / NavMesh 管移动*。

有限状态机（FSM）

FSM 由一组状态与转移规则构成：角色每个时刻处于一个状态，满足条件时跳转到另一个状态。巡逻、追逐、攻击、逃跑是最经典的 AI 状态组合。

class AI {
  constructor() {
    this.state = 'patrol'
    this.states = {
      patrol:  { enter: () => {},  update: dt => this.doPatrol(dt) },
      chase:   { enter: () => {},  update: dt => this.doChase(dt) },
      attack:  { enter: () => {},  update: dt => this.doAttack(dt) },
      flee:    { enter: () => {},  update: dt => this.doFlee(dt) }
    }
  }
  change(next) {
    if (next !== this.state && this.states[next]) this.state = next
  }
  update(dt) {
    // 状态转移判断
    if (this.state === 'patrol' && this.seePlayer()) this.change('chase')
    if (this.state === 'chase' && this.distToPlayer() < 30) this.change('attack')
    if (this.hp < 20) this.change('flee')
    // 执行当前状态
    this.states[this.state].update(dt)
  }
}

FSM 的优点是简单直观、可预测；缺点是状态爆炸——状态一多，转移表难以维护，行为组合（如"追击中受伤逃跑"）难以表达。

行为树（Behavior Tree）

行为树把决策组织成一棵树：从根节点开始，每个节点返回 Success / Failure / Running，父节点根据子节点结果决定继续或回退。核心节点：

• 选择节点（Selector，?）：从左到右执行子节点，任一成功则整个成功（回退逻辑，"试试看哪条路走得通"）
• 顺序节点（Sequence，→）：从左到右执行，任一失败则整个失败（"必须都完成"）
• 条件节点（Condition）：检查条件，返回成功或失败
• 动作节点（Action）：执行行为，可返回 Running（持续进行中）

Selector（巡逻目标）
├── Sequence（发现敌人）
│   ├── Condition：玩家可见？
│   ├── Action：追逐
│   └── Action：攻击
├── Action：走到巡逻点
└── Action：原地等待

行为树与 FSM 的关键差异在于复用与组合：行为树的节点天然可复用（"追逐"可以被多个 AI 共享），且修改行为只需增删节点，不需要维护转移矩阵。

A* 寻路

A* 是网格地图最常用的寻路算法，在广度优先的基础上引入启发式函数，优先扩展"看起来离终点更近"的格子，大幅减少搜索范围。

核心公式

每个格子维护三个值：

• g：从起点到当前格的实际代价（直线 10，对角 14）
• h：从当前格到终点的预估代价（曼哈顿距离或欧氏距离）
• f = g + h：排序优先级，开放集中每次取出 f 最小的格子扩展

算法步骤

1. 起点放入开放集（待考察），记录 g=0
2. 循环：从开放集取 f 最小的格子；已考察则放入关闭集
3. 若该格是终点，沿父指针回溯得到路径，结束
4. 否则把四个（或八个）相邻可走格子加入开放集，更新 g、h、父指针
5. 开放集为空仍未达终点 → 无可达路径

下面的可运行示例演示了 A* 的完整搜索过程：左键拖拽画墙，红色为终点、黄色为最终路径、蓝色为正在考察的开放集、灰色为已放弃的关闭集。可以直观看到启发式如何让搜索"直奔终点"而不是四面扩散：

优化手段

手段	思路
双向 A*	起点终点同时搜，相遇即停，减少探索量
Jump Point Search	规则网格上跳过无分支的直线段，大幅剪枝
分层寻路	先在高代价层找大方向，再在局部细化
路径平滑	对结果做视线检测拉直，消除折线感
路径缓存	地图静态时缓存路径，AI 复用

NavMesh 导航

A* 在规则网格（Square Grid）上工作，但游戏地图往往是任意形状的多边形（斜坡、洞穴、走廊）。**导航网格（NavMesh）*把可行走区域预先划分成多个凸多边形（三角形为主），寻路时在"多边形图"上做 A，再沿多边形边界做路径跟随。

为什么用多边形而不是网格

维度	网格寻路	NavMesh
地图表达	格子粒度受限于分辨率	多边形贴合任意地形
节点数量	大场景格子数以万计	多边形数远少于格子
寻路速度	快但节点多	节点少，搜索更快
路径质量	折线多，需平滑	天然贴合地形，走位自然
动态障碍	可临时标格	需要重新划分区域

导航流程

1. 生成：美术/编辑器把可行走区域烘焙成三角形网格（如 Unity NavMesh、Recast）
2. 寻路：把起点/终点映射到所在三角形，在三角形邻接图上做 A*，得到三角形序列
3. 路径跟随：沿三角形序列计算出折线路径，AI 逐点移动
4. 避障：多个 AI 同向行进时，用 RVO（速度障碍）等算法互相避让，避免拥堵重叠

与 A* 的组合用法

// 高层决策（行为树）决定"去哪"
const goal = behaviourTree.evaluate()

// 低层移动（NavMesh）负责"怎么去"
const corners = navMesh.findPath(agent.pos, goal)   // 三角形 A* + 折线化
for (const corner of corners) {
  agent.moveTo(corner)
}

决策链组合示例

把四层技术拼成一个完整的 AI：

FSM:      patrol → chase → attack → flee（谁在什么时候做什么）
行为树:   chase 下细分「需要走桥 / 需要绕路 / 直接追」的选择逻辑
A*/NavMesh: 计算到达目标点的实际移动路线
RVO:     与其他单位相遇时平滑避让

层级分离让每一层都能独立测试：寻路错误查 NavMesh，行为错误查行为树，状态错乱查 FSM——这也是商业引擎把 AI 拆成多个组件的设计动机。