[Перевод] Пишем игру «Жизнь» для NES на Rust29.05.2020 12:47

Этот пост — о программе на Rust…

$ cargo install conway-nes

…выводящей двоичный файл NES…

$ conway-nes > life.nes

…в котором выполняется конвеевская игра «Жизнь»!

$ fceux life.nes    # fceux is a NES emulator

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

Рендеринг на NES

NES отображает два типа графики:

Спрайты и фон

Спрайты — это тайлы размером 8x8 пикселей, которые можно располагать в определённых пиксельных координатах; обычно они используются для персонажей и объектов игры:

Только спрайты

Фон — это 2D-сетка из тайлов размером 8x8 пикселей, которая называется nametable. Отдельные тайлы можно заменять, весь фон имеет возможность плавной прокрутки. Обычно он используется для в основном статичных фонов и элементов интерфейса пользователя:

Только фон

Для конвеевской игры «Жизнь» я буду рендерить только фон и заменять элементы nametable, чтобы обновлять сетку тайлов в соответствии с состоянием клеток. Графическое оборудование NES не оптимизировано для внесения частых и больших изменений в nametables. К счастью, большинство изменений за кадр игры «Жизнь» относительно невелико.

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

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

Для рендеринга одного поколения «Жизни» рендереру требуется переменное количество кадров,
которое оказывается меньше, если изменения между поколениями менее значительны. Вот замедленная запись на которой чётко заметна изменчивость частоты кадров.

Краткое введение в фоновую графику NES

Nametable фона хранится в видеопамяти. Эта память подключена к графическому чипу, и центральный процессор к ней прямого доступа не имеет. Каждый элемент nametable — это один байт, который обрабатывается как индекс таблицы паттернов, содержащей формы тайлов. Разрешение экрана NES составляет 256x240 пикселей или 32x30 тайлов размером 8x8 пикселей, поэтому в nametable хранится 32 x 30 = 960 элементов.

ЦП обновляет nametable, записывая пару регистров с отображением в памяти (конкретно 0x2006 и 0x2007). Один регистр за две последовательные операции записи задаёт текущий адрес видеопамяти (адреса видеопамяти состоят из 2 байтов, но регистр имеет ширину всего в 1 байт). Второй регистр используется для записи байта данных в текущий адрес видеопамяти и инкремента текущего адреса. Благодаря этому можно задать последовательность порядковых элементов nametable за 1 запись на элемент, плюс 2 первых записи для задания адреса начала последовательности.

Доступ к этой паре регистров возможен только во время интервала гашения обратного хода развёртки (VBLANK), равного периоду в 2273 такта ЦП (примерно 1,27 мс), по одному разу за кадр (NES выдаёт 60 FPS). Во время этого интервала графическое оборудование не обновляет дисплей. Это не такое большое время, поэтому, возможно, стоит потратить чуть больше времени вне интервала VBLANK, чтобы во время него всё выполнялось более плавно.

Просто перерисовываем то, что изменилось

Моя стратегия рендеринга заключалась в следующем: использовать долю времени вне интервала VBLANK для поиска различий между каждой из пар идущих друг за другом состояний, а затем создать очередь отрисовки, в которой будут перечислены все части nametable, требующие обновления, и то, на что их нужно заменить. Затем, во время VBLANK, итеративно обойти очередь отрисовки, применяя изменения. Чем меньше изменений, тем меньше времени это займёт.

Так как каждая клетка в конвеевской «Жизни» или жива, или мертва, для обозначения текущего состояния каждой клетки я использую всего один бит. Каждый тайл nametable обозначает клетку, то есть существует 960 клеток, а для описания одного поколения клеток требуется 960 / 8 = 120 байт.

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

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

Так как текущий адрес видеопамяти увеличивется при каждой записи в видеопамять, не требуется явным образом задавать адрес видеопамяти между двумя последовательными полосами из 8 тайлов. Поэтому очередь отрисовки — это последовательность серий последовательных полос по 8 тайлов.

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

Позиция на экране: один байт в интервале от 0 до 119 указывает, какой байт обновляется. Чтобы преобразовать это значение в адрес видеопамяти, нужно умножить его на 8, а затем прибавить базовый адрес nametable.
Размер (Size): один байт, указывающий, сколько байтов данных тайлов за ним следует.
Данные тайлов: последовательность из Size байтов, в которых значение каждого бита обозначает состояние клетки в текущем поколении «Жизни».

