Как (и зачем) мы портировали Shenzhen Solitaire под MS-DOS

Кейт Холман и Зак Барт — разработчики из игровой студии Zachtronics. Если вы любите запутанные технические статьи о создании игр для 25-летних компьютеров, возможно, вам понравятся наши игры-головоломки: SpaceChem, Infinifactory, TIS-100 и SHENZHEN I/O!

Приступаем

Смогут ли два программиста, привыкшие к созданию игр для современных компьютеров с гигабайтами ОЗУ и полноцветными HD-дисплеями, портировать свои игры под MS-DOS? Никто из нас не имел опыта разработки на таком старом оборудовании, но работа в искусственно ограниченных системах — основа дизайна игр Zachtronics, поэтому мы были обязаны попробовать!

Проект начался с того, что Зак создал макет SHENZHEN SOLITAIRE, мини-игры в пасьянс из нашей игры SHENZHEN I/O (также продаваемой как отдельная игра). Вот как пасьянс мог выглядеть на экране 256-цветного VGA-дисплея:

Похоже на игры, которые можно было увидеть на экранах PC начала 90-х! Теперь осталось только написать код, правда?

Среда разработки

Сначала нам нужно выяснить, как писать программы, которые можно будет запустить на древнем компьютере с DOS. Целевым оборудованием будет винтажный IBM-совместимый PC из коллекции Зака:

• Процессор Intel 80386SX с частотой 20 МГц
• 5 МБ ОЗУ
• VGA-карта
• 3½-дюймовый дисковод
• Мышь с последовательным (serial) интерфейсом
• MS-DOS версии 6.22

Единственным разумным вариантом языка программирования для машины той эпохи будет C. Мы не собирались писать всю игру на языке ассемблера x86! Подумав над разными вариантами рабочих инструментов, мы остановились на Borland C++ 3.1, выпущенном в 1992 году. Запущенная в DOSBox Borland C++ обеспечила удобную и точную эмуляцию целевой машины.

Графика

У компьютеров с VGA-графикой была пара режимов отрисовки. Популярным и простым вариантом был режим Mode 13h: разрешение 320 x 200 пикселей с 256 цветами. Более сложным вариантом был неофициальный режим Mode X, имевший более высокоре разрешение: 320 x 240 пикселей. В Интернете много руководств по работе с режимом Mode 13h, и программировать для него очень просто: 320x200 пикселей представлены массивом 64 000 байт, каждый байт представляет собой один пиксель. Mode X более загадочен и сложен в использовании, но он имеет очевидные преимущества: разрешение 320 на 240, одно из немногих разрешений VGA с квадратными пикселями. Также он поддерживает отрисовку 256 цветами, выбираемыми из палитры. Большинство цветов можно использовать в любом VGA-режиме. Мы хотели сделать графику лучше и усложнить себе работу, потому что мы это любим. Поэтому мы решили использовать Mode X.

Итак, у нас есть графический режим со множеством пикселей и цветов (для компьютеров того времени). Что же мы будем отрисовывать? Самые важные элементы — это:

• Полноэкранные фоны (обои рабочего стола, зелёный карточный стол)
• Карты (в том числе значки карт и числа на картах в трёх цветах)
• Текст (для кнопок и меток)

У нас уже были полноцветные версии в высоком разрешении всех этих ресурсов из оригинальной версии SHENZHEN SOLITAIRE, но их нужно преобразовать в гораздо меньшее разрешение и использовать в общем не более 256 цветов. Какими-то хитростями не удалось бы выполнить такое преобразование, только несколько часов работы в Photoshop с ручной перерисовкой карт, символов и элементов интерфейса, масштабирования разрешений и цветовых палитр фонов.

