游戏AI的一些概念

发表于2022-01-09| 分类于游戏开发

游戏AI是游戏开发中非常重要的一环，在很大程度上也决定了游戏性。

这里的AI并不是深度学习、强化学习等理论AI，而是游戏中非玩家控制的角色，在游戏运行时自动做出某些看起来比较智能的行为。

比如笔者比较喜欢的《孤胆枪手》这款游戏，游戏中形形色色的外星怪物，会源源不断地朝玩家涌来，试图攻击并杀死玩家，在玩家控制角色移动位置后，怪物也会自动调整行动路线并继续攻击。这些怪物就是比较典型的游戏智能体。

因此，本文主要研究游戏AI中涉及到的概念，以及一些基础功能的研究和实现。

参考 *《游戏人工智能编程案例精粹》 *《代码本色：用编程模拟自然系统》

Game AI Pro
游戏AI 这个系列的文章看起来写的非常好
https://www.bilibili.com/video/BV1pN411f794
https://www.bilibili.com/video/BV1P4411J75m

传统游戏AI的做法是通过规则驱动的思路来实现，即设计出角色在不同情况下的行为逻辑，再通过角色控制的接口，配合动画实现具体角色行为。

游戏AI大概可以分为下面三个阶段

感知器，收集各种参数用来做决策
做决策的系统，根据感知器获得的数据决定如何处理
行动模块，根据决策采取对应的行动

换句话说，游戏AI基本上都是程序员预先定义编写好可能发生的行为，甚至可以理解为是一堆很大的if..else。如何优雅的管理这些条件判断，以及更方便地进行扩展，就是游戏AI最需要做的事情。

主流的方式是通过有限状态机和行为树来实现，下面会逐一介绍。

1. 有限状态机 FSM

参考

状态模式、有限状态机与 Unity版本实现

1.1. 状态类

下面展示了一个红绿等的状态切换，每按一次切换键，会依次按照green->yellow->red循环切换，

enum LightColor {
    green = "green",
    yellow = "yellow",
    red = "red",
}

let color = LightColor.green;
const click = () => {
    if (color === LightColor.green) {
        color = LightColor.yellow;
        console.log("警告~");
    } else if (color === LightColor.yellow) {
        color = LightColor.red;
        console.log("危险~");
    } else if (color === LightColor.red) {
        color = LightColor.green;
        console.log("安全~");
    }
};

click();
click();
click();
click();
click();

这种写法看起来很直观，但if...else的缺点也很明显：当状态逐渐变多，这里的代码就变得难以维护。

可以看出，状态的切换公式大概是：当某种事件触发时，会将旧状态转换成新状态，同时产生一些副作用

newState（新状态） + effect（副作用，上面是打印） = state（旧状态） + event（触发事件）

因此可以对state进行抽象

class Light {
    currentState: State;

    update() {
        if (this.currentState) {
            this.currentState.excute();
        }
    }
    changeState(state: State) {
        this.currentState = state;
    }
}

abstract class State {
    light: Light;
    constructor(light: Light) {
        this.light = light;
    }
    abstract excute(): void;
}

class RedState extends State {
    excute() {
        this.light.changeState(new GreenState(this.light));
        console.log("安全~");
    }
}
class GreenState extends State {
    excute() {
        this.light.changeState(new YellowState(this.light));
        console.log("警告~");
    }
}
class YellowState extends State {
    excute() {
        this.light.changeState(new RedState(this.light));
        console.log("危险~");
    }
}

const ligth = new Light();
ligth.changeState(new GreenState(ligth));

// 事件触发状态的更新
function click() {
    ligth.update();
}
click();
click();
click();
click();
click();

我们将每种状态都抽象成单独的 State，并由 state 对象处理其变化逻辑，这样，当状态逻辑修改时，改动的范围就会小很多。

有时候还需要在状态切换前后执行一些逻辑，可以在State基类上在实现enter和exit方法，然后在changeState的时候调用

