30. Januar 2013

Case Study: Role-Playing Game in C++

A minimal implementation in C++ of a role-playing game with 2D graphics, as part of an exercise at university.

Note: if you do not want to read anything, you can skip to the videos at the end of this page.

Background

Programming games is a challenge because they pose a variety of tricky programming questions, largely due to the dynamics of games and the bandwidth of tasks that need to be solved. The latter often include the interaction between objects, the specification of the game rules, the user interface, and the artificial intelligence. Måns Vestin from RaySearch Laboratories (former Technical Director at EA DICE) pointed at a few programming challenges during his talk at KTH Stockholm in January 2013 – especially those occurring in larger gaming projects (such as Battlefield). But that is another story. This article describes an implementation of a game that solves all the above-mentioned tasks in a minimalistic way.

Game

The game itself is a real-time role-playing game, loosely coupled to the saga of the Lord of the Rings. The objective of the game is to find the ring, while avoiding being taken out by orcs that are all over the map. While the game is real-time, the time between two ticks is made very large and all actors move on a checkerboard-like map. This avoids having to bother with a lot of geometrical issues. Orcs and rangers can appear at different places on the map. Some items can be found on the map and used by the human player while searching for the ring.

Paradigmas

Since there was a strict deadline, I decided to develop the game in a test-driven manner. This was also convenient because a game is a piece of software that can easily broken up into small features. The second paradigma was adherence to the model-view-controller scheme, which also facilitated test-driven development.

Architecture

The game has separate modules for the model, the view, and the controller. The algorithms are separated in order to make testing easier. The game depends on the cairomm library and the X Window System for rendering graphics to the screen. Unit testing is done with the help of CxxTest, which can be tightly integrated into CMake using a macro. CxxTest is suitable because one does not need to add or remove a lot of boilerplate code for each test.

The model of the game consists mainly of the map and three kinds of objects: actors, items, and effects. Actors can move on the map, pick-up items, use items or drop items. Effects are triggered regularly and represent events in the game, e.g. new actors entering the game.

Interactions

A game is full of more or less complex interactions. Here, object-oriented programming is very helpful. The following figure illustrates the relationship between some of the C++ classes. An edge between classes A and B denotes makes use of.

Algorithms

The presented game is not very heavy on algorithms, mostly because all geometrical problems have been avoided by using a map with very large tiles. However, the artificial intelligence that controls all computer players requires a path-finding algorithm. The computer players (orcs, rangers, and elbs) are basically finite-state machines that can switch between scouting, resting, hunting, and fighting. In most of these states, the computer players need to find the shortest path to either an enemy, or to another spot on the map. Path-finding is conducted by A* search.

Language

Some features of C++11 turned out to be very helpful. The most helpful were function binding (for mapping keys to actions for the human player), lambda functions (customizing behaviour of AI players), shared pointers (simplifying memory management), and weak pointers (avoiding memory leaks in circular references).

Videos

Here is a time lapse video of a game session where the human player succeeds and finds the ring:

The same game session in real-time:

Here is a time lapse video of a game session, recorded on a mini-map:

The same game session, in real-time:

And a few screenshots: