Алгоритм, управляющий движением целого города — как работает ИИ дорожной системы в Cities: Skylines

Каждый автомобиль прогнозирует потенциальные аварийные ситуации и делает всё возможное, чтобы их избежать.

Блогер Томми Томпсон, специализирующийся на теме ИИ в играх, опубликовал на своём сайте текст, в котором рассказал о принципах, лежащих в основе системы дорожного движения в Cities: Skylines. Мы выбрали из материала главное.

Часто в играх искусственный интеллект контролирует не самые очевидные вещи. Например, в Cities: Skylines вся транспортная и навигационная система строится на основе ИИ.

У основного конкурента Cities: Skylines, SimCity, на момент релиза наблюдались большие проблемы с передвижением персонажей по городу. На улицах были постоянные пробки, а жители города вели себя не так, как ожидалось — у них не было индивидуальности, поэтому они ходили на ближайшую работу, а затем возвращались не в тот дом, из которого вышли утром. Со временем разработчики постарались решить эти проблемы в патчах, но далеко не все игроки остались довольны результатом.

В Cities: Skylines эти проблемы по большей части решены, хотя и там можно иногда встретить пробки. Тем не менее все горожане занимаются своими делами, как этого можно было ожидать. Каждый персонаж в Cities: Skylines содержит информацию, которая используется в процессе городского моделирования. Эти данные включают в себя:

Каждая из этих характеристик имеет своё значение. Уровень образования влияет на то, какой работой заняты персонажи, определяет производительность предприятий и ценность жилых районов. А счастье связано с тем, насколько хорошо работают жители.

На перемещение персонажей больше всего влияет их возраст:

Все эти персонажи по-разному пользуются транспортной структурой. Одни горожане используют личный транспорт, а другие передвигаются на общественном. Город постоянно растёт и меняется, а жители стареют: средняя продолжительность их жизни — шесть внутриигровых лет. Всё это важно сбалансировать, чтобы система работала правильно.

Каждый сегмент дороги хранит информацию о себе: что это за дорога, сколько у неё полос движения и в какую сторону. Сегменты работают благодаря узлам — они помогают системе понять, где находится начало и конец движения на отдельном сегменте.

Эта информация распространяется и на тротуары, которые работают примерно так же. Но они могут быть подняты, опущены, находиться в туннелях, а также пересекать дорогу. Вся эта информация используется, когда горожанин принимает решение пойти куда-либо.

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

Когда персонаж решает, что ему нужно отправиться в путь, он использует всю доступную информацию о транспортной инфраструктуре города, включая: дороги, тротуары, перекрёстки, маршруты общественного транспорта и доступные транспортные средства. Он анализирует систему узлов внутри дорог и тротуаров, чтобы найти самый быстрый маршрут к точке назначения

Если горожанин владеет автомобилем, он будет использовать его. В ином случае он проверит тротуары и расписание общественного транспорта. Эта система позволяет персонажу менять способ передвижения прямо в процессе — он может идти пешком, а затем сесть на общественный транспорт. Пункты назначения могут быть разными — кроме школы и работы горожане могут посещать больницы, магазины, рестораны и другие заведения.

Но существуют и некоторые специальные средства передвижения. Например, пожарный не поедет с ведром воды на общественном автобусе — он вместе с командой доберётся до пожара на специальной машине. Это же касается и докторов.

Также есть строгие ограничения на передвижение. К примеру, обычные пешеходы не могут заходить на дорогу. Если до места назначения нет тротуаров и общественного транспорта, то персонаж просто не сможет туда попасть. Разработчики никогда не упоминали, какой алгоритм применяется для поиска пути, но автор предполагает, что это модифицированная версия A* или алгоритма Дейкстры.

Когда персонаж передвигается на автомобиле, он учитывает не только топологию дорожной сети, но и её дополнительные свойства — выделенные велосипедные или автобусные полосы, ограничение скорости, количество полос и текущий уровень загруженности. Система генерирует путь, а автомобиль использует его для движения. Персонаж также может пересаживаться на общественный транспорт.

Чтобы система работала корректно, в Cities: Skylines есть жёсткое ограничение на количество горожан и транспорта на улицах города. Существует отдельная система, которая отслеживает, есть ли свободные места для передвижения. Если есть, то она разрешает персонажам передвигаться.

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

С помощью этой симуляции прогнозируется движение транспорта, благодаря чему не происходит аварий — машины снижают скорость, если это нужно. Это особенно актуально на перекрёстках и в узких местах. Также весь транспорт распознаёт цвет светофоров.

Чтобы свести к минимуму аварии, машины во время симуляции проверяют вероятность столкновения — так они выявляют аварийно-опасный участок дороги. Чтобы определить, какой автомобиль поедет первым, сравнивается расстояние до опасного участка. Остальной транспорт движется в порядке очереди, адаптируя свою скорость.

Несмотря на все эти усилия, проблемы с пробками всё ещё существуют. Есть несколько причин, из-за которых это происходит.

Часто случается так, что во время движения в городе что-то меняется, из-за чего путь становится неверным. Другая причина — невозможность перестроиться из одной полосы на другую несколько раз подряд. Разработчики экспериментировали с этой возможностью, но она провоцировала ещё больше проблем.

Ещё одна причина заключается в том, что некоторые автомобили заранее прогнозируют проблемы на дороге, из-за чего просто стоят на дороге до тех пор, пока всё не разрешится. Если же автомобиль оказался в безвыходном положении, он телепортируется в начало пути.

#ии #геймдизайн