Анализ исходного кода Another World

Original author: Fabien Sanglard
  • Translation
image

Я потратил две недели на чтение и реверс-инжиниринг исходного кода Another World (в Северной Америке игра вышла под названием Out Of This World). Моя работа основана на обратной разработке Грегори Монтуа (Gregory Montoir) оригинального исполняемого файла для DOS из двоичного кода в C++.

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

Всё это умещалось на гибкий диск ёмкостью 1,44 МБ и работало на 600 КБ ОЗУ. Совсем неплохо для 1991 года! Как обычно, я привёл свои заметки в порядок — это поможет кому-нибудь сэкономить несколько часов работы.

Но… какой исходный код?


Исходный код Another World никогда официально не публиковался и утечек тоже не было. Люди, страстно влюблённые в эту революционную игру, выполнили обратную разработку исполняемого файла DOS.

Отчасти это стало возможным благодаря небольшому размеру двоичного файла (20 КБ). Почему он был таким маленьким? Потому что ANOTHER.EXE — это не сама игра, а только виртуальная машина:

  • Хранящая байт-код.
  • Выполняющая системные вызовы.

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

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

  • 1991 год: Amiga, Atari ST
  • 1992 год: Apple IIGS, DOS, SNES, Mega Drive
  • 1993 год: 3DO
  • 2004 год: GameBoy Advanced
  • 2005 год: Windows XP, Symbia OS, Windows Mobile
  • 2011 год: iOS

Каждый раз нужно было всего лишь скомпилировать виртуальную машину под ОС — байт-код оставался тем же!

Архитектура


Исполняемый файл занимает всего 20 КБ. Он имеет следующую схему:

image

Мы видим здесь четыре модуля:

  • Virtual Machine (виртуальная машина): управляет всей системой.
  • Resource Manager (менеджер ресурсов): загружает ресурсы с гибкого диска, когда их запрашивает виртуальная машина.
  • Sound/Music mixer (микшер звука/музыки): микширует шумы при запросе ВМ.
  • Renderer (рендерер): считывает и рендерит вершины по запросу ВМ. Считывает вершины из сегментов памяти.

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

При запуске исполняемый файл устанавливает значение «0» для программного счётчика потока виртуальной машины (0x00) и начинает интерпретирование. После этого всё управляется байт-кодом.

Объяснение процесса визуализации


На предыдущей схеме показаны три буфера кадров (framebuffer). Два нужны, потому что Another World реализует двойную буферизацию программно, а третий используется как умная оптимизация:

Третий буфер кадра используется только один раз для композитинга фона и сцены, а потом повторно применяет его кадр за кадром с помощью простого memcpy:


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

Интересный факт: этот знаменитый фон состоит из 981 полигона.

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


Здесь очень чётко видны:

  • Двойная буферизация с визуализацией, выполняемой по очереди в переднем/заднем буфере.
  • Буфер фона генерируется один раз и хранится в верхнем левом буфере. Затем он копируется в начале каждого кадра.
  • Если фон изменяется (например, в случае с остановкой автомобиля), буфер фона обновляется, чтобы сэкономить ещё больше места и времени.

Если вы хотите проанализировать отрисовку подробнее, то вот полное видео.

Виртуальная машина Another World


На странице Эрика Шайи (Eric Chahi) подробно объясняется структура ВМ.

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

Вот несколько скриншотов из редактора байт-кода ВМ (его создал Эрик Шайи и дал ему название «script editor»):



Здесь заметно, как теряется метка: setvec 21 nag1 устанавливает счётчик инструкций потока 21 на смещение метки «nag1». В байт-коде видно только жёстко заданное смещение.

Случаи использования кодов операций


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

image

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

image

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

Управление ресурсами


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

typedef struct memEntry_s
{

    int bankId;
    int offset;
    int size;
    int unpackedSize;

} memEntry_t;

Если ВМ запрашивает resourceId, то менеджер ресурсов:

  • Находит его, открывая файл банка (по bankId).
  • Пропускает offset и считывает size байт в ОЗУ.
  • Если size != unpackedSize, то ресурс должен быть распакован.

Немного статистики о сжатии:

Общее количество ресурсов: 146
Сжатых : 120
Несжатых :  28
Примечание: 82% ресурсов сжато.


Общий размер (несжатый) : 1820901 байт.
Общий размер (сжатый)   : 1236519 байт.
Примечание: экономия при сжатии : 32%.


