Quake source code analysis

I was delighted to study the Quake World source code and set out in the article everything I understood. I hope this will help those who wish to understand. This article is divided into four parts:

• Architecture
• Network
• Forecasting
• Visualization

Architecture

Quake Client

Quake learning should start with the qwcl project (client). WinMain entry WinMain is in sys_win.c . In short, the code looks like this:
')

  WinMain { while (1) { newtime = Sys_DoubleTime (); time = newtime - oldtime; Host_Frame (time) { setjmp Sys_SendKeyEvents IN_Commands Cbuf_Execute /*  */ CL_ReadPackets CL_SendCmd /* // */ CL_SetUpPlayerPrediction(false) CL_PredictMove CL_SetUpPlayerPrediction(true) CL_EmitEntities /*  */ SCR_UpdateScreen } oldtime = newtime; } } 

Here we can distinguish three main elements of Quake World:

• CL_ReadPackets and CL_SendCmd
• CL_SetUpPlayerPrediction , CL_PredictMove and CL_EmitEntities
• SCR_UpdateScreen visualization

The network layer (also called the Net Channel) outputs world information to the frames variable ( frame_t array). They are transmitted to the prediction layer, in which collisions are processed, and the data is output in the form of visibility indications ( cl_visedicts ) with a scope definition (POV). VisEdicts are used in the render layer along with the POV ( cl.sim* ) variables for rendering the scene.



setjmp :

Setting an intermediate code point, if something bad happens, the program returns here.

Sys_SendKeyEvents :

Receiving Windows messages, minimizing windows, etc. The corresponding update of the engine variable (for example, if the window is minimized, then the world is not rendered).

IN_Commands :

Getting information about the input from the joystick.

Cbuf_Execute :

In each game cycle, commands are executed in the buffer. Commands are generated mainly through the console, but they can come from the server or even by pressing a key.

The game starts with exec quake.rc in the command buffer.

CL_ReadPackets and CL_SendCmd :

Processing the network part of the engine.

CL_SendCmd intercepts mouse and keyboard input, generates a command, which is then sent.

Since Quake World used UDP, transmission reliability was guaranteed by the sequence / sequenceACK set in the netChannel packet headers. In addition, the last team was systematically sent again. On the client side, there were no restrictions on packet transmission, updates were sent as often as possible. From the server side, the message was sent to the client only if the packet was received and the sending speed was lower than the processing speed. This limit was set by the client and sent to the server.

The whole section "Network" is devoted to this topic.

CL_SetUpPlayerPrediction , CL_PredictMove and CL_EmitEntities :

Performed prediction in the engine and the calculation of collisions. They are mainly designed to combat network latency.

This topic is devoted to the entire section "Prediction".

SCR_UpdateScreen :

Visualization in the engine. In this part BSP / PVS are actively used. Here is the branching of code based on include / define . The Quake engine can render the world either programmatically or with hardware acceleration.

The Visualization section is entirely devoted to this.

Opening zip and compiling

Opening zip:

The q1sources.zip archive has two folders / two Visual Studio projects: QW and WinQuake .

• WinQuake is a code with a combined client and server code that works as a single process (ideally it should be two separate processes if DOS supported them). Network play was only possible on the LAN.
• QW is the “Quake World” project, in which the server and client must run on separate machines (note that the client WinMain is WinMain (in sys_win.c ), and the server entry point is main (also in sys_win.c )) .

I learned Quake World with openGL rendering. There are four subprojects in this project:

• gas2asm - utility for porting assembly code from GNU ASM to x86 ASM
• qwcl - Quake client
• QWFwd - proxy located in front of Quake servers
• qwsv - Quake server side

Compilation:

After installing Windows and the DirectX SDK, compilation in Visual Studio 2008 reveals one error:

 .\net_wins.c(178) : error C2072: '_errno' : initialization of a function 

Currently _errno is a Microsoft macro used for something else. You can correct these errors by replacing the variable name with _errno for example with qerrno .

net_wins.c

  if (ret == -1) { int qerrno = WSAGetLastError(); if (qerrno == WSAEWOULDBLOCK) return false; if (qerrno == WSAEMSGSIZE) { Con_Printf ("Warning: Oversize packet from %s\n", NET_AdrToString (net_from)); return false; } Sys_Error ("NET_GetPacket: %s", strerror(qerrno)); } 

Linker complains about LIBC.lib in the qwcl project. Just add it to the list of ignored libraries "Ignored Library" and the assembly of four projects will be executed.

