文档章节

Golang: 有限状态自动机

陈亦
 陈亦
发布于 2014/02/24 16:43
字数 2250
阅读 2553
收藏 31

有限状态机 又简称FSM(Finite-State Machine的首字母缩写)。这个在离散数学里学过了,它是计算机领域中被广泛使用的数学概念。是表示有限个状态以及在这些状态之间的转移和动作等行为的数学模型。编译原理学得好的童鞋应该对FSM不陌生,因为编译器就用了FMS来做词法扫描时的状态转移。

FSM的概念在网上一搜可以搜一大堆出来,但估计您也看不大明白。本文将以不一样的方式来讲述FSM的概念以及实现。

现实生活中,状态是随处可见的,并且通过不同的状态来做不同的事。比如冷了加衣服;饿了吃饭;困了睡觉等。这里的冷了、饿了、困了是三种不同的状态,并且根据这三个状态的转变驱动了不同行为的产生(加衣服、吃饭和睡觉)。

FSM是什么

所谓有限状态机,就是由有限个状态组成的机器。再看上面举到的例子:人就是一部机器,能感知三种状态(冷、饿、困)。由于气温降低所以人会觉得冷;由于到了吃饭的时间所以觉得饿;由于晚上12点所以觉得困。状态的产生以及改变都是由某种条件的成立而出现的。不考虑FSM的内部结构时,它就像是一个黑箱子,如下图:

左边是输入一系列条件,FSM通过判定,然后输出结果。

FSM的处理流程

上图FSM屏蔽了判定的过程,事实上FSM是由有限多个状态组成的,每个状态相当于FSM的一个部件。比如要判断一个整数是否偶数,其实只需要判断这个整数的最低位是否为0就行了,代码如下:

$GOPATH/src/fsm_test

----main.go

package main

import (
	"fmt"
)

func IsEven(num int) bool {
	if num&0x1 == 0x0 {
		return true
	}

	return false
}

func main() {
	fmt.Printf("%d is even? %t\n", 4, IsEven(4))
	fmt.Printf("%d is even? %t\n", 5, IsEven(5))
}

$ cd $GOPATH/src/fsm_test
$ go build
$ ./fsm_test
4 is even? true
5 is even? false

对数字5来说,它的二进制表示为0101。二进制只能为0或1,所以二进制的字符集合为:{0, 1},对应到FSM来说,就是有2种状态,分别为S0和S1。如果用FSM来处理,它总是从左边读取(当然也可以把FSM反过来),也就是从0101最左边那位开始输入:首先输入左边第一位0,停留在S0状态,然后输入第二位1,转到S1状态,再输入第三位0,则又回到S0状态,最后输入是后一位1则又回到S1状态。如下图所示:

上图忽略了一个很重要的细节,就是0和1是怎么输入的。状态S0和状态S1是FSM里的2个小部件,它们分别关联了0和1(也可以说是特定的输入语句),所以只能通过FSM来输入。当FSM接收到0时,它就交给S0去处理,这时S0就变成当前状态,然后对S0输入1,S0则将它交给S1去处理,这时S1就变成当前状态。如此这般,FSM持有有限多个状态,它可以接收输入并执行状态转移(比如将最初的0交给S0去处理)。状态S0和状态S1也是如此。

但是为什么最开始FSM接收输入的0后会交给S0去处理呢?这是因为FSM的默认状态是S0。就像是有一台电视机,它总是有默认的频道的,您一打开电视机就可以看到影像,即使是满屏的雪花点。而且可以在按下电视机的开关前预先调整频道,之后也可以调整频道。

如何用程序建模

FSM持有有限多个状态集合,有当前状态、默认状态、接收的外部数据等。并且FSM有一系列的行为:启动FSM、退出FSM以及状态转移等。State(状态)也会有一系列的行为:进入状态,转移状态等。并且State还有Action行为,比如电视机当前频道正在播放西游记,切换频道后就变成了播放封神榜,原理上是一样的。代码定义如下:

package main

// 接口
type IFSMState interface {
	Enter()
	Exit()
	CheckTransition()
}

// State父struct
type FSMState struct{}

// 进入状态
func (this *FSMState) Enter() {
	//
}

// 退出状态
func (this *FSMState) Exit() {
	//
}

// 状态转移检测
func (this *FSMState) CheckTransition() {
	//
}

type FSM struct {
	// 持有状态集合
	states map[string]IFSMState
	// 当前状态
	current_state IFSMState
	// 默认状态
	default_state IFSMState
	// 外部输入数据
	input_data interface{}
}

// 初始化FSM
func (this *FSM) Init() {
	//
}

// 添加状态到FSM
func (this *FSM) AddState(key string, state IFSMState) {
	//
}

// 设置默认的State
func (this *FSM) SetDefaultState(state IFSMState) {
	//
}

