0x00 前言

因為臨近年關工作繁忙，已經(jīng)有一段時間沒有更新博客了。到了元旦終于有時間來寫點東西，既是積累也是分享。如題目所示，本文要來聊一聊在游戲開發(fā)中經(jīng)常會涉及到的話題——游戲AI。設計游戲AI的目標之一是要找到一種便于使用并容易拓展的的方案，常見的一些游戲AI方案包括了有限狀態(tài)機(FSM)、分層有限狀態(tài)機（HFSM）、面向目標的動作規(guī)劃（GOAP）以及分層任務網(wǎng)絡（HTN）和行為樹（BT）等等。下面我們就來聊一聊比較有代表性的游戲AI方案——狀態(tài)機。

0x01 有限狀態(tài)機(FSM)

有限狀態(tài)自動機 (Finite State Machine，F(xiàn)SM)是表示有限多個狀態(tài)以及在這些狀態(tài)（State）之間轉(zhuǎn)移（Transition）和動作（Action）的數(shù)學模型。有限狀態(tài)機的模型體現(xiàn)了兩點：

1. 狀態(tài)首先是離散的：某一時刻只能處于某種狀態(tài)之下，且需要滿足某種條件才能從一種狀態(tài)轉(zhuǎn)移到另一種狀態(tài)。
2. 然后狀態(tài)總數(shù)是有限的。
   

從它的定義，我們可以看到有限狀態(tài)機的幾個重要概念：

• 狀態(tài)（State）：表示對象的某種形態(tài)，在當前形態(tài)下可能會擁有不同的行為和屬性。
• 轉(zhuǎn)移（Transition）：表示狀態(tài)變更，并且必須滿足確使轉(zhuǎn)移發(fā)生的條件來執(zhí)行。
• 動作（Action）：表示在給定時刻要進行的活動。
• 事件（Event）：事件通常會引起狀態(tài)的變遷，促使狀態(tài)機從一種狀態(tài)切換到另一種狀態(tài)。

而狀態(tài)機便是用來控制對象狀態(tài)的管理器。在滿足了某種條件或者說在某個特定的事件被觸發(fā)之后，對象的狀態(tài)便會通過轉(zhuǎn)換來變成另外一種狀態(tài)，而對象在不同的狀態(tài)之下也有可能會有不同的行為和屬性。
當然，有限狀態(tài)機的應用范圍很廣，但是顯然游戲開發(fā)是有限狀態(tài)機最為成功的應用領域之一。除了游戲AI的實現(xiàn)可以依靠有限狀態(tài)機之外，游戲邏輯以及動作切換都可以借助有限狀態(tài)機來實現(xiàn)。因此游戲中的每個角色或者器件或者邏輯都有可能內(nèi)嵌一個狀態(tài)機。

0x02 HFSM分層有限狀態(tài)機

如果我們仔細觀察一個有限狀態(tài)機的話，可以發(fā)現(xiàn)它在邏輯結(jié)構(gòu)上是沒有層次的，如果和行為樹來做對比的話可以發(fā)現(xiàn)這一點十分明顯。在行為樹中，節(jié)點是有層次（Hierarchical）的，子節(jié)點由其父節(jié)點來控制。例如行為樹中有一種節(jié)點叫做“序列（Sequence）節(jié)點”，它的作用是順序執(zhí)行所有子節(jié)點（如果某個子節(jié)點失敗返回失敗，否則返回成功）。而將行為樹的這個優(yōu)勢應用到有限狀態(tài)機上，分層有限狀態(tài)機HFSM便誕生了。

分層的好處

