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