И здесь становится важным основной недостаток Mode X: для представления 320 x 240 пикселей нужно 76 800 байт. У VGA-карт в целом 256 килобайт видеопамяти, но они разделены на четыре «плоскости» по 64 кБ каждая. Одновременно можно обращаться только к одной из них*. Это вполне подходит для режима Mode 13h, в котором требуется всего 64 000 байт, но в Mode X нужно разделять его видеоданные на несколько плоскостей.

*Всё немного сложнее: в некоторых режимах VGA, в том числе и в Mode 13h, можно получить доступ к нескольким плоскостям одновременно, но у такого подхода есть свои недостатки. Mode X позволяет программисту обращаться одновременно только к одной плоскости.

На этом этапе код графики начинает выглядеть сложным, поэтому мы обратились к Graphics Programming Black Book Майкла Абраша, самому хорошему источнику знаний о VGA. Как объясняет Black Book, режим Mode X разделяет данные о пикселях на четыре плоскости. Каждая плоскость хранит четверть пикселей по схеме с чередованием. В плоскости 0 хранятся пиксели 0, 4, 8, 12, и т.д. В плоскости 1 хранятся пиксели 1, 5, 9, 13, и так далее.

Это классическая ситуация в программировании игр: мы знаем выходные данные, которые нам нужно создавать, и выбор способа структурирования входных данных (в нашем случае — изображений) будет иметь колоссальное влияние на сложность и скорость кода рендеринга. К счастью, нам не пришлось разбираться в этом всём самостоятельно: в книге Абраша есть куча полезных советов по эффективной отрисовке в Mode X. Поскольку весь экран разделён на четыре плоскости, а переключение между плоскостями — относительно медленный процесс, то самый удобный (и быстрый!) вариант — разбить каждое изображение на четыре блока данных, чтобы порции данных каждой из плоскостей находились в одном смежном фрагменте. Благодаря этому код становится невероятно простым и максимально быстрым. Вот код, отрисовывающий полноэкранное (320 x 240) изображение в память VGA:

// Пример кода: отрисовка изображения в память VGA
void far *vgaMemory = MAKE_FAR_POINTER(0xA000, 0x0000);
short bytesPerPlane = (320 / 4) * 240;
for (plane = 0; plane < 4; plane++)
{
    SetCurrentVgaPlane(plane);
    _fmemcpy(vgaMemory, imageData, bytesPerPlane);
    imageData += bytesPerPlane;
}

Этот фрагмент кода также демонстрирует некоторые странности, с которыми нам придётся иметь дело при написании 16-битной программы для DOS. С помощью 16-битных указателей можно напрямую обращаться только к 64 кБ памяти. (Это «ближние» указатели.) Однако у большинства компьютеров под DOS гораздо больше памяти, а адреса, относящиеся к памяти VGA, уже занимают 64 кБ! В ассемблере с этой проблемой справляются с помощью регистров сегментов. В C обычно используют «дальние указатели», то есть 32-битный тип указателей, позволяющий обращаться к 1 мегабайту. (Жизнь стала гораздо проще с появлением 32-битных процессоров, потому что появилась возможность обращаться 4 ГБ памяти, не заботясь о регистрах сегментов.)

К счастью, 64 кБ — это очень много, и почти вся игра умещается в эти рамки. Только две части кода требуют использования дальних указателей. Первый я уже упомянул: память VGA располагается во всём 64-килобайтном диапазоне с адреса 0xA0000. Второй фрагмент — это данные изображений. Преобразовав всю графику в низкое разрешение с одним байтом на пиксель, мы получили примерно 250 кБ данных изображений, хранящихся в одном большой файле. Это больше 64 кБ, поэтому для него тоже потребовался дальний указатель. Кроме того, эта часть оказалась единственной в коде, для которой мы использовали динамическое выделение памяти.

Управление памятью

Основным источником ошибок и сложностей во многих программах на C становится управление динамически выделяемой памятью. В Shenzhen Solitaire мы сделали всё просто: мы точно знали, сколько карт нам нужно отслеживать, поэтому выделили память под них заранее. В коде нет вызовов malloc(), способных привести к ошибкам, и нет вызовов free(), о которых можно забыть. (Такая же стратегия относится и к состоянию в остальной части игры.) Вот как выглядит состояние движка пасьянса:

// Пример кода: объявление состояния движка пасьянса
struct CardOrCell
{
    byte Suit;
    byte Value;
    byte CellType;
    struct CardOrCell *Parent;
    struct CardOrCell *Child;
};

CardOrCell Cards[NUM_CARDS];
CardOrCell FreeCells[NUM_FREE_CELLS];
CardOrCell FoundationCells[NUM_FOUNDATION_CELLS];
CardOrCell TableauCells[NUM_TABLEAU_CELLS];
CardOrCell FlowerCell;
CardOrCell *DraggedCard;

Как я упомянул выше, единственное место, где нам не удалось использовать эту стратегию — данные изображений, потому что они заняли гораздо больше 64 кБ. Поэтому мы сохранили все изображения в один большой файл (как объяснялось выше, данные изображений были разделены на четыре плоскости) и загружали их при загрузке игры вместе с отображением полосы загрузки:

// Пример кода: загрузка данных изображений из файла
// В настоящем исходном коде этот процесс более сложен,
// кроме того, он включает в себя более надёжную обработку ошибок.
FILE *f = fopen("SHENZHEN.IMG", "rb"); assert(f);
long size = GetSizeOfFile(f);
ImageData = farmalloc(size); assert(ImageData);
long loaded = 0;
byte huge *dest = ImageData;
while (loaded < size)
{
    long result = fread(dest, 1, 1024, f); assert(result != 0);
    loaded += result;
    dest += result;
    // (обновление полосы загрузки)
}
fclose(f);

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

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

// Пример кода: отрисовка логотипа экрана загрузки
bool logoDrawn = false;
while (loaded < size)
{
    ...
    // Отрисовываем фон экрана загрузки после его загрузки:
    if (!logoDrawn && loaded > ImageOffsets[IMG_BOOT_BACKGROUND + 1])
    {
        Blit(IMG_BOOT_BACKGROUND, 101, 100);
        logoDrawn = true;
    }
}

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

Как найти и использовать данные изображения при его отрисовке? Все используемые в игре изображения сохранялись в файлы PNG, созданные в современном ПО. Эти PNG затем обрабатывались в специальной программе запекания контента. Запекатель контента преобразовывал PNG в формат, легко обрабатываемый 16-битной программой для DOS. При этом создавались три файла: большой двоичный файл, содержащий все пиксельные данные в виде индексов палитры, небольшой двоичный файл, содержащий палитру из 256 цветов, общую для всех изображений, и файл заголовка C, содержащий метаданные, позволяющие давать изображениям имена и находить их данные. Вот как выглядят метаданные:

// Пример кода: метаданные изображений, автоматически сгенерированные
// инструментом для запекания контента
#define IMG_BUTTON        112
#define IMG_BUTTON_HOVER    113
#define IMG_CARD_FRONT        114
// ID других изображений...

long ImageOffsets[] = { 0L, 4464L, 4504L, 4544L, ... };
short ImageWidths[] = { 122, 5, 5, 5, ... };
short ImageHeights[] = { 36, 5, 5, 5, ... };

byte huge *ImageData = /* загружаемые из файла данные изображений */

Для каждого файла PNG, обработанного запекателем контента, они назначают ID (например IMG_CARD_FRONT), записывают его ширину, высоту и расположение данных. Для отрисовки изображения мы вызываем функцию отрисовки, например Blit(IMG_CARD_FRONT, x, y). Затем функция отрисовки вызывает ImageInfo(IMG_CARD_FRONT, ...) для получения данных и метаданных изображения.

