跳到主要內容

狀態機的程式設計風格

本文是要說明狀態機程式的寫法,如果你曾經看過狀態機或是已經知道怎麼樣畫狀態機,但是卻不知道怎麼樣寫程式,那麼本文將會讓你知道怎麼做。
一個狀態機包含了四個元素
  1. 狀態(state)
  2. 轉移條件(transition condition),也有人用事件(event)或是訊息(message)來表示。
  3. 輸出(output),也有人用工作(task)表示。
  4. 輸入(input)
其中輸入這項其實是非必要的。

考慮一個紅綠燈的控制一個程式,讓我們先描述紅綠燈的工作方法
  1. 綠燈 60 秒後,轉黃燈。黃燈 10 秒後,再轉紅燈。
  2. 紅燈 40 秒後,轉黃燈。黃燈 5 秒後,再轉綠燈。
首先,我們要找出所謂的狀態。在問題的描述中,狀態多半是以名詞或是形容詞的形式出現的。所以,上面的描述中,名詞有哪些?
紅燈, 黃燈, 綠燈剛好就是最明顯的三個名詞。讓我們想想看,這三個名詞是合適的狀態代表嗎?
一個好的狀態
  1. 清楚的定義。通常,不清楚的定義代表狀態內可能複合了好幾個狀態,試著把他們分離出來形成獨立的狀態,就會清楚了。
  2. 明確的轉移條件。過於複雜的轉移條件,可能也是因為複合了好幾個狀態的結果。分離他們,條件就會清楚了。
  3. 彼此間很容易找到關係。亦即若你可以找到一條轉移的路徑,從A狀態直接或間接轉移到B狀態。這兩個狀態就是有關係的。若是一個狀態或是一組狀態與其他的狀態完全沒有交集或關係。那麼你面對的可能不是單一的狀態機。把他們分成兩個分開寫吧。
毫無疑問的,紅燈, 黃燈, 綠燈一定是狀態,我們需要給狀態一個ID,好方便我們寫成構思狀態機及寫程式。 習慣上,我們會用enum來宣告state。
enum STATE {STATE_RED, STATE_YELLOW, STATE_GREEN};
那麼轉移條件呢?轉移條件通常帶有邏輯描述。具有比較限制大小長短前後轉換等詞彙或是相似的語句。 此外,在這些語句或詞彙的前後往往就是前面所找出的狀態。
在前面的描述中,符合上面所說的有
  1. 綠燈 60 秒後,轉黃燈。
  2. 黃燈 10 秒後,再轉紅燈。
  3. 紅燈 40 秒後,轉黃燈。
  4. 黃燈 5 秒後,再轉綠燈。
讓我們用比較接近程式的說法,重新撰寫這四個敘述。
  1. 若在綠燈狀態60秒後,切換到黃燈狀態。
  2. 若之前是由綠燈轉到黃燈狀態,且在黃燈狀態超過10秒後,切換到紅燈狀態。
  3. 若在紅燈狀態40秒後,切換到黃燈狀態。
  4. 若之前是由紅燈轉到黃燈狀態,且在黃燈狀態超過5秒後,切換到綠燈狀態。
要注意的是第二及第四點,雖然原來的敘述沒有特別說明前面一個狀態與狀態轉移之間的關係。但是,其中『再』這個字卻是暗中點出了這點。 在處理狀態轉移條件關係時,這種與前後文有關的敘述要特別注意。
另外是輸入與輸出的部份。雖然描述中沒有特別提及什麼使用者輸入或是其他控制訊號的輸入。實際上,如果我們要做有關時間相關的控制時, 免不了需要有timer或是counter這類的輸入來做為輔助。
而輸出的部份就比較容易理解了,對燈號的控制就是我們的輸出。
/* Define states. */
enum STATE {STATE_RED, STATE_YELLOW, STATE_GREEN};

/* State flags are declared here. */
STATE state_before_change;
STATE state_prev;
STATE state;
bool state_changing;

