Boost C++ libraries and game engines

There is a neat development cost calculator on the boost web site. Pretty easy to use. You enter "code only" into the "include" combo box and get your magic answer:

$188,229,523

Wow. I mean... Wow! You get almost two hundred millions for free, into your personal disposal!
Only that makes it worth including Boost into your project, whatever you develop. Right?..

If we talk game engines in particular, there is certainly no need for all the excessive functionality the Boost libraries provide.
However, there are surprisingly many parts of it, which I've seen being reimplemented in the small and big game engines over and over again (and, frankly, implemented quite a few bits of functionality myself).
Such as:

• smart pointers
• memory pool allocators
• lexical cast 
• variant types
• program options
• property trees
• tokenizing
• threading wrappers
• signals
• serialization
• filesystem abstraction

 - these usually find their place in the "core" part of the game engine. Also there are more specialized parts, like:

• graph operations
• state machines
• regular expressions
• image operations
• networking
• python binding

All of these facilities (and many more) can be considered of direct use for your typical modern game engine.

Also, it's no doubt that boost code is of very high quality, tried and true, well-tested, portable and besides it is slowly moving into C++ standard. It uses template metaprogramming, which presumably in certain cases can improve efficiency due to aggressive inlining and doing some stuff at compile time. The code is also considered to be generic, so one is supposed to be able to flex it to high degrees adapting to one's own needs.

Jason Gregory in Game Engine Architecture book (in my opinion, rather good one) mentions the topic:

• Boost provides a lot of useful facilities not available in STL.
• In some cases, Boost provides alternatives to work around certain problems with STL's design or implementation.
• Boost does a great job of handling some very complex problems, like smart pointers. (Bear in mind that smart pointers are complex beasts, and they can be performance hogs. Handles are usually preferable; see Section 14.5 for details).
• Th Boost libraries' documentation is usually excellent. Not only does the documentation explain what each library does and how to use it, but in most cases it also provides an excellent in-depth discussion of the design decisions, constraints, and requirements that went into constructing the library. As such, reading the Boost documentation is a great way to learn about the principles of software design.

If you are already using STL, then Boost can serve an excellent extension and/or alternative to many STL's features. However, be aware of the following caveats:

• Most of the Boost classes are templates, so all one needs in order to use them is the appropriate set of header files. However, some of the Boost libraries build into rather large .lib files and may not be feasible for use in very small-scale game projects.
• While the world-wide Boost community is an excellent support network, the Boost libraries come with no guarantees. If you encounter a bug, it will ultimately be your team's responsibility to work around or fix it.
• Backward compatibility may not be supported.
• The Boost libraries are distributed under the Boost Library License. Read the license information carefully to be sure it is right for your engine.

But frankly, while I agree about smart pointers and documentation, there are bigger  concerns usually popping up regarding Boost:

• Compiling time - due to all inter-dependencies and heavy template use
• Code readability 
• Performance (usually as a tradeoff for flexibility and safety, there are quite a few horror evidences)
• Easiness of misuse and building extra complexity out from nothing
• Versioning problems
• Huge size of the library itself, when used as a third-party dependency

It turns out that there is still a lot of controversy regarding the very topic of using boost in games. People are quite often cautious about it, and in many cases avoid using it altogether.

Of course, it does not really come as much surprise in regards to the game industry as specific branch of software development. The mental model of your typical game engine architecture, sketched directly from my head into an (almost) UML diagram looks like this:

...which hopefully explains a lot.

Recently I've started to try porting some of five years old code to Linux, and on the quest of eradicating windows.h dependencies found out that there is a class called "FilePath", which allows to do some basic filesystem operations and uses WinApi directly.

It came into my mind that its functionality is an ad-hoc implementation of a subset of what boost::filesystem library provides. Except that the latter is portable, has more functionality, is more stable and well-documented.

There are certain biases I've got, and due to all aforementioned factors (including the NIH syndrome), the decision did not seem to be as simple to make.
Another mental model of mine has crystallized with time, and here's the sketch of it:

I remember Joe Armstrong saying in Coders at Work:

Seibel: But do you think it's really feasible to really open up all those black boxes, look inside, see how they work, and decide how to tweak them to one's own needs?

