python實作FSM及相關注意點(呂萬友)

有限狀态機FSM

轉載 2016年11月18日 09:34:49

• 标簽：

• 1901
• 編輯
• 删除

有限狀态機又簡稱FSM(Finite-State Machine的首字母縮寫)。這個在離散數學裡學過了，它是計算機領域中被廣泛使用的數學概念。是表示有限個狀态以及在這些狀态之間的轉移和動作等行為的數學模型。編譯原理學得好的童鞋應該對FSM不陌生，因為編譯器就用了FMS來做詞法掃描時的狀态轉移。

FSM的概念在網上一搜可以搜一大堆出來，但估計您也看不大明白。本文将以不一樣的方式來講述FSM的概念以及實作。

現實生活中，狀态是随處可見的，并且通過不同的狀态來做不同的事。比如冷了加衣服；餓了吃飯；困了睡覺等。這裡的冷了、餓了、困了是三種不同的狀态，并且根據這三個狀态的轉變驅動了不同行為的産生(加衣服、吃飯和睡覺)。

FSM是什麼

所謂有限狀态機，就是由有限個狀态組成的機器。再看上面舉到的例子：人就是一部機器，能感覺三種狀态(冷、餓、困)。由于氣溫降低是以人會覺得冷；由于到了吃飯的時間是以覺得餓；由于晚上12點是以覺得困。狀态的産生以及改變都是由某種條件的成立而出現的。不考慮FSM的内部結構時，它就像是一個黑箱子，如下圖：

左邊是輸入一系列條件，FSM通過判定，然後輸出結果。

FSM的處理流程

上圖FSM屏蔽了判定的過程，事實上FSM是由有限多個狀态組成的，每個狀态相當于FSM的一個部件。比如要判斷一個整數是否偶數，其實隻需要判斷這個整數的最低位是否為0就行了，代碼如下：

$GOPATH/src/fsm_test

—-main.go

01	package main

02

03

import (

04

"fmt"

05

)

06

07	func IsEven(num  int )  bool {

08	if num&0x1 == 0x0 {

09	return true

10

}

11

12	return false

13

}

14

15	func main() {

16	fmt.Printf( "%d is even? %t\n" , 4, IsEven(4))

17	fmt.Printf( "%d is even? %t\n" , 5, IsEven(5))

18

}

1

$&nbsp;</code><code class="functions" style="word-break:break-all; padding:0px!important; margin:0px!important; font-family:Consolas,&quot;Bitstream Vera Sans Mono&quot;,&quot;Courier New&quot;,Courier,monospace!important; border:0px!important; color:rgb(255,20,147)!important; outline:0px!important; float:none!important; vertical-align:baseline!important; position:static!important; left:auto!important; top:auto!important; right:auto!important; bottom:auto!important; height:auto!important; width:auto!important; line-height:1.1em!important; font-size:10pt!important; min-height:inherit!important">cd</code>&nbsp;<code class="plain" style="word-break:break-all; padding:0px!important; margin:0px!important; font-family:Consolas,&quot;Bitstream Vera Sans Mono&quot;,&quot;Courier New&quot;,Courier,monospace!important; border:0px!important; outline:0px!important; float:none!important; vertical-align:baseline!important; position:static!important; left:auto!important; top:auto!important; right:auto!important; bottom:auto!important; height:auto!important; width:auto!important; line-height:1.1em!important; font-size:10pt!important; min-height:inherit!important">$GOPATH/src/fsm_test

2	$ go build

3	$ ./fsm_test

4	4 is even?  true

5	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行為，比如電視機目前頻道正在播放西遊記，切換頻道後就變成了播放封神榜，原理上是一樣的。代碼定義如下：

01	package main

02

03

// 接口

04	type IFSMState interface {

05

Enter()

06

Exit()

07	CheckTransition()

08

}

09

10	// State父struct

11	type FSMState  struct {}

12

13

// 進入狀态

14	func ( this *FSMState) Enter() {

15

//

16

}

17

18

// 退出狀态

19	func ( this *FSMState) Exit() {

20

//

21

}

22

23

// 狀态轉移檢測

24	func ( this *FSMState) CheckTransition() {

25

//

26

}

27

