Technical Summary

C++ is the chosen programming language. The code compiles under Mac OSX, Linux and Windows with the GNU C++ compiler, g++ (no earlier than 3.4.5 was tested, MinGW when using Windows).

Renderer

The code is graphics driver independent where possible. Driver dependent code (currently only for OpenGL) is added to the binaries at compile time using a macro definition. Compilation units which require a renderer to compile raise an error if that macro (GX) is not set to ‘OGL’, this is set by default in the Makefiles.

Compilation

Classes are separated into different directories and have their own Makefiles.

For example,

cd terrain

make

creates the object file for the Terrain class. In most cases,

make demo

makes an executable demonstrating some of the capabilities of the class.

Dependencies

I have tried to create as much code from scratch as possible. However, the following packages are required to exist in your compiler’s search paths for much of the source to compile:

• GLee, GL Easy Extension library (http://elf-stone.com/glee.php), a version of this is provided in the lib directory.
• Boost, including a pre-compiled boost_thread (http://www.boost.org/), pre-compiled versions of boost_thread for Windows and Mac OS X are available in the dist directory (inside Foundation.zip for Windows, inside Foundation.dmg/Foundation.app/Contents/libs/ for Mac OS X).
• freeglut (http://freeglut.sourceforge.net/), or GLUT (http://www.opengl.org/resources/libraries/glut/). Windows compilations should use freeglut, Linux and Mac OS X compilations can use either. GLUT comes by default with Mac OS X.

Demonstration

A demonstration of the engine is provided with a view towards the actual idea for the game. The code for the demonstration is in the foundation directory. Here, ‘make demo’ builds an executable using all of the classes here presented.

Controls

• w = forwards.
• s = backwards.
• a = spin left.
• d = spin right.
• q = strafe left.
• e = strafe right.

• hold and move right mouse button = rotate the camera.
• left mouse button = select a unit, place a building.
• click right mouse button = path a unit.
• spacebar = command all units to path to random locations.
• middle mouse button or b = open the ControlRing offering building selection.
• escape = clear currently selected building.
• -/+ = zoom.
• mouse scroll (freeglut only) = zoom.

Techniques and Technologies

Within the demonstration code I have demonstrated a working knowledge and understanding of general computer science topics such as makefiles and the compilation process, C++, object-orientation, classes, inheritance, templates, project organisation, SVN. I have also demonstrated a number of game-development and graphical application practices such as scene composition and the rendering pipeline, height maps, interpolation, animation, shaders, camera manipulation, bill-boarding, display lists, procedural generation, A* pathing, frustum culling, picking, vertex-arrays.

Threads

The demonstration creates several threads other than the main thread of execution:

• The code that interfaces between the keyboard and the camera gives smoother movement when in a thread.
• Two CPU intensive tasks that might other-wise cause gaps between rendered frames are in threads; unit pathing and water perturbation.

Class Breakdown

Details of individual classes’ rules follow; a diagram of class relationships is at the end.

Bounding

• Represents the extent of an object’s bounds.

• Boxes, spheres and cones.
• Used  for collision detection, occlusion and picking, etc.

• Inheriting from Bounded gives the class a standard interface for interacting with Bounding elements.

To-do:

• Other shapes, including irregular or aggregates.

Building

• The BuildingForm class represents the appearance of a building that is common to a group of buildings of a certain type. For now this is just a bounding box.
• The Building class represents an individual building in the game world.

• Coordinates and visual appearance such as scale and rotation.

To-do:

• Implement a proper model format for rendering of an actual building appearance.
• Track other properties such as hit-points and construction progress.
• Ringable icon preview (see the ControlRing class).

Camera

• Uses spherical coordinates to create a camera that can orbit around its focus.

• Azimuth and inclination rotation (spin and elevation).
• Radius (zoom).

• Positions the camera in world-coordinates.
• Terrain collision.

• Moves away from the camera’s focus at regular intervals and checks for a collision with the terrain.
• If a collision is found the interval is inverted and reduced in magnitude.
• Recurses until the increment is very small or until no collision is found when the increment is moving outwards (from the original call).

ControlRing

• This is a UI control that renders as a two-dimensional ring with selectable items.

• Item pointers can be added to the selectable options.
• When opened the control tracks which segment the user’s cursor is currently over using a point in triangle check and allows clicking to select that segment’s item.
• When an item is selected the control returns the item that the user selected.

• Items added to this control must inherit from the Ringable class which gives them methods to show a preview, cost and hot-key, etc for the item.

Improvements:

• Beautify with animations and textures.

Frustum

• Computes the viewing-frustum from projection and camera data.

• Stores the actual frustum planes as well as alternative representations, i.e. the frustum cone.

• Provides frustum culling checks.

• Sphere in frustum cone.

To-do:

• Other frustum culling checks, e.g.:

• Sphere in sphere,
• Axis-aligned box (AAB) in cone,
• Sphere and AABs in frustum planes.

Improvements:

• Link this code in more tightly with the camera so that, for example, when we know which side of the frustum objects were previously on they are only checked against the frustum when the camera is moved towards them.

Image

• Retrieves the pixel data from files of type TARGA or Bitmap.

To-do:

• Completely re-write this code to homogenise error handling.

Note:

While I was developing this application I wanted to get into using textures ASAP and so hacked together parts of code I’d found elsewhere with my own.

Matrix

• A templated class representing sized and typed matrices.

• Results in compile-time errors if incorrectly sized matrices are used in, for example, multiplication.

• Standard matrices such as the identity matrix as well as matrices initialised from arrays.
• Matrix operations such as multiplication, dot product, cross product, equality.

Improvements:

• Results could be cached, increasing memory usage across the board but many algorithms would benefit with little programming effort.

Perlin

• Object orientated version of Julien Guertault’s improved Perlin noise code.
• Revised to use my Matrix classes and operations.

Picker

• Implements colour-picking of objects.

• The constructor selects an even distribution of colours over a requested range.
• Objects are assigned a unique colour which can be retrieved from a two-way look-up table.

• A rendered scene is examined for the presence of different colours and a list of objects present in a specified region is returned.

Plane

• Representation of a mathematical plane.

• Signed distance of a point from a plane,
• Intersection of a line and a plane,

SkyDome

• Generates and renders the vectors for a hollow hemi-sphere.

• Including texture coordinates for proper and artifact-free rectilinear texture display.

• Works out where on the hemi-sphere a light-source should be placed based on coordinates of the source within the texture.

To-do:

• Use VertexArray for rendering.

• Moving light-source (e.g. sun).
• Moving and morphing clouds.
• Night and day effects.
• Weather conditions.

Terrain

• Reads in a height-map from an Image file.

• Height-values are turned into way-points. Way-points are vertices with extra information used in pathing and obstacle collisions.
• Stores its different aspects into image channels; height data in blue, tree-density in green and floral-density in red.
• Generates the normals for the height values via matrix computations.
• Uses bi-linear interpolation to estimate the heights between the height map values.

• Rendering includes frustum-culling and level-of-detail binary-tree recursion.

• Uses Vertex and Fragment shaders to texture and colour the terrain as well as fading out the edges (to be used for e.g. unexplored areas).

• Flora is distributed across the terrain based on density values from the image map file.

• Trees (see the Tree class’s section).
• Three floral display-lists are created by texturing two crossing rectangles.
• Only flora close to the camera’s focus is rendered and the edges are alpha-blended to merge the transition into the terrain.

• Each time the terrain is rendered it calculates the way-point that the user’s cursor is currently over by retrieving the depth of that pixel and un-projecting using the model and projection matrices.

• Can also render an ‘occluding’ version of the terrain useful for colour-picking (see the Picker class’s section).

• Spherical and square obstacles can be added and queried using the Bounded class.
• Navigating around way-points uses the A* algorithm. Trees, water and buildings are treated as obstacles.

• Paths for units use two different scales of way-point subdivisions.

• The ‘minor scale’ is the set of way-points as defined by the height-map, it is the most granular representation of the grid possible.
• The ‘major scale’ is another representation of the height-map but with a lower granularity. For example, a grid with subdivisions of size 5 can be imagined which skips over the way-points between the 1st, 6th and 11th way-points as though these way-points were not involved in the connections between them.

• The overall path for a unit across the terrain is calculated from three subsections; the unit finds the nearest way-point which lies on a grid with the requested size major scale’s size, the unit then makes larger-scale jumps towards the way-point on this grid which is closest to the destination way-point, finally the unit moves from this way-point to it’s final destination once again using the highest granularity of pathing.
• Interaction with the open-list is optimised via a heap data-structure.
• The path is represented as a vector of way-points.

Improvements:

• Work out the floral-density from the tree-density channel and use the spare channel to define patches of water.
• ROAM rendering or vertex-array rendering for areas that will not change.
• The way-points used as the starting and ending major way-points should be the way-point with the lowest holistic distance to the final destination from a selection of neighbours.
• Pathing should take advantage of established roads by giving nodes representing roads a lower cost.

To-do:

• A mini-map version of the terrain to be rendered into a sub-window of the main window.
• Tree felling and animation, e.g. wind.

Tree

• The TreeForm class represents a programmatically generated tree-like structure.

• Recursively calls generate branches.
• Stochastically, two or three branches are spawned at the previous branches’ end-points and centre of the parent branch and rotated and scaled accordingly.
• Leaves are added which cross the new branches using textured rectangles.

• The Tree class tracks aspects of individual trees.

• Coordinates
• Visual display, such as tilt, scale and rotation.

To-do:

• Rendering of different stages of growth and decay (could use the recursive nature of the way the trees are created to achieve this).

Unit

• Represents a mobile element.

• Coordinates,
• Speed, accessible surfaces, maximum inclination and declination.

• Can follow a path.

• Interpolates between way-points based on the unit’s defined speed.
• Attaches the unit to the terrain.

To-do:

• Code for non-idle or pathless actions such as ‘gather’, ‘deposit’, ‘follow’, etc.
• Recalculate a portion of the route if the next way-point in the path has become obstructed.
• Introduce a model format to store a visual display for the unit.
• Store other data such as hit-points, carried items, etc.

Vertex

• A Vertex object represents a point of space with certain characteristics.

• Colour, normal, texture coordinates.

• A Waypoint adds extra properties to a vertex for use with height-maps such as information used in pathing and definitions for obstacles.
• The VertexArray class stores a vector of vertices and generates arrays suitable for vertex-array operations such as glDrawPrimitives.

• Currently index-arrays are generateable for a triangle-strip representation of the stored vertices.

To-do:

• Creation of VertexArray indices for different drawing modes e.g. triangle fan.

Water

• Represents and renders areas of water.

• Waves (sine) and turbulence (perlin noise).
• Caustics using textures.

• Only calculates height values for vertices above the terrain and within the frustum cone.
• Caches previous calculations for future use.

Improvements:

• Instead of sine-waves to calculate the height of all the nodes special nodes should be chosen to be oscillators. The remaining node’s heights should be calculated by their neighbour’s heights. This should ease the heavy CPU time requirement of the current implementation and allow for ad-hoc waves such as those created by a pathing unit.

Relationship Diagram