Хитрый виртуальный город: как в Cities Skylines работает ИИ горожан

На самом деле на улицах города находятся не все его жители.

Вышедший в 2015 году Cities Skylines остается одним из наиболее удачных градостроительных симуляторов последних лет. Разработчикам из Colossal Order удалось более-менее достоверно воссоздать устройство современных мегаполисов.

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

Доктор Томми Томпсон, исследователь искусственного интеллекта, считает симуляцию Cities Skylines очень удачной. В колонке на Gamasutra Томпсон рассказывает, как устроен ИИ горожан в Cities Skylines и чем он отличается от предыдущих игр жанра.

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

Что не так с SimCity

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

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

Как в Cities Skylines устроены горожане

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

Кроме того, хотя игроки этого не видят, у персонажей есть возраст. Всего игра выделяет пять возрастных групп, от детей до пенсионеров; персонажи игры умеют взрослеть и переходить из одной группы в другую. На полный цикл уходит около 6 игровых лет.

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

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

Как в Cities Skylines работают дороги

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

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

Как персонажи движутся из точки А в точку Б

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

К примеру, персонажи не могут ходить по дорогам пешком, а в некоторых случаях — допусти, когда пожарные или медики едут на вызов — им нужно пользоваться только определенными транспортными средствами.

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

Как игра оптимизирует нагрузку

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

В есть есть система, постоянно отслеживающая наличие «свободных мест» в общественном транспорте, на дорогах и улицах. Если мест нет, то персонаж никуда не отправится, но игрок из-за этого не пострадает: экономика и другие системы будут работать нормально.

Как работает транспорт

За моделирование транспортных средств отвечает отдельная система. Она отвечает за то, чтобы машины ехали по выбранному пути, не врезались друг в друга и поддерживали правильную скорость. Система обсчитывает поведение транспорта только 4 раза в секунду, для определения скорости движения рендер использует аппроксимацию.

Чтобы транспортные средства аккуратно проходили повороты, используется стандартная карта наборов дорожных узлов. В ней есть информация о перекрестках — на ее базе игровой движок строит сплайны, по которым движутся автомобили.

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

Мелкие хитрости

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

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

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

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