Как Pizza Tycoon симулировала трафик на 25 МГц процессоре в 1994 году

Если ваша симуляция десятка сущностей на экране уже уехала в графы сцены, pathfinding и полноценный collision detection — возможно, вы решаете не ту задачу. FinnKuhn 14 лет писал систему движения машин для DOS-игры 1994 года Pizza Tycoon — и каждый раз упирался в переусложнённую архитектуру. Пока не прочитал оригинальный ассемблер и не увидел: направление движения там зашито прямо в тип тайла дороги, а машинам вообще не нужно ничего планировать. Ниже — его рассказ о том, как это крутится на Intel 386 25 МГц.

Мы перевели статью FinnKuhn. Далее — от первого лица.

Контекст

Я работаю над Pizza Legacy — опенсорсной реимплементацией DOS-игры 1994 года Pizza Tycoon. В игре есть режим крупного плана: когда прокручиваешь карту, видишь постоянный поток машин на улицах. Одновременно — штук двадцать-тридцать маленьких спрайтов, но они ездят по сетке улиц, выстраиваются в очередь на перекрёстках и в целом создают ощущение живого города. Иногда они проезжали сквозь друг друга — был такой баг, — но этого хватало, чтобы карта выглядела населённой. И всё это крутилось на 386-м процессоре на 25 МГц.

Режим крупного плана города в Pizza Tycoon: машины двигаются по сетке улиц.

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

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

И всё это время в голове сидела одна мысль: оригинальный Pizza Tycoon крутил эту симуляцию на 25 МГц. Почему у меня реализации всегда получались такими сложными?

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

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

Как устроены города

Сначала посмотрим, из чего вообще состоит город. Видно двухполосные дороги, T-перекрёстки, четырёхсторонние перекрёстки и углы. Карты в Pizza Tycoon — это сетка 160×120 тайлов, где каждый тайл берётся из файла landsym.vga.

Оригинальный landsym.vga с добавленными границами между тайлами и координатами столбца и строки.

Дорожная система

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

Тайл 0x16 — это нижняя часть горизонтальной дороги, то есть машины здесь могут ехать только слева направо. Соответственно, 0x06 — справа налево, а 0x26 и 0x36 — то же самое, но для вертикального движения.

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

С углами та же история. 0x56 (CORNER_SW в моём enum) — это угол, на котором машина может либо ехать дальше на запад, либо повернуть на юг. Когда машина доезжает до угла, она подбрасывает монетку: 50% — едет прямо, 50% — поворачивает. Карты спроектированы так, чтобы дорожная сеть всегда оставалась согласованной: рядом с CORNER_SW обязательно стоит либо тайл с движением с юга на север (то есть машине придётся свернуть на юг), либо ещё один угловой тайл, который тоже допускает и поворот, и проезд прямо.

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

Допустимые направления движения для разных типов тайлов, показаны стрелками.

Движение: один пиксель за такт

Машины двигаются на один пиксель за такт игрового цикла. На каждом такте главный цикл проверяет, не заблокирована ли машина, и если нет — прибавляет или вычитает один пиксель у её экранной координаты в зависимости от направления. Восток: +1 к X. Север: −1 к Y. Никакой векторной математики.

Есть второй счётчик — progress, который идёт от 16 к 1. Когда он доходит до нуля — сбрасывается в 16, и игра запускает тайловую логику: смотрит, какой там следующий тайл, решает новое направление, обновляет кадр спрайта (чтобы визуально развернуть машину в новую сторону).

Поскольку каждый тайл имеет размер 16×16 пикселей, тайловая логика срабатывает ровно один раз на пересечение тайла. Движение на один пиксель — каждый такт, тяжёлая тайловая логика — только в 1 из 16 тактов.

Когда машина только спавнится, progress устанавливается в случайное значение от 1 до 16. Это разносит проверки границ тайлов между разными тактами, так что нагрузка размазывается равномерно — примерно 25 машин не упираются в тайловую логику одновременно.

Обнаружение столкновений: дешёвый O(n²)

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

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

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

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

Спавн машин

Когда игрок входит в режим крупного плана, игра сканирует все 132 тайла видимой области (12 столбцов × 11 строк) и для каждого дорожного тайла кидает кубик против плотности трафика района, чтобы решить, спавнить ли там машину. Районы с высокой плотностью получаются загруженнее, с низкой — пустыми. Угловые тайлы из точек спавна исключены: машины появляются только на прямых участках.

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

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

Почему это работает

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

• Машинам не нужен поиск пути — карта сама говорит им, куда можно ехать.
• Обнаружение столкновений дешёвое, потому что ранний выход по направлению делает большинство пар практически бесплатными.
• Нет скорости и физики — один пиксель за такт выглядит достаточно убедительно.
• Если врезался — просто подожди 10 тактов. А если надо повернуть — просто проехал половину тайла и повернул. Работает на любом тайле в любом направлении.

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

Я переписал систему довольно близко к ассемблеру оригинала — по сути, пара switch-блоков с разными вариантами маршрутизации в зависимости от типа тайла. Код можно посмотреть в методе decide_desired_direction в Car.cpp репозитория проекта.

Источник: «How Pizza Tycoon simulated traffic on a 25 MHz CPU» — блог Pizza Legacy. Публикуется с разрешения автора в рамках открытого проекта.