Как писали игры для приставок: чудеса оптимизации и жёсткий кодинг

В 1980-х годах, когда при­став­ки толь­ко появ­ля­лись, вышла NES — Nintendo Entertainment System. В Рос­сию она попа­ла в виде китай­ско­го кло­на «Ден­ди», «Кен­ги» и про­чих, поэто­му если у вас была вось­ми­бит­ная при­став­ка, то это была NES.

У NES было очень мало памя­ти и очень мед­лен­ный по нынеш­ним мер­кам про­цес­сор. Эта ста­тья о том, как сде­лать кру­тую игру в очень огра­ни­чен­ных условиях.


Та самая при­став­ка, спра­ва пока ещё две кноп­ки вме­сто четырёх. 

Для раз­бо­ра мы взя­ли видео из кана­ла Morphcat Games — How we fit an NES game into 40 Kilobytes. Там раз­ра­бот­чи­ки повто­ря­ют опыт гейм­ди­зай­не­ров про­шло­го и пишут игру для ста­ро­го желе­за. Как обыч­но, если зна­е­те англий­ский, то луч­ше посмот­ри­те видео цели­ком, а если нет — дер­жи­те наш тек­сто­вый вариант.

Почему именно 40 килобайт

В 1980-х объ­ём памя­ти на циф­ро­вых устрой­ствах изме­ря­ли в кило­бай­тах, пото­му что ещё не было таких про­дви­ну­тых её тех­но­ло­гий. В боль­шин­стве кар­три­джей для вось­ми­бит­ных при­ста­вок было по 40 кило­байт памя­ти. Для срав­не­ния, это в сто тысяч раз мень­ше, чем на флеш­ке в 4 гига­бай­та. Даже эта ста­тья весит боль­ше, чем 40 кило­байт, так что по совре­мен­ным мер­кам это­го дей­стви­тель­но мало.


Два бло­ка памя­ти в кар­три­джах, 8 и 32 кило­бай­та, в сум­ме — 40 килобайт. 

Что­бы исполь­зо­вать боль­ше памя­ти, нуж­но было идти на вся­кие ухищ­ре­ния — ста­вить рас­ши­ри­те­ли памя­ти или отдель­ные бло­ки для рабо­ты с несколь­ки­ми кар­три­джа­ми одно­вре­мен­но. Так как почти ни у кого из гей­ме­ров такой рос­ко­ши не было, то раз­ра­бот­чи­ки исполь­зо­ва­ли толь­ко 40 доступ­ных килобайт.

Когда у тебя мало памя­ти, у тебя мало воз­мож­но­стей: уров­ни одно­об­раз­ные, вра­ги одно­об­раз­ные, гейм­плей оди­на­ко­вый. Но ино­гда раз­ра­бот­чи­ки шли на безум­ные ухищ­ре­ния, и в игру полу­ча­лось запих­нуть мно­го «миров», сек­ре­тов и вари­ан­тов геймплея.

Одна из игр, кото­рая взо­рва­ла мозг всем в своё вре­мя, была та самая «Супер Марио»: в ней было огром­ное коли­че­ство раз­но­об­раз­ных уров­ней раз­ной слож­но­сти, бос­сы, сек­рет­ные уров­ни и непро­стой, очень насы­щен­ный гейм­плей. Были уров­ни на зем­ле, под зем­лёй, под водой и даже на небе; у героя было несколь­ко режи­мов — низ­кий, высо­кий, в белом ком­би­не­зоне. А как вам идея раз­ру­ша­е­мо­го мира? А как вам ата­ки с воз­ду­ха? Коро­че, «Марио» была безум­ной, неве­ро­ят­ной игрой для сво­е­го вре­ме­ни, а всё бла­го­да­ря оптимизациям.

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


«Супер Марио» — игра, в кото­рую играл каж­дый, у кого была приставка. 

Логика игры

Что­бы в игру было инте­рес­нее играть доль­ше пяти минут, раз­ра­бот­чи­ки поста­ви­ли такие требования:

  1. Это будет плат­фор­мер — игра, где глав­но­му герою нуж­но бегать и пры­гать по плат­фор­мам, зале­зать наверх и ска­кать через препятствия.
  2. Герой смо­жет лов­ко дви­гать­ся и стре­лять по врагам.
  3. Что­бы мож­но было играть ком­па­ни­ей, дела­ют муль­ти­пле­ер на четы­рёх человек.

