[Перевод] Как игре Pitfall для Atari удалось поместить 255 комнат в картридж на 4КБ

Игры для Atari 2600 разрабатывались в условиях сильных ограничений. Когда Уоррен Робинетт продвигал идею, которая в дальнейшем станет игрой Adventure (в ней нужно исследовать мир из множества комнат и подбирать предметы, которые помогают игроку в пути), ему отказали, потому что посчитали, что её невозможно реализовать. И это было логично. Консоль появилась в конце 70-х; до Робинетта никто ещё не создавал игру с несколькими экранами. Это была эпоха Space Invaders и Pac Man, когда весь игровой мир постоянно находился у игрока перед глазами, поэтому то, что выпущенная в 1980 году Adventure состояла из 30 комнат, было весьма впечатляюще.

Первый экран игры Adventure. Игрок управляет точкой (которую Робинетт называл «человеком»).

Разработчикам даже пришлось объяснять эту концепцию в руководстве к игре:

Каждая область, показанная на экране телевизора, будет иметь один или несколько барьеров или стен, через которые вы НЕ можете проходить. Также там есть один или несколько проёмов. Чтобы перейти из одной области в соседнюю, «выйдите» с экрана телевизора через один из проёмов, и на экране появится соседняя область.

Наличие нескольких комнат было довольно большой инновацией, а то, что в Adventure удалось реализовать целых 30 комнат, стало настоящей революцией. Однако в созданной Дэвидом Крэйном и выпущенной в 1983 году Pitfall! таких комнат было 255, и каждая из них была более сложной (с точки зрения графики), чем любая комната Adventure. В статье я расскажу, как этого удалось добиться.

Примечание: в игре Superman было несколько комнат и её выпустили до Adventure, но она создавалась на основе кода Adventure.

Типичный экран Pitfall!

Но чтобы в полной мере осознать сложность реализации этого достижения, стоит рассказать о сложностях, с которыми сталкивались программисты игр для Atari. Сама консоль имела всего 128 байт ОЗУ. Это 1024 бит. Для сравнения: это предложение при кодировании в ASCII занимает больше места, не говоря уже о формате UTF, в котором оно на самом деле закодировано. Этого достаточно, чтобы показать, что в Atari было не так много памяти

Но это ведь не важно, в самом картридже ведь будет достаточно места? Ну, в какой-то мере да. В то время картриджи Atari 2600 обычно содержали 4 КБ ПЗУ, подавляющее большинство которого приходилось занимать кодом игры. Даже если опустить необходимость хранения кода, на каждую комнату можно выделить всего 16 байт, а ведь код всё равно нужно где-то хранить.

Примечание: адресуемое пространство в Atari 2600 составляло всего 2 КБ. Использование 4 КБ было возможно благодаря технике под названием «переключение банков» (bank switching).

Так как же Крэйн справился с такими ограничениями пространства при создании игры?

Процедурная генерация

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

Однако самая большая проблема такого решения заключается в том, что сгенерированные данные нужно куда-то сохранять. Именно так поступают игры типа Rogue и Minecraft. Они случайным образом генерируют миры, чтобы дать игрокам разнообразие, но после генерации данных они их сохраняют. Ограничения Atari не позволяли воспользоваться этой роскошью.

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

Описание комнаты

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

Байт, в котором хранится схема текущей комнаты, разделён на четыре части:

Биты 0-2: объекты

Первые три бита определяют типы создаваемых объектов. Эта система усложняется двумя аспектами, которые контролируют биты 3-5.

Во-первых, комната может содержать сокровище (если значения битов 3-5 равны 101). Если в ней есть сокровище, то обычный предмет, определяемый битами 0-2, не будет создан, и его место займёт соответствующее сокровище.

Во-вторых, существуют крокодилы (если значения битов 3-5 равны 100), при которых не создаются никакие другие объекты. Кроме того, если значения битов 0-2 равны 010, 011, 110 или 111, то создаётся лоза, позволяющая игроку раскачаться и перепрыгнуть через крокодилов. При всех других значениях лозы не будет и игроку придётся прыгать по головам крокодилов.

Примечание: я всегда записываю первым старший бит, поэтому «100» точнее было бы назвать «битами с 5-й по 3-й».

Правила создания предметов и сокровищ:

(С этим было довольно сложно разобраться.)

Биты 3-5: тип ямы

Биты 3-5 контролируют тип ямы или ям, с которыми столкнётся игрок.

Подвижные битумные ямы без сокровища (биты 110) всегда имеют лозу, а если сокровище есть (биты 101), то над битумной ямой не будет лозы (благодарю Майка Ширальди за то, что сообщил мне это).

Биты 6-7: деревья

Биты 6 и 7 определяют паттерн деревьев. Это никак не влияет на геймплей, но даёт игроку ощущение смены локаций. Паттерны деревьев похожи друг на друга, поэтому я не буду вдаваться в подробности, но если вы хотите посмотреть, то они используются в комнатах 1, 2, 3 и 5, и имеют битовые паттерны 11, 10, 00 и 01.

Бит 7: подземная стена

