Strategy & State:條件判斷式的消除者

strategy-pattern
Strategy Pattern

身為一位程式設計者,你是否曾面臨條件判斷式繁殖過盛的困擾?經常用折疊不完的 N 層 if-else 結構來考驗自己的腦力?或是只能瞪著超過 500 行的 switch-case 條件判斷式舉手投降?您的困擾我瞭解,請容許我向您引薦本篇文章的雙主打星——Strategy 與 State 範式,讓它們帶領我們一同邁向美妙動人的範式之道吧!

首先要瞭解的是,為什麼要將 Strategy 與 State 範式放在同一篇文章裡介紹?因為兩者雖然在設計層面的動機與出發點有所差異,但是在實際的應用面中非常地相近。根據《物件導向設計模式》(Design Patterns) 書中的定義,只要將右圖中的 Strategy、ConcreteStrategyA 與 ConcreteStrategyB 角色,更改為 State、ConcreteStateA 與 ConcreteStateB,就會變成 State 範式的結構圖,可以說兩者就像是孿生兄弟般密切相關。

如果真的要區分出 Strategy 與 State 範式之間的差異,可以參考《重構——向範式前進》中論述的內容:

State pattern 對「必須在一整族 state classes 的實體之間輕鬆轉換」的 class 有益,而 Strategy pattern 則是有助於讓 class 把演算法執行任務委託給「一整族 Strategy classes 的某一個實體」。

從我理解的角度來解釋,Strategy 範式比較著重於包裝相同派系的演算法,而 State 範式則特別注重在各狀態之間的轉換邏輯。所以只要瞭解 Strategy 或 State 範式兩者之一,就等於學會了兩種設計模式,真的是太划算太值得啦!雖然 Strategy 與 State 範式非常單純而且易於理解,但這兩項看似不起眼的小小範式,卻經常能夠在程式系統中發揮很好的應用效果,絕對是程式設計者不可不學的必備基礎知識。本文中將以 Strategy 範式為主,說明兩者在遊戲系統中的相關應用。

如上面的 UML 結構圖所示,Strategy 範式由三種角色的交互作用而生:

  • Strategy:制訂出一組共通的介面,使 Context 能夠透過此介面呼叫由 ConcreteStrategy 所實做的演算法。
  • ConcreteStrategy:根據 Strategy 所制訂的介面,具體實做出合適的演算法。
  • Context:Strategy 的操作者,另可定義介面以供 Strategy 存取自己的資料。

讓我們直接來看看,單純的條件判斷式在遊戲系統中產生的問題,以及 Strategy 範式如何解決問題。

在遊戲系統的程式碼中,特別是與遊戲邏輯相關的部分,經常會面臨需依照各項條件要素,切換不同控制邏輯的情況。以一般的遊戲主迴圈流程為例,多半由偵測鍵盤滑鼠等輸入裝置、更新遊戲世界,以及繪製遊戲世界三項程序組成:

while (m_GameIsRunning) {	
	// 處理輸入裝置訊息
	ProcessInput();
	// 更新遊戲邏輯
	Update();
	// 繪製遊戲世界
	Render();
}

但是對於一個完整的遊戲來說,光是區分為上述這三項處理程序,無法完整滿足遊戲中的各種設計需求以及狀態轉換。例如,在剛啟動遊戲時、進入遊戲主選單時,以及遊戲運行中時,可能就會需要三種完全不同的偵測、更新與繪製程序,所以在此可以宣告一些列舉值,用來區分各種遊戲狀態,接著再以 if-else 條件判斷句在處理程序中分項處理:

enum GameState
{
	GameState_Init,
	GameState_Menu,
	GameState_InGame,
};

void ProcessInput()
{
	if (m_State == GameState_Init) {
		// 處理剛啟動遊戲時的輸入偵測邏輯
	}
	else if (m_State == GameState_Menu) {
		// 處理進入遊戲主選單時的輸入偵測邏輯
	}
	else if (m_State == GameState_InGame) {
		// 處理遊戲運行時的輸入偵測邏輯
	}
}

除了 ProcessInput() 函式以外,Update() 與 Render() 函式也以同樣的方法區分成不同的流程控制邏輯。如此一來,只要我們在程式執行的過程中改變 m_State 的數值,當遊戲主迴圈下次進入這三項程序時,自然就會切換至不同的處理流程中了。這樣的程式邏輯看起來完全無害,不是嗎?

但實際上,使用 if-else 敘述句的作法不夠直覺化,有另外一位控制結構的候選者更合適於擔綱這項任務。只要是熟習程式語言基本語法的讀者,應該不難想到可以將上面的 if-else 敘述句,轉換成另外一種作用相同的 switch-case 敘述句:

void ProcessInput()
{
	switch (m_State)	{
		case GameState_Init: {
			// 處理剛啟動遊戲時的輸入偵測邏輯
			break;
		}
		case GameState_Menu: {
			// 處理進入遊戲主選單時的輸入偵測邏輯
			break;
		}
		case GameState_InGame: {
			// 處理遊戲運行時的輸入偵測邏輯
			break;
		}
	}
}

相較於 if-else 敘述句,使用 switch-case 敘述句的優點,在於每個分支選項都會擁有同等的重要性。所以對於程式設計者來說,只要一見到 switch-case,首先就會聚焦在控制變數 m_State 的身上,並且直覺化地理解其中的各項 case 程序,都是具有同等重要性的程式碼。而也正因為 switch-case 比較符合程式設計者的直覺觀感,所以在遊戲系統的程式碼中,switch-case 敘述句也是最常被濫用與誤用的條件判斷式

當遊戲專案剛啟始,同時整個程式系統仍處於萌芽階段時,使用前述 switch-case 的方法並不會產生任何問題。然而,隨著與日俱增的專案進度與設計需求,程式系統也會無可避免地越來越加錯綜複雜。可能一開始時,程式設計者只是單純想使用一個最簡單明快的方法,以解決切換控制邏輯的需求;然而,隨之而來的程式碼增修幅度,總是遠遠超過原先的預期程度。即使只是偶爾增加個十幾行程式碼,到了專案中後期時,卻有可能使一個小小的 switch-case 敘述句膨脹至 500 行以上的巨型怪物。

為了避免 switch-case 毫無節制地接受程式設計者的餵食,最終成為體態臃腫的大傢伙,我們立即可想到的一項改善方式,就是把原來散落在 case 敘述句中的程式碼,依照功能分門別類,包裝成一個個的中小型函式:

void Update()
{
	switch (m_State)
	{
		case GameState_Init:
		{
			UpdateNetwork();
			UpdateGameWorld();
			UpdatePhysicsEngine();
			UpdateAudioEngine();
			UpdateGraphicsEngine();
			break;
		}
		case GameState_Menu:
		{
			break;
		}
		case GameState_InGame:
		{
			break;
		}	
	}
}

有些奉「效能」兩字為最高指導原則的程式設計者,可能會因為遊戲執行效能上的疑慮,而不願意將原來的程式碼包裝成一個個的小型函式。但事實上,這不僅是沒有必要的顧慮,也是一種「過早進行最佳化」的錯誤觀念。在最低限度的情況下,甚至只需要妥善利用 inline 方式來宣告函式,就能夠大幅降低函式呼叫的成本了。

雖然將 case 敘述句中的程式碼分裝處理是個好的開始,但是仍然沒有解決根本上的條件判斷式過多的問題,而且使用 switch-case 敘述句,就像是中了流行性感冒病毒一樣,會不斷地在整個程式系統中傳染擴散開來,讓程式設計者越來越難以擺脫。以上述的幾個分裝函式為例,除了在原有的 Update() 函式中判斷不同的運作條件之外,UpdateNetwork() 是不是同樣也需要進行判斷?還有 UpdateGameWorld()、UpdatePhysicsEngine() 和 UpdateGraphicsEngine() 函式呢?應該也免不了需要切換不同的控制流程吧!

所以,分裝函式最終經常會長出像這樣的程式碼:

void UpdateNetwork()
{
	switch (m_State) {
		case GameState_Init: {
			break;
		}
		case GameState_Menu: {
			break;
		}
		case GameState_InGame: {
			break;
		}	
	}
}