Так как у нас огра­ни­че­ния по памя­ти, всю игру пишут на Ассем­бле­ре — это язык, кото­рый рабо­та­ет напря­мую с про­цес­со­ром. С одной сто­ро­ны, код Ассем­бле­ра испол­ня­ет­ся очень быст­ро; с дру­гой — в нём рабо­та идёт тупо с пере­кла­ды­ва­ни­ем дан­ных из одной ячей­ки про­цес­со­ра в дру­гую. Это при­мер­но как гото­вить суши, рабо­тая с инди­ви­ду­аль­ны­ми рисинками.

Память рас­пре­де­ли­ли так:

  • 8 кило­байт на графику,
  • 32 кило­бай­та на сам код игры и хра­не­ние данных.

Персонажи

В игре есть два вида гра­фи­ки: ста­тич­ный фон и дви­жу­щи­е­ся пред­ме­ты — игро­ки, про­тив­ни­ки, бос­сы и выстре­лы. Всё, что дви­жет­ся, назы­ва­ет­ся спрай­та­ми. Раз­ра­бот­чи­ки делят всю гра­фи­че­скую память на две части — одну под спрай­ты, вто­рую под фон:


Каж­дая кле­точ­ка — это мини-квадратик 8 на 8 пикселей. 

В каж­дом таком квад­ра­ти­ке мож­но что-то нари­со­вать, но исполь­зо­вать при этом толь­ко три цвета. 

Если объ­еди­нить несколь­ко квад­ра­ти­ков в один, полу­чит­ся метас­прайт. В нашем слу­чае — персонаж. 

При­став­ка может исполь­зо­вать одно­вре­мен­но толь­ко 4 вида палит­ры, поэто­му у нас полу­ча­ет­ся 4 цвет­ных глав­ных героя и нерас­кра­шен­ный злодей. 

Новое огра­ни­че­ние: на экране одно­вре­мен­но может быть толь­ко 8 спрай­тов — на боль­шее не хва­та­ет памя­ти. Поэто­му для зло­дея места не оста­ёт­ся. Мож­но пой­ти на хит­рость и пока­зы­вать их быстро-быстро по оче­ре­ди, но тогда кар­тин­ка будет мер­цать и выгля­деть хуже. 

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

Мень­ше раз­мер героя — боль­ше сво­бод­но­го места для дизай­на зло­де­ев, бос­сов и спе­ц­эф­фек­тов. Сей­час в таб­лич­ке собра­ны все вари­ан­ты того, как может выгля­деть пер­со­наж в игре — и в прыж­ках, и на бегу. 

Большой босс и оптимизация памяти

Если с пер­со­на­жем всё ста­ло про­ще, когда его умень­ши­ли, то с бос­сом всё немно­го слож­нее. Он боль­шой, зани­ма­ет мно­го места и у него мно­го ани­ма­ции. Зада­ча — сде­лать так, что­бы бос­сы зани­ма­ли как мож­но мень­ше места в памяти.


Боль­шой босс и все его вари­ан­ты анимации. 

Если мы рас­пре­де­лим все спрай­ты по таб­ли­це один в один, то у нас быст­ро закон­чит­ся место и один кусо­чек не поме­стит­ся. Запом­ни­те эту кар­тин­ку как при­мер неопти­ми­зи­ро­ван­ной рабо­ты с памятью. 

Для нача­ла раз­ра­бот­чи­ки раз­би­ли бос­са гори­зон­таль­но на три части, и каж­дая ани­ми­ру­ет­ся отдель­но. Вид­но, что ани­ма­ция при­чёс­ки состо­ит из трёх кар­ти­нок, каж­дая из кото­рых немно­го отли­ча­ет­ся от остальных. 

Если раз­бить кар­тин­ки с при­чёс­кой на отдель­ные квад­ра­ти­ки, то мы заме­тим, что у них есть повто­ря­ю­щи­е­ся части. Поэто­му доста­точ­но нари­со­вать одну деталь, а потом исполь­зо­вать её во всех трёх вари­ан­тах причёски. 

Нахо­дим остав­ши­е­ся оди­на­ко­вые части и тоже остав­ля­ем толь­ко одну из них. 

