Trí Tuệ Nhân Tạo trong Games - Phần 1: Thiết Kế AI với FSM

Trí tuệ nhân tạo là gì?

Các tổ chức sống như động vật, con người đều có trí tuệ giúp trong việc đưa ra những quyết định. Máy tính chỉ là thiết bị điện tử có thể xử lý dữ liệu, phép toán logic ở tốc độ cao. Trí tuệ nhân tạo (AI) là đề tài chính của việc tạo ra máy tính có thể suy nghĩ và quyết định như tổ chức sống, thực thi những phép toán chuyên biệt.

FSM

Là từ viết tắt của Finite State Machine hay có thể hiểu là 1 đối tượng dùng để chuyển trạng thái. Nó là những mô hình đơn giản nhất và thông dụng nhất trong việc tạo AI, bao gồm 1 số trạng thái có hạn và trạng thái khởi tạo, sau đó nó sẽ sử dụng những sự kiện để chuyển trạng thái này sang trạng thái khác, 1 đối tượng AI chỉ có 1 trạng thái nhất định tại 1 thời điểm.

Thành phần cơ bản

FSM có 4 thành phần cơ bản:

1. Trạng thái: tập hợp các trạng thái của đối tượng.
2. Chuyển trạng thái: định nghĩa mối quan hệ giữa các trạng thái khác nhau.
3. Quy luật: được dùng để khởi đầu 1 sự kiện chuyển trạng thái.
4. Sự kiện: thành phần dùng để kiểm tra quy luật.

Ví dụ

Dưới đây là 1 FSM đơn giản về 1 con Monkey có 3 trạng thái là: stop, walk, turn.

#ifndef __Monkey_h__
#define __Monkey_h__  
  
#include <time.h>  
  
#include "cocos2d.h"  
  
USING_NS_CC;  
  
  
#define MAX_STOP_TIME  10  
#define MAX_WALK_TIME  20  
  
#define MAX_WALK_DIST  100  
  
enum MonkeyState {  
    stSTOP,  
    stWALK,  
    stTURN  
};  
    
class Monkey  : public Node {  
public:  
    Monkey()  {  
        log("Monkey()");  
    }  
  
    CREATE_FUNC(Monkey);  
  
    virtual bool init() {  
        _curPos = 0;  
        _step = 1;  
  
        changeState(stSTOP);  
  
        this->scheduleUpdate();  
  
        return true;  
    }  
  
    void changeState(MonkeyState newState) {  
        _curState = newState;  
        _curTime = time(0);          
    }  
  
    void stop() {  
        cocos2d::log("stop()");  
    }  
  
  
    void walk() {  
        _curPos += _step;  
        cocos2d::log("walk(): pos=%d", _curPos);  
    }  
  
  
    void turn() {  
        _step *= -1;  
        cocos2d::log("turn(): step=%d", _step);          
    }  
  
  
    void update(float dt) {  
        switch (_curState) {  
        case stSTOP:  
            if (isStopTimeout()) {  
                changeState(stWALK);  
                walk();  
            }  
            break;  
  
        case stWALK:  
            walk();  
  
            if (isWalkOutBorder()) {  
                changeState(stTURN);  
                turn();  
            } else if (isWalkTimeout()) {  
                changeState(stSTOP);  
                stop();  
            }  
            break;  
  
        case stTURN:  
            changeState(stWALK);  
            walk();  
            break;  
        }  
    }  
  
private:  
    MonkeyState _curState;  
  
    time_t _curTime;  
  
    int    _curPos;  
    int    _step;  
  
public:  
    bool isStopTimeout() {  
        return (time(0) - _curTime > MAX_STOP_TIME);  
    }  
  
    bool isWalkTimeout() {  
        return (time(0) - _curTime > MAX_WALK_TIME);  
    }  
   
    bool isWalkOutBorder() {  
        return (_curPos > MAX_WALK_DIST || _curPos < -MAX_WALK_DIST);  
    }  
};  
  
#endif // __Monkey_h__

• Dòng 16-20: khởi tạo 1 enum là các trạng thái của con Monkey.
• Dòng 30-39: khởi tạo các thuộc tính của Monkey, trạng thái đầu tiên là stop, và sau đó chạy hàm update() của Monkey.
• Dòng 41-44: hàm có chức năng thay đổi trạng thái của Monkey.
• Dòng 46-60: hàm trạng thái của Monkey gồm stop, walk, turn.
• Dòng 63-89: hàm update của Monkey, ứng với giá trị của _curState sẽ có 1 trạng thái nhất định của Monkey. Chú ý kỹ các điều kiện chuyển trạng thái trong hàm update này.
• Dòng 92-97: khai báo các thuộc tính cần có.
• Dòng 100-110: gồm các hàm điều kiện, hàm update sẽ kiểm tra điều kiện ở các hàm này, nếu phù hợp sẽ chuyển trạng thái cho Monkey.

Với việc hoàn tất công việc thiết kế AI ở trên thì công việc hoàn thành rất tốt nhưng nếu phát triển hơn cần thêm các trạng thái bổ sung. Với thiết kế ở trên, nếu có N state cho AI thì thời gian xử lý trung bình sẽ là N/2.

Tham khảo

• https://www.cocos2d-x.org
• https://www.en.wikipedia.org

Bài chung series

• Trí Tuệ Nhân Tạo trong Games - Phần 1: Thiết Kế AI với FSM
• Trí Tuệ Nhân Tạo trong Games - Phần 2: Thiết Kế AI với FSM