05.游戏AI方法之有限状态机

行为编辑(Behavior authoring) 是，那些不涉及搜索或者学习，只取决于静态特定的表示方法。在游戏开发中，特定行为编辑常见的方法有：有限状态机，行为树和基于效用的AI等。它们在目前的游戏开发中，依然是最流行的一些AI方法。

今天我们来讨论有限状态机(Finite State Machine)。

有限状态机（FSM）

有限状态机在计算机科学中，主要是用在解析文本算法或者编译器将输入代码拆分为可解释符号等。在游戏AI中，我们把任何状态机都叫有限状态机。

有限状态机就是指在单个时间内只能处于某一个状态，当对应的转换条件满足后，会把当前状态转变为另外一种状态。

一个有限状态机有三个主要的部分：

状态存储着某个任务的信息
转换指的是某一种状态改变，需要满足条件
动作处于某种状态后的动作

我们用伪代码来描述这些接口。

下面是状态类的接口，里面有四个方法，三个返回执行的动作列表，一个返回该状态下的转换列表。

class State:
   function getActions() -> Action []
   function getExitActions() -> Action []
   function getEntryActions() -> Action []
   function getTransactions() -> Transaction []

转换接口中的isTriggered是判断是否触发转换。

class Transaction:
    function isTriggered() -> bool
    function getTargetState() -> State
    function getActions() -> Action []

现在我们来定义一个状态机：

class
  StateMachine:
    currentState: State
    currentState: State = initialState
    function update() -> Action []:
        triggered: Transaction = null
        for transaction in currentState.getTransactions():
            if transaction.isTriggered():
                triggered = transaction
                break
        if triggered:
            targetState = triggered.getTargetState()
            actions = currentState.getExitActions()
            actions += triggered.getAction()
            actions += targetState.getEntryActions()
            currentState = targetState
            return actions
        else:
            return currentState.getActions()

顺便写下转换的实现：

这里用了一个Condition类，用来判断是否触发。

class Transaction:
    actions: Action []
    function getAction() -> Action []:
        return actions
    targetState: State
    function getTargetState() -> State:
        return targetState
    condition: Condition
    function isTriggered() -> bool:
        return condition.test()

Condition类的接口：

class Condition:
    function test() -> bool

当然，我们还可以根据需要创建Condition的子类来实现自己的逻辑，这里就不继续了。

吃豆人的有限状态机

在04.《吃豆人》的游戏AI分析中，我们有列出吃豆人的有限状态机。

吃豆人有三个状态和四个转换：

状态：寻找豆子，追击鬼魂和躲避鬼魂

转换：吃下能量药丸，鬼魂不在附近，鬼魂在附近和能量药丸作用消失（鬼魂闪烁）

我们使用C#在Unity来测试

转换和条件测试的实现：

public class Condition{
    public virtual bool Test()
    {
        return false;
    }}
public class Transaction{
    public Condition Condition;
    public State target;}

状态实现：

using UnityEngine;
using System.Collections.Generic;
public class State: MonoBehaviour{
    public List transactions;}
public virtual void Awake(){
    transactions = new List();
    //todo
    //设置你的transactions}
public virtual void onEnable() {
    //todo
    //初始化状态}
public virtual void onDisable() {
    //todo
    //销毁状态}
public virtual void Update(){
    //todo
    //行为逻辑}
public void LateUpdate(){
    foreach (Transaction transaction in transactions)
    {
        if (transaction.Test())
        {
            transaction.target.
enabled = true;
            this.
enabled = false;
            return;
        }
    }}

根据上面的框架，你能写出吃豆人的有限状态机么？总的来说，有限状态机的设计和实现都比较简单，在游戏上广泛使用也证明了它的实用。

但是在一些大规模的游戏中，它的设计会变得极端的复杂，在某些任务上可能会存在一些限制，因为它是静态的，缺乏灵活性和动态性。

更多的实现可以阅读参考资源1的链接，目前正在开发一个游戏demo来测试这些算法，后面会公布项目地址。

参考资源：

https://github.com/QianMo/Unity-Design-Pattern/tree/master/Assets/Behavioral%20Patterns/State%20Pattern

往期回顾：