Monthly Archives: January 2014

Simple and Efficient Singleton Pattern

For game engines the singleton pattern is pretty commonly used for various global accesses, like for the core engine or for specific systems. Often times things like texture managers, the graphics implementation or a physical simulator are represented as singular entity that can be accessed globally.

A singleton pattern can be used to help facilitate and assert the existence of only one of these systems at any given time. This is important for a lot of code that is created under the assumption that only one given instance will be alive at once.

Advantages of Singletons

The biggest reason singletons are used is for code clarity. Any programmer that realizes something is a singleton is instantly informed of how it should be used. Beyond conceptual aids a singleton can also be an efficient means of allowing global access of an object. Often times in games everything is owned by something, otherwise referred to as the “Ownership Pattern”.

If a game consists purely of things owning other things (except for the core Game or Engine object), retrieving different systems from global access might be hard. This is because the Engine would be the only global thing. Code like this:

is long and annoying and also inefficient; there are many unnecessary levels of indirection. Instead a singleton can be used to solve such a problem.

A Traditional Approach

The traditional approach to creating a singleton is to utilize some code like so:

This approach does in fact ensure that only a single instance of a given class is alive at any given time, and can be especially effective if the constructor and destructor are declared in the private section.

Drawbacks

There is a pretty big drawback to this traditional style: construction and destruction order. C++ makes no guarantee about the construction and destruction order of objects on global (file) scope. This means that the code run for each destructor of every singleton instance (despite construction time) can run in any order.

This poses a huge problem for systems that depend on one another. What if the TextureManager class contained a pointer to the Graphics class? What if the destructor of the TextureManager tries to access the Graphics pointer and the Graphics singleton has already destructed?

Such an issue does have workaround solutions, but it might be best to have some form of singleton that controls construction and destruction explicitly.

A Better Singleton

Here’s a simple way to implement a singleton and allow explicit construction and destruction:

This singleton is actually quite safe due to the simple assertion in the constructor. The nice thing about this assertion is that it can be compiled away during release builds. This might be considered an advantage against the traditional approach, as the traditional approach will often times have a boolean flag to test for previous construction (in the assembly of the compiled C++).

Since it is a slight inconvenience to add the instance handling to every class you wish to be a single the use of a template mixin can help. Making such a utility can be tricky due to multiple inheritance. I will leave solving the multiple inheritance issue as an exercise for the reader.

I myself use this sort of singleton (I don’t even have a utility) and enjoy it. I actually don’t even use a Get function but just have a global extern’d pointer in my header.

I’ve also seen this exact implementation in a few areas, one of which is in an article by Scott Bilas in the first Game Programming Gems book (he covers the multiple inheritance issue),

Setting up wxWidgets

wxWidgets is a nice cross-platform GUI library for C++. I know quite a few colleagues that used it for creation of various editors and applications. One of them is Sean Reilly, who wrote a really useful series of steps to follow in order to setup your wxWidgets project. Here are his steps:

Hopefully this is helpful to someone!

Automated Lua Binding

Welcome to the fifth post in a series of blog posts about how to implement a custom game engine in C++. As reference I’ll be using my own open source game engine SEL. Please refer to its source code for implementation details not covered in this article. The folder of interest would be LuaInterface.


Introduction

Binding things to Lua is twofold: objects and functions must be able to be sent to and retrieved from Lua. Functions can be either static C or struct/class methods. Objects can be sent “by value” or “by reference”. As you can imagine it is important to be able to unify and simplify the binding process as much as possible to reduce all manual dev-work and upkeep.

Generic C++ Functor

As with many things in a modern C++ game engine it is critical to have a generic C++ functor. Ideally this functor can wrap around class/struct methods (not only static functions). It is also possible have this functor able to refer to a function within Lua as well.

Please see my article and slides on C++ Function Binding for implementation details not covered here.

Prerequisites

This article is on the topic of automatic Lua binding; if you’re unfamiliar with how to bind simple C functions to Lua please do a little research and come back later. The deep end of the pool is actually pretty deep!

I also suggest a working knowledge of C++ templates before trying to implement these sort of features. A working knowledge of Lua is also essential.

Setting the Boundaries

