Грязные трюки и оперативка

https://www.gamasutra.com/view/news/310660/Memory_Matters_A_special_RAM_edition_of_Dirty_Coding_Tricks.php
  • Перевод
image

Проблемы с ограничениями памяти давно в прошлом?

Оказывается, нет. Плохо работают с памятью не только некоторые коммерческие движки — у многих платформ достаточно агрессивные требования к ОЗУ. Кроме того, к ним добавляются ещё и ограничения по размерам дисков и картриджей.

Мы собрали примеры из игровой индустрии (разных годов и платформ), о почти незаконных способах ужимания уровней, текстур и целых игр в требуемые объёмы. Может быть, эти способы не очень красивы, но они позволили разработчикам выпустить игры, и никто до сих пор ни о чём не догадался.

Про экран загрузки


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

Наша команда на самом деле заметила эту проблему очень поздно, потому что мы у нас была возможность запускать игру с нужного уровня. Эта функция редактора уровней позволяла программистам и дизайнерам перескакивать непосредственно к уровню, с которым они работали, пропуская основное меню и предыдущие миссии. Такая возможность жизненно необходима в процессе разработки, и я ещё ни разу не видел игру без этой функции (конечно, перед выпуском игры её часто вырезают).

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

Когда отдел контроля качества нашёл эту ошибку, то оказалось довольно сложно устранить все утечки на таком позднем этапе разработки. Первые утечки находились легко, но постепенно становилось всё сложнее отследить и очистить каждый небольшой фрагмент памяти перед началом уровня. Мы провели большую работу — можно было запустить 4-5 уровней подряд, но рано или поздно консоль вылетала. Пройти кампанию за один раз было невозможно.

Команде разработчиков не удавалось исправить всё вовремя. Хотя, возможно, они просто слишком быстро сдались, не знаю точно… Но они воспользовались доступной разработчикам функцией удобного API консоли Xbox. Тогда (и на Xbox 360 тоже) было возможно попросить консоль перезагрузиться. И разработчик мог сообщить Xbox, что нужно делать после перезапуска.

То есть мы могли попросить консоль перезагрузиться и снова запустить ту же игру с определённым параметром. Так быстрый запуск уровней переместился из редактора в саму игру. После завершения уровня игра перезагружала консоль и снова запускала сама себя с параметром командной строки (названием запускаемого уровня). Разумеется, перезагрузка обозначала появление чёрного экрана, поэтому быстро был реализован экран затемнения, выполнявший переход к чёрному цвету. Консоль перезагружалась и переходила на следующий уровень, как это бы сделал редактор, а затем плавно увеличивала яркость. Вуаля, идеальный (?) способ очистки всей памяти между уровнями готов.

Николя Мерсье

ОЗУ и Крэш


Я был одним из двух программистов (вместе с Энди Гэвином), писавшим Crash Bandicoot для PlayStation 1.

ОЗУ была основной проблемой даже тогда. PS1 имела всего 2 МБ ОЗУ, и нам приходилось идти на безумные подвиги, чтобы уместить в них игру. У нас были уровни, содержавшие больше 10 МБ, которые должны были подгружаться и выгружаться из памяти динамически без малейших торможений — задержек при загрузке, когда частота кадров опускается ниже 30 Гц.


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

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

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

Однако проблема такого случайно направляемого поиска заключается в том, что никогда не знаешь, получишь ли те же самые результаты снова. Некоторые уровни Crash умещались в максимально допустимое количество страниц (кажется, их было 21), только когда стохастическому упаковщику «сильно везло». Это значит, что после упаковки уровня можно изменить код единственной черепахи и никогда больше не добиться той же конфигурации упаковки в 21 странице.

Иногда бывало, что кому-нибудь из художников нужно было что-то поменять. При этом мы выходили за пределы допустимого количества страниц, и нам приходилось почти случайным образом изменять другие ресурсы, пока упаковщик не находил подходящую конфигурацию упаковки (попробуйте объяснить это раздражённому художнику в три часа утра).

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

Наконец, нам удалось уместить Crash в память PS1 и ещё оставались свободными четыре байта. Да, четыре из 2097152. Старые добрые времена.

— Дэйв Бэггетт, inky.com (и сотрудник Naughty Dog №1)