Armstrong: Over the years I've kind of made a generic mistake and the generic mistake is not to open the black box. To mentally think, this black box is so impenetrable and so difficult that I won't open it[...] But it's not actually difficult. [...] ...you should certainly consider the possibility of opening them.

Shattering the personal biases by means of opening black boxes sounds like a good plan.

So, where do all the dependencies come from?

Here's the layout of the whole boost include directory (which is roughly 50 Mb, while the whole boost directory is 200 Mb), made with StepTree:

We don't really need all of that. Luckily, there is bcp utility, which is part of boost distribution and does exactly that - it allows to strip away only the subset of code needed. So, if I am interested in boost::filesystem library:

cd boost
mkdir ../boost_fs
bcp --boost=boost filesystem.hpp boost_fs

 It creates boost_fs folder, which has only the code needed to compile this particular library and use it. However, this folder is around 8 Mb, which is a bit more than could be expected (keep in mind that most of this code is header files, which most certainly are going to be included into the project). The layout looks like this (this time rendered in WinDirStat):

The boost::filesystem code itself takes just about 3%! The rest is occupied mostly by:

• mpl - which is an "all-around c++ template tricks" kind of library
• preprocessor - which is a library to do the copypasting job for the programmer in very smart way
• type_traits - which allows to get and use some basic information about templated types in case of templated classes 

Granted, code reuse is generally a good thing, and  boost (having the goal of being highly reusable library itself) is known to do it heavily, cross-referencing between the libraries. But this looks a bit extreme.
Ironically, though, the development guidelines for the Boost libraries do discuss the topic of excessive library interdependencies.
Let's run again bcp in "report mode":

bcp --report filesystem.hpp fs_report.html

This generates html report file with all the dependencies gathered. At the bottom of this file there are all the include chains gathered (the file is big, mind you).
This representation is only helpful in showing that there are very many header inclusion paths starting from boost/filesystem.hpp and most of them end in either of other aforementioned boost libraries.
Let's try to build an inclusion graph using Doxygen:

sudo apt-get doxygen graphviz
cd ../boost_fs
doxygen -g
emacs Doxyfile

Then edit the file to ensure parameters are set:

HAVE_DOT = YES
RECURSIVE = YES
EXTRACT_ALL = YES

Save, and then:

doxygen Doxyfile

The part of inclusion graph for the main header, boost/filesystem.hpp look like this:

The gate to the flurry of includes seems to be opened via boost/iterator/iterator_facade.hpp, which has another graph on it's own:

Browsing these graphs on its own already starts to give some insight, but to get things even more clear we could try to inspect even different representation of the source code... the source code itself.

Doing that, it becomes more clear where do these dependencies come from. For example, there is a directory iterator, which is templated by the path type, which in fair enough, as the path can have possibly Unicode representation. Iterator classes are generic in a sense that they don't do many assumptions about the particular type uses, and thus require the general metaprogramming facilities provided by mpl and typetraits. Mpl, in turn, uses preprocessor libraries for its needs. And then there are preprocessed headers for several compilers... quite a lot of things are happening in order to provide the functionality which you actually may not need.

In this particular case there is, for example, physfs library which might suite the needs even better without providing nearly all the generic facilities as boost does.

Does it mean that there is no use for boost? Of course not:

• One still can use it, but physical dependencies tracking is important even more than usual. In case of filesysem it could be wrapped with an additional interface, so as few cpp translation units as possible include boost/filesystem.hpp and the rest which is pulled in together with it.
• One can also possibly take the parts of interest and "strip" them out of unneeded generic parts. Here's a good example:  OgreAny.h
• One can read the documentation and, most importantly, the code to borrow good practices and ideas (and to examine the "bad" ones as well).

Whatever you do, just make sure you crack the black box open first.

Bees in Space, or story of my first freeware game project

It was around five years ago when I decided to try making a small game project on my own and publish it on the internets as freeware.

The reason was that I wanted to experience myself a "full" game development cycle in miniature.

And for fun, of course.

Probably the end result is not such a big deal, but I've certainly enjoyed the process and learned quite a bit from it. Actually doing the things, no matter how small they appear, gives that invaluable insight into their very nature, which can not be gained otherwise. When those small, non-uniform (and often beyond the boundaries of one's present competence) things form a complete whole, a closed loop, then this insight may get even more eyes-opening.

At least that's my feeling about it, in the end.

