The Template Insertion Pattern (C++)

How I created a strange design pattern and how it proved to be so incredibly useful.

Like many amazing finds or new things, this particular solution came from a tricky problem. To understand the issue best, I have created a small diagram below that shows a simplified hierarchy of the action classes:

*This diagram is not an actual representation of the classes, it just demonstrates the basic idea.

As you can see at the bottom of the hierarchy, a particular action has 3 classes (a shared implementation and then child classes for both the server and client specific code). This means the client and server implementations derive from a common base and it is easy to write common code for both as well as functionality for client / server using either separate calls or virtual functions that are overridden. Above these leaf classes we have many parent classes that handle various different functionalities.

The issue here, which is actually a relatively common issue, is this:

What happens when we need one of the parent class functionalities to have common server or client code? It would look like this:

Ah, the classic diamond inheritance; Both the shared implementation and the server or client specific parent need to derive from the classes above, because their callbacks and variables rely on that information. I guess you could draw the diagram with the connection either how it is (with Fireball a child of Projectile Client) or Fireball Client as a child of Projectile Client. Either way, the issue is the same (the client has ambiguous parent classes). What we need is for Fireball to have derive from Projectile Client, but only on the actual client (because otherwise Fireball Server will be trying to derive from a class that it doesn't know about.

In the past, the solution has just been to put virtual functions in the shared implementation and then for each child that needs to, will implement the functionality themselves. This is especially annoying though when there are many classes and/or when the implementation is almost identical. Bonus annoyance if there is a lot of code for the implementation(s).

So we solved this by coming up with the idea of what we called 'template parent insertion'. I am sure there must be a formal name for this but I have not been able to find it (let me know if you know!). At first glance it appears very similar to The Curiously Recurring Template Pattern (CRTP), but in reality it is quite different, and is actually solving a different problem.

So how does it work? First of all, here is a diagram to help explain:

*I will attach some source code below to complement this diagram.

Basically the idea is that the shared class (Fireball in this case) is a template class which derives from the template itself, The child classes derive from this and pass in the class that they want Fireball to inherit from, via the template. Hence why, at the time, we sort of called it 'template insertion'; because it allows you to stick a class in-between. The server or client can insert different classes to each other, or one can insert a class and the other doesn't need to, which provides a great design for class hierarchies like this where we have a separate client and server implementation with a shared base.

Pitfalls:

The main issues I faced with this design is compiling with GCC on Linux. Firstly, in the base class (in this case Fireball), when referencing functions or members from the parent class (the template class), I had to always use this-> or it would be a compilation error. The other issue, in the same scenario but for template functions called from members or functions from the parent class, I had to always use the following syntax:

this->GetObject().template GetComponent< Health >();

Instead of:

GetObject().GetComponent< Health >();

Details of this issue can be read here.

So there it is, a relatively nice solution to a common problem. Although I'm sure in most situations you are better off rethinking your design such as trying to use free standing helper functions, or creating a separate implementation that doesn't derive from the Projectile, or even just using regular composition (storing a member that handles the specific implementation that can't be in shared code). For myself and the situation I had, this proved to be the easiest method to achieve what I needed, so maybe it will prove useful for others too. Programming has infinite possibilities and there is no perfect solution to everything. What is important though, is having as many patterns, tricks, designs and knowledge as possible to construct the best possible solution you can for a particular problem!

Example source code available here.

2D Mining Game

I have started work on a new game! I recently bought Super Motherload for quite cheap and played it through. Super Motherload is a Steam release sequal to the original free Miniclip game Motherload. There was also a paid version called Motherload Goldium which is now bundled with Super Motherload. They are all great games, with the latest being mostly a reskinned version of the original (new graphics, different characters) but also with some small new puzzles and things. It is surprising how addictive and enjoyable the game loop of these games is. The simple game loop works as follow:

- Mining down to get ores / resources

- Returning to the surface to sell them

- Purchase new upgrades in order to go deeper

- Repeat

The game limits you by having a fuel tank that must be refuelled and a hull damage meter. The joy of going further down into the ground and finding new rare ores and resources, which in turn allow you to upgrade your vehicle, is really fun and is very similar to the "Mine" in "Minecraft". Exploration is the key here, finding new places and being rewarded for your effort.

After playing Super Motherload I thought that the game was good, but had the possibility of being so much more. Firstly I did not like that the level is limited in width (you cannot go past a certain value left or right, which is wider than your screen). I also was not a huge fan of the puzzle elements involving the various bombs. I enjoyed them, but when a large percent of the best ores was gated behind puzzles I quickly got bored of them. There was just too many puzzles everywhere which made them less interesting. Lastly I am not a story kind of person and so I didn't really enjoy that the game just ends after killing the final boss, although it was quite fun and challenging. I would of preferred further potential for game-play without just replaying it the exact same with a different character.

For this game I would like to incorporate combat, as well as fog of war. I am also messing with the idea of a mode where you have a tower defence element on the surface, but I am not sure about this just yet.

I have also decided to use Unity to create this game. Two main factors contributed to this decision: Firstly, I used c# for my last project (rock climbing training app) and I really enjoyed it. It is such a nice break from c++ without memory management and dealing with libraries and includes etc. Secondly, after working for quite a while on my 2D engine with SFML, I felt like I wanted to focus more on the game development side as opposed to engine development. It took a huge amount of time to get the engine up to a usable level and even still, it is far from good and full of features. Implementing the smallest things would just take so much time, partially because I was focusing on optimisation and the design so significantly. Unity also has the bonus of being able to ship to multiple platforms, having a great community, having endless features and is also another great skill to add to my knowledge base.

2D SFML Engine

Recently I have been spending my spare time working on a new 2D engine in C++. The engine is built off of SFML (Simple and Fast Media Library) [2] which provides a platform independent layer with several modules that handle the following: System, window, graphics, networking and audio. SFML is a great base to build off of because it lets you skip the tedious beginnings of creating a multi-platform window and rendering system. SFML renders using OpenGL and is low level; focusing on providing basic functionalities without limiting the scope, architecture or design of your program. I have been using Trello [1] to track my tasks which as been working great.

Entity Component System

The main goal of this engine was to try my hand at writing an efficient and modern Entity Component System. I read many many articles on various ECS designs and eventually jumped into writing my own. I decided to go with an ECS where entities are simple POD's (plain old data) which contain a vector of handles to components (and keeps track of the component type). More on handles later. Components of each type are then stored in a custom vector like memory allocator which holds them all in contiguous memory and only ever adds components to an empty space or to the end. It pre-allocates a large pool of memory (user defined) so that it can reduce the chances of it having to perform a reallocation. Contiguous memory of components means that it is very fast to iterate over all components of a single type because there will be 0 (or as close as possible to 0) cache misses. This leads into the 3rd aspect of the ECS which is systems. Systems are essentially a module that run over a list of all components of a certain type (or multiple types). For example, I have a "Movement System" which operates on Transform Components. It handles updating the position / rotation of the transform component if it has any movement values set. There is a lot of data and information about this style of ECS, so I won't go into huge detail onto it. I find it more useful (and hopefully others do too) to show an overview of the actual implementation:

Handle System

I set up a handle system based off of Randy Gaul's SEL engine [8]. The system allocates memory for you when requested and returns a handle which allows you to access this memory. This works like a shared pointer except that the handle will properly update even if the memory has changed. The handle itself has two forms:

- Base handle (contains an index and a counter)

- Template handle (child of a base handle, templated to a type T which it holds and uses when the handle is requested to retrieve the data. This means you don't need to cast the type or know what it is, as it is saved in the template.

Post Mortem

Overall I think the engine works decently and does its job of being an efficient ECS well. I think the handle system is good in practice, but turns out to be a nightmare when trying to debug things because you cannot directly access the pointer without looking it up in the allocator (which is tedious). This handle system was based off of Randy Gaul's SEL engine [8], but I get the feeling that Randy never tried to use his engine to build a game. Once it is working, it works great, but the process of development has too many opportunities for pitfalls and frustration, which is where you spent most of your time when developing games.

The next step for me with this engine was / is to build a Python / Lua scripting system so that I don't have to directly interface with the engine. This would (hopefully) provide less opportunity to create bugs and errors when doing things in C++. It would allow better separation of game logic and engine code.

I may re-approach this engine in the future, it has a lot of room for adding features and development but right now I feel like I am not 100% happy with the final outcome of the engine core. It was a great experience setting up my first ECS and learning all about fast memory based architectures. I also enjoyed reading about various design patterns and spending time incorporating and designing them into my engine.

SFML is an amazing library and I would 100% recommend it to anyone getting into C++ 2D game development. It gives you so much freedom but allows you to skip a large amount of tedious, platform specific boilerplate that once you have done it before, isn't very enjoyable to setup again. It also allows you to extend the library to perfectly fit your needs and build features on top of it.

Resources

1. Engine Trello Board

2. SFML Website

3. Thor - SFML Utility / Extention Project

4. Example ECS

5. ECS Design by Tobs

6. ECS Design by Tobias Stein

7. Randy Gaul's Website

8. SEL (Simple Engine Library) by Randy Gaul