Design pattern for large decision tree based AI in c++

Question

I'm currently writing an AI for a game that is written in c++. The AI is conceptually fairly simple, it just runs through a decision tree and picks appropriate actions. I was previously using prolog for the decision engine but due to the other developers using c++ and some issues with integrating the prolog code I'm now trying to port it to c++.

Currently I have a bunch of facts and rules in prolog (100+). Many express things in the form, if game_state then do action xyz. Most of the rules are fairly simple with a few being rather complex. I looked at a finite state machine approach, but that didn't seem to scale to the larger situations so well. My first attempt at coding this up in c++ was a huge nightmare of if then else case statements. I had this sort of code popping up everywhere:

    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
    }

The complexity became quickly unmanageable.

If there a good way to code this sort of problem in c++? Are there any good design patterns to deal with this type of situation? There is no requirement that the logic has to be contained within the source, it just needs to be accessible from c++. The only real requirement is that it is reasonably fast.

I also looked at rules engines and if fast enough they could be appropriate. Do you know if there is a open source c++ rules engine that would be appropriate?

Answer 1

Hi

You can consider following strategy.

Ask your self following questions?

1- How many of rules are there?

2- Are these rules changing fortnightly?

3- What is the avg. rate of new rules which are introduced in the system?

if you convinced that no of rules are pretty much and these rules are chaging frequently and there is a good rate that new rules are being introduced then Consider using Design Pattern

For your case because your code maintains state and change behaviour based upon state , try to implement State Design Pattern which can be found here.

http://en.wikipedia.org/wiki/State_pattern

http://www.codeproject.com/KB/architecture/statepattern3.aspx

http://www.codeproject.com/Articles/38962/State-Design-Pattern.aspx

Answer 2

I don't really get why a finite state machine is not sufficiant for your game. It is a common way to do what you want to. You could make it data driven to stay you code clean from concrete actions. The finite state m. is also described in "AI for Game Dev" O'Reilly (David M. Bourg & Glenn Seemann) You maybe want to split you rules in several smaller rule sets to keep the machine small and understandable.

Answer 3

Code is Data, and Data is Code. You've got working code - you just need to expose it to C++ in a way it can compile, then you can implement a minimal interpreter to evaluate it.

One possibility is to take your Prolog rules and translate them in the most direct way possible to a data structure. Maybe you could design a simple table like:

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

Similarly, function calls can populate data structures in such a way that it looks similar to your original Prolog:

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

Then you implement a simple interpreter to traverse that data structure and find the answers you need. With less than 1000 rules, a brute force approach at searching is likely to be fast enough, but you can always get clever later and try to do things the way a real Prolog environment would when the time comes.

Answer 4

Hi

If you want to convert your prolog code to c++ code, have a look at the Castor library (C++) which enable Logic Programming in C++: http://www.mpprogramming.com/Cpp/Default.aspx

I haven't tried it out myself, so I don't know anything about it's performance.

If you want to use a state-machine, have a look at Boost.Meta State Machine

Answer 5

How about use mercury? its basically built to interface with C code.

Answer 6

You can use polymorphism. Calling a virtual function is effectively a big-ass switch/case that's done and optimized for you by the compiler.

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

In the above example, I didn't need to switch about any of the states, or even know that different states exist or what they do (in the StateMachine class, anyways), the selection logic was done by the compiler.

Answer 7

Trying to match Prolog's expressive power with state machines is like trying to outrun a car with a bicycle.

Castor is probably the way to go. It is very lightweight and allows smooth interop between Logic programming and rest of C++. Take a look at the tutorial videos on http://www.mpprogramming.com/cpp