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

Background

Computer Games and Game Engines

Game Genres
There are many computer game genres. Out of the genres which use graphics (as opposed to text based games) the main ones are First Person Shooter (FPS), Real Time Strategy (RTS) and Role Playing Game (RPG). All genres contain games which are either single player (wherein other players are simulated using artificial intelligence) or multi-player (where several players can interact in the same virtual world via a computer network), or both.

In a FPS game, the player travels around in a three dimensional world, shooting "bad guys." In a RTS game, the player views a two dimensional map with many units (for example, of an army) on it. They control their own units and use them to attack and defeat their opponents. An RPG is similar, except the player controls only one unit, their "character", via which they explore a 2D (e.g. Age of Empires II [6]) or 3D (e.g. World of Warcraft [7]) world.

Computer games can also be divided into those that run on PCs and those that run on consoles, which are purpose-made gaming computers usually connected to a TV. In this project, only PC games will be considered, since the hardware is much more ubiquitous, and the cost of development tools for console games is prohibitive.

In this project, only FPS game engines will be discussed, however future work may involve investigating other genres.

Game Architecture
Most modern computer games can be split into three parts: the game engine, the game logic and the game art. The game engine is the main executable file which runs on the computer. It provides an environment within which the game logic runs, as well as basic mathematics, graphics, audio, user input and network functions. The game logic may take the form of scripts, bytecode for a virtual machine, or a library (a DLL for example). The game logic’s task is to control the game play, and to use the engine to display the game art as appropriate. The game art consists of things such as pictures (textures in game parlance), maps (layouts of virtual worlds), models (3D representations of things inhabiting the world, for example players, weapons or flowerpots) and sounds.

It is possible to use a game engine for creating many different computer games, by altering the game logic and art. Such alterations are called "modifications" or "mods" for short. Creating a mod is the easiest way of customising an existing game. There is an active community of amateur "modders" for every game, as well as the occasional commercial mod (for example, Return to Castle Wolfenstein is based on the Quake 3 engine). Extensive mods are referred to as "total conversions," in which all the game logic and art has been replaced.

In some cases, it is possible to modify the game engine itself, if its source code is available. There are several open source game engines, discussed below, as well as older commercial engines which were open-sourced by their developer, such as Quake 2.

Available Game Engines
Game engines can be divided into two categories: open source and closed source.

Open Source Game Engines
Open source game engines are either ones written by amateurs, or older commercial engines which the developer decided to open source.

Out of the amateur ones, the main ones are:

1. OGRE[8]

A mature multi-platform engine, supporting OpenGL and DirectX rendering, written in C and C++, under the LGPL licence. It has an OO based design, and supports loadable code modules. It provides a hierarchical scenegraph, basic physics functions, and has a 2D GUI system built in, supporting common widgets and TrueType fonts. It has a large and active support community of developers and users. It is however mostly a graphics engine, with no support for networking or audio.

2. Crystal Space[9]

Another popular and well-supported engine based on OpenGL, which runs on Windows, Linux and MacOS, with a LGPL licence. Based on a OO design, with support for code plugins. Provides simple networking and audio functions as well as a 2D GUI system.

3. Irrlicht[10]

This engine can use either OpenGL, DirectX or software for rendering. It runs on Windows and Linux, and is under the zlib license. It has a reputation as having poorer graphics quality and rendering speed then the others, which is offset by being easier to develop with[12]. It is often viewed as the ideal beginner’s engine[12]. It uses a hierarchical scenegraph for scene management, and has basic 2D GUI functionality. It is somewhat smaller than the engines above, with only one main developer, however there is a large support community of enthusiasts. It also provides basic physics routines, but lacks any network functions.

4. The Nebula Device 2[13]

This is a Windows only, DirectX based engine. It was not investigated further.

5. OpenSceneGraph[14] and OpenSG[15]

These are not game engines, rather purely graphical engines. However, they do provide an easy way of creating an interactive 3D world, so they are mentioned for completeness. They are based on OpenGL, and run on many platforms. They lack physics, audio, network and 2D GUI functionality.

In addition to these, there are the Doom, Doom 2, Quake and Quake 2 engines which have been open-sourced by id Software[16]. They run on Linux and Windows, are OpenGL based, and since they are from a real commercial game they include support for all the gaming features such as physics, audio, network, 2D GUI, etc. They suffer from being older, providing poorer rendering quality than the newer engines. Quake and Quake 2, the newest of the four, still have a sizeable amateur modding community.

Closed Source Game Engines
Currently, in the FPS genre, there are three main game engine families, each form a different developer: Doom 3 and Quake 3 engines from id Software[16], Half Life and Half Life 2 engines from Valve Software[17] and Unreal Tournament (UT) and Unreal Tournament 2004 (UT2004) engines by Epic Games[18]. Doom 3, Half Life 2 and UT2004 represent the latest generation from each developer, and are the best game engines available. Quake 3, UT and Half Life are the previous generation engines. It should be noted that the Half Life engine is based on the Quake and Quake 2 engines.