Внимание к деталям


Это случилось лет десять назад. В то время я работал в небольшой студии над RTS, выпускавшейся исключительно для PC. Команда была средней по размеру (около 35 человек), мы уже работали около года и находились на середине процесса производства.

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

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

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

Итак, мы создали ISO-образы, записали английскую, французскую и испанскую версии и протестировали их. Никаких проблем не возникало. И тут дело дошло до немецкого диска! Мы начали прожигать ISO, и на экране появилось сообщение «Образ не помещается на носитель».

Что? Как такое возможно? Мы только что записали три другие версии, а на часах уже восемь вечера. Компакт-диски нужно было отправить в семь утра следующего дня. Мы начали разбираться, и оказалось, что записанная немецкая озвучка длится дольше и занимает на диске больше места, чем другие языки. Все наши требования к объёму были установлены с учётом других языков. Теперь у нас оставалось примерно 10 часов на устранение проблемы, запись CD и проверку его работоспособности. Времени на пережатие звука или другие хитрые изменения для экономии места на диске уже не было.

Тогда у нас появилась великолепная идея: выбрать один из уровней, удалить пакет текстур высокого разрешения и заменить его на копию пакета среднего разрешения. Бам! Сэконлено 50 МБ, ISO влезает на CD. Так что наши немецкие друзья с мощными PC играли в один из уровней с той же детализацией текстур, что и люди со средними конфигурациями! Да, признаюсь, это была долгая и напряжённая ночь.

— Реми Кенин, архитектор движка Far Cry

Важен не размер...




В 2008 году мы работали над загружаемой из XBLA игрой. В то время жёсткие диски поставлялись в комплекте не со всеми 360 и загружаемые игры должны были работать при установке на карты памяти. Наша игра была довольно маленькой — примерно 240 МБ. Это значило, что нам нужно было протестировать продукт на картах памяти объёмом 256 и 512 МБ.

С карты в 512 МБ игра запускалась отлично, но при запуске с 256 МБ возникали периодические нестабильные торможения системы. Мы немного подумали над решением, но в результате пришли к выводу, что лучше потратить усилия на повышение качества игры, а не на борьбу с призраками.

Поэтому мы засунули внутрь игровых данных музыкальный файл на 20 МБ, чтобы общий размер файла превысил 260 МБ. Благодаря этому для сертификации нам не нужно было проверять игру на карте памяти с 256 мегабайтами. Это была хорошая игра, которую мы выпустили вовремя. Microsoft и наши клиенты ни о чём не догадались.

— Аноним

Куча мучений


При портировании хорошей экшн-игры с PC на PS2 у нас возникало множество «весёлых» моментов: 256-мегабайтную PC-игру с активным использованием динамического выделения нужно было уместить в 32 МБ. Даже после внесения множества оптимизаций и добавления потоковой подгрузки уровней она занимала слишком большой объём, поэтому:

  • Машина, на которой выполнялась сборка, загружала уровень после запуска системы и отслеживала каждое выделение памяти. Она смотрела, какие операции выделения доживали до начала уровня; при повторном запуске игры она использовала эту последовательность для линейного выделения каждого постоянного размещения, а всё остальное распределяла в кучу или временную память. Это экономило примерно до 15% (5 МБ) памяти, значительно ускоряло выделение памяти и сильно снижало фрагментацию. Но всё равно, через примерно три уровня опять возникала слишком большая фрагментация, поэтому:
  • Машина для сборки выполняла второй шаг: перезапускалась, загружала уровень (с оптимизициями из первого шага), а в начале уровня сбрасывала дамп всей кучи на диск. Готовая игра просто загружала эти образы памяти непосредственно поверх кучи (временно сохраняя локальные параметры профиля в стек) при загрузке каждого уровня.

Результат: очень быстрая загрузка уровней и нулевая фрагментация в начале каждого уровня ценой увеличения времени сборки каждого release candidate.

— Аноним

Пакуем пиксели


В процессе разработки Minecraft для 3DS мы страдали от нехватки памяти, даже на более мощной New 3DS. Поэтому мы хотели поэкспериментировать с форматами текстур, которые поддерживала 3DS. Внутренний формат текстур на 3DS был очень странным. Он был основан на тайлах, упорядоченных в зигзагообразный паттерн из зигзагообразных паттернов, которые затем линейно упорядочивались на самом высоком уровне.