那么引入了分層之后的HFSM到底帶來了什么好處呢？
最大的好處便是在一定程度上規(guī)范了狀態(tài)機的狀態(tài)轉(zhuǎn)換，從而有效地減少了狀態(tài)之間的轉(zhuǎn)換。
舉一個簡單的小例子：例如RTS游戲中的士兵。如果邏輯沒有層次上的劃分，那么我們對士兵所定義的若干狀態(tài)，例如前進、尋敵、攻擊、防御、逃跑等等，就需要在這些狀態(tài)之間定義轉(zhuǎn)移，因為它們是平級的，因此我們需要考慮每一組狀態(tài)的關系，并維護一大堆沒有側(cè)重點的轉(zhuǎn)移。
如果在邏輯上是分層的，我們就可以將士兵的這些狀態(tài)進行一個分類，把幾個低級的狀態(tài)歸并到一個高級的狀態(tài)中，并且狀態(tài)的轉(zhuǎn)移只發(fā)生在同級的狀態(tài)中。
例如高級狀態(tài)包括戰(zhàn)斗、撤退，而戰(zhàn)斗狀態(tài)中又包括了尋敵、攻擊等幾個小狀態(tài)；撤退狀態(tài)中又包括了防御、逃跑這幾個小狀態(tài)。

總而言之，分層狀態(tài)機HFSM從某種程度上規(guī)范了狀態(tài)機的狀態(tài)轉(zhuǎn)移，而且狀態(tài)內(nèi)的子狀態(tài)不需要關心外部狀態(tài)的跳轉(zhuǎn)，這樣也做到了無關狀態(tài)間的隔離。

0x03 有限狀態(tài)機的實現(xiàn)

那么到底如何實現(xiàn)一個有限狀態(tài)機呢？主要有兩種方式來實現(xiàn)，即集中管理控制以及模塊化管理。具體來說，這兩種方式的實現(xiàn)如下：

1. 使用switch語句：所有的狀態(tài)之間的轉(zhuǎn)移邏輯全都寫在一個部分，需要根據(jù)不同的分支來判斷轉(zhuǎn)移條件是否符合。
2. 使用狀態(tài)模式（State Pattern）：一種常見的設計模式。在狀態(tài)模式中，我們?yōu)槊總€狀態(tài)創(chuàng)建與之對應的類，這樣就將狀態(tài)轉(zhuǎn)移的邏輯從臃腫的switch語句中分散到了各個類中。

了解了有限狀態(tài)機大體上可以分為這兩種實現(xiàn)方式，那么接下來我們就具體來看一看這兩種方式是如何實現(xiàn)的。

switch語句

在實現(xiàn)有限狀態(tài)機時，使用switch語句是最簡單同時也是最直接的一種方式。這種方式的基本思路是為狀態(tài)機中的每一種狀態(tài)都設置一個case分支，專門用來對該狀態(tài)進行控制。

上圖是一個具體的使用有限狀態(tài)機實現(xiàn)游戲AI的場景，描述的是一個游戲單位的AI，下面我們就使用switch語句來實現(xiàn)圖中的狀態(tài)機。

