Source Code Analysis Another World

I spent two weeks reading and reverse-engineering the source code for Another World (in North America, the game was released under the title Out Of This World). My work is based on the reverse engineering of Gregory Montoir (Gregory Montoir) of the original DOS executable from binary code in C ++.

I was shocked to discover an elegant system consisting of a virtual machine interpreting bytecode in real time and generating full-screen vector motion. The result of this work was one of the best games of all time ...
')
All this fit on a flexible disk with a capacity of 1.44 MB and worked on 600 KB of RAM. Not bad for 1991! As usual, I put my notes in order - it will help someone save a few hours of work.

But ... what is the source code?

The source code for Another World has never been officially published, and there were no leaks either. People passionately in love with this revolutionary game, reverse engineer the executable DOS file.

In part, this was made possible due to the small size of the binary file (20 KB). Why was he so small? Because ANOTHER.EXE is not the game itself, but only a virtual machine:

• Storing bytecode.
• Making system calls.

The byte code performs all the game logic using its own opcodes, but uses system calls to perform “heavy” tasks such as drawing, playing music, sounds, and managing game resources.

Implementing only a virtual machine for the desired OS requires much less effort, so the game was ported by more than a dozen platforms:

• 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

Each time it was necessary only to compile the virtual machine under the OS - the byte-code remained the same!

Architecture

The executable file takes only 20 KB. It has the following scheme:



We see here four modules:

• Virtual Machine (virtual machine): manages the entire system.
• Resource Manager (resource manager): loads resources from a floppy disk when a virtual machine requests them.
• Sound / Music mixer: mixes noise when requesting a VM.
• Renderer (renderer): reads and renders vertices on VM request. Reads vertices from memory segments.

Interesting fact: the memory segment of the palettes actually contains several palettes used for beautiful effects of gradual color change.

When running, the executable file sets the value “0” for the software counter of the virtual machine thread ( 0x00 ) and starts interpreting. After that, everything is controlled bytecode.

Explaining the visualization process

The previous diagram shows three framebuffers. Two are needed because Another World implements double buffering programmatically, and the third is used as smart optimization:

The third frame buffer is used only once for background and scene compositing, and then reapplies its frame by frame using simple memcpy :


In this video, the rendering of the legendary screen of the first level of Another World is slowed down so that you can notice the rendering process. Everything is drawn using polygons and pixigons. The number of redrawing is very significant, but since the scene is generated only once, it is not so bad.

Interesting fact: this famous background consists of 981 polygons.

To visualize the full picture, I slowed down and rendered three frame buffers and what is displayed on the screen:


Here you can see very clearly:

• Double buffering with visualization performed in turn in the front / rear buffer.
• The background buffer is generated once and stored in the upper left buffer. It is then copied at the beginning of each frame.
• If the background changes (for example, in the case of stopping the car), the background buffer is updated to save even more space and time.

If you want to analyze the rendering in more detail, here is the full video .

Virtual Machine Another World

The page of Eric Chahi explains in detail the structure of the VM.

In the github code, you can see how each opcode is implemented. Everything is pretty simple to understand, with the exception of visualization operations. The trick is that the source code of the polygon segment in which the vertices are to be read is embedded with the identifier of the opcode.

Here are some screenshots from VM bytecode editor (Eric Shayi created it and gave it the name "script editor"):



Here it is noticeable how the label is lost: setvec 21 nag1 sets the instruction counter of stream 21 to the offset of the label “nag1”. In the bytecode, only the hard offset is visible.

Use Case Codes

The diagrams below show the invocation of operation codes by the virtual machine, which is actually a system call to the resource manager for loading four memory segments. This usually happens at the beginning of the game (the whole game is divided into 10 parts):



In the following diagram, the operation code is also a render system call, which requests drawing and receiving vertices. Codes of operations of visualization are a little more difficult because they contain instructions to addresses from which it is necessary to read tops. The selection of the target frame buffer is a completely independent opcode:



Note: the choice of where the renderer should read vertices (from the kinematic polygon segment or from the animation segment) is encoded using opcodeId.

Resource management

Resources are identified by a unique integer identifier. At startup, the resource manager opens MEMLIST.BIN and retrieves entries from it as follows:

 typedef struct memEntry_s { int bankId; int offset; int size; int unpackedSize; } memEntry_t; 

If VM requests resourceId, then resource manager:

• Finds it by opening the bank file (by bankId).
• Passes offset and reads size bytes into RAM.
• If size ! = unpackedSize , then the resource must be unpacked.

Some statistics about compression:

   : 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 

I did not waste time on the reverse development of the compression algorithm. The fact that the sound didn’t shrink very well brought me to the idea that the algorithm is sensitive to entropy ... so maybe this is a variation of the Huffman algorithm?

Of the 146 resources, 120 are compressed:

• Vector visualization plus compression on top of it gave a HUGE benefit (saving up to 62% of the space!).
• Sound compression is very inefficient: the savings are small, and resources occupy 47% of the floppy disk space.

An interesting fact: the initial screen saver (resource 0x1C ) with a duration of 3 minutes takes only 57,510 bytes after compression.

Memory management

As in all games of the 90s, memory was not allocated during gameplay. When you start the game engine received 600 KB of memory (does anyone still remember 640 KB of basic DOS memory?). These 600 KB were used as a stack distributor:



Free memory: the memory manager was able to free up memory one cycle back OR free all memory. In practice, the entire memory was released at the end of each of the 10 parts of the game.

Interesting fact: initially byte-code and vertices were stored in all 600 KB. But after two years of generating backgrounds from polygons / pixigons, the game was still far from complete. To speed up development, Eric Shayi decided to embed a hack into his remarkable architecture (at the cost of performance): the resource manager can load a background void copyToBackgroundBuffer(const uint8 *src); from a floppy disk into the background buffer ( void copyToBackgroundBuffer(const uint8 *src); ). Therefore, at the end of the base memory 32KB (320x200 / 2) were reserved.

An interesting fact: this hack was used with the release of Another World under Windows XP in 2005. All backgrounds were drawn by hand and downloaded directly from the hard drive without using the renderer and its pixigons:

Purist corner

If you are a purist and want to play only the original version, Another World works great in DosBOX:



Or you can play the version for Windows XP. I recommend to buy the Collector's edition , because it contains a lot of additional information, including technical notes by Eric Shayi:

And something else

I worked a lot on the code to make it easier to understand. Here is an example of how much it has become clearer.

Before:

 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; } } } } } 

After:

  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; } } } } 

• I used MACROS to get rid of confusing hard-coded values.
• Renamed variables.
• Added LOTS of comments.

Here is a “human readable” source code! Successful hacking.