А вот тут вид­но, что это один и тот же спрайт, толь­ко в зер­каль­ном виде. Ком­пью­те­ру неслож­но нари­со­вать его отра­жён­ным, поэто­му тоже мож­но сме­ло оста­вить толь­ко один из них. С послед­ни­ми тре­уголь­нич­ка­ми в каж­дой кар­тин­ке — то же самое: это отзер­ка­лен­ные пер­вые спрайты. 

В ито­ге вся верх­няя часть бос­са вме­сте с ани­ма­ци­ей поме­сти­лась в четы­рёх спрай­тах. Это и есть опти­ми­за­ция: было 16 спрай­тов, ста­ло 4. 

То же самое дела­ют для сред­ней части. Сей­час она зани­ма­ет 3 × 8 = 24 спрайта. 

А сей­час — 7. 

После пол­ной опти­ми­за­ции босс зани­ма­ет все­го 21 спрайт. Из этих кусоч­ков соби­ра­ет­ся ито­го­вый вид босса. 

Срав­ни­те с пер­во­на­чаль­ным вари­ан­том до оптимизации 🙂 

Карта

Для карт у нас столь­ко же памя­ти, сколь­ко и на спрай­ты (то есть мало), поэто­му раз­ра­бот­чи­ки будут дей­ство­вать так же:

  • раз­би­вать фон на отдель­ные ячейки;
  • смот­реть, как мож­но опти­ми­зи­ро­вать эти ячей­ки для хра­не­ния в памяти;
  • смот­реть, мож­но ли что-то исполь­зо­вать повтор­но, для эко­но­мии памяти.

Глав­ная зада­ча на этом эта­пе — мак­си­маль­ная эко­но­мия видео­па­мя­ти. Для это­го каж­дый экран с уров­нем игры раз­би­ва­ет­ся не на метап­лит­ки 2 × 2, как в при­ме­ре выше, с пер­со­на­жем, а на мета­ме­тап­лит­ки или супер­п­лит­ки — 4 × 4 ячей­ки. Вот для чего это нужно:


Если раз­бить про­сто на квад­ра­ти­ки 8 × 8, как в памя­ти, то вся види­мая на экране часть уров­ня зай­мёт 960 байт. Это почти кило­байт, и это очень много. 

Раз­би­ва­ют уро­вень на метап­лит­ки 16 × 16. Теперь на одну кар­ту нуж­но 240 байт, что­бы поме­тить каж­дую такую метап­лит­ку, но это всё рав­но мно­го. Умень­ша­ем дальше. 

Теперь уро­вень делит­ся на супер­боль­шие плит­ки по 16 яче­ек в каж­дой. В ито­ге для того, что­бы про­ну­ме­ро­вать каж­дую такую супер­п­лит­ку, нуж­но все­го 60 байт. Уже мож­но работать. 

Вот так соби­ра­ют­ся метап­лит­ки — из четы­рёх яче­ек в памяти. 

Теперь мож­но соби­рать такие метап­лит­ки в вир­ту­аль­ные набо­ры и каж­дой при­сво­ить какой-то код. Но и это ещё не всё. 

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

Кол­лек­ция вир­ту­аль­ных супер­п­ли­ток. С ними мож­но сде­лать любые уров­ни и фоны. 

Рисуем карты (и оптимизируем их)

Даже 60 байт на экран, кото­рые у нас полу­чи­лись, — это всё рав­но очень мно­го, ведь нуж­но сде­лать мно­го раз­ных карт, напи­сать логи­ку пове­де­ния пер­со­на­жей и сде­лать меню, застав­ки и тит­ры. Каж­дый байт на счету.

Пер­вый вари­ант — умень­шить коли­че­ство памя­ти для отри­сов­ки кар­ты: сде­лать их сим­мет­рич­ны­ми, что даст нам 30 байт вме­сто 60. Мы рису­ем одну поло­вин­ку кар­ты, а потом про­сто отзер­ка­ли­ва­ем её. Срав­ним с кар­той, кото­рую мы бы хоте­ли получить:


Вро­де всё на месте, а выгля­дит пло­хо — сра­зу вид­на сим­мет­рия и доступ наверх закрыт блоками. 

