標(biāo)題: C++ 狀態(tài)機(jī)問題 [打印本頁]
作者: 51黑tt 時(shí)間: 2016-3-5 20:09
標(biāo)題: C++ 狀態(tài)機(jī)問題
有限自動(dòng)機(jī)（Finite Automata Machine）是計(jì)算機(jī)科學(xué)的重要基石，它在軟件開發(fā)領(lǐng)域內(nèi)通常被稱作有限狀態(tài)機(jī)（Finite State Machine），是一種應(yīng)用非常廣泛的軟件設(shè)計(jì)模式（Design Pattern）。本文介紹如何構(gòu)建基于狀態(tài)機(jī)的軟件系統(tǒng)。
一、什么是狀態(tài)機(jī)
有限狀態(tài)機(jī)是一種用來進(jìn)行對(duì)象行為建模的工具，其作用主要是描述對(duì)象在它的生命周期內(nèi)所經(jīng)歷的狀態(tài)序列，以及如何響應(yīng)來自外界的各種事件。在面向?qū)ο蟮能浖到y(tǒng)中，一個(gè)對(duì)象無論多么簡(jiǎn)單或者多么復(fù)雜，都必然會(huì)經(jīng)歷一個(gè)從開始創(chuàng)建到最終消亡的完整過程，這通常被稱為對(duì)象的生命周期。一般說來，對(duì)象在其生命期內(nèi)是不可能完全孤立的，它必須通過發(fā)送消息來影響其它對(duì)象，或者通過接受消息來改變自身。在大多數(shù)情況下，這些消息都只不過是些簡(jiǎn)單的、同步的方法調(diào)用而已。例如，在銀行客戶管理系統(tǒng)中，客戶類（Customer）的實(shí)例在需要的時(shí)候，可能會(huì)調(diào)用帳戶（Account）類中定義的getBalance()方法。在這種簡(jiǎn)單的情況下，類Customer并不需要一個(gè)有限狀態(tài)機(jī)來描述自己的行為，主要原因在于它當(dāng)前的行為并不依賴于過去的某個(gè)狀態(tài)。
遺憾的是并不是所有情況都會(huì)如此簡(jiǎn)單，事實(shí)上許多實(shí)用的軟件系統(tǒng)都必須維護(hù)一兩個(gè)非常關(guān)鍵的對(duì)象，它們通常具有非常復(fù)雜的狀態(tài)轉(zhuǎn)換關(guān)系，而且需要對(duì)來自外部的各種異步事件進(jìn)行響應(yīng)。例如，在VoIP電話系統(tǒng)中，電話類（Telephone）的實(shí)例必須能夠響應(yīng)來自對(duì)方的隨機(jī)呼叫，來自用戶的按鍵事件，以及來自網(wǎng)絡(luò)的信令等。在處理這些消息時(shí)，類Telephone所要采取的行為完全依賴于它當(dāng)前所處的狀態(tài)，因而此時(shí)使用狀態(tài)機(jī)就將是一個(gè)不錯(cuò)的選擇。
游戲引擎是有限狀態(tài)機(jī)最為成功的應(yīng)用領(lǐng)域之一，由于設(shè)計(jì)良好的狀態(tài)機(jī)能夠被用來取代部分的人工智能算法，因此游戲中的每個(gè)角色或者器件都有可能內(nèi)嵌一個(gè)狀態(tài)機(jī)�？紤]RPG游戲中城門這樣一個(gè)簡(jiǎn)單的對(duì)象，它具有打開（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)?font face="Times New Roman">Unlocked，進(jìn)一步還可以通過旋轉(zhuǎn)門上的把手將其狀態(tài)轉(zhuǎn)變?yōu)?font face="Times New Roman">Opened，從而成功地進(jìn)入城內(nèi)。
在描述有限狀態(tài)機(jī)時(shí)，狀態(tài)、事件、轉(zhuǎn)換和動(dòng)作是經(jīng)常會(huì)碰到的幾個(gè)基本概念。
狀態(tài)（State） 指的是對(duì)象在其生命周期中的一種狀況，處于某個(gè)特定狀態(tài)中的對(duì)象必然會(huì)滿足某些條件、執(zhí)行某些動(dòng)作或者是等待某些事件。
事件（Event） 指的是在時(shí)間和空間上占有一定位置，并且對(duì)狀態(tài)機(jī)來講是有意義的那些事情。事件通常會(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è)特定條件滿足時(shí)進(jìn)入第二個(gè)狀態(tài)。
動(dòng)作（Action） 指的是狀態(tài)機(jī)中可以執(zhí)行的那些原子操作，所謂原子操作指的是它們?cè)谶\(yùn)行的過程中不能被其他消息所中斷，必須一直執(zhí)行下去。
二、手工編寫狀態(tài)機(jī)
與其他常用的設(shè)計(jì)模式有所不同，程序員想要在自己的軟件系統(tǒng)中加入狀態(tài)機(jī)時(shí)，必須再額外編寫一部分用于邏輯控制的代碼，如果系統(tǒng)足夠復(fù)雜的話，這部分代碼實(shí)現(xiàn)和維護(hù)起來還是相當(dāng)困難的。在實(shí)現(xiàn)有限狀態(tài)機(jī)時(shí)，使用switch語句是最簡(jiǎn)單也是最直接的一種方式，其基本思路是為狀態(tài)機(jī)中的每一種狀態(tài)都設(shè)置一個(gè)case分支，專門用于對(duì)該狀態(tài)進(jìn)行控制。下面的代碼示范了如何運(yùn)用switch語句，來實(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語句實(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ù)，專門用來對(duì)轉(zhuǎn)換條件進(jìn)行檢查，以及激活轉(zhuǎn)換時(shí)所需要執(zhí)行的各種動(dòng)作。這樣一來，程序結(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語句一直是實(shí)現(xiàn)有限狀態(tài)機(jī)的唯一方法，甚至像編譯器這樣復(fù)雜的軟件系統(tǒng)，大部分也都直接采用這種實(shí)現(xiàn)方式。但之后隨著狀態(tài)機(jī)應(yīng)用的逐漸深入，構(gòu)造出來的狀態(tài)機(jī)越來越復(fù)雜，這種方法也開始面臨各種嚴(yán)峻的考驗(yàn)，其中最令人頭痛的是如果狀態(tài)機(jī)中的狀態(tài)非常多，或者狀態(tài)之間的轉(zhuǎn)換關(guān)系異常復(fù)雜，那么簡(jiǎn)單地使用switch語句構(gòu)造出來的狀態(tài)機(jī)將是不可維護(hù)的。
三、自動(dòng)生成狀態(tài)機(jī)
為實(shí)用的軟件系統(tǒng)編寫狀態(tài)機(jī)并不是一件十分輕松的事情，特別是當(dāng)狀態(tài)機(jī)本身比較復(fù)雜的時(shí)候尤其如此，許多有過類似經(jīng)歷的程序員往往將其形容為"毫無創(chuàng)意"的過程，因?yàn)樗麄冃枰獙⒋罅康臅r(shí)間與精力傾注在如何管理好狀態(tài)機(jī)中的各種狀態(tài)上，而不是程序本身的運(yùn)行邏輯。作為一種通用的軟件設(shè)計(jì)模式，各種軟件系統(tǒng)的狀態(tài)機(jī)之間肯定會(huì)或多或少地存在著一些共性，因此人們開始嘗試開發(fā)一些工具來自動(dòng)生成有限狀態(tài)機(jī)的框架代碼，而在Linux下就有一個(gè)挺不錯(cuò)的選擇──FSME（Finite State Machine Editor）。
| 歡迎光臨 (http://www.raoushi.com/bbs/) |
Powered by Discuz! X3.1 |