So now, after five years I've suddenly realized that it was not that bad, after all, and it might be a good idea to reflect on that past thing. Just for fun, again.

Picking a theme
The old-school game called Hexxagon was a primary inspiration for that. It was very tempting, of course, to start something grand, like Diablo or GTAIII clone, but that would obviously defeat the whole purpose of trying to finish the game and see what happens after that.

Being as simple as it is, it still involves quite a bit of work in different areas of programming, gameplay design, user interface, art, "marketing", maintenance and support etc - even though every problem here is a toy one, as comparing to a "real-life" game project.


The Game

Essentially, it's a zero sum, deterministic two-players game, somewhat similar to othello.

In it's simplest form AI for such a game is using minimax algorithm, quite often with alpha-beta pruning optimization, to search the game tree, depth first, to a certain level (or until the time limit is reached).

There is quite a bit of research in this area, with a lot of heuristics proposed to improve the "smartness" of the evaluator and game tree search. They would be certainly interesting to try implementing, but as soon as I've got the basic minimax with alpha-beta pruning working, I decided not to bother with this for the time being.

Again, for the sake of being able to work on other things and finish the game.

The board evaluation procedure was dead simple - it was the difference between the one's and rival's balls, the bigger the better, weighted together with the possibility to move, based on some simple heuristic, details of which I don't remember.

The "board" was represented as a bitmask, wrapped by rows, with bit being set if there is something in the corresponding cell (with "something" having different meaning depending on the context), and the whole board state was represented as a triple of bitmasks: one for black balls, one for white balls, and one for empty cells.

Then the bulk of operations/queries on the board state can be conveniently/efficiently done with the bitwise operations.

This, I believe, is called "bitboards", and is quite common trick when programming similar two-player games.

The Engine
I admit that quite a bit of things here could be done in much simpler way, especially in context of such a simple task at hand.

However, in retrospective it does not look that bad. It was certainly good learning experience, and some of the engine design decisions taken seem to have saved quite a bit of time, which would be otherwise wasted doing boring and repetitive things manually and then fixing all the mistakes done in the process.

Few of the things, in no particular order:

• Game-specific code was minimal and separated from the rest (an "engine" code)
• The engine code itself was quite modular and layered, different layers were communicating through the interfaces (for example, widgets are using the sprite manager to display sprites, which is using the renderer interface to draw the textured quads, and the renderer interface can have separate implementations for different graphics APIs - I used to have two of them dx8 and dx9). 
• Sprites were packed into "packages", using custom format, every sprite was cut into power-of-two chunks in a quadtree, and then those chunks were laid out in runtime on the surfaces in the texture memory cache. There was a custom C# tool which did the packing of the sprites, and generating of the font packages as well.
• A poor man c++ reflection system (using macro and template tricks) for the classes, derived from the "base game object" class, which made it possible to automatically serialize object hierarchies in text/binary format.
• Custom text format for representation of the object hierarchies in "scripts". I used XML at first (because I knew that rolling your own is a sin, and XML is the answer), but it turned out to be extremely ugly and hard to edit manually. So I did roll my own (which I called JML), using flex/bison, and it turned out to be not as bad as they said.
• There is a "data binding" mechanism in scripts, the idea I've borrowed from Qt back then, and then eventually Microsoft has stolen it from me and implemented in WPF :)
• I've got a set of ad-hoc python scripts which would generate project files (.vcproj/.sln, .dsp/.dsw). Every module had a text file called depends.txt, which used a simple syntax to describe which other internal/external libraries it references. The python script would then walk the source tree, find these files and do the generation. This way I could experiment with different physical source code layouts and manage dependencies explicitly without tinkering for ours in Visual Studio property dialogs.

So, for example, the main menu dialog script would look like this:

dialog "MainMenu"
{
    // ...
    picture "Logo"
    {
        skinpack        = "logo";
        extents         = { 40, 30, 330, 100 };
        stretch         = true;
        skinframe       = 0;
    }

    shortcut "EditorShortcut"
    {
        Key             = "E";
        Action          = >>MenuSystem.OnEditor;
    }
        
    button "ContinueGame"
    {
        text            = L"Continue Game";
        extents         = { 290, 160, 270, 48 };
        font            = "font_menu";
        fontheight      = 48;
        fgcolor         = 0xFF49CD49;
        shadowcolor     = 0xFF11FF11;
        hoverfgcolor    = 0xFF88FF88;
        unpress         = >>MenuSystem.OnContinueGame;
        visible         = <<Core.Game.HasPlayers;
    }
    // ...
}

