Маленькие секреты большой экономии

    Почему 16 байт достаточно для сохранения игры, и другие мелочи


    Пятьдесят и сто лет спустя у программистов будут всё те же проблемы: им будет очень сильно не хватать объёма доступной памяти для реализации всего, что хочется.

    25 лет назад игровые картриджи содержали 64—128 килобайтов памяти, но каким-то образом этого объёма хватало, чтобы уместить игру на десятки часов геймплея. Сегодня 128 килобайт — это размер маленькой JPEG-картинки, а о том, что доступно в современном бытовом компьютере, в эпоху Super Mario Bros. даже не приходилось мечтать.

    Там были и музыка, и звуки, и неплохая по тем временам графика. Да, некоторое можно было делать с помощью того, что уже было в игровой приставке или компьютере, но в основном приходилось идти на различные ухищрения, чтобы уместить в эти скромные возможности огромное количество звуков, музыки, анимации, изображений и игровых алгоритмов. Как же это удавалось разработчикам тех лет?

    Основной секрет: игры писались на ассемблере, то есть приходилось почти напрямую указывать процессору, какие операции нужно производить. Это и причина, и следствие: было бы трудно работать над крупными проектами, написанными на таком низком уровне.

    Другая маленькая деталь: многое программное обеспечение нужно писать так, чтобы его мог править и исправлять другой программист после тебя. Разработчикам игр под Atari 2600, Sega Master System, NES и SNES и даже под более поздние консоли конца 90-х типа PlayStation 1 или Nintendo 64, беспокоиться было не о чем: зачем кому-то за пределами команды знать, как работает продукт? После выпуска ничего уже не исправить, патч на картридж не накатишь. Наоборот, было предпочтительнее избегать всяких хакеров, выпускавших чит-системы, например, Game Genie. Игры имели почти полный контроль над консолью безо всяких операционных систем, поэтому не требовалось многослойной архитектуры, которую запихивают во все современные продукты для улучшения независимости от программных и аппаратных средств.

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

    Битмап из 16 цветов занимает не так много места, блок из 20×20 пикселей потребует всего ½×20×20 = 200 байтов. За один цикл процессора можно обработать 2 пикселя.

    Графика имела низкое разрешение и была двухмерной. Но можно было с успехом обманывать чувства с помощью псевдо-3D или 2.5D. Наиболее известным 2.5D-автосимулятором является Rad Racer 1984 года. Lotus Esprit Challenge (справа) 1992 года выглядит достаточно правдоподобно.

    Элементами 2.5D известны шутеры от первого лица Doom и Wolfenstein 3D. Слева представлен фрагмент The Train: Escape to Normandy (1987 год) для Commodore 64.

    Музыка генерировалась на лету, её никто не хранил в записанном виде — на это просто не хватило бы места. Иногда бывали исключения, но они лишь иллюстрируют нецелесообразность для той эпохи хранить звуки игры в виде аудиозаписи. Восьмую часть картриджа на 512 килобайт Sonic the Hedgehog, самой первой игры серии про бегающего синего ёжика из 1991 года, занимал вот этот звук длительностью в одну—две секунды. Он был нужен для того, чтобы название фирмы-издателя проигрывалось при запуске.

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



    The Legend of Zelda, самая первая из легендарной серии про эльфоподобного мальчика в зелёном колпачке, для 1986 года была огромной игрой, которую даже пришлось умещать на дорогой катридж в целых 128 килобайт. Сегодня эта цифра звучит смешно, но игра действительно немаленькая: она состояла из одного большого надмира и двух подземелий, каждое из которых было в два раза больше надмира. Изображения кликабельны.



    Первая уловка видна сразу: из стандартной сетки бы выжат максимум. Подземелья состоят из 16 × 16 = 256 экранов, надмир из 16 × 8 = 128. Поэтому данные о том, в каком экране находится Линк, умещаются в один байт: по 4 бита на каждую из координат, при этом для надмира один из битов не использовался. Интересно, что у второго подземелья синяя область в виде буквы L не умещается в отведённое ей пространство, поэтому её дополнительные два экрана расположены левее.

    Если присмотреться, то каждый из экранов представляет из себя матрицу. Экраны надмира и подземелий обрабатывались по-разному. Экран надмира — это сетка из 16×11 тайлов, каждый из которых может быть землёй, песком, камнем, кустом, водой, водопадом, могильной плитой, лестницей, мостом/пристанью, люком или дыркой в стене, плюс несколько опций для специальных декораций — деревьев и входов в подземелья, которые обрабатывались особым образом.

    Кроме земли, больше 3 тайлов не использовалось, поэтому двух байтов, разбитых на 4-битовые нибблы, хватает для хранения информации о том, какие типы тайлов должны быть на экране. Каждый из тайлов требует лишь 2 бита данных. В итоге каждый экран требует 44 байта данных (и два байта для хранения информации о используемых тайлах). Всего надмир умещается в чуть меньше 6 килобайт.

    Большая часть экранов надмира использует либо белый, коричневый или зелёный цвета, а некоторые — это коричневый на зелёном, зелёный на коричневом или белый на коричневом. Два цвета могут использоваться в виде цвета внешней рамки и цвета внутренних элементов. Всего 6 опций, которые умещаются в три бита или ниббл (полбайта).

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

    У нас осталось 12 лишних бит. Нужно хранить информацию о каждой из стен (ничего, 3 типа дверей, точка для бомбы, взорванный проход). 6 вариантов × 4 стены = 24, то есть всё умещается в 5 бит. Кроме того, нужно хранить информацию о типе преграды: камень, статуя, вода/лава, песок или пустота, на что уходит 3 бита. Последние 4 бита определяют цветовую схему комнаты. Каждая из цветовых схем определяется байтом (2 варианта по 16 цветов).

    Итак, на хранение всего игрового мира за счёт множества хитростей уходят какие-то килобайты.

    Сохранения тоже являются примером различных уловок. Для хранения информации о бомбах используется 4 бита, вторая половина байта используется для хранения информации о количестве ключей (до 7). Стрелы и деньги используют одно значение длиной в байт, поэтому каждый выстрел из 255 возможных обходится в рупию. Для хранения информации о количестве кусков Трифорса отведён целый байт, поскольку нужно учесть порядок их сбора.

    Всего есть 8 используемых сокровищ, но одно из них имеет три уровня, а другие два — два уровня. Есть 6 «пассивных» сокровищ, которые, к примеру, позволяют передвигаться по воде или двигать тяжёлые камни, и одно из них тоже имеет два уровня. Наконец, у Линка может быть либо бронзовый, белый или магический меч или он может быть безоружным. Итого возможно иметь 22 различных предмета в инвентаре, для хранения которых потребуется 3 байта, но останется целых 2 бита.

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

    Шестью битами можно задать 26 букв, 10 цифр и несколько специальных знаков. На название сохранения отведено целых 8 символов, которые хранятся в 6 байтах. В японской версии пришлось использовать весь диапазон ASCII, поэтому там максимальная длина составляет 6 символов. Байт уходит на координату экрана в надмире или подземелье, один байт на другие разнообразные данные.

    Таким образом сохранение игры умещается в 16 байт, при этом это не просто сохранение, оно подписано текстом. Для сравнения: этого пространства хватит для 8 символов кириллицы в UTF-8. И сегодня игровые разработчики делают многое для того, чтобы уместить свои сохранения в кластеры файловых систем, но 16 байт — это просто погрешность для современного софта и передачи данных.

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

    Для этого была написана прекрасная система подкачки страниц, которая подгружала куски по 64 килобайта по мере продвижения игрока по карте. Написано всё было так, что даже на скорости дисковода консоли в 300 килобайт в секунду всё прогружалось к моменту появления игрового персонажа в заданной области карты.

    Для хранения ресурсов игры (звуки, текстуры, модели, код) в этих кусках по 64 килобайт была написана утилита запаковки. Некоторые уровни едва умещались, поэтому утилита использовала разнообразные алгоритмы — first-fit, best-fit и другие. После рассмотрения нескольких попыток выбирался наилучший вариант. Задача осложнялась тем, что с изменением левел-дизайна менялись возможности запаковки данных, что было связано со сложностью математической составляющей процесса — подобное трудно объяснить художникам, которым внезапно что-то захотелось переделать. Наибольшей проблемой оставалась оптимизация кода на С и ассемблере, но в итоге всё уместилось под завязку — осталось всего лишь 4 байта свободного места из двух мегабайт ОЗУ.

    В автосимуляторе 1984 года Revs была своя маленькая уловка. Графика игры выглядела так, как показано ниже. Немалая часть экрана отводилась под равномерно синюю область неба



    Этим и воспользовался создатель игры британец Джефф Крэммонд. Он использовал эту область данных видеопамяти для хранения довольно большого куска кода, места для которого в BBC Micro было очень мало. Эта область закрашивалась синим цветом, поэтому игрок не знал об этом, если только игра не заканчивалась с ошибкой — тогда экран заполнялся каким-то мусором.

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

    По материалам треда на Quora.

    Similar posts

    Ads
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More

    Comments 22

      +4
      Основной секрет: игры писались на ассемблере, то есть приходилось почти напрямую говорить микросхемам, какие операции нужно производить.

      Это утверждение вводит читателя в заблуждение. Ассемблер является языком программирования, который оперирует инструкциями процессора, а вовсе не логическим состоянием микросхем напрямую. Да, писать на ассемблере сложней, так как возможность построить собачью конуру из бетонных блоков весьма ограничена (правда современные уютные библиотечки таки решают проблему и предоставляют бетонные блоки для желающих), потому приходится ковырять зубилом и молотком.
        +5
        Elite для ZX Spectrum помещалась в 48 килобайт. А там было, страшно подумать, семь галатик с сотней обитаемых звёзд, с разными названиями, торговой информацией и т.д. Видимо, был какой-то постоянный генератор для всего этого добра, потому что карта оставалась постоянной всегда :)
          +2
          Все эти галактики создавались генератором псевдослучайных чисел — для одного сида последовательность была постоянной.
            +3
            Восемь галактик. Генератор был на основе последовательности Фибоначчи.
              +2
              48 это с видеопамятью и с «системой». От бейсика совсем уйти было сложно. Как минимум загрузчик был на бейсике, так что на него оставляли часть памяти. Часть им использовалась как служебная… Сейчас уже точно не вспомню, но вроде какая-то память использовалась для подпрограмм из ПЗУ. Если их затереть, то мы теряли работу с некоторыми стандартными библиотеками… В общем не припомню я, чтобы на программу можно было выделить больше 40кб (не считая конечно вариантов с диском, вариантов 128к и вариантов когда новые уровни подгружались с кассеты отдельно.)
                +2
                На самом деле псевдослучайно генерируемых галактик было больше, если поменять константу в сейвке игры, то генерировались уже новые 8 галактик.
                    +2
                    Сами демки там маленькие, а генерация текстур и звука производится на лету, но оно опирается на возможности директикса (который сам по себе — тонны кода) и вообще то не очень щадяще использует ресурсы. Хотя надо отдать должное — они выжимают из железа почти все на что оно способно, в отличие от не оптимально пишущихся современных тяжелых игр.
                      +1
                      >не очень щадяще использует ресурсы
                      Это да, я когда впервые запустил игру, не знаю, чему больше поразился: её размеру или тому, что у меня иногда до трех фпс проседало на не очень-то древнем на тот момент железе. Динамическая генерация, фракталы… Я потому и вспомнил .kkrieger в контексте Elite.
                    +2
                    помню как сохранялся на кассету, затем мял магнитофонную пленку, загружал это «сохранение» и получал кучу бабок и оружия… эхх, детство
                      +1
                      Мы соединяли 2 спектрума друг с другом и сохраняли сейв в один из спектрумов, ковырялись в нём, а потом заливали назад. Так и не нашли Raxxla :)
                        +1
                        Вроде бы, устройство генератора имён было таково, что Raxxla не могла получиться.
                          +1
                          Мы об этом не знали :)
                    +4
                    Окей. Раз уж программировал на Java ME — так Java ME. Когда я программировал, была там такая Nokia Series 40 с 64 килобайтами архива и 210 килобайтами памяти — не очень крута для игр, но достаточно дорога, безглючна и живёт с аккумулятора неделю. Там есть два направления экономии: экономия памяти и экономия архива.

                    1. Массивы, везде массивы. Отдельный класс отводил только на объекты, которых немного.
                    2. Мало классов, в которых большей частью static. Было много классов-утилит, состоящих из одного static’а (Dev=Device, G=Game, D=Data, Load=загрузка данных, Skin=внешний вид, Snd=sound…) — специальный препроцессор добавлял их к какому-то классу.
                    3. Банальная обфускация.
                    4. Инициализация массивов занимала много, все предвычисленные таблицы крупнее двух десятков элементов грузили из файлов.
                    5. Не моя уловка, а телефонная — но даже цифровые звуки кодировались очень эффективно, с качеством в 8 или 12 кб/с, тем же кодеком AMR, что используется в разговорах. Другие звуки — это несколько нот MIDI, около сотни байт.
                    6. Файлы данных объединялись в файлы покрупнее, чтобы сжать их эффективнее.
                    7. Минималистичные меню, которые всячески (зачастую без меры) украшали на телефонах, на которых памяти уже хватало.
                    8. Персонажи составлялись из маленьких кусочков специальной программой (написанной тоже мной). Координаты объектов на картинке можно было экспортировать в byte, можно в word — в зависимости от того, «малый» или «крупный» экран.
                      +11
                      Мне кажется, именно вследствие ограниченности ресурсов, старые игры имели тот шарм, который так редко встречается в играх новых. Тогда перед программистами постоянно стоял challenge. И все остальные разработчики игры впитывали этот дух и не отставали в своей работе.

                      Сейчас же, когда зачастую все инструментарии имеются и документированы, в основном нужны количественные решения — здесь 500 строк кода, там 150… Также работают дизайнеры и другие участники создания игры. Это ведёт к рутине и, в конце-концов, к халтуре.
                        +4
                        Я скажу более важную вещь. Когда у моего спектрума было 48кБ памяти, я был готов часами задрачиваться в dizzy и офигевать от элиты, а сейчас у меня в стиме после очередной распродажи 40+ игр, которые «вроде интересно, но как-то времени нет».

                        ЗЫ И трава была зеленее.
                        +3
                        Еще можно вспомнить River Raid, где уровни тоже генерировались на основе псевдослучайных последовательностей.

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

                        В некоторых играх использовалась генерация лабиринтов. Это не только позволяло иметь большие и сложные уровни, но добавляло в игру элемент случайности, когда уровни каждый раз разные, и игроку необходимо их исследовать заново.
                          +1
                          > Насчет «генерации музыки на лету» — эта фраза несколько вводит в заблуждение, возникает впечатление, что на лету генерируются ноты. Нет, ноты хранятся в памяти. Но в компактной форме. На лету (в реальном времени) идет только синтез звука.

                          Бывает и полностью на лету, без хранения нот (правда не знаю насколько широко она исполльзовалась на практике). Типа countercomplex.blogspot.ru/2011/10/algorithmic-symphonies-from-one-line-of.html
                            +1
                            не знаю насколько широко она исполльзовалась на практике

                            Насколько мне известно, мелодии так не генерировались никогда. Может быть, разве что, спецэффекты. Были программы для алгоритмической композиции, типа Algomusic на Амиге, но это было уже в 90х, и не на 8-битках, и как отдельное приложение, а не компонент игры.
                          +1
                          Креш бандикут на первой плейстейшн — непревзойденный шедевр. До сих пор его скриншоты выглядят на уровне. А тогда просто дух захватывало.
                            +9
                            Причин «ожирения» современного софта несколько.
                            Фреймворки. На вопрос «как уменьшить мою программу минимум в 10 раз» есть универсальный ответ — «выкинь фреймворки». Работает всегда, даже в древние времена Delphi отказ от VCL позволял снизить размер результирующего модуля с 300Кб до 30.
                            Сейчас же во всех областях софтостроения наблюдается просто засилие фреймворков. Вполне обычной стала ситуация, когда простой фонарик под Android весит за 20Мб и требует полный набор разрешений, а статическая вроде бы Web-страничка, где нет ничего кроме текста, заставляет ваш смартфон раскаляться в руках.
                            Особенно интересно тут то, что фреймворки — это такая большая уравниловка. Они упрощают работу для новичков, но существенно затрудняют для опытных кодеров, которые для реализации чего-то нестандартного зачастую вынуждены как-то обходить фреймворки, городя тонны костылей.
                            Кроссплатформенность. Задача создания кода, который бы запускался абсолютно везде, на корню убивает искусство программирования. Всё, что нам остаётся — следовать стандартам, создавая унылый, скучный код. И, опять же, уже даже речи не идёт о том, чтоб выжать из железа максимум. Зато приходится наворачивать тонны абстракций, опять же не идущих на пользу производительности. Думаю, многие программисты мечтают о том, чтобы появилось одно-единственное унифицированное устройство… или хотя бы облачные технологии развились настолько, чтоб игру можно было написать только для сервера, а клиентам всего лишь передавалась бы картинка и звук.
                            Защита от дурака. Все эти бесконечные песочницы и разграничения доступа, с помощью которых пытаются бороться с вирусами и троянами. В итоге троянам плевать — как были, так и есть — а вот нормальным программам достаётся куда меньше контроля над системой, т.ч. зачастую игра даже не в состоянии обеспечить предсказуемое время отклика или гарантировать, что в критический момент не начнёт вдруг отжирать мощности какой-то левый процесс.
                            Кризис перепроизводства. Когда ежедневно выходит больше игр, чем человек может хотя бы просмотреть — качество неизбежно будет ниже плинтуса. Потому что в таких условиях игра всего лишь должна быть не ниже среднего уровня, а все «лишние» средства и ресурсы предпочтительнее вложить в маркетинг. Шедевр, не потративший ни копейки на раскрутку, провалится со 100% гарантией, т.к. его просто не найдут в груде мусора.
                            Ну а когда вложения в рекламу дают бОльший выхоп, чем вложения в код, графику, идею и т.д., результат вполне очевиден. Сложно сказать, можно ли что-то с этим сделать — нужен какой-то способ ранжирования игр по их «крутости», а без продвинутого ИИ это малореально.
                              0
                              > Фреймворки

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

                              > Кроссплатформенность. Задача создания кода, который бы запускался абсолютно везде, на корню убивает искусство программирования. Всё, что нам остаётся — следовать стандартам, создавая унылый, скучный код.

                              Искусство программирования — в алгоритмах и архитуктуре, никто его не убивает. Да и для кросс-платформенного низкоуровнего программирования инструментов предостаточно.

                              А вот не-кроссплатформенный код, насколько бы изящно и изобретательно он не использовал недокументированные возможности для «выжимания всего из железа» — на деле мёртвый мусор: через N лет железо сменится и он перестанет работать как задумано, ещё через K железа вообще не останется, а запустить этот код получится даже не на каждом эмуляторе (например, игры, использующие свойства ЭЛТ дисплеев чтобы получить больше цветов чем позволяла система).

                              > Защита от дурака. Все эти бесконечные песочницы и разграничения доступа

                              Это вообще мимо, ибо этим занимается система.

                              > Кризис перепроизводства

                              Не понятно как это связано с ожирением софта.

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