class Light {
  changeState(state: State) {
    if(this.currentState) {
      this.currentState.exit()
    }
    this.currentState = state
    this.currentState.enter()
  }
}
// 每个State子类自己实现enter和exit方法即可

在上面我们的状态实例维持了一个light实例的引用，在部分场景下可以通过参数的形式来替换

class RedState extends State {
    excute(light: Light) {
        light.changeState(new GreenState(light));
        console.log("安全~");
    }
}

这样做的好处是 State 与 Light 对象完全解耦，因此每个状态都可以通过单例的形式在多个 light 的共享，节省创建实例的开销。

但单例的缺点也很明显，那就是无法保存Light实例的单独数据和属性，至于采取哪种方式就看具体场景了。

1.2. 状态机

上面的例子展示了每种状态单独切换的场景，在实际的场景中，状态之间的切换可能更复杂一些。

通常把所有与状态相关的数据和方法封装到一个StateMachine类中，可以使设计更为简单。

比如玩家控制的角色有一把枪，包含待机、装弹、射击、子弹耗光等多种状态，相较于把这些状态放在角色类，不然单独实现一个枪的StateMachine类，通过委托它管理当前枪的状态。

// 状态机模板类
class StateMachine<T> {
    owner: T
    currentState: State
    constructor(owner: T) {
        this.owner = owner
    }
    setCurrentState(state: State) {
        this.currentState = state
        this.currentState.enter()
    }
    changeState(state: State) {
        if (this.currentState) {
            this.currentState.exit()
        }
        this.currentState = state
        this.currentState.enter()
    }
    update() {
        if (this.currentState) {
            this.currentState.excute()
        }
    }
}

class Gun {
    stateMachine: StateMachine<Light>
    constructor() {
        this.stateMachine = new StateMachine(this)
          // 初始化状态
        this.stateMachine.setCurrentState(new HoleOnState())
    }
    update() {
        this.stateMachine.update()
    }
}

同理，在Gun相关的状态类中，也需要获取Gun实例的stateMachine，然后执行状态切换的逻辑。这样Gun实例就无需关心具体的状态切换了。

前面提到了，当执行某些事件时，会触发状态的更新，从而执行对象的相关逻辑。在实际开发场景中，事件驱动是更常用的做法，即通过事件广播给游戏中相关的对象，然后监听了相关事件的对象就可以做出状态切换的动作。

2. 行为树

参考

2.1. 行为树

参考AI行为树的工作原理，这篇文章写得很好，建议移步阅读。下面是一些整理。

行为树是一棵用于控制 AI 决策行为的、包含了层级节点的树结构。

树的最末端——叶子，就是这些 AI 实际上去做事情的命令；
连接树叶的树枝，就是各种类型的节点，这些节点决定了 AI 如何从树的顶端根据不同的情况，来沿着不同的路径来到最终的叶子这一过程。

当每次需要找出一个行为的时候，会从树的根节点出发，遍历各个节点，找出第一个和当前数据相符合的行为，因此行为树有固定的遍历顺序(类似于先序遍历，某些类型的节点会影响遍历顺序)。

在遍历时，每个节点会返回success、fail或pending之一作为结果，这些状态可以决定行为树的走向，也就可以控制AI按照预期以某种顺序执行行为树中的行为。

流程大概就是这样。接下来看看节点的类型，一共有三种节点类型

组合节点-Composite

组合节点通常可以拥有一个或更多的子节点，这些子节点会按照一定的次序或是随机地执行，最常见的是Sequence次序节点，

当所有子节点都返回 success 时，这个组合节点返回 success
只要有一个子节点返回 fail，则这个组合节点返回 fail

修饰节点-Decorator

修饰节点只拥有一个子节点，一般用来修改子节点返回结果，或者用来重复执行、终止子节点等功能

叶子结点-Leaf

叶子节点没有子节点，用来承载具体的行为逻辑。类似于if (xxx) { do xxx}中间的do xxx。

叶子结点可以包含参数，用于处理具体的逻辑。这些参数可以从黑板得到，下面会介绍。

