引言

前置阅读：建议先阅读向量和距离与检测。

游戏 AI 的核心任务通常是：我知道我在哪，我要去哪，怎么去？ 这涉及两个层面： 1. 宏观寻路: 规划一条从 A 到 B 的路径（A* 算法）。 2. 微观移动: 如何控制速度和方向来沿着路径移动，并避开障碍（操纵行为）。 前半部分解决“走哪条路”，后半部分解决“怎么走得自然、不撞人”。

1. 寻路 (Pathfinding) - A*

A* (A-Star) 是最著名的寻路算法。它结合了 Dijkstra 的广度优先搜索和贪婪最佳优先搜索。 核心公式： \[ F = G + H \]

• G (Cost): 从起点走到当前格子的实际代价。
• H (Heuristic): 从当前格子到终点的估算代价（通常用曼哈顿距离或欧几里得距离）。
• F: 总评分。每次都选择 F 值最小的格子继续探索。

1.1 启发函数 (Heuristic) 的选择

启发函数 \(H\) 的选择直接影响 A* 的效率和路径质量：

准则：启发函数必须不高估实际代价（即 Admissible），否则 A* 不保证最短路径。

1.2 Grid vs NavMesh

A* 通常在网格 (Grid) 上运行，但现代 3D 游戏更常用 导航网格 (Navigation Mesh / NavMesh)：

• Grid：简单直观，适合 2D 或体素世界。缺点是在开阔地形上节点过多。
• NavMesh：将可行走区域划分为凸多边形，只在多边形之间寻路。大幅减少节点数量，适合 3D 场景。

Unity 和 Unreal 都内置了 NavMesh 烘焙工具，实际项目中很少需要自己实现 A*，但理解原理有助于调参和排错。

1.3 Open List 数据结构选择

A* 每一步要从 Open List 取出 F 值最小的节点，数据结构选择对性能影响巨大：

二叉堆是最佳平衡点：插入和弹出都是 O(log N)，且对 CPU 缓存友好。

var openList = new PriorityQueue<Node, float>(); // 二叉堆
openList.Enqueue(startNode, startNode.F);
while (openList.Count > 0) {
    Node current = openList.Dequeue();
    if (current == goal) return ReconstructPath(current);
    foreach (Node neighbor in GetNeighbors(current)) {
        float tentativeG = current.G + Cost(current, neighbor);
        if (tentativeG < neighbor.G) {
            neighbor.G = tentativeG;
            neighbor.F = tentativeG + Heuristic(neighbor, goal);
            neighbor.Parent = current;
            openList.Enqueue(neighbor, neighbor.F);
        }
    }
}

进阶：在均匀网格上，Jump Point Search (JPS) 跳过对称路径来减少展开节点数，速度可达普通 A* 的 10 倍以上，且路径完全等价。

2. 操纵行为 (Steering Behaviors)

一旦有了路径，或者在开放空间中移动，我们需要计算每一帧的力。 Craig Reynolds 在 1986 年提出了著名的 Boids 模型来模拟鸟群。

基本公式： \[ \vec{Steering} = \vec{Desired} - \vec{Velocity} \] \[ \vec{Force} = \text{clamp}(\vec{Steering}, \text{maxForce}) \]

2.1 分离 (Separation)

“别挤我！” 检查周围邻居，计算一个背离它们的向量平均值。距离越近，斥力越大。

2.2 对齐 (Alignment)

“随大流。” 计算周围邻居的平均速度方向（Heading），并尝试转向该方向。

2.3 内聚 (Cohesion)

“别掉队。” 计算周围邻居的平均位置（Center of Mass），并尝试向该点移动。

代码实现 (Seek 行为) — 所有操纵行为的基础：

Vector3 Seek(Vector3 target) {
  Vector3 desired = (target - position).normalized * maxSpeed;
  Vector3 steering = desired - velocity;
  return Vector3.ClampMagnitude(steering, maxForce);
}

void Update() {
  Vector3 force = Seek(targetPosition);
  velocity += force * Time.deltaTime;
  velocity = Vector3.ClampMagnitude(velocity, maxSpeed);
  position += velocity * Time.deltaTime;
  if (velocity != Vector3.zero)
    transform.forward = velocity;
}

3. 组合行为

