游戏AI的一些概念

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

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

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

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

<!--more-->

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

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

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

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

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

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

1. 有限状态机 FSM

参考

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基类上在实现enterexit方法,然后在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 如何从树的顶端根据不同的情况,来沿着不同的路径来到最终的叶子这一过程。

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

在遍历时,每个节点会返回successfailpending之一作为结果,这些状态可以决定行为树的走向,也就可以控制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策略中一个重要分支。

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

参考

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*寻路还要快很多。这个算法启发于自然界中真实动物的寻路过程,并加以改善以解决各种阻挡问题,其思路类似于水往地处流

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

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

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

参考

4. 一个例子

TODO

5. 小结

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

关于TailwindCSS的一些思考记一次CI构建优化