All of these engines are fully featured, and there exist one or more complete games based on each of these engines. This is in contrast to most of the open source engines above, which provide more basic functionality. The open source engines often need to be combined with other libraries and toolkits to create a playable game, while the six engines listed here have all of the required functions built in. Out of these six, Quake 3 deserves special mention as id Software plans to open source it in the near future[19]. This would mean that, unlike the other engines here, extensive modifications to the game engine would be possible. (Mods for the other ones are restricted to altering the game logic and art.)

Another engine which should be mentioned is Torque by GarageGames[11]. It is an inexpensive commercial engine. It was not considered for this project.

Quake 3
As the Quake 3 engine was chosen for use in this project, this section gives a very brief overview of the engine and its architecture. For more information see [20,21], although the documentation available is rather limited.

Quake 3 uses the standard FPS game control system: mouse look and keyboard. Moving the mouse around changes the direction the player looks in. The mouse buttons are typically used for walking forwards and for shooting. Various keys on the keyboard are used for crouching, jumping, moving backwards, strafing and switching weapons. The keys can be remapped to different in-game functions via a process known as key binding.

Quake 3 is by design a network-oriented (LAN or internet) game, using the client-server model of communications. Each computer running Quake 3 runs an instance of quake3.exe, the game engine. This executable is capable of running bytecode for three virtual machines: game, cgame and UI, stored in the files game.qvm, cgame.qvm and ui.qvm. "QVM" refers to Quake Virtual Machine. game.qvm is the server part of the game. It is responsible for maintaining the state of the game world, such as positions of all entities, and sending messages to the clients. It also has the final say on issues such as whether a certain bullet hit a certain player or not. Game.qvm does not do any rendering; it only communicates with clients. cgame is the client QVM – there is one running on each computer connected to a particular game. The client is responsible for rendering the map and entities, according to data sent by the server. Additionally, the client will interpolate the positions of entities in the world between snapshots sent by the server, to minimise the effect of slow network connections or dropped packets. Finally, ui.qvm is responsible for displaying the in-game menus. It is the first QVM started, and it will start the game and/or cgame QVMs when the user, via the menu system, chooses to start a new game.

The QVMs are all coded in ANSI C. They are then compiled by a compiler provided by id Software, which outputs bytecode that can be run by the quake3.exe engine. The virtual machine does not support dynamic memory allocation (no malloc()).

Within the QVM environment there are several available system calls or traps. These are functions that can be called within the code of the QVM, to pass control into the main quake3.exe executable. This is how tasks such as drawing on the screen, file and network access are carried out. All these function have trap_ prefixes, e.g. trap_FS_FOpenFile().

Note that individual polygons are not drawn via system calls the trap_ functions deal with higher-level data such as models or maps. This is of course to improve performance, since drawing all individual polygons from within an interpreted VM would introduce unnecessary overhead.

In a normal multi-player game, one computer is the server. This computer will be running quake3.exe, which will in turn be running game.qvm (for the main game server logic) and cgame.qvm (to provide a client on that computer, so a player may use it to play in the game). Other computers, clients, may join the server; these computers will be running quake3.exe, which will be only running cgame.qvm. It is also possible to run a dedicated server, that is having quake3.exe only run game.qvm, for increased server performance.

The game data such as textures, audio and models is kept in .pak files. These are just a zip archive of all the individual files. There is a special file hierarchy that needs to be used within the zip files, such as all sounds are placed in sounds\, the QVMs in qvm\ and so on. For development purposes, files may also be placed outside the .pak, but following the same file hierarchy as if they were in it. If then the in-game option sv_pure is set to 0, these files can be accessed by the game code normally.

Quake 3 provides a drop-down console, which can be activated at any point in the game or in the menus by pressing the tilde ‘~’ key. There, commands can be typed, such as \connect 192.168.0.12 to connect to a game server, or variables can be set, such as \sv_pure 0. Variables that can be altered via the console are called cvars.

Internally, the main message passing mechanism (or rather, the most easily accessible and modifiable one) is based on passing variable-length, null-terminated strings. These can be sent from the server to the client (a ServerCommand) or vice-versa (a ClientCommand). Additionally, the client can send messages to the UI QVM via trap_SendConsoleCommand(). The UI can also send messages directly to the server, via the trap_Cmd_ExecuteText() call, although in this case the command is only appended to the cue of commands waiting at the server, not immediately executed.

Currently, only the Quake 3 game logic code is open to the public. This consists of a total of approximately 100 000 lines of ANSI C code running on the three Quake 3 virtual machines.

Spatial Memory and 3D User Interfaces

Spatial memory refers to the ability of humans to remember where things are placed in the physical world. Some people have better spatial memory ability then others, and several papers[22,23,24] provide evidence that people with better spatial memories will perform better when using certain computer user interfaces.