/* The threshold or conditions for state machine are defined here. */
const int period_red = 40;
const int period_green = 60;
const int period_yellow_green_to_red = 10;
const int period_yellow_red_to_green = 5;

/* Reset state machine to initial state. */
void reset_state_machine()
{
  state_before_change = STATE_RED;
  state_prev = STATE_RED;
  state = STATE_RED;
  state_changing = false; 
}

/* Execute state machine. reset_state_machine() 
 * should be called before the first time run_state_machine called(). 
 */
void run_state_machine()
{
  /* State transition */
  if (state_prev == STATE_RED)
  {
    if (timer >= period_red)
    {
      state = STATE_YELLOW;
    }
  }
  else if (state_prev == STATE_YELLOW)
  {
    if (state_before_change == STATE_RED && timer >= period_yellow_red_to_green)
    {
      state = STATE_GREEN;
    }
    else if (state_before_change == STATE_GREEN && timer >= period_yellow_green_to_red)
    {
      state = STATE_RED;
    }
  }
  else if (state_prev == STATE_GREEN)
  {
    if (timer >= period_green)
    {
      state = STATE_YELLOW;
    }
  }
  else
  {
    // Non-exist state.
    ASSERT(FALSE);
  }

  /* Conditions and flags for state transition. */
  state_changing = (state != state_prev);
  state_before_change = (state_changing) ? state_prev : state_before_change;
  state_prev = state;

  /* Tasks which are independent from states. */
  if (state_changing)
  {
    RESET_TIMER();
  }

  /* Tasks which are related to specified state.*/
  if (state == STATE_RED)
  {
    LED_RED(ON);
    LED_YELLOW(OFF);
    LED_GREEN(OFF);
  }
  else if (state == STATE_YELLOW)
  {
    LED_RED(OFF);
    LED_YELLOW(ON);
    LED_GREEN(OFF);
  }
  else if (state == STATE_GREEN)
  {
    LED_RED(OFF);
    LED_YELLOW(ON);
    LED_GREEN(OFF);
  }

  /* Tasks which are independant from states. */
  // DO SOMETHING.
 } /* void run_state_machine() */
這個程式主要分為兩大區塊
  1. 狀態轉移控制區塊
  2. 輸出控制區塊
其中,輸出控制區塊按順序又可細分為:
  1. 狀態無關前級輸出控制區塊
  2. 狀態相依輸出控制區塊
  3. 狀態無關後級輸出控制區塊
其中,狀態相依輸出控制區塊很好理解,就是依照現在的狀態所需控制的動作。這個區塊的 程式第一個要做的是判斷目前的狀態,然後去做對應的輸出控制。
至於位於狀態相依輸出控制區塊之前與之後的兩個控制區塊,主要是肩負輸出控制區塊的準備與收尾的工作。 這兩個區塊其實是可以分散在不同的狀態輸出控制條件中。但是,常會發現同樣的與狀態無關的工作將會重複出現在狀態控制中。 為了節省程式碼,並且減少程式碼拷貝的情形。將其獨立於狀態控制的前後將會是實作上很好的作法。 以上面的例子來說,如果我們將RESET_TIMER()寫在不同的狀態輸出控制中,則每個狀態都要寫一次。程式會變成下面這樣。
...