Total RT_SOUND          несжатый размер:  699868 (38% от общего несжатого размера) сжатый размер  585052 (47% пространства на гибком диске) экономия: (16%)
Total RT_MUSIC          несжатый размер:   33344 (2% от общего несжатого размера) сжатый размер 3540 (0% пространства на гибком диске) экономия: (89%)
Total RT_POLY_ANIM      несжатый размер:  384000 (21% от общего несжатого размера) сжатый размер  106676 (9% пространства на гибком диске) экономия: (72%)
Total RT_PALETTE        несжатый размер:   18432 (1% от общего несжатого размера) сжатый размер   11032 (1% пространства на гибком диске) экономия: (40%)
Total RT_BYTECODE       несжатый размер:  203546 (11% от общего несжатого размера) сжатый размер  135948 (11% пространства на гибком диске) экономия: (33%)
Total RT_POLY_CINEMATIC несжатый размер:  365960 (20% от общего несжатого размера) сжатый размер  291008 (24% пространства на гибком диске) экономия: (20%)
Примечание: чёртов коэффициент сжатия звука!

Всего файлов банков: 148
Файлов Total RT_SOUND: 103
Файлов Total RT_MUSIC:   3
Файлов Total RT_POLY_ANIM:  12
Файлов Total RT_PALETTE:   9
Файлов Total RT_BYTECODE:   9
Файлов Total RT_POLY_CINEMATIC:   9

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

Из 146 ресурсов 120 сжаты:

  • Векторная визуализация плюс сжатие поверх него давали ОГРОМНУЮ выгоду (экономия до 62% места!).
  • Сжатие звука очень неэффективно: экономия мала, и ресурсы занимают 47% пространства гибкого диска.

Интересный факт: начальная заставка (ресурс 0x1C) длительностью 3 минуты занимает после сжатия всего 57 510 байт.

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


Как и во всех играх 90-х во время игрового процесса память не распределялась. При запуске движок игры получал 600 КБ памяти (кто-нибудь ещё помнит 640 КБ базовой памяти DOS?). Эти 600 КБ использовались как стековый распределитель:

image

Свободная память: менеджер памяти имел возможность освобождать память на один цикл назад ИЛИ освобождать всю память. На практике вся память освобождалась в конце каждой из 10 частей игры.

Интересный факт: изначально во всех 600 КБ хранились байт-код и вершины. Но после двух лет генерирования фонов из полигонов/пиксигонов игра по-прежнему была далека от завершения. Для ускорения разработки Эрик Шайи решил внедрить в свою замечательную архитектуру хак (ценой ему стало снижение производительности): менеджер ресурсов может загружать битовое изображение фона с гибкого диска в буфер фона (void copyToBackgroundBuffer(const uint8 *src);). Поэтому в конце базовой памяти были зарезервированы 32КБ (320x200/2).

Интересный факт: этот хак применили при выпуске Another World под Windows XP в 2005 году. Все фоны были нарисованы вручную и загружались напрямую с жёсткого диска без использования рендерера и его пиксигонов:

image

image

image

Уголок пуриста


Если вы пурист и хотите играть только в оригинальную версию, то Another World замечательно работает в DosBOX:

image

Или можно поиграть в версию для Windows XP. Рекомендую купить Collector's edition, потому что в ней содержится множество дополнительной информации, в том числе и технические заметки Эрика Шайи:

image

И ещё кое-что


Я много работал над кодом, чтобы сделать его проще для понимания. Вот пример того, насколько он стал яснее.

До:

void Logic::runScripts() {                                                                                                
      for (int i = 0; i < 0x40; ++i) {                                                                                  
        if (_scriptPaused[0][i] == 0) {                                                                           
	     uint16 n = _scriptSlotsPos[0][i];                                                                 
	     if (n != 0xFFFF) {                                                                                
	         _scriptPtr.pc = _res->_segCode + n;                                                       
	         _stackPtr = 0;                                                                            
	         _scriptHalted = false;                                                                    
	         debug(DBG_LOGIC, "Logic::runScripts() i=0x%02X n=0x%02X *p=0x%02X", i, n, *_scriptPtr.pc);
	         executeScript();                                                                          
	         _scriptSlotsPos[0][i] = _scriptPtr.pc - _res->_segCode;                                   
	         debug(DBG_LOGIC, "Logic::runScripts() i=0x%02X pos=0x%X", i, _scriptSlotsPos[0][i]);      
	         if (_stub->_pi.quit) {                                                                    
	            break;                                                                                					
	         }                                                                                       
	     }                                                                                                 					
	    }                                                                                                         					                                                                                                             
	  }                                                                                                                 						                                                                                                              
	}

