Шаблон проектирования для большого дерева решений на основе дерева в С++

В настоящее время я пишу AI для игры, написанной на С++. ИИ концептуально довольно прост, он просто проходит через дерево решений и выбирает соответствующие действия. Я ранее использовал пролог для механизма принятия решений, но из-за других разработчиков, использующих С++, и некоторые проблемы с интеграцией кода пролога, который я сейчас пытаюсь перенести на С++.

В настоящее время у меня есть куча фактов и правил в прологе (100+). Многие выражают вещи в форме, если game_state затем выполняет действие xyz. Большинство правил довольно просты, некоторые из них довольно сложны. Я посмотрел на подход с конечным автоматом, но, похоже, это не так масштабно для больших ситуаций. Моя первая попытка кодирования этого в С++ была огромным кошмаром if if else case case. У меня появился такой код:

    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
    }

Сложность стала быстро неуправляемой.

Если есть хороший способ закодировать эту проблему в С++? Есть ли хорошие шаблоны проектирования для решения этой ситуации? Нет требования, чтобы логика содержалась в источнике, она просто должна быть доступна из С++. Единственным реальным требованием является то, что он достаточно быстр.

Я также рассмотрел механизмы правил, и если бы они были достаточно быстрыми, они могли бы быть подходящими. Знаете ли вы, есть ли механизм с открытым исходным кодом С++, который был бы уместен?

Ответ 1

Код - это данные, а Data - код. У вас есть рабочий код - вам просто нужно выставить его на С++ так, как он может скомпилировать, тогда вы можете реализовать минимальный интерпретатор для его оценки.

Одна из возможностей - принять ваши правила 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, когда придет время.

Ответ 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) логика выбора выполнялась компилятором.

Ответ 3

Если вы хотите преобразовать свой пролог-код в код С++, взгляните на библиотеку Castor (С++), которая позволяет программировать логику в С++: http://www.mpprogramming.com/Cpp/Default.aspx

Я сам не пробовал, поэтому я ничего не знаю об этой производительности.

Если вы хотите использовать государственную машину, посмотрите на машину состояния Boost.Metap >

Ответ 4

Я действительно не понимаю, почему конечная машина не является достаточной для вашей игры. Это обычный способ сделать то, что вы хотите. Вы можете заставить данные управлять, чтобы оставаться чистым от конкретных действий. Конечное состояние т. также описано в "AI for Game Dev" O'Reilly (David M. Bourg and Glenn Seemann) Возможно, вам захочется разделить ваши правила на несколько более мелких наборов правил, чтобы машина была маленькой и понятной.

Ответ 5

Как насчет использования ртути? он в основном построен для взаимодействия с кодом C.

Ответ 6

Попытка сопоставить выразительную силу Prolog с государственными машинами - это похоже на попытку обогнать автомобиль с помощью велосипеда.

Кастор - это, наверное, путь. Он очень легкий и обеспечивает плавный переход между программным обеспечением Logic и остальным С++. Взгляните на обучающие видеоролики на http://www.mpprogramming.com/cpp