日韩黑丝制服一区视频播放|日韩欧美人妻丝袜视频在线观看|九九影院一级蜜桃|亚洲中文在线导航|青草草视频在线观看|婷婷五月色伊人网站|日本一区二区在线|国产AV一二三四区毛片|正在播放久草视频|亚洲色图精品一区

分享

有限狀態(tài)機(jī)與c-c++語(yǔ)言實(shí)現(xiàn)

 知識(shí)池塘 2014-09-27

有限狀態(tài)機(jī)(Finite State Machine或者Finite State Automata)是軟件領(lǐng)域中一種重要的工具,很多東西的模型實(shí)際上就是有限狀態(tài)機(jī)。

最近看了一些游戲編程AI的材料,感覺(jué)游戲中的AI,第一要說(shuō)的就是有限狀態(tài)機(jī)來(lái)實(shí)現(xiàn)精靈的AI,然后才是A*尋路,其他學(xué)術(shù)界討論比較多的神經(jīng)網(wǎng)絡(luò)、模糊控制等問(wèn)題還不是很熱。

FSM的實(shí)現(xiàn)方式:
1) switch/case或者if/else
這無(wú)意是最直觀的方式,使用一堆條件判斷,會(huì)編程的人都可以做到,對(duì)簡(jiǎn)單小巧的狀態(tài)機(jī)來(lái)說(shuō)最合適,但是毫無(wú)疑問(wèn),這樣的方式比較原始,對(duì)龐大的狀態(tài)機(jī)難以維護(hù)。

2) 狀態(tài)表
維護(hù)一個(gè)二維狀態(tài)表,橫坐標(biāo)表示當(dāng)前狀態(tài),縱坐標(biāo)表示輸入,表中一個(gè)元素存儲(chǔ)下一個(gè)狀態(tài)和對(duì)應(yīng)的操作。這一招易于維護(hù),但是運(yùn)行時(shí)間和存儲(chǔ)空間的代價(jià)較大。

3) 使用State Pattern
使用State Pattern使得代碼的維護(hù)比switch/case方式稍好,性能上也不會(huì)有很多的影響,但是也不是100%完美。不過(guò)Robert C. Martin做了兩個(gè)自動(dòng)產(chǎn)生FSM代碼的工具,for java和for C++各一個(gè),在http://www./resources/index上有免費(fèi)下載,這個(gè)工具的輸入是純文本的狀態(tài)機(jī)描述,自動(dòng)產(chǎn)生符合State Pattern的代碼,這樣developer的工作只需要維護(hù)狀態(tài)機(jī)的文本描述,每必要冒引入bug的風(fēng)險(xiǎn)去維護(hù)code。

4) 使用宏定義描述狀態(tài)機(jī)
一般來(lái)說(shuō),C++編程中應(yīng)該避免使用#define,但是這主要是因?yàn)槿绻煤陙?lái)定義函數(shù)的話(huà),很容易產(chǎn)生這樣那樣的問(wèn)題,但是巧妙的使用,還是能夠產(chǎn)生奇妙的效果。MFC就是使用宏定義來(lái)實(shí)現(xiàn)大的架構(gòu)的。
在實(shí)現(xiàn)FSM的時(shí)候,可以把一些繁瑣無(wú)比的if/else還有花括號(hào)的組合放在宏中,這樣,在代碼中可以3)中狀態(tài)機(jī)描述文本一樣寫(xiě),通過(guò)編譯器的預(yù)編譯處理產(chǎn)生1)一樣的效果,我見(jiàn)過(guò)產(chǎn)生C代碼的宏,如果要產(chǎn)生C++代碼,己軟MFC可以,那么理論上也是可行的。
 

 

 

 

一.引言言

