Quake 3 Source Code Overview: Architecture (Part 1)

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

The engine is essentially an improved idTech2, but there are some interesting improvements. Key points may appear as a result:

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

• A system of virtual machines and related tools, which generally account for 30% of the code. From this point of view, idTech3 is a mini-operating system that provides system calls for three processes.
• Elegant network system based on snapshots and introspection of memory.
')
As usual, I wrote a lot of notes that I put in order and designed. I hope this will save some people time and encourage others to learn more code and become better engineers.

First contact

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

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

When it comes time to learn a big project, I prefer to use Xcode: fast backlight, keyboard shortcuts for finding definitions and string highlighting make the tool more powerful than VisualStudio. But opening a project with Quake3 revealed that XCode 4.0 cannot open the XCode 2.0 project.
In the end, I decided to use Visual Studio 2010 Professional on Windows 8. After installing the Productivity Power Tools to Visual Studio, it became more pleasant to work.
The first thing that struck me in Visual Studio is that instead of one project, it opened 8. 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 shows better 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 slight digression: the working title of idTech3 was “Trinity”. Since idTech4 was called “Neo”, I thought it was related to the movie “The Matrix” ... but id Software stated in an interview with firingsquad.com that they named the engine after the Trinity River in Dallas.

Architecture

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



Now let's look at the internal structure in the form of 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) of each impact, then to recreate the error. This design decision was discussed in detail in the .plan of 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 with bot.lib, which is a separate project due to its chaotic development history.

- the client part is responsible for predicting where objects are located (to compensate for the delay) and render the image. It is statically linked to the rendering project: a separate project that would allow Direct3D or even rendering software to be included is very simple.

Code

From a code point of view, here is a partially expanded loop illustrating the client and server events being processed and sent:

 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 I was studying the code.
An interesting thing can be noticed here, which perfectly illustrates how important virtual machines are: nowhere we see the RE_RenderScene call (a function that selects and gives 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 some object and makes a prediction, then OpenGL is called via 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:



On the pie chart, you can clearly see how unusual the proportions are, since tools account for 30% of the code.

This is partly because idtech3 implements the ANSI C compiler features: Open Source Little C Compiler (LCC) is used to generate bytecode for virtual machines.

Memory allocation

Two common allocators are used here:
Zone Allocator: running at runtime, allocating small and short-term memory
Hunk Allocator: works during loading level, large and long-term memory allocation, which loads the contents of pak files (geometry, maps, textures, animation).

I recommend reading

Quake History - Masters of Doom.
The two best compiler books to better understand Quake virtual machines.
Article to understand what is LCC Intermediate Representation