Instruments

As an IDE, Visual Studio Express (free) came up perfectly. I recommend reading several books if you want to understand the engine more deeply on the basis of BSP / PVS, Id Software and Quake:



My bookshelf for Quake's source code week looked like this:

Network

The network architecture of QuakeWorld at one time was considered a terrific innovation. All subsequent online games used the same approach.

Network stack

The basic unit of information exchange in Quake was the . They are used to update the position, orientation, health, damage to the player, etc. TCP / IP has many excellent features that would be useful in real-time simulation (transmission control, delivery reliability, packet order retention), but this protocol could not be used in the Quake World engine (it was used in the original Quake). In first person shooters, information that is not received on time is not worth resending. Therefore, UDP / IP was selected. To ensure the reliability of the delivery and preserve the order of the packages, a network layer abstraction " NetChannel " was created.

From the point of view of OSI, NetChannel conveniently located over UDP:



So, to summarize: the engine mainly works with . When it needs to send or receive data, it assigns this task to the Netchan_Transmit and Netchan_Process from netchan.c (these methods are the same for the client and server).

NetChannel Header

The NetChannel header has the following structure:

Bit offset	Bits 0-15	16-31
0	Sequence
32	ACK Sequence
64	QPort	Teams
94	...

• Sequence is an int number initialized by the sender and increasing by one each time a packet is sent. Sequence used for many purposes, but the most important task is to provide the receiver with the ability to recognize lost / duplicate / extra UDP packets. The most significant bit of this integer is not part of the sequence, but a flag indicating whether (the ) contains reliable data (more on this later).
• The ACK Sequence is also an int , it is equal to the last received number of the sequence. Thanks to him, the other side of NetChannel can understand that the package has been lost.
• QPort is a bypass of the error of the NAT routers (see details at the end of the section). Its value is a random number set when the client starts.
• Commands: transmitted meaningful data.

Reliable messages

Unreliable commands are grouped into a UDP packet, it is marked with the last outgoing number of the sequence and sent: it does not matter to the sender whether he will be lost. Reliable commands are handled differently. The main thing is to understand that there can be only one unconfirmed reliable UDP packet between the sender and the receiver.

In each game cycle, when a new reliable team is generated, it is added to the message_buf array (controlled by the message variable) ( 1 ). The set of reliable commands is then moved from the message to the reliable_buf ( 2 ) array. This only happens if the reliable_buf empty (if it is not empty, it means that another set of commands has been previously sent and its receipt has not yet been confirmed).

Then the final UDP packet is formed: a NetChannel ( 3 ) header is added, then the contents of reliable_buf and the current unreliable commands (if there is enough space).

On the receiving side, the UDP message is parsed, the incoming sequence number is transmitted to the outgoing sequence ACK ( 4 ) (along with a bit flag indicating that the packet contains reliable data).

With the following message received:

• If the reliability bit flag is true, it means that the UDP packet is delivered to the receiver. NetChannel can clear reliable_buf ( 5 ) and is ready to send a new set of commands.
• If the reliability bit flag is false, then the UDP packet has not reached the receiver. NetChannel is retrying sending content reliable_buf . New commands are accumulated in message_buf . If the array is full, the client is reset.

Transmission control

As I understand it, transfer control is performed only on the server side. The client sends its status updates as often as possible.

The first transfer control rule that is active only on the server: send the packet only if the packet was received from the client. The second type of transfer control is “choke”, the parameter that the client sets with the console command rate . It allows the server to skip update messages, reducing the amount of data sent to the client.

Important commands

Commands contain a type code stored in a followed by useful information from the command. Perhaps the most important are commands giving information about the state of the game ( frame_t ):

• svc_packetentities and svc_deltapacketentities : update such objects as rocket tracks, explosions, particles, etc.
• svc_playerinfo : sends updates about the player’s position, last team, and team duration in milliseconds.

Read more about qport

Qport has been added to the NetChannel header to fix the error. Prior to qport, Quake server identified the client by the combination of “remote IP address, remote UDP port”. Most of the time this worked well, but some NAT routers can arbitrarily change their port translation pattern (remote UDP port). The UDP port becomes unreliable, and John Carmack (John Carmack) explained that he decided to identify the client by “remote IP address, Qport in the NetChannel header”. This fixed the error and allowed the server to change the target UDP response port on the fly.

Latency calculation