Очередь отрисовки завершается отрицательной позицией экрана.

Вот несколько первых элементов очереди отрисовки из приведённого выше примера:

Позиция на экране: 8 Размер: 1 Данные: 0x00 (0b00000000)
Позиция на экране: 10 Размер: 1 Данные: 0x80 (0b10000000)
Позиция на экране: 12 Размер: 1 Данные: 0x1C (0b00011100)
Позиция на экране: 14 Размер: 2 Данные: 0x80 (0b10000000) 0x00 (0b00000000)

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

Тайминги

В идеальной ситуации вся логика приложения должна выполняться вне интервала VBLANK, пока графическое оборудование занято обновлением дисплея. Затем должен вызываться рендерер. Он ожидает начала VBLANK, а затем начинает обновлять элементы nametable и обрабатывает всю очередь отрисовки до завершения VBLANK.

Однако в реальности для обработки очереди отрисовки часто требуется несколько кадров. Когда приближается завершение VBLANK, рендерер остаётся на месте до начала следующего VBLANK, а затем продолжает с места, на котором закончил.

Все изменения, внесённые в nametable во время интервала VBLANK, становятся видимыми при следующем обновлении дисплея. Именно поэтому при низкой частоте кадров заметен вертикальный артефакт стирания.

Вот визуализация элементов nametable, записываемых в каждом кадре.

Паттерны

На показанной выше анимации показаны места nametable, в которые ведётся запись в каждом кадре. Каждый элемент nametable — это один байт, который обрабатывается как индекс таблицы паттернов. Таблица паттернов — это область видеопамяти размером 4 КБ, содержащая 256 паттернов. Паттерн — это 16 байт = 128 битное описание тайла размером 8 x 8 = 64 пикселей, где каждая пара битов определяет цвет пикселя.

В игре «Жизнь» каждая клетка или жива, или мертва, поэтому одним из решений может быть использование двух паттернов. Паттерн 0 будет обозначать мёртвую клетку, паттерн 1 — живую клетку. Остальные паттерны не используются.

При записи нуля в элемент nametable соответствующий тайл фона будет являться мёртвой клеткой,

А при записи единицы будет отображаться живая клетка.

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

// Note that this is pseudocode!
// I don't compile rust to run on the NES.
// I write assmebly in a rust DSL. See below.

// assume video memory address is already set correctly
let mut byte_to_render = next_byte_from_draw_queue();
for i in 0..8 {

    // take the current bit
    let pattern_index = byte_to_render & 1;

    // assume this increments the current video memory address
    write_to_video_memory(pattern_index);

    // right shift so the next bit can be tested
    byte_to_render = byte_to_render >> 1;
}

Такая система работает, но её можно улучшить. Центральный процессор NES имеет всего один регистр общего назначения, называемый накопителем. При побитовом AND текущее значение накопителя заменяется результатом операции AND. Чтобы выполнить сдвиг вправо и считать следующий бит, нам нужно скопировать исходное значение накопителя, выполнить для него AND с 1, чтобы получить текущий бит, записать результат в видеопамять, а затем восстановить исходное значение накопителя из копии, сделанной до сдвига вправо. Всё это должно выполняться во время предыдущего интервала VBLANK.

Заметьте, что pattern_index равен 1 ровно тогда, когда byte_to_render нечётное. Таблица паттернов содержит 256 элементов, так что каждый возможный байт является валидным элементом nametable. Мы можем избавиться от необходимости считывания текущего бита из byte_to_render, если зададим таблицу паттернов таким образом, чтобы все нечётные элементы nametable соответствовали живой клетке, а все чётные — мёртвой клетке.

Таблица паттернов принимает вид:

Каждый чётный элемент — мёртвый, а каждый нечётный — живой.

Код рендеринга байта можно упростить:

let mut byte_to_render = next_byte_from_draw_queue();
for i in 0..8 {
    // assume this increments the current video memory address
    write_to_video_memory(byte_to_render);

    // right shift so the next bit can be tested
    byte_to_render = byte_to_render >> 1;
}

Это преобразуется в простой ассемблерный код:

INX        ; increment X index register - the pointer into draw queue
LDA $00,X  ; read next byte from draw queue into accumulator

; unrolled loop

