Контекст
Я работал над Pizza Legacy — опенсорсным воссозданием игры 1994 года Pizza Tycoon для DOS. В игре есть вид на улицы города, при скроллинге которого игрок наблюдает постоянный поток машин. Это примерно 20-30 маленьких спрайтов, однако они едут по дорожной сети, создают очереди на перекрёстках и в целом выглядят как оживлённый город. Да, симуляция иногда глючит, машины проезжают друг через друга, но этого достаточно, чтобы придать карте ощущение жизни. И всё это на процессоре 386 с частотой 25 МГц.
Когда я приступил к реализации своего проекта в 2010 году, то первым делом создал этот вид улиц, но мне понадобилось ещё четырнадцать лет, прежде чем машины начали двигаться по нему так, как это меня устраивало; за эти годы я совершил множество попыток, но каждый раз сталкивался с проблемами и заходил в тупик из-за создания переусложнённой системы.
В 2017 году я попробовал сделать так, чтобы каждый тайл отслеживал занятые позиции, а каждая машина запрашивала разрешение, прежде чем двигаться вперёд, резервируя и освобождая слоты в процессе перемещения. По сути, это превратилось в систему блокировок, необходимую для того, чтобы всего лишь перемещать несколько пикселей; машины и тайлы при этом постоянно пытались синхронизироваться.
Всё это время мне не давала покоя одна мысль: если оригинальная Pizza Tycoon работала на процессоре с частотой 25 МГц, то почему мои версии всегда оказывались столь сложными?
Наконец, я решил заняться ассемблерным кодом (на медленное понимание и документирование которого я уже потратил много лет), чтобы разобраться, что же происходит в оригинале; кроме того, я воспользовался помощью LLM, которые на тот момент (пару лет назад) были новой и увлекательной технологией, способной разбираться в ассемблерном коде лучше, чем я.
Теперь, когда я создал полностью работающую систему, мне понятно, в чём я ошибался: я подошёл к решению этой задачи, держа в голове кучу современных концепций: графы сцен, поиск путей, распознавание коллизий и, разумеется, большие ресурсы CPU для выполнения всего этого!
Города
Для начала посмотрим, как выглядят города:
Мы видим двухполосные дороги, T-образные перекрёстки, X-образные перекрёстки и углы. В Pizza Tycoon карты состоят из сетки размером 160 на 120 тайлов, где все тайлы взяты из файла landsym.vga:
0x54 соответствует столбцу 5, строке 4 (тайлу крыши склада).Система дорог
Вернёмся к дорожному движению; самое важное наблюдение, позволяющее этой системе работать на таком медленном CPU: машинам не нужно знать, куда они едут. У каждого типа тайла дороги есть собственное направление. Тайл дороги 0x16 — это нижняя часть горизонтальной дороги, то есть на нём машины могут двигаться только слева направо. Аналогично, тайл дороги 0x06 предназначен только для движения справа налево, а 0x26 и 0x36 — движения по вертикали.
Это значит, что город, по сути, оказывается кучей односторонних дорог: когда машина знает, на каком тайле она находится, она продолжает движение.
Углы работают аналогично: 0x56 (CORNER_SW в моём enum) — это угол, позволяющий машине или продолжить двигаться на запад, или повернуть на юг. Когда машина попадает на угловой тайл, она бросает монетку и с вероятностью 50% продолжит двигаться прямо или сделает поворот. Карты спроектированы таким образом что дороги всегда логичны, то есть рядом с CORNER_SW есть тайл, или обеспечивающий движение на юг, или ещё один крайний тайл, позволяющий или повернуть, или двигаться прямо.
Есть и ещё одно дополнительное правило, позволяющее движению выглядеть естественно: если машина только что совершила поворот влево, то следующий угол заставляет её двигаться прямо; два поворота влево подряд запрещены.
Движение: по одному пикселю на каждый такт игры
Машины могут двигаться по одному пикселю на кадр. На каждом такте основной цикл проверяет, мешает ли машине что-то двигаться, и если нет, он выполняет инкремент или декремент её экранной координаты в зависимости от направления. Движение на восток прибавляет 1 к X. Движение на север вычитает 1 из Y.
В игре есть второй счётчик progress, выполняющий обратный отсчёт с 16. Достигнув нуля, он снова становится равным 16, после чего игра выполняет логику границ тайлов: ищет следующий тайл, выбирает новое направление, обновляет кадр спрайта (чтобы визуально повернуть машину в новом направлении). Так как каждый тайл имеет размер 16 пикселей в высоту и ширину, эта логика выполняется ровно при пересечении каждого тайла. Попиксельное движение происходит в каждом такте; более тяжёлая логика выполняется в 16 раз реже.
При создании машины счётчику progress присваивается случайное значение от 1 до 16. Это распределяет все машины, чтобы их проверки краёв тайлов не приходились на один кадр, а работа распределялась равномерно.
Распознавание коллизий: дешёвое O(n²)
В отличие от моих попыток реализации сложного распознавания коллизий, в оригинале игры применяется простая попарная проверка: для каждой машины мы обходим весь список машин и проверяем, наложатся ли они друг на друга в следующем такте. Если да, то устанавливаем таймер ожидания в 10 тактов для машины, которой мешает другая, и переходим к следующему автомобилю.
Однако код распознавания коллизий написан так, чтобы как можно быстрее выполнять выход. Первым делом он извлекает направление другой машины; так как дороги односторонние, движение на восток и на запад никогда не происходит на одной дороге, поэтому у двух машин, едущих на восток и на запад, коллизий не будет. Эта пара сразу же выполняет возврат без чтения координат. То же самое происходит для востока и юга, запада и севера и так далее.
Допустим, если на экране находится 25 машин, то нужно выполнить 625 попарных вызовов за кадр. Примерно половина из них выполняет возврат всего спустя несколько команд CPU благодаря проверке направления. Большинство остальных не проходят проверку нахождения в одной полосе (едущие в одном направлении машины должны быть на одной дороге, то есть нужно выполнить одно сравнение равенства). До выполнения самой арифметики координат обычно добирается меньше десятка машин.
Когда машине преграждают путь, ожидание в 10 тактов создаёт естественные дорожные пробки: передняя машина рано или поздно обнаруживает, что путь свободен, и пробка рассасывается. В этой системе есть баги (особенно если она работает долгое время, а на карте много перекрёстков), но учитывая то, что её смысл не в реализации точной симуляции вождения, а в простой демонстрации движения на экране, она работает идеально и очень эффективно. У системы распознавания коллизий есть некоторые особенности: некоторые сочетания никогда не проверяются (например, едущая на восток машина никогда не пересечётся с едущей на юг); возможно, в этом и заключается причина багов.
Создание машин
При переходе к экрану улиц игра сканирует все 132 тайлов окна (12 столбцов на 11 строк) и для каждого тайла дороги бросает кубик с учётом плотности дорожного движения района, решая, создавать ли машину. Угловые тайлы исключены из списка точек создания, поэтому машины могут появляться только на тайлах прямых дорог.
Машины, выезжающие за край экрана, заново создаются как машины нового (случайного) цвета, едущие в другом направлении на тайле, идущем в другом направлении. Поэтому игра не беспокоится о повторном создании машин: когда одна машина, едущая на восток, выходит за границы экрана, она создаёт под ней новую машину, едущую на запад и так далее.
Обратите внимание на машины, выезжающие с карты по краям: их заменяют машины, едущие в обратном направлении.
При скроллинге новая открытая полоса тайлов обрабатывается таким же образом, имея вероятность создания на тайлах автомобилей.
Почему это работает
Оглядываясь на свои неудачные попытки, я понял, что проектировал решение задач, о которых оригинал игры даже не задумывался. Машинам не нужен поиск пути, потому что карта сообщает им, куда они могут двигаться. Распознавание коллизий малозатратно, потому что благодаря логике раннего выхода проверка большинства пар практически бесплатна. В игре нет скорости и физики, потому что 1 пикселя на такт достаточно, чтобы всё выглядело правдоподобно. Когда машина должна столкнуться с другой, просто делаем паузу на 10 тактов а когда нужно сделать поворот, достаточно переместиться на половину ширины тайла, а затем выполнить поворот; это срабатывает для всех тайлов в любом направлении.
Я достаточно точно воссоздал всё это на основе ассемблерного кода, потребовалась всего пара операторов switch с разными вариантами прокладывания маршрутов для каждого типа тайлов. Код можно изучить в методе decide_desired_direction файла Car.cpp.
