Ретроспектива разработки Crash Bandicoot, или как разработчики упаковывали целые игры в 2MB RAM

Original author: Dave Baggett
Вот вам анекдот из конца 90-ых. Я (Dave Baggett) был одним из двух программистов (вместе с Andy Gavin), разрабатывающих Crash Bandicoot для PlayStation 1.



Оперативная память была главной проблемой даже в те времена. У PS1 было всего 2MB RAM, и нам приходилось совершать безумные вещи, чтобы уместить в них игру. У нас были уровни, содержащие более 10MB чистых данных, и эти 10 мегабайт должны были постранично загружаться и выгружаться в память динамически, без каких-либо видимых задержек для игрока, при фреймрейте в 30 кадров в секунду.

В основном это работало за счёт того, что Andy написал потрясную систему подкачки, которая должна была подгружать и выгружать страницы в память размером 64K, по мере того как Crash проходил уровень. Эта система была настоящим произведением искусства, задействовавшая весь диапазон доступных инструментов, начиная от высокоуровневного менеджмента памятью, заканчивая прямой работой с памятью и программированием в опкодах. Andy также пришлось контроллировать расположение байтов на CD-ROM, чтобы даже при скорости 300KB/сек PS1 могла успеть загрузить данные для всех деталей уровня к тому времени как Crash добирался до него.

Я же написал упаковщик, который брал ресурсы игры — звуки, арт, код на lisp для управления существами, и т.д. и упаковывал их в страницы по 64К для системы подкачки, написанной Andy. (Между прочим, задача упаковки в страницы фиксированного размера набора произвольных размеров данных — NP-полная, и, почти не поддающаяся решению за полиномиальное, т.е. сколь либо приемлемое время. Задача о ранце.).

Некоторые из уровней едва помещались, и мой упаковщик использовал целый набор алгоритмов (first-fit, best-fit, и т.д.), чтобы пробовать получить наилучший вариант упаковки, включая стохастический поиск, похожий на процесс градиентного спуска, используемый в алгоритме имитации отжига. По существу, у меня была целая куча разных стратегий упаковки, и я пробовал их все и использовал наилучший получившийся результат.

Проблема использования случайного направленного поиска заключалась в том, что ты никогда не мог быть уверен, что сможешь ещё раз получить точно такой же результат. Некоторые уровни Crash Bandicoot умещались в максимально допустимое количество страниц (21, если не ошибаюсь) только лишь из-за того, что упаковщику повезло и он нашёл этот вариант. Так же, это означало, что как только ты получил упакованный уровень, ты мог поменять код для какой-нибудь черепашки и уже никогда не получить упаковку, помещающуюся в 21 страницу. Были случаи, когда дизайнер хотел что-нибудь поменять и это раздувало количество страниц, и нам приходилось менять что-нибудь в других, почти случайных, местах, до тех пор, пока упаковщик снова не найдёт рабочий вариант. Попробуй объяснить это раздражительным дизайнерам в 3 часа утра :)

Самым лучшим эпизодом этой ретроспективы и самым худшим периодом времени тогда была упаковка кода ядра на С и ассемблере. У нас было буквально пару дней чтобы выпусть «gold master» версию — наш последний шанс успеть к сезону праздников, до того, как мы потеряем ещё один год. И мы сидели, переставляя C код в семантически одинаковые, но синтаксически разные конструкции, чтобы заставить компилятор выдать код, который был на 200, 125, 50, а потом и 8 байт меньше. Переставляли, например: «for (i=0; i < x; i++)» — а давайте попробуем переписать это в while-цикл и используем для итерации переменную, которая уже использовалась где-то ранее? Это всё делалось уже после того как мы перепробовали стандартные трюки, такие как помещение данных в два последних бита указателя (и это работало только благодаря тому, что адреса R3000 были выровнены по 4 байта).

В конечном счёте, Crash уместился в память PS1, и даже осталось свободных 4 байта! Да, 4 байта из 2097152. Удачи.
AdBlock has stolen the banner, but banners are not teeth — they will be back

More
Ads