void UpdateGameWorld()
{
	switch (m_State)	{
		case GameState_Init: {
			break;
		}
		case GameState_Menu: {
			break;
		}
		case GameState_InGame: {
			break;
		}	
	}
}

還有 UpdatePhysicsEngine()、UpdateGraphicsEngine()、UpdateAudioEngine() 和 UpdateOOXX() 等等,到處都是 switch-case 敘述句,想躲也躲不了!

而除了近乎無性繁殖的 switch-case 程式碼以外,更令人頭痛的是,當程式設計者需要加入一項全新的遊戲狀態,例如 GameState_Pause 來控制遊戲暫停時的邏輯運作時,我們必須得回過頭來,前往每一個與 m_State 變數相關的 switch-case 敘述句中,加上一則新的 case 敘述句使 GameState_Pause 狀態能夠正確運作。或許你會認為:「用 Copy-Paste 的方式很快就可以完成,不是嗎?」但是人為干預的動作越多,也就代表疏忽犯錯的可能性越高。

清楚瞭解濫用 if-else 與 switch-case 的種種問題之後,就輪到本篇的英雄主角上場,拯救我們程式設計者的世界啦!為了能夠妥善管理各種不同遊戲狀態之間的運作邏輯,首先可以利用純虛擬函式,宣告一個無法直接具現化的抽象類別 GameState,來扮演最前面所提到的 Strategy 角色:

class GameState
{
public:
	virtual void Update() = 0;
	virtual void Render() = 0;
	virtual void ProcessInput() = 0;
};

將 GameState 宣告為抽象類別,優點在於強制使用者必須自行定義子類別的實做細節,藉此可避免對於 GameState 類別的誤用情形。接著,就可以依照遊戲系統的需求,自 GameState 衍生出一個個獨特的 ConcreteStrategy 角色:

class GameInitState : public GameState
{
public:
	virtual void Update() {
		// 處理剛進入遊戲時的更新程序
	}
	
	virtual void Render() {
		// 處理剛進入遊戲時的繪製程序
	}
	
	virtual void ProcessInput() {
		// 處理剛進入遊戲時的輸入偵測程序
	}
};

class GameMenuState : public GameState
{
public:
	virtual void Update() {
		// 處理遊戲主選單的更新程序
	}
	
	virtual void Render() {
		// 處理遊戲主選單的繪製程序
	}
	
	virtual void ProcessInput() {
		// 處理遊戲主選單的輸入偵測程序
	}
};

依此方式製作出 GameInitState、GameMenuState 與 GameInGameState 類別後,就可以快樂地和 switch-case 說再見囉!原來的 ProcessInput()、Update() 與 Render() 三項程序就可以修改為:

void ProcessInput()
{
	m_CurrentState->ProcessInput();
}

void Update()
{
	m_CurrentState->Update();
}

void Render()
{
	m_CurrentState->Render();
}

是的,你沒看錯!就這麼容易!先前由一個 m_State 變數以及 switch-case 敘述句控制的條件判斷式,轉換成僅需要一個 m_CurrentState 物件進行操控的程式碼邏輯。程式設計者只需要依條件更換 m_CurrentState 所指向的 ConcreteStrategy 物件,就能夠輕鬆地享受後續的免費服務而無須費心。所以只要我們能夠善加利用 C++ 語言的「虛擬」與「多型」特性,就能夠為程式設計者節省下許多非常珍貴的腦容量與腦細胞,使用在其他更有意義的難題上。

而 Strategy 與 State 範式,不僅能夠用在遊戲主迴圈的流程控制程序中,更可以運用在人工智慧等許多不同的系統中。像遊戲系統中常見的角色狀態機制,同樣也可以利用 State 範式的方式來實作。首先定義好基礎的 State 類別之後,就可以進一步衍生出 IdleState、MoveState、CombatState 等等不同用途的狀態類別:

class Character;

class State
{
public:
	State(Character* context);
};

class IdleState : public State
{
public:
	IdleState(Character* context);
};