К сожалению, никто из нашей команды не был знаком со сжатыми форматами, чтобы написать утилиту преобразования. Один программист, Иэн, раньше работал над конвертером текстур для Mega Man Legacy Collection, но тот обрабатывал в основном несжатые пиксельные данные.

Этот конвертер текстур получал .png и выдавал файл ".3dst" с собственным форматом, который изобрёл Иэн — в сущности, это был небольшой заголовок и сырые данные, которые мы могли просто записать в память («3dst» расшифровывается как «3DS Texture» — логично, правда?).

Nintendo предоставила свою собственную утилиту преобразования, но она только экспортировала изображения в файлы «package», которые нужно было использовать с библиотекой Nintendo для парсинга и загрузки во время выполнения игры. Для нас это было слишком затратно. И тут нам снова не повезло — этот формат файлов Nintendo не документировала, а он казался единственным способом получить сжатые изображения, собранные в поддерживаемый 3DS формат.

Поэтому я решил углубиться в hex-редактор. Я скармливал утилите Nintendo разные изображения различных размеров и форматов, замечая те изменения, которые происходили в заголовке их файлов, пока не определил достаточное количество полей, чтобы быстро создать необходимые мне данные. Я набросал небольшую утилиту для извлечения сырых данных из package-файлов Nintendo, потом написал пакетный скрипт для применения этого процесса ко всем необходимым нам текстурам. Решение не было быстрым, и уж точно было не изящным, но со своей задачей оно справилось.

— Кит Кейзершот, программист Digital Eclipse

Just brew it


Когда я работал над 3D-гонкой для платформы, куча содержалась внутри раздела данных исполняемого файла. Это был похожий на elf исполняемый формат под названием mod, он содержал огромную область, заполненную нулями, в которой приложение размещало память при загрузке файла в память.

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

— Эндрю Хэйнинг
Поделиться публикацией
AdBlock похитил этот баннер, но баннеры не зубы — отрастут

