Quake 3 Source Code Review: Architecture (Part 1)

Since I had one week before my next contract, I decided to end my id article cycle. After Doom , Doom Iphone , Quake1 , Quake2 , Wolfenstein iPhone and Doom3 , I decided to study code that I had not yet reviewed: idTech3 - 3D Quake III engine and Quake Live.

The engine is essentially an improved idTech2, but there are some interesting enhancements. The key points may look as follows:

• Part 2: a dual-core visualization tool with materials based on shaders (created through OpenGL Fixed Pipeline)
• Part 3: a new network model based on snapshots
• Part 4: virtual machines play a major role in the engine, combining Quake1 mobility / security and Quake2 speed
• Part 5: a new artificial intelligence for bots.
I was particularly impressed with:

• The virtual machine system and related tools, which together account for 30% of the code. From this point of view, idTech3 is a mini-operating system that provides system calls of three processes.
• An elegant network system based on images and self-analysis of memory.

As usual, I wrote a lot of notes , which I put in order and designed. I hope this saves time for some people and encourages others to learn more code and become better engineers.

First contact

Since the esteemed ftp.idsoftware.com has recently been closed, you can find the code on id Software's GitHub account .

git clone https://github.com/id-Software/Quake-III-Arena.git 

When it comes time to study a large project, I prefer to use Xcode: quick highlighting, keyboard shortcuts to find definitions and string highlighting make the tool more powerful than VisualStudio. But opening a project with Quake3 showed that Xcode 4.0 could not open an Xcode 2.0 project.
In the end, I decided to use Visual Studio 2010 Professional on Windows 8. After installing Productivity Power Tools to Visual Studio, it became more pleasant to work.
The first thing that struck me in Visual Studio was that it opened 8. Instead of one project, not all of them are used, depending on the type of assembly: DEBUG or RELEASE (in particular, game, cgame and q3_ui: virtual machine projects). Some of the projects are not used at all (splines and ui).
The table better shows which project affects which modules:

Projects	Type	DEBUG Builds	RELEASE Builds	Comments
botlib	Static library	botlib.lib	botlib.lib	AI
cgame	Dynamic library / bytecode	cgamex86.dll	-
game	Dynamic library / bytecode	qagamex86.dll	-
q3_ui	Dynamic library / bytecode	uix86.dll	-
quake3	Executable	quake3.exe	quake3.exe
renderer	Static library	renderer.lib	renderer.lib	Opengl based
Splines	Static library	Splines.lib	Splines.lib	Used NOWHERE!
ui	Dynamic library / bytecode	uix86_new.dll	-	Used for Quake III Arena.

A small digression: idTech3's working name was “Trinity”. Since idTech4 was called “Neo”, I thought it was related to the movie “The Matrix” ... but id Software claimed in an interview with firingsquad.com that it was named after the “Trinity River in Dallas” engine.

Architecture

A convenient way to understand the architecture: first you need to consider software as a black box receiving input signals (arrows at the top left) and generating outputs (arrows at the bottom):



Now we will see the internal structure as a white box with 6 modules (quake3.exe, renderer.lib, bot. lib, game, cgame and q3_ui) interacting as follows:



You need to understand 2 important things in the project:

• Each input signal (keyboard, win32 messages, mouse, UDP socket) is converted to event_t and placed in a centralized event queue (sysEvent_t eventQue [256] ) It also allows you to record (keep a log) each impact, then to recreate the errors. This design decision was discussed in detail in .plan by John Carmack on October 14, 1998.

• Explicit separation of client and server (this was outlined in Q&A, which I did with John Carmack.

- The server part is responsible for maintaining the state of the game, determining what clients need and connecting them over the network. It is statically linked to bot.lib which is a separate project because of its chaotic history of the development.

- the client side is responsible for predicting where the objects (for delay compensation) and the image rendering it is statically linked into the project rendering separate project that poses. olil to Direct3D or even rendering include very simple.

The code

From a code point of view, here is a partially deployed loop illustrating the processed and dispatched client and server events:

int WinMain(HINSTANCE hInstance, HINSTANCE hPrevInstance, LPSTR lpCmdLine, int nCmdShow)
    {
        Com_Init
        NET_Init
        while( 1 )
        {
            // Общий код
            IN_Frame()  // Добавление Win32 событий джойстика и мыши как event_t в общую очередь событий
            {
	             IN_JoyMove                                    
	             IN_ActivateMouse
	             IN_MouseMove
            }
            Com_Frame
            {
                 // Общий код
                 Com_EventLoop    // Pump win32 message, UDP socket and console commands to the queue 
                                                                      // (sysEvent_t eventQue[256]) 
                 Cbuf_Execute
                 // Код сервера
                 SV_Frame
                 {
                     SV_BotFrame                                 // переход к bot.lib
                     VM_Call( gvm, GAME_RUN_FRAME, svs.time )    // Переход к VM игры, где выполняется
                                                                      // игровая логика
                     SV_CheckTimeouts
                     SV_SendClientMessages          // послать снимок или изменение снимка 
                                                                   // подключившемуся клиенту
                 } 
                 // Common code
                 Com_EventLoop
                 Cbuf_Execute
                 // Client code
                 CL_Frame
                 {
                     CL_SendCmd                                 // кладем событие в очередь и
                                                                    // отправляем команды на сервер
                     SCR_UpdateScreen
                        VM_Call( cgvm, CG_DRAW_ACTIVE_FRAME);   // отправляем сообщение
                                            // на клиентскую VM (do Predictions).
                             or
                        VM_Call( uivm, UI_DRAW_CONNECT_SCREEN); // если меню видимо, сообщение отправлено
                     S_Update                                   // обновить буфер звука
                 }
            }
        }
    }

Here is a fully expanded loop that I used as a map while studying the code.
An interesting thing can be noticed here, which perfectly illustrates how important virtual machines are: nowhere do we see a call to RE_RenderScene (a function that selects and issues OpenGL commands). What happens instead:

1. Quake3.exe sends a client VM message: CG_DRAW_ACTIVE_FRAME, which signals that an update is needed.
2. The virtual machine selects an object and makes a prediction, then OpenGL is called through the Quake3 system call (CG_R_RENDERSCENE).
3. Quake3.exe receives a system call and actually calls RE_RenderScene.

Statistics

Here are some statistics from cloc:



The pie chart clearly shows how unusual the proportions are, since tools occupy 30% of the code.

This is partly because idtech3 implements the ANSI C compiler features: The Little C Compiler (LCC) is an open source code used to generate bytecode for virtual machines.

Memory allocation

Two usual allocators were used here:
Zone Allocator: works at runtime, allocation of small and short-term memory
Hunk Allocator: works at runtime loading, large and long-term memory allocation into which the contents of pak files are loaded (geometry, maps, textures, animation).

I recommend reading

According to the history of Quake - Masters of Doom.
Two best compiler books to better understand Quake virtual machines.
An article to understand what LCC Intermediate Representation is.