Предыдущие части:
В прошлый раз мы остановились на том, что научили Ботов более или менее естественно перемещаться по игровому миру. Однако их перемещение абсолютно бесцельно.
Целей у игрового искусственного интеллекта может быть много, но одна из наиболее распространенных (которая не редко является подцелью более сложных целей) - поиск пути для перемещения Бота в заданную точку игрового мира. Решением именно этой проблемы мы и займемся.
Не забудьте получить актуальную версию проекта AISimulator. Либо скачайте архив, либо сделайте pull из git-репозитория.
Основные отличия:
QRect;Поверхностно пройдемся по побочным изменениям.
Добавляемая Цель (зеленый квадрат) на уровне Модели представляет собой просто другой тип Бота. Это сделано в расчете на будущее, когда мы займемся "убегающим" ИИИ. А пока что эти Боты-цели не двигаются.
Само добавление Цели реализовано через обработчик события mousePressEvent() в Представлении:
void AISimulatorView::mousePressEvent( QMouseEvent* e ) {
if( e->button() != Qt::LeftButton ) {
QWidget::mousePressEvent( e );
return;
}
int x = AIModel::blocksToPoints(
e->pos().x() / PIXELS_IN_MODEL_POINT / AIModel::BLOCK_SIZE
) + AIModel::HALF_BLOCK_SIZE;
int y = AIModel::blocksToPoints(
e->pos().y() / PIXELS_IN_MODEL_POINT / AIModel::BLOCK_SIZE
) + AIModel::HALF_BLOCK_SIZE;
m_model->addBot( x, y, 3 );
repaint();
}
Координаты Бота-цели определяются исходя из разметки игрового поля по сетке. То есть Бот добавляется не точно в указанную точку, а в центр соответствующего блока.
Обработчик столкновений между Ботами нужен, чтобы убирать достигнутые Цели из игрового мира. Как только "боевой" Бот (желтый) сталкивается с Ботом-целью (зеленый), последний "умирает". Реализовано все это по тому же принципу, как и с классом BotAI, то есть на основе паттерна Стратегия:
class CollisionResolver {
public:
virtual ~CollisionResolver();
virtual void resolve( const AIModel& model, Bot* b1, Bot* b2 );
};
void CollisionResolver::resolve( const AIModel&, Bot* b1, Bot* b2 ) {
if( b1->getType() != b2->getType() ) {
if( b1->getType() == 3 ) {
b1->die();
} else {
b2->die();
}
}
}
Обработка получилась довольно примитивной, и при добавлении новых типов Ботов будет работать неправильно, но наши текущие задачи она решает, поэтому оставляем так, как есть.
Следует заметить, что у Бота добавилась операция die(). Эта операция сама по себе почти ничего не делает. Бот всего лишь помечается "умершим", а за очистку игрового поля от мертвых Ботов отвечает Модель:
QSet< QPair< std::shared_ptr< Bot >, std::shared_ptr< Bot > > > resolved;
if( m_resolver ) {
for( auto b1 : m_bots ) {
for( auto b2 : m_bots ) {
auto pair = qMakePair( b1, b2 );
if( resolved.contains( pair ) ) {
continue;
}
if( b1->hasCollisions( *b2 ) ) {
m_resolver->resolve( *this, b1.get(), b2.get() );
resolved << pair;
}
}
}
auto it = m_bots.begin();
while( it != m_bots.end() ) {
if( it.value()->isDead() ) {
it = m_bots.erase( it );
} else {
++it;
}
}
}
Итак, у нас в распоряжении Бот и координаты точки (не ограничиваемся перемещением до Бота-цели). Нужно найти последовательность направлений Бота, которая приведет его в эту точку:
std::vector< Bot::Direction > findPath( const Bot& bot, int x, int y ) const;
Задача понятна. Как подойти к ее решению? Можно попробовать компоновать путь из такой последовательности направлений, которая с каждым шагом приближает Бот к Цели. Звучит логично. Чем ближе мы к Цели - тем лучше. Но, к сожалению, этот алгоритм работает неправильно.
На скриншоте слева видно, что если Бот попытается идти навстречу Цели, то он просто упрется в стену (путь номер 1). Правильный путь (номер 2) лежит в обход.
И как же найти правильный путь? Для этого мы воспользуемся алгоритмом поиска в ширину. Конечно, для поиска пути можно использовать и поиск в глубину (его мы использовали при решении судоку), но нам нужен кратчайший маршрут, поэтому такой подход отпадает.
Идея поиска в ширину заключается в следующем:
Внимательно изучите соседний рисунок. На нем схематично представлена логика работы алгоритма поиска в ширину для первых трех итераций.
Обратите внимание на характер обхода. На каждой итерации мы получаем квадрат все с большей и большей длинной стороны. Этим квадратом гарантировано будет охвачено все игровое поле, поэтому Боту-цели от нас не скрыться.
Поскольку за каждую итерацию мы добавляем всего один "слой" в область охвата, то можно гарантировать, что других более близких путей не существует. Однако могут существовать другие равнозначные пути той же длины. Все зависит от порядка обхода (в примере принят обход по часовой стрелке).
Например, если искомая точка - 21, то путь легко построить по стрелкам: 1-3-10-21. А если точка - 14, то путь: 1-2-6-14. Следует заметить, что мы будем строить путь задом наперед: от искомой точки до начальной.
На самом деле, в нашем тестовом приложении все будет несколько сложнее. Ведь присутствуют стенки, которые могут блокировать Бота, но и заставить его сдвинуться на расстояние, которое окажется меньше обычного. Однако алгоритм поиска в ширину решает и эти задачи в довесок, без особого вмешательства с нашей стороны.
Осталось только записать все это на C++:
std::vector< Bot::Direction > AIModel::findPath( const Bot& bot, int x, int y ) const {
// Посещенные точки будем сохранять в множестве
QSet< QPoint > visitedPoints;
visitedPoints << QPoint( bot.getX(), bot.getY() );
// Эта структура поможет при построении дерева обхода
// Она хранит состояние Бота и указатель на предыдущий узел (точку графа)
struct Node {
Node( const Bot& b, std::shared_ptr< Node > p = nullptr ) :
bot( b ), prev( p ) { }
Bot bot;
std::shared_ptr< Node > prev;
};
// Алгоритм поиска в ширину строится на основе очереди
QQueue< std::shared_ptr< Node > > q;
q << std::make_shared< Node >( bot );
while( !q.isEmpty() ) {
// Забираем из очереди узел, относительно которого будем пытаться двигаться
std::shared_ptr< Node > node = q.dequeue();
// Для всех возможных направлений
for( int i = 0; i < Bot::DIRECTION_COUNT; ++i ) {
// Пробуем сделать шаг
Bot::Direction d = Bot::Direction( i );
Bot bCopy = node->bot;
bCopy.setDirection( d );
bCopy.startMoving();
bCopy = doMove( bCopy );
// Смотрим на координату точки, в которой оказался Бот
QPoint p( bCopy.getX(), bCopy.getY() );
if( p.x() == x && p.y() == y ) {
// Если путь найден, то есть попали в искомую точку
std::vector< Bot::Direction > path;
// Заносим в результат направление, которое привело нас сюда на последней итерации
path.push_back( d );
std::shared_ptr< Node > n = node;
// Проходим по всему дереву в обратном порядке, кроме самого первого узла, который просто
// указывал на точку отсчета
while( n->prev ) {
// Заносим направления в маршрут
path.push_back( n->bot.getDirection() );
n = n->prev;
}
// Путь составлен в обратном порядке, поэтому переворачиваем его
std::reverse( path.begin(), path.end() );
return path;
}
if( !visitedPoints.contains( p ) ) {
// Если точка еще не была посещена, то заносим ее в список посещенных
visitedPoints << p;
// А затем создаем и добавляем в очередь узел для состояния, которое привело нас в эту точку
// Обратите внимание на то, что мы привязываем к этому узлу предыдущий
q << std::make_shared< Node >( bCopy, node );
}
}
}
// Если путь найти не удалось, то возвращаем пустой маршрут
return std::vector< Bot::Direction >();
}
Самое сложное позади. Теперь реализуем ИИИ, которые смогут воспользоваться этой функцией.
Итак. В простейшем случае Бот может просто двигаться к последней появившейся Цели:
void PathFinderAI::doStep( const AIModel& model, Bot* bot ) {
auto targets = model.getBots( 3 );
if( targets.isEmpty() ) {
// Если Целей нет, то останавливаем Бота
bot->stopMoving();
return;
}
auto target = targets.first();
auto path = model.findPath( *bot, target->getX(), target->getY() );
if( path.empty() ) {
bot->stopMoving();
return;
}
bot->startMoving();
bot->setDirection( path.front() );
}
Если вы попробуете испытать этот алгоритм, то увидите, что со временем все Боты собираются в одного большого, и начинают двигаться практически по одной и той же траектории. Суммарная эффективность "убивания" Целей при этом снижается.
Чуть более эффективный алгоритм ИИИ может отправлять Бота не за последней появившейся Целью, а за ближайшей к нему. Чтобы получить точную оценку расстояния, мы могли бы сравнивать длину реальных путей до различных Целей. Но при большом количестве Ботов такой расчет начнет существенно тормозить работу.
С другой стороны, можно модернизировать алгоритм поиска пути. Траектории движения Ботов часто пересекаются. Поэтому нет особо смысла пересчитывать маршрут, который уже был найден до этого.
Однако мы поступим проще. Будем считать расстояние по формуле. Без учета стенок (как изначально собирались строить алгоритм поиска пути). Конечно, оно не всегда правильное, но в большинстве случаев обеспечивает приемлемый результат:
void SmartPathFinderAI::doStep( const AIModel& model, Bot* bot ) {
auto targets = model.getBots( 3 );
if( targets.isEmpty() ) {
bot->stopMoving();
return;
}
auto target = *std::min_element(
targets.begin(),
targets.end(),
[ &bot ]( const std::shared_ptr< Bot >& b1, const std::shared_ptr< Bot >& b2 ) {
return bot->squareDistanceTo( *b1 ) < bot->squareDistanceTo( *b2 );
}
);
auto path = model.findPath( *bot, target->getX(), target->getY() );
if( path.empty() ) {
bot->stopMoving();
return;
}
bot->startMoving();
bot->setDirection( path.front() );
}
Если Цели будут появляться достаточно часто и в различных местах игрового мира, то эффективность этого ИИИ оказывается неплохой. Но если Цели появляются по одной, то его поведение полностью совпадает с поведением предыдущего варианта.
Если мы и правда хотим добиться максимальной эффективности при решении этой задачи (быстрое убивание Целей), то неплохим вариантом может стать добавление логики "патрулирования" или "деления территории". В первом случае Боты при отсутствии Целей будут равномерно гулять по игровому полю, чтобы суметь оперативно среагировать на новую "жертву". Неплохо с этим может справиться наш ИИИ SmartSingleMemRandomAI, с которым мы разобрались в прошлый раз. Второй вариант заключается в том, чтобы привязать каждого Бота к некоторой территории. В этом случае Бот будет атаковать лишь те Цели, которые попали на его территорию. Например, территории можно разбить по квадратам, хотя это не всегда окажется оптимальным (все зависит от рельефа игрового мира). Если заинтересовались, то попробуйте реализовать эти алгоритмы самостоятельно.
На этом мы заканчиваем знакомство с ИИИ поиска пути (а также алгоритмом поиска в ширину). Боты-охотники готовы, но Боты-цели ведут себя скучно (они не двигаются). В следующий раз мы исправим это и реализуем "убегающий" ИИИ…
Неплохо!
owl
Спасибо