实现简易而强大的游戏AI——FSM,有限状态机

在很久很久以前,受限于计算机性能和图形效果,游戏往往是以玩家为唯一主动对象的,玩家发出动作,游戏响应结果。除此之外,不需要系统在玩家没有发出动作时产生响应。可以说,玩家的动作与游戏是“同步”的。

随着计算机的处理能力的发展,更绚丽的游戏逐渐产生。玩家就不能只满足盯着屏幕上静态的一张张图片进行游戏。也就是说,游戏应该有自己的方式能够与玩家主动沟通。这样才能使游戏更加生动,虚拟的环境显得更加真实。游戏上非玩家角色(NPC)应该有着自己独立的动作。

像星际争霸这类RTS游戏推动了游戏AI产业的发展。游戏AI的编写方法也逐渐规范。

最早,游戏AI往往是这样写的:

switch(自己){  
    case "血量充足":
        打怪();
        break;
    case "快死了":
        补血();
        break;
    case "死了":
        游戏全局->Gameover();
        break;
}

血量充足就要去打怪,快死了就补血,彻底死了游戏就结束。 把这个代码放到一个无限死循环里头,好了,这个游戏AI就算做成了。把这东西放到代码里头,提交,然后等老板发工资。

但是老板突然说:“你这个AI写的太简单了”。然后又balabala提了一大堆需求: 老板又让你加上这些功能:血量80的时候用魔法补一补就行了,血量60的时候吃个小血瓶,血量40的时候吃大血瓶,血量20的时候赶快逃跑。

然后你又要找到上面这个switch,然后修改里头的case。想象一下,万一你碰到了一个Dota高手当老板,心中有着各种很NB的杀敌策略,你需要虽是根据环境判断利用那种策略。策略越来越多,很快,一个带有上万行代码的函数就横空出世了!如果这个时候遇到bug了,先别说怎么改了,光把这个几M的源代码打开都够费劲的吧?然后,然后你就没有然后了。。。

上面的方法在遇到大量的状态(State)的时候会让代码崩溃,好在有无数前辈前仆后继用各种切身体会帮我们提出了一种又一种精简代码的手段。

不知大家有多少人学过数字电路。学过里面的“状态图”? 在时序电路里头,一个系统往往由一堆状态组成,从状态A,通过输入,跳转到状态B。这就是状态图。例如下面的图片:

上面这种方法就被称作“有限状态机”(FSM,Finite State Machine)。那么究竟什么是FSM?

FSM是一种数据结构,它由以下几个部分组成:

  1. 内在的所有状态(必须是有限个)
  2. 输入条件
  3. 状态之间起到连接性作用的转换函数

为什么要用FSM?

因为它编程快速简单,易于调试,性能高,与人类思维相似从而便于梳理,灵活且容易修改

FSM的描述性定义

一个有限状态机是一个设备,或是一个模型,具有有限数量的状态。它可以在任何给定时间根据输入进行操作,使得系统从一个状态转换到另一个状态,或者是使一个输出或者一种行为的发生,一个有限状态机在任何瞬间只能处于一种状态。

挖掘状态

例如我们有这样一个场景。玩家控制一个Hero打怪练级。这个英雄等级不够没啥经验带上典型的阿Q精神,所以基本上只有这三个动作:

  1. 平时的状态是巡逻,就是漫无目的的走。。。
  2. 如果遇到敌人之后大量一下敌人。
  3. 如果敌人比自己弱小,那就打。
  4. 如果敌人比自己强大,那就跑。

根据上面的需求我们能画出这样一张状态图:

我对FSM的基本解释:一个智能体,在有规则的时间间隔内询问现在所掌握的环境数据,使得它能够基于从游戏环境中接受到的刺激进行必要的状态转换。每一个状态可以模型化为一个分离的对象,或者存在于智能体外部的函数。

这样,FSM提供给了我们一个清楚灵活的结构。

FSM一般骨架代码

一般FSM中需要有以下几个类作为一种数据框架:

  • FSMState类:抽象类,表示基本状态,所有状态都应该继承自这个类
  • FSM类:一台有限状态机
  • FSMAIControl类:存放有限状态机,通常就是游戏AI的主循环。并且能存放环境感知数据等内容。

下面是C++伪代码:

class FSMState{  
public:  
    string stateName = '';
    void enter(FSM * fsm) = 0;
    void exit(FSM * fsm) = 0;
    void update(FSM * fsm) = 0;
    void init(FSM * fsm) = 0;
    FSMState *checkTransition(FSM * fsm) = 0;
};

class FSM{  
private:  
    FSMState * currentState;
public:  
    void init(FSMState * initState){ //初始化状态
        this->currentState = initState;
        this->currentState->init();
        this->currentState->enter();
    }
    void update(){
        this->currentState->update(this); // 执行当前状态的操作
        FSMState * newState = this->currentState->checkTransition(this);
        if(this->currentState->stateName == newState->stateName){ //转换前后两个状态相同

        }else{ //转换前后两个状态不同
            this->currentState->exit();
            this->currentState = newState;
            this->currentState->init();
            this->currentState->enter();
        }
    }
};

例如上文中我们打怪练级的例子

class Monster: FSM{ //怪物类,继承自FSM  
public:  
    Monster(FSMState * initState){//构造函数中初始化一个状态
        this->init(initState);
    } 

    // Monster自身的数据
    int attackPower; // 攻击力
}

class FSMAIController{ //控制类,可以是主循环、定时器等等,一般由系统提供  
    vector <FSM*> fsms; //有多个状态机(多个AI角色)
    while(定时器触发){
        for (items in fsms){ //遍历每一个状态机
            items->update();
        }
    }
}

// 下面就是各种状态类
class StatePatrol: FSMState{ //巡逻状态  
public:  
    string stateName = 'patrol';
    void enter(FSM * fsm){};
    void exit(FSM * fsm){};
    void update(FSM * fsm){
        进行巡逻();
    };
    void init(FSM * fsm){};
    FSMState *checkTransition(FSM * fsm){
        if(发现敌人,而且比自己弱)
            return new StateAttack(); //进入攻击状态
        if(发现敌人,但比自己强)
            return new StateRun(); //进入逃跑状态
    };
}

class StateAttack: FSMState{ //攻击状态  
public:  
    string stateName = 'attack';
    void enter(FSM * fsm){};
    void exit(FSM * fsm){};
    void update(FSM * fsm){
        攻击敌人();
    };
    void init(FSM * fsm){};
    FSMState *checkTransition(FSM * fsm){
        if(打死敌人了)
            return new StatePatrol(); //进入巡逻状态
        if(血快掉光了)
            return new StateRun(); //进入逃跑状态
    };
}

class StateRun: FSMState{ //逃跑状态  
public:  
    string stateName = 'patrol';
    void enter(FSM * fsm){};
    void exit(FSM * fsm){};
    void update(FSM * fsm){
        逃跑();
    };
    void init(FSM * fsm){};
    FSMState *checkTransition(FSM * fsm){
        if(逃到了安全地带)
            return new StatePatrol(); //重新进入巡逻状态
    };
}

从上面的介绍中我们很容易归纳出一套FSM比较通用的一般步骤:

  1. 确定状态
  2. 列举感知数据
  3. 分别编写状态Update逻辑
  4. 确定转移状态的条件。

Friskit

继续阅读此作者的更多文章