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

Design of the Source Code Comprehension Tool

Requirements for the Tool

The main purpose of the tool is to illustrate how game engines may be used for information visualisation. Therefore, the tool should use a visualisation metaphor that maps simply and naturally into a static 3D world occupied by dynamic, interactive entities. The metaphor that was chosen is to represent source code files as entities in a static 3D world. They can be moved around at will, to arrange them in logical groupings. Files can be viewed by walking up to them. The source files are cross-references using hyperlinks, so that clicking on a symbol in the source code takes the user to a definition of that symbol. Also, back and forward buttons exist so that the user can walk through their history, like in a web browser.

The metaphor used by the tool is essentially just a 3D version of a web browser, using cross-referenced source files as the web pages. The advantages of using a game engine instead of a normal browser are mainly: multi-user support ether via a LAN or the internet, so one user can guide another user via the code; and utilisation of the user’s spatial memory, since closely-related files can be placed together in the 3d world – hopefully making it easier for the user to comprehend the structure of the source code.

Throughout the design of the tool, the use scenario considered the most was that of a new employee, or group of employees, arriving to work at a company, and being given a guided tour of the company’s source code base by an existing employee.

The main functional requirements identified are:

1. A web browser like interface, but with webpages (source code files) represented as movable 3D entities in a 3D world. Syntax highlighting and hyperlinks are to be displayed when a source code file is shown.
2. Collaborative support:
• Ability for users to identify, by their appearance (model), other users in the world.
• Ability for a user to give a guided tour so that the new employees can automatically follow the experienced employee.
• Ability for users to point out specific parts of the code to each other during a guided tour by circling parts of code on their screen, and having the same drawing appear on the other player’s screens.
• Communication between users (chat)

Requirements for the Game Engine and Engine Choice

The game engine used needs to be multi-user capable, stable, and well tested. Additionally, since as discussed in the theory section the tool will be implemented by modifying an existing game running on the chosen game engine, there must be a well-tested, open-source, implementation of a game for the chosen game engine.

The game engine which seems to best meet these requirements is the Quake 3 engine, with the corresponding game implementation, Quake 3 Arena. The Quake 3 engine source code is at the moment not available to the public. The Quake 3 Arena source code is available, under a certain licence (which does appear to permit modifying the source code and distributing the modified game virtual machine bytecode see the licence for details.).

The open source game engines, such as Ogre, Crystal Space and Irrlicht, were investigated, however most of them lacked crucial features (such as networking support), or had no well-tested game implemented using them.

The User Interface and Interaction Metaphor (Single User)

The tool is based on displaying source code files as individual entities within a 3D world. These entities can be moved around, much like icons can be moved around on a 2D desktop. The entities are drawn as floating "T" shapes, for no reason other than that this seemed to be the most appropriate of the existing entity models in Quake 3. (Another model could be easily substituted in the future.) The size of the drawn entity indicates the size of the corresponding source file. There is a minimum size (approximately the size of a player’s head), which is used for empty files, and a maximum size (slightly bigger then a whole player), which is used for files of 100 kilobytes and more. Between these two extremes the size relationship is linear. All file entities have their filename displayed above them. This is done in such a way as to have the text always be facing the player, and be of constant size, irrespective of the distance between the player and the file. This was done to improve the readability. Additionally, header files (detected as those files whose name ends in ".h") have their filenames displayed in red, and their "T" shapes surrounded by a spheroid, while other files have their filenames in blue, and have no surrounding spheroid. Below are shown a small header file (left) a large .c file (right):



Files can be picked up by shooting at them. When this happens, the file disappears from the map, in all players’ views, but a "T" icon appears on the side of the screen of the player who is now holding the file. The player can then walk anywhere on the map, and press the e key (or whatever key is bound to the item use quake function) to drop the file at the new location. The file than appears at this new place in the map, in all players’ views. In the current implementation, there is no way for players to distinguish if a certain player is carrying a file. This may cause some confusion due to "missing" files, so this feature should be add in a later version.


Click for higher resolution.

To view the contents of a file, a player just walks into a file. When they are close enough, the file is displayed on the screen, as shown above, in a scrollable box. The file may be scrolled using the arrow and page up and down keys. The current position in the file is indicated by a scrollbar on the left and as line and column numbers at the top of the screen. The scrollbar cannot by currently dragged with the mouse, like a normal windows scrollbar, but this feature may be added in a future version of the tool.