有限狀態(tài)機(jī)是一種用來(lái)進(jìn)行對(duì)象行為建模的工具,其作用主要是描述對(duì)象在它的生命周期內(nèi)所經(jīng)歷的狀態(tài)序列,以及如何響應(yīng)來(lái)自外界的各種事件。在面向?qū)ο蟮能浖到y(tǒng)中,一個(gè)對(duì)象無(wú)論多么簡(jiǎn)單或者多么復(fù)雜,都必然會(huì)經(jīng)歷一個(gè)從開(kāi)始創(chuàng)建到最終消亡的完整過(guò)程,這通常被稱(chēng)為對(duì)象的生命周期。一般說(shuō)來(lái),對(duì)象在其生命期內(nèi)是不可能完全孤立的,它必須通過(guò)發(fā)送消息來(lái)影響其它對(duì)象,或者通過(guò)接受消息來(lái)改變自身。在大多數(shù)情況下,這些消息都只不過(guò)是些簡(jiǎn)單的、同步的方法調(diào)用而已。例如,在銀行客戶(hù)管理系統(tǒng)中,客戶(hù)類(lèi)(Customer)的實(shí)例在需要的時(shí)候,可能會(huì)調(diào)用帳戶(hù)(Account)類(lèi)中定義的getBalance()方法。在這種簡(jiǎn)單的情況下,類(lèi)Customer并不需要一個(gè)有限狀態(tài)機(jī)來(lái)描述自己的行為,主要原因在于它當(dāng)前的行為并不依賴(lài)于過(guò)去的某個(gè)狀態(tài)。[1]

遺憾的是并不是所有情況都會(huì)如此簡(jiǎn)單,事實(shí)上許多實(shí)用的軟件系統(tǒng)都必須維護(hù)一兩個(gè)非常關(guān)鍵的對(duì)象,它們通常具有非常復(fù)雜的狀態(tài)轉(zhuǎn)換關(guān)系,而且需要對(duì)來(lái)自外部的各種異步事件進(jìn)行響應(yīng)。例如,在VoIP電話(huà)系統(tǒng)中,電話(huà)類(lèi)(Telephone)的實(shí)例必須能夠響應(yīng)來(lái)自對(duì)方的隨機(jī)呼叫,來(lái)自用戶(hù)的按鍵事件,以及來(lái)自網(wǎng)絡(luò)的信令等。在處理這些消息時(shí),類(lèi)Telephone所要采取的行為完全依賴(lài)于它當(dāng)前所處的狀態(tài),因而此時(shí)使用狀態(tài)機(jī)就將是一個(gè)不錯(cuò)的選擇。[1]

游戲引擎是有限狀態(tài)機(jī)最為成功的應(yīng)用領(lǐng)域之一,由于設(shè)計(jì)良好的狀態(tài)機(jī)能夠被用來(lái)取代部分的人工智能算法,因此游戲中的每個(gè)角色或者器件都有可能內(nèi)嵌一個(gè)狀態(tài)機(jī)??紤]RPG游戲中城門(mén)這樣一個(gè)簡(jiǎn)單的對(duì)象,它具有打開(kāi)(Opened)、關(guān)閉(Closed)、上鎖(Locked)、解鎖(Unlocked)四種狀態(tài),如圖1所示。當(dāng)玩家到達(dá)一個(gè)處于狀態(tài)Locked的門(mén)時(shí),如果此時(shí)他已經(jīng)找到了用來(lái)開(kāi)門(mén)的鑰匙,那么他就可以利用它將門(mén)的當(dāng)前狀態(tài)轉(zhuǎn)變?yōu)?/span>Unlocked,進(jìn)一步還可以通過(guò)旋轉(zhuǎn)門(mén)上的把手將其狀態(tài)轉(zhuǎn)變?yōu)?/span>Opened,從而成功地進(jìn)入城內(nèi)。[1]

1 控制城門(mén)的狀態(tài)機(jī)

在描述有限狀態(tài)機(jī)時(shí),狀態(tài)、事件、轉(zhuǎn)換和動(dòng)作是經(jīng)常會(huì)碰到的幾個(gè)基本概念。