class MoveState : public State
{
public:
	MoveState(Character* context);
};

class CombatState : public State
{
public:
	CombatState(Character* context);
};

「萬里長城萬里長~」如同萬里長城般綿延不絕而且橫跨數個頁面的 if-else 或 switch-case 敘述句,絕對是任何一位程式設計者最不願意見到的程式碼結構之一。當你爽快地揮舞著 if-else 與 switch-case 連段 Combo 招式時,請先暫停片刻,冷靜下來想想這樣的做法是否合適?是否有其他方法可以簡化條件判斷式?

另外,如果你習慣於撰寫動輒六、七層以上的條件判斷式深度,不但是在考驗自己的邏輯思考空間,同時也是在殘害程式碼的閱讀者與維護者——而很有可能你自己就是那位可憐的閱讀者與維護者。為了避免寫出深達地底三萬呎的迷宮結構,我們可以多加利用 return、break 敘述句,或者判斷反向的 boolean 值,以減少條件判斷式的巢狀深度。

平時要如何自我檢查是否已經中了條件判斷式的流行性感冒?通常當你發現自己反覆用著 Copy-Paste 在程式碼檔案之間,處理某些「大部分相同而小部分相異」的程式碼時,很可能就是一種濫用條件判斷式的徵兆。請記得,早期發現早期治療的效果最好,否則當程式碼日益增長茁壯,重構的痛苦也會越來越厚重。當你發現自己在兩個地方以上寫著相同的條件判斷式時,可能就是就是 Strategy 與 State 範式該出馬的時候了!

體認完 Strategy 與 State 如何拯救世界之後,最後也該瞭解它們可能產生的副作用。若從效能層面考量,比起單純的 switch-case 敘述句,使用 Strategy 或 State 範式需要一次額外的 virtual table 提領步驟,多少會造成某種程度的效能衝擊。然而,就像之前所提到的「不要過早進行最佳化」,程式設計者應該先以 80/20 法則確認系統的效能瓶頸所在,然後再開始動手改善,才能獲得最佳的優化效益。另外要注意的是,Strategy 與 State 範式並不是任何狀況都適用的銀子彈,如果用在錯誤的地方,將會產生過多小型的物件類別,反而可能降低類別階層的耦合性與內聚力。

只要善加利用 Strategy 與 State 範式,就可以大幅簡化遊戲系統的運作邏輯,使程式碼更加易於閱讀與維護,同時也會變成一種無須太多註解與文件說明,就能夠在程式設計者間達到良好成效的溝通方式。以後再見到 switch-case 敘述句或是準備下手使用之前,不妨先仔細分析一下,想想是否能夠使用 Strategy 或者 State 範式取而代之吧!這樣可以讓你自己也讓其他人過得更快樂唷~

延伸閱讀

  • 《重構——改善既有程式的設計》:
    〈8.15〉以 State/Strategy 取代型別代碼
  • 《重構——向範式前進》:
    〈7.2〉以 Strategy 替代條件邏輯
    〈7.4〉以 State 替代「狀態變換」條件句

