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

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

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

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

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

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

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



Были достоинства и у 8-битного адресуемого пространства. Если нужно записать 3 бита, теряется всего 5, а не 27, как на 32-битном процессоре. (По этой же причине 64-битные программы почти всегда крупнее 32-битных.) Битмап из 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.

Источник: geektimes.ru/post/242152/