28	type FSM  struct {

29

// 持有狀态集合

30	states map[string]IFSMState

31

// 目前狀态

32	current_state IFSMState

33

// 預設狀态

34	default_state IFSMState

35

// 外部輸入資料

36	input_data interface{}

37

}

38

39

// 初始化FSM

40	func ( this *FSM) Init() {

41

//

42

}

43

44	// 添加狀态到FSM

45	func ( this *FSM) AddState(key string, state IFSMState) {

46

//

47

}

48

49	// 設定預設的State

50	func ( this *FSM) SetDefaultState(state IFSMState) {

51

//

52

}

53

54

// 轉移狀态

55	func ( this *FSM) TransitionState() {

56

//

57

}

58

59

// 設定輸入資料

60	func ( this *FSM) SetInputData(inputData interface{}) {

61

//

62

}

63

64

// 重置

65	func ( this *FSM) Reset() {

66

//

67

}

68

69	func main() {

70

}

以上代碼隻是初略的定義。我們知道FSM不是直接去選擇某種狀态，而是根據輸入條件來選擇的。是以可以定義一張輸入語句和狀态的映射表，本文僅僅簡單實作。

NPC例子

遊戲中一個玩家可以攜帶寵物，那麼這個 寵物(NPC)就可以看作是FSM。比如這個寵物在每天8點鐘開始工作(掙金币)，中午12點鐘開始打坐練功。8點鐘和12點鐘就是對這個FSM的輸入語句，對應的狀态則是開始工作和開始打坐練功。代碼實作如下：

001	package main

002

003

import (

004

"fmt"

005

)

006

007

// 接口

008	type IFSMState interface {

009

Enter()

010

Exit()

011	CheckTransition(hour  int )  bool

012	Hour()  int

013

}

014

015	// State父struct

016	type FSMState  struct {}

017

018

// 進入狀态

019	func ( this *FSMState) Enter() {

020

//

021

}

022

023

// 退出狀态

024	func ( this *FSMState) Exit() {

025

//

026

}

027

028

// 狀态轉移檢測

029	func ( this *FSMState) CheckTransition(hour  int ) {

030

//

031

}

032

033

// 打坐

034	type ZazenState  struct {

035

hour  int

036

FSMState

037

}

038

039	func NewZazenState() *ZazenState {

040	return &ZazenState{hour: 8}

041

}

042

043	func ( this *ZazenState) Enter() {

044	fmt.Println( "ZazenState: 開始打坐" )

045

}

046

047	func ( this *ZazenState) Exit() {

048	fmt.Println( "ZazenState: 退出打坐" )

049

}

050

051	func ( this *ZazenState) Hour()  int {

052	return this .hour

053

}

054

055

// 狀态轉移檢測

056	func ( this *ZazenState) CheckTransition(hour  int )  bool {

057	if hour ==  this .hour {

058	return true

059

}

060

061	return false

062

}

063

064

// 工作

065	type WorkerState  struct {

066

hour  int

067

FSMState

068

}

069

070	func NewWorkerState() *WorkerState {

071	return &WorkerState{hour: 12}

072

}

073

074	func ( this *WorkerState) Enter() {

075	fmt.Println( "WorkerState: 開始工作" )

076

}

077

078	func ( this *WorkerState) Exit() {

079	fmt.Println( "WorkerState: 退出工作" )

080

}

081

082	func ( this *WorkerState) Hour()  int {

083	return this .hour

084

}

085

086

// 狀态轉移檢測

087	func ( this *WorkerState) CheckTransition(hour  int )  bool {

088	if hour ==  this .hour {

089	return true

090

}

091

092	return false

093

}

094

095	type FSM  struct {

096

// 持有狀态集合

097	states map[string]IFSMState

098

// 目前狀态

099	current_state IFSMState

100

// 預設狀态

101	default_state IFSMState

102

// 外部輸入資料

103	input_data  int

104

// 是否初始化

105	inited      bool

106

}

107

108

// 初始化FSM

109	func ( this *FSM) Init() {

110	this .Reset()

111

}

112

113	// 添加狀态到FSM

114	func ( this *FSM) AddState(key string, state IFSMState) {

115	if this .states == nil {

116	this .states = make(map[string]IFSMState, 2)

117

}

118	this .states[key] = state

119

}

