译者这次的排版增加了缩进,结果看起来很怪异,以后不添加了。
坦白说,我在这一章节有点激动了然后摆出了很多很多的内容.。表面上这个章节是在讲State模式,,但如果想讲State,我必须得深入更基础的有限状态机(finite state machine)的概念, 而当我们深入时,又必须要介绍 层次状态机(hierarchical state machine)和下推自动机(pushdown automata) 。
三言两语肯定讲不完上面这一大堆,所以下面的代码样例留空了很多,你应该靠自己去填补。但我希望这些代码能够讲明白大致的结构。
没学过状态机也不用怕。AI和编译器大牛们可能对它了然于胸,但其他的编程圈子未必能够了解一二。我觉得状态机应该要让更多的人学习到,所以这里我要为状态机抛出一个完全不同的问题。
AI和编译器的搭配呼应了早期的人工智能,50和60年代,大部分AI研究人员专注于语言处理。而许多编译器使用的是给自然语言使用的语法分析技术。
我们都是这么过来的
现在我们要做一个横板卷轴的平台跳跃游戏。我们要把主人公,也即是玩家的头像实现在游戏里。主人公需要对玩家输入做出响应。按B键跳跃。挺简单的:
void Heroine::handleInput(Input input)
{
if (input == PRESS_B)
{
yVelocity_ = JUMP_VELOCITY;
setGraphics(IMAGE_JUMP);
}
}
发现Bug了嘛?
你没有限制“空跳”——一直按B角色就会一直悬在空中。可以在Heroine类中加入isJumping_
这个布尔字段进行简单的修复:
void Heroine::handleInput(Input input)
{
if (input == PRESS_B)
{
if (!isJumping_)
{
isJumping_ = true;
// Jump...
}
}
}
这里还应该增加把isJumping_设置为false的代码,我这里为了简洁起见给省去了。
下一步,我们要让角色在玩家按下↓键是下蹲,释放↓键时站起。
void Heroine::handleInput(Input input)
{
if (input == PRESS_B)
{
// Jump if not jumping...
}
else if (input == PRESS_DOWN)
{
if (!isJumping_)
{
setGraphics(IMAGE_DUCK);
}
}
else if (input == RELEASE_DOWN)
{
setGraphics(IMAGE_STAND);
}
}
这次发现Bug了嘛?
在这段代码里,如果你:
- 按↓下蹲
- 按B从下蹲的位置跳跃
- 在角色还在空中时释放下蹲键
角色就会在跳跃时切换到站立的图像(译者我咋觉得这是个feature不是bug哈哈),是时候加flag了:
void Heroine::handleInput(Input input)
{
if (input == PRESS_B)
{
if (!isJumping_ && !isDucking_)
{
// Jump...
}
}
else if (input == PRESS_DOWN)
{
if (!isJumping_)
{
isDucking_ = true;
setGraphics(IMAGE_DUCK);
}
}
else if (input == RELEASE_DOWN)
{
if (isDucking_)
{
isDucking_ = false;
setGraphics(IMAGE_STAND);
}
}
}
下一步, 要是能在跳跃过程中按↓键让角色进行天降正义的俯冲攻击就厉害了…
void Heroine::handleInput(Input input)
{
if (input == PRESS_B)
{
if (!isJumping_ && !isDucking_)
{
// Jump...
}
}
else if (input == PRESS_DOWN)
{
if (!isJumping_)
{
isDucking_ = true;
setGraphics(IMAGE_DUCK);
}
else
{
isJumping_ = false;
setGraphics(IMAGE_DIVE);
}
}
else if (input == RELEASE_DOWN)
{
if (isDucking_)
{
// Stand...
}
}
}
再来捉一捉虫子,找到没?
我们没有在下坠冲刺时检查空跳,又要添加字段了……
上面有些做法是显然不正确的。而每当修改这段代码时都会破坏代码结构。我们得增加一大堆动作,这还没算上 行走 的动作呢,照这样下去,游戏还没开发完Bug就满天飞了。
你理想中那位永远都能写出完美无瑕代码的人不只是个超级程序员那么简单。他们有着对出错倾向代码的嗅觉,进而避离开这些代码。
复杂分支和多重状态——不断改变的字段——是两种容易出错的代码类型,上面的样例把这两样占全了。
有限状态机救场
一顿焦头烂额之后,你理清了除了纸笔之外的桌子上的杂七杂八,然后开始画起了流程图。你给角色的每个行为都画了一个方盒子,代表:站立、跳跃、下蹲和下坠(空中加速降下)。当角色能够对这些状态的按键输入做出响应时,你就画出了从一个盒子到另一盒子的箭头,并用相应的按键作为标记。
干得漂亮,你已经做出了一个有限状态机(finite state machine)。这些来自于计算机科学中的一个分支:自动机理论,同族的数据结构中也包括了著名的图灵机。有限状态机(以下简称FSM)是这一家族中最简单的成员。
FSM的要旨如下:
- 状态机能够处理的状态集合须是固定的。在我们的例子中就是站立、跳跃、下蹲和下坠。
- 状态机在同一时刻只能处于一个状态。我们的角色不能同时进行跳跃和站立。实际上这也是我们使用FSM的原因。
- 状态机能够接收一系列的输入或事件。在本例中即为按键下压和释放。
- 每个状态都有一个过渡(transitions)集合,每个过渡都与输入相联系且指向某一状态。如果状态机接收的输入满足其当前状态的某个过渡,那么状态机就会转变为该过渡指向的状态。例如,在站立状态按↓键会过渡到下蹲状态;在跳跃时按↓键会过渡到下坠状态。如果当前状态接收的输入没有相关过渡对应,则该输入会被忽略。
译者 transition即状态转移中的那个“转移”,但我不想这么翻译。
纯粹形式上来说就这么几样东西:状态、输入、以及过渡。你可以把它们画成流程图,可惜编译器不会识别我们这样的涂鸦描述,那我们该如何实现它呢?设计模式四人组的State模式提供了一种方法——后面我们会提到它——先从简单点儿的开始。
我最爱给FSM打的比方是像Zork这样有些年头的文字冒险游戏。游戏里存在着一些彼此通过“出口”相连的房间,你通过输入像“去北边”这样的命令来探索这些房间。
这正好映射到了状态机身上:每个房间就是一个状态。你所在的房间就是当前状态,每个房间的出口就是过渡。而用以导航的命令则是输入。
枚举和Switch
Heroine类存在的一个问题是,它拥有一些能够组合,却不可以同时为true
的Boolean字段,比如isJumping_
和isDucking_
永远不能同时为true
。当你每次只有一个标记可以为true的时候,你应该意识到要使用枚举了。
在上面的例子中,这里的枚举恰好是FSM的状态集合,定义为:
enum State{
STATE_STANDING,
STATE_JUMPING,
STATE_DUCKING,
STATE_DIVING
};
我们使用一个state_
字段来代替之前的一堆boolean
字段的标记,并且调整了分支语句的顺序。在先前的代码中我们是先判断输入再判断状态。这使得代码能够把按键输入的处理逻辑进行整合,但各个状态也弥散四处。而我们想要对状态进行统一处理,因此要把状态提前。代码如下:
void Heroine::handleInput(Input input)
{
switch (state_)
{
case STATE_STANDING:
if (input == PRESS_B)
{
state_ = STATE_JUMPING;
yVelocity_ = JUMP_VELOCITY;
setGraphics(IMAGE_JUMP);
}
else if (input == PRESS_DOWN)
{
state_ = STATE_DUCKING;
setGraphics(IMAGE_DUCK);
}
break;
case STATE_JUMPING:
if (input == PRESS_DOWN)
{
state_ = STATE_DIVING;
setGraphics(IMAGE_DIVE);
}
break;
case STATE_DUCKING:
if (input == RELEASE_DOWN)
{
state_ = STATE_STANDING;
setGraphics(IMAGE_STAND);
}
break;
}
}
上面的改动乍看没什么,却着实提升了其代码质量。我们仍然有一些分支语句,但多个状态现在成为了一个字段,对于单一状态进行处理的所有代码都被聚合在了一起。这是实现状态机最简单的,同时也是用户友好的方式。
具体说来, 游戏主角不再拥有无效的状态了。使用
boolean
字段的可能会出现没有意义的某些状态的值的集合,而使用枚举,每一个值都是有效的。
但问题可能总要比办法多。假设我们添加了这样一个动作:角色下蹲一段时间来进行蓄力,释放下蹲进行蓄能攻击。当角色下蹲时,我们需要追踪蓄力时间。
我们来给角色的类添加一个chargeTime_
字段来存储蓄力攻击的时间。假设update()
方法每一帧都会调用,这个方法里添加如下代码:
void Heroine::update()
{
if (state_ == STATE_DUCKING)
{
chargeTime_++;
if (chargeTime_ > MAX_CHARGE)
{
superBomb();
}
}
}
要是你觉得这就是Update Method 模式, 恭喜你中奖了!
我们还要在进行下蹲时重置计时,因此调整一下handleInput()
:
void Heroine::handleInput(Input input){
switch(state_){
case STATE_STANDING:
if(input == PRESS_DOWN){
state_ = STATE_DUCKING;
chargeTime_ = 0;
setGraphics(IMAGE_DUCK);
}
// Handle other inputs...
break;
// Other states...
}
}
总地来说,要加入蓄力攻击,就不得不修改两个方法并且向Heroine加入cahrgeTime_
字段,尽管该字段只有在下蹲状态才会真正使用到。而我们更倾向于把所有这样的代码和数据包装到一个地方。设计模式四人组帮了我们一把。
状态(机)模式
对于深入面向对象思想的人来说,每一个条件分支都是一次动态调度的机会(换句话讲就是C++里的虚函数调用)。而我觉得那样只会越陷越深,有时一个if就足够了。
这一点是有着历史基础的。许多最初的面向对象信众们,比如“设计模式”的作者四人组和从SmallTalk过来写了“重构”一书的Martin Fowler[1]。 那样的话,(分支)只是你在条件中唤起的一个方法,它的实现取决于
true
和false
对象.
但我们的例子已经达到了使用面向对象的临界点了。我们需要去使用State模式。引述设计模式四人组的话来说:
允许一个对象在其内部状态发生变化时改变自身行为。看起来就像是该对象改变了自己的类一样。
这句话其实啥也没说,我们的switch
语句不就做了这个工作了嘛。他们所描述的具体设计模式在应用于我们的角色身上时是这样的:
状态接口
首先来为 状态 定义一个接口。 每种行为都是状态相关的——先前代码中的switch
——成为了接口中的一个个虚方法。也就是我们的handleInput()
和update()
:
class HeroineState{
public:
virtual ~HeroineState() {}
virtual void handleInput(Heroine& heroine, Input input){}
virtual void update(Heroine& heroine){}
};
状态类
为每一个state定义一个实现了上述接口的类。其方法定义了角色在处于相关状态时的具体行为。换句话说就是提取switch
语句中的case
到方法体中。例如:
class DuckingState:public HeroineState{
public:
DuckingState():chargeTime_(0){}
virtual void handleInput(Heroine& heroine, Input input){
if(input == RELEASE_DOWN){
heroine.setGraphics(IMAGE_STAND);
}
}
virtual void update(Heroine& heroine){
chargeTime_ ++;
if(chargeTime_ > MAX_CHARGE){
heroine.superBomb();
}
}
private:
int chargeTime_;
};
注意chargeTIme_
从Heroine
挪到了DuckingState
中。这样做的好处是数据只在处于该状态的时候才有意义,而且现在的对象模型反映了更精确的情况。
状态委托
下一步,在Heroine
中添加指向其当前状态的指针,将庞大的switch
语句委托给了state。
class Heroine
{
public:
virtual void handleInput(Input input)
{
state_->handleInput(*this, input);
}
virtual void update()
{
state_->update(*this);
}
// Other methods...
private:
HeroineState* state_;
};
想要改变角色的状态只需将state_
变量重新赋值使其指向不同的HeroineState
实例即可。State 模式完整地展现其中。
这看起来就像时Strategy和Type Object模式. 而加上State模式, 以上三种设计模式都囊括了一个主要的对象, 而这个主对象对其他的次要对象有委托行为. 但这些模式的意图是不同的.
- Strategy模式旨在为主对象的某部分行为进行解耦.
- Type Object意图使多个对象共享同一类型对象的引用进而表现相似的行为.
- State模式的目的则是通过改变被委托的对象来改变主要对象的行为.
状态对象在哪里?
现在我未说明的一点是,在改变状态的时候需要将state_
指向新的state对象,但该对象是从何处而来的呢?当我们使用enum的实现时,解决方式比较无脑——枚举值只是数字这样的原始数据类型。可是现在的state都有了类,也就是说我们需要实际存在的实例来指向。对于这一点,有两种常见的解决方式:
静态化状态
如果一个state对象没有其他任何字段的话,那么它所有的数据就只是指向内部虚函数表的指针。在本例中,我们只需要单一实例即可。反正每个实例都是完全一样的。
如果你定义的state除了唯一一个虚方法就没有其他任何字段的话, 这个设计模式其实可以进一步简化。把每一个state类换成state方法——原版的顶级方法。然后在你的主类中的
state_
字段就变成了函数指针。译者或许在某些语言里也可以用closure实现?
这样的话你可以创建一个static的实例。即使是你同时拥有多个包含该状态的FSM,因为没有状态机特别指明的地方,他们都指向同一个实例。
这就是Flyweight(享元)模式。
static实例的放置位置并无太多要求,合理即可。比方说放在state基类里:
class HeroineState{
public:
static StandingState standing;
static DuckingState ducking;
static JumpingState jumping;
static DivingState diving;
// Other code...
};
这里的每个静态字段都是游戏使用的状态实例。要让角色跳跃,则standing状态要做的是。
if(input == PRESS_B){
heroine.state_ = &HeroineState::jumping;
heroine.setGraphics(IMAGE_JUMP);
}
实例化状态
上述解决方式有时也并不奏效。静态的state对于下蹲状态不好使。因为它具有chargeTime_
这一字段,这在角色进行下蹲时是具体到角色的。如果游戏仅有一个角色还好说,可如果要添加双人竞技/合作模式就要出问题的。
这种情况下,我们不得不在转换状态的时候创建state对象。当然,分配新的state意味着释放当前的state。必须要小心行事,因为引发状态变化的代码是在当前state的方法中的。我们并不想把当前对象在其本身外删除。
替代方式是我们允许handleInput()
可以返回新状态实例。当返回新实例时,旧的会被删除,而当前state会切换到新实例。
void Heroine::handleInput(Input input){
HeroineState* state = state_->handleInput(*this, input);
if(state != NULL){
delete state_;
state_ = state;
}
}
这样在返回新实例前我们不会删除旧有的实例。现在,从站立状态到下蹲状态需要创建新的实例。
HeroineState* StandingState::handleInput(Heroine& heroine,
Input input)
{
if (input == PRESS_DOWN)
{
// Other code...
return new DuckingState();
}
// Stay in this state.
return NULL;
}
我更倾向于尽可能使用静态的的state,,这样就不必每当状态变更时去消耗动态分配内存的资源。 而且state本身就蕴含了一层stateful这种表示静态状态的意义。
当你为state动态分配内存时, 可能回带来分片问题. Object Pool模式可供帮助.
进入和退出
State模式的目标是把所有行为和数据封装在单个state的类里。我们已经略有小成,但仍需打磨。
当游戏角色变更状态时我们就改变动画。当前这一部分的代码还处于角色变更前装填的控制下。当角色从下蹲到站立的状态时转换时,下蹲的状态会这样设置图像:
HeroineState* DuckingState::handleInput(Heroine& heroine, Input input){
if(input == RELEASE_DOWN){
heroines.setGraphics(IMAGE_STAND);
return new StandingState();
}
//OtherCode...
}
而我们想要的是每个类各行其道,只控制自身对应的图像。可以通过赋给state一个 进入 动作来完成这一需求(译者虽然还是耦合在具体的State类中,但至少不是在输入处理那块了,enter的调用是在基类的虚方法里):
class StandingState : public HeroineState
{
public:
virtual void enter(Heroine& heroine)
{
heroine.setGraphics(IMAGE_STAND);
}
// Other code...
};
现在回到Heroine。改变代码,在处理状态变更的代码中调用enter()
:
void Heroine::handleInput(Input input)
{
HeroineState* state = state_->handleInput(*this, input);
if (state != NULL)
{
delete state_;
state_ = state;
// Call the enter action on the new state.
state_->enter(*this);
}
}
然后下蹲时的代码可以简化为:
HeroineState* DuckingState::handleInput(Heroine& heroine,
Input input)
{
if (input == RELEASE_DOWN)
{
return new StandingState();
}
// Other code...
}
上述工作做的就是切换到standing状态并在standing状态中变更图像。现在状态真真正正地被封装起来了。使用 进入 动作的另一个好处是无论你是从哪一个状态切换而来,它只会在被切换后的状态里运行。
现实中很多状态图都有多个到同一状态的转换。例如,角色在跳跃或下坠后都会以站立状态结束。这表明我们要在转换发生的地方重复很多代码。而使用entry动作巩固了这一情况。
当然,我们也可以进行扩展,使其支持 退出 动作。这就变成了我们在离开一个状态时需要调用的方法。
译者状态机并不是让你的代码运行效率提升,而是进行大刀阔斧的解耦,从而提高代码的可维护性和开发效率,以及避免逻辑漏洞。这比运行时或编译时的各种优化技术都要珍贵。
但代价是什么呢?
我不遗余力地向你你推销FSM,不过现在我要釜底抽薪了。到目前为之我并未说谎,FSM也确实适合解决一些特定的问题。但FSM的长处同时也是它的短板。
状态机通过强制使用一种限制性非常强的结构来帮助你在繁杂代码中理清头绪。你获得的只有一个固定的状态集合,单一的一个当前状态,以及一些硬编码进去的过渡行为。
如果你想在更为复杂的场景下使用状态机,比如游戏的AI,你马上就会看到此模型的局限性。幸好先行者们已经找到了规避其中一些障碍的方法。此章之后我会为你介绍这几种方法。
有限状态机并不是图灵完备的。自动机理论使用了一系列的抽象模型来描述计算,每一种都极为复杂。图灵机就是其中最有表现力的模型之一。
“图灵完备”是说一个系统(通常是编程语言)能够实现图灵机,也就是说,所有图灵完备的语言在某种程度上,表达力都是等效的。FSM不够灵活,无法成为其中一员。
并发状态机
我们要给Heroine增加携带枪械的能力。当角色持枪时,他仍然能够像以前那样跑、跳跃、下蹲等等。但是他也能同时进行开火。
如果还限制在FSM里,那么状态数量就必须要翻倍了。对于每一个存在的状态,都需要另一个等效的持枪状态:持枪站立、持枪跳跃、持枪下蹲等等。
增加更多的枪支则会使状态数量爆炸式上升。不仅仅是数量上,结构上也十分冗余:除了控制开火的那一点代码,持枪和空手状态基本是一摸一样的。
问题在于,我们把两种状态——“做什么”和“携带什么”混在一个状态机里了。对所有组合情况的建模需要为每一种组合都设置状态。修复方法显而易见:使用分离开的两个状态机。
如果“做什么”有n个状态,“携带什么”有m个状态,使用单一状态机需要n×m个状态。而使用两个状态机只需要n+m个。
原本控制角色动作的状态机先放着不动。然后定义出一个新的状态机表示携带行为。Heroine要持有两个状态引用,如:
class Heroine
{
// Other code...
private:
HeroineState* state_;
HeroineState* equipment_;
};
这里为了清晰展示,给 装备 使用了全量的状态模式,但在实际操作中,因为这里只有两种状态(携带和不携带),所以设置布尔类型的flag也是可以的。
当角色把输入处理委托到状态中时,他需要同时使用两者:
void Heroine::handleInput(Input input)
{
state_->handleInput(*this, input);
equipment_->handleInput(*this, input);
}
功能更为丰富的系统可能会让一个状态机消耗掉输入,使得其他的状态机不能接收到。这样可以防止两个状态机错误地响应同一个输入。
每一个状态机都能够对输入响应,生成行为,并且各自独立地改变状态。当两个状态机的状态集合互不相干时,这么做效果很好。
实际开发中,你可能会遇到状态之间交互的情形。譬如,在跳跃的时候角色不能开火,或者持械的时候就不能俯冲。要处理这样的情况,在其中的一个状态里你可能需要添加一些if
语句来判断另一个状态机的状态。这并非是最优雅的解决方案,但是能凑活使用。
层次状态机
下推自动机
用处几何
注
[1]. “重构”一书指的就是”Refactoring:Improving the Design of Existing Code”, 作者是Martin Fowler。