Information Visualisation utilising
3D Computer Game Engines

Case Study: A source code comprehension tool

By Blazej Kot; Project supervised by: Burkhard Wuensche, John Hosking, John Grundy

Tool Implementation

The dox2html Tool

The purpose of this tool is to take output from the doxygen[30] source code documentation tool, a set of HTML pages, and to remove extraneous information and complicated HTML elements, outputting files in a format that will be simple and fast to parse within the Quake 3 VM environment.

This tool is implemented in 420 lines of C++, in the file dox2html.cpp. The tool as written will only run on windows, but should be easy to port. The code is reasonably well documented, so the reader should refer there for any detailed implementation details. For the purposes of the present discussion, only the output format of this tool will be discussed in detail. For an example of how to use this tool see the Example section.

One file of output is created for each initial source code file (Doxygen creates many additional files, which are analysed by dox2html). Despite the name, the output of the tool is not actually valid HTML, but it is a very simplified form of HTML. There is no header or footer. For the most part, the output contains a verbatim copy of the original source file. Line breaks are kept in the same place as in the original. The normal HTML escaping of &, < and > as &amp &gt &lt exists in the output. Two HTML tags are placed within the output files by the dox2html.

The first tag is for links. It takes the form of

<a href="targetfilename#targetlinenumber">text</a>

