Finite-State Machine有限状态机理论

 

By 
翻译:Mars

什么是有限状态机。

FSM是一个假设的状态机的计算模型。同一时间只有一个状态被激活,所以状态机必须从一个状态过度到另一个从而执行不同的行为。

FSM组合在一起,从而可以组织和描述一个执行流,从而实现游戏的AI。敌人的大脑,例子,每个状态描述一个行为,攻击或者躲避。

 

FMS_enemy_brain

一个FSM可以通过图来描述,节点代表了状态,边是转换过程。每个边有个提示是何时发生转换,像当玩家接近标签player is near,提示状态机从漫游转换到攻击。

 

计划状态和对应的转换

实现FSM需要状态和转换过程。想象下面的状态,描述一个蚂蚁的行为,当鼠标接近就逃跑,找到叶子就回家,到家就出去找叶子。

fsm_ant_brain.png

需要注意到是,

逃跑只和找叶子链接,找叶子和回家链接。

当蚂蚁在回家的时候,鼠标不会影响到蚂蚁从而使蚂蚁逃跑。

fsm_ant_brain_no_transition.png

 

实现FSM

一个类就可以描述和概括FSM,命名为FSM实例。将每个状态实现为方法或者函数,使用一个属性函数 activeState来决定哪个状态被激活。

public class FSM {
    private var activeState :Function; // points to the currently active state function
    public function FSM() {
    }
    public function setState(state :Function) :void {
        activeState = state;
    }
    public function update() :void {
        if (activeState != null) {
            activeState();
        }
    }
}

因为每个状态都是个function,所以当某个状态激活时,对应的描述状态的方法会被每次游戏更新的时候召唤(调用).

activeState 属性,类型函数,是一个指向函数的指针,它会指向哪个状态的function被调用。

update()必须在FSM类里面的每一帧都调用。从而,调用activeState属性指向的function。这样可以持续更新激活状态的行为。

setStatet()方法会使FSM过渡到新状态,给activeState指向一个新的state function。这个状态函数不必是FSM的成员;可以是外部class的,这样,FSM类会更加范型generic和reusable,复用。

使用FSM类已经讨论过了。是时候实现一个角色的’大脑’了。

之前解释过了蚂蚁将使用利用FSM去控制。

下面是状态和改变的表述,看代码:

FSM of ant brain with focus on the code.

The ant is represented by the Ant class, which has a property named brain and a method for each state. The brain property is an instance of the FSM class:

蚂蚁 Ant class,拥有属性brain,和每个状态的方法。

brain属性是一个FSM的实例。

public class Ant
{
    public var position   :Vector3D; //坐标
    public var velocity   :Vector3D; //速率
    public var brain      :FSM;      //脑子
 
    public function Ant(posX :Number, posY :Number) {
        //初始化坐标,速率,给个FSM脑子
        position    = new Vector3D(posX, posY);
        velocity    = new Vector3D( -1, -1);
        brain       = new FSM();
 
        // Tell the brain to start looking for the leaf.
        // 告诉大脑开始寻找叶子
        brain.setState(findLeaf);
    }
 
    /**
     * The "findLeaf" state. 寻找叶子状态
     * It makes the ant move towards the leaf.
     * 让蚂蚁寻找叶子
     */
    public function findLeaf() :void {
    }
 
    /**
     * The "goHome" state. 回家
     * It makes the ant move towards its home.
     */
    public function goHome() :void {
    }
 
    /**
     * The "runAway" state. 逃跑
     * It makes the ant run away from the mouse cursor.
     */
    public function runAway() :void {
    }
 
    //公共更新函数
    public function update():void {
        // Update the FSM controlling the "brain". It will invoke the currently
        // active state function: findLeaf(), goHome() or runAway().
        //更新FSM控制脑子,它会调用当前的激活状态:findLeaf(),goHome()和runAway().
        brain.update();
 
        // Apply the velocity vector to the position, making the ant move.
        // 作用矢量到坐标,让蚂蚁移动。
        moveBasedOnVelocity();
    }
 
    (...)
}

蚂蚁类也拥有速率,坐标属性,都是通过欧拉积分计算运动, Euler integration.

update()方法会被游戏每一帧调用,所以FSM也会被更新。

为了简单解释,代码使用moveBasedOnVelocity()省略具体实现。更多内容看转向行为Understanding Steering Behaviors 章节。

下面是每个状态的实现,开始于findLeaf(),状态负责指导蚂蚁寻找叶子的坐标:

public function findLeaf() :void {
    // Move the ant towards the leaf.计算方位
    velocity = new Vector3D(Game.instance.leaf.x - position.x, Game.instance.leaf.y - position.y);
 
    if (distance(Game.instance.leaf, this) <= 10) {
        // The ant is extremelly close to the leaf, it's time
        // to go home.足够接近,回家,脑子更新状态回家。
        brain.setState(goHome);
    }
 
    if (distance(Game.mouse, this) <= MOUSE_THREAT_RADIUS) {
        // Mouse cursor is threatening us. Let's run away!
        // It will make the brain start calling runAway() from
        // now on.鼠标威胁到了蚂蚁,规避。脑子调用runAway()
        brain.setState(runAway);
    }
}

goHome()状态,引导蚂蚁回家:

public function goHome() :void {
    // Move the ant towards home 计算回家
    velocity = new Vector3D(Game.instance.home.x - position.x, Game.instance.home.y - position.y);
 
    if (distance(Game.instance.home, this) <= 10) {
        // The ant is home, let's find the leaf again.
        // 到家了,再去找叶子
        brain.setState(findLeaf);
    }
}

最终,runAway()状态,让蚂蚁规避鼠标:

public function runAway() :void {
    // Move the ant away from the mouse cursor
    // 反向计算逃离速率
    velocity = new Vector3D(position.x - Game.mouse.x, position.y - Game.mouse.y);
 
    // Is the mouse cursor still close? 是否还需要逃离
    if (distance(Game.mouse, this) > MOUSE_THREAT_RADIUS) {
        // No, the mouse cursor has gone away. Let's go back looking for the leaf.足够远了就再找叶子。
        brain.setState(findLeaf);
    }
}

最终蚂蚁被FSM脑子控制了:

假设蚂蚁在回家路上也要规律鼠标,FSM更新如下:

看起来改动很小,增加一个新的变化,不过这样会导致一个问题:如果当前是逃离状态,然后鼠标离开了,那么蚂蚁应该是回家还是找叶子?

解决方法是使用基于栈FSM。和现在的FSM不同,使用栈来控制状态。栈顶是激活状态;过渡由压栈和出栈控制:

在过渡中,栈顶的激活状态告诉接下来要做什么。

It can pop itself from the stack and push another state, which means a full transition (just like the simple FSM was doing). It can pop itself from the stack, which means the current state is complete and the next state in the stack should become active. Finally, it can just push a new state, which means the currently active state will change for a while, but when it pops itself from the stack, the previously active state will take over again.

这样,他自身可以通过栈改变状态。

当,当前状态完成,将完成的状态压出。然后新激活状态压入。

这段不翻译了。。绕来绕去。。MDZZ。

基于栈的FSM可以像之前那样实现。

只是需要用函数操作一个数组来控制栈。

activeState属性不再需要了,栈顶指向了当前激活状态。

public class StackFSM {
    private var stack :Array;
 
    public function StackFSM() {
        this.stack = new Array();
    }
 
    public function update() :void {
        var currentStateFunction :Function = getCurrentState();
 
        if (currentStateFunction != null) {
            currentStateFunction();
        }
    }
 
    public function popState() :Function {
        return stack.pop();
    }
 
    public function pushState(state :Function) :void {
        if (getCurrentState() != state) {
            stack.push(state);
        }
    }
 
    public function getCurrentState() :Function {
        return stack.length > 0 ? stack[stack.length - 1] : null;
    }
}

setState() 方法被替换成pushState()和popState();

push会增加新状态到栈,pop移除。两个方法都会让状态极过度到新状态,当他们改变顶部栈的时候。

当使用FSM栈,记得最重要的是,每个状态必须完成自己弹出栈。

状态弹出一般是当这个状态不在需要的时候。比如attack()激活时目标已经死了。就需要自己弹出栈。

拿蚂蚁做例子,只要改一些代码适应FSM栈。就可以解决之前的问题,代码如下:

public class Ant {
    (...)
    public var brain :StackFSM;
 
    public function Ant(posX :Number, posY :Number) {
        (...)
        brain = new StackFSM();
 
        // Tell the brain to start looking for the leaf.
        brain.pushState(findLeaf);
 
        (...)
    }
 
    /**
     * The "findLeaf" state.
     * It makes the ant move towards the leaf.
     */
    public function findLeaf() :void {
        // Move the ant towards the leaf.
        velocity = new Vector3D(Game.instance.leaf.x - position.x, Game.instance.leaf.y - position.y);
 
        if (distance(Game.instance.leaf, this) <= 10) {
            // The ant is extremelly close to the leaf, it's time
            // to go home.
            brain.popState(); // removes "findLeaf" from the stack.
            brain.pushState(goHome); // push "goHome" state, making it the active state.
        }
 
        if (distance(Game.mouse, this) <= MOUSE_THREAT_RADIUS) {
            // Mouse cursor is threatening us. Let's run away!
            // The "runAway" state is pushed on top of "findLeaf", which means
            // the "findLeaf" state will be active again when "runAway" ends.
            brain.pushState(runAway);
        }
    }
 
    /**
     * The "goHome" state.
     * It makes the ant move towards its home.
     */
    public function goHome() :void {
        // Move the ant towards home
        velocity = new Vector3D(Game.instance.home.x - position.x, Game.instance.home.y - position.y);
         
        if (distance(Game.instance.home, this) <= 10) {
            // The ant is home, let's find the leaf again.
            brain.popState(); // removes "goHome" from the stack.
            brain.pushState(findLeaf); // push "findLeaf" state, making it the active state
        }
         
        if (distance(Game.mouse, this) <= MOUSE_THREAT_RADIUS) {
            // Mouse cursor is threatening us. Let's run away!
            // The "runAway" state is pushed on top of "goHome", which means
            // the "goHome" state will be active again when "runAway" ends.
            brain.pushState(runAway);
        }
    }
     
    /**
     * The "runAway" state.
     * It makes the ant run away from the mouse cursor.
     */
    public function runAway() :void {
        // Move the ant away from the mouse cursor
        velocity = new Vector3D(position.x - Game.mouse.x, position.y - Game.mouse.y);
         
        // Is the mouse cursor still close?
        if (distance(Game.mouse, this) > MOUSE_THREAT_RADIUS) {
            // No, the mouse cursor has gone away. Let's go back to the previously
            // active state.
            brain.popState();
        }
    }
    (...)
}

结果就是蚂蚁会逃离鼠标,然后过度到之前激活的状态。

FSM对于实现游戏AI很有用。可以很容易的用图来表示,让开发者看到整个大局,调整,优化最终结果。

实现FSM方法函数表示状态很简单,但是很强。更复杂的结果也可以达到,保证可控,简单执行流程防止负面影响。给你的游戏NPC升级脑子吧。

发表评论

邮箱地址不会被公开。