Хочу поделиться с читателем тем, как работают алгоритмы, управляющие соперниками в моей аркадной гоночной игре beaterCore.
Проблема ИИ в гонках
Цель объединяющая ИИ-агентов в большинстве игр: Найти маршрут от одной точки до другой.
Неважно, рогалик это или шутер, оптимальный маршрут всегда один – тот что с наименьшей дистанцией. В некоторых случаях алгоритм поиска пути модифицируют так, чтобы бот шёл по более “естественным маршрутам”, например, обходя опасные для него места стороной, но суть от этого не меняется.
А вот для гонок оптимальный маршрут – тот, что занимает меньше всего времени. И если учесть, что физические свойства покрышек просто не позволяют машине поворачивать на 90 градусов за 1 секунду, а также необходимость автомобиля сбрасывать скорость перед поворотами, и конечно же, время, которое автомобиль тратит на то, чтобы набрать эту скорость назад – самый короткий маршрут уже перестаёт быть оптимальным.
Как искать самый быстрый маршрут
Просто! При поиске пути в качестве стоимости отрезка используем время пути вместо расстояния. Как понять сколько времени автомобиль потратит на прохождение отрезка? Тоже просто, из школьных уроков физики вспоминаем, что время прохождения участка пути составляет:
Где L – длина участка, а v – скорость.
Длину отрезка мы знаем, а скорость… Задача становится сложнее.
Для начала вспомним, что автомобилю нужно время на ускорение. Соответственно текущую скорость нужно будет хранить на каждом шагу алгоритма. Скорость набирается за счет ускорения, а ускорение можно считать за константу – например 5 м/с². Еще скорость стоит ограничить, ведь автомобиль не способен ускоряться до бесконечности.
Теперь нужно определиться, что является причиной, по которой автомобиль сбрасывает скорость. Самая очевидная – радиус поворота. Для его определения в своей игре я использую три предыдущие точки построенного маршрута – чем более резкие переходы между ними, тем меньше радиус и тем ниже скорость.
Зная радиус поворота на сегменте, можно определить максимальную скорость автомобиля на нем. Простая формула для этого:
Где k – коэффициент трения покрышки с поверхностью
Теперь автомобиль набирает скорость на прямых и теряет её на поворотах. Если использовать найденное время пути как стоимость прохождения сегмента, то получится маршрут уже напоминающий траектории, по которым движутся гоночные автомобили
Построение вершин для маршрута
Алгоритм требует набора вершин, между которыми он будет строить маршрут. В первых прототипах я создавал одну вершину на каждый метр ландшафта карты. Но чем больше вершин, тем больше компьютеру необходимо времени на построение маршрута. А ведь машинам нужно обгонять соперников и уворачиваться от них же, адаптироваться под смену обстановки и отклонения от траектории, так что желательно, чтобы на построение маршрута уходило не больше 100 мс.
В итоге пришёл к тому, чтобы создавать наброски маршрутов самостоятельно в специальном редакторе. Вершины строятся из этого наброска по десять вершин в ширину.
Полученные точки также стоит отфильтровать, то есть убрать все места, через которые автомобиль не способен проехать. Для этого каждая вершина смотрит на своих соседей и определяет максимальную разницу в высоте с ними. Если эта величина превышает порог, – вершина удаляется.
Скорость и тормозной путь
Я уже упомянул, как алгоритм поиска пути ищет максимальную скорость на каждом сегменте маршрута. Но машине еще нужно проехать по этому маршруту, и при этом учитывать свою тормозную дистанцию.
Для этого машина смотрит свой маршрут наперед и определяет максимально допустимую скорость предстоящих поворотов. Чем быстрее едет автомобиль – тем больше дистанция, на которой идёт проверка.
Смотрим на ландшафт
Моя игра во многом про бездорожье. Ранее мы фильтровали вершины, через которые совсем нельзя проехать. Теперь проделаем похожую операцию, только вместо удаления вершин будем модифицировать скорость на неровных участках дороги, а также участках с наклоном. Алгоритм следующий
-
Делим отрезок пути на точки которые высоту которых возможно измерить на ландшафте
-
Для каждой точки берем 2 дополнительных измерения: слева и справа от направления отрезка
-
Разницу между двумя измерениями можно считать за угол наклона
-
А за “неровность” – максимальное отклонение в высоте между всеми точками на отрезке
Эти параметры затем можно использовать как модификатор скорости, а также в алгоритме поиска пути, чтобы автомобиль избегал неровных дорог.
Делаем соперников быстрее
Алгоритмы, указанные выше, строят неплохой маршрут, но с ограниченным количеством данных им приходится оставаться достаточно консервативными. Я очень долго старался подбирать параметры и добавлять всё больше данных в алгоритм, чтобы улучшить время прохождения кругов, но алгоритмы никак не могли сравниться даже с новичками, редко играющими в гонки.
Проблему решил я спорно. Так как у меня уже был редактор маршрутов, я просто добавил функционал “подбадривать” соперников на определённых сегментах. Если компьютер слишком медленно проезжает поворот и его можно без рисков проехать быстрее, я просто выставляю, что скорость на этом участке может быть на 70% выше вручную.
В будущем можно придумать алгоритм, на основе которого соперники сами бы определяли, какие повороты можно проехать быстрее, а каких стоит остерегаться, методом проб и ошибок. Но руки до этого пока не доходили, мне было проще выставлять модификаторы скорости вручную.
Оптимизация
Маршрут можно искать ч��рез всю трассу, так он гарантированно будет самым быстрым. Но чем больше вершин в маршруте, тем дольше его вычислять. А я уже упомянул про ограничение в 100 мс для времени поиска пути.
К счастью, в игре есть контрольные точки, так что компьютеру нужно найти маршрут лишь только до двух следующих контрольных точек.
Почему двух, а не одной? Если использовать одну – компьютер будет игнорировать все что находится за контрольной точкой, поэтому спокойно поедет 100 км/ч в тупик, даже не думая о тормозах
Эпилог
Я не стал описывать свою реализацию алгоритма А* – во многом потому, что она у меня плохая. Статей в интернете на эту тему огромное множество и описывать его лишний раз я толка не вижу. Я надеюсь, что информация, которую я описал в этой статье, поможет другим игроделам в разработке своих ИИ-соперников.
Несмотря на простоту решений, описанных в этой статье, мне лично пришлось доходить до них несколько месяцев методом проб и ошибок
Автор: the_hellbox
