基于C++有限狀態(tài)機(jī)的實(shí)現(xiàn)技術(shù)(調(diào)查報(bào)告)
Posted on 2008-06-13 15:01 RichardHe 閱讀(1822) 評論(0) 編輯 收藏 引用 所屬分類: [轉(zhuǎn)]有 限狀態(tài)機(jī)是一種用來進(jìn)行對象行為建模的工具,其作用主要是描述對象在它的生命周期內(nèi)所經(jīng)歷的狀態(tài)序列,以及如何響應(yīng)來自外界的各種事件。在面向?qū)ο蟮能浖? 系統(tǒng)中,一個(gè)對象無論多么簡單或者多么復(fù)雜,都必然會(huì)經(jīng)歷一個(gè)從開始創(chuàng)建到最終消亡的完整過程,這通常被稱為對象的生命周期。一般說來,對象在其生命期內(nèi) 是不可能完全孤立的,它必須通過發(fā)送消息來影響其它對象,或者通過接受消息來改變自身。在大多數(shù)情況下,這些消息都只不過是些簡單的、同步的方法調(diào)用而 已。例如,在銀行客戶管理系統(tǒng)中,客戶類(Customer)的實(shí)例在需要的時(shí)候,可能會(huì)調(diào)用帳戶(Account)類中定義的getBalance()方法。在這種簡單的情況下,類Customer并不需要一個(gè)有限狀態(tài)機(jī)來描述自己的行為,主要原因在于它當(dāng)前的行為并不依賴于過去的某個(gè)狀態(tài)。[1]
遺憾的是并不是所有情況都會(huì)如此簡單,事實(shí)上許多實(shí)用的軟件系統(tǒng)都必須維護(hù)一兩個(gè)非常關(guān)鍵的對象,它們通常具有非常復(fù)雜的狀態(tài)轉(zhuǎn)換關(guān)系,而且需要對來自外部的各種異步事件進(jìn)行響應(yīng)。例如,在VoIP電話系統(tǒng)中,電話類(Telephone)的實(shí)例必須能夠響應(yīng)來自對方的隨機(jī)呼叫,來自用戶的按鍵事件,以及來自網(wǎng)絡(luò)的信令等。在處理這些消息時(shí),類Telephone所要采取的行為完全依賴于它當(dāng)前所處的狀態(tài),因而此時(shí)使用狀態(tài)機(jī)就將是一個(gè)不錯(cuò)的選擇。[1]
游戲引擎是有限狀態(tài)機(jī)最為成功的應(yīng)用領(lǐng)域之一,由于設(shè)計(jì)良好的狀態(tài)機(jī)能夠被用來取代部分的人工智能算法,因此游戲中的每個(gè)角色或者器件都有可能內(nèi)嵌一個(gè)狀態(tài)機(jī)。考慮RPG游戲中城門這樣一個(gè)簡單的對象,它具有打開(Opened)、關(guān)閉(Closed)、上鎖(Locked)、解鎖(Unlocked)四種狀態(tài),如圖1所示。當(dāng)玩家到達(dá)一個(gè)處于狀態(tài)Locked的門時(shí),如果此時(shí)他已經(jīng)找到了用來開門的鑰匙,那么他就可以利用它將門的當(dāng)前狀態(tài)轉(zhuǎn)變?yōu)?/span>Unlocked,進(jìn)一步還可以通過旋轉(zhuǎn)門上的把手將其狀態(tài)轉(zhuǎn)變?yōu)?/span>Opened,從而成功地進(jìn)入城內(nèi)。[1]
圖1 控制城門的狀態(tài)機(jī)
在描述有限狀態(tài)機(jī)時(shí),狀態(tài)、事件、轉(zhuǎn)換和動(dòng)作是經(jīng)常會(huì)碰到的幾個(gè)基本概念。
狀態(tài)(State)指的是對象在其生命周期中的一種狀況,處于某個(gè)特定狀態(tài)中的對象必然會(huì)滿足某些條件、執(zhí)行某些動(dòng)作或者是等待某些事件。
事件(Event)指的是在時(shí)間和空間上占有一定位置,并且對狀態(tài)機(jī)來講是有意義的那些事情。事件通常會(huì)引起狀態(tài)的變遷,促使?fàn)顟B(tài)機(jī)從一種狀態(tài)切換到另一種狀態(tài)。
轉(zhuǎn)換(Transition)指的是兩個(gè)狀態(tài)之間的一種關(guān)系,表明對象將在第一個(gè)狀態(tài)中執(zhí)行一定的動(dòng)作,并將在某個(gè)事件發(fā)生同時(shí)某個(gè)特定條件滿足時(shí)進(jìn)入第二個(gè)狀態(tài)。
動(dòng)作(Action)指的是狀態(tài)機(jī)中可以執(zhí)行的那些原子操作,所謂原子操作指的是它們在運(yùn)行的過程中不能被其他消息所中斷,必須一直執(zhí)行下去。
二、基于傳統(tǒng)C語言的FSM實(shí)現(xiàn)技術(shù)
2.1、基于switch(狀態(tài))的實(shí)現(xiàn)
在實(shí)現(xiàn)有限狀態(tài)機(jī)時(shí),使用switch語句是最簡單也是最直接的一種方式,其基本思路是為狀態(tài)機(jī)中的每一種狀態(tài)都設(shè)置一個(gè)case分支,專門用于對該狀態(tài)進(jìn)行控制。下面的代碼示范了如何運(yùn)用switch語句,來實(shí)現(xiàn)圖1中所示的狀態(tài)機(jī):
|
使用switch語句實(shí)現(xiàn)的有限狀態(tài)機(jī)的確能夠很好地工作,但代碼的可讀性并不十分理想,主要原因是在實(shí)現(xiàn)狀態(tài)之間的轉(zhuǎn)換時(shí),檢查轉(zhuǎn)換條件和進(jìn)行狀態(tài)轉(zhuǎn)換都是混雜在當(dāng)前狀態(tài)中來完成的。例如,當(dāng)城門處于Opened狀態(tài)時(shí),需要在相應(yīng)的case中調(diào)用closeDoor()函數(shù)來檢查是否有必要進(jìn)行狀態(tài)轉(zhuǎn)換,如果是的話則還需要調(diào)用changeState()函數(shù)將當(dāng)前狀態(tài)切換到Closed。顯然,如果在每種狀態(tài)下都需要分別檢查多個(gè)不同的轉(zhuǎn)換條件,并且需要根據(jù)檢查結(jié)果讓狀態(tài)機(jī)切換到不同的狀態(tài),那么這樣的代碼將是枯燥而難懂的。從代碼重構(gòu)的角度來講,此時(shí)更好的做法是引入checkStateChange()和performStateChange()兩個(gè)函數(shù),專門用來對轉(zhuǎn)換條件進(jìn)行檢查,以及激活轉(zhuǎn)換時(shí)所需要執(zhí)行的各種動(dòng)作。這樣一來,程序結(jié)構(gòu)將變得更加清晰:
|
但checkStateChange()和performStateChange()這兩個(gè)函數(shù)本身依然會(huì)在面對很復(fù)雜的狀態(tài)機(jī)時(shí),內(nèi)部邏輯變得異常臃腫,甚至可能是難以實(shí)現(xiàn)。
三、基于面向?qū)ο蟮?/span>FSM實(shí)現(xiàn)技術(shù)
3.1、用一個(gè)類實(shí)現(xiàn)FSM
class DoorFSM {
private:
States __Y;
std::queue<Event> __events;
void __processEvent( Event e );
protected:
virtual void enterOpened() = 0;
virtual void enterLocked() = 0;
virtual void enterUnlocked() = 0;
virtual void enterClosed() = 0;
public:
/* States */
enum States { Closed, Unlocked, Locked, Opened }; // states
/*Events*/
enum Event { Lock, Unlock, Open, Close };
/// Constructor
DoorFSM() { __Y = Opened; }
/// Destructor
virtual ~DoorFSM() {}
/** Get current FSM state
@returns current FSM state
*/
States currentState() { return __Y; }
/** Send event to FSM
Use this function to send event to DoorFSM After you call it given event will be handled, and, if some of transition conditions match, appropriate transition will be triggered, and currentState() will be changed. If this function is called during existing event handling process, given event will be added to pending event queue, and will be handled after current transition. See examples for details.
*/
void A( Event e );
};
void DoorFSM::__processEvent( Event e )
{
States yOld = __Y;
bool pass = false;
switch( __Y ) { //transitions
case Closed:
if( e == Open ) {
//outcome actions
__Y = Opened;
pass = true;
}
else if( e == Lock ) {
//outcome actions
__Y = Locked;
pass = true;
}
break;
case Unlocked:
if( e == Lock ) {
//outcome actions
__Y = Locked;
pass = true;
}
else if( e == Open ) {
//outcome actions
__Y = Opened;
pass = true;
}
break;
case Locked:
if( e == Unlock ) {
//outcome actions
__Y = Unlocked;
pass = true;
}
break;
case Opened:
if( e == Close ) {
//outcome actions
__Y = Closed;
pass = true;
}
break;
}
if( yOld == __Y && !pass ) { return; }
switch( __Y ) { // income actions
case Closed:
enterClosed();
break;
case Unlocked:
enterUnlocked();
break;
case Locked:
enterLocked();
break;
case Opened:
enterOpened();
break;
}
}
void DoorFSM::A( Event e )
{
bool __empty = __events.empty();
__events.push( e );
if( __empty ) {
while( !__events.empty() ) {
__processEvent( __events.front() );
__events.pop();
}
}
}
class DoorFSMLogic : public DoorFSM
{
protected:
virtual void enterOpened(){std::cout << "Enter Opened state." << std::endl;}
virtual void enterLocked() {std::cout << "Enter Closed state." << std::endl;}
virtual void enterUnlocked() {std::cout << "Enter Locked state." << std::endl;}
virtual void enterClosed() {std::cout << "Enter Unlocked state." << std::endl;}
};
測試程序
int main()
{
DoorFSMLogic door;
door.A(DoorFSM::Close);
door.A(DoorFSM::Lock);
door.A(DoorFSM::Unlock);
door.A(DoorFSM::Open);
}