With a scripting language it’s important to clearly define what you want to expose to script. Is the entire game in Lua? Are only specific parts accessible? What are the boundaries. It’s all too easy to get very caught up in what to send, what to implement, what not to do. Having clear boundaries of exactly what you want to do is the best way to start coding.

Passing Objects to Lua

Objects can be passed to Lua by reference and value. A reference would consist of 4 bytes of memory to contain a pointer to some C++ memory. This allows Lua to store a “reference” to an object in C++. Most of the work involved in this type of object binding is in allow Lua to call C++ methods or functions on the pointer its storing.

The benefits of this approach are such that: calling class methods is pretty fast and shouldn’t be a worry; fairly simple to implement as most of the work is finished by creating a generic functor in C++; no hassle or upkeep when wanting to send new types of objects to Lua -each object is just a 4 byte pointer.

Passing by Reference with lightuserdata

There are two ways I’d recommend to pass an object to Lua with: userdata and lightuserdata. A lightuserdata represents a void * in Lua and can hold a reference to an object in C++.

Here’s how one might send and retrieve lightuserdata from Lua:

This method is very fast, simple to implement and has very minimal memory overhead. Additionally lightuserdata can be compared to one another, and are equal if the underlying address is equivalent. However, one cannot attach metatables to lightuserdata and there is no sense of type safety what so ever. A lack of type safety means that if someone passes a lightuserdata into an incorrect C function the host program will likely crash.

With lightuserdata the following code is possible:

This solution will work for one, maybe two people working on a smaller project or minimal amount of code. I can imagine that the lack of type safety will be the biggest issue as time goes on.

Reflection for Type Safety

It is possible to implement type-safety in Lua. However this requires Lua code to be maintaining type information. Lua is a scripting language meaning it ought best be used to script things. Something so integral and common as type-safety might better be implemented in lower-level C++ code.

Implementing type safety on the C++ side has two benefits: efficiency of implementation; type-safety can optionally be compiled away in release mode.

I highly recommend building yourself a simple, custom introspection library in C++. All that is really needed to start is the ability to query a type’s size and name efficiently. Please see my older article on custom Introspection or the game engine SEL for examples on how to implement such a system.

With a simple macro-based registration system one can register and lookup type information via introspection like so:

After this is complete and working (if you don’t have an implementation of introspection yet this is fine, just think of it as a black box) a small generic Variable object ought to be created. Sample code of a functional Variable object is in this post.

A Variable can be used like so:

It is important to note that the Variable itself is not a templated type!

When passing an object to Lua we can send a pointer to a Variable. As long as the Variable exist in memory in C++ the lightuserdata within Lua will point to a valid Variable. Upon retrieval of the Lua object back to C++ a type assertion can be run:

Generic Static Function Binding

Bind C-style static functions in a generic way makes heavy use of custom introspection. The way I was originally taught was to just throw the entire binding function (in C++) at you all at once and let you suffer. Prepare to suffer as I did!

This function isn’t doing the bind, it’s what is bound. Every time a function in C++ is called from Lua, this function is called first.

An upvalue in Lua is akin to static variables in C. Using this we can attach a pointer to a generic functor to a bound C function within Lua. As Lua calls a C function this upvalue is retrieved and eventually used to actually call the C function.

The rest is just a matter of handling variables to/from Lua. In the above example the Variable object contains some helper functions call ToLua and FromLua. The nice thing about my implementation of this within SEL is that no heap memory is used during this entire process! All this code boils down to a very efficient method of generically calling C functions.

I will leave binding C++ methods as an exercise for the reader. By now you ought to have an idea of where to look for example implementation! The idea is to handle type information for the “this pointer” of the method, and pass around an actual “this pointer” to call the method.

Calling Methods from Lua

Lets say you have an implementation that allows Lua code like the following:

A few things need to happen here. The first is that the object in question should only call methods that are actually methods of that specific type of class; one cannot simply bind all C++ methods and place functions in Lua within the global scope. Any object type could call any method type making for a lack of type-safety and dangerous code.

At this point the lightuserdata will have to be upgraded to a full userdata. Full userdata in Lua enjoy benefits such as the ability to set and modify metatables. If you’re not familiar with Lua metatables please do a little research on the topic and come back later.

