文档章节

有限状态机(FSM)简单实现

j_m
 j_m
发布于 2012/10/11 10:27
字数 1947
阅读 540
收藏 3
简述
有限状态机(以下用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可以非常容易地模拟消息机制,这有利于模块清晰化,更容易设计出正交的程序。

本文转载自:http://blog.csdn.net/lanphaday/article/details/1510688

j_m

j_m

粉丝 23
博文 156
码字总数 18
作品 0
徐汇
程序员
私信 提问
在 Ruby 中使用状态机

有限状态机(FSM) 会用在我们周围的方方面面,如果你睁大眼睛,你会看到电子商务处理订单,火车站的电子转换器(electronic turn styles )等,都会用到有限状态机。在我之前作为一个电子工程师...

ifsc01
2013/01/29
3.4K
2
HTFramework框架使用手册(三) FSM有限状态机

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/qq992817263/article/details/86073351 索引 FSM模块简介 FSM有限状态机用于模拟一切可以抽象为有限状态机结构...

神码编程
01/08
0
0
Golang: 有限状态自动机

有限状态机 又简称FSM(Finite-State Machine的首字母缩写)。这个在离散数学里学过了,它是计算机领域中被广泛使用的数学概念。是表示有限个状态以及在这些状态之间的转移和动作等行为的数学模...

陈亦
2014/02/24
2.6K
5
基于C语言的状态机实现技术

基于C语言的状态机实现技术 嵌入式开发交流群280352802,欢迎加入! 一、简介 有限状态机是一种用来进行对象行为建模的工具,其作用主要是描述对象在它的生命周期内所经历的状态序列,以及如...

长平狐
2013/06/03
1K
0
有限状态机(FSM)的设计与实现(一)

有限状态机(FSM)是表示有限个状态及在这些状态之间的转移和动作等行为的数学模型,在计算机领域有着广泛的应用。通常FSM包含几个要素:状态的管理、状态的监控、状态的触发、状态触发后引发...

j_m
2012/10/11
701
0

没有更多内容

加载失败,请刷新页面

加载更多

JAVA 实现雪花算法生成唯一订单号工具类

import lombok.SneakyThrows;import lombok.extern.slf4j.Slf4j;import java.util.Calendar;/** * Default distributed primary key generator. * * <p> * Use snowflake......

huangkejie
昨天
6
0
PhotoShop 色调:RGB/CMYK 颜色模式

一·、 RGB : 三原色:红绿蓝 1.通道:通道中的红绿蓝通道分别对应的是红绿蓝三种原色(RGB)的显示范围 1.差值模式能模拟三种原色叠加之后的效果 2.添加-颜色曲线:调整图像RGB颜色----R色增强...

东方墨天
昨天
6
1
将博客搬至CSDN

将博客搬至CSDN

算法与编程之美
昨天
5
0
HTML5+CSS3从入门到精通 中文pdf版​

本文转载于:专业的前端网站➵HTML5+CSS3从入门到精通 中文pdf版 HTML5+CSS3从入门到精通是通过基础知识+中小实例+综合案例的方式,讲述了用HTML5+ CSS3设计构建网站的必备知识,相对于专业指...

前端老手
昨天
6
0
聊聊nacos client的ConfigFilterChainManager

序 本文主要研究一下nacos client的ConfigFilterChainManager IConfigFilterChain nacos-1.1.3/api/src/main/java/com/alibaba/nacos/api/config/filter/IConfigFilterChain.java public in......

go4it
昨天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部