Comments 31

    +13
    Это шикарно!
      +19
      Должно быть здесь: История одного байта
        0
        От первого Крэша у меня очень противоречивые ощущения (поскольку играл в него совсем недавно, а не в те годы, ностальгических очков нет), за что уже успел отхватить критики от зрителей моей передачи… Но прочитав эту статью, я немного пересмотрел своё мнение. Если игра пишется и оптимизируется шаманскими методами, разработчикам уже не до тонкостей! Да и будь они менее удачливыми, выходит, игра могла не выйти вообще.
          +6
          Повторю здесь то, что писал в опросе: Crash 1 — шедевр прежде всего программирования (тот же Mario 64 вышедший на 2 месяца раньше, по графике и рядом не стоял, хотя N64 более продвинутая по железу), а вот геймплей они допилили уже во второй версии, в нее и третью нужно играть. Мемуары разработчиков очень интересны: all-things-andy-gavin.com/2011/02/02/making-crash-bandicoot-part-1
            +8
            Я плюсую комментарий и ссылку обязательно почитаю. Шедеврален он (возможно шедеврален...) по результату, но судя по статье — не с точки зрения программированию. Когда ты от отчаянья и без системы начинаешь подменять одни команды другими, надеясь, что в этот раз оптимизатор всё упакует как надо, когда методом проб и ошибок что-то меняешь на уровне, что бы поменять что-то в другой части уровня… Можно ли называть Это шедевром программирования, когда программист практически не управляет своим детищем, а надеется, что оно заработает? Вопрос философский…

            Ну и сравнивать эти игры довольно странно. Разный геймплей (огромные уровни с исследованием и узенькие уровни-кишки из одного угла карты в другой… красота нечеловеческая, угу). Эта почти идеальная физика и управляемость Mario 64 и никакое управление в полёте Crash'а… И это при том, блин, что я не мариобой, но графику выше геймплея я не поставлю.

            И последнее. Crash — игрушка вышедшая на 2м году жизни консоли, когда понимание её возможностей уже более менее оформилось (но не авторами игры, судя по посту… ;-). Super Mario 64 — вышла одновременно с консолью, когда потенциал её до конца раскрыт не был. Так что сравнение некорректное. Плюс в марио полигонов маловато, тут соглашусь, но что смотрится она хуже — это вопрос предпочтений и вкусов. Я смотрю на игры сейчас и Марио мне менее красивой не кажется.

            Но это всё дикий оффтоп, так что чую, сейчас по мою душу опять придут фанаты...
              0
              Crash — игрушка вышедшая на 2м году жизни консоли, когда понимание её возможностей уже более менее оформилось (но не авторами игры, судя по посту… ;-).
              Именно так: было понятно, что удел PS1 — убогое и ограниченное 3D с «треугольными» обьектами и «музычкой с CD» (Wipeout — наше всё), а что-то круче — стоит ждать от PS2. Crash Bandicoot выкинул всё это «знание» и перевернул представление людей о том, как должна выглядеть игра для PlayStation.

              Когда ты от отчаянья и без системы начинаешь подменять одни команды другими, надеясь, что в этот раз оптимизатор всё упакует как надо, когда методом проб и ошибок что-то меняешь на уровне, что бы поменять что-то в другой части уровня…
              … то это значит, что ты выжимаешь из железа всё, на что оно способно. А когда у вас у игрушки с графикой SNES системные требования — как DOOM3, то… наоборот.

              Причём это не значит, что Crash Bandicoot — это шедевр, а Undertale — отстой. Просто они… немного о разном.

              И это при том, блин, что я не мариобой, но графику выше геймплея я не поставлю.
              А вот многие игроки — поставят. И именно они «вытащили» PlayStation и «утопили» N64. Crash Bandicoot был примерно так же популярен тогда, как какой-нибудь Call of Duty сегодня — и по похожим причинам…
            –7
            А я понимаю разработчиков. На данный момент работаю над проектом на c#. Требования жесткие, программа должна запускаться на машинах с XP (а это .net 3.5), в качестве каркаса используем Prism (wpf). Бд MS SQLServer. И вот что бы это чудо работало и на «Калькуляторах» реально приходиться плясать с бубном — это и жесткая оптимизация ресурсов WPF и всевозможное кэширование данных, что бы лишний раз не делать обращения к мс серверу. Ах да «Калькуляторы» обладают одной не приятной особенностью — наличием памяти, точнее отсутствием необходимого объема.
              +5
              на машинах с XP (а это .net 3.5)
              Это .NET 4.0. К которому путём некоторого количества шаманств прикручивается даже async/await. Хотя он и к 2.0 прикручивается.
                0
                Речь идет больше о WPF на фреймворке, а вот тут отличия значительные, мыло в тексте, отсутствие «Кэшированная композиция», мега баг с RadioButton.IsChecked и привязкой… Со всем этим можно жить, можно и на заборе спать. Вот только очень много неудобств, допилов и
                некоторого количества шаманств прикручивается
                и это все в место того что бы заниматься высокоуровневой архитектурой ( которая мне куда интересней чем технологическое шаманство, от которого к сожалению ни куда не деться )
                +10
                несколько странно видеть требование «запуск даже на калькуляторе» и тормозной WPF (3 draw calls чтобы отрисовать эллипс) с монструозной Prism'ой в одном предложении.
                  0
                  Настоящие проблемы у тех, кто хочет строить действительно интересные интерфейсы (то есть приложения для потребителе)

                  К сожаление потребитель на которого мы работаем (а это тысячи клиентов) часто не намерены обновлять железо ради покупки инструмента, но при этом все хотят красивый интерфей да еще удобный да еще и что бы летал. Бизнес диктует правила из за которых приходится плясать с бубном.
                    0
                    WinForms намного менее требователен к железу, а скорость разработки не сильно ниже (да, там нет MVVM, но и MVP не плох). Ну и Qt+qml как вариант (красиво и без тормозов)
                +6
                Мда, «калькуляторы» с windows xp и .NET… У меня был опыт оптимизации приложения под слабое железо (raspberry pi и сложное ресуркоемкое мультимедийное приложение), но это ни что, по сравнению с неделями впихивания нужного функционала в МК с 512 байт ОЗУ
                  +1
                  >>МК с 512 байт ОЗУ
                  Это еще хорошо. ATTiny2313 с 2к flash/128b RAM, или Tiny13 c 2k/64b, вот это было интересно, да.
                  Впрочем в МК почему-то чаще приходилось оптимизировать чтобы вписаться по времени, а память наоборот свободная оставалась.
                    +1
                    Кто первый вспомнит Atari 2600 с 128 БАЙТАМИ оперативки и 0 байтов видео-памяти?)
                      +4
                      Atari 2600
            • UFO just landed and posted this here
              0
              Богатство оформления этой игры поражало.
              • UFO just landed and posted this here
                +6
                А у меня эта игра, а точнее ее 3 часть связана с болью и страданиями.
                Так получилось что на втором этаже она висла, при попытке зайти в открытые ворота.
                Но у меня был Action Replay не PRO а обычный.
                Не знаю, что меня подтолкнуло, но я тупо перебирал в нем ячейки памяти и писал в них единичку, так продолжалось месяц за месяцем.

                Запуск соньки, вход в Action Replay ввод нового кода, запуск игры… Зависон. Запуск соньки, вход в Action Replay ввод нового кода, запуск игры… Зависон. Запуск соньки, вход в Action Replay ввод нового кода, запуск игры… Зависон. Запуск соньки, вход в Action Replay ввод нового кода, запуск игры… Зависон. Запуск соньки, вход в Action Replay ввод нового кода, запуск игры… Зависон. Запуск соньки, вход в Action Replay ввод нового кода, запуск игры…

                И вдруг, в один из запусков ворота на этаже оказались открыты, и я смог пройти в следуюшие ворота, и перейти на следующий этап.
                  +20
                  Вы точно знаете, что такое безумие)
                    +1
                    помещение данных в два последних бита указателя (и это работало только благодаря тому, что адреса R3000 были выровнены по 4 байта)


                    повезло Вам, что флаг открытия ворот был не в последнем бите. А то бы указатели легли в 0x...000
                      +1
                      На самом деле мне ЖУТКО повезло, так как я был ни сном ни духом про формат кодов для Acrion Replay.
                      А там ведь были и команды сравнения ячейки в памяти, и записи в ячейку, и команды копирования.
                      А уж каких артефактов я навидался в процессе этого поиска.

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

                    0
                    Ностальгия, обожал эту серию, особенно третью часть, потом еще гоночки были, CTR вроде.
                    • UFO just landed and posted this here
                      +6
                      Читаю этот текст как — «Невероятные приключения программистов в прошлом веке»! Крутяк :)
                        +2
                        Мне кажется, или программируя в таких узких рамках железа, программисты более, кхм, скилловые? Это наверное тот ещё челендж.
                          +2
                          Смотря что назвать скиллом, «впихнуть невпихнуемое» это конечно круто, но все это не от хорошей жизни, а от недостатка, недостатка ресурсов, памяти, мощности… Шаманство катострофически снижает читаемость и понимаемость кода, а значит и сопровождение. Но к сожалению часто приходиться брать в руки бубен и надеяться, что этот код ни кто ни когда не увидет и уж тем более не станет побывать исправлять.
                          0
                          Вот ещё текст с кучкой примеров из того обсуждения на «Кворе».

                          Only users with full accounts can post comments. Log in, please.