Как сделать ИИ для гонок

Пост является, по сути, продолжением статьи Как сделать простой автосимулятор.

Гонки — своего рода священный Грааль геймдева. Любительских гоночных игр исчезающе мало, даже простых и аркадных. А дело в том, что чисто технически «простых» гонок не существует — есть определенный минимум, которому они обязаны соответствовать, чтобы быть играбельными, и достижение этого — очень непростая задача. Если физика, как я уже отмечал в вышеупомянутой статье, не обязана быть чересчур навороченной и допускает довольно широкий разброс реалистичности, то с искусственным интеллектом особой свободы нет — виртуальные соперники обязаны изображать реальных водителей, причем, желательно, хороших. Это задача-минимум, и она же, как ни странно, задача-максимум, потому что игровому боту сильно лучше человека быть не положено.

Не будет преувеличением сказать, что ИИ — это самое сложное в играх. О графике в Интернете говорят очень много, о физике — намного меньше, а об игровом искусственном интеллекте почти не говорят. До этой территории мало кто добирается, а кто добирается — в основном, крупные студии — держат свои ноу-хау в секрете. Поэтому скажу честно: я не знаю, как написаны контроллеры оппонентов в коммерческих гоночных играх, и давно бросил попытки выяснить. Я пошел своим путем.

У классических гонок есть большое преимущество — линейность и детерминированность. Машины должны ехать в одном направлении по заранее известному маршруту. Это позволяет хранить статическую информацию обо всей трассе в памяти и использовать ее для расчетов. Думаю, все гонки хранят трассу в виде последовательности маршрутных точек (waypoint’ов), а затем каким-то образом пускают по этой траектории ботов. Простейший, наивный вариант — просто двигать машину по сплайну, образованному waypoint’ами (можно использовать кубический сплайн, кривую Катмулла-Рома или что-то подобное). Но, поскольку это кинематический подход, он не будет дружить с физикой. Кроме того, придется думать, как реалистично изображать поворот, как избежать «эффекта трамвая», позволяя машине отклоняться от курса, и т.д. В результате простое, на первый взгляд, решение превратится в монстра из костылей. Поэтому я сразу решил отказаться от кинематики и сделать такой алгоритм, который управлял бы машиной тем же способом, что и игрок — рулем и газом, что будет физично и честно. Базово эта задача решается элегантным, хотя и не самым тривиальным в реализации методом.

Алгоритм Pure Pursuit

Алгоритм «чистого преследования» — это популярный в робототехнике метод автоматического следования траектории. Его суть в том, что автомат в каждый момент времени преследует целевую точку на траектории, находящуюся на некотором расстоянии от себя (lookahead distance, Ld). Эта точка всегда впереди и указывает в нужную сторону, как морковка перед осликом.

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

Поиск целевой точки — самая сложная часть алгоритма, потому что сам по себе Pure Pursuit не описывает наиболее эффективный способ делать это. Поскольку трасса у нас хранится в виде последовательности waypoint’ов, в нашем случае задача сводится к перебору отрезков и нахождению их точек пересечения с окружностью радиуса Ld и с машиной в центре. Пересечений может быть много, но нас интересует то, которое находится дальше по маршруту. Для оптимизации я храню индекс ближайшего к машине waypoint’а по направлению маршрута. Это позволяет сильно сократить количество потенциальных пересечений, ведь нас интересует не вся трасса, а только несколько ее сегментов в непосредственной близости от машины.

Мою реализацию алгоритма вы можете найти в репозитории Chillwave Drive.

Как рулить?

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

Кривизна — это радиус дуги, которая соединит текущую позицию машины с целевой точкой:

// Локальный вектор от машины к целевой точке
Vector2f localTarget = targetPoint - car.position;

// Расстояние от машины до целевой точки
float distanceToTarget = localTarget.length;

// Мировой угол вектора к целевой точке
float angleToTarget = atan2(localTarget.x, localTarget.y);

// Мировой угол вектора текущей ориентации машины
float carFacingAngle = atan2(car.direction.x, car.direction.y);

// Угол между ориентацией машины и вектором к целевой точке
float alpha = angleToTarget - carFacingAngle;