/* Tasks which are related to specified state.*/
if (state == STATE_RED)
{
 /* Tasks which are independant from states. */
 if (state_changing)
 {
  RESET_TIMER();
 }

 LED_RED(ON);
 LED_YELLOW(OFF);
 LED_GREEN(OFF);
}
else if (state == STATE_YELLOW)
{
 /* Tasks which are independant from states. */
 if (state_changing)
 {
  RESET_TIMER();
 }

 LED_RED(OFF);
 LED_YELLOW(ON);
 LED_GREEN(OFF);
}
else if (state == STATE_GREEN)
{
 /* Tasks which are independant from states. */
 if (state_changing)
 {
  RESET_TIMER();
 }

 LED_RED(OFF);
 LED_YELLOW(ON);
 LED_GREEN(OFF);
}
這還是因為我們的狀態少。假設有N個狀態,就會有N-1份的程式碼要寫。至於前後級之分, 主要是看狀態無關的工作是必須在狀態相關的工作做之前還是做完後,才能進行。通常屬於準備 性質的工作會放在前面,收尾性質的工作在後面。
最後,state_changing, state_before_change及state_prev這三個條件幾乎是狀態機都會用上的 條件,不妨在一開始設計狀態機時就寫上去。這三個狀態條件使用的時機為:
state_changing
用來表示現在正是狀態轉換的瞬間。需要在狀態變化時做的事情可以利用這個條件來做。
state_before_change
這是用來記錄狀態變化之前的狀態。用在我們需要清楚知道我們目前狀態是由哪個狀態變化而來。
state_prev
單純用來記錄前一個狀態,不管是否狀態有變化過。
上面的範例中已經點出了一個狀態機程式的基本結構及樣式:
  1. 宣告狀態為常數,並給予符合其意義的名稱。
  2. 撰寫狀態轉移控制條件。
  3. 填入狀態轉移旗標(state_changing, state_before_change, state_prev)
  4. 執行狀態工作的準備程序 (狀態無關前級輸出控制區塊)。
  5. 執行狀態工作 (狀態相依輸出控制區塊)。
  6. 執行狀態工作的結束程序 (狀態無關後級輸出控制區塊)。
狀態機一般都是會被引入在一個持續執行的迴圈中。所以呼叫狀態機的程式可能如下:
void main()
{
 reset_state_machine();
 
 while (1)
 {
  run_state_machine();
  sleep(1000); /* Call sleep() to avoid this loop occupy too much CPU time. */
 }
}
狀態機不是唯一描述邏輯的方法,但是卻是相當優雅的一種。尤其當你的條件多到無法處理的時候,狀態機可以幫你分類你的條件。 讓你只專心於某個狀態到另一個狀態之間的條件處理。
程式設計師應該將狀態機視為必備的技能之一。善加運用在工作之中,以期寫出可讀性更高的程式。
ps: 前面的範例中,多用if-elseif-else作為狀態的判斷。其實,還蠻多人使用switch作為狀態的判斷,這兩者其實是相同的東西。

2 則留言

這個網誌中的熱門文章

解決Python script無法在cp65001的console下執行的問題

你是否有這樣的經驗,明明沒問題的script,拿到某的電腦一直看到下面的訊息而無法執行。
LookupError: unknown encoding: cp65001 cp65001是什麼鬼!?其實,它就是UTF8阿!只是,Microsoft喜歡叫他cp65001(code page 65001號)。附帶一提,我們常用的Big5是cp950。想要知道你目前所使用的code page可以在Windows的console視窗執行

Portable Python

我常常需要把Python寫的script帶到其他電腦使用,因此,一個免安裝,可攜帶的Python就顯得十分重要。最近看過了幾個可攜式Python的方案,下面這個PortablePython是我覺得最合我意的方案。因為它提供了大部分會用到的Python module及工具,甚至連wxPython及PyGame也有。同時也有好用的Python編輯器PyScripter。所有開發Python所需的開發工具都一應俱全了!把它放到隨身碟中,就不用到處幫人安裝Python了。

PortablePython: http://www.portablepython.com/

有點兒怪的生蛋拌麵

前幾日在看日本的料理東西軍時,看到了一個料理是把麵煮好以後再把生蛋打上去攪和著吃。看起來滋味不俗!電視節目結束後立馬衝入廚房準備材料開始實作!

家裡沒有什麼蕎麥麵,就隨便拆了包泡麵煮熟,順便把冰箱裏面擺很久的甜不辣與貢丸拿出來一起煮熟,然後切條切片後放在麵上當配菜。