這是GAMEGEMS中的第三章的第一部分，番的不好。你可以直接閱讀原文。原本以為這是人工智能的部分，看到一半才發(fā)現(xiàn)只是一個簡單的框架。如果你想學人工智能，這里沒有，就不要浪費時間了。由于本人水平有限，其中難免會出現(xiàn)原則性的錯誤，希望指正。
關鍵字：有限狀態(tài)機、狀態(tài)、輸入、狀態(tài)轉(zhuǎn)換、輸出狀態(tài)當前狀態(tài)
一個有限狀態(tài)機類
在這篇文章中，我們創(chuàng)建了一個通用的有限狀態(tài)機（FSM）的C++類。有限狀態(tài)機是計算機科學和數(shù)學理論的抽象，它在許多的方面是很有用處的。這里我們不去講解有限狀態(tài)機的理論上的知識。而是講如何實現(xiàn)一個“有限狀態(tài)機”，“有限狀態(tài)機”在游戲的人工智能方面是很有用處的。
“有限狀態(tài)機”是由有限的狀態(tài)組成的一個機制。一個“狀態(tài)”就是一個狀況。你考慮一下門；它的“狀態(tài)”有“開”或“關”以及“鎖”與“未鎖”。
對于一個“有限狀態(tài)機”，它應該有一個“輸入”。這個“輸入”可以影響“狀態(tài)轉(zhuǎn)換”。“有限狀態(tài)機”應該有一個簡單（或復雜）的狀態(tài)轉(zhuǎn)換函數(shù)，這個函數(shù)可以決定什么狀態(tài)可以變成“當前狀態(tài)”。
這個當前的新狀態(tài)被稱為“有限狀態(tài)機”的“狀態(tài)轉(zhuǎn)換”的“輸出狀態(tài)”。如果你對這個概念有些迷惑，就把“門”做為理解“有限狀態(tài)機”的例子。當一個“門”處于“關閉”狀態(tài)和“鎖”狀態(tài)，當你輸入了“使用鑰匙”時，門的狀態(tài)可以變成“未鎖”狀態(tài)（即“狀態(tài)轉(zhuǎn)換”的輸出狀態(tài)，也就是門的當前狀態(tài)）。當你輸入了“使用手”時，門的狀態(tài)可以轉(zhuǎn)換成“開”的狀態(tài)。當門處于“開”的狀態(tài)時，我們輸入“使用手”時，會使門的狀態(tài)重新回到“關”的狀態(tài)。當“門”處于“關”的狀態(tài)時，我們輸入“使用鑰匙”時，這將會使門重新回到“鎖”的狀態(tài)。當門處于“鎖”的狀態(tài)，我們輸入“使用手”，就不能把門的狀態(tài)轉(zhuǎn)換到“開”的狀態(tài)，門仍然會保持“鎖”的狀態(tài)。還有，當門處于“開”的狀態(tài)時，我們輸入“使用鑰匙”是不能把門的狀態(tài)轉(zhuǎn)換成“鎖”的狀態(tài)的。
總之，“有限狀態(tài)機”是一個有限的狀態(tài)組成的，其中的一個狀態(tài)是“當前狀態(tài)”。“有限狀態(tài)機”可以接受一個“輸入”，這個“輸入”的結(jié)果將導致一個“狀態(tài)轉(zhuǎn)換”的發(fā)生（即從“當前狀態(tài)”轉(zhuǎn)換到“輸出”狀態(tài)）。這個“狀態(tài)轉(zhuǎn)換”是基于“狀態(tài)轉(zhuǎn)換函數(shù)”的。狀態(tài)轉(zhuǎn)換完成之后，“輸出狀態(tài)”即變成了“當前狀態(tài)”。
輸入 狀態(tài)轉(zhuǎn)換函數(shù)
當前狀態(tài)-----》狀態(tài)轉(zhuǎn)換-------------》輸出狀態(tài)（當前狀態(tài)）
那么，人們是如何將這個概念應用到游戲的AI系統(tǒng)中的呢？有限狀態(tài)機的功能很多：管理游戲世界、模擬NPC的思維、維護游戲狀態(tài)、分析玩游戲的人的輸入，或者管理一個對象的狀態(tài)。
假如在一個冒險游戲中有一個NPC，名字可以叫MONSTER。我們可以先假設這個MONSTER在游戲中有如下的狀態(tài)：BERSERK、RAGE、MAD、ANNOYED以及UNCARING。（前幾個狀態(tài)不好分別）。假設，MONSTER對于不同的狀態(tài)可以執(zhí)行不同的操作，并且假設你已經(jīng)有了這些不同操作的代碼。我們這時可以使用“有限狀態(tài)機”來模擬這個MONSTER的行為了。只要我們給出不同的“輸入”，MONSTER就會做出不同的反應。我們再來指出這些“輸入”是什么：PLAYER SEEN、PLAYER ATTACKS、PLAYERGONE、MONSTER HURT、MONSTER HEALED。這樣我們可以得到一個狀態(tài)轉(zhuǎn)換的表格，如下：游戲狀態(tài)轉(zhuǎn)換表：
當前狀態(tài) 輸入 輸出狀態(tài)
UNCARING PLAYER SEEN ANNOYED
UNCARING PLAYER ATTACKS MAD
MAD MONSTER HURT RAGE
MAD MONSTER HEALED UNCARING
RAGE MONSTER HURT BERSERK
RAGE MONSTER HEALED ANNOYED
BERSERK MONSTER HURT BERSERK
BERSERK MONSTER HEALED RAGE
ANNOYED PLAYER GONE UNCARING
ANNOYED PLAYER ATTACKS RAGE
ANNOYED MONSTER HEALED UNCARING
根據(jù)上面的這個表格，我們可以很容易的畫出一個MONSTER的“狀態(tài)轉(zhuǎn)換圖”，MONSTER的每一個狀態(tài)就是圖中的頂點。
因此，根據(jù)當前狀態(tài)和對FSM的輸入，MONSTER的狀態(tài)將被改變。這時根據(jù)MONSTER的狀態(tài)執(zhí)行相應操作的代碼（假設已經(jīng)實現(xiàn)）將被執(zhí)行，這時MONSTER好像是具備了人工智能。顯然，我們可以定義更多的“狀態(tài)”，寫出更多的“輸入”，寫出更多的“狀態(tài)轉(zhuǎn)換”，這樣，MONSTER可以表現(xiàn)的更真實，生動，當然，這些游戲的規(guī)則問題應該是策劃制定的。
FSMclass以及FSMstate
現(xiàn)在，我們?nèi)绾伟堰@些方法變成現(xiàn)實？使用FSMclass和它的組成部分FSMstate可以實現(xiàn)這些想法。
定義FSMstate
class FSMstate
{
unsigned m_usNumberOfTransition; //狀態(tài)的最大數(shù)
int* m_piInputs; //為了轉(zhuǎn)換而使用的輸入數(shù)組
int* m_piOutputState; //輸出狀態(tài)數(shù)組
int m_iStateID; //這個狀態(tài)的唯一標識符
public:
//一個構(gòu)造函數(shù)，可以接受這個狀態(tài)的ID和它支持的轉(zhuǎn)換數(shù)目
FSMstate(int iStateID,unsigned usTransitions);
//析構(gòu)函數(shù)，清除分配的數(shù)組
~FSMstate();
//取這個狀態(tài)的ID
int GetID(){return m_iStateID;}
//向數(shù)組中增加狀態(tài)轉(zhuǎn)換
void AddTransition(int iInput,int iOutputID);
//從數(shù)組中刪除一個狀態(tài)轉(zhuǎn)換
void DeleteTransition(int iOutputID);
//進行狀態(tài)轉(zhuǎn)換并得到輸出狀態(tài)
int GetOutput(int iInput);
};
對這個類的分析：
功能：主要是實現(xiàn)與一個狀態(tài)相關的各種操作。我們前面假設了MONSTER的各種狀態(tài)：
#define STATE_ID_UNCARING 1
#define STATE_ID_MAD 2
#define STATE_ID_RAGE 3
#define STATE_ID_BERSERK 4
#define STATE_ID_ANNOYED 5
狀態(tài)轉(zhuǎn)換所需的輸入有：
#define INPUT_ID_PLAYER_SEEN 1
#define INPUT_ID_PLAYER_ATTACK 2
#define INPUT_ID_PLAYER_GONE 3
#define INPUT_ID_MONSTER_HURT 4
#define INPUT_ID_MONSTER_HEALED 5
以上是五個狀態(tài)的標識符。
我們就要聲明5個FSMstate的實例，每一個實例代表一個狀態(tài)和與之有關的操作。假設我們先處理狀態(tài)STATE_ID_MAD
類成員變量m_iStateID就等于STATE_ID_MAD類成員變量m_usNumberOfTransition就是可由這個狀態(tài)轉(zhuǎn)換成的狀態(tài)的個數(shù)，前面有一個表，其中有兩個狀態(tài)可以由這個狀態(tài)產(chǎn)生，它們分別是STATE_ID_UNCARING和STATE_ID_RAGE。
這時，m_usNumberOfTransition等于2。
m_piInputs是一個指針變量，它保存與這個狀態(tài)相關的輸入，在前面的表中我們知道與STATE_ID_MAD相關的輸入為
INPUT_ID_MONSTER_HURT和INPUT_ID_MONSTER_HEALED，因此m_piInputs中存放的是這兩個數(shù)據(jù)。
而m_piOutputState存放的是與STATE_ID_MAD相關的狀態(tài)，即STATE_ID_RAGE和STATE_ID_UNCARING，這樣，m_piOutputState中存放的數(shù)據(jù)便是這兩個值。
以上是對成員變量的解釋，下面解釋成員函數(shù)：
構(gòu)造函數(shù)
FSMstate::FSMstate(int iStateID,unsigned usTransitions)
{
if(!usTransitions) //如果給出的轉(zhuǎn)換數(shù)量為0，就算為1
m_usNumberOfTransitions=1;
else
m_usNumberOfTransitions=usTransitions;
//將狀態(tài)的ID保存起來
m_iStateID=iStateID;
//分配內(nèi)存空間
try
{
m_piInputs=new int[m_usNumberOfTransitions];
for(int i=0;i<m_usNumberOfTransitions;++i)
m_piInputs[i]=0;
}
catch(...)
{
throw;
}
try
{
m_piOutputState=new int[m_usNumberOfTransition];
for(int i=0;i<m_usNumberOfTransitions;++i)
m_piOutputState[i]=0;
}
catch(...)
{
delete [] m_piInputs;
throw;
}
}
這就是構(gòu)造函數(shù)，在FSMstate類中共有四個成員變量，在這個函數(shù)中全部被初始化了。FSMstate是一個類，是否還記得MONSTER的狀態(tài)（如MAD、UNCARING）。這個類就是實現(xiàn)對MONSTER的一個狀態(tài)的管理的。假如這個狀態(tài)是STATE_ID_MAD，與這個狀態(tài)相關的狀態(tài)有兩個，上面已經(jīng)講過了。這時我們給成員變量賦值，在這個具體例子中它們的值如下：
m_usNumberOfTransition=2
m_piInput[0]=0;
m_piInput[1]=0;
m_piOutputState[0]=0;
m_piOutputState[1]=0;
m_iStateID=STATE_ID_MAD;
析構(gòu)函數(shù)：
FSMState::~FSMState()
{
delete [] m_piInputs;
delete [] m_piOutputState;
}
析構(gòu)函數(shù)將動態(tài)分配的存儲空間釋放了。
void FSMstate::AddTransition(int iInput,int iOutputID)
{
for(int i=0;i<m_usNumberOfTransitions;++i)
if(!m_piOutputState[i]) break;
if(i<m_usNumberOfTransition)
{
m_piOutputState[i]=iOutputID;
m_piInputs[i]=iInput;
}
}
這個函數(shù)給兩個前面構(gòu)造函數(shù)動態(tài)分配的空間加入數(shù)據(jù)，首先要找到兩個數(shù)組中找到適當?shù)奈恢茫螅绻恢檬呛戏ǖ?span lang="EN-US">
我們就可以把數(shù)據(jù)加入這兩個數(shù)組中。因為STATE_ID_MAD與兩個狀態(tài)有關，因此，我們可以調(diào)用兩次這個函數(shù)，把這兩個狀態(tài)加入到類中：
AddTransition(INPUT_ID_MONSTER_HURT,STATE_ID_RAGE);
AddTransition(INPUT_ID_MONSTER_HEALED,STATE_ID_UNCARING)
這樣，與狀態(tài)STATE_ID_MAD相關的“狀態(tài)”和“輸入”也加入了。
void FSMstate::DeleteTransition(int iOutputID)
{
// 遍歷每一個輸出狀態(tài)
for(int i=0;i<m_usNumberOfTransitions;++i)
{
//如果找到輸出狀態(tài)，退出循環(huán)
if(m_piOutputState[i]==iOutputID)
break;
}
//如果沒有找到輸出狀態(tài)，返回
if(i>=m_usNumberOfTransitions)
return;
//將輸出狀態(tài)的內(nèi)容置0
m_piInputs[i]=0;
m_piOutputState[i]=0;
//被刪除的輸出狀態(tài)的后面的輸出狀態(tài)前移
for(;i<(m_usNumberOfTransition-1);++i)
{
if(!m_piOUtputState[i])
break;
m_piInputs[i]=m_piInputs[i+1];
m_piOutputState[i]=m_piOutputState[i+1];
}
//最后面的輸出狀態(tài)置0
m_piInputs[i]=0;
m_piOutputState[i]=0;
}
這個函數(shù)是要刪除與一個狀態(tài)相關的輸出狀態(tài)。設一個狀態(tài)STATE_ID_MAD，與之相關的狀態(tài)有兩個STATE_ID_RAGE,STATE_ID_UNCARING，當然這是經(jīng)過初始化以及前面的添加狀態(tài)函數(shù)之后，產(chǎn)生了這兩個相關的狀態(tài)。你想刪除哪一個？如果你想刪除相關的輸出狀態(tài)，只要在刪除函數(shù)中指出那個狀態(tài)即可，例如：
DeleteTransition(STATE_ID_RAGE);
你就可以刪除輸出狀態(tài)STATE_ID_RAGE了。
int FSMstate::GetOutput(int iInput)
{
//先給輸出狀態(tài)賦值（如果未找到與輸入對應的輸出狀態(tài)時，返回這個值）
int iOutputID=m_iStateID;
//遍歷輸出狀態(tài)
for(int i=0;i<m_usNumberOfTransitions;++i)
{
//如果沒找到，退出循環(huán)
if(!m_piOutputState[i])
break;
//如果找到了與“輸入”相對應的“輸出狀態(tài)”，進行賦值。
if(iInput==m_piInputs[i])
{
iOutputID=m_piOutputState[i];
break;
}
}
//返回“輸出狀態(tài)”
return(iOutputID);
}
這個函數(shù)功能是返回與“輸入”相對應的“輸出狀態(tài)”的標識。如果沒有與“輸入”相對應的“輸出狀態(tài)”，返回原來的狀態(tài)，如果有與之對應的“輸出狀態(tài)”，返回這個狀態(tài)的ID。
下面定義的是FSMclass，這個類用于維護FSMstate對象集合。
class FSMclass
{
State_Map m_map; //包括了狀態(tài)機的所有狀態(tài)
int m_iCurrentState; //當前狀態(tài)的ID
public:
FSMclass(int iStateID); //初始化狀態(tài)
~FSMclass()
//返回當前狀態(tài)ID
int GetCurrentState() {return m_iCurrentState;}
//設置當前狀態(tài)ID
void SetCurrentState(int iStateID) {m_iCurrentState=iStateID;}
//返回FSMstate對象指針
FSMstate* GetState(int iStateID);
//增加狀態(tài)對象指針
void AddState(FSMstate* pState);
//刪除狀態(tài)對象指針
void DeleteState(int iStateID);
//根據(jù)“當前狀態(tài)”和“輸入”完成“狀態(tài)”的轉(zhuǎn)換。
int StateTransition(int iInput);
};
FSMclass::m_map是FSMstate對象的集合，是從STL<map>中實現(xiàn)的。
FSMclass::m_iCurrentState是FSMstate對象的狀態(tài)標識，是“有限狀態(tài)機”的當前狀態(tài)。
FSMclass::GetCurrentState()可以用之訪問當前的FSMstate對象的狀態(tài)的標識符。
FSMclass::SetCurrentState()可以設置當前FSMstate對象的狀態(tài)的標識符。
FSMclass::GetState()可以取得有限狀態(tài)機中的任何FSMstate對象的指針。
FSMclass::AddState()增加有限狀態(tài)機中的FSMstate對象。
FSMclass::DeleteState()刪除有限狀態(tài)機中的FSMstate對象
FSMclass::StateTransition()初始化狀態(tài)轉(zhuǎn)換，根據(jù)輸入返回輸出狀態(tài)。
這個類使用了STL，我不知道它怎么用：）。聽說是高人才使用它，高人起碼要寫過上萬行的代碼。因此不能詳細介紹這個類了
總之，可以這么理解這兩個類FSMstate,FSMclass.FSMstate代表了一個狀態(tài)以及和狀態(tài)相關的數(shù)據(jù)和操作。如在MONSTER中有五個狀態(tài)，我們就要聲明五個類的對象，每個對象中包括了與這個狀態(tài)相關的狀態(tài)，輸入和各種轉(zhuǎn)換函數(shù)。可以說FSMstate是對每一個狀態(tài)的封裝（包括相關數(shù)據(jù)和操作），游戲中的對象有多少狀態(tài)，就要聲明多少個FSMstate對象。而FSMclass則是對這若干個FSMstate對象（這個例子中MONSTER有五個狀態(tài)）進行的封裝。在FSMclass中指明了若干個FSMstate中哪一個是當前的MONSTER擁有的狀態(tài)并且可以設置，得到以及刪除狀態(tài)，并且可以進行狀態(tài)間的轉(zhuǎn)換。
總之：游戲中的MONSTER有多少狀態(tài)，游戲中就要聲明多少的FSMstate對象，每一個FSMstate對象包括了與特定的狀態(tài)相關的數(shù)據(jù)和操作。而FSMclass只有一個，它用于協(xié)調(diào)若干個FSMstate之間的關系和操作。
下面是如何在游戲中使用兩個類的例子：
首先是創(chuàng)建FSMstate對象（若干個），有多少狀態(tài)就要循環(huán)多少次，下面是增加STATE_ID_UNCARING狀態(tài)的例子：
FSMstate* pFSMstate=NULL;
//創(chuàng)建狀態(tài)
try
{
//第一個參數(shù)是增加狀態(tài)的標識，第二個參數(shù)指明了與這個
//狀態(tài)相關的狀態(tài)的個數(shù)。
pFSMstate=new FSMstate(STATE_ID_UNCARING,2);
}
catch(...)
{
throw;
}
//之后給這個狀態(tài)加入相關的“輸入”和“輸出狀態(tài)”
pFSMstate->AddTransition(INPUT_ID_PLAYER_SEEN,STATE_ID_ANNOYED);
pFSMstate->AddTransition(INPUT_ID_PLAYER_ATTACKS,STATE_ID_MAD);
這個函數(shù)指明了與特定狀態(tài)相關的“輸入”和“輸出狀態(tài)”
比如第一個函數(shù)，它表明如果我要輸入一個INPUT_ID_PLAYER_SEEN，這時就會產(chǎn)生一個輸出狀態(tài)，STATE_ID_ANNOYED。
我們應該為每一個狀態(tài)做上面的事情，這里就略過了。之后我們要聲明一個FSMclass對象，用于協(xié)調(diào)上面的FSMstate對象之間的關系。
try
{
m_pFSMclass=new FSMclass(STATE_ID_UNCARING);
}
catch(...)
{
throw;
}
上面指明了MONSTER的當前狀態(tài)是STATE_ID_UNCARING最后將FSMstate對象分別加入到FSMclass中。
下面介紹如何使用FSMclass
使用十分簡單，只要我們給出一個“輸入”，之后，我們便可以得到一個“輸出狀態(tài)”，根據(jù)這個“輸出狀態(tài)”我們執(zhí)行相應的操作，最后，把這個“輸出狀態(tài)”變成MONSTER的當前狀態(tài)。
在游戲中發(fā)生了一些事情，如玩游戲的人指出他控制的人進攻MONSTER（用鼠標點擊了MONSTER），這時會產(chǎn)生一個“輸入”iInputID=INPUT_ID_PLAYER_ATTACK;
這時，我們調(diào)用狀態(tài)轉(zhuǎn)換函數(shù)：
m_iOutputState=m_pFSMclass->StateTransition(iInputID);
這時，我們的“輸入”對MONSTER產(chǎn)生了刺激，產(chǎn)生了一個“輸出狀態(tài)”。這時我們根據(jù)這個輸出狀態(tài)調(diào)用相應的代碼執(zhí)行就可以了，這時的MONSTER好像有應反了，我們說它有了簡單的智能。
if(m_iOutputState==STATE_ID_MAD)
{
//some code for the monster to act mad
}
當然，我們也應該把其它狀態(tài)執(zhí)行的操作也寫出來，但只寫一個就可以了。使用這個狀態(tài)機就是這么簡單。總之，FSMclass不是全部的人工智能，相反，它只是一個框架，一個開始智能需要的還很多。只要你可以分出“狀態(tài)”，并且知道什么“輸入”產(chǎn)生什么“輸出狀態(tài)”就可以了，當然這是一個游戲的規(guī)則，策劃應當完成這個部分？