Design

It was obviously programmer art, from the beginning to end.

I've found a few free sound samples on the internets, painted basic game screen elements myself in gimp (that included the space bee from the main menu screen).

I've used Comic Sans MS in user interface, which is a trademark of amateurish design.The interface itself is not consistent, not intuitive, badly laid out and uses a horrible color palette.

So it's hard to call it a "design", rather an inconsistent pile of placeholders. Which I did realize back then, but again did not overfocus on that, hoping that eventually I might get a help from someone who has a taste and gets interested in this.

The Editor

I've decided to add a certain "non-linear" twist to the original Hexxagon gameplay.

The player would progress through the sequence of "levels", which get more complex in terms of the original board setup (the "smartness" of the computer opponent would still remain the same, as it is essentially the same limited depth/time minimax solution tree search). When certain level is won, it opens one or more new ones, and it's up to player to pick which one to play next.

So, it is not necessary to win all the levels in order to "beat the game". The levels form a kind of a graph with nodes being the particular board setups. And if there is an edge from a source level to destination one, it means that destination is available to play after the source is won.

While all the levels and transitions between them could perfectly be "designed" in Notepad (and probably it would be a better idea to keep it that simple), I've decided to make an "in-game" editor for those.

Which turned out to be pretty rad in the end:

One could pan, zoom the whole graph, select node groups, move them around, double click on nodes and edit them etc.

The whole game, when zoomed away, would look like a big DAG, where the leftmost node here is the starting level, and the rightmost one is the end level, which has to be won to finish the game.

Release
The testing (including the focus testing) was done by myself and my friends. The game was obviously far away from being ready, but at least it was somewhat playable, so I decided not to wait an eternity "til it's done" and publish an early version.

I used NSIS for the installer, and was quite happy with that, as the whole distributable size was below 1Mb, which was pretty good for the downloadable game.

Funny enough, I clearly remember myself not counting the things like making an installer or the game's web page as work, which has to be taken into account.

Turned out, that even with the help of such great tools like NSIS or Inno Setup (which make life much, much easier in this regard), it still took considerable amount of time, especially since I did not have much previous experience in these areas.

So that was another good lesson to learn.

Evaluation
I have submitted "version 0.4" to tucows for evaluation and basically forgot about it, because the evaluation queues are pretty long, and it can take a few months before your software gets there (well, it used to be the case five years ago, but I presume it's not very different today).

So it was quite a surprise for me to finally get my game reviewed and rated... with whooping three cows! Which according to the tucows folks themselves means:

If your application receives a three-, four-, or five-cow rating, congratulations! As you'll see by reading the Ratings Guide, this is no small feat. You are in the company of some of the best programmers in the world. We receive hundreds of requests each week for inclusion in the Tucows software library. The fact that you scored in the three-cow range or higher has earned you a spot on our site. This is a sign that your product is among the best of its kind.

See? My little game is among the best of it's kind!

Seriously, though, I've got an extremely good feedback in an e-mail soon after, where they were giving a detailed explanation about how did they evaluate the game, separately on topics of visuals, sound, fun and longevity, user interface, easiness to grasp etc.

Obviously, graphics, sound and user interface were quite far from being the strongest sides, and that was very expected.

Another weak side was perceived complexity of the game, and most of all that it is very hard for a new person to figure out what are the rules of the game and how to play in general (even though the rules are quite simple).

It was also quite expected, as I was observing it myself during my "focus tests", and was going to "fix" it in later versions by making a tutorial (quite frankly, I had to postpone it to  "later versions" because it also turned out harder than I was originally expecting).  

But still, I've got my three cows and that was quite a revelation.

Aftermath
Well, there is none. Soon after I've decided to change my job and move to live in another country, so it was left where it was, at version 0.4.

I did not finish the game, there were quite a bit of things to do yet, but still managed to experience one iteration of the possible game project life cycle, from beginning to what can be called "end".

It's not on tucows anymore, but still is downloadable on the internets.
I've also made the source code public, and it was available until my hosting period has ended.

But all in all, being a failure it is (i did not really finish the game, and it did not find its players), it still was a success to me personally, in the experience it has brought.