STA $2007  ; store accumulator value at address 0x2007, which writes it to video memory
LSR        ; right shift the accumulator
STA $2007  ; writing 0x2007 increments the current video memory address so repeatedly
LSR        ;   writing 8 times will populate 8 consecutive nametable entries
STA $2007
LSR
STA $2007
LSR
STA $2007
LSR
STA $2007
LSR
STA $2007
LSR
STA $2007

Rust?

Примерно год назад я создал на Rust эмулятор NES, и захотел написать простые программы для NES, чтобы его протестировать. Я создал небольшую Rust-библиотеку mos6502_assembler для написания ассемблерных программ для MOS6502 (процессора NES). Ещё одна небольшая Rust-библиотека ines, написанная мной как часть эмулятора, позволяет считывать и записывать ROM-файлы NES в формате INES, являющемся стандартным форматов файлов, понимаемым всеми эмуляторами NES.

// Function to read the state of the controller into address 0x00FF
b.label("controller-to-255");
const CONTROLLER_REG: Addr = Addr(0x4016);

// toggle the controller strobe bit to copy its current value into shift register
b.inst(Lda(Immediate), 1);
b.inst(Sta(Absolute), CONTROLLER_REG); // set controller strobe
b.inst(Sta(ZeroPage), 255); // store a 1 at 255 - used to check when all bits are read
b.inst(Lsr(Accumulator), ()); // clear accumulator
b.inst(Sta(Absolute), CONTROLLER_REG); // clear controller strobe

// shift each of the 8 bits of controller state from the shift register into address 255
b.label("controller-to-255-loop");
b.inst(Lda(Absolute), CONTROLLER_REG); // load single bit into LBS of acculumator
b.inst(Lsr(Accumulator), ()); // shift bit into carry flag
b.inst(Rol(ZeroPage), 255); // shift carry flag into 255, and MSB of 255 into carry flag

// if that set the carry flag, this was the 8th iteration
b.inst(Bcc, LabelRelativeOffset("controller-to-255-loop"));

b.inst(Rts, ()); // return from subroutine

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

Предварительная обработка

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

В приведённом выше примере кода адрес регистра контроллера 0x4016 присвоен константе Rust CONTROLLER_REG. Возможность присвоения значений именам стандартна для большинства ассемблеров, но когда ассемблер встроен в язык общего назначения, то для этого всего лишь нужно присвоить значение переменной/константе!

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

// zero-out first 8 bytes of memory
b.inst(Lda(Immediate), 0);
for i in 0..8 {
    b.inst(Sta(ZeroPage), i);
}

Процессор 6502 имеет всего 3 регистра, поэтому в коде со вложенными циклами обычно не хватает регистров для хранения счётчиков циклов. Но это не катастрофа — счётчики циклов можно хранить в памяти, но это довольно неудобно и сказывается на времени выполнения, поэтому я часто использую эту технику для облегчения нагрузки. Разумеется, за это приходится расплачиваться увеличением размера кода. Если бы мы работали с более современными архитектурами, то я бы упомянул, как это вредит локальности и приводит к повышению количества промахов кэша, но у 6502 нет кэша.

Валидация

Ещё одно преимущество встраивания заключается в возможности использования системы типов базового языка для валидации свойств «гостевой» программы.

Рассмотрим инструкцию STA, которая сохраняет (STore) значение накопителя (Accumulator) в память. В процессоре 6502 инструкции, получающие как аргументы адреса памяти, параметризуются «режимом адресации», определяющим, как аргумент сопоставляется с адресом.

В приведённом выше примере есть строка…

const CONTROLLER_REG: Addr = Addr(0x4016);
b.inst(Sta(Absolute), CONTROLLER_REG);

…имеющая режим адресации «Absolute» (абсолютный) и аргумент 0x4016. Абсолютный режим адресации считывает следующие 2 байта после опкода инструкции в памяти и воспринимает их как адрес (в 6502 адреса 16-битные). Эта строка сохраняет текущее значение накопителя в 0x4016.

Следующая строка…

b.inst(Sta(ZeroPage), 255);

…имеет режим адресации «Zero Page» (нулевая страница) и аргумент 255 (0xFF в шестнадцатеричном виде). Режим адресации Zero Page считывает один байт после опкода инструкции и воспринимает его как индекс первых 256 байт памяти (т.е. «нулевой страницы» в терминологии 6502). Эта строка сохраняет текущее значение накопителя в адрес 0x00FF.

