Joel's Weblog: Quake 2 Source Code Commentary

Quake 2 Source Code Commentary

Beginning to look at someone else's source code for a large project, is a daunting task. It can be overwhelming at first. Thus, before diving into the Quake 2 source code, I wanted to see if I could get a head start based on someone else's time and effort already spent exploring the code.

Searching the Internet, I am unable to find anything, thus I decided to record my own thoughts and observations as I look at the source code, in hopes that it may be of some use to someone else. This will at first be mostly a collection of my random thoughts and observations as I proceed, and may perhaps one day be organized into an more intelligible document.

Note that at the moment, this is organized in web-log fashion, with the most recent addition at the top.

1/19/2005

The renderer, examined yesterday, does not seem to do any sorting based on texture.  It does sort the entities based on cache proximity, but not the textures.  As the surfaces are being drawn, though, if the texture to be drawn is already set as the current texture, then time is saved by not resetting the texture state.

1/18/2005

Question: where/how does Pmove() get called?

Server:

SV_InitGameProgs() in sv_game.c sets the Pmove member of a game_import_t structure to the Pmove() function.  (Reminder: the game import struct is pointers in the server passed to the game.  The game export struct is filled with pointers in the game, and is passed to the server.)  This is the only place in the server where this function is refered to.

Game:

ClientThink() in p_client.c calls gi.Pmove().


Client:

CL_PredictMovement() in cl_pred.c calls Pmove()
which is called by CL_Frame() in cl_main.c


Question: how is the stair climbing motion smoothed

CL_CalcViewValues() in cl_ents.c has code commented mentioning smoothing out stair climbing.
which is called by CL_AddEntities(), which sends entities, particles, and lights to the renderer.

in CL_CalcViewValues(), the renderer's vieworg (I assume this is the camera position) is moved down by an amount proportional to cl.predicted_step, and (it looks like) proportional to the amount of time left until 100 time units after the predicted stair-step took place.  (quantities utilized: cls.realtime, cl.predicted_step_time, and cl.predicted_step)

cl (client_state_t) and cls (client_static_t) are both global variables (defined in cl_main.c)

cls.realtime  holds the current game time


In CL_PredictMovement(), after a Pmove, if the change in height of the player is >63 but <160, and the player is on the ground, then 
cl.predicted_step is set to this change in height *0.125, and
cl.predicted_step_time is set to the time (in milliseconds) halfway between the last frame and this one (i.e. now - frametime/2)

Question:  why the *0.125?  This must be some scaling factor between the world coords and the renderer, since the player (predicted) position is also scaled by 0.125.  I read somewhere that one game unit in Quake equals 1.5 inches; this happens to be 0.125 feet.  Perhaps this is the scaling factor here.  This would indicate that while the game uses units equal to 1.5 inches (1/8 of a foot), the renderer uses feet.



Rendering...
SCR_UpdateScreen() (cl_scrn.c) calls
V_RenderView()	(cl_view.c) which makes the following calls:
	V_ClearScene()
	CL_AddEntities()	(build a list of entities to draw)
	V_TestParticles()
	V_TestEntities()
	V_TestLights()
the entities are sorted, then
	re.RenderFrame()
	SCR_DrawCrosshair()

