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

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

12 голосов
/ 11 сентября 2010

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

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

    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 ++ с открытым исходным кодом?

Ответы [ 6 ]

10 голосов
/ 14 сентября 2010

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

Одна из возможностей - взять ваши правила Пролога и перевести их самым прямым способом в структуру данных. Может быть, вы могли бы разработать простой стол, как: 

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

Аналогичным образом, вызовы функций могут заполнять структуры данных таким образом, чтобы он выглядел аналогично вашему исходному Прологу: 

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

Затем вы реализуете простой интерпретатор для обхода этой структуры данных и поиска ответов, которые вам нужны. При менее чем 1000 правилах подход с использованием грубой силы при поиске, вероятно, будет достаточно быстрым, но вы всегда можете стать умнее позже и попытаться сделать то же, что и в реальной среде Prolog, когда придет время.

5 голосов
/ 15 сентября 2010

Вы можете использовать полиморфизм. Вызов виртуальной функции - это, по сути, переключатель / случай с большой задницей, который выполняется и оптимизируется для вас компилятором. 

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 голосов
/ 15 сентября 2010

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

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

Если вы хотите использовать конечный автомат, взгляните на Boost.Meta State Machine

2 голосов
/ 11 сентября 2010

Я не совсем понимаю, почему конечный автомат не подходит для вашей игры.Это обычный способ делать то, что вы хотите.Вы можете сделать это на основе данных, чтобы сохранить ваш код в чистоте от конкретных действий.Конечное состояние m.О'Рейли (David M. Bourg & Glenn Seemann) также описывает «AI для разработчика игр». Возможно, вы захотите разделить ваши правила на несколько небольших наборов правил, чтобы машина была маленькой и понятной.

1 голос
/ 15 сентября 2010

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

0 голосов
/ 24 сентября 2010

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

Кастор, наверное, и есть путь. Он очень легкий и обеспечивает плавное взаимодействие между программированием на логику и остальной частью C ++. Посмотрите обучающие видео на http://www.mpprogramming.com/cpp

...