Третий режим адресации «Immediate» считывает один байт после опкода инструкции и воспринимает его как литеральное значение, а не как адрес.

b.inst(Lda(Immediate), 42); // Load the accumulator with the value 42

Он значим только тогда, когда инструкция считывает из памяти. Использовать режим адресации Immediate с STA невозможно, потому что не имеет смысла сохранять текущее значение накопителя как литеральное.

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

Если я попробую написать так…

b.inst(Sta(Immediate), 42); // Store the accumulator with the value 42

…то это будет ошибка несогласования типов:

error[E0277]: the trait bound `mos6502_model::addressing_mode::Immediate: mos6502_model::instruction::sta::AddressingMode` is not satisfied --> conway/src/main.rs:609:5 | 609 | b.inst(Sta(Immediate), 42); // Store the accumulator with the value 42 | ^^^^^^^^^^^^^^^^^^^^^^^^^^^ the trait `mos6502_model::instruction::sta::AddressingMode` | is not implemented for | `mos6502_model::addressing_mode::Immediate` | = note: required by `mos6502_model::instruction::sta::Inst`

Игра «Жизнь»

Состояние 960 клеток хранится в 120-байтном массиве, который инициализируется случайными значениями при помощи простого генератора случайных чисел (32-битного Xorshift), seed-ом которого является количество кадров после запуска. Вычисление второго поколения автомата заполняет второй 120-байтный массив новыми состояниями клеток. Третье поколение перезаписывает первые состояния клеток, четвёртое — вторые, и так далее. В любой момент времени предыдущие два поколения клеток присутствуют в паре массивов.

Обновление 8 клеток за раз

Поскольку каждый байт состояния описывает состояние 8 клеток, будет удобно вычислять новые состояния клеток по 8 за раз, то есть по одному байту состояния за раз. Для каждого бита текущего байта в этом бите представлено количество живых клеток, соседних к текущей клетке.
Подсчёт всех 8 соседей производится одновременно. Благодаря этому, для каждого байта необходимо считывать из памяти всего 9 байт (8 соседних байтов и сам текущий байт).

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

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

Предварительно вычисляемые соседи

Для вычисления следующего состояния полосы из 8 клеток нужно учесть 8 соседних байтов в сетке 4x30 байт.

Вычисление индексов соседей клетки с заданным индексом — это несложная задача, но вычисление 8 соседей каждого из 120 байтов — это всё равно нетривиальный объём работы, который NES нужно выполнять в каждом кадре, особенно учитывая то, что байты по краям сетки с некоторых сторон не имеют соседей.

Вот индексы первых нескольких строк сетки:

0 | 1 | 2 | 3 4 | 5 | 6 | 7 8 | 9 | 10 | 11 ...

Код на Rust, генерирующий ROM, предварительно вычисляет индексы соседей каждого байта в следующем порядке: верхний, нижний, левый, верхний левый, нижний левый, правый, верхний правый, нижний правый.

X,4,X,X,X,1,X,5 | X,5,0,X,4,2,X,6 | X,6,1,X,5,3,X,7 | X,7,2,X,6,X,X,X 0,4,X,X,X,5,1,9 | 1,9,4,0,8,6,2,10 | 2,10,5,1,9,7,3,11 | 3,11,6,2,10,X,X,X ...

Символами X в этой таблице отмечены соседи, которые не существуют, потому что байт находится на краю сетки. В предварительно вычисленной таблице соседей вместо X используется значение 120. В состоянии есть 120 байтов с индексами в интервале от 0 до 119. После последнего байта состояния в смещении 120 я храню значение 0. Поэтому при чтении соседнего байта рядом с байтом, не имеющим такого соседа, вместо него считывается 0. Это аналогично тому, что видимая область сетки была бы окружена границей из клеток, которые всегда мертвы.

Исходный код

Все мои Rust-библиотеки и исполняемые файлы, относящиеся к NES, находятся в этом репозитории.

Неудачные решения

Когда я впервые реализовал игру «Жизнь» и запустил её с простой конфигурацией глайдеров, она в целом работала, но всё разрушилось, когда разность между кадрами стала равна нулю.

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

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

В предыдущем посте я более подробно объяснял такие глитчи и демонстрировал, как в первой части Legend of Zelda они использовались для реализации скроллинга:
«Переходы между экранами в Legend of Zelda используют недокументированные возможности NES».