什么是有限状态机FSM

什么是有限状态机FSM

简述
有限状态机（以下用FSM指代）是一种算法思想，简单而言，有限状态机由一组状态、一个初始状态、输入和根据输入及现有状态转换为下一个状态的转换函数组成。在Gof的23种设计模式里的state模式是一种面向对象的状态机思想，可以适应非常复杂的状态管理。
现 在，FSM被普遍用于搜索引擎的分词、编译器实现和我们普遍关注的游戏开发中。游戏开发中，通常用FSM实现NPC控制，如当NPC受到攻击时根据健康、 力量等选择逃跑还是反攻的行为，一般是用FSM实现的。FSM的实现方法有很多种，不能简单地说孰优孰劣，但现代开发中，一般都比较推荐面向对象的实现方 式：因为可重用性和健壮性更高，而且当需求变更的时候，也有很好的适应性。
实践
理 论从实践中来，也要回到实践中去。我们现在通过实例来探索一下FSM的实现吧。首先假设有这样一个世界（World），世界里只有一台永不缺乏动力的汽车 （Car），汽车是次世代的，没有油门方向盘之类的落后设备，只有两个互斥的按钮——停止（Stop）和行进（Run），随着时间的流逝，汽车根据驾驶员 的操作走走停停。下面的代码可以实现这种功能：
while True:
       key = get_key() # 按下什么键
       if key == "stop":
              stop(car)
       elif key == "run":
              go(car)
       keep(car) # 保持原态  

完 成了功能而且直观、简洁的程序员万岁！但这时候客户（策划或者玩家）觉得走走停停太没意思了，他们想要掉头、左转和右转的功能，我们就要在while循环 里增加更多的if...else分支；他们想要更多的车，我们就要要在每一个分枝里增加循环；他们不仅仅想要Car了，他们还要要玩Truck，这时我们 就需要在分枝的循环里判断当前的车是否支持这个操作（如Truck的装卸货物Car就不支持）；他们……
这个while循环终于无限地庞大起来，我们认识到这样的设计的确是有点问题的，所以我们尝试用另一种方法去实现FSM。首先我们来实现汽车（Car）：
class Car(object):
       def stop(self):
              print "Stop!!!"
  
       def go(self):
              print "Goooooo!!!"  

只有两个方法stop和go，分别执行Stop和Run两个按钮功能。接下来我们编写两个状态管理的类，用以处理当按钮被按下、弹起和保持时需要工作的流程：
class stop_fsm(base_fsm):
       def enter_state(self, obj):
              print "Car%s enter stop state!"%(id(obj))
  
       def exec_state(self, obj):
              print "Car%s in stop state!"%(id(obj))
              obj.stop()
  
       def exit_state(self, obj):
              print "Car%s exit stop state!"%(id(obj))  
class run_fsm(base_fsm):
       def enter_state(self, obj):
              print "Car%s enter run state!"%(id(obj))
  
       def exec_state(self, obj):
              print "Car%s in run state!"%(id(obj))
              obj.go()
  
       def exit_state(self, obj):
              print "Car%s exit run state!"%(id(obj))  

stop_fsm和run_fsm都继承自base_fsm，base_fsm是一个纯虚的接口类：
class base_fsm(object):
       def enter_state(self, obj):
              raise NotimplementedError()
  
       def exec_state(self, obj):
              raise NotImplementedError()
  
       def exit_state(self, obj):
              raise NotImplementedError()  

enter_state 在obj进入某状态的时候调用——通常用来做一些初始化工作；exit_state也离开某状态的时候调用——通常做一些清理工作；而 exec_state则在每一帧的时候都会被调用，通常做一些必要的工作，如检测自己的消息队列并处理消息等。在stop_fsm和run_fsm两个类 的exec_state函数中，就调用了对象的stop和go函数，让汽车保持原有的状态。
至现在为止，Car还没有接触到FSM，所以我们需要提供一个接口，可以让它拥有一个FSM：
       def attach_fsm(self, state, fsm):
              self.fsm = fsm
              self.curr_state = state  

我们还需要为Car提供一个状态转换函数：
       def change_state(self, new_state, new_fsm):
              self.curr_state = new_state
              self.fsm.exit_state(self)
              self.fsm = new_fsm
              self.fsm.enter_state(self)
              self.fsm.exec_state(self)  