The Quake engine stores the 64 most recently sent commands (in the frame_t : frames array) along with senttime . They can be accessed directly by the number of the sequence used to transfer them ( outgoing_sequence ).

  frame = &cl.frames[cls.netchan.outgoing_sequence & UPDATE_MASK]; frame->senttime = realtime; //   

After receiving confirmation from the server, the time to send the command is obtained from sequenceACK . Latency is calculated as follows:

  //    frame = &cl.frames[cls.netchan.incoming_acknowledged & UPDATE_MASK]; frame->receivedtime = realtime; latency = frame->receivedtime - frame->senttime; 

Elegant solutions

Array index cycling
The network part of the engine stores the 64 most recently received UDP packets. A naive solution to looping through an array would be to use the integer division remainder operator:

 arrayIndex = (oldArrayIndex+1) % 64; 

Instead, a new value is computed with the binary AND operation for UPDATE_MASK. UPDATE_MASK is 64-1.

 arrayIndex = (oldArrayIndex+1) & UPDATE_MASK; 

This code looks like this:

  frame_t *newpacket; newpacket = &frames[cls.netchan.incoming_sequence&UPDATE_MASK]; 

Update: here is a comment received from Dietrich Epp regarding optimization of division operations with the remainder:

     ,        "".          :   file.c: unsigned int modulo(unsigned int x) { return x % 64; } unsigned int and(unsigned int x) { return x & 63; }  gcc -S file.c      file.s. ,    ,    !     ""    << 5  *32.      ,    ,   ,     << 5  & 63 "",    *32  %64  . --Dietrich .globl modulo .type modulo, @function modulo: pushl %ebp movl %esp, %ebp movl 8(%ebp), %eax andl $63, %eax popl %ebp ret .size modulo, .-modulo .globl and .type and, @function and: pushl %ebp movl %esp, %ebp movl 8(%ebp), %eax andl $63, %eax popl %ebp ret .size and, .-and 

Forecasting

We looked at the NetChannel abstraction for network data exchange. Now we will find out how latency is compensated by prediction. Here is the study material:

• Article by John Carmack himself.
• Another article ( archive ) from Valve about Half-life engine description (Half-life uses Quake engine).

Forecasting

Forecasting is probably the hardest, least documented and essential part of the Quake World engine. The purpose of forecasting is to defeat the latency, namely, to compensate for the delay necessary for the medium to transmit information. Forecasting is performed on the client side. This process is called “Client Side Prediction”. On the server side, lag compensation techniques are not applied.

Problem:



As you can see, the state of the game is “older” by half the amount of latency. If we add time to send the command, we need to wait for the full cycle (latency) to see the results of our actions:



To understand the Quake prediction system, you need to understand how NetChannel fills the frames variable ( frame_t array).



Each command sent to the server is saved in frames along with the senttime index netchannel.outgoingsequence .

When the server confirms the receipt of a command using sequenceACK , you can accept the sent command and calculate the latency:

 latency = senttime-receivedtime; 

At this stage, we know the world as it was latency / 2 back. In NAT, latency is quite low (<50 ms), but on the Internet it is huge (> 200ms), and it is necessary to perform prediction to simulate the current state of the world. This process is performed differently for the local player and other players.

Local player

For a local player, latency is reduced to almost 0 due to the extrapolation of what will be the state of the server. This is done using the last status received from the server and the “play” of all commands sent since that moment.



Therefore, the client predicts what his position on the server will be at t + latency / 2.

From a code point of view, this is done using the CL_PredictMove method. First, the Quake engine selects the sentime limit for the “playable” commands:

 cl.time = realtime - cls.latency - cl_pushlatency.value*0.001; 

Note: cl_pushlatency is a console variable (cvar) whose value is set on the client side. It is equal to the negative client latency in milliseconds. From this it is easy to conclude that: cl.time = realtime .

Then all other players are defined in CL_SetSolidPlayers (cl.playernum); how hard objects (so that you can test collisions) and “play” commands sent from the last received state to the moment: cl.time <= to->senttime (collisions are tested at each iteration using CL_PredictUsercmd ).

Other players

For other players, the Quake engine does not have “sent but not yet confirmed teams”, so interpolation is used instead. Starting from the last known position, cmd interpolated to predict the resulting position. Predicted position only, without angular rotation.

Quake World also takes into account the latency of other players. The latency of each player is sent along with the update of the world.

Code