// 转移状态
func (this *FSM) TransitionState() {
	//
}

// 设置输入数据
func (this *FSM) SetInputData(inputData interface{}) {
	//
}

// 重置
func (this *FSM) Reset() {
	//
}

func main() {
}

以上代码只是初略的定义。我们知道FSM不是直接去选择某种状态,而是根据输入条件来选择的。所以可以定义一张输入语句和状态的映射表,本文仅仅简单实现。

NPC例子

游戏中一个玩家可以携带宠物,那么这个 宠物(NPC)就可以看作是FSM。比如这个宠物在每天8点钟开始工作(挣金币),中午12点钟开始打坐练功。8点钟和12点钟就是对这个FSM的输入语句,对应的状态则是开始工作和开始打坐练功。代码实现如下:

package main

import (
	"fmt"
)

// 接口
type IFSMState interface {
	Enter()
	Exit()
	CheckTransition(hour int) bool
	Hour() int
}

// State父struct
type FSMState struct{}

// 进入状态
func (this *FSMState) Enter() {
	//
}

// 退出状态
func (this *FSMState) Exit() {
	//
}

// 状态转移检测
func (this *FSMState) CheckTransition(hour int) {
	//
}

// 打坐
type ZazenState struct {
	hour int
	FSMState
}

func NewZazenState() *ZazenState {
	return &ZazenState{hour: 8}
}

func (this *ZazenState) Enter() {
	fmt.Println("ZazenState: 开始打坐")
}

func (this *ZazenState) Exit() {
	fmt.Println("ZazenState: 退出打坐")
}

func (this *ZazenState) Hour() int {
	return this.hour
}

// 状态转移检测
func (this *ZazenState) CheckTransition(hour int) bool {
	if hour == this.hour {
		return true
	}

	return false
}

// 工作
type WorkerState struct {
	hour int
	FSMState
}

func NewWorkerState() *WorkerState {
	return &WorkerState{hour: 12}
}

func (this *WorkerState) Enter() {
	fmt.Println("WorkerState: 开始工作")
}

func (this *WorkerState) Exit() {
	fmt.Println("WorkerState: 退出工作")
}

func (this *WorkerState) Hour() int {
	return this.hour
}

// 状态转移检测
func (this *WorkerState) CheckTransition(hour int) bool {
	if hour == this.hour {
		return true
	}

	return false
}

type FSM struct {
	// 持有状态集合
	states map[string]IFSMState
	// 当前状态
	current_state IFSMState
	// 默认状态
	default_state IFSMState
	// 外部输入数据
	input_data int
	// 是否初始化
	inited     bool
}

// 初始化FSM
func (this *FSM) Init() {
	this.Reset()
}

// 添加状态到FSM
func (this *FSM) AddState(key string, state IFSMState) {
	if this.states == nil {
		this.states = make(map[string]IFSMState, 2)
	}
	this.states[key] = state
}

// 设置默认的State
func (this *FSM) SetDefaultState(state IFSMState) {
	this.default_state = state
}

// 转移状态
func (this *FSM) TransitionState() {
	nextState := this.default_state
	input_data := this.input_data
	if this.inited {
		for _, v := range this.states {
			if input_data == v.Hour() {
				nextState = v
				break
			}
		}
	}
	
	if ok := nextState.CheckTransition(this.input_data); ok {
		if this.current_state != nil {
			// 退出前一个状态
			this.current_state.Exit()
		}
		this.current_state = nextState
		this.inited = true
		nextState.Enter()
	}
}

// 设置输入数据
func (this *FSM) SetInputData(inputData int) {
	this.input_data = inputData
	this.TransitionState()
}

// 重置
func (this *FSM) Reset() {
	this.inited = false
}

func main() {
	zazenState := NewZazenState()
	workerState := NewWorkerState()
	fsm := new(FSM)
	fsm.AddState("ZazenState", zazenState)
	fsm.AddState("WorkerState", workerState)
	fsm.SetDefaultState(zazenState)
	fsm.Init()
	fsm.SetInputData(8)
	fsm.SetInputData(12)
	fsm.SetInputData(12)
	fsm.SetInputData(8)
	fsm.SetInputData(12)
}

$ cd $GOPATH/src/fsm_test
$ go build
$ ./fsm_test
ZazenState: 开始打坐
ZazenState: 退出打坐
WorkerState: 开始工作
WorkerState: 退出工作
WorkerState: 开始工作
WorkerState: 退出工作
ZazenState: 开始打坐
ZazenState: 退出打坐
WorkerState: 开始工作

关于对FSM的封装

FSM主要是处理感知外部数据而产生的状态转变,所以别打算去封装它。不同的条件,不同的状态以及不同的处理方式令FSM基本上不太可能去封装,至也多只是做一些语法上的包装罢了。

结束语