// Пример кода: поиск метаданных для изображения
void ImageInfo(short imageID, short *w, short *h, byte huge **image)
{
    assert(imageID >= 0 && imageID < IMAGE_COUNT);
    *w = ImageWidths[imageID];
    *h = ImageHeights[imageID];
    *image = ImageData + ImageOffsets[imageID];
}

Низкоуровневая оптимизация: немного ассемблера

После завершения реализации работы с графикой логику игрового процесса пасьянса мы доделали быстро, и всё выглядело красиво, хоть и работало очень медленно. Как всегда, единственный способ эффективной оптимизации — это профилирование кода. В состав Borland C++ входит Turbo Debugger, очень полезный профилировщик, учитывая то, что ему 25 лет:

В нашем случае результаты профилирования не удивили. Программа тратила почти всё время на процедуры отрисовки, копируя данные изображений в память VGA. Копирование сотен тысяч пикселей в секунду на 386 с частотой 20 МГц — очень требовательный процесс! Изучение ассемблерного кода, сгенерированного компилятором Borland, дало нам понять, что есть много непроизводительных издержек, замедляющих внутренние циклы процедур отрисовки:

Хотя мы старались по максимуму придерживаться C, было очевидно, что для оптимизации критически важных внутренних циклов процедур отрисовки никак не обойтись без языка ассемблера. Язык ассемблера часто использовался в программировании игр 90-х, когда процессоры были медленными, а оптимизации компилятора — не такими эффективными. Поэтому мы переписали только внутренние части функций отрисовки на встроенном ассемблерном коде. Вот встроенный ассемблерный код внутри функции Blit(), которая используется для большей части процесса отрисовки игры:

// Пример кода: отрисовка встроенным ассемблерным кодом
byte far *vgaPtr = /* адрес памяти VGA */;
byte far *imgPtr = /* адрес исходных данных изображений */;
asm PUSHA
asm PUSH DS
asm LES DI, vgaPtr
asm LDS SI, imgPtr
asm MOV BX, h
asm CLD
each_row:
    asm MOV CX, lineWidth
    asm REP MOVSB   // Эта команда делает всю работу!
    asm ADD DI, dstSkip
    asm ADD SI, srcSkip
    asm DEC BX
    asm JNZ each_row
asm POP DS
asm POPA

Перед этим ассемблерным кодом есть много кода на C, вычисляющего, куда выполнять отрисовку, откуда выполнять считывание данных изображений, как вставить отрисованное изображение в видимую область, но подавляющая часть времени выполнения тратится на команду REP MOVSB. Эта команда аналогична memcpy() из C, но нативно поддерживается процессорами x86, и это самый быстрый * способ копирования памяти на ранних процессорах x86, таких как 386. Как и в memcpy(), необходимо указать указатель на источник, указатель на получатель и число (в регистрах), после чего процессор автоматически копирует в цикле нужное количество данных.

В Shenzhen Solitaire для MS-DOS встроенный ассемблерный язык используется всего в трёх участках кода, и все они очень похожи на этот фрагмент кода. Использование встроенного ассемблера в этих критически важных функциях отрисовки увеличило скорость этих функций в 5-10 раз. Несмотря на множество строк кода настройки и другого кода, выполняемого в игре, основная часть времени ЦП тратилась на простое копирование байтов.

*На самом деле, REP MOVSW или REP MOVSD были бы ещё быстрее, потому что вместо одного они копируют 2 или 4 байта одновременно. Однако в нашей версии Borland C++ поддерживались только 16-битные команды, что не позволило использовать MOVSD. Мы пробовали использовать MOVSW, но у нас возникли трудности с её правильной работой. Даже если бы REP MOVSW ускорила процедуры отрисовки вдвое, этого всё равно было бы недостаточно для решения наших высокоуровневых проблем с производительностью.

Двойная буферизация

Следующей проблемой, которую предстояло решить, стало мерцание.