The code for predicting and calculating collisions can be summarized as follows:

  CL_SetUpPlayerPrediction(false) CL_PredictMove | /*    */ | CL_SetSolidPlayers | | CL_PredictUsercmd | | PlayerMove |   CL_SetUpPlayerPrediction(true) CL_EmitEntities CL_LinkPlayers | /*    */ |    | | CL_SetSolidPlayers | | CL_PredictUsercmd | | PlayerMove CL_LinkPacketEntities CL_LinkProjectiles CL_UpdateTEnts 

This part is difficult, because Quake World not only performs predictions for players, but also recognizes collisions based on predictions.

CL_SetUpPlayerPrediction(false)

The first call does not perform the prediction, it only places the players in the positions received from the server (that is, with a delay in t-latency / 2).

CL_PredictMove()

This is where the local player moves:

• Orientation is not interpolated and runs completely in real time.
• Position and speed: all commands sent up to the current time ( cl.time <= to->senttime ) are applied to the last position / speed received from the server.

Learn more about updating position and speed:

• First, other players turn into solid objects (in their last known position, set in CL_SetUpPlayerPrediction(false) ) using CL_SetSolidPlayers .
• The engine cycles through all sent commands, checking for collisions and predicting the position using CL_PredictUsercmd . Collisions for other players are also tested.
• The resulting position and speed are stored in cl.sim* . They will be used later to set the viewpoint.

CL_SetUpPlayerPrediction(true)

In the second call on the server side, the position of other players at the current moment is predicted (but the movement is not performed yet). The position is extrapolated from the last known commands and the last known position.

Note: There is a small problem here: Valve recommends (for cl_pushlatency ) to predict the state of the local player on the server side at t + latency / 2. However, the position of other players is predicted on the server side at time t. Perhaps the best value for cl_pushlatency in QW was -latency / 2?

CL_EmitEntities

This is where the visibility guidelines are generated. Then they are transferred to the renderer.

• CL_LinkPlayers: Other players are moving, other players are turning into solid objects and collision detection is performed for their predicted position.
• CL_LinkPacketEntitiesPacket: objects from the last state received from the server are predicted and associated with visibility indications. That is why there is a lag for the released rocket.
• CL_LinkProjectiles: machining nails and other shells.
• CL_UpdateTEnts: standard update of light rays and objects.

Visualization

When developing the original game, the most effort was spent on the Quake renderer module. This is described in detail in the book by Michael Abrash and in the files of .plan by John Carmack.

Visualization

The scene visualization process is inherently associated with the BSP card. I recommend reading more about Binary Space Partitioning ( binary space splitting ) in Wikipedia. In short, Quake maps underwent extensive pre-processing. Their volume is recursively cut as follows:



This process created a BSP with leaves (the creation rules are as follows: select an existing polygon as a cutting plane and select a separator that cuts fewer polygons). After creating a BSP, PVS (Potentially Visible Set, potentially visible set) was calculated for each sheet. Example: Sheet 4 can potentially see leaves 7 and 9:



The final PVS for this sheet was saved as a bit vector:

Id sheet	one	2	3	four	five	6	7	eight	9	ten	eleven	12	13	14	15	sixteen
PVS for sheet 4	0	0	0	one	0	0	one	0	one	0	0	0	0	0	0	0

The result was a global PVS of about 5MB in size. It was too much for the PC in 1996. Therefore, PVS was compressed using length difference compression.

Compressed PVS for sheet 4	3	2	one	7

Encoded PVS contained only the number of zeros between ones. , (32767) PVS 20.

BPS PVS :

• BSP , .
• PVS , PVS BSP.
• BSP, .
• (Node) , .
• .
• .

Note: BSP is used several times. For example, to bypass the map from the nearest points to the distance for each active light source and mark polygons on the map.

Note 2: During software rendering, the BSP-tree was traversed from farthest points to the nearest ones.

Code analysis

In short, the visualization code can be represented as follows:

 SCR_UpdateScreen { GL_BeginRendering SCR_SetUpToDrawConsole V_RenderView | R_Clear | R_RenderScene | | R_SetupFrame | | Mod_PointInLeaf | | R_SetFrustum | | R_SetupGL | | R_MarkLeaves | | | Mod_LeafPVS | | | Mod_DecompressVis | | R_DrawWorld | | | R_RecursiveWorldNode | | | DrawTextureChains | | | | R_RenderBrushPoly | | | | DrawGLPoly | | | R_BlendLightmaps | | S_ExtraUpdate | | R_DrawEntitiesOnList | | GL_DisableMultitexture | | R_RenderDlights | | R_DrawParticles | R_DrawViewModel | R_DrawAliasModel | R_DrawWaterSurfaces | R_PolyBlend GL_Set2D SCR_TileClear V_UpdatePalette GL_EndRendering } 