apparantly the server rounds to nearest 1/8 foot (thus planes and surfaces must be on a 1/8 foot boundary.  Thus the camera is nudged by 1/16 in each axis to prevent the camera from lying exactly on any surface e.g. water.


re.RenderFrame() is set to R_RenderFrame in GetRefAPI in r_main.c
also in 				  GetRefAPI in gl_rmain.c
(incidentally, re.RenderFrame() is called in a few other places too.

the GL version of R_RenderFrame() calls:
	R_RenderView()
	R_SetLightLevel()
	R_SetGL2D()

R_RenderView() calls:
	R_PushDlights()
	qglFinish()
	R_SetupFrame()	sets up matrices and other things
	R_SetFrustum()  sets up 4 frustum planes
	R_SetupGL()	sets up GL state eg viewport, matrices, culling, blending
	R_MarkLeaves()	determines which nodes and leaves are potentially visible
	R_DrawWorld()
	R_DrawEntitiesOnList()
	R_RenderDlights()
	R_DrawParticles()
	R_DrawAlphaSurfaces()
	R_Flash()


r_worldmodel is of type model_t (gl_model.h)

R_DrawWorld() calls:
	R_ClearSkyBox()		invalidates the skybox mins and maxs
	R_RecursiveWorldNode()
	DrawTextureChains()
	R_BlendLightmaps()
	R_DrawSkyBox()		draws 6 faces
	R_DrawTriangleOutlines()


R_RecursiveWorldNode()
returns immediately if: is a solid region, is not potentially visible, bounding box is outside the frustum

if a leaf, mark each surface that should be drawn
if not a leaf:
Call R_RecursiveWorldNode() on the near side child
do drawable stuff for this node, then
Call R_RecursiveWorldNode() on the far side child.
for the current node, call R_AddSkySurface() for each sky surface
if translucent, add to texturechain (linked list of surfaces)
otherwise for each surface, call GL_RenderLightmappedPoly()

1/12/2005

Pmove(pmove_t) in pmove.c appears to be the function used by both the server and the client to move the player.

the pmove_t struct is in q_shared.h  Among other things, it looks like it has the bounding box for the player, the groundentity for the player, the waterlevel for the player, a pointer to the trace function to use, etc.  It also contains a pmove_state_t struct, which is the information necessary for client side movement prediction.  It contains the player's position, velocity, 

Pmove() calls PM_FlyMove if flying.  Otherwise calls:
PM_CheckDuck()
PM_CatagorizePosition()		(to set groundentity, watertype, and waterlevel)
PM_DeadMove()			(if dead)
PM_CheckSpecialMovement()
For normal movement, it calls
PM_CheckJump()
PM_Friction()
possibly PM_WaterMove() or PM_AirMove()
PM_CatagorizePosition()		(again)
PM_SnapPosition()


PM_CatagorizePosition()
works by doing a trace from the current position to one unit down.
if didn't collide or the collide plane is too steep, then we're not on the ground.
Checks first if vertical velocity is really large upward (don't do anything)
Also, if vertical velocity is large enough downward, then set a timeout to prevent a jump from occuring too soon.
Also, this ground entity is saved in an array as an entitiy that the player is touching.

As for water level, it can be 1, 2, or 3.
1: point one unit above feet is in water
2: point halfway between feet and eyelevel is in water
3: point at eyelevel is in water
These 3 points are checked in that order, calling pointcontents()

PM_CheckSpecialMovement() checks for ladder, water jump, and jump out of water.

PM_CheckJump() sets a flag when the player jumps and clears it when the player releases the jump
button (i.e. the upward desired move is no longer big enough) to prevent repeated jumps by holding the jump button.  If a jump happens, then an amount is added onto the upward velocity, and clamps upward velocity to a lower bound.

PM_Friction() handles ground and water friction
if speed is less than 1 unit, then horizontal movement is clamped to zero
if the player is on the ground, and the surface is not slick or a ladder,
then change in speed is computed as a proportion of the speed
same if in water (and not on a ladder), but friction is multiplied by the waterlevel
the change in speed is subtracted from the current speed and the velocity rescaled.

PM_AirMove() is for normal movement on ground and jumping.
computes desired horizontal velocity.
calls PM_AddCurrents() for water currents, ladder movement, and conveyor belts
gets speed and normal dir for desired vel.
clamps desired vel to max speed (different whether ducked or not)
ladder case is handled first calling PM_Accelerate and PM_StepSlideMove
otherwise, if we're on the ground (i.e., there is a groundentity) then the vertical velocity is set to zero and calls PM_Accelerate().
Then gravity is subtracted from velocity, and PM_StepSlideMove is called only if there is a horizontal movement (no need to fall since we are on the ground)
Otherwise, if we're not on ground, then call PM_AirAccelerate, subtract gravity and call PM_StepSlideMove().


PM_Accelerate()
takes a desired direction and speed (and acceleration constant)
The component of current velocity in this direction is computed.  The difference in the desired and the current component is computed, and a portion of the desired velocity is computed (based on the acceleration contstant).  This portion is is clamped to make sure it's not accidentally greater than the desired increase in speed.  This value is now added on to the current velocity.
The result of this is (given a constant desired velocity) the current velocity is changed, linearly over time to the desired velocity.  (It would be interesting to try modifying this so that the amount of change is instead proportional to the difference between the desired and current velocities.)

PM_AirAccelerate appears to be exactly the same, but clamps the desired speed to a maximum speed.


1/10/2005
Looking at SV_movestep() in m_move.c

This is the fuction that causes an entity to step up stair steps.
This is done by doing a trace straight up and down, from one STEPSIZE 
above a point to one stepsize below the point.  If allsolid, then it's 
impossible, if startssolid then try just going from the point to one 
stepsize below it.  If the trace encounters no obstacle, then the ground 
got pulled out from under or we walked off a cliff or something.  


what does the relink argument do?


So, my question is, what happens when there is a wall alongside a 
staircase and the user walks into the corner where a stair step and the 
wall meet.  Then this vertical trace will be allsolid, entirely inside the 
wall, whereas what we would like is to slide along the wall and up the 
stair.

how does gi.pointcontents() work?
where,when is SV_movestep() called? ans: only in SV_StepDirection() and 
M_walkmove(), both in m_move.c

when a horizontal movement is attempted by the entity, a horizontal trace 
is not performed--only the vertical trace at the ending location, to check 
for the step.  Wouldn't this allow moving through walls?

I attempted bypassing SV_movestep() and recompiling.
The only apparent result is that the monsters aren't able to move.  The 
(client) player is still able to climb stairs, so the player stairclimbing 
code must be elsewhere.

pmove.c looks promising (is this "player move"?)
It's in qcommon\ so that both the client and server can call its 
functions.
Two promising functions: 
PM_StepSlideMove_() and 
PM_StepSlideMove()

PM_StepSlideMove_() appears to compute a sliding movement very similar to 
that in SV_FlyMove().
PM_StepSlideMove() uses the previous function to compute the player 
movement.  Two movements are computed--a "down" movement for regular 
moving and an "up" movement for stepping.  The "down" movement is just a 
regular sliding movement using the current velocity.  The "up" movement is 
computed by jumping straight up STEPSIZE (checking to make sure that 
position is not a colliding one), then computing a sliding movement using 
the current velocity, then doing a trace straight down a STEPSIZE.   
Whichever movement ("up" or "down") resulted in the larger horizontal 
distance is the one we use (alternate code used the movement that had the 
largest distance along the direction of the velocity), unless the "up" 
move landed us on a plane that is too steep (i.e., it was too steep for us 
to have stepped up onto it.)

I'm not exactly sure what the last line of this function is for.



12/22/2004
SV_RunGameFrame calls ge->RunFrame
ge gets assigned in SV_InitGameProgs() in sv_game.c using Sys_GetGameAPI()
Sys_GetGameAPI() is in sys_win.c
Sys_GetGameAPI() loads the game dll (e.g. gamex86.dll) by name
and calls "GetGameAPI" from the dll to obtain the struct that will get 
assigned to ge.  ge stands for "game export".  It looks like ge gets 
filled with all the game functions that the server will need.  The server 
passes in a "game import" (gi) struct containing all the server functions 
that the game needs.

This function can be found in g_main.c
so, ge->RunFrame points to G_RunFrame

apparently G_RunFrame always advances the world by 0.1 seconds, not by 
elapsed time.  interesting.  then how do we get a frame-rate of greater 
than 10fps?

The game makes the following calls once per 0.1 seconds?
// choose a client for monsters to target this frame
	AI_SetSightClient ();
calls G_RunEntity on each entity (including the world)
calls M_CheckGround(ent) to see if the ground under the entity moved
// see if it is time to end a deathmatch
	CheckDMRules ();
// see if needpass needs updated
	CheckNeedPass ();		this is for passwords
// build the playerstate_t structures for all players
	ClientEndServerFrames ();

G_RunEntity(ent) makes the following calls
	ent->prethink
	One of:
		SV_Physics_Pusher (ent);	(for pushable things like 
doors I think)
		SV_Physics_None (ent);
		SV_Physics_Noclip (ent);
		SV_Physics_Step (ent);		(for players and monsters 
I think)
		SV_Physics_Toss (ent);		(for items and corpses and 
stuff; basic freefall/bounce)

ground is any surface normal with positive z

SV_Physics_Step() calls:
	M_CheckGround()		see if we're on the ground
	SV_CheckVelocity()	// bound velocity
	SV_AddRotationalFriction()	if any angular velocity
	SV_AddGravity()			if airborn
		TODO: findout what hitsound is
	apply friction to velocity in the vertical direction for flying 
and swimming monsters.
TODO: see what M_CheckBottom does
	if player is moving:
		apply friction to x and y directions
		SV_FlyMove()
		gi.linkentity()
		G_TouchTriggers()
		gi.sound() 		play sound if player wasn't on 
ground but now is.
// regular thinking
	SV_RunThink(ent)	


SV_FlyMove handles moving according to the entity's velocity, calling 
collision detection (gi.trace() (which is SV_Trace)), and sliding along 
surfaces.
We only loop a specified number of times (4), each time constraining the 
velocity to be parallel to the surface.  Or, if we collide with 2 surfaces 
without moving (and constraining velocity to any of the surfaces still 
results in a velocity component entering one of the surfaces), then 
constrain velocity along the crease between the surfaces.
Or, if we are in contact with >2 surfaces without moving and no valid 
constraining of the velocity is possible, then set velocity = 0.
	

SV_Trace() in sv_world.c does collision detection for a moving (axis 
aligned) box.  It is called when any entity moves.
It calls CM_BoxTrace() to check collision with the world
and 	   SV_ClipMoveToEntities() to check collision with other solid 
entities

CM_BoxTrace is in cmodel.c
It has a few special cases:
	Stationary box: calls CM_BoxLeafnums_headnode() and 
CM_TestInLeaf()
	Moving single point (box size 0) and general case: calls 					
CM_RecursiveHullCheck()

I assume CM_RecursiveHullCheck() traverses the BSP.
When a leaf is reached, CM_TraceToLeaf is called.


CM_TraceToLeaf()
Checks all brushes in the leaf
marks each brush as it's checked to make sure we don't check the same 
brush twice in different leaves.  Looks like each time a trace is done, a 
checkcount is incremented and each node in the bsp has a checkcount 
variable that is compared to the current check number.
Calls CM_ClipBoxToBrush() for each brush
if this causes the movement to goto zero, then we're done with the entire 
trace

ClipBoxToBrush()
checks if brush has no sides
loops through all the sides


Question: Where is the code for stair-climbing?



12/21/2004
Looking at CL_Frame()

The client makes the following calls once per frame:
	IN_Frame()		(input?)
// fetch results from server
	CL_ReadPackets ();
// send a new command message to the server
	CL_SendCommand ();
// predict all unacknowledged movements
	CL_PredictMovement ();
	SCR_UpdateScreen ();	(render the scene)
// update audio
	S_Update ( );	(passing it the player position and orientation)
	CDAudio_Update();
// advance local effects for next frame
	CL_RunDLights ();
	CL_RunLightStyles ();
	SCR_RunCinematic ();
	SCR_RunConsole ();


Looking at SV_Frame()
The server makes the following calls once per frame:
// check timeouts
	SV_CheckTimeouts ();		(see if we lost a connection to a 
client)
// get packets from clients
	SV_ReadPackets ();
// update ping based on the last known frame from all clients
	SV_CalcPings ();
// give the clients some timeslices
	SV_GiveMsec ();
// let everything in the world think and move
	SV_RunGameFrame ();
// send messages back to the clients that had packets read this frame
	SV_SendClientMessages ();
// save the entire world state if recording a serverdemo
	SV_RecordDemoMessage ();
// send a heartbeat to the master if needed
	Master_Heartbeat ();		(I'm not sure what 'master' is)
// clear teleport flags, etc for next frame
	SV_PrepWorldFrame ();


12/20/2004
Once per message loop, WinMain calls Qcommon_Frame, with the number of elapsed milliseconds, which in turn calls SV_Frame and CL_Frame.
The server calls the 'game' (SV_Frame() calls SV_RunGameFrame() calls ge->RunFrame() )

and the client calls the 'refresh' (CL_Frame() calls SCR_UpdateScreen())

calls
	V_RenderView
calls
	re.RenderFrame()
which is a function pointer to
	R_RenderFrame()		(in r_main.c)
calls
	R_EdgeDrawing()
calls
	R_RenderWorld()		(in r_bsp.c)
which apparently renders the bsp tree by calling
	R_RecursiveWorldNode()
which renders faces (from visible leaf nodes) front to back calling
	R_RenderFace		(in r_rast.c)


12/17/2004
Initial observations:

Directory tree:

// these appear self-explanatory.  From Michael Abrash's "Ramblings" I recall
// that the client in Quake 1 handles basic simulation and rendering, while the
// server handles the authoritative simulation.  Player input is received by the
//client, sent to the server, and game updates are sent from server to client.
	client // some, not all, files with cl_*  Appears to be mostly audio, input and view/display stuff.
	server // files easily recognizable as server.h or sv_*.c

// things that aren't client and aren't server?
// appears to contain the game logic and physics
	game	

// the renderer, I suppose.  Called by the client?
	ref_gl
	ref_soft

// Capture the flag addon
	ctf	

// wrappers for the os specifics
	irix
	linux
	solaris
	win32
	null

// donno yet
	qcommon		// apparently stuff used by both client and server
	rhapsody	// ???

We're left with many questions.  Let's move on...

-------------------------------------------------
Opening the VC6 project reveals 5 projects:
ctf
game
quake2
ref_gl
ref_soft

Okay... why 5 projects?  What's the difference between 'game' and 'quake2'?

'game' seems to have mainly files from the 'game' directory (makes sense), so just game logic.

'quake2' contains the client and server

Still, why are 'game' and 'quake2' separate projects?  For that matter why is the renderer 2 additional separate projects?  Doesn't a project correspond to a resulting executable?

Answer: 'ctf' and 'game' both build gamex86.dll
'quake2' builds quake2.exe
'ref_gl' builds ref_gl.dll
'reg_soft' builds ref_soft.dll

-------------------------------------------------

Well, since at this point in time, I am most interested in the world-models/renderer, I'll start with ref_gl.

The 'ref_gl' project has all the source files from the 'ref_gl' directory plus:
win32\glw_imp.c
win32\glw_win.h
win32\q_shwin.c
win32\qgl_win.c
win32\winquake.h
game\q_shared.c
game\q_shared.h
qcommon\qcommon.h
qcommon\qfiles.h
client\qmenu.h
client\ref.h

plus a nonexistant ref_gl.h




gl_model.h seems to contain the definitions for structs handling brushes and polygons forming the world model

qfiles.h contains data about all the quake data file formats

This is just a guess, but it seems that types beginning with d (like dmodel_t) correspond to how the information is formatted in a data file, while types beginning with an m (like mmodel_t) correspond to how quake stores the information in memory.

I believe ref_ stands for 'refresh'.

win32\sys_win.c contains WinMain()
win32\vid_dll.c contains MainWndProc()

Attempting to build everything (Release) resulted many, many warnings, and 2 errors (both caused by 'ref_soft'; the others compile fine)

Joel's Weblogs

Quake 2 Source Code Commentary

1/19/2005

1/18/2005

1/12/2005

1/10/2005

12/22/2004

12/21/2004

12/20/2004

12/17/2004