为Car提供一个保持状态的函数：
       def keep_state(self):
              self.fsm.exec_state(self)  

现在只有两个状态，但我们知道需求随时会改动，所以我们最好弄一个状态机管理器来管理这些状态：
class fsm_mgr(object):
       def __init__(self):
              self._fsms = {}
              self._fsms[0] = stop_fsm()
              self._fsms[1] = run_fsm()
      
       def get_fsm(self, state):
              return self._fsms[state]
      
       def frame(self, objs, state):
              for obj in objs:
                     if state == obj.curr_state:
                            obj.keep_state()
                     else:
                            obj.change_state(state, self._fsms[state])  

fsm_mgr最重要的函数就是frame，在每一帧都被调用。在这里，frame根据对象现在的状态和当前的输入决定让对象保持状态或者改变状态。
这时候，我们的实例基本上完成了。但我们还要做一件事，就是建立一个世界（World）来驱动状态机：
class World(object):
       def init(self):
              self._cars = []
              self._fsm_mgr = fsm_mgr()
              self.__init_car()
  
       def __init_car(self):
              for i in xrange(1):   # 生产汽车
                     tmp = Car()
                     tmp.attach_fsm(0, self._fsm_mgr.get_fsm(0))
                     self._cars.append(tmp)
  
       def __frame(self):
              self._fsm_mgr.frame(self._cars, state_factory())
  
       def run(self):
              while True:
                     self.__frame()
                     sleep(0.5)  

从 代码可见，World里有Car对象，fsm_mgr对象；在run函数里，每0.5s执行一次__frame函数（FPS = 2），而__frame函数只是驱动了fsm_mgr来刷新对象，新的命令是从state_factory函数里取出来的，这个函数用以模拟驾驶员的操作 （按下Stop或者Run按钮之一）：
def state_factory():
       return random.randint(0, 1)  

现在我们就要初始化世界（World）可以跑起我们的FSM了！
if __name__ == "__main__":
       world = World()
       world.init()
       world.run()  

用python解释器执行上面的代码，我们可以看到程序不停地输出Car的状态：
......
Car8453392 exit run state!
Car8453392 enter stop state!
Car8453392 in stop state!
Stop!!!
Car8453392 in stop state!
Stop!!!
Car8453392 exit stop state!
Car8453392 enter run state!
Car8453392 in run state!
Goooooo!!!
Car8453392 exit run state!
Car8453392 enter stop state!
Car8453392 in stop state!
Stop!!!
Car8453392 exit stop state!
Car8453392 enter run state!
Car8453392 in run state!
Goooooo!!!
Car8453392 in run state!
Goooooo!!!
Car8453392 exit run state!
Car8453392 enter stop state!
Car8453392 in stop state!
Stop!!!
Car8453392 in stop state!
Stop!!!
Car8453392 exit stop state!
Car8453392 enter run state!
Car8453392 in run state!
Goooooo!!!
......  

  
结论
这时再回头来看看我们之前的问题：
1、玩家想要功能更多的Car，比如掉头。
我 们可以通过为Car增加一个调头（back）的方法来执行掉头，然后从base_fsm中继承一个back_fsm来处理调头。之后在fsm_mgr里增 加一个back_fsm实例，及让state_factory产生调头指令。听起来似乎比之前while+if的方式还要麻烦不少，其实不然，这里只有 back_fsm和为fsm_mgr增加back_fsm实例才是特有的，其它步骤两种方法都要执行。
2、玩家要更多的Car。
这对于面向对象的FSM实现就太简单了，我们只要把World.__init_car里的生产数量修改一下就行了，要多少有多少。
3、玩家要更多型号的车，如Truck。
从Car派生一个Truck，然后增加装货、卸货的接口。最大的改动在于Truck状态转换的时候需要一些判断，如不能直接从装货状态转换到开动状态，而是装货、停止再开动。
通 过这几个简单的问题分析，我们可以看到，使用面向对象的方式来设计FSM，在需求变更的时候，一般都只增删代码，而仍少需要改动已有代码，程序的扩展性、 适应性和健壮性都得很大的提高；因此，在世界庞大、物种烦多、状态复杂且条件交错的游戏开发中应用面向对象的FSM实在是明智之选。还有一点，面向对象的 FSM可以非常容易地模拟消息机制，这有利于模块清晰化，更容易设计出正交的程序。