После:

  void VirtualMachine::hostFrame() {                                                                       
                                                                                                         
	// Выполнение ВМ для каждого активного потока (один кадр ВМ).                                     
	// Неактивные потоки помечаются указателем инструкции потока 0xFFFF (VM_INACTIVE_THREAD).    
	// Поток должен иметь код операции прерывания, чтобы интерпретатор смог перейти к следующему потоку.                 
                                                                                                         
	for (int threadId = 0; threadId < VM_NUM_THREADS; threadId++) {                                         
                                                                                                         
		if (!vmIsChannelActive[CURR_STATE][threadId])                                                           
			continue;                                                                                             
		                                                                                                       
		uint16 pcOffset = threadsData[PC_OFFSET][threadId];                                                    
                                                                                                         
		if (pcOffset != VM_INACTIVE_THREAD) {                                                                  
                                                                                                         
			// Установка указателя скрипта в нужное положение.                                                      
			// pc скрипта используется для выполнения executeThread по порядку                                                        
			// для получения следующего кода операции.                                                                            
			_scriptPtr.pc = res->segBytecode + pcOffset;                                                          
			_stackPtr = 0;                                                                                        
                                                                                                         
			gotoNextThread = false;                                                                               
			debug(DBG_VM, "VirtualMachine::hostFrame() i=0x%02X n=0x%02X *p=0x%02X", threadId, n, *_scriptPtr.pc);
			executeThread();                                                                                      
                                                                                                         
			//Поскольку .pc будет изменён этой следующей итерацией цикла, нам нужно сохранить его.                  
			threadsData[PC_OFFSET][threadId] = _scriptPtr.pc - res->segBytecode;                                  
                                                                                                         
			debug(DBG_VM, "VirtualMachine::hostFrame() i=0x%02X pos=0x%X", threadId, threadsData[0][threadId]);
			   
			if (sys->input.quit) {                                                                                
				break;                                                                                               
			}                                                                                                     
		}                                                                                                      
		                                                                                                       
	}                                                                                                       
  }    

  • Я использовал MACROS, чтобы избавиться от запутанных жёстко заданных значений.
  • Переименовал переменные.
  • Добавил МНОЖЕСТВО комментариев.

Здесь выложен «человекочитаемый» исходный код! Успешного хакинга.
Support the author
Share post
AdBlock has stolen the banner, but banners are not teeth — they will be back

More
Ads

Comments 16

    +10
    Эта игра — настоящее произведение искусства: прекрасное внешне и не менее прекрасное внутри.
      +1
      При этом без единого текста или слова.

      Но вот в детстве на приставке никак не мог запустить игру, а потом уже на эмуляторе: проходила заставка, телепорт в бассейн, тонет и… всё.
      Только потом понял, что это уже геймплей и надо нажимать верх. Это один из немногочисленных минусов этого шедевра.
        0

        Для меня это было плюсом! Сам не понимал, почему умираю и все, а когда догадался, то радовался и это было круто

          0

          Вот тут, кстати, автор говорит об этом:


        0

        Игра проходится на одном дыхании! Очень хорошо продуманная атмосфера, которая создается музыкой + картинкой + сюжетом. Будто смотришь или читаешь качественную Научную Фантастику.
        Погрешности в разрешении изображения оставляют простор для фантазии.
        А наличие нескольких концовок!
        Надо еще раз ее пройти!

          +1
          Какие ещё есть концовки кроме улёта в закат с раненым другом?
            0

            Видимо запамятовал. Действительно, интернет молчит об альтернативных концовках. Извините)

              0
              меня вот, кажется, на x286-м с EGA упорно убивали в конце…
              или это я не прошел до конца?
          +2
          Одна из самых любимых игр, прошел ее на: sega 3do dos win ps3 ps4
          Мало кто знает, но у игры есть продолжение: Heart of the Alien
            0
            У этой игры есть странность: она вышла эксклюзивно на Sega CD — а это мягко говоря не самая распространенная система была даже в свои годы.

            Но сейчас есть опен-сурс переделка под разные платформы — http://hota.sourceforge.net/
              0
              Кстати сам автор игры был против издания этой игры вообще, а так же выступал против того, чтобы она считалась официальным продолжением:
              Eric Chahi recalled: «Interplay insisted in making the sequel in order to make the most of the CD-ROM medium's capabilities. After discussion, I agreed. Rather than making a chronological development related to the first story, I decided that redesigning the game from the alien point of view was excellent, and would make the player discover Another World with other eyes. I could already picture scenes where Lester would be in the background fighting guards, while the player would control the alien in the foreground and then join our first hero, help him, etc… The concept was good but, alas, neither the animations nor the game, entirely developed by Interplay, were up to the job. It was a flop.» Reportedly, «quickly after it was released, Chahi made a public statement that the title did not represent his vision of the world he crafted and disowned it altogether from being treated as an official sequel.»
            0
            Вот еще интересная презентация, где автор рассказывает и демонстрирует некоторые моменты создания игры.
              0
              Разработчик игры вообще молодец. Водичку в те времена было нереальным трудом такую игру создать.
              Надеюсь он разрабатывает продолжение игры и что все фанаты поддержат его проекты рублем, евро и баксом.
                0
                В одиночку
                  0
                  Продолжение давным-давно вышло на Sega и называлось «Heart of the Alien». Правда делалось оно уже после того, как Шайи ушёл из компании. На ютубе можно найти ролики с прохождением этой игрушки.
                    0
                    Да я видел, но она больше похожа на любительский ремейк-продолжение.
                    Я имел ввиду продолжение в современном мире, перезапуск в новом форм факторе.

                Only users with full accounts can post comments. Log in, please.