Design-Muster für große Entscheidungsbaum AI in C++

Question

Ich schreibe gerade eine AI für ein Spiel, das in C++ geschrieben ist. Die KI ist konzeptionell ziemlich einfach, sie läuft einfach durch einen Entscheidungsbaum und wählt geeignete Aktionen aus. Ich habe vorher Prolog für die Entscheidungs-Engine verwendet, aber aufgrund der anderen Entwickler, die C++ benutzen und einige Probleme mit der Integration des Prolog-Codes, versuche ich jetzt, es nach C++ zu portieren.

Derzeit habe ich eine Reihe von Fakten und Regeln in Prolog (100+). Viele drücken Dinge in der Form aus, wenn game_state dann Aktion xyz macht. Die meisten Regeln sind ziemlich einfach, einige sind ziemlich komplex. Ich betrachtete einen endlichen Automaten, aber das schien nicht so gut auf die größeren Situationen zu skalieren. Mein erster Versuch, dies in C++ zu kodieren, war ein riesiger Albtraum von dann noch anderen Case-Statements. Ich hatte diese Art von Code überall auftauchen:

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 
    } 

Die Komplexität wurde schnell unüberschaubar.

Wenn es eine gute Möglichkeit gibt, diese Art von Problem in C++ zu codieren? Gibt es gute Entwurfsmuster, um mit dieser Art von Situation umzugehen? Es gibt keine Anforderung, dass die Logik in der Quelle enthalten sein muss, sie muss nur von C++ aus zugänglich sein. Die einzige wirkliche Anforderung ist, dass es einigermaßen schnell ist.

Ich schaute auch auf Regeln Motoren und wenn schnell genug, könnten sie angemessen sein. Weißt du, ob es eine Open-Source-C++ - Regel-Engine gibt, die angemessen wäre?

Answer 1

Code ist Daten und Daten sind Code. Sie haben funktionierenden Code - Sie müssen ihn nur in C++ verfügbar machen, so dass er kompilieren kann, dann können Sie einen minimalen Interpreter implementieren, um ihn zu evaluieren.

Eine Möglichkeit besteht darin, Ihre Prolog-Regeln zu übernehmen und sie so direkt wie möglich in eine Datenstruktur zu übersetzen. Vielleicht könnten Sie eine einfache Tabelle entwerfen wie:

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... 
} 

ähnlich Funktionsaufrufe Datenstrukturen so füllen, dass es zu Ihrem ursprünglichen Prolog aussieht:

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

Dann implementieren Sie einen einfachen Dolmetscher um diese Datenstruktur zu durchqueren und die Antworten zu finden, die Sie brauchen. Mit weniger als 1000 Regeln ist ein Brute-Force-Ansatz bei der Suche wahrscheinlich schnell genug, aber Sie können später immer schlauer werden und versuchen, Dinge so zu machen, wie es eine echte Prolog-Umgebung wäre, wenn die Zeit dafür gekommen ist.

Answer 2

Ich verstehe nicht wirklich, warum eine endliche Zustandsmaschine für Ihr Spiel nicht ausreichend ist. Es ist eine übliche Art und Weise zu tun, was Sie wollen. Sie könnten es datengesteuert machen, um den Code vor konkreten Aktionen zu schützen. Der endliche Zustand m. wird auch in "AI for Game Dev" beschrieben. O'Reilly (David M. Bourg & Glenn Seemann) Sie möchten vielleicht Ihre Regeln in mehrere kleinere Regelsätze aufteilen, um die Maschine klein und verständlich zu halten.

Answer 3

Wenn Sie Ihren Prolog-Code zu c konvertieren möchten ++ Code, haben einen Blick auf die Castor-Bibliothek (C++), die Logikprogrammierung in C ermöglichen ++: http://www.mpprogramming.com/Cpp/Default.aspx

Ich habe es nicht ausprobiert, mich, so Ich weiß nichts über seine Leistung.

Wenn Sie eine State-Maschine verwenden möchten, haben Sie einen Blick auf Boost.Meta State Machine

Answer 4

Wie wäre Verwendung Quecksilber?Es ist im Grunde gebaut, um mit C-Code zu interagieren.

Answer 5

können Sie Polymorphismus verwenden. Das Aufrufen einer virtuellen Funktion ist in Wirklichkeit ein großartiger Schalter/Fall, der vom Compiler für Sie erstellt und optimiert wurde.

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!" 
} 

Im obigen Beispiel, ich muss über eines der Staaten nicht wechseln oder sogar wissen, dass verschiedene Zustände existieren oder sie tun, was (in der Statemachine Klasse, sowieso), war die Auswahllogik getan vom Compiler.

Answer 6

Der Versuch Prolog des Ausdruckskraft mit Zustandsmaschinen entsprechen ist wie der Versuch, ein Auto mit einem Fahrrad zu entkommen.

Castor ist wahrscheinlich der Weg zu gehen. Es ist sehr leicht und ermöglicht eine reibungslose Interop zwischen Logic-Programmierung und Rest von C++. Werfen Sie einen Blick auf den Tutorial-Videos auf http://www.mpprogramming.com/cpp