// Угол нужно нормировать, чтобы избежать физически невозможной кривизны
while (alpha > PI)  alpha -= 2.0 * PI;
while (alpha < -PI) alpha += 2.0 * PI;

// Вычисляем кривизну
float curvature = (2.0 * sin(alpha)) / distanceToTarget;

Наконец, вычисляем угол руления для передних колес:

float steeringAngle = atan2(curvature * wheelbase, 1.0);

wheelbase — это колесная база автомобиля, расстояние между передней и задней осями.

У меня в движке положение руля задается числом от -1 до 1 (чтобы не привязываться к конкретным пороговым значениям угла), поэтому полученный угол я перенормирую:

float steeringInput = clamp(steeringAngle, -maxSteeringAngle, maxSteeringAngle) / maxSteeringAngle;
steeringInput = clamp(steeringInput * steeringForce, -1.0f, 1.0f);

Коэффициент steeringForce зависит от физики машины, целевой скорости и желаемого характера руления. Я использую около 10.0, но вам, скорее всего, придется подгонять этот параметр под особенности вашей физической модели. Чем выше steeringForce, тем сильнее будет oversteer на поворотах, и, как следствие, может получиться эффектный дрифт. Но для этого обязательно нужно ограничивать скорость в зависимости от кривизны, о чем как раз дальше и пойдет речь.

Как давить на газ?

Тут все проще. Нужно вычислить целевую безопасную скорость для заданной кривизны поворота, а затем скорректировать дроссель пропорционально ошибке скорости — разности текущей скорости и целевой. Моя функция ускорения/торможения позволяет также задать абсолютный максимум скорости, который может быть константой, а может и динамической величиной, зависящей от ситуации. Например, вы можете поделить всю трассу на «опасные» и «безопасные» участки — на опасных вы разрешаете ботам разгоняться, а на опасных снижаете максимальную скорость.

float targetSpeed = maxSpeed;
float absCurvature = abs(curvature);

if (absCurvature > 0.001f)
{
    float safeSpeed = sqrt(maxLateralAcceleration / absCurvature);
    if (safeSpeed < targetSpeed)
        targetSpeed = safeSpeed;
}

// Минимальный порог скорости, чтобы машина не остановилась совсем
if (targetSpeed < 5.0)
    targetSpeed = 5.0;

float speedError = targetSpeed - currentSpeed;

if (speedError > 0.0)
{
    // Если машина едет медленее, чем нужно, ускоряемся
    float throttle = clamp(speedError * accelerationCoef, 0.0f, 1.0f);
}
else
{
    // Если машина едет слишком быстро, тормозим
    float brake = clamp(abs(speedError) * brakingCoef, 0.0f, 1.0f);
}

Скорость задается в метрах в секунду.

maxLateralAcceleration (максимальное боковое ускорение) — интересный параметр, который, вкупе со steeringForce, позволяет контролировать «агрессивность» ИИ на поворотах. При низком значении сброс скорости будет сильнее зависеть от кривизны, что делает поведение бота более осторожным. При высоком значении, напротив, бот будет вести себя «безумнее» и даже может не вписаться в крутой поворот. Этот параметр опять-таки можно сделать динамическим, чтобы тактика зависела от ситуации на дороге. Например, если бот вырвался вперед, ему не нужно рисковать, а если он догоняет, то пытается проходить повороты дрифтом. Из-за некоторой непредсказуемости физики, такое вождение может быть успешным, но иногда приводит к вылету с трассы, что выглядит очень реалистично.

Дополнения

Описанный подход рассчитан на управление в идеальных условиях — когда машина находится на трассе, и перед ней нет препятствий. Если бот вылетел и врезался, нужно временно игнорировать Pure Pursuit и активировать отдельный «режим эвакуации». Если текущая скорость машины меньше порогового минимума в течение определенного промежутка времени, это значит, что движению что-то мешает, и нужно дать назад. Длительность реверса тоже ограничивается таймером, по истечении которого мы возвращаемся в режим Pure Pursuit и пытаемся ехать дальше.

Также можно расширить модель поддержкой динамического уклонения от препятствий, чтобы бот мог обгонять другие машины на трассе — это уже тема для отдельной статьи.