Предыдущие части:

1. Игровой искусственный интеллект: Введение
2. Игровой искусственный интеллект: Тестовая площадка
3. Игровой искусственный интеллект: Простейшие алгоритмы
4. Игровой искусственный интеллект: Поиск пути

Обновление проекта

Скачайте архив или сделайте pull (тэг v.1.3), чтобы получить актуальную версию исходников.

Изменения следующие:

1. Боты условно поделены на две группы: атакующие (желтые) и защищающиеся (зеленые);
2. Для каждой группы можно независимо выбирать ИИИ;
3. Добавлен NullBotAI (см. Паттерн Null Object)
4. Для атакующих Ботов рассчитывается "Карта Опасности", о которой мы скоро поговорим;
5. Добавлен специфичный для защищающихся Ботов ИИИ, который пытается убежать от атакующих Ботов.

Задача для защищающихся Ботов заключается в том, чтобы предотвратить столкновение с атакующими. Проще всего разбить эту задачу на две части: сначала оценить степень опасности каждой области игрового мира; а затем выбрать оптимальный в сложившейся ситуации ход.

Карта Опасности

Зона вокруг атакующего Бота - опасна, а чем ближе мы к нему, тем опасность серьезнее. На основе этого логичного предположения не сложно построить "Карту Опасности". Для этого поставим каждой клетке игрового мира некий балл. Чем выше балл, тем опаснее клетка:

class AIModel {
public:
    // …

    // Клетка с атакующим Ботом = смерть
    static const int DEATH_RADIUS = 0;

    // Клетки вокруг атакующего Бота = сверх опасно
    static const int EXTREME_DANGER_RADIUS = 1;

    // Область в двух клетках от атакующего Бота = нужно быть осторожным
    static const int WARNING_RADIUS = 2;

    // Очки для различных уровней опасности (выбраны достаточно произвольно)
    enum DangerLevel {
        WARNING = 10,
        CRITICAL = 30,
        EXTREME = 50,
        DEATH = 100
    };

    // …
};

void AIModel::refreshDangerMap() {
    for( Row& r : m_dangerMap ) {
        std::fill( r.begin(), r.end(), 0 );
    }

    for( auto b : m_bots ) {
        if( b->getType() != 2 ) {
            // Нас интересуют только атакующие Боты
            continue;
        }

        int x = b->getX() / BLOCK_SIZE;
        int y = b->getY() / BLOCK_SIZE;
        markDangerArea( x, y, DEATH_RADIUS, DEATH );
        markDangerArea( x, y, EXTREME_DANGER_RADIUS, EXTREME );
        markDangerArea( x, y, WARNING_RADIUS, WARNING );
    }
}

void AIModel::markDangerArea( int x, int y, int radius, int score ) {
    for( int row = y - radius; row <= y + radius; ++row ) {
        for( int column = x - radius; column <= x + radius; ++column ) {
            if(
                column < 0 || m_field[ 0 ].size() <= static_cast< size_t >( column ) ||
                row < 0 || m_field.size() <= static_cast< size_t >( row )
            ) {
                continue;
            }
            m_dangerMap[ row ][ column ] += score;
        }
    }
}

Для большей наглядности все опасные клетки подсвечиваются в Представлении на основании их уровня (см. скриншот выше).

Убегающий ИИИ

Имея Карту Опасности, защищающийся Бот может сориентироваться, в какую сторону лучше идти. Если у него есть несколько допустимых направлений, то интуитивно понятно, что лучше всего выбирать более безопасное (хотя это и не всегда работает правильно). За основу возьмем простой ИИИ SingleMemRandomAI, который обеспечивал достаточно естественную траекторию движения:

// Уровень опасности будем оценивать по крайним точкам на основе ожидаемого положения Бота после хода
// Если ход сделан налево, то проверяем соседнюю клетку слева
// Если ход сделан вверх. то проверяем соседнюю клетку сверху
// И т.д.
int getDanger( Bot::Direction dir, const Bot& b, const AIModel& model ) {
    const int halfBotSize = b.getSize() / 2;

    Bot bCopy = b;
    bCopy.setDirection( dir );
    bCopy = model.doMove( bCopy );
    int x = bCopy.getX();
    int y = bCopy.getY();
    switch( dir ) {
    case Bot::LEFT:
        x -= halfBotSize;
        break;
    case Bot::RIGHT:
        x += halfBotSize;
        if( x % AIModel::BLOCK_SIZE == 0 ) {
            x -= AIModel::BLOCK_SIZE;
        }
        break;
    case Bot::UP:
        y -= halfBotSize;
        break;
    case Bot::DOWN:
        y += halfBotSize;
        if( y % AIModel::BLOCK_SIZE == 0 ) {
            y -= AIModel::BLOCK_SIZE;
        }
        break;
    default:
        break;
    }

    return model.getDangerMap()[ y / AIModel::BLOCK_SIZE ][ x / AIModel::BLOCK_SIZE ];
}

void RunAwayAI::doStep( const AIModel& model, Bot* bot ) {
    bot->startMoving();

    auto directions = model.findValidDirections( *bot );

    if( !directions.empty() ) {
        // Сначала находим минимальный уровень опасности в соседних клетках для допустимых направлений
        auto it = directions.begin();
        int minDanger = getDanger( *it, *bot, model );
        ++it;
        for( ; it != directions.end(); ++it ) {
            int danger = getDanger( *it, *bot, model );
            if( danger < minDanger ) {
                minDanger = danger;
            }
        }

        // Исключаем из допустимых все направления, уровень опасности для которых превышает минимум
        // Этим мы гарантируем, что заведомо более опасные пути выбираться не будут
        it = directions.begin();
        while( it != directions.end() ) {
            if( minDanger < getDanger( *it, *bot, model ) ) {
                it = directions.erase( it );
            } else {
                ++it;
            }
        }
    }

    // А здесь то же самое, что и для SingleMemRandomAI
    if(
        !directions.empty() &&
        std::find( directions.begin(), directions.end(), bot->getDirection() ) == directions.end()
    ) {
        bot->setDirection( directions[ rand() % directions.size() ] );
    }
}

Алгоритм достаточно прост, но и работает не идеально (идеальный бы не допускал столкновений). Однако следует учитывать, что защищающиеся Боты находятся в заведомо проигрышной ситуации, поэтому получившееся решение смотрится вполне приемлемым.

Недостатки текущей реализации

ИИИ поиска и убегания работают, но для них наблюдаются некоторые проблемы, которые относительно несложно исправить:

1. Если атакующий Бот за стеной, то опасности он не представляет. Не помешало бы учитывать стены при построении Карты Опасности. Сам алгоритм ИИИ при этом менять не придется;
2. Если защищающийся Бот глубоко попал в опасную зону, то двигаться нужно от эпицентра опасности, а не к нему или вдоль него. Убегающие Боты должны отталкиваться от атакующих, как магниты одноименными полюсами. Изменения затрагивают только ИИИ;
3. Чтобы получить более точные оценки, Карту Опасности лучше строить не по сетке, а по четким окружностям (с координатами в условных точках). Для перехода к подобной схеме требуются достаточно кардинальные изменения, как в ИИИ, так и в алгоритме построения карты;
4. Алгоритм поиска пути может уйти в бесконечную погоню (и делает это намного чаще, чем хотелось бы). Он зажмет убегающего Бота в угол. И будет ходить из стороны в сторону, не приближаясь к нему. Это связано с тем, что минимальный путь не уникален. Его можно построить разными способами. Все зависит от порядка обхода. Сейчас приоритет выше у движения по горизонтали. Исправить эту проблему не так сложно. Достаточно выполнять обход допустимых направлений на основе относительного положения цели.

Заключение

В качестве темы следующей статьи у меня есть несколько вариантов:

1. Заняться улучшениями и исправить указанные недостатки;
2. Доработать GUI, чтобы приложение стало полноценным конструктором, в котором можно динамически менять размеры игрового мира, ставить стены, просматривать вспомогательную информацию, добавлять Ботов и т.д.;
3. Рассмотреть какую-то новую задачу, которую мы еще не затрагивали.

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

Похожие публикации