Some research has been done regarding whether spatial memory is best utilised in 2D or 3D interfaces. The results of Cockburn et al.[25] seem to indicate that users find a 3D user interface more confusing and cluttered, hence eliminating any possible benefits due to improved spatial memory use. In this paper, an experiment was carried out by having subjects recall the location of items in a 2D, 2.5D and 3D spaces, both physical and virtual (on a computer screen). The main result was that the subjects performed best with the 2D interface.

The paper above also mentions that adding semantic labels to elements in a 3D space may improve user performance to above that of a standard 2D interface. The tool implemented in the present project places the elements in virtual rooms and hallways in a 3D world, unlike the experiment by Cockburn et al. where the items were all floating in space, thereby hopefully providing a type of semantic label, and so overcoming the confusion that may arise from a plain 3D interface.

In a paper on 3D software visualisation[26] there is a very good summary of research about the advantages 3D visualisation, which is quoted below, due to its applicability:

"The work of Hubona, Shirah and Fout [Hubona et al. 1997] suggest that users' understanding of a 3D structure improves when they can manipulate the structure. Ware and Franck [Ware and Franck 1994] indicate that displaying data in three dimensions instead of two can make it easier for users to understand the data. In addition, the error rate in identifying routes in 3D graphs is much smaller than 2D [Ware et al. 1993]. The CyberNet system[Dos Santos et al. 2000] shows that mapping large amount of (dynamic) information to 3D representation is beneficial, regardless of the type of metaphors (real or virtual) used. Also, 3D representations have been shown to better support spatial memory tasks than 2D [Tavanti and Lind 2001]. In addition, the use of 3D representations of software in new mediums, such as virtual reality environments, are starting to be explored [Knight and Munro 1999, Maletic et al. 2001]."[26]

Sofware Visualisation

A substantial amount of work has been done in the area of software visualisation. In this section, only several selected examples of 3D software visualisation are presented.

SeeSoft[27], is one of the better-developed 3D software visualisations. A sample visualisation using the sv3D[26] implementation of this system is shown below, taken from [26]:



This figure shows one source file, each line of which is represented by a cuboid. In this example, the colour of the cuboid represents the control structure type, while the height represents the nesting level of the line. The sv3D implementation allows the user to arbitrarily map other attributes of the code lines to various graphical attributes, such as transparency.

Another interesting 3D visualisation is ArchView[28]. Here, individual source code modules are represented by "LEGO blocks" floating in a 3D space. Import relationships between modules are shown by arrows, while the type of module (a user-specified categorisation) is represented by the colour and shape of the bricks. Below is an example taken from the ArchView paper, showing the architecture of a medium-sized project.



Yet another interesting visualisation[29] uses a 3D city metaphor to represent a software project. In the below image taken form that paper, Java classes are represented by individual buildings, whose size represents the number of source code lines in that class. The spacing of buildings shows the amount of coupling between the classes, and the type of building indicates the quality of the code old and collapsed buildings represent code which needs to be refactored. Cars travelling within this city show the dynamic execution path of the visualised program. Since the cars leave traces, places of heavy traffic can be identified, and these correspond to heavy communication between classes.

Various aspects related to software project management are then superimposed on top of this view, such as surronding often executed classes by flames and coloring parts of the code which are not used brown.



Previous uses of Game Engines for Visualisation

PSDoom[4] is a utility for process management, implemented as a modification of the Doom computer game. It provides the functionality of the Unix ps command via a 3D user interface. Running processes are represented as monsters (enemies), which can be shot and killed, thereby killing the associated process. Monsters can fight back, and more important processes are represented by bigger monsters (which are more difficult to kill), thereby reducing the chance that they will be killed. Interestingly, when many processes are running, and the 3D space becomes crowded with monsters, the monsters start attacking each other (a normal Doom behaviour). This provides a natural control mechanism for processes in a heavily loaded system less important monsters will be killed first, since the important monsters are represented by stronger monsters. The screenshot below shows the user killing the emacs process.



Heckenberg et al.[5] implement a visualisation of a simplified financial market, "The Minority Game," using a modification of the Unreal Tournament 2003 computer game. The Minority Game consists of two teams of agents. These agents are represented as 3D players in the game. The Minority Game centres on the agents making decisions so as to end up on the "winning team" (which is defined as the team with least agents.) In the current implementation, this is all that the agents do – swap teams, which can be seen by viewing the scoreboard. Future work is suggested to make use of other game features, such as players being able to throw stocks and money at each other, to perform trading. The screenshot below shows the scoreboard where the agents can be observed as they swap teams.



Computer games can also be used to visualise less abstract concepts, such as in [2], where Unreal Tournament is used to visualise a battlefield in 3D in an army simulation. Another relevant paper[3] discusses a tool for landscape design and planning based on a game engine. Moloney et al.[1] have used a game engine for visualising architectural designs.