基于c ++的大决策树设计模式

Question

我正在为一个用c ++编写的游戏编写AI.AI在概念上相当简单,它只是通过决策树运行并选择适当的操作.我以前使用prolog作为决策引擎,但是由于其他开发人员使用c ++以及集成prolog代码的一些问题,我现在正尝试将其移植到c ++.

目前我在prolog(100+)中有一堆事实和规则.许多表达形式的东西,如果game_state然后做动作xyz.大多数规则都相当简单,有些规则相当复杂.我看了一个有限的状态机方法,但这似乎并没有如此好地扩展到更大的情况.我在c ++中编写这个代码的第一次尝试是一个巨大的噩梦,如果是其他案例陈述.我把这种代码随处可见:

    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
    }

复杂性很快变得难以管理.

如果有一个很好的方法来编写c ++中的这类问题？有没有好的设计模式来处理这种情况？不要求逻辑必须包含在源代码中,只需要从c ++访问即可.唯一真正的要求是它速度相当快.

我还查看了规则引擎,如果速度足够快,它们可能是合适的.你知道是否有适合的开源c ++规则引擎？

Answer 1

代码是数据,数据是代码.你有工作代码 - 你只需要以可以编译的方式将它暴露给C++,然后你可以实现一个最小的解释器来评估它.

一种可能性是采用Prolog规则并以最直接的方式将它们转换为数据结构.也许你可以设计一个简单的表,如:

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

类似地,函数调用可以以与原始Prolog类似的方式填充数据结构:

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

然后,您实现一个简单的解释器来遍历该数据结构并找到您需要的答案.只有不到1000条规则,搜索中的暴力方法可能足够快,但您可以随时变得聪明,并尝试按照真正的Prolog环境的方式来做事.

Answer 2

你可以使用多态.调用虚拟函数实际上是编译器为您完成并优化的大型开关/案例.

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

在上面的例子中,我不需要切换任何状态,甚至不知道存在不同的状态或它们做什么(在StateMachine类中,无论如何),选择逻辑由编译器完成.