Mẫu thiết kế cho AI dựa trên quyết định lớn trong C++

Question

Tôi hiện đang viết AI cho trò chơi được viết bằng C++. AI là khái niệm khá đơn giản, nó chỉ chạy qua cây quyết định và chọn các hành động thích hợp. Trước đây tôi đã sử dụng prolog cho công cụ quyết định nhưng do các nhà phát triển khác sử dụng C++ và một số vấn đề với việc tích hợp mã prolog tôi đang cố gắng chuyển nó sang C++.

Hiện tại tôi có một loạt các sự kiện và quy tắc trong prolog (100+). Nhiều người thể hiện những điều trong hình thức, nếu game_state sau đó làm xyz hành động. Hầu hết các quy tắc khá đơn giản với một số ít phức tạp. Tôi nhìn vào một cách tiếp cận máy tính hữu hạn, nhưng điều đó dường như không quy mô đến các tình huống lớn hơn rất tốt. Nỗ lực đầu tiên của tôi trong việc mã hóa điều này trong c + + là một cơn ác mộng lớn nếu có các trường hợp khác. Tôi có loại mã này xuất hiện ở mọi nơi:

if(this->current_game_state->some_condition == true){ 
     if(this->current_game_state->some_other_condition == false){  
       //some code 
     }else{ 
      return do_default_action(); 
     } 
    }else if(this->current_game->another_condition){ 
     //more code 
    } 

Sự phức tạp trở nên nhanh chóng không thể quản lý được.

Nếu có cách nào tốt để mã loại vấn đề này trong C++? Có bất kỳ mẫu thiết kế tốt nào để đối phó với loại tình huống này không? Không có yêu cầu rằng logic phải được chứa trong nguồn, nó chỉ cần có thể truy cập từ C++. Yêu cầu thực sự duy nhất là nó nhanh chóng hợp lý.

Tôi cũng xem xét các công cụ quy tắc và nếu đủ nhanh, chúng có thể phù hợp. Bạn có biết liệu có một cỗ máy quy tắc C++ nguồn mở nào phù hợp không?

Answer 1

Mã là dữ liệu và Dữ liệu là Mã. Bạn đã có mã làm việc - bạn chỉ cần để lộ nó cho C++ theo cách nó có thể biên dịch, sau đó bạn có thể thực hiện một trình thông dịch tối thiểu để đánh giá nó.

Một khả năng là thực hiện các quy tắc Prolog của bạn và dịch chúng theo cách trực tiếp nhất có thể đến cấu trúc dữ liệu. Có lẽ bạn có thể thiết kế một bảng đơn giản như:

struct { 
    State coming_from; 
    Event event; 
    void (*func)(some, args); 
    State going_to; 
} rules[] = { 
    { WANDERING_AROUND, HEAR_SOUND, look_around, ENEMY_SEEN }, 
    { ENEMY_SEEN,  GUN_LOADED, fire_gun, SNEEK_AWAY }, 
    { next, rule, goes, here }, 
    etc... 
} 

Tương tự như vậy, các cuộc gọi chức năng có thể cư cấu trúc dữ liệu theo một cách như vậy mà nó trông giống như Prolog ban đầu của bạn:

void init_rules() { 
    rule("Parent", "Bill", "John"); 
    rule("Parent", "Paul", "Bill"); 
    // 99 more rules go here... 
} 

Sau đó, bạn thực hiện một thông dịch viên đơn giản để duyệt qua cấu trúc dữ liệu đó và tìm câu trả lời bạn cần. Với ít hơn 1000 quy tắc, một cách tiếp cận bạo lực trong tìm kiếm có thể đủ nhanh, nhưng bạn luôn có thể thông minh sau và cố gắng làm mọi thứ theo cách mà môi trường Prolog thực sự sẽ xảy ra khi thời gian đến.

Answer 2

Tôi không thực sự hiểu tại sao một máy trạng thái hữu hạn không hiệu quả cho trò chơi của bạn. Đó là một cách phổ biến để làm những gì bạn muốn. Bạn có thể làm cho nó dữ liệu được định hướng để giữ cho bạn mã sạch từ hành động cụ thể. Trạng thái hữu hạn m. cũng được mô tả trong "AI cho Game Dev" O'Reilly (David M. Bourg & Glenn Seemann) Bạn có thể muốn chia nhỏ quy tắc của bạn thành nhiều bộ quy tắc nhỏ hơn để giữ cho máy nhỏ và dễ hiểu.

Answer 3

Nếu bạn muốn chuyển đổi mã prolog của bạn để C++ mã, có một cái nhìn tại các thư viện Castor (C++) cho phép logic lập trình trong C++: http://www.mpprogramming.com/Cpp/Default.aspx

tôi đã không thử nó ra bản thân mình, vì vậy Tôi không biết gì về hiệu suất của nó.

Nếu bạn muốn sử dụng một nhà máy, có một cái nhìn tại Boost.Meta State Machine

Answer 4

Làm thế nào về việc sử dụng thủy ngân?về cơ bản nó được xây dựng để giao tiếp với mã C.

Answer 5

Bạn có thể sử dụng đa hình. Gọi một hàm ảo có hiệu quả là một chuyển đổi lớn/trường hợp được thực hiện và tối ưu hóa cho bạn bởi trình biên dịch.

class GameState { 
    virtual void do_something() { std::cout << "GameState!"; } 
    // some functions 
    virtual ~GameState() {} 
}; 
class SomeOtherState : public GameState { 
    // some other functions 
    virtual void do_something() { std::cout << "SomeOtherState!"; } 
}; 
class MyFinalState : public GameState { 
    virtual void do_something() { std::cout << "MyOtherState!"; } 
}; 
class StateMachine { 
    std::auto_ptr<GameState> curr_state; 
public: 
    StateMachine() 
     : curr_state(NULL) {} 
    void DoSomething() { curr_state->DoSomething(); } 
    void SetState(GameState* ptr) { curr_state = ptr; } 
    template<typename T> void SetState() { curr_state = new T; } 
}; 
int main() { 
    StateMachine sm; 
    sm.SetState(new SomeOtherState()); 
    sm.SetState<SomeOtherState>(); 
    sm.DoSomething(); // prints "SomeOtherState!" 
    sm.SetState<MyFinalState>(); 
    sm.DoSomething(); // prints "MyFinalState!" 
} 

Trong ví dụ trên, tôi không cần phải chuyển đổi về bất cứ tiểu bang, hoặc thậm chí biết rằng các quốc gia khác nhau tồn tại hoặc những gì họ làm (trong lớp statemachine, anyways), logic lựa chọn đã được thực hiện bởi trình biên dịch.

Answer 6

Cố gắng phù hợp với sức mạnh biểu cảm của Prolog với các máy trạng thái giống như cố gắng chạy nhanh hơn một chiếc xe hơi bằng xe đạp.

Castor có lẽ là con đường để đi. Nó rất nhẹ và cho phép tương tác mượt mà giữa lập trình Logic và phần còn lại của C++. Hãy xem các video hướng dẫn trên http://www.mpprogramming.com/cpp