Под капотом RollerCoaster Tycoon: оптимизация как искусство сказать «нет»

RollerCoaster Tycoon (1999) до сих пор называют эталоном оптимизации. Крис Сойер написал игру почти целиком на ассемблере и заставил процессоры конца девяностых тащить парки с тысячами посетителей без единой просадки кадра — то, с чем многие современные градостроительные симуляторы справляются хуже на железе в сотни раз мощнее. Ларс Тофус в блоге Larst Of Us разобрал, как это устроено. Исходников игры нет, но есть почти эквивалент — OpenRCT2, побайтовая фанатская переразработка на годах реверс-инжиниринга. По ней и видно, насколько агрессивно вылизан каждый кусок.

Первое, что бросается в глаза, это типы данных под деньги. Сойер не брал один универсальный тип на все случаи, а подбирал размер под максимально ожидаемое значение. Общая стоимость парка может быть огромной, поэтому под неё отведено 4 байта. А цена товара в ларьке заведомо маленькая, под неё хватает одного байта. На современных процессорах разницы уже нет, поэтому в OpenRCT2 всё свели к 8-байтовым переменным, но в оригинале экономили каждый байт.

Второй приём — замена арифметики битовыми сдвигами. Вместо умножения на 4 в коде стоит сдвиг влево на две позиции, вместо деления на 8 — сдвиг вправо на три. Сдвиг намного дешевле для процессора. Интересна тут не сама техника, а то, как часто она применима: сдвигом можно умножать и делить только на степени двойки. То, что в коде это встречается постоянно, означает, что игровые формулы изначально проектировались под удобные числа. Представьте программиста, который просит геймдизайнера заменить 9,5 на 8, потому что так удобнее процессору. В обычной студии это невозможно. В RCT программист и дизайнер — один человек, и это открывает третий, самый глубокий слой оптимизаций.

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

🔘 У поиска пути есть жёсткий лимит глубины обхода сети дорожек, и при его достижении поиск просто сдаётся и возвращает неудачу.
🔘 По умолчанию гостю можно пройти лишь до глубины в 5 развилок. Когда гость жалуется, что не может найти выход, это буквально работа алгоритма, который мог бы искать дальше, но не стал ради кадров.
🔘 Механик важнее обычного гостя, ему лимит подняли до 8 развилок.
🔘 Гость, купивший карту парка в киоске, получает лимит 7 вместо 5, и ему легче найти выход. Техническое ограничение превратили в игровую механику.

Тем же принципом решена толкучка. Система столкновений и обхода для тысяч агентов убила бы фреймрейт, поэтому гости в RCT не сталкиваются и не избегают друг друга — на одной плитке дорожки их могут стоять хоть тысячи. Но они считают соседей: если рядом слишком людно, падает счастье и летит жалоба игроку. Для игрока результат тот же — приходится планировать дорожки, чтобы не было давки, — а расчёт на порядок дешевле. Вывод Тофуса: менять дизайн ради производительности кажется радикальным шагом, но при должном диалоге между кодом и геймдизайном это даёт выигрыш, которого не добьёшься никакой микрооптимизацией. Иногда лучшая оптимизация — это смелость сказать техническому вызову «нет».

Сохранять тем, кто любит истории про low-level инженерию, ценит дизайн, продиктованный железом, и хочет показать коллегам, что значит «оптимизировано до предела».

https://www.larstofus.com/the-gold-standard-of-optimization-a-look-under-the-hood-of-rollercoaster-tycoon

@prog_stuff