找回密碼
 立即注冊

QQ登錄

只需一步,快速開始

搜索
查看: 1513|回復: 0
收起左側(cè)

C++ 狀態(tài)機問題

[復制鏈接]
ID:107189 發(fā)表于 2016-3-5 20:09 | 顯示全部樓層 |閱讀模式
有限自動機(Finite Automata Machine)是計算機科學的重要基石,它在軟件開發(fā)領(lǐng)域內(nèi)通常被稱作有限狀態(tài)機(Finite State Machine),是一種應用非常廣泛的軟件設(shè)計模式(Design Pattern)。本文介紹如何構(gòu)建基于狀態(tài)機的軟件系統(tǒng)。
一、什么是狀態(tài)機
有限狀態(tài)機是一種用來進行對象行為建模的工具,其作用主要是描述對象在它的生命周期內(nèi)所經(jīng)歷的狀態(tài)序列,以及如何響應來自外界的各種事件。在面向?qū)ο蟮能浖到y(tǒng)中,一個對象無論多么簡單或者多么復雜,都必然會經(jīng)歷一個從開始創(chuàng)建到最終消亡的完整過程,這通常被稱為對象的生命周期。一般說來,對象在其生命期內(nèi)是不可能完全孤立的,它必須通過發(fā)送消息來影響其它對象,或者通過接受消息來改變自身。在大多數(shù)情況下,這些消息都只不過是些簡單的、同步的方法調(diào)用而已。例如,在銀行客戶管理系統(tǒng)中,客戶類(Customer)的實例在需要的時候,可能會調(diào)用帳戶(Account)類中定義的getBalance()方法。在這種簡單的情況下,類Customer并不需要一個有限狀態(tài)機來描述自己的行為,主要原因在于它當前的行為并不依賴于過去的某個狀態(tài)。
遺憾的是并不是所有情況都會如此簡單,事實上許多實用的軟件系統(tǒng)都必須維護一兩個非常關(guān)鍵的對象,它們通常具有非常復雜的狀態(tài)轉(zhuǎn)換關(guān)系,而且需要對來自外部的各種異步事件進行響應。例如,在VoIP電話系統(tǒng)中,電話類(Telephone)的實例必須能夠響應來自對方的隨機呼叫,來自用戶的按鍵事件,以及來自網(wǎng)絡(luò)的信令等。在處理這些消息時,類Telephone所要采取的行為完全依賴于它當前所處的狀態(tài),因而此時使用狀態(tài)機就將是一個不錯的選擇。
游戲引擎是有限狀態(tài)機最為成功的應用領(lǐng)域之一,由于設(shè)計良好的狀態(tài)機能夠被用來取代部分的人工智能算法,因此游戲中的每個角色或者器件都有可能內(nèi)嵌一個狀態(tài)機?紤]RPG游戲中城門這樣一個簡單的對象,它具有打開(Opened)、關(guān)閉(Closed)、上鎖(Locked)、解鎖(Unlocked)四種狀態(tài),如圖1所示。當玩家到達一個處于狀態(tài)Locked的門時,如果此時他已經(jīng)找到了用來開門的鑰匙,那么他就可以利用它將門的當前狀態(tài)轉(zhuǎn)變?yōu)?font face="Times New Roman">Unlocked,進一步還可以通過旋轉(zhuǎn)門上的把手將其狀態(tài)轉(zhuǎn)變?yōu)?font face="Times New Roman">Opened,從而成功地進入城內(nèi)。
在描述有限狀態(tài)機時,狀態(tài)、事件、轉(zhuǎn)換和動作是經(jīng)常會碰到的幾個基本概念。
狀態(tài)(State) 指的是對象在其生命周期中的一種狀況,處于某個特定狀態(tài)中的對象必然會滿足某些條件、執(zhí)行某些動作或者是等待某些事件。
事件(Event) 指的是在時間和空間上占有一定位置,并且對狀態(tài)機來講是有意義的那些事情。事件通常會引起狀態(tài)的變遷,促使狀態(tài)機從一種狀態(tài)切換到另一種狀態(tài)。
轉(zhuǎn)換(Transition) 指的是兩個狀態(tài)之間的一種關(guān)系,表明對象將在第一個狀態(tài)中執(zhí)行一定的動作,并將在某個事件發(fā)生同時某個特定條件滿足時進入第二個狀態(tài)。
動作(Action) 指的是狀態(tài)機中可以執(zhí)行的那些原子操作,所謂原子操作指的是它們在運行的過程中不能被其他消息所中斷,必須一直執(zhí)行下去。
二、手工編寫狀態(tài)機
與其他常用的設(shè)計模式有所不同,程序員想要在自己的軟件系統(tǒng)中加入狀態(tài)機時,必須再額外編寫一部分用于邏輯控制的代碼,如果系統(tǒng)足夠復雜的話,這部分代碼實現(xiàn)和維護起來還是相當困難的。在實現(xiàn)有限狀態(tài)機時,使用switch語句是最簡單也是最直接的一種方式,其基本思路是為狀態(tài)機中的每一種狀態(tài)都設(shè)置一個case分支,專門用于對該狀態(tài)進行控制。下面的代碼示范了如何運用switch語句,來實現(xiàn)圖1中所示的狀態(tài)機:
switch (state)  {
  // 處理狀態(tài)Opened的分支
  case (Opened): {
    // 執(zhí)行動作Open
    open();
    // 檢查是否有CloseDoor事件
    if (closeDoor()) {
      // 當前狀態(tài)轉(zhuǎn)換為Closed
      changeState(Closed)
    }
    break;
  }
  // 處理狀態(tài)Closed的分支
  case (Closed): {
    // 執(zhí)行動作Close
    close();
    // 檢查是否有OpenDoor事件
    if (openDoor()) {
      // 當前狀態(tài)轉(zhuǎn)換為Opened
      changeState(Opened);
    }
    // 檢查是否有LockDoor事件
    if (lockDoor()) {
      // 當前狀態(tài)轉(zhuǎn)換為Locked
      changeState(Locked);
    }
    break;
  }
  // 處理狀態(tài)Locked的分支
  case (Locked): {
    // 執(zhí)行動作Lock
    lock();
    // 檢查是否有UnlockDoor事件
    if (unlockDoor()) {
      // 當前狀態(tài)轉(zhuǎn)換為Unlocked
      changeState(Unlocked);
    }
    break;
  }
  // 處理狀態(tài)Unlocked的分支
  case (Unlocked): {
    // 執(zhí)行動作Unlock
    unlock();
    // 檢查是否有LockDoor事件
    if (lockDoor()) {
      // 當前狀態(tài)轉(zhuǎn)換為Locked   
      changeState(Locked)
    }
    // 檢查是否有OpenDoor事件   
    if (openDoor()) {
      // 當前狀態(tài)轉(zhuǎn)換為Opened
      changeSate(Opened);
    }
    break;
  }
}
使用switch語句實現(xiàn)的有限狀態(tài)機的確能夠很好地工作,但代碼的可讀性并不十分理想,主要原因是在實現(xiàn)狀態(tài)之間的轉(zhuǎn)換時,檢查轉(zhuǎn)換條件和進行狀態(tài)轉(zhuǎn)換都是混雜在當前狀態(tài)中來完成的。例如,當城門處于Opened狀態(tài)時,需要在相應的case中調(diào)用closeDoor()函數(shù)來檢查是否有必要進行狀態(tài)轉(zhuǎn)換,如果是的話則還需要調(diào)用changeState()函數(shù)將當前狀態(tài)切換到Closed。顯然,如果在每種狀態(tài)下都需要分別檢查多個不同的轉(zhuǎn)換條件,并且需要根據(jù)檢查結(jié)果讓狀態(tài)機切換到不同的狀態(tài),那么這樣的代碼將是枯燥而難懂的。從代碼重構(gòu)的角度來講,此時更好的做法是引入checkStateChange()performStateChange()兩個函數(shù),專門用來對轉(zhuǎn)換條件進行檢查,以及激活轉(zhuǎn)換時所需要執(zhí)行的各種動作。這樣一來,程序結(jié)構(gòu)將變得更加清晰:
switch (state)  {
  // 處理狀態(tài)Opened的分支
  case (Opened): {
    // 執(zhí)行動作Open
    open();
    // 檢查是否有激發(fā)狀態(tài)轉(zhuǎn)換的事件產(chǎn)生
    if (checkStateChange()) {
      // 對狀態(tài)機的狀態(tài)進行轉(zhuǎn)換
      performStateChange();
    }
    break;
  }
  // 處理狀態(tài)Closed的分支
  case (Closed): {
    // 執(zhí)行動作Close
    close();
    // 檢查是否有激發(fā)狀態(tài)轉(zhuǎn)換的事件產(chǎn)生
    if (checkStateChange()) {
      // 對狀態(tài)機的狀態(tài)進行轉(zhuǎn)換
      performStateChange();
    }
    break;
  }
  // 處理狀態(tài)Locked的分支
  case (Locked): {
    // 執(zhí)行動作Lock
    lock();
    // 檢查是否有激發(fā)狀態(tài)轉(zhuǎn)換的事件產(chǎn)生
    if (checkStateChange()) {
      // 對狀態(tài)機的狀態(tài)進行轉(zhuǎn)換
      performStateChange();
    }
    break;
  }
  // 處理狀態(tài)Unlocked的分支
  case (Unlocked): {
    // 執(zhí)行動作Lock
    unlock();
    // 檢查是否有激發(fā)狀態(tài)轉(zhuǎn)換的事件產(chǎn)生
    if (checkStateChange()) {
      // 對狀態(tài)機的狀態(tài)進行轉(zhuǎn)換
      performStateChange();
    }
    break;
  }
}
checkStateChange()performStateChange()這兩個函數(shù)本身依然會在面對很復雜的狀態(tài)機時,內(nèi)部邏輯變得異常臃腫,甚至可能是難以實現(xiàn)。
在很長一段時期內(nèi),使用switch語句一直是實現(xiàn)有限狀態(tài)機的唯一方法,甚至像編譯器這樣復雜的軟件系統(tǒng),大部分也都直接采用這種實現(xiàn)方式。但之后隨著狀態(tài)機應用的逐漸深入,構(gòu)造出來的狀態(tài)機越來越復雜,這種方法也開始面臨各種嚴峻的考驗,其中最令人頭痛的是如果狀態(tài)機中的狀態(tài)非常多,或者狀態(tài)之間的轉(zhuǎn)換關(guān)系異常復雜,那么簡單地使用switch語句構(gòu)造出來的狀態(tài)機將是不可維護的。
三、自動生成狀態(tài)機
為實用的軟件系統(tǒng)編寫狀態(tài)機并不是一件十分輕松的事情,特別是當狀態(tài)機本身比較復雜的時候尤其如此,許多有過類似經(jīng)歷的程序員往往將其形容為"毫無創(chuàng)意"的過程,因為他們需要將大量的時間與精力傾注在如何管理好狀態(tài)機中的各種狀態(tài)上,而不是程序本身的運行邏輯。作為一種通用的軟件設(shè)計模式,各種軟件系統(tǒng)的狀態(tài)機之間肯定會或多或少地存在著一些共性,因此人們開始嘗試開發(fā)一些工具來自動生成有限狀態(tài)機的框架代碼,而在Linux下就有一個挺不錯的選擇──FSMEFinite State Machine Editor)。

回復

使用道具 舉報

您需要登錄后才可以回帖 登錄 | 立即注冊

本版積分規(guī)則

小黑屋|51黑電子論壇 |51黑電子論壇6群 QQ 管理員QQ:125739409;技術(shù)交流QQ群281945664

Powered by 單片機教程網(wǎng)

快速回復 返回頂部 返回列表