16 Replies to “Strategy & State:條件判斷式的消除者”

  1. 個人認為以pattern的精神、目的和使用時機來比較會比以UML的結構相似度比較來得好,誤用design pattern比不用更糟糕!

  2. 寫的不錯耶
    在遊戲界知道 Design Pattern跟Refactory理論的人不多

    對我來說Command Pattern某些”角度”上也蠻像的
    比如很多的遊戲在接收網路封包 跟接收UI event的程式都有巨大的switch case
    這時候可以”考慮” Command Pattern

    誤不誤用有時候很難講
    <>(這本書太重要了)多看一點
    就不會被拘限方法論中
    系統架構本來就會隨著時間改變而變化
    覺得應該用就用 用了覺得會有壞味道就在refactory回來

    想起這幾年都在維護之前前輩寫的系統
    到處都是五六千行的switch + if else
    要馬就是上萬行的class 真是痛苦死了…..

  3. 半路大提到的這兩個pattern應該算是寫遊戲程式常用必備的良方吧XD
    市面上講design pattern的書比較少有以遊戲為案例的, 有時看完design pattern的書還不曉得可以用在哪說:)

    感謝分享~

  4. State基本上確實是遊戲必備

    我個人比較常用的是Observer Pattern,大概是中學時受Starcraft的影響比較大(SC的地圖編輯器裏面那些Trigger,現在想來應該就是一大堆的Observer吧)

    虛函數讀取vtable的那點功夫,和函數内部一般要處理的東西相比之下幾乎不值一提,所以用一點點效率換取更高的可維護性又何嘗不可?

    PS: The Art of Game Design確實是一本好書,推薦入手

  5. 突然想到用c一样可以避免条件判断,用函数指针的数组。
    #define STATE_INIT 0
    #define STATE_INGAME 1
    #define STATE_END 2

    typedef int (*loopfunc) (double);

    int g_state = 0;

    int state_init (double dtime) {}
    int state_ingame (double dtime) {}
    int state_end (double dtime) {}

    loopfunc g_statepool[] = {state_init, state_ingame, state_end};

    int gameloop (double dtime)
    {
    g_statepool[g_state] (dtime);
    }

  6. 有時候 switch 還是需要的, 因為殺雞不需用牛刀.
    有時間可以看看 Ogre3D 的 OO, 寫的非常的漂亮.

  7. 我的習慣是先畫出use case,再決定是否要用Design Pattern。

    殺雞用牛刀只是浪費開發成本;當牛刀一出便殺個片甲不流。

  8. @Michael:
    的確,UML 的結構圖只是個參考指引而已。不要只是照圖硬套,結果反而曲解了範式存在與應用的本意。

    @Rich:
    之前我也有使用過以 Command 範式實作出來的網路協定機制,真的能夠省下很多不必要的 switch-case 程式碼累贅,也可以讓剛接觸網路系統的程式設計者,更容易理解系統的整體流程與架構。五、六千行的 switch-case + if-else……真是太要命啦~ 囧rz

    在 < 和 > 之間的字被吃掉了,我猜你應該是想指《重構——改善既有程式的設計》這本書吧? XD

    @jbyu:
    Strategy 和 State 範式,也可以和 Factory Method 範式一起混搭使用,效果會更好!

    謝謝你的文章~

    @zii:
    如果沒有虛擬函式存在,C++ 語言就等同於廢掉了一半武功。所以即使需要付出一些代價,我們還是得瞭解怎麼合理運用虛擬與多型機制才行哪。

    @gino:
    對於已經用習慣的人來說,會覺得使用 Strategy 和 State 範式是很自然的事情。可是對其他比較不熟悉設計模式的人來說,常常不能理解為什麼我們要這樣做啊。 XD

    @Wxy:
    在遊戲的程式系統中,Observer 也是個超級實用的好傢伙!(是不是該介紹它出場哩?)

    我也同意幾乎可以不用操心存取 vtable 的花費這樣的看法,但我發現對於很多從 ASM 與 C 語言時代走來的人而言,很難說服他們接受「以微小效能影響換取大幅程式碼可讀性」的觀念。

    我在上個週末已經買了《The Art of Game Design》。目前找不到合適的詞彙來形容內心的激動與衝擊,正在享受沈浸於這本書中的樂趣,Having new eyes!

    @zii:
    沒錯!你所提出的函式指標作法,就是從前在 C 語言的環境下經常會使用的一種技巧。然而函式指標有個小缺陷,在於它無法保證提供型別安全的約束力。所以在 C# 以及其他比較新穎的程式語言中,就會提供像是 delegate 這類程式語法,以進一步改善函式指標的問題。

    @路人甲:
    是的,這篇文章所要傳達的訊息,並不是要叫大家把所有的 switch-case 敘述句都換成 Strategy 範式,只是想提醒我們自己,在工具箱裡除了殺雞小刀可以使用之外,別忘了還有青龍偃月刀可以幫助我們。

    我有稍微涉獵過 OGRE 引擎的設計模式,也很喜歡它在許多面向中的架構設計,詳細內容請見這篇文章

    @vamper:
    先畫出 Use Case 是個好習慣~ 如果在撰寫程式碼之前,每次都能先從 User 端的角度出發設想,那麼要選擇哪一把工具就會不是太困難的問題了。

    非常感謝以上各位的寶貴意見與迴響。 :)

  9. @zii: 函數指標除了猴子大提到的型別安全問題 最大的不同就是 Strategy或是State是物件(如果是”Interface”那更好)…物件能提供無限的可能性壓(可以包裝任何資料 可以透過繼承介面實做的方式讓無限其他種類的物件都可以為成為State或Strategy)

  10. @Rich:
    沒錯沒錯,比起功用單純的函式,物件擁有非常大的彈性,而這也是使用函式指標與 Strategy/State 範式最大的差異點。

    謝謝你幫忙補充,我是半路不是猴子大~ XD

  11. 這麼作的確能解決 ProcessInput() 等函式內部大量條件判斷式的缺點。不過個人想了一下,應該還是有一個類似條件判斷式的程式,來決定現在餵給 ProcessInput() 等函式進行判斷的 m_CurrentState 是屬於哪種 class 的衍生物吧?比如

    //遊戲開始時
    m_CurrentState = StateFactory::create(StateFactory::GameInitState);

    //遊戲主選單
    m_CurrentState = StateFactory::create(StateFactory::GameMenuState);

    個人猜想這個判斷應該是無法避免的?

  12. @snowmantw:
    可以運用 std::map 結構的查表法來做。即使是在創建物件時,也同樣能夠免除條件判斷式喔~

  13. 關於 snowmantw 的問題,我覺得是不用使用 Factory 的。如果把一個State當作一個普通變數,你也必定要給它一個初始值,之後在 State transition 的時候改變它的值。

    void Game::SetCurrentState(State *state) {
    delete mCurrentState;
    mCurrentState = state;
    }

    //遊戲開始時
    game.SetCurrentState(new GameInitState(/**/));

    如果所有 State 的洐生類別都是 Stateless 的,更可以使用 Singleton,而不需要每次 new/delete:

    game.SetCurrentState(GameInitState::Instance());

    除非你希望用一個 enum 把各個 state classes 的實作藏起來 (減少編譯期的 coupling?),才需要 Factory。

    對於 AI 方面來說,用腳本會比較有彈性。我覺得如何利用腳本語言的動態能力,是一個值得探討的問題。和靜態語言 C++ 相比,所需的 “Design Pattern” 會很不同。以 State Pattern 為例,動態腳本裡可以在執行期改變一個 function 的內容,例如 charater.Tick = character.Combat,而不用另外設立類別。

    State Pattern 用來實現 AI,應該可以當作是 Finite State Machine (FSM) 的一種實現方式。以前想過做一個 Editor 可視化編輯 FSM,不過在實憏的遊戲中,很多時候會遇到一些狀態組合的問題,例如上半身和下半身的動作狀態是分開的,又或加入其他屬性(痲痺、中毒、祝福…),單個 FSM 往往很難處理。到最後,好像還是看情況用不同的編程方式處理比較可行。

  14. @Milo:
    談到 FSM State 類別的創建,的確無須使用 Factory 範式就可以達成目的。我個人的習慣是使用 enum 來指定要轉換的 State 類別,並且把資料儲存在 Context 物件中以達成 Stateless 的狀態類別設計。如此一來,就不需要在其他的 State 實作檔中 include 其他(或所有)的 State 表頭檔,而且也僅需具現化一份 State 的實作體即可。

    在腳本語言中撰寫 FSM 的相關程式碼真的容易許多!事實上我在《水晶守護者》中,就是利用 Lua 的威力,才能夠很迅速地完成玩家與敵人角色的狀態邏輯。但相對要付出的代價,就是程式碼比較難以維護,稍不留意就很容易會形成一片混亂的狀態。

    不同狀態間的組合是個很難處理的問題,一般來說我會利用類似查表的方式來解決,要不然就得實作出階層式的 FSM 才行了。雖然 FSM 很簡單易用,但也不適合用來處理太複雜的條件轉換邏輯哪。

Leave a Reply