В режиме Mode X для описания полного экрана графики требуется 75 кБ памяти VGA. Но 256 кБ памяти VGA было достаточно для хранения трёх «экранов» одновременно. В нашем коде мы мысленно назвали их Screen 0, Screen 1 и Screen 2. Пока мы использовали только Screen 0. Для реализации двойной буферизации мы использовали Screen 0 и 1. В каждый момент времени один экран был «передним буфером», отображаемым на экране, а второй использовался в качестве «заднего буфера», области, в которой игра отрисовывает новые или изменившиеся элементы. Когда мы готовы отобразить новый кадр графики, мы выполняем «отражение страницы», функцию VGA, которая мгновенно меняет отображаемую часть памяти.

Двойная буферизация решила проблему мерцания, но игра по-прежнему была слишком медленной. Простой правки низкоуровневого кода отрисовки было недостаточно. Как обычно, Абраш это предвидел. Основной посыл книги Graphics Programming Black Book — выбор подходящих алгоритмов и высокоуровневого дизайна программы дают бо́льший выигрыш в производительности, чем низкоуровневые ассемблерные трюки.

Высокоуровневая оптимизация: статичный фон

Во-первых, мы заметили, что бо́льшая часть экрана почти всегда остаётся одинаковой и не меняется из кадра в кадр.

По экрану обычно движется курсор мыши, иногда перетягиваются несколько карт, но фон и большинство карт остаются полностью неизменными. Чтобы воспользоваться этим, мы назначили последний полный экран памяти VGA Screen 2 «статичным фоном». Мы стали отрисовывать все редко изменяемые элементы интерфейса (то есть почти всё, кроме курсора мыши) на Screen 2. То есть процедура отрисовки каждого кадра обычно была такой:

1. Копируем статичный фон в задний буфер.
2. Отрисовываем мышь (и все перетягиваемые карты) в задний буфер.
3. Делаем задний буфер видимым.

Это позволило избавиться от солидной части работы в большинстве кадров, но копирование всего статичного фона по-прежнему было большой работой. Хуже того, когда статичный фон менялся, например, когда карту поднимали мышью, то сначала статичный фон нужно было полностью перерисовать в дополнение к другой покадровой работе. Это значило, что обычно игра работала плавно, но при нажатии на карты или кнопки присутствовали заметные и неприемлемые торможения.

На этом этапе разработки у нас были две основные затраты производительности: перерисовка статичного фона (время от времени) и копирование статичного фона в задний буфер (в каждом кадре). Мы нашли простое решение для снижения затрат на перерисовку фона: у каждой стопки карт имеется собственная область на экране, и обычно за кадр нужно перерисовать всего одну или две стопки. Это значило, что нужно перерисовывать только 10-20% статичного фона, что занимало пропорционально меньше времени.

Высокоуровневая оптимизация: грязные прямоугольники

Последней проблемой, мешавшей игре работать с приемлемой частотой кадров, было копирование статичного фона, происходившее каждый кадр. Нашим решением стала ещё одна классическая техника из эпохи до возникновения аппаратного ускорения графики: отслеживание грязных прямоугольников. Вы можете помнить «грязные прямоугольники» по Windows 95, при зависании программ такие ситуации возникали часто. Когда программа зависала, пользователь мог перетаскивать другое окно по окну зависшей программы, пока оно не становилось пустым или не покрывалась графическим мусором. Области, по которым пользователь перерисовывал, таская окно, были «грязными». Зависшая программа должна была перерисовывать их, как только пользователь убирал с них окно на переднем плане.

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

Благодаря этому улучшению игра наконец смогла плавно работать на нашей тестовой машине. Мы решили, что у большинства оснащённых VGA-картами компьютеров характеристики получше, чем у нашей тормозной 20-мегагерцовой машины с процессором 386, поэтому были уверены, что производительность игры будет достаточно высокой для выпуска игры.

Ввод

