[C20] Lập trình máy trạng thái (Finite state machine programing)

ntaquan

Gà con
Finite state machine (FSM) là một mô hình toán học biểu diễn trạng thái của hệ, đây là một nhánh của lý thuyết Automata, được ứng dụng rất nhiều trong các hệ thống tự động, quản lý đơn hàng, game, regex, trí tuệ nhân tạo (AI),...
Trong môn "kỹ thuật số", chúng ta đã được giới thiệu qua 2 loại cơ bản là Mealy và Moore. Dễ thấy, một FSM thường được biểu diễn bởi flow chart hoặc state table, từ đó ta có thể biết được cách thức hoạt động của hệ thống.
Đây là một VD điển hình được sử dụng trong một bộ não của một quân địch trong một game RPG, mỗi state đại diện cho một hành động (evade, attack, wander,...), một state sẽ có các transition chuyển đổi qua các state khác thông qua các event (if player is near, GO FOR THE HEADDDD!!!!!)
fsm_enemy_brain.png

Thế này thì enemy khôn hơn cả player rồi :doubt:

Đặc điểm của FSM:
  • Loại bỏ được những câu lệnh if, else, while lồng nhau. Đơn giản hóa vấn đề, dễ kiểm tra (debug).
  • Mỗi state tương ứng sẽ có một hàm thực hiện, tách biệt với các state khác. Phù hợp cho việc mở rộng, phát triển sau này.
  • Chỉ phù hợp với một vài bài toán nhất định.
Ý tưởng triển khai:
Do các tác vụ lặp đi lặp lại theo một chu trình cố định, hữu hạn. Chúng ta sẽ sử dụng một vòng lặp vô tận để cập nhật liên tục ngõ ra dựa vào các state hiện tại và ngõ vào.
Một enum bao gồm các state:
typedef enum {STATE_A, STATE_B, STATE_C} state_t;

Các hàm được gọi tương ứng của từng state:
void function_state_A(void);
void function_state_B(void);
void function_state_C(void);

Thế trong mấy hàm đó viết gì?? Tự do biến hóa nhé :v
C:
void function_state_A(void)
{
    // TODO
    if (<trigger_event>)
        state = STATE_B;     // go to state B
}
Để ý là trước khi ra khỏi một hàm, ta cần phải cập nhật biến state để nhảy qua trạng thái khác mỗi khi có một event nào đó xảy ra.

Có 2 phương pháp thường dùng để lập trình FSM:
1. Dùng switch-case
C:
typedef enum {STATE_A, STATE_B, STATE_C} state_t;

volatile state_t state = STATE_A;
void function_state_A(void);
void function_state_B(void);
void function_state_C(void);

int main(void)
{
    while (1)
    {
        switch (state)
        {
            case STATE_A:
                function_state_A();
                break;
      
            case STATE_B:
                function_state_B();
                break;
      
            case STATE_C:
                function_state_C();
                break;
        }
    }
    return 0;
}
Túm lại thì switch-case sẽ chọn xem hàm nào được thực hiện dựa vào biến state qua mỗi vòng lặp.

2. Dùng array con trỏ hàm (ngắn gọn nhưng hack não hơn)
C:
typedef enum {STATE_A, STATE_B, STATE_C} state_t;

volatile state_t state = STATE_A;
void function_state_A(void);
void function_state_B(void);
void function_state_C(void);
void (*state_table[])(void) = {function_state_A, function_state_B, function_state_C};

int main(void)
{
    while (1)
    {
        state_table[state]();
    }
    return 0;
}
Nhận xét: phương pháp này có time complexity là O(1) do thời gian tra bảng là hằng số, nên nhanh hơn so với phương pháp 1.
Bài tập: Có làm mới có ăn chứ :misdoubt:
Game catch the led, cần 2 LED (1 red, 1 green) + 1 button + 1 MCU. Mlem cho ai dùng MSP430 :big grin:
Mở đầu game là cả 2 LED sẽ chớp tắt 3 lần, sau đó thay phiên nhau chớp tắt theo một chu kỳ T nào đó. Nếu trong lúc luân phiên đó, player ấn vào button khi LED green đang sáng thì nháy LED green 2 lần rồi lại thay phiên nhau chớp tắt với thời gian T nhỏ hơn (qua màn). Còn nếu player ấn vào button khi LED red đang sáng thì cũng nháy LED red 2 lần (tương tự green) để báo thua rồi sau đó reset game (reset T).

Trước khi đặt mông vào code hãy tìm cách vẽ flow chart hoặc state table của hệ (cần mấy state, transition thế nào), và cũng nên suy nghĩ tới trường hợp nếu không dùng FSM thì cần tất cả bao nhiêu lệnh if và while @@.
 
Last edited:

Vien_beos

Trứng gà
hôm trước có đọc một lần chả hiểu cái gì cả :doubt: nay học kỹ thuật số phần hệ tuần tự mới thấy quen quen,đọc lại thì ok, chả hiểu gì cạ :-s:-s
 
Top