将上述力加权求和： \[ \vec{F}_{total} = w_1 \vec{F}_{sep} + w_2 \vec{F}_{align} + w_3 \vec{F}_{coh} + w_4 \vec{F}_{path} \] 通过调整权重，可以模拟出鱼群、鸟群甚至僵尸潮的运动模式。

3.1 力的叠加与截断

加权求和后需要归一化吗？通常不需要——用 ClampMagnitude 限制最大力即可。即使权重之和大于 1，clamp 也会自然处理。

但简单 clamp 有个缺点：分离力和路径跟随力方向相反时可能互相抵消，导致 boid 卡住。更好的方案是优先级截断 (Priority-Based Truncation)——按优先级依次”消费”力预算，预算耗尽则忽略低优先级的力：

Vector3 PriorityTruncate(float maxForce) {
    float budget = maxForce;
    Vector3 total = Vector3.zero;
    // 优先级从高到低
    Vector3[] forces = { ObstacleAvoidance(), Separation(),
                         PathFollow(), Alignment(), Cohesion() };
    foreach (var f in forces) {
        if (budget <= 0f) break;
        float mag = Mathf.Min(f.magnitude, budget);
        total += f.normalized * mag;
        budget -= mag;
    }
    return total;
}

高优先级的力（如避障）总能获得完整预算，低优先级的力在”有余力”时才生效。

4. Boids 空间优化

Boids 的三个行为都需要查找”感知半径内的邻居”。每帧对 N 个 boid 做两两距离检查是 O(N²)——1000 个 boid 就不可接受了。

4.1 空间哈希 (Spatial Hashing)

将世界划分为均匀网格，每个 boid 映射到一个格子。查找邻居时只检查当前格子及相邻格子：

int CellSize = perceptionRadius; // 格子大小 = 感知半径
Dictionary<int, List<Boid>> grid = new();

int Hash(Vector3 pos) {
    int x = Mathf.FloorToInt(pos.x / CellSize);
    int z = Mathf.FloorToInt(pos.z / CellSize);
    return x * 73856093 ^ z * 19349663;
}
void Rebuild(List<Boid> allBoids) {
    grid.Clear();
    foreach (var b in allBoids) {
        int key = Hash(b.position);
        if (!grid.ContainsKey(key)) grid[key] = new List<Boid>();
        grid[key].Add(b);
    }
}
List<Boid> GetNeighbors(Boid self) {
    var result = new List<Boid>();
    for (int dx = -1; dx <= 1; dx++)
    for (int dz = -1; dz <= 1; dz++) {
        int key = Hash(self.position + new Vector3(dx, 0, dz) * CellSize);
        if (grid.TryGetValue(key, out var cell))
            foreach (var b in cell)
                if (b != self && Vector3.Distance(b.position, self.position) < CellSize)
                    result.Add(b);
    }
    return result;
}

格子大小设为感知半径是最优选择——太小需检查更多格子，太大则每格 boid 过多。

对于 boid 分布不均匀的场景（一半密集、一半空旷），四叉树 / 八叉树 (Quadtree / Octree) 会自适应细分，效果更好。但大多数游戏中空间哈希因实现简单、缓存友好而成为首选。

5. 行为树与操纵行为

在实际游戏 AI 架构中，操纵行为通常嵌入到行为树 (Behavior Tree) 中作为叶节点。行为树的选择节点 (Selector) 和序列节点 (Sequence) 决定何时激活哪些力，操纵行为负责计算具体的力向量。

例如：敌人行为树可能是”巡逻 → 发现玩家 → 追击（Seek）→ 进入攻击范围 → 攻击”，每个状态对应不同的 steering force 组合。

行为树是一个独立的大话题，这里只需记住：Steering Behaviors 是”肌肉”，Behavior Tree 是”大脑”。推荐阅读 AI for Games (Ian Millington) 了解完整架构。

总结

• A* 解决了”怎么走迷宫”的问题，二叉堆是 Open List 的最佳数据结构。
• Steering Behaviors 解决了”怎么走得自然”的问题。
• 空间哈希让 Boids 从 O(N²) 降到近似 O(N)，是大规模群体模拟的关键。
• 优先级截断比简单加权更鲁棒，保证关键行为（如避障）永远优先。
• 简单的向量加减法就能涌现出复杂的群体智能。

< 上一篇: 随机与噪声 | 回到目录