Бит 7 также используется для того, чтобы управлять расположением подземной стены — справа или слева. Он не управляет наличием стены, оно определяется в другой части кода, но если стена есть, то значение бита, равное 0, помещает её слева, а значение 1 — справа.

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

Регистры сдвига с линейной обратной связью

Описывающие комнату байты генерируются системой, которую Крэйн назвал «полиномным счётчиком» (polynomial counter); сегодня мы называем её регистром сдвига с линейной обратной связью (linear feedback shift register, LFSR).

LFSR — это способ генерации псевдослучайных чисел по порождающему значению (seed): берётся двоичное число, выполняется логический сдвиг влево или вправо, а затем вычисляется входящий бит через линейную функцию исходных битов. Обычно этой функцией является последовательность из нескольких XOR.

В качестве примера давайте используем LFSR в Pitfall!

Когда игрок начинает игру, байт комнаты имеет шестнадцатеричное значение C4 (11000100 в двоичном виде, 196 — в десятичном). Это порождающее значение (seed). Когда игрок переходит на одну комнату вправо, байт сдвигается влево, и младший бит (бит 0) становится XOR битов 3, 4, 5 и 7. Формула такова:

b0 ← b3' + b4' + b5' + b7'

Где + обозначает XOR, а апостроф — бит в предыдущем состоянии. Этот паттерн имеет желательное свойство — является LFSR максимальной длины, то есть создаёт каждое сочетание из 8 бит, за исключением одним нулей. Это позволяет миру Pitfall! и содержать максимальное количество комнат, и иметь равную вероятность любой битовой строки (повторюсь, за исключением нулей).

Примечание: + обозначает XOR, потому что сложение mod 2 эквивалентно операции XOR над битами.

То есть когда мы перемещаемся после первой комнаты вправо, байт меняет значение с 11000100 на 10001001. Все биты сдвигаются влево, а затем биту 0 присваивается значение 1, так как 1 = 0 + 0 + 0 + 1.

На ассемблере 6502 это было реализовано так:

; room' = room << 1 | (bit3 + bit4 + bit5 + bit7)
LOOP_ROOM:
  LDA ROOM
  ASL
  EOR ROOM
  ASL
  EOR ROOM
  ASL
  ASL
  EOR ROOM
  ASL
  ROL ROOM
  DEX
  BPL LOOP_ROOM

Код целиком можно посмотреть здесь. Данный фрагмент начинается со строки 3012.

ROOM — это байт, описывающий текущую комнату. Прежде чем переходить к тому, как он работает, важно обратить внимание на последние две строки и понять, почему всё это находится в цикле. Крэйн хотел, чтобы если Pitfall Harry (главный герой Pitfall!) находится в подземелье, то прохождение через комнату перемещало его через три комнаты. DEX выполняет декремент регистра X, а BPL выполняет ветвление, если результаты предыдущего вычисления не были отрицательными, поэтому Крэйн реализовал это поведение, задавая регистру X значение 2 перед вызовом этой подпроцедуры, если Гарри находится под землёй. В противном случае регистр X имеет значение 0 и зацикленность отсутствует.

Если точнее, ROOM — это место в памяти, где находится байт, описывающий комнату.

Вот поэтому это цикл. Остальная часть кода, как часто бывает с ассемблером для Atari, довольно запутанна. Я пишу статью не про ассемблер 6502, поэтому не буду вдаваться в подробности, но, по сути, команды ASL (arithmetic shift left, арифметический сдвиг влево) перемещают биты в правильные позиции, а команды EOR (exclusive or, исключающее ИЛИ) выполняют XOR битов. В конце команда ROL (rotate left, вращение влево) сдвигает байт ROOM влево, записывая в бит 0 бит переноса. Этот бит переноса является результатом предыдущих EOR и ASL. Всё вышеописанное создаёт нужное поведение.

Если мы хотим увидеть каждую комнату, которую генерирует этот код, то можем воспользоваться приведённым ниже кодом ассемблера 6502, который обходит в цикле приведённый выше код, пока байт не вернётся к начальному значению, и сохраняет каждй сгенерированный байт по порядку в адреса с $00 по $FF (с 0 по 255).

  LDA #0          ; initialize address offset to 0
  TAX

define ROOM $00
define SEED $C4

  LDA #SEED
  STA ROOM

LOOP_ROOM:        ; do all the LFSR stuff
  ASL
  EOR ROOM
  ASL
  EOR ROOM
  ASL
  ASL
  EOR ROOM
  ASL
  ROL ROOM

  LDA ROOM
  INX             ; increment address offset
  STA $00,X       ; store generated byte

  CMP #SEED       ; stop if we complete a cycle
  BEQ STOP

  JMP LOOP_ROOM   ; get next room byte

STOP:
  BRK

Примечание: хороший эмулятор 6502 можно найти здесь.

Но всё это не даёт понимания того, почему дизайн Крэйна был настолько гениальным. Выше описывается происходящее, когда мы идём вправо, но что если мы пойдём влево, чтобы вернуться в предыдущую комнату? Восемь битов, описывающих эту комнату, никогда не сохраняются в памяти; в памяти хранится только текущая комната. Как Pitfall! реализует движение влево? При помощи этого LFSR:

b7 ← b4' + b5' + b6' + b0'

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

Этот LFSR примечателен тем, что является инверсией предыдущего. Каждый раз, когда игрок идёт влево, этот LFSR отменяет последнее действие, сделанное LFSR, когда игрок шёл вправо. Здесь и далее я буду называть этот LFSR левым LFSR, а предыдущий — правым LFSR.

На ассемблере 6502 левый LFSR был реализован следующим образом:

; room' = room >> 1 | ((bit4 + bit5 + bit6 + bit0) * 128)
LOOP_ROOM:
  LDA ROOM
  ASL
  EOR ROOM
  ASL
  EOR ROOM
  ASL
  ASL
  ROL
  EOR ROOM
  LSR
  ROR ROOM
  DEX
  BPL LOOP_ROOM

Можно заметить, что этот LFSR тоже имеет метку LOOP_ROOM. Её мы взяли из дизассемблированного кода, потому что не знаем, как сам Крэйн назвал этот фрагмент кода, но то, что они имеют одинаковую метку — это вполне нормально. Так получилось потому, что команды ветвления (например, BPL) могут выполнять смещение счётчика программ максимум на 255, а эти две метки разделены более чем тысячей команд. Чтобы перемещаться на более дальние расстояния, потребуется или JMP или JSR, то есть команды безусловных переходов.

Давайте минуту поразмыслим над тем, чего добился Крэйн. Он нашёл LFSR, который является инвертируемым и имеет максимальную длину. Это очень впечатляющий программный трюк. Но не верьте мне на слово, что эти два LFSR являются обратными друг другу, я докажу это вам.

Операции LFSR игры Pitfall инвертируемы. Доказательство:

Рассмотрим последовательность из восьми бит B = b₇ b₆ b₅ b₄ b₃ b₂ b₁ b₀. Используем B_r для обозначения B, к которому применён правый LFSR и B_l для обозначения B, к которому применён левый LFSR. Мы хотим показать, что B_rl = B_lr = B. То есть мы хотим показать, что результат применения сначала правого, а потом левого LFSR, или сначала левого, а потом правого, аналогичны отсутствию действий.

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

Чтобы показать, что B_rl = B, вспомним, что такое правый LFSR:

b0 ← b3' + b4' + b5' + b7'

Применив это уравнение к B = b₇ b₆ b₅ b₄ b₃ b₂ b₁ b₀, мы получим следующее:

Тогда применив левый LFSR, который, как мы помним, имеет вид:

b7 ← b4' + b5' + b6' + b0'

к B_r, мы получим:

И это подтверждает факт, что B_rl = B. Доказательство того, что B_lr = B, почти такое же, поэтому я оставлю его в качестве задания для читателя*.

* Всегда ненавидел, когда так писали в учебниках.

Сказанное выше можно подтвердить и простым кодом, поэтому если вы хотите попробовать, то вот маленькая программа на JavaScript. Я добавил в неё и функцию, перечисляющую все комнаты.

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

---

Постскриптум: как я во всём этом разобрался

Можно решить, что информация о столь важной для истории и популярной игры, как Pitfall!, широко распространена и доступна в Интернете. Но на самом деле это не так.

Многие знали, что в игре используется LFSR, но способ его реализации, насколько я знаю, не описан подробно нигде, за исключением самого ассемблера. Но когда я нашёл проанализированную и откомментированную версию ассемблера, то оказалось, что представленное там описание LFSR на самом деле неверно! По крайней мере, неверно описание левого LFSR. Но ошибка была довольно очевидна, поэтому было несложно понять, как он реализуется на самом деле.

Примечание: изначально в комментарии говорилось, что за декрементом LFSR следовал XOR с битом 1 вместо бита 0. Теперь эта ошибка исправлена.

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

Как же я это сделал? Я написал небольшую программу для генерации последовательности LFSR (программу на JavaScript, ссылка на которую дана выше) и сравнил её с комнатами. Проведение этого анализа для бита 7, управляющего стороной экрана, на которой отрисовывалась подземная стена, было простой задачей, как и биты 6 и 7, управляющие деревьями. Но всё остальное оказалось довольно монотонным. Бесценным ресурсом для меня стала эта карта.

Меня удивило, что, насколько я могу судить, мне довелось первым подробно описать способ рендеринга мира в игре Pitfall!, но в то же время я разочарован. Если вы не смотрели этот доклад на GDC о сохранении истории игр, то вам точно стоит это сделать. В отличие от истории многих других дисциплин, история ПО сохраняется не очень хорошо, несмотря на то, что сохранить её должно быть проще всего. У нас не сохранился оригинальный исходный код почти ни одной игры для Atari, NES, SNES, ColecoVision, и так далее. Дизассемблированный код бесценен, но всё-таки это не оригинал. И он не позволяет прочитать комментарии разработчиков.

Возможно, нам повезёт, и у Activision, Atari и Nintendo где-то в хранилищах есть оригинальный код, который они опубликуют в свободном доступе ради блага человечества, но я бы не особо на это надеялся. Каждый, кто может, должен работать над сохранением любого возможного фрагмента истории, потому что сама себя она не сохранит.