SCR_UpdateScreen

Calls:

1. GL_BeginRendering(sets the values ​​of variables ( glx,gly,glwidth,glheight), later used in R_SetupGLto set the viewing area and projection matrix)
2. SCR_SetUpToDrawConsole (Determines the height of the console: why is it here, and not in the part related to 2D ?!)
3. V_RenderView (3D scene rendering)
4. GL_Set2D (switch to orthogonal projection (2D))
5. SCR_TileClear (Additional drawing of many 2D objects, console, FPS metrics, etc.)
6. V_UpdatePalette ( , openGL , , ..). v_blend
7. GL_EndRendering ( ( )!)

V_RenderView
:

1. V_CalcRefdef (, )
2. R_PushDlights (. )
3. R_RenderView

: R_PushDlights ( R_MarkLights ). BSP ( ), . BSP ( ). , . R_MarkLights , «Frames of Reference» ( dist = DotProduct (light->origin, splitplane->normal) - splitplane->dist; )).

R_RenderView

:

1. R_Clear ( GL_COLOR_BUFFER_BIT / GL_DEPTH_BUFFER_BIT)
2. R_RenderScene
3. R_DrawViewModel ( )
4. R_DrawWaterSurfaces ( GL_BEND/GL_MODULATE . sin cos gl_warp.c )
5. R_PolyBlend ( , V_UpdatePalette v_blend . ( ), )

R_RenderScene

:

1. R_SetupFrame ( BSP, «r_viewleaf» )
2. R_SetFrustum ( mplane_t[4] . .
3. R_SetupGL ( GL_PROJECTION, GL_MODELVIEW, glCullFace, Y Z, X Z Quake openGL.)
4. R_MarkLeaves
5. R_DrawWorld
6. S_ExtraUpdate ( , )
7. R_DrawEntitiesOnList ( )
8. GL_DisableMultitexture ( )
9. R_RenderDlights ( )
10. R_DrawParticles (, , ..)

R_SetupFrame

:

 r_viewleaf = Mod_PointInLeaf (r_origin, cl.worldmodel); 

Quake / BSP, .

Mod_PointInLeaf model.c, BSP ( BSP- model->nodes ).

:

• , , .
• BSP ( , BSP-) .

R_MarkLeaves

r_viewleaf BSP ( R_SetupFrame ), ( Mod_LeafPVS ) ( Mod_DecompressVis ) (PVS). BSP: node->visframe = r_visframecount.

R_DrawWorld

:

1. R_RecursiveWorldNode ( BSP , , ( R_MarkLeaves ), cl.worldmodel->textures[]->texturechain .)
2. DrawTextureChains ( , texturechain: cl.worldmodel->textures[]. . .)
3. R_BlendLightmaps ( , ).

Note:

This part uses the notorious openGL “immediate mode”, while it was considered the “last word of technology”.

In R_RecursiveWorldNodemost of the clipping operations are performed. A node is shut down if:

• Its contents are solid objects.
• Sheet was not marked in PVS ( node->visframe != r_visframecount)
• Sheet does not pass clipping on the pyramid of visibility.

MDL format

The MDL format is a set of fixed frames. The Quake engine does not interpolate the position of the vertices to smooth the animation (therefore, a high frame rate does not improve the animation).

Elegant solutions

Elegant leaf

tagging A naive approach to leaf tagging BSP for rendering is to use a boolean variable isMarkedVisible. Before each frame you need:

1. Set the values ​​of all boolean variables to false.
2. PVS true.
3. if (leave.isMarkedVisible)

Quake ( r_visframecount variable). :

1. PVS leaf.visframe = r_visframecount
2. if (leaf.visframe == r_visframecount)

R_SetupFrame « » BSP while.

  node = model->nodes; while (1) { if (node->contents < 0) return (mleaf_t *)node; plane = node->plane; d = DotProduct (p,plane->normal) - plane->dist; if (d > 0) node = node->children[0]; else node = node->children[1]; } 

openGL ( glBindTexture(GL_TEXTURE_2D,id) ) . , , , .

 cl.worldmodel->textures[textureId]->texturechain[] 

After clipping is complete, texture chains are drawn in order. Thus, the total N texture switching is performed, where N is the total number of visible textures.

  int i; for ( i = 0; i < cl.worldmodel->textures_num ; i ++) DrawTextureChains(i);