此外某些叶子节点还可以调用其他行为树，当前行为树的数据传给对方，这样就可以更模块化地设计行为树并复用。

下图展示了一个比较复杂的行为树

2.2. 黑板

黑板（Blackboard）是一种数据集中式的设计模式，主要用于多模块之间的数据共享，非常适合作为行为树的节点数据来源。

当一个行为树被调用时，一个数据上下文（黑板）也被创建出来，节点可以读取和修改黑板上的数据（具体作用根据节点类型来确定）。

比如一个友军NPC准备攻击最近的敌人，除了自身的位置外，还需要遍历敌人列表，找到距离最近的敌人。这个敌人列表的数据，就需要从黑板上读取。

2.3. 库

在npm上面随便搜了一下，发现BehaviorTree.js貌似可以实现一个简单的行为树。

下面直接演示一下示例代码

const { BehaviorTree, Sequence, Task, SUCCESS, FAILURE } = require('behaviortree')

// 注册一些全局的叶子节点
BehaviorTree.register('bark', new Task({
  run: function (dog) {
    dog.bark()
    return SUCCESS
  }
}))

// 一个sequence节点，按顺序遍历叶子节点
const tree = new Sequence({
  nodes: [
    'bark', // 对应上面注册的bark节点
    new Task({
      run: function (dog) {
        dog.randomlyWalk()
        return SUCCESS
      }
    }),
    'bark',
    new Task({
      run: function (dog) {
        if (dog.standBesideATree()) {
          dog.liftALeg()
          dog.pee()
          return SUCCESS
        } else {
          return FAILURE
        }
      }
    })
  ]
})

// Dog类，提供AI的具体行为
class Dog {
  bark () {
    console.log('*wuff*')
  }

  randomlyWalk () {
    console.log('The dog walks around.')
  }

  liftALeg () {
    console.log('The dog lifts a leg.')
  }

  pee () {
    console.log('The dog pees.')
  }

  standBesideATree () {
    return true
  }
}

const dog = new Dog() // the nasty details of a dog are omitted

const bTree = new BehaviorTree({
  tree: tree,
  blackboard: dog // 黑板上面的数据会在Task run方法中传入
})

// The "game" loop:
setInterval(function () {
  bTree.step()
}, 1000/60)

在游戏循环开始之后，就会一次次的遍历行为树。

3. 路径规划

自动寻路是AI策略中一个重要分支。

路径规划的目的并不是要找到最近且效率最高的路径，而是在效率和消耗方便取的一个平衡，获得一个较优的路径规划即可。

参考

PathFinding.js，这个项目直观地演示了路径规划
游戏AI之路径规划

3.1. A*寻路

在2D游戏和没有高度的3D游戏中，最常规的寻路算法就是A*寻路法，其大致思路就是Dijkstra算法结合贪心思想

参考：javascript-astar。

var graph = new Graph([
  [1,1,1,1],
  [0,1,1,0],
  [0,0,1,1]
]);
var start = graph.grid[0][0];
var end = graph.grid[1][2];
var result = astar.search(graph, start, end);

在战棋游戏、网格地图等场景下，A*寻路可以非常方便地解决这些问题。

3.2. B* 寻路算法

Branch Star分支寻路算法，传说效率比A*寻路还要快很多。这个算法启发于自然界中真实动物的寻路过程，并加以改善以解决各种阻挡问题，其思路类似于水往地处流

直接朝目标点移动，若遇到障碍则尝试绕行
绕开障碍后重复上述步骤

可以看出这种方式获得的路径可能并不是最优的，比较适合简单障碍的地图或不知道地图信息的尝试摸索寻路。

3.3. NavMesh导航网格

navMesh主要用于3d寻路中，这里暂不深究了。

参考

Cocos Creator3.x NavMesh导航网格寻路

4. 一个例子

TODO

5. 小结

本文主要整理了游戏AI中用到的一些技术，后面在项目开发中会逐渐补充。