Fatgrammer的状态机编程练习

状态机(State Machine),在电气,电子行业应用比较多。对于程序员,尤其是在应对流程复杂的业务逻辑时也非常有用。大多情况下,只要设计出良好的状态图,就可以机械地将其翻译成代码。状态机家族很庞大,有说不完的话题,我不打算涵盖每一点一面。以下主要讲述一些个人的理解和编程实践。

游戏编程有个重要的概念,触发器(是Trigger不是电路中的Flip-flop)。它核心的两个概念,事件(Event)和动作(Action),有时候可选的加上环境(Environment)/ 条件(Condition)。举个例子:

大多格斗游戏,输入“↓→A”,会发出波动拳,像街头霸王的Ken。对触发器来说,“↓→A”就是事件,波动拳就是动作。但在浮空和倒地时不能发出波动拳,这两个就可以算作环境或条件。再之后,波动拳又可以作为触发下一个动作的事件。

类似的,状态机也有两个核心概念,状态(State)和转换(Transition),转化过程可以包含一系列的动作(Action)。状态机也有事件(Event)的说法,但是不强调。事件也可以称作“输入(Input)”,这样,在转换结束时就可能产生相应的输出(Output)。

对于上面的Ken来说,“站立”状态的他,受到了“↓→A”这个事件/输入。然后呢?转换到哪里去了?如果玩游戏够多,应该知道,转换到了“硬直”。也就是有一瞬间,无法进行任何操作。在转换到“硬直”状态时,会触发一个Tick()动作用来计时。计时到点后,它又会触发一个新事件/输出转换到“站立”状态。同时,波动拳作为一个新的状态机,继续自己的使命。

基于状态机实现触发器的简单理论就是这样,当然你也可以基于流程去实现,不过根据经验最后会写成一盘意大利面

我们大多使用的是有限状态机(FSM),其次又可以分为DFA/NFAMealy Machine/ Moore Machine等等。先不用纠结这些细节,用到时自然能分清楚。下面通过一个“简易微波炉”的例子来分析和实现一个状态机。

正所谓“简易微波炉”,需要以下假设:

  • 永动
  • 有按钮ON
  • 有按钮OFF
  • 每次按下ON恒定加热(Heating)100秒
  • 无法在门开(Opened)时下加热。加热时打开门,机器停止
  • 加热或门开时灯亮(Light_ON),也就是关门且停止时灯灭(Light_OFF)。
  • 机器初始处于关门(Closed),停止(Stopped)状态;

我们先暴力绘制一张状态图:

这里抽象出了三种核心状态Init,Heating,Door_Opened,真实情况应该复杂的多。这里需要一些异步,不过暂且不考虑。先看一个简单的实现:

//actions
void turnOff() {}
void Tick() {
  // send a signal of Time_Expiration
}
void lightOn() {}
void openDoor() {}
void lightOff() {}
void closeDoor() {}
// abstract state
enum{ 
 Init,        //CLOSED, STOPPED, LIGHT_OFF
 Door_Opened, //OPENED, HEATING, LIGHT_ON
 Heating      //CLOSED, HEATING, LIGHT_ON
};
// event
enum { 
 Push_ON, Push_OFF, Open_Door, 
 Close_Door, Time_Expiration 
};
uint8_t current_state = Init;
uint8_t event;

while (cin << event) {
  if (current_state == Init) {
    if (event == Push_ON) {
      current_state = Heating;
      Tick();
    } else if (event == Open_Door) {
      current_state = Door_Opened;
      lightOn();
    }
  } else if (current_state == Heating) {
    if (event == Push_OFF) {
      current_state = Init;
      turnOff();
    } else if (event == Time_Expiration) {
      current_state = Init;
      turnOff();
    } else if (event == Open_Door) {
      current_state = Door_Opened;
      openDoor();
    }
  } else if (current_state == Door_Opened) {
    if (event == Close_Door) {
      current_state = Init;
      closeDoor();
    }
  }
}

习惯上这里会用嵌套switch来实现,不过这个例子十分简单,条件语句看起来更清晰。Redux就采用同类的状态机,业务复杂的时候,阅读体验十分爆炸。老派黑客大都推荐数据驱动编程,也被应用在状态机设计上,这里可以先列张表:

State Event Action  New State
Init Push_ON  Tick  Heating
Init Open_Door  lightOn  Door_Opened
Heating Push_OFF  turnOff Init
Heating Time_Expiration  turnOff  Init
Heating  Open_Door openDoor  Door_Opened
Door_Opened Close_Door  closeDoor  Init

再下来就是机械翻译了(这里修改动了动作函数,使其返回新的状态):

Function<uint8_t(void)> State_Table[Max_State][Max_Even] = {
    Tick, lightOn, nullptr, nullptr, nullptr,
    nullptr, turnOff, openDoor,nullptr, turnOff,
    nullptr, nullptr, nullptr, closeDoor, nullptr
};
while(cin >> event){
  current_state = State_Table[current_state][event]();
}

是不是即简单又赏心悦目呢?

这里还有种有趣的实现方式,就是状态模式(State Pattern),维基百科的例子创建了一个全局上下文(Context),负责管理全局状态,有些像OpenGL的设计思路。我们的例子基础代码应该是这样的:

class StateLike {
  virtual StateLike* Push_ON();
  virtual StateLike* Push_OFF();
  virtual StateLike* Open_Door();
  virtual StateLike* Close_Door();
  virtual StateLike* Time_Expire();
};

class Init : public StateLike {
  StateLike* Push_ON() { return new Heating; }
  StateLike* Open_Door() { return new DoorOpened; }
};

class Heating : public StateLike {
  StateLike* Push_OFF() { return new Init; }
  StateLike* Time_Expire() { return new Init; }
  StateLike* Open_Door() { return new DoorOpened; }
};

class DoorOpened : public StateLike {
  StateLike* Close_Door() { return new Init; }
};

这里还可以创建一个工厂,将消息和函数关联起来,顺便将状态委托给全局的上下文以便管理。不过,状态模式看起来炫酷,实际开销比较大,简明程度一般。我个人还是推荐数据驱动的写法。

状态机用来处理复杂流程,还是比较合适的。当然这里还有嵌套状态,确定性之类的探讨,以至于如何更好的设计状态机,这些将留在后续的博文中。

Leave a Reply

Your email address will not be published. Required fields are marked *