По сравнению с графикой, все остальные аспекты игры были непривычно просты. В IBM-совместимых компьютерах большинство необходимых базовых служб предоставляется BIOS и DOS с помощью API на основе прерываний. В эти службы входят считывание вводимых с клавиатуры и мыши данных, считывание и запись на диски, открытие файлов и выделение памяти. Вот некоторые из прерываний, которые мы использовали в Shenzhen Solitaire:

• INT 16h: API клавиатуры
• INT 21h: системные вызовы DOS
• INT 33h: API мыши

Эти API должны использоваться из ассемблерного кода, примерно так:

// Пример кода: вызов функций BIOS с помощью ассемблера
// Используем INT 16h, 1h для получения последней нажатой клавиши.
mov AL, 16h
mov AH, 01h
int 16h
// При нажатии клавиши устанавливается нулевой флаг.
jnz no_key_pressed
// Обработка ввода клавиши…
no_key_pressed:
// Продолжение выполнения программы...

Считывание состояния мыши выполняется похожим образом: вызовом INT 33h, 3h для получения текущего положения мыши и состояния кнопок. По сравнению с прямым доступом к оборудованию или даже с использованием API современных ОС это невероятно просто.

Звук

Звуковые эффекты — важная часть любой игры, но воспроизведение музыки и звука на очень старых PC — сложная задача. Простейший вариант, имеющийся у всех IBM-совместимых PC — динамик «PC speaker». Этот динамик управляется простой микросхемой таймера на материнской плате. Это значит, что динамик очень просто настроить на непрерывное проигрывание звука с постоянной частотой. У некоторых PC также есть специальные звуковые карты, но их гораздо сложнее использовать и они не всегда есть в системе.

Из-за ограничений PC speaker мы воспроизводили только короткие «музыкальные» фрагменты в определённых моментах игры: при запуске игры, её закрытии и после победы. В PC эпохи процессоров 386 мало возможностей для точного измерения времени, и сложно проигрывать даже простую музыку через PC speaker одновременно с выполнением других действий. Поэтому мы снова выбрали самый простой вариант: так как музыкальные фрагменты очень короткие, мы просто останавливаем игру на одну-две секунды, то есть на длительность проигрывания музыкального эффекта. Код задания и воспроизведения таких фрагментов очень прост:

void PlayStartupMusic(void)
{
    sound(73);
    delay(220);
    sound(110);
    delay(220);
    sound(165);
    delay(220);
    sound(98);
    delay(220);
    sound(110);
    delay(220);
    sound(147);
    delay(440);
    nosound();
}

Кроме музыкальных фрагментов мы хотели добавить звуковой эффект, с которым бы брались и ложились карты, чтобы игра ощущалась более физической. Его тоже реализовали через PC speaker с помощью временного отключения автоматического генератора звука на основе таймера и включением-отключением его вручную для создания краткого «клика».

Выпускаем игру!

Портирование Shenzhen Solitaire под MS-DOS оказалось и проще, и сложнее, чем мы ожидали. Несмотря на огромную разницу мощности процессоров целевого оборудования (одноядерный Intel 80386SX с частотой 20 МГЦ) и нашего привычного оборудования (четырёхъядерный Intel Core i7-4770K с частотой 3500 МГЦ), неоптимизированная геймплейная логика работала с молниеносной скоростью и мало влияла на производительность. Но недостаток заключался в том, что всё кажется быстрым, когда отрисовка всех пикселей экрана занимает почти 150 миллисекунд! В процессе работы мы многое узнали об архитектуре компьютеров, которые сейчас вполне можно считать понятными лишь посвящённым. Несмотря на информативность и интересность процесса, мы вряд ли будем использовать регистры сегментов в будущих играх Zachtronics. Мы не такие садисты!

Если вам интересно поиграть в порт Shenzhen Solitaire под MS-DOS и читаете эту статью до 12 сентября 2017 года, то оцените наш проект на Kickstarter и закажите копию игры как часть нашего релиза только для гибких дисков. Полный исходный код в комплекте!

Автор: PatientZero

Источник