A full userdata allows us to place a copy of a Variable within Lua memory, instead of just a void *. This means a temporary Variable can be used to call ToLua, instead of requiring that the Variable sent stays valid in C++ for the duration of usage within Lua.

Currently a way to create metatables for all of our C++ types is required. Assuming a linked list of all TypeInfo objects from the introspection system is available:

This loop is just creating metatables given the string names of what each metatable should be called.

After the tables are created the actual C++ methods and functions should be bound. This turns out to be really simple! It is assumed that each function and method registered within the introspection system can be passed to the function at some point (perhaps during registration of the type information):

And that’s really all there is to it! The idea here is to make sure that a type with methods sent to Lua has its userdata fixed with a metatable containing the available methods to call. When the __index metamethod is called it will search within the metatable itself for an appropriate member. Members of the metatable are the functions we bound to Lua. After they are fetched they can be called. This is what happens behind the scenes when we do:

Passing Object by Value

Passing objects by value is actually much more difficult. The idea is to utilize tables to to store representations of the members associated with a class or struct. A table can be used to represent state of an object.

The __index and __newindex metamethods of a userdata should be set to look into the state table first. This lets users assign new values, and lets your ToLua and FromLua functions copy members from C++ to/from this Lua state table.

If a member is not found in the state table the metatable can then be searched by setting the __index metamethod of the state table to refer to the proper metatable.

All of this table indirection does incur significant overhead, however it allows objects in Lua to be used like so:

I myself have not implemented this type of Lua binding, though it is entirely possible and can be quite nice to work with. I reiterate that adding this many tables incurs both memory and performance overhead not seen with the other styles. This seems to be the only drawback.

Conclusion

Well this post turned out longer than I expected -over 2k words! Hopefully the information was clear. It’s really nice being able to refer people to a complete and working example such as the SEL engine; it makes writing articles much easier and simpler.

Hopefully this can help someone out there! As always feel free to ask questions or provide comments right here on this page.

Please see Game Programming Gems 6 ch. 4.2 for more information about binding C++ objects to Lua,

Simple Sprite Batching

Welcome to the fourth post in a series of blog posts about how to implement a custom game engine in C++. As reference I’ll be using my own open source game engine SEL. Please refer to its source code for implementation details not covered in this article. Files of interest are Graphics.cpp and Graphics.h.


Batching and Batches

Did I say “simple” sprite batching? I meant dead simple!

Modern graphics card drivers (except Mantle???) do a lot of stuff, and it makes for passing information over to the GPU (or retrieving it) really slow on the PC platform. Apparently this is more of a non-issue on consoles, but meh we’re not all working with consoles now are we?

The solution: only send data one time. It’s latency that kills performance and not so much the amount of data. This means that we’ll do better at utilizing a GPU if we send a lot of data all at once as opposed to sending many smaller chunks.

This is where “batching” comes in. A batch can be thought of as a function call. In OpenGL you’ll see something like DrawArrays, and in DirectX something else. These types of functions send chunks of data to the GPU in a “batch”

Sprites and 2D

Luckily it’s really easy to draw sprites in 2D: you can use a static quad buffer and instance by sending transforms to the GPU, or you can precompute transformed quads on the CPU and pass along a large vertex  buffer, or anything in-between.

However computing the batches is slightly trickier. For now lets assume we have sprites with different textures and different zOrders.

Computing Batches

In order to send a batch to the GPU we must only draw sprites with the same texture. This is because we can only render instances (or a large vertex array) with a given texture in order to lower draw calls. So we must gather up all sprites with the same texture and render in the correct order according to their zOrders.

If you are able to store your sprites in pod-structures then you’ll be in luck: you can in-place sort a large array of pods really easily using std::sort. If not, then you can at least make an array of pointers or handles and sort those. You’ll have extra indirection, but so be it.

Using std::sort requires STL compatible iterators, and you’ll want one with random access  (array index-style access). Here’s an example with a std::vector:

The sort implementation within your package of the STL is likely going to be quicksort.

This sort will sort by zOrder first, and if zOrders are matching then sort by texture. This packs a lot of the sprites with similar textures next to each other in the draw list.