The displayed text is shown using syntax highlighting, for easier comprehension. Function invocations and uses of variables are displayed as hyperlinks by being underlined in blue. Clicking on a hyperlink will take the user to where the symbol in question is defined in the source code. If the definition is within the same file, the file is scrolled so that the definition is at the top of the screen. If the definition is in another file, the file view is closed, so that the user sees the 3D world. The user’s view is than slowly panned around so that the file in which the symbol is defined is centred on the screen. The player is then slid towards the file, and upon reaching it the file is displayed, with the definition of the symbol at the top of the screen. In the present implementation, if the files are in different rooms separated by a wall, the player will be slid through the wall, which may be disorientating to the player. In future, part of the AI route-finding algorithm in Quake 3 could be reused to have the player follow a path to the destination file without crossing any walls.

Each time a player clicks on a hyperlink, the currently viewed file, and their position therein, is added to their history. The history operates exactly like a web browser’s history, via a back and forward button.

Multi-User Features

Most of the multi-user features present in Quake 3 remain unaltered. These include the ability of players to see other players in the 3D world, to chat with them, and to view the names of all players in the current game by pressing the F1 key (the scoreboard key). In Quake 3, each player can choose a 3D model that will be their avatar in the 3D world. Each player also can set their name this is the name that will be displayed in the scoreboard and in the chat dialog.

To chat in Quake 3, the user presses the talk key (usually t). They can type in a message, and when they press enter, the message will be printed in the top left hand corner of all the player’s screens (accompanied by a short "beep" sound). This does not work if the player is currently using an in-game menu in this case, any incoming messages are ignored. Since in the current implementation the source file contents display is implemented in the UI QVM, this means that players can’t easily chat while viewing files. Chatting in this case is still possible, but in a roundabout way: pressing the tilde key brings down the console, where users can type messages to each other (messages beginning with \ are treated as commands, so message to be sent to other players must not begin with a \). The disadvantage of this is that unless they have the console open, they will not be notified of any incoming messages. This could be improved in future versions, by providing a chat box in the UI.

The standard Quake 3 interaction provides a simple way of seeing what file another player is looking at one can walk around the map, looking for that player’s model, and see what file they are standing at. In future versions, an "overview" map could be added that displays, in 2D, the location of all files and players this would simplify finding players on a large map. Unfortunately, the standard Quake 3 multi-user system does not provide a simple way of seeing which part of the file another user is looking at, and also there is no simple way of pointing out certain lines of code to another user.

Therefore, two new multi-user features were added to Quake 3 for this tool: a way of "locking" one’s view with another player’s, so that your screen shows exactly what the other player is seeing; and a way of "drawing" on the file display, so that one can point out parts of the source code to other users.

The lock view feature works as follows: when viewing a file (that is, when standing very near it in the 3D world), portraits of all other players also viewing the same file are displayed at the bottom of the screen. Clicking on one of these portraits locks your view with that player’s. This is indicated by the background of that player’s portrait flashing. When your view is locked with another players’, you cannot scroll, but your view shows exactly what the other player sees if they scroll, your view also scrolls to the same position.

One can point out bits of source code to other users currently viewing a file. This is done by dragging the mouse cursor with the right mouse button held down. This leaves behind a long trail of squares, which fade out over time. This can be used for example for circling or underlining certain items. In the present implementation, if one player viewing a file draws on it, the same trail of squares appears in the view of all other players also viewing the source file, irrespective of whether their views are locked or not. Whether the trail drawing should be restricted to only the players with locked views is something to be investigated in the future. Each player has a unique colour, which is used as the background of their portrait, as well as for the colour of the trail of squares. This is so users can easily identify who is drawing.

Detailed Design and High-Level Overview of Implementation

There are two distinct problems that need to be solved in the implementation: first, the parsing and analysing of the source code to create the hyperlinks and syntax highlighting information; and second, the actual display of these files in the 3D multi-user environment. This section provides a summary overview of the way these problems were overcome, while the next section, Implementation, contains a more detailed description.

 

Source Code Analysis and Cross-Referencing