狀態(tài)(State指的是對(duì)象在其生命周期中的一種狀況,處于某個(gè)特定狀態(tài)中的對(duì)象必然會(huì)滿(mǎn)足某些條件、執(zhí)行某些動(dòng)作或者是等待某些事件。

事件(Event指的是在時(shí)間和空間上占有一定位置,并且對(duì)狀態(tài)機(jī)來(lái)講是有意義的那些事情。事件通常會(huì)引起狀態(tài)的變遷,促使?fàn)顟B(tài)機(jī)從一種狀態(tài)切換到另一種狀態(tài)。

轉(zhuǎn)換(Transition指的是兩個(gè)狀態(tài)之間的一種關(guān)系,表明對(duì)象將在第一個(gè)狀態(tài)中執(zhí)行一定的動(dòng)作,并將在某個(gè)事件發(fā)生同時(shí)某個(gè)特定條件滿(mǎn)足時(shí)進(jìn)入第二個(gè)狀態(tài)。

   動(dòng)作(Action指的是狀態(tài)機(jī)中可以執(zhí)行的那些原子操作,所謂原子操作指的是它們?cè)谶\(yùn)行的過(guò)程中不能被其他消息所中斷,必須一直執(zhí)行下去。

二、基于傳統(tǒng)C語(yǔ)言的FSM實(shí)現(xiàn)技術(shù)

2.1、基于switch(狀態(tài))的實(shí)現(xiàn)

在實(shí)現(xiàn)有限狀態(tài)機(jī)時(shí),使用switch語(yǔ)句是最簡(jiǎn)單也是最直接的一種方式,其基本思路是為狀態(tài)機(jī)中的每一種狀態(tài)都設(shè)置一個(gè)case分支,專(zhuān)門(mén)用于對(duì)該狀態(tài)進(jìn)行控制。下面的代碼示范了如何運(yùn)用switch語(yǔ)句,來(lái)實(shí)現(xiàn)圖1中所示的狀態(tài)機(jī):

 

 
switch (state)  {
  // 處理狀態(tài)Opened的分支
  case (Opened): {
    // 執(zhí)行動(dòng)作Open
    open();
    // 檢查是否有CloseDoor事件
    if (closeDoor()) { 
      // 當(dāng)前狀態(tài)轉(zhuǎn)換為Closed
      changeState(Closed)
    }
    break;
  } 
  // 處理狀態(tài)Closed的分支
  case (Closed): {
    // 執(zhí)行動(dòng)作Close
    close();
    // 檢查是否有OpenDoor事件
    if (openDoor()) {
      // 當(dāng)前狀態(tài)轉(zhuǎn)換為Opened
      changeState(Opened);
    }
    // 檢查是否有LockDoor事件
    if (lockDoor()) {
      // 當(dāng)前狀態(tài)轉(zhuǎn)換為Locked
      changeState(Locked);
    }
    break;
  }
 
  // 處理狀態(tài)Locked的分支
  case (Locked): {
    // 執(zhí)行動(dòng)作Lock
    lock();
    // 檢查是否有UnlockDoor事件
    if (unlockDoor()) {
      // 當(dāng)前狀態(tài)轉(zhuǎn)換為Unlocked
      changeState(Unlocked);
    }
    break;
  }
 
  // 處理狀態(tài)Unlocked的分支
  case (Unlocked): {
    // 執(zhí)行動(dòng)作Unlock
    unlock();
    // 檢查是否有LockDoor事件
    if (lockDoor()) {
      // 當(dāng)前狀態(tài)轉(zhuǎn)換為Locked    
      changeState(Locked)
    }
    // 檢查是否有OpenDoor事件    
    if (openDoor()) {
      // 當(dāng)前狀態(tài)轉(zhuǎn)換為Opened
      changeSate(Opened);
    }
    break;
  } 
}

使用switch語(yǔ)句實(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)中來(lái)完成的。例如,當(dāng)城門(mén)處于Opened狀態(tài)時(shí),需要在相應(yīng)的case中調(diào)用closeDoor()函數(shù)來(lái)檢查是否有必要進(jìn)行狀態(tài)轉(zhuǎn)換,如果是的話(huà)則還需要調(diào)用changeState()函數(shù)將當(dāng)前狀態(tài)切換到Closed。顯然,如果在每種狀態(tài)下都需要分別檢查多個(gè)不同的轉(zhuǎn)換條件,并且需要根據(jù)檢查結(jié)果讓狀態(tài)機(jī)切換到不同的狀態(tài),那么這樣的代碼將是枯燥而難懂的。從代碼重構(gòu)的角度來(lái)講,此時(shí)更好的做法是引入checkStateChange()performStateChange()兩個(gè)函數(shù),專(zhuān)門(mén)用來(lái)對(duì)轉(zhuǎn)換條件進(jìn)行檢查,以及激活轉(zhuǎn)換時(shí)所需要執(zhí)行的各種動(dòng)作。這樣一來(lái),程序結(jié)構(gòu)將變得更加清晰:

 

 
switch (state)  {
 
  // 處理狀態(tài)Opened的分支
  case (Opened): {
    // 執(zhí)行動(dòng)作Open
    open();
    // 檢查是否有激發(fā)狀態(tài)轉(zhuǎn)換的事件產(chǎn)生
    if (checkStateChange()) {
      // 對(duì)狀態(tài)機(jī)的狀態(tài)進(jìn)行轉(zhuǎn)換
      performStateChange();
    }
    break;
  } 
  // 處理狀態(tài)Closed的分支
  case (Closed): {
    // 執(zhí)行動(dòng)作Close
    close();
    // 檢查是否有激發(fā)狀態(tài)轉(zhuǎn)換的事件產(chǎn)生
    if (checkStateChange()) {
      // 對(duì)狀態(tài)機(jī)的狀態(tài)進(jìn)行轉(zhuǎn)換
      performStateChange();
    }
    break;
  }
 
  // 處理狀態(tài)Locked的分支
  case (Locked): {
    // 執(zhí)行動(dòng)作Lock
    lock();
    // 檢查是否有激發(fā)狀態(tài)轉(zhuǎn)換的事件產(chǎn)生
    if (checkStateChange()) {
      // 對(duì)狀態(tài)機(jī)的狀態(tài)進(jìn)行轉(zhuǎn)換
      performStateChange();
    }
    break;
  }
 
  // 處理狀態(tài)Unlocked的分支
  case (Unlocked): {
    // 執(zhí)行動(dòng)作Lock
    unlock();
    // 檢查是否有激發(fā)狀態(tài)轉(zhuǎn)換的事件產(chǎn)生
    if (checkStateChange()) {
      // 對(duì)狀態(tài)機(jī)的狀態(tài)進(jìn)行轉(zhuǎn)換
      performStateChange();
    }
    break;
  } 
}

checkStateChange()performStateChange()這兩個(gè)函數(shù)本身依然會(huì)在面對(duì)很復(fù)雜的狀態(tài)機(jī)時(shí),內(nèi)部邏輯變得異常臃腫,甚至可能是難以實(shí)現(xiàn)。

在很長(zhǎng)一段時(shí)期內(nèi),使用switch語(yǔ)句一直是實(shí)現(xiàn)有限狀態(tài)機(jī)的唯一方法,甚至像編譯器這樣復(fù)雜的軟件系統(tǒng),大部分也都直接采用這種實(shí)現(xiàn)方式。但之后隨著狀態(tài)機(jī)應(yīng)用的逐漸深入,構(gòu)造出來(lái)的狀態(tài)機(jī)越來(lái)越復(fù)雜,這種方法也開(kāi)始面臨各種嚴(yán)峻的考驗(yàn),其中最令人頭痛的是如果狀態(tài)機(jī)中的狀態(tài)非常多,或者狀態(tài)之間的轉(zhuǎn)換關(guān)系異常復(fù)雜,那么簡(jiǎn)單地使用switch語(yǔ)句構(gòu)造出來(lái)的狀態(tài)機(jī)將是不可維護(hù)的。

三、基于面向?qū)ο蟮?/span>FSM實(shí)現(xiàn)技術(shù)

3.1、用一個(gè)類(lèi)實(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;}

};

測(cè)試程序

int main()

{

  DoorFSMLogic door;

  door.A(DoorFSM::Close);

  door.A(DoorFSM::Lock);

  door.A(DoorFSM::Unlock);

  door.A(DoorFSM::Open);

}

  -關(guān)于FSM

    本站是提供個(gè)人知識(shí)管理的網(wǎng)絡(luò)存儲(chǔ)空間,所有內(nèi)容均由用戶(hù)發(fā)布,不代表本站觀點(diǎn)。請(qǐng)注意甄別內(nèi)容中的聯(lián)系方式、誘導(dǎo)購(gòu)買(mǎi)等信息,謹(jǐn)防詐騙。如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容,請(qǐng)點(diǎn)擊一鍵舉報(bào)。
    轉(zhuǎn)藏 分享 獻(xiàn)花(0

    0條評(píng)論

    發(fā)表

    請(qǐng)遵守用戶(hù) 評(píng)論公約

    類(lèi)似文章 更多