switch (state)  {  // 處理狀態(tài)Waiting的分支  case State.Waiting:     // 執(zhí)行等待    wait();    // 檢查是否有可以攻擊    if (canAttack()){      // 當前狀態(tài)轉(zhuǎn)換為Attacking      changeState(State.Attacking);    }    // 若不可攻擊，則檢查是否有可以移動    else if (canMove()) {       // 當前狀態(tài)轉(zhuǎn)換為Moving      changeState(State.Moving)    }    break;  // 處理狀態(tài)Moving的分支  case State.Moving:     // 執(zhí)行動作move    move();    // 檢查是否可以攻擊敵人    if (canAttack()) {      // 當前狀態(tài)轉(zhuǎn)換為Attacking      changeState(State.Attacking);    }    // 若不可攻擊，則檢查是否可以等待    else if (canWait()) {      // 當前狀態(tài)轉(zhuǎn)換為Waiting      changeState(State.Waiting);    }    break;  // 處理狀態(tài)Attacking的分支  case State.Attacking:     // 執(zhí)行攻擊attack    attack();    // 檢查是否可以等待    if (canWait()) {      // 當前狀態(tài)轉(zhuǎn)換為Waiting      changeState(State.Waiting);    }    break;}

通過這個小例子，我們可以看到使用switch語句實現(xiàn)的有限狀態(tài)機的確可以很好的運行。不過我們還可以發(fā)現(xiàn)這種方式在實現(xiàn)狀態(tài)之間的轉(zhuǎn)換時，1.檢查轉(zhuǎn)換條件以及2.進行狀態(tài)轉(zhuǎn)換的代碼都是混雜在當前的狀態(tài)分支中來完成的，這樣就會導致代碼的可讀性降低甚至會增加日后的維護成本。
這是因為在每個具體的狀態(tài)下，都需要檢查多個具體的轉(zhuǎn)換條件，對符合條件的還需要轉(zhuǎn)移到新的具體的狀態(tài)，這樣的代碼是難以維護的，因為它們需要在具體的情況下處理具體的事物。即便我們將檢查轉(zhuǎn)換條件和進行狀態(tài)轉(zhuǎn)換的代碼分別封裝成兩個專門的函數(shù)FuncA（檢查轉(zhuǎn)換條件）和FuncB（進行狀態(tài)轉(zhuǎn)換），switch語句中各個具體狀態(tài)的代碼可能會更加清晰。但是隨著邏輯復雜度的增加，F(xiàn)uncA和FuncB這兩個函數(shù)本身的復雜度可能也會增加，甚至最后變得臃腫不堪。

狀態(tài)模式

當控制一個對象狀態(tài)轉(zhuǎn)換的條件表達式過于復雜時，把狀態(tài)的判斷邏輯轉(zhuǎn)移到一系列類當中，可以把復雜的邏輯判斷簡單化。因此，使用狀態(tài)模式來實現(xiàn)狀態(tài)機雖然不如直接使用switch語句來的直接，但是對于狀態(tài)更易維護也更易拓展。下面我們就來看一看狀態(tài)模式中的角色：

　　1. 上下文環(huán)境（Context）：它定義了客戶程序需要的接口并維護一個具體狀態(tài)的實例，將與狀態(tài)相關的操作（1.檢查轉(zhuǎn)換條件；2.進行狀態(tài)轉(zhuǎn)換）交給當前的具體狀態(tài)對象來處理。
　　2. 抽象狀態(tài)（State）：定義一個接口以封裝使用上下文環(huán)境的的一個特定狀態(tài)相關的行為。
　　3. 具體狀態(tài)（Concrete State）：實現(xiàn)抽象狀態(tài)定義的接口。
下面，我們就按照這三個角色來實現(xiàn)上一小節(jié)圖中的狀態(tài)機吧。
context類：

public class Context{    PRivate State state;    public Context(State state)    {        this.state = state;    }    public void Do()    {        state.CheckAndTran(this);    }}

抽象狀態(tài)類：

public abstract class State{    public abstract void CheckAndTran(Context context);}

具體狀態(tài)類

public class WaitingState : State{    public override void CheckAndTran(Context context)    {        //執(zhí)行等待動作        Wait();        //檢查是否可以攻擊敵人        if (canAttack()){            // 當前狀態(tài)轉(zhuǎn)換為Attacking            context.State = new AttackingState();        }        // 若不可攻擊，則檢查是否有可以移動        else if (canMove()) {             // 當前狀態(tài)轉(zhuǎn)換為Moving            context.State = new MovingState();        }    }}...

雖然看似狀態(tài)模式緩解了使用switch語句那種代碼臃腫、可讀性維護性差的問題，但是狀態(tài)模式并非沒有自己的缺點。可以看出狀態(tài)模式的使用必然會增加類和對象的個數(shù)，如果使用不當將導致程序結(jié)構(gòu)和代碼的混亂。

0x04 褒揚和批判

在游戲開發(fā)中使用狀態(tài)機顯然不失為一種不錯的選擇，首先它的概念并不復雜，其次它的實現(xiàn)也十分簡單而直接。但它的缺點卻也十分明顯，例如難以復用，因為它往往需要根據(jù)具體的情況來做出反應，當然當狀態(tài)機的模型復雜到一定的程度之后，也會帶來實現(xiàn)和維護上的困難。如何選擇，可能就是一個仁者見仁智者見智的問題了。