真实的场景中,这个NPC所做的工作可能会非常多。比如自动判断周边的环境,发现怪物就去打怪,没血了就自动补血,然后实在打不过就逃跑等等。上例中的SetInputData()就是用于模拟周边环境的数据对NPC的影响,更复杂的情况还在于NPC有时候执行的动作是不能被打断的(上例中的Exit()方法),它只有在完成某个周期的行为才能被终止。这个很容易理解。比如NPC发送网络数据包的时候就不能轻易的被中断,那这个时候其实是可以实现同步原语,状态之间互相wait。

FSM被广泛用于游戏设计和其它各方面,的确是个比较重要的数学模型。


© 著作权归作者所有

陈亦
粉丝 241
博文 23
码字总数 53194
作品 0
浦东
高级程序员
私信 提问
加载中

评论(5)

TMACkan
TMACkan
解释的很好!
回去干活
回去干活
smc状态机,这个工具能自动生成代码不错,在搞cocos2dx时用过,不过现在搞go好像还没支持这个语言.如果有java大神的话,希望能搞个出来,直接写配置文件生成框架
go-skyblue
go-skyblue
有点点理解了
yusihuo
yusihuo
学习了
狗头666
狗头666
似乎有一点点看懂了,数学没学好还是很遗憾
确定性有限自动机(DFA)多模式匹配算法

在上篇 ac多模式匹配最后,有说到下面的冗余转移,这篇探讨下确定性有限自动机多模式匹配算法; 已知g(4,e) = 5; 假设M 当前状态为4, 且下一个字符不是'e',这时候M 会调用f(4)=1,其实这时候我...

famince
2014/02/24
631
3
利用有限自动机(finite automata)进行模式匹配

一、一、有限自动机定义及基本术语: 一个有限自动机 M 是一个5元组(Q, q0,A, Σ, δ),其中: Q 是所有状态的有限集合; q0 ∈ Q (属于)是初始状态; A ⊆ Q (子集)是接受状态的集合;(对...

famince
2013/12/06
2.5K
9
AC(Aho—Corasiek) 多模式匹配算法

简介: AC多模式匹配算法产生于1975年的贝尔实验室,最早使用于图书馆的书目查询程序中。该算法以有限状态自动机(FSA),以及KMP前缀算法 为基础.(有说法: ac自动机是KMP的多串形式,是一个有限...

famince
2014/01/27
5K
1
AC自动机+trie树实现高效多模式匹配字典

前言 经常会遇到一类需求,在一段字符串中查找所有能匹配上的模式,比如查找一段文字匹配上字典中哪些短语。这时为了高效处理,就会考虑 AC 自动机,即 Aho-Corasick 自动机算法。它的核心思...

超人汪小建
2018/07/09
0
0
KMP算法的理解,伪代码,c代码实现

1、字符串问题形式化定义:假设文本是一个长度为n的T[1..n],而模式是一个长度为m的数组P[1..m],其中m<=n,如果有T[s+1..s+m]==P[1..m],那么就称模式P在T中出现。s为有效偏移,否则称为无效...

thoresa
2015/05/18
468
0

没有更多内容

加载失败,请刷新页面

加载更多

OSChina 周六乱弹 —— 早上儿子问我他是怎么来的

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】 @凉小生 :#今日歌曲推荐# 少点戾气,愿你和这个世界温柔以待。中岛美嘉的单曲《僕が死のうと思ったのは (曾经我也想过一了百了)》 《僕が死の...

小小编辑
今天
1K
12
Excption与Error包结构,OOM 你遇到过哪些情况,SOF 你遇到过哪些情况

Throwable 是 Java 中所有错误与异常的超类,Throwable 包含两个子类,Error 与 Exception 。用于指示发生了异常情况。 Java 抛出的 Throwable 可以分成三种类型。 被检查异常(checked Exc...

Garphy
今天
22
0
计算机实现原理专题--二进制减法器(二)

在计算机实现原理专题--二进制减法器(一)中说明了基本原理,现准备说明如何来实现。 首先第一步255-b运算相当于对b进行按位取反,因此可将8个非门组成如下图的形式: 由于每次做减法时,我...

FAT_mt
昨天
14
0
好程序员大数据学习路线分享函数+map映射+元祖

好程序员大数据学习路线分享函数+map映射+元祖,大数据各个平台上的语言实现 hadoop 由java实现,2003年至今,三大块:数据处理,数据存储,数据计算 存储: hbase --> 数据成表 处理: hive --> 数...

好程序员官方
昨天
24
0
tabel 中含有复选框的列 数据理解

1、el-ui中实现某一列为复选框 实现多选非常简单: 手动添加一个el-table-column,设type属性为selction即可; 2、@selection-change事件:选项发生勾选状态变化时触发该事件 <el-table @sel...

everthing
昨天
11
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部