Предыдущие части:
Чтобы получить исходники обновленного тестового приложения, вы можете скачать архив с github, или взять их из git-репозитория (тег v1.1).
Отличия от предыдущей версии:
std::unique_ptr используется std::shared_ptr;reset(), предназначенная для сброса состояния. Она требуется в тех случаях, когда ИИИ имеет внутреннюю память;Более подробно о всех изменениях вы можете узнать из комментариев в git-репозитории.
Наиболее интересным изменением здесь является возможность регистрации и выбора алгоритмов ИИИ. Эти функции реализованы в главном виджете (оборачивающем Представление):
void MainWidget::registerAI( const QString& name, BotAI* ai ) {
if( m_aiCmb ) {
// Если комбо-бокс инициализирован
// Добавляем в него название ИИИ
m_aiCmb->addItem( name );
// И сохраняем сам объект ИИИ
m_ais.push_back( std::shared_ptr< BotAI >( ai ) );
}
if( m_ais.size() == 1 ) {
// Если добавлен первый ИИИ, то активируем его
onAIChanged( 0 );
}
}
// Этот слот привязан к сигналу currentIndexChanged() комбо-бокса m_aiCmb
void MainWidget::onAIChanged( int i ) {
if( 0 <= i && static_cast< size_t >( i ) < m_ais.size() ) {
// Устанавливаем i-ый зарегистрированный ИИИ
m_model.setAI( m_ais[ i ] );
}
}
Тогда инициализация ИИИ в main() выглядит так:
int main( int argc, char* argv[] ) {
QApplication a( argc, argv );
MainWidget w;
w.registerAI( "EasyRandomAI", new EasyRandomAI );
w.registerAI( "SmartRandomAI", new SmartRandomAI );
w.registerAI( "SingleMemRandomAI", new SingleMemRandomAI );
w.registerAI( "AccumulatingRandomAI", new AccumulatingRandomAI );
w.registerAI( "SmartSingleMemRandomAI", new SmartSingleMemRandomAI );
w.show();
return a.exec();
}
Из этих ИИИ нам пока что знаком только первый - EasyRandomAI, который мы создали в прошлый раз. Теперь разберемся с остальными.
Визуально EasyRandomAI вел себя уж слишком примитивно. Сделаем его "умную" версию, запретив биться об стену. Для этого добавим в Модель функцию, которая находит допустимые направления (не в стену):
std::vector< Bot::Direction > AIModel::findValidDirections( const Bot& bot ) const {
std::vector< Bot::Direction > directions;
for( int i = 0; i < Bot::DIRECTION_COUNT; ++i ) {
// Для каждого направления (вверх, вниз, влево, вправо)
// Делаем копию Бота
Bot botCopy = bot;
// Устанавливаем его направление
Bot::Direction d = Bot::Direction( i );
botCopy.setDirection( d );
// Пробуем сдвинуть Бота на одну точку в проверяемом направлении
botCopy.move( 1 );
if( !hasCollisions( botCopy ) ) {
// Направление допустимо, если столкновения со стеной не произошло
directions.push_back( d );
}
}
return directions;
}
С такой функцией реализация SmartRandomAI становится тривиальной:
void SmartRandomAI::doStep( const AIModel& model, Bot* bot ) {
auto directions = model.findValidDirections( *bot );
bot->startMoving();
bot->setDirection( directions[ rand() % directions.size() ] );
}
Стоит признать, что такой ИИИ выглядит не очень умно. Но разница в поведении по сравнению с Easy-версией все же заметна. Главное, что мы получили при реализации этого ИИИ, - крайне полезная функция findValidDirections().
Создадим ИИИ, который берет решение не просто с потолка (по рандому), а на основе хоть какого-то анализа своих предыдущих действий. Идея следующая: если на прошлом шаге Бот шел в направлении, которое допустимо и на текущем шаге, то пусть так и идет (ничего не трогаем), иначе выбираем одно из допустимых направлений случайным образом (как в SmartRandomAI). Реализовать такой ИИИ очень просто:
void SingleMemRandomAI::doStep( const AIModel& model, Bot* bot ) {
bot->startMoving();
auto directions = model.findValidDirections( *bot );
if(
std::find(
directions.begin(),
directions.end(),
bot->getDirection()
) == directions.end()
) {
// Меняем направление лишь тогда,
// когда текущего нет в списке допустимых на этом шаге
bot->setDirection( directions[ rand() % directions.size() ] );
}
}
Поведение этого ИИИ интереснее, чем то, что мы рассматривали до этого. Он водит Ботов по линейным траекториям, которые выглядят намного "разумнее", чем неуверенные дерганья его предшественников.
Однако он не лишен недостатков. Основная претензия к этому ИИИ заключается в том, что он уж слишком линейный. Пока Бот во что-то не врежется, он никуда не свернет. Это может привести к появлению замкнутых кругов, как на скриншоте (область, выделенная красным цветом).
Поэтому такой ИИИ не подойдет для случаев, когда игровой мир слишком ровный. Чем больше препятствий, тем интереснее поведение этого алгоритма.
При разработке предыдущего ИИИ мы немного схитрили. На самом деле у него не было своей памяти. Для анализа предшествующего шага он использовал лишь состояние Бота. В этот раз мы пойдем другим путем. Создадим улучшенную версию SmartRandomAI, добавив эффект накопления:
SmartRandomAI);SingleMemRandomAI, однако ИИИ теперь не столь доверчив. Логика достаточно разумна - если обычно слева все хорошо, то скорее всего, и в следующий раз там будет все замечательно, но не факт;Реализовать такой ИИИ можно следующим образом:
static const int MAX_CHANCE = 100;
static const int MIN_CHANCE = 5;
void AccumulatingRandomAI::doStep( const AIModel& model, Bot* bot ) {
bot->startMoving();
if( !m_memory.contains( bot->getID() ) ) {
// Если ИИИ ничего не знает о Боте, то заводим новую ячейку в памяти
// Шанс выбора любого направления один и тот же (25 из 100)
m_memory[ bot->getID() ].resize( Bot::DIRECTION_COUNT, MAX_CHANCE / Bot::DIRECTION_COUNT );
}
auto directions = model.findValidDirections( *bot );
// Нам нужны шансы для допустимых на данном шаге направлений
// chances[ 0 ] = chances[ Bot::LEFT ] - шанс, что Бот пойдет налево
// chances[ 1 ] = chances[ Bot::RIGHT ] - шанс, что Бот пойдет направо
// и т.д.
std::vector< double > chances( Bot::DIRECTION_COUNT, 0 );
for( auto d : directions ) {
// Для каждого допустимого направления добавляем
chances[ d ] = m_memory[ bot->getID() ][ d ];
}
// Выбираем случайное число от нуля до суммарного значения шансов для текущего шага
// Суммарное значение не обязательно будет сотней, поскольку не все направления могут оказаться допустимыми
const int p = rand() % std::accumulate( chances.begin(), chances.end(), 0 );
// Выбираем направление, исходя из распределения вероятностей
// В какую из областей попало случайное число p, туда и идем:
// 0 25 50 75 100
// |== Идем налево ==|== Идем направо ==|== Идем вверх ==|== Идем вниз ==|
// ^ - например, p попало сюда, поэтому идем направо
double sum = 0;
size_t i = 0;
for( ; i < chances.size(); ++i ) {
sum += chances[ i ];
if( p < sum ) {
break;
}
}
const Bot::Direction direction = Bot::Direction( i );
bot->setDirection( direction );
// Перераспределяем шансы для следующего шага
for( int i = 0; i < Bot::DIRECTION_COUNT; ++i ) {
// Для каждого направления
if( i == direction ) {
// Пропускаем выбранное на текущем шаге направление
continue;
}
if( MIN_CHANCE < m_memory[ bot->getID() ][ i ] ) {
// Если шансы по направлению больше минимума (5 в данной реализации), то производим
// перераспределение
m_memory[ bot->getID() ][ i ]--;
m_memory[ bot->getID() ][ direction ]++;
}
}
}
void AccumulatingRandomAI::reset() {
m_memory.clear();
}
Реализация получилась не самой простой, но думаю, что вы без труда в ней разберетесь.
Поведение этого алгоритма не намного лучше, чем у "чисто" случайных. Однако он имеет одну интересную особенность. Этот ИИИ в какой-то мере учится обходить препятствия. Обучение это весьма условное, но оно есть. Обратите внимание на отмеченную траекторию движения на скриншоте выше. Когда ИИИ решил, что Боту нужно идти вверх (шанс движения вверх стал выше, чем у остальных направлений), то он достаточно быстро обходит простые преграды.
Объяснить такое поведение можно следующим образом: основной вектор движения Бота направлен вверх. Вниз он соберется идти не скоро. В одну сторону по горизонтали ему мешает идти стена, поэтому он постепенно "понимает", что имеет смысл попробовать пойти в противоположную сторону (при этом продолжая пытаться идти вверх), попадая в проход. В результате Бот сам находит путь от одного конца лабиринта до другого. Однако у него это не всегда получается.
Такой алгоритм сложно назвать особо полезным. Он довольно неуклюж, поскольку на переползание шансов с одного направления на другое уходит много времени (из-за этого Боты в основном просто бьются об стены). Конечно, можно поэкспериментировать с ним, но добиться приемлемого поведения будет проблематично.
Улучшим алгоритм SingleMemRandomAI - уберем проблему зацикливания. Для этого будем учитывать развилки в лабиринте. Бот не будет просто продолжать следовать в выбранном направлении (если оно остается допустимым), а будет отслеживать появившиеся альтернативы. К развилке будем относить допустимые пути, которые стали таковыми на данном шаге, но не были на предыдущем.
На C++ этот ИИИ реализуется следующим образом:
void SmartSingleMemRandomAI::doStep( const AIModel& model, Bot* bot ) {
bot->startMoving();
auto directions = model.findValidDirections( *bot );
QVector< Bot::Direction > openedDirections;
for( Bot::Direction d : directions ) {
if( !m_memory[ bot->getID() ].contains( d ) ) {
// Если этого направления не было в прошлый раз, то включаем его в развилку
openedDirections << d;
}
}
if( std::find( directions.begin(), directions.end(), bot->getDirection() ) != directions.end() ) {
// Если текущее направление Бота допустимо, то оно тоже входит в развилку
openedDirections << bot->getDirection();
} else {
// Иначе включаем в развилку все допустимые направления
openedDirections.clear()
for( Bot::Direction d : directions ) {
openedDirections << d;
}
}
// Направление на развилке выбирается случайным образом
bot->setDirection( openedDirections[ rand() % openedDirections.size() ] );
// Сохраняем в памяти те пути, которые были допустимы на этом шаге и не будут включены в
// развилку на следующем
m_memory[ bot->getID() ].clear();
// Обратное направление исключается из развилки, чтобы Бот не дергался
// Можете убрать следующую строку и посмотреть, что из этого получится
m_memory[ bot->getID() ] << Bot::reverseDirection( bot->getDirection() );
for( Bot::Direction d : directions ) {
m_memory[ bot->getID() ] << d;
}
}
void SmartSingleMemRandomAI::reset() {
m_memory.clear();
}
Этот ИИИ все равно заставляет Ботов ходить вдоль стен. Но теперь зацикливания не происходит. Боты стали гораздо подвижнее и веселее. Если вам требуется алгоритм, моделирующий внешнюю активность без определенной цели, то из рассмотренных здесь вариантов, этот является наилучшим кандидатом.
Еще более интересного поведения для SmartSingleMemRandomAI можно добиться, если учитывать не только прошлое, но и будущее. Для этого в развилку нужно включать еще и те пути, которые сейчас допустимы, но перестанут быть таковыми на следующем шаге. Можете попробовать реализовать такое улучшение самостоятельно.
Мы разобрали несколько простых алгоритмов ИИИ. Некоторые из них оказались лучше, другие хуже. Однако что значит лучше или хуже? По каким критериям? Я исходил исключительно из здравого смысла, когда делал вывод, что последний ИИИ выглядит привлекательнее, чем остальные.
Но цель для ИИИ у нас все же была. Она заключалась в том, чтобы обеспечить более или менее естественное поведение Ботов. То есть Боты должны:
Таким образом, в дальнейшем мы будем подходить к разработке ИИИ исходя из конкретных целей. В качестве цели для следующей статьи выступит поиск путей в лабиринте…