The source code of the project to be visualised needs to be processed before it can be displayed. In this step, hyperlinks in the source code need to be created whether a symbol is used, with the target of the link being the definition of the symbol. Additionally at this stage mark-up for syntax highlighting is added. In principle, all of this processing could be done within the code running on the Quake 3 Virtual Machines, but due the fact that these VMs support no dynamic memory allocation, are slower than native code and have limited file access ability, it was decided to do this processing before the tool is run.

In the present implementation, the pre-processing step consists of first running the doxygen[30] source code documentation tool, which generates a set of HTML pages of documentation and cross-referenced source code. Then, a purpose-written tool, temporarily named "dox2html", is run with the output of doxygen as its input. This tool simplifies the HTML pages, removing style sheets, line numbers, and all of the unnecessary documentation, leaving behind only source code files with syntax highlighting and hyperlink information. The details of the output format are discussed in the implementation section.

The dox2html tool, after processing all of the files from Doxygen, also generates a file called filenames. This file contains the names of all files in the project, one per line. It is used as an integer-to-filename mapping by the code running in Quake 3.

Quake 3 Modification

The main modification to Quake 3 is the addition of a new entity, a sourcefile entity. Each source file entity has a unique identification number, itemid. The corresponding line in the filenames file (mentioned above) contains the name of the real source file represented by this entity.

Q3Radiant is the tool used to make and edit Quake 3 maps. In the current implementation of this project, this tool is used to modify an existing Quake 3 map, removing all of the normal game play items, and placing sourcefile entities around the map. Within Q3Radiant, unique numbers, starting at 1, are assigned to the itemid field of all the sourcefiles. In future, it may be a good idea to automate the generation of the map, by for example analysing the couplings between source code files and placing closely coupled source files next to each other.

Most of the code added to Quake 3 deals with handling various player interactions with the new sourcefile entity type. Modifications to code running on all three Quake virtual machines need to be made.

The game QVM (server) needs to be modified so that the sourcefile entities may be loaded at game start from the map. Additionally, the server keeps track of which players are using which files, for the lock view feature. The server also handles passing messages between players who have their views locked, to keep them synchronised. The server is also responsible for keeping track of any source files being carried to make sure that they disappear when picked up and reappear when dropped. When a player walks up to an item, the server sends a message to the cgame QVM running on that player’s computer, which forwards it to the UI QVM there so that the file is displayed. The server also enables players to "teleslide" between files when they click on hyperlinks. Upon receiving a command from a UI QVM indicating that player needs to be slid to a new file, the server animates that player’s view to point at the new file, and starts sliding the player towards that file. If there is an intervening wall between the player and the destination, the server allows the player to go through the wall (this is called "noclip" in Quake 3). Another related modification is to change the contents type of player entities from CONTENTS_BODY to 0. This has the effect that players can run (and shoot) through each other, reducing crowding around files, and avoiding having a telesliding player end up stuck inside another player.

The cgame QVM (client) needs to be modified to display the file name labels above the source files in the 3D world. The labels are not drawn as part of the 3D world, but rather superimposed on top of the rendered view. This is done as it is easier to implement, and also it has the advantage that the labels are a constant size and always facing the player. There are some other modifications to the client, mostly to do with passing messages from the server to the UI, as the server cannot directly send a command to the UI of a specific client in Quake 3.

The UI QVM contains the biggest addition. Upon receiving a message from the server (forwarded to it by the client), the UI brings up a display of a source file. The UI handles the scrolling of the file locally, however it sends messages to the server to tell it what position the user is looking at, so that the server may forward this to other clients who have their view locked with this player. The UI also contains functions to keep track of the history, and to allow users to "draw" on top of the source file and forward the "drawings" to the other users of the same file, via the server. The text for the source files, along with the filenames file is stored locally on each player’s computer, in the SRCVIS directory within the main Quake directory.

One other minor modification needs to be made to both the game and cgame VMs – the removal of gore. Quake 3 by default draws large amounts of blood when players are shot or killed, and the death animations may be disturbing to some users. Most of the gore can be disabled by setting the com_blood cvar to 0. There is also no need for players to be running around with guns when viewing source files, so these were disabled from being drawn in the client code. Additionally, the map on which the current demo is based, q3dm1, had an animated pool of blood, which was removed.

Players are given an infinite amount of ammunition, which they need since files are picked up by shooting at them.