120

121	// 設定預設的State

122	func ( this *FSM) SetDefaultState(state IFSMState) {

123	this .default_state = state

124

}

125

126

// 轉移狀态

127	func ( this *FSM) TransitionState() {

128	nextState :=  this .default_state

129	input_data :=  this .input_data

130	if this .inited {

131	for _, v := range  this .states {

132	if input_data == v.Hour() {

133	nextState = v

134

break

135

}

136

}

137

}

138

139	if ok := nextState.CheckTransition( this .input_data); ok {

140	if this .current_state != nil {

141	// 退出前一個狀态

142	this .current_state.Exit()

143

}

144	this .current_state = nextState

145	this .inited =  true

146	nextState.Enter()

147

}

148

}

149

150

// 設定輸入資料

151	func ( this *FSM) SetInputData(inputData  int ) {

152	this .input_data = inputData

153	this .TransitionState()

154

}

155

156

// 重置

157	func ( this *FSM) Reset() {

158	this .inited =  false

159

}

160

161	func main() {

162	zazenState := NewZazenState()

163	workerState := NewWorkerState()

164	fsm :=  new (FSM)

165	fsm.AddState( "ZazenState" , zazenState)

166	fsm.AddState( "WorkerState" , workerState)

167	fsm.SetDefaultState(zazenState)

168	fsm.Init()

169	fsm.SetInputData(8)

170	fsm.SetInputData(12)

171	fsm.SetInputData(12)

172	fsm.SetInputData(8)

173	fsm.SetInputData(12)

174

}

01

$&nbsp;</code><code class="functions" style="word-break:break-all; padding:0px!important; margin:0px!important; font-family:Consolas,&quot;Bitstream Vera Sans Mono&quot;,&quot;Courier New&quot;,Courier,monospace!important; border:0px!important; color:rgb(255,20,147)!important; outline:0px!important; float:none!important; vertical-align:baseline!important; position:static!important; left:auto!important; top:auto!important; right:auto!important; bottom:auto!important; height:auto!important; width:auto!important; line-height:1.1em!important; font-size:10pt!important; min-height:inherit!important">cd</code>&nbsp;<code class="plain" style="word-break:break-all; padding:0px!important; margin:0px!important; font-family:Consolas,&quot;Bitstream Vera Sans Mono&quot;,&quot;Courier New&quot;,Courier,monospace!important; border:0px!important; outline:0px!important; float:none!important; vertical-align:baseline!important; position:static!important; left:auto!important; top:auto!important; right:auto!important; bottom:auto!important; height:auto!important; width:auto!important; line-height:1.1em!important; font-size:10pt!important; min-height:inherit!important">$GOPATH/src/fsm_test

02	$ go build

03	$ ./fsm_test

04	ZazenState: 開始打坐

05	ZazenState: 退出打坐

06	WorkerState: 開始工作

07	WorkerState: 退出工作

08	WorkerState: 開始工作

09	WorkerState: 退出工作

10	ZazenState: 開始打坐

11	ZazenState: 退出打坐

12	WorkerState: 開始工作

關于對FSM的封裝

FSM主要是處理感覺外部資料而産生的狀态轉變，是以别打算去封裝它。不同的條件，不同的狀态以及不同的處理方式令FSM基本上不太可能去封裝，至也多隻是做一些文法上的包裝罷了。

結束語

真實的場景中，這個NPC所做的工作可能會非常多。比如自動判斷周邊的環境，發現怪物就去打怪，沒血了就自動補血，然後實在打不過就逃跑等等。上例中的SetInputData()就是用于模拟周邊環境的資料對NPC的影響，更複雜的情況還在于NPC有時候執行的動作是不能被打斷的(上例中的Exit()方法)，它隻有在完成某個周期的行為才能被終止。這個很容易了解。比如NPC發送網絡資料包的時候就不能輕易的被中斷，那這個時候其實是可以實作同步原語，狀态之間互相wait。

FSM被廣泛用于遊戲設計和其它各方面，的确是個比較重要的數學模型。

http://blog.csdn.net/erlib/article/details/24174691

</div>
</article>