Подробнее
Реклама
Комментарии 17
  • +4
    В конторе где я работал году в 2008 использовалось что-то типа подхода из раздела «Куча мучений»: при экспорте фактически делался образ памяти, который писался на диск с игрой. При загрузке уровня этот образ просто линейно читался в оперативную память, затем восстанавливались указатели (для этого еще писалась табличка со смещениями всех указателей и объектов и тем кто на что должен потом указывать) и в итоге в памяти образовывались уже готовые данные игры. Никакого сложного парсинга, никаких случайных чтений с диска.
    В те годы (эпоха PS3) это уже было не так принципиально, а вот на прошлых поколениях приставок, говорят, иначе было практически невозможно уложиться в ограничения по времени загрузки уровня при условии довольно медленного привода для дисков.
    • 0

      у Яндекса и сейчас есть где-то в открытом доступе либа, которая позволяет создавать и юзать практически все стандартные контейнеры поверх образа из файла, ничего не де-сереализируя

      • 0
        внекоторых промышленных дистрибутивах линукса была замечательная возможность «как бы перезагрузится» просто скопировать нужный дамп в оперативку.
        очень удобно.
    • 0
      Интересно, такие дикие утечки памяти — быдлокодинг или проблемы консоли?
      • +3
        Проблемы кодинга. Но называть это быдлкодингом — рука не поворачивается. Всё таки разработка в сжатые сроки всегда имеет последствия. И утечки — одна из них.
      • +5
        Хотя трюки может быть и грязные, но спасибо разработчикам, которые смогли выжать всё до капли из платформы и дать геймерам в те далёкие годы прекрасный, красочный и весёлый Crash Bandicoot.
        • +1
          Да вроде нет ощущения гразных хаков от этой статьи. Всё более или менее норм.
        • +1
          Немного другая версия перевода про Crash Bandicoot, есть интересные комменты:
          Ретроспектива разработки Crash Bandicoot, или как разработчики упаковывали целые игры в 2MB RAM
          • 0
            Спасибо, эта версия ГОРАЗДО понятнее.
          • +3
            Наверное, здесь должна быть ссылка на известную историю про 1 байт.
            • –2
              Переполнение мозга от таких длинных историй…
              Так в итоге что, бабуля ему тоже не помогла впихнуть, только успокоиться?
            • +5
              Моя история. Игры для мобильников, Java ME.

              ПАМЯТЬ.
              • Строки в собственной однобайтной кодировке. В этой же кодировке работал шрифт собственного формата (ради технологичности: было много нелокализованных и плохо локализованных мобильников).
              • Большинство информации — static-массивы и static-функции.
              • Эти static’и для удобства разбивались на несколько классов (Dev=device, M=menu, G=game, Skin=оформление, D=data) и в таком виде отлаживались; специальный препроцессор объединял их в один. С константами ничего не надо было делать; ProGuard работал отлично.
              • Если мобильник поворачивал картинки и имел мало памяти, некоторые спрайты делали симметричными и хранили только половинку (в хороших мобилках хранили весь спрайт).

              АРХИВ.
              • Предвычисленные таблицы грузились из файлов (так компактнее).
              • Ещё один препроцессор объединял кучу файлов в один: грузим, например, таблицу спрайтовых атласов, затем тригонометрическую таблицу, затем таблицу меню, затем ещё что-то…
              • KZIP для архивов и PNGOUT для картинок. Даже 7-zip (он нужен был, если какой-то мобильник глючил, тогда в Zlib было немало ошибок) давал меньший архив, чем стандартные утилиты.
              • Иногда даже бывало, что к одному PNG мы пристраивали разные палитры, разбив его на палитру и «всё остальное».
              • Мелкие математические функции вроде max лучше было написать свои, чем импортировать: архива меньше брало.
              • Я специально настаивал: в играх для слабых мобильников резать всё, что угодно, только не игровой процесс. Заставка — одноцветный экран с каким-то логотипом, и т.д.
              • +2
                Еще хорошо бы вспомнить ZX-Spectrum.
                Некоторые игры использовали область памяти для вывода изображения для хранения там данных и искусственно их затемняли атрибутами цвета, делая эту часть экрана например черной.
                • 0
                  А очистка экрана через стековые функции, которые почему-то работали сильно быстрее чем пересылка байтов…
                  • 0
                    Не только очистка, но и копирование/рисование. И «почему-то» вполне понятно — например, потому что не нужно выполнять инкремент/декремент адреса и, например, потому что одной командой обрабатывалось сразу два байта, а не один.
                    • 0
                      Эх, вспоминаю времена демосцены. К примеру есть вывод RGB изображения, где с использованием стека выводятся пикселы и область цвета заливается одним цветом. Со стеком делал интовый (в рамках одного прерывания) попиксельный сколл текста, с ускорением, цветом и другими фишками. Вот там со стеком наигрался вдоволь. Единственное ограничение было, что отображалось только 6 строк со знакоместа и 2 линии просто затирались.

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

                      Да и вообще стек использовался и при отрисовке спрайтов.

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

                      А так очистка экрана через стек действительно быстрее: Побайтово — 7 + 6 = 13 тактов на байт, через стек 11 тактов на 2 байта. А учитывая убогую схемотехнику клонов и округление тактов в четную большую сторону, 14 против 6 на байт.
                      • 0
                        Через стек на спектруме быстрее были абсолютно все линейные операции с памятью. Как вы пишете, очистка (или заполнение) — 11 тактов на 2 байта (PUSH HL), копирование данных — 21 такт на 2 байта (LD HL, XXXX; PUSH HL — при этом «исходные» данные содержали по 2 байта полезной информации и 2 байта кодов команд), но это был единственный способ, позволяющий копировать на пентагоне (70К тактов между прерываниями) весь ч/б экран (6К) за прерывание.
                        А причина — Z80 был великолепным (по тем временам) процессором с точки зрения схемотехники, он позволял создать простейший вычислительный модуль чуть ли не на 4-х микросхемах, но вот на быстродействие его никто не оптимизировал (его оптимизировали на совместимость с медленными микросхемами памяти и портов, все операции работы с шиной у него выполнялись по 2 такта). В итоге вышло, что самым быстрым оказался стек.

                  Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.