much like a normal HTML link. However, the anchor points (the number following the #), are not explicitly declared inside the target file, as one would expect from standard HTML. Rather, the Quake 3 mod parses this number, then goes to target file, and then scrolls to the line number.

The second tag is for syntax highlighting. Doxygen uses a CSS-based system for syntax highlighting, so the tags it puts in the source files are just left in place by dox2html. These tags look like <span class="classtype">text</span>. Classtype is one of: keyword, keywordtype, keywordflow, comment, preprocessor, stringliteral or charliteral. Each of these has a corresponding colour and style defined in the CSS file by Doxygen. Similar colours to these are used by the Quake 3 mod to display the syntax highlighting.

Currently, "dox2html" is incomplete, and some links in the resulting files are "dead" (have an invalid or null target), and some links in the original documentation are omitted (specifically, the ones that have to do with structs in C, since Doxygen uses a special format for documenting these, which dox2html currently just skips over.) This something that could be improved in the future.

The Quake 3 Modification

This section attempts to give a detailed overview of all the modifications made to the Quake 3. This section is written with two purposes in mind: to help future coders extend the present implementation of the tool, and to allow other people to judge the difficulty of using Quake 3 for information visualisation. This, after all, is the main aim of this project. This section was written after the modifications were made, so there may be some omissions or minor factual errors below. All modifications or additions were tagged with a \\bkot comment, so searching the source code for bkot should bring up all the modifications and additions.

The sections below document the modifications, one file at a time, to the Quake 3 game logic code running on the three Quake 3 Virtual Machines.

Server-side Modifications (game.qvm)

Modifications to bg_public.h

This file contains declarations of several data structures types that are used by both the client and server ("bg" refers to Both Games).

• A new #define was added, #define PMF_FRICTIONLESS 32768. This is used in the pm_flags field of the pmove_t struct. PMF refers to Physical Move Flag. There are some existing PMF_s, such as walking, flying and swimming. PMF_FRICTIONLESS was added as this is the type of movement the player undergoes when they teleslide to a file. None of the existing PMF_ types provided the necessary behaviour for telesliding (moving at a constant velocity, through walls).
• A new element was added to the holdable_t enum, HI_SOURCEFILE. "HI" refers to Holdable Item. This is used by the code to keep track of what type of item the player is carrying.

Modifications to g_local.h

This file contains declarations only used by the server code ("g" is for "game.qvm")

• One function declaration was added: Drop_Sourcefile(). This function is used when a player wants to drop a sourcefile they are carrying.
• Two fields were added to the gentity_s struct. One instance of this struct is used by the server to keep track of the state of each entity in the game. The added fields are only guaranteed to have valid values if the entity is a sourcefile. The added fields are:
• int itemid This is a number which is unique for each sourcefile. It corresponds to the itemid field set in Q3Radiant, the map editing tool for Quake 3. The itemidth line in the filenames file contains the filename of the file represented by this sourcefile entity.
• int users This is a set of 32 bits, one for each of the first 32 clients to join the game. If bit number n is set (LSB=0), this indicates that player n is currently "using" this entity, that is that they have walked up to it and are viewing the contents of the file.
• Thirteen fields were added to the gclient_s struct. One instance of this struct is used by the server to keep track of the state of each client (player) in the game.
• int using_entity This stores the index in the global g_entities array (in which all entity data structures are kept) of the entity that this client is currently using (viewing). 1 indicates the client is not viewing any. This information is redundant with the users field of the entity struct, but is kept here to speed up the passing of scroll and draw events between users of the same file.
• int touch_sourcefile_frame This stores the game time when this client last touched a source file entity. This is needed to avoid repeatedly drawing the contents of a sourcefile when a player walks into a sourcefile and stops. A message is only sent to the UI if the user touches a file, and the client touch_sourcefile_frame is sufficiently far in the past (more than 0.5 seconds).
• int target_item When the client is telesliding, this stores the itemid of the destination sourcefile. This is needed to avoid displaying the contents of any sourcefiles that the client may touch while sliding to the destination file.
• int target_linenum When telesliding, this stores the line number to be displayed when the client reaches the destination.
• float target_angles[3], float target_angles_start[3],
  int target_angle_time These three fields are used for smoothly panning the client’s view toward the destination sourcefile when starting a teleslide. Ideally, this could all be done in the client (cgame.qvm), but doing it on the server appeared easier.
• float target_dir[3] This stores a vector pointing in the direction of the destination sourcefile when telesliding.
• int followers This is a set of 32 bits, one for each of the first 32 clients to join the game. If bit number n is set, this indicates that that player is currently "following" this client. This is used for forwarding scroll messages to players with locked views.
• int following Indicates the clientid (index into the g_entities array) of the player the client is following, -1 if none.
• int scroll_last_line, int scroll_last_col These record the last scroll event received from the client. This should correspond to the place where the client is currently looking inside the sourcefile. This is needed so that when another client locks his view with this player’s, the server can tell the locking client where to scroll to, without asking the other player for an update of its scroll position.
• gentity_t *item_ent Pointer to the entity which the player is carrying, that is the one that was shot by the player, NULL otherwise. This is used as follows: when the player shoots a sourcefile, it is made invisible, and a pointer is assigned to this field. When the user drops the file, the entity is moved to the current player location, and made visible. This is the normal mechanism for holdable items implemented by Quake 3.

Modifications to bg_misc.c

This file contains miscellaneous function and variable definitions use by both the server and client.

• A new item type, sourcefile, was added to the bg_itemlist array. This is where the connection between the type of entity and its display model is made. For now, sourcefile uses the same model as the holdable teleporter. Additionally, sourcefile is defined to have a giTag of HI_SOURCEFILE and a giType of IT_HOLDABLE. This provides a way of distinguishing sourcefiles from other entities when processing the g_entities array.
• The BG_CanItemBeGrabbed() function was modified. This function tests whether a player should be able to pick up an item – in Quake 3, when a player walks over an item the item is picked up. The modification was that if the item is a sourcefile, the function returns qfalse, since sourcefiles are picked up by shooting them, not walking over them.

Modifications to bg_pmove.c

This file contains functions used by both the client and server which define the physics of player movement.

• The function PM_NoclipMove() was modified so that if the player’s move flag PMF_FRICTIONLESS is set, no friction would be applied to the movement. This is to ensure that when telesliding, the player will move at a constant velocity.

Modifications to bg_slidemove.c

This file contains functions used by both the client and server which define the physics of player movement. Specifically, it contains functions that make players bump off walls they hit when sliding around.

• The function PM_SlideMove() was modified so that if the player’s move flag PMF_FRICTIONLESS is set, the player didn’t bump off any walls. This was necessary since a teleslide often takes the player through a wall.

Modifications to g_active.c

This file contains many of the message passing functions that handle events from clients and generate events in the server, such as deciding when a player has touched an item.

• ClientEvents() was modified, to respond to the USE_ITEM event from the client, which is generated when the player presses the use key (usually e). If the player is carrying a sourcefile, it will be dropped by involving the Drop_Sourcefile() function.
• ClientThink_real(), which is called once for each client animation frame, was modified to create the smooth panning of the client view towards the destination when starting a teleslide. The modification makes use of the target_ fields of the client, mentioned above.
• ClientThink_real() was additionally modified so that if the client is moving with PMF_FRICTIONLESS set the client can touch items, even if the client’s noclip flag is set. This is so touch item events are generated for sourcefiles even when the player is telesliding (this is not normal Quake 3 behaviour) so that the server knows when the player reached the target.

Modifications to g_client.c

This file contains functions that deal with clients joining and leaving the game.

• ClientSpawn(), the client set-up function, was modified so that the all the clients’ r.contents fields are set to 0 this means that players can walk and shoot though each other. This is to avoid players becoming stuck in a crowd around files, and to reduce distractions from bored users walking around and shooting other users. The function was also modified to give the clients infinite ammo for the machinegun weapon, and to set all the clients’ god flag, making them invulnerable.
• ClientDisconnect() was modified so that if a client leaves the game while they are carrying a sourcefile, it is dropped, rather than vanishing off the map.

Modifications to g_cmds.c

This file contains handlers for all commands send by the clients. Commands are messages consisting of a variable-length, null-terminated string of characters. The strings consist of space-delimited tokens. The first token is the command type, and the following tokens are command arguments. Four new command types and handlers were added.

• ClientCommand() was modified to invoke the appropriate new handlers when one of the four new commands, sv_gotofile, sv_following, sv_scrolled or sv_trail was received by the server from a client.
• A new command handler Cmd_following() was added. This command is sent by a client when that client wants to lock it’s view with some other client’s. This command takes the form of sv_following who, where who is the clientid of the other client. If who is 1, the server records that the client is no longer following anyone. The handler updates the followers and following fields of the clients involved. It then sends a cg_scrolled command to the initiating client, telling it where to scroll to synchronise its view.
• A new command handler Cmd_GotoFile() was added. This command is sent by the client when it wants to teleslide to another file, for example due to the user clicking on a hyperlink. The command takes two arguments, the destination itemid and the destination line number. The function locates the destination file, and sets up the fields in the client structure so the various telesliding animations can happen. Additionally, it informs all followers of this client that it is telesliding. The details of this function are best understood by looking at the source code of the handler, due to many special case scenarios. Telesliding players are made invisible, since if there are two or more players telesliding together to the same destination, they will occupy the same physical location, which results in "jittery" drawing on the clients’ screens. This jitter may be an effect of the client-side prediction failing to deal with players with r.contents set to 0 correctly, however making the players invisible is an acceptable solution for now. Players can slide at two speeds: if the destination is far away, the player moves much faster towards it than if it were nearby. This is to avoid the player getting lost when going a short distance, by giving them time to orient, but on the other hand it avoid lengthy waits when going far. In future, perhaps the speed of the player could be controlled by the user via accelerate and decelerate keys.
• A new command handler Cmd_scrolled() was added. This is responsible for forwarding scroll messages from each client to all the clients that have their views locked with that client. This is done by referring to the followers field of the initiating client’s data structure. The handler takes two arguments, the current scroll line position and scroll column position. The handler sends messages to all followers in the format cg_scrolled clientid line column, where clientid is the id of the initiating client.
• A new command handler Cmd_trail() was added. This is used for forwarding drawing messages between all players viewing a sourcefile. When the user at one of the clients drags the mouse with the right mouse button held down, the client sends a sv_trail x y command to the server every few hundred milliseconds, where x and y are the current mouse position. The Cmd_trail() handler forwards these messages to all other clients who are currently using the same file as the initiator. The forwarded message is of the format cg_trail clientid x y, where the clientid is that of the initiating client so that the receiving client knows what colour to draw the trail with.

Modifications to g_items.c

This file contains most of the functions that deal with interacting with items in the game, such as picking them up, shooting and using them, as well as the code that initialises ("spawns") the items in the game.

• The Touch_Item() function was modified to specify what happens when a user walks up to a sourcefile. The modification first checks if any work needs to be done. Quake 3 triggers the Touch_Item() function continuously when a player is within the bounding box of an item. For the purposes of this project, only one event is needed when the user first enters the bounding box. This is approximated by recording the time that the last Touch_Item() event occurred in the touch_sourcefile_frame field of the client data structure. If upon entering Touch_Item() this time is more than 500ms in the past, this is taken as meaning the user just recently entered the sourcefile bounding box. Only in this case is the rest of the modified code run. The touch_sourcefile_frame is updated with the current game time (level.time global variable) every time Touch_Item() is invoked for a sourcefile. This whole solution is not ideal, since sometimes the server may pause for more then 500ms, for example if a client running on the same machine as the server needs to load a large file, which causes the modified code to be run again. In future, a better solution for this needs to be found, but the present solution works acceptably on reasonable fast computers.
  
  The bulk of the modification deals with stopping the player if they are telesliding, updating the users and using_entity fields of the entity and client structs, telling the client that it needs to bring up a display of the sourcefile, and letting other users of the same file know that a new user has joined them. The details of this are best understood by referring to the source code.
• Touch_Item() was further modified to prevent the standard Quake 3 item pick up function being invoked when a player touches a sourcefile.
• A new function, Drop_Sourcefile() was added. It is a customised version of Drop_Item(). This function handles moving the dropped sourcefile to the correct position, and making it visible.
• FinishSpawningItem() was modified, to set the contents type of sourcefiles such that they can be shot at. In normal Quake 3, items cannot be shot bullets go through them.
• A new function, G_SourcefileHit() was added. This is used as callback function in source file’s entity data structure, which is called by Quake 3 when the sourcefile is hit by a bullet. The callback checks if the attacker is already carrying a file and, if not, hides the item from view on the map and adds a pointer to it to the client’s item_ent field.
• G_SpawnItem() was modified, to initialise the sourcefile’s entity data structure so that the G_SourcefileHit() callback is called when the entity is shot. Additionally, the sourcefile’s itemid is copied to that entities’ s.generic1 field. The s member, of type entityState_t, contains all the state information of the entity which is sent via the network to the client. Since the client needs to know each sourcefiles’ itemid (so that it can display the correct filename and file contents), the itemid must be put somewhere into the s member. Unfortunately, entityState_t cannot be modified, as it is directly accessed by the Quake 3 executable (game engine), whose source code is not available and so cannot be altered. However, within entityState_t there is a rarely-used field, int generic1, which can be made to do double-duty as the itemid. This is a good example of a limitation of using Quake 3 – the network protocol cannot be altered. This is not a fatal limitation, since firstly the gerneic1 field exists, and secondly a workaround could be coded where extra state information is passed via server and client commands.

Modifications to g_spawn.c

This file contains functions and data to do with starting the game world, and placing all entities in their start states.

• An item was added to the fields[] array. This array keeps track of what fields in the entity structure (gentity_t) are to be loaded from the map file. The item added was itemid, with a type of integer (which is need for correct parsing the map file). This modification was needed so that the itemids specified in Q3Radiant were correctly loaded into the server’s entity state data structure.

Modifications to g_utils.c

This files contains miscellaneous server functions.

• The function G_KillBox() was modified so it immediately returns so that is does nothing. This function is normally used by Quake 3 when a player enters the game world, to make sure no players exist at the start point. This is to avoid players becoming stuck in each other. Since in the implemented tool, the contents type of players was changed so that the players can move through each other, this is no longer needed.

Client-side Modifications (cgame.qvm)

Modifications to cg_local.h

• A field was added to the centity_t structure, float size. This is used for storing the size at which sourcefiles should be drawn. This value is initialised according to the size of the file represented by the sourcefile entity.

Modifications to cg_draw.c

• The function CG_DrawScores() was disabled (returns instantly). In a normal Quake 3 game, player accumulate kills or "frags" – the player with most frags wins. This function displays the current player’s and leader’s score in the bottom-right-hand corner of the client display. This is not needed, so was disabled
• The function CG_DrawAmmoWarning() was likewise disabled. This function normally displays a warning when the player is low on ammunition. This warning is incorrectly displayed even when the player has infinite ammo, so it was disabled.
• CG_Draw2D() was modified, to call CG_Sourcefiles() to draw the names of sourcefiles.

Modifications to cg_ents.c

This file contains code that deals with entity animations and spawning.

• The function CG_Item() was modified, to alter the way sourcefile entities are drawn. Source files are scaled in all directions by the value of their entity data structure’s size field. If the file is a header file (ends in h), a sphere is drawn around the sourcefile entity.

Modifications to cg_events.c

• Minor change to CG_UseItem(), so that no message is displayed when a sourcefile is dropped. Also, if the player attempts to drop a sourcefile when none is being carried, a message is displayed saying "Not carrying any files!"

Modifications to cg_main.c

• Two function calls were added to the main client start up routine: CG_InitMemory() and SRCV_Init().

Modifications to cg_servercmds.c

This file contains code that responds to commands sent by the server to the client.

• In CG_MapRestart(), the drawing of a "FIGHT!" message was disabled. This is normally displayed when the game starts.
• CG_ServerCommand() was modified, to recognise three new commands: cg_show_file, cg_scrolled and cg_trail. These commands are sent almost verbatim to the UI QVM, where they are processed. The code in this function replaces the cg_ prefix with ui_, so that cg_trail becomes ui_trail. This is to avoid an infinite loop, since when the client sends any command, it is first processed by CG_ServerCommand(). If the name were not changed, the client would keep sending the same message to itself forever. (At least, that is what appeared to be happening during debugging.)

Modifications to cg_snapshot.c

This file contains functions which are called at each client calculation frame (render frames may occur more often).

• CG_ResetEntity() was modified, to initialise the size field of sourcefiles correctly, based on the corresponding file size. This is probably not the best place to do this, since it will be done more often than necessary when called here. In future, a better place needs to be found.

Addition of sourcevis.c

This new file was added to handle two tasks: the mapping of itemids to real filenames, and the drawing of the file names above the corresponding sourcefiles.

• The mapping is carried out as described in the design section, where line number n of a file called filenames contains the name of the file corresponding to the sourcefile with itemid of n. The smallest allowed value of itemid is 1.
• The drawing of the filenames is based on code taken from a web forum[31], which in turn took it from "HLHack 1.3 by deltashark." Essentially, the code projects the 3D location of the sourcefile on to the 2D screen, moves up a bit, and draws the file name there. If the filename ends in h, the filename is drawn in red, else in blue. The main non-static function provided for file name drawing is CG_Sourcefiles(), which loops through all sourcefiles and prints their names. A side-effect of the client-server design of Quake 3 is that only the file names of source files which are potentially visible are drawn. This is because the server only tells the client about entities which are potentially visible to that client, to avoid cheating.

Modifications to cg_weapons.c

• CG_MachineGunEjectBrass() was disabled, so that no brass (empty shell cartridges from the machinegun) is drawn.
• CG_RegisterItemVisuals() was modified to correctly set up the sphere around header sourcefiles.
• CG_AddPlayerWeapon() was disabled, so that players are drawn without guns (see design section).

Modifications to the UI (ui.qvm)

Modifications to ui_atoms.c

UI_ConsoleCommand() was modified, to add three new commands: ui_show_file, ui_scrolled and ui_trail. When these commands are received the functions UI_SourceFile_Draw(), UI_SourceFile_ScrollCmd() and UI_SourceFile_TraceCmd() are invoked, respectively. Arguments are converted from strings to integers where appropriate before invoking the functions.

Addition of ui_sourcefile.c

This file, 1200 lines long, contains all the functions that deal with displaying the source files’ text, clicking on hyperlinks, scrolling, providing back and forward buttons, locking views, and communicating with the server (via the client). There are many complicated functions inside this file, so only a brief overview is given below, the source code remains the best place to learn about the detailed workings.

UI_SourceFile_Draw() is the fucntion which is normally called first, via the ui_show_file command from the server. It loads the source file into memory, and sets up the UI QVM for drawing of the sourcefile (registers sfMenuDraw() as a draw callback for the current menu).

Due to the lack of dynamic memory support in the Quake 3 VMs, the file is loaded from disk in 50K byte chunks only one chunk is kept in a (static) buffer at a time. When the user scrolls outside of the currently loaded 50K chunk, a new 50K chunk is loaded. This approach adds quite a lot of complex code. Theoretically, one could create a huge static buffer (say 100MB), and allocate memory out of that as needed. The problem with that is there seems to be no documentation regarding how much memory is accessible to the QVM but there is a comments somewhere in the code that it must fit in the stack of the host CPU, so this is probably platform dependant. This might be something worth looking into in future versions. When the Quake 3 engine source code is released, some form of dynamic memory allocation could perhaps be add to the VMs.

One limitation due to the lack of dynamic memory allocation wasn’t worked around: the filenames file is limited to 16K. This limit is plenty for all practical applications, but could be removed in a future version.

The normal Quake 3 UI functions do not provide a scrollable textbox. Therefore, all the scrolling and display functions had to be coded by hand. These new functions only use standard Quake 3 functions for drawing individual characters on the screen all other functionality was coded from scratch. This shows that the Quake 3 UI is not very advanced, and may need a lot of work to tailor it to a specific application. However, some Quake 3 UI replacements and improvements are available on the internet these may be investigated in the future.

The user can scroll the text by using the arrow keys, pageup and pagedown keys, and the mouse scrollwheel. The current position in the file is displayed as a scrollbar on the left side of the screen. Currently, the scrollbar is not fully implemented, so the user cannot click on it to scroll. This should be finished in a future version.

The source code file is parsed as it is loaded. When syntax highlighting tags are encountered, the current draw colour is changed to that corresponding to the syntax element. If a hyperlink tag is encountered, the following text is underlined in blue.

When the user clicks on the text, the code identifies what line was clicked, and then parses that line to see if there is a link at that position. If so, it identifies the target file and line number, and adds it to the history. If the destination is in the same file as is currently displayed, the view is scrolled there, otherwise the UI instructs the server (via the sv_gotofile command) to teleslide the player to the destination file.

The UI keeps track of what other players are viewing the same file as the UI is displaying, via receiving commands from the server. At the bottom of the screen, this information is displayed as portraits of all the other players. Each portrait’s background colour is unique. When a user clicks on one of the portraits, its background starts flashing. The scrolling functions are then disabled, and a message is sent to the server to tell it that this user wants to follow another user. The server will then send messages whenever the other user scrolls or clicks a link, which are processed by the UI so as to keep the two views identical.

If the user drags the mouse with the right mouse button down, a trail of squares is drawn on the screen. Messages containing the location of the cursor are sent to the server, which will forward it to the UIs of all the other players also viewing the same file. When the UI receives such a message, a new trail is drawn at the specified location, with the colour corresponding to the portrait background of the user drawing the trail. At the moment, these trails are drawn even if the players are looking at different parts of the file. This should be fixed in future versions.

One major bug still remains, which can cause the client to crash when viewing a text file which fills the entire screen with text. It seems that in this case, Quake 3 reaches some internal limit for the number of polygons it can draw. When this happens, invoking the r_speeds 1 command via the console shows that around 8200 triangles are being drawn on the screen. In practice, most source files have plenty of white space, so this bug does not occur often. However, this is a major bug, and needs to be fixed in future versions. This is possible a bug of the Quake 3 game engine, so access to the Quake 3 game engine source may be needed to fix this.