From here it’s just a matter of looping over the sprite array and finding the beginning/end of each segment with the same texture.

Optimizations

A few simple operations can be done here to ensure that computing batches goes as fast as possible. The first is to get all of your sprites together in a single array and sort the array in-place. This is easily done if your sprites are mere pods. This ensures very high locality of reference when transforming the sprite array.

The second optimization is to only sort the sprite array when it has been modified. If a new sprite is added to the list you can sort the whole thing. However there is no need to sort the draw list (sprite array) every single frame if no changes are detected.

Conclusion

Like I said, sprite batching is super simple in 2D. It can get much more complex if you add in texture atlasing into the mix. If you wish to see an OpenGL example please see the SEL source code.

I was able to render well over 8k dynamic sprites on-screen in my own preliminary tests. I believe I actually ended up being fill-rate bound instead of anything else. This is much more than necessary for any game I plan on creating.

C++ Enumeration Reflection

Welcome to the third post in a series of blog posts about how to implement a custom game engine in C++. As reference I’ll be using my own open source game engine SEL. Please refer to its source code for implementation details not covered in this article. Files of interest are EnumData.h, Enum.cpp and Enum.h.


Crazy Viking Studios

Lets thank the Crazy Viking Studios guys for their generous contribution in knowledge on this topic! One day as a student I emailed them about their enumeration editing in their awesome editor for Volgarr the Viking. They responded with a bunch of source code in a demo! The techniques here have been learned from Taron their programmer.

Introduction

Enumerations in C++ are a pretty nice feature. They provide type safety and a very readable way to name a lot of various types of constants. However there could be so much more added on top of enumerations in C++ to make extremely useful.

Lets take a trip through our imagination and imagine a game editor. In this editor you can create arbitrary constants with a name and associated integral value. This would be great for some sort of scripting or game logic.

This here can be implemented in C++ (during coding time as a compile-time constant) through enumerations. However there are some features that can be added to this to allow an editor to manipulate things:

  • Add new entries
  • Modify existing entries
  • Delete entries

Basic Enumeration Editing

In order for an editor to manipulate this information within a C or C++ file some run-time memory is required to store a representation of the actual enumerations in code. Data tables (structs) will work well for this. Lets imagine a structure to contain one of these enumerations; we’ll need string representations of all of the enumeration entries:

If an Enum instance were created to contain identical string representations of the entries with the Spells enum, then a constant-time conversion of enumeration to string could be achieved just by indexing the Enum vector with a value.

Converting a string back to an enumeration would best be done with a small hash table. This will keep string to enum conversions const-time.

Much to be Desired

This is all fine and good, however if a user creates a new entry as a string this won’t update the actual C++ enumeration entries -new entries only exist until the editor shuts off. Additionally there isn’t an easy way to lookup a particular Enum struct. It would be nice to be able to lookup an Enum struct in various ways, such as by string name or template type. It would also be cool to be able to serialize enumerations to/from file.

It might be fairly simple to actually modify the source code containing a particular enumeration in C++ whenever an entry is modified, deleted or added. This would let programmers actually use enumerations created in an editor within their code (after a recompile). It is also possible to hookup the new entries to be loaded in the Enum struct as a string literal.

Automation

As you can imagine a lot of manual labor is going to be needed in order to upkeep all of this crazy editing and modifying of enumerations. Some generalization and automation is needed to keep dev-work at an absolute minimum.

This is the time when I reference an old project I created to demonstrate a simple idea for serialization in C. The trick is use a source file and include it multiple times with various macro definitions. The source file to be included fills out the macros, but the macros are interpreted differently depending on when it was included. This allows you to write data files and interpreters using the preprocessor.

This is exactly what we need for building up some automated reflection and editing of enumerations.

Imagine a data file like so (a header without multiple inclusion guards and some macro invocations):

Lets take this data file and create a normal enumeration:

As you can see the macros from the data file are going to interpret the data as an enumeration. It is important to just always #undef all the macros in case they were previously defined.

After the preprocessor runs and the macros expand we will end up with something like:

Now the key part comes with defining the macros again to interpret the data in an all new way. Here’s an example to automate the creation of the Enum struct containing string literals:

The idea here is to construct an array of const char * literals and pass them to the Enum struct’s constructor. The struct can loop over them until the sentinel NULL value is found. When expanded by the preprocessor this file might look like:

While the Enum struct is looping over the literals passed to it in the constructor, it can also be adding the strings to a hash table to lookup appropriate indices.

Editor Support

Now that a great scheme for automation of generating the actual enumeration data is setup, all that is required is to make sure that an editor can easily find an appropriate C++ file to modify when entries are modified. My solution was just to cram all enumerations into a single C++ file. This C++ is detailed with a nice comment saying something like: WARNING: This file is auto-generated by the Enum Editor.

This actually works pretty well but has a single drawback: editing an enumeration causes a global recompile of the project. There are no separate namespaces or naming schemes in my own implementation, meaning that each enumeration has to be unique to avoid compilation errors.

From here it’s just a matter of writing to your C++ data file.

Tree Heirarchy

Wouldn’t it be great to be able to say “This enum is a subset of this entry”? That might have sounded confusing, here’s an example:

The idea is to allow each enumeration entry to contain an enumeration by creating a tree hierarchy.

This would be great for all sorts of game logic or general organization! It’s also possible to implement a really fast IsA function, so you could go if(type->IsA( Dragon )). Implementing this would just be a matter of traversing the tree hierarchy.

Enumeration Features

I implemented a bunch of rag-tag features in my game engine SEL and would like to cover a couple of the more useful ones. Just take a quick look at an example declaration of the Enum struct:

I’m sure most readers can imagine how these methods are useful and how to implement them.

However looking up a specific enumeration by name (useful for macros) or by template type is something that is a little harder to implement. Please see SEL for a working reference on how to accomplish these. The idea is to use the multiple-inclusion trick on the data file to define some template specializations.

Serialization and Introspection Registration

Serializing enumerations should be really straightforward for both binary and string formats. For binary the numerical representations can be utilized. And string format uses the string arrays constructed at compile-time.

The rest is just a matter of writing some string to/from file routines.

Some introspection techniques rely on the user to register various types within the reflection system. In this case it turns out this registration can also be automated with multiple-file inclusion on the data file! Just define a routine to register each enumeration type. There’s not much to it!

Conclusion

I certainly hope this helps someone out there! Please do comment or ask questions right here on the post, I always enjoy reading them.

Component Based Design – Lua Components and Coroutines

Welcome to the second post in a series of blog posts about how to implement a custom game engine in C++. As reference I’ll be using my own open source game engine SEL. Please refer to its source code for implementation details not covered in this article.


I would like to start this post off with a big thank you to Trent Reed for providing great advice in implementing various aspects of Lua integration for a game engine based upon component based design.

If you’re unfamiliar with component based design in general I advise doing a little research before reading the rest.

Since Lua is such an awesome scripting language it would be great if we could give every game object a component whose sole purpose is just to hold some code. This code could be a type of AI brain, or a little bit of game logic.

I always bring up this one particular back and forth patrol AI as a great example. Imagine you could do this in C++:

When this component is updated the code within a script is substituted for C++ code. Imagine if you could write AI code like so:

This enemy patrols left, right and then throws a bomb. This type of code is actually realistic with a simple feature of Lua’s called Coroutines. I am sadly unable to find my original reference for creating a nice C++ Coroutine wrapper, but I do have a nice wrapper within SEL you can look at. UPDATE: Game Programming Gems 5 has the exact article I used when building my own Coroutine implementation. I believe the section is called “Building Lua into Games”.

The entire purpose of a Coroutine is to allow Lua to pause the state of a function call and resume it exactly where it left off from at a later point in time. This lets you write code that can take pauses and resume later, allowing for extremely readable and easy to create game logic.

Creating and using Coroutines is pretty simple and there exist a lot of references on the internet of how to do so. If you like you can view my own implementation within my SEL game engine.

However there does come a time when one actually thinks about how to store these scripts as components in a simple way. As recommended in one of my other posts, your GameObject should look something like this in an engine utilizing Component Based Design:

There rises an issue of storing components whose only difference is a string representing the script name; what if we want to hold any number of these? One simple idea is to create a single LuaComponent type in C++ of which is stored in a slightly different manner; a separate vector of LuaComponents can be utilized to separate the game logic components from the rest of the core engine components.

This allows LuaComponents to accessed via string lookup:

Start Update and Finish

It would be really nice if each component’s script name just referred to a sinle Lua file. If this were true then a naming convention can be established: a Lua component might only be a .lua file that contains functions Start, Update and Finish.

This sounds nice but a method for calling these various functions must be concocted. One simple can’t place all LuaComponent function defintions for Start, Update and Finish into the global Lua environment.

The idea is to create a unique Lua table for each GameObject that contains a LuaComponent. Within this table an isolated Lua environment can be constructed to define the 3 base functions. This also adds the benefit that all global variables within a LuaComponent file are local to each individual LuaComponent instance. This is especially important when you have lots of LuaComponents of a single script type. You don’t want globals in the LuaComponent file to be shared between all instances.

Implementing this is pretty easy if your game objects already have unique identifiers (preferable integers). I’ll take a slight detour on unique ids for a moment.

Unique Object IDs

The simplest way to implement unique IDs for your game objects is to keep track of a single integer. This integer starts at 0, and each time a new object is created the integer is incremented after assigning the object’s ID as the value of the integer.

This works so long as your integer overflow is very high. Luckily 32 bits of precision is more than enough for any game.

This can be taken farther with handles as detailed in one of my other posts.

Implementing Script Environments

Given a unique id for a game object a table in Lua can be constructed especially for this object:

The idea here is to create a new table instance for a game object if no table already exists. Then a new environment is created within this table (Environments in Lua are just tables).

The next step is to somehow get our .lua file definitions into this environment. In Lua 5.1 (and some lesser versions) there is a nice setfenv function which sets the environment of a Lua function. This is perfect for our cause as files loaded from .lua files are made into chunks, which are just nameless function objects! All that needs be done is to load the script and set it’s environment to the fresh new environment given to our object instance, and run the loaded chunk.

In Lua 5.2 and beyond there’s no nice setfenv function. Instead we must change the first upvalue of the chunk, which is the environment of the chunk. There are a couple ways to do this and I ended up choosing the easiest to implement. Here is my finished loader in Lua:

I decided to make use of the debug library. This allows me to inject a chunk’s definitions into an environment without fetching data from file. First implementations are likely to make use of lua’s loadfile function, as it actually does have a parameter to specify an environment. However loading from file is really slow, so ideally one would just keep a reference to the loaded chunk and run it on different environments as needed.

Coroutines, or Not?

I myself haven’t experienced this, but around the internet and through word of mouth I’ve heard that coroutines aren’t as fast as we’d all like them to be. This is too bad, but can be dealt with. One way is with recycling of coroutines. I will likely mess with this myself later (when I need to), but I haven’t yet found it necessary.

Instead my LauComponents in SEL contain a boolean to determine if the component will be run as a coroutine or normal Lua function call. A normal Lua function cannot have fancy WaitSeconds or WaitFrames calls, but it is still Lua. This way developers can have control over the amount of overhead a given LuaComponent actually  imposes.

Lua File System

Since I wrote about loading Lua chunks and holding them for later use, it would be helpful to know how to load all files from a folder in Lua. This lets you drop a .lua file into a specified folder and suddenly your engine has access to a new LuaComponent type. This can be coupled with asset hot-loading! There’s a great article by Noel Llopis on asset hot-loading in Game Programming Gems 6.

I highly recommend using Lua File System (LFS). LFS is extremely small and has the same license as Lua itself. This is great in case you need to modify the source. It’s also extremely useful.

I recommend compiling LFS into Lua itself, whether or not you’re making a dynamic library or static library. I had good results doing this  myself.

Here’s an example of some of my code used to load all scripts within a folder (traverse all sub-folders recursively):

There’s great support for querying file extensions, names, paths and differentiating between files and folders.

I actually use LFS as my standard file directory traversal tool in general, not just for LuaComponents.

Adieu

Hopefully this article provides some insight into creating dynamic game logic components with Lua! If I wrote this correctly someone out there is excited to try Coroutines with Component Based Architecture.