И вот тут раз­ра­бот­чи­ки дела­ют оче­ред­ной хит­рый ход, кото­рый даст им немно­го допол­ни­тель­ной памя­ти для гра­фи­ки. Смотрите:

  1. Они дают для хра­не­ния одной супер­п­лит­ки один байт.
  2. Счи­та­ют по кар­тин­ке, сколь­ко полу­чи­лось супер­п­ли­ток в про­шлом раз­де­ле — 96.
  3. Так как про­грам­ми­сты начи­на­ют счи­тать с нуля, то самое боль­шое чис­ло, кото­рое полу­чит­ся, — 95, а это 1011111 в дво­ич­ной систе­ме счисления.
  4. В этом длин­ном чис­ле все­го 7 цифр, а в бай­те их 8, поэто­му оста­ёт­ся один лиш­ний бит из каж­до­го числа.
  5. 4 супер­п­лит­ки дадут 4 бита.
  6. Эти 4 бита мож­но исполь­зо­вать, что­бы сдви­нуть по кру­гу ряд с зер­каль­ным отра­же­ни­ем и полу­чить как бы новый ряд, уже без види­мой симметрии.

Если вы не зна­е­те, что такое дво­ич­ная систе­ма счис­ле­ния, — почи­тай­те нашу ста­тью об этом, а потом вер­ни­тесь сюда.


4 супер­п­лит­ки дают 4 бита. Посмот­рим, что мож­но с ними сделать. 

Сна­ча­ла дела­ют сим­мет­рич­ный уровень… 

А затем сдви­га­ют верх­нюю поло­су впра­во по кру­гу. 1100 — это 12 в деся­тич­ной систе­ме счис­ле­ния, имен­но столь­ко сдви­гов впра­во нуж­но сде­лать, что­бы полу­чи­лось как на картинке. 

То же самое дела­ют с тре­тьей стро­кой и полу­ча­ют уже при­ем­ле­мое нача­ло уровня. 

Дей­ствуя таким обра­зом, раз­ра­бот­чи­ки могут менять уров­ни до неузна­ва­е­мо­сти, не затра­чи­вая при этом вооб­ще лиш­ней памя­ти. Пом­ним, что наш экран — это ещё не весь уро­вень, свер­ху нуж­но нари­со­вать ещё мно­го раз по столь­ко же.

Добавляем в игру сложный режим

Когда игрок про­шёл все уров­ни, ему мож­но дать воз­мож­ность поиг­рать на повы­шен­ной слож­но­сти: он уже зна­ет всю игру и может прой­ти более слож­ные ловуш­ки и бос­сов. Напри­мер, слож­ный режим может отли­чать­ся дизай­ном уров­ней и пове­де­ни­ем противников.

Что­бы и этот режим поме­стил­ся в остав­шу­ю­ся память, сно­ва исполь­зу­ют трю­ки с памя­тью и графикой.


Что­бы игрок понял, что нача­лись труд­но­сти, про­сто меня­ют палит­ру. Это почти столь­ко же по памя­ти, но выгля­дит сложнее. 

Уро­вень мож­но поме­нять так: берут исход­ную кар­тин­ку, накла­ды­ва­ют свер­ху новые дета­ли и полу­ча­ют слож­ную лока­цию. В сред­нем на это ухо­дит по 7 байт на каж­дый экран. 

В чем оптимизация, брат

  1. Умень­ши­ли пер­со­на­жей: малень­кие спрай­ты — мень­ше памяти.
  2. Опти­ми­зи­ро­ва­ли гра­фи­ку: вме­сто боль­ших повто­ря­ю­щих­ся кар­ти­нок — мно­го малень­ких повто­ря­ю­щих­ся картинок.
  3. Опти­ми­зи­ро­ва­ли архи­тек­ту­ру уров­ней: сде­ла­ли их сим­мет­рич­ны­ми, но сдви­ну­ли ряды по кру­гу влево-вправо, что­бы доба­вить разнообразия.
  4. Для допол­ни­тель­но­го раз­но­об­ра­зия вве­ли новые цве­то­вые палитры.
  5. Более слож­ные уров­ни не хра­ни­ли в памя­ти цели­ком. Для них хра­ни­лись лишь допол­ни­тель­ные ловуш­ки и вра­ги. А на фоне лежа­ли те же ста­рые уровни.
  6. И всё это на чистом Ассемблере.