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

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

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

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

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

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

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

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

  • имя;
  • образование;
  • адрес проживания;
  • место работы или учёбы;
  • уровень счастья;
  • текущая активность;
  • здоровье;
  • богатство;
  • семья.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

7878
35 комментариев

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

25
Ответить

Недавно была статья, вроде как раз на ДТФ, где разраб глупость ИИ объяснял невозможностью реализации полноценного ИИ в многотысячеом городе без превращения средней пекарни в доменную печь.

4
Ответить

Адепты глупого ИИ подъехали. Выбирают всегда самый быстрый путь, проблема ИИ в том, что при этом он не учитывает пробки. 
Скоростные трассы работают - жители всегда стремятся ехать по ним. 

ЗЫ. Создал город на 920 тысяч человек без модов на траффик. Средняя скорость 88-91%, пробок нет вообще.

1
Ответить

ты неправ

Ответить

Убил кучу часов в этой великолепной игре. Единственное что не понимаю до сих пор - это вырвиглазные цвета машин и зданий. Благо, все решается модами

19
Ответить

Про аварии автор поста что-то нафантазировал.
Жители и машины спокойно проходят сквозь друг друга. Аварии невозможны.
Машинам плевать на переезд пешеходов, но да, красоты ради они избегаю столкновений друг с другом.

11
Ответить

А ещё если застроить аэропорт со всех сторон высотками - самолёт будет пролетать сквозь них. Машины преспокойной ездят сквозь друг друга. И это хорошо, вот ещё аварий не хватало ко всем этим наводнениям, больным жителям, перебоям с водой, просадкам бюджета, нехватке зон, медленным мусоровозкам и т.д))

2
Ответить