Category Archives: Engine

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),

Automated Lua Binding

Capture

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

Capture

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++ Reflection Part 6: Lua Binding

Binding C/C++ functions to Lua is a tedious, error prone and time consuming task when done by hand. A custom C++ introspection system can aide in the automation of binding any callable C or C++ function or method a breeze. Once such a functor-like object exists the act of binding a function to Lua can look like this, as seen in a CPP file:

The advantage of such a scheme is that only a single CPP file would need to be modified in order to expose new functionality to Lua, allowing for efficient pipe-lining of development cycles.

Another advantage of this powerful functor is that communication and game logic can be quickly be created in a script, loaded from a text file, or even setup through a visual editor. Here is a quick example of what might be possible with a good scripting language:

In the above example a simple enemy is supposed to follow some target object. If the target is close enough then the enemy damages it. If the target dies, the enemy flashes a bright color and then acquires a new target.

The key here is the message subscription within the initialization routine. During run-time objects can subscribe to know about messages emitted by any other object!

So by now hopefully one would have seen enough explanation of function binding to understand how powerful it is. I’ve written some slides on the topic available in PDF format here (do note that these slides were originally made for a lecture at my university):

Download (PDF, Unknown)

Templates and Metaprogramming

Recently I’ve begun to take over a club called Game Engine Architecture Club at DigiPen. The founder of the club graduated and asked me to try running it. I’ve found it be to a lot of fun! The first lecture I did was on template metaprogramming in C++ (TMP).

The lecture was recorded live and is currently up on DigiPen’s youtube channel for public viewing. Though the slides are visible during the video, I don’t think I can share the slides themselves publicly.

Hope you enjoy the video!

Component Based Engine Design

What is Component Based Design?

Component based engine design was originally pioneered in order to avoid annoying class hierarchies that inheritance introduces. The idea is to package all functionality of game objects into separate objects. A single game object is just a collection of the components, as so the components of a game object define it’s behavior, appearance and functionality. This is perfectly fine, though there are plenty of resources out that talk about this topic. However I’d like to take a step back and start from the top.

It should be noted that the implementation presented here is just one way of going about things, and comes directly from my highly subjective opinion. Perhaps you as a reader can come up with or know of better solutions or designs.

Here is an example game object, note that the game object is generic and simply contains some components:


The Actual Engine

The engine of a game can be thought of as a manager of systems. As to what a system is, we’ll get to that later, for now think of a system as either Physics, Graphics or AI. The engine ought to have a main loop function, as well as an update function. The update function calls update on all contained systems in a specific order. The main loop function is just a small infinite loop that calls update.

Often times the main loop will deal with timestepping itself. Have a look at the linked article to learn more about proper timestepping.

It is important to have your engine expose the update function, as sometimes your engine will need to be compiled as a static library and linked to externally. In this case the main loop of your simulation may reside outside of the engine library altogether. A common usage I’ve seen for this sort of design choice is when creating an editor of some sort, perhaps a level or content editor. Often times these editors will have a veiwport to preview the game, and in order to do so access to some sort of engine update function is necessary.

Beyond containing and calling update, the Engine also forwards global messages to all the systems. More on messaging later.


Singletons?

Creating more than one instance of an engine should never happen. The question of “should I make this a singleton” will sometimes arise. In my experience the answer is often no. Unless you’re working on a large team of programmers where the chances of some moron making an instance of some Engine or System class, making things a singleton is just a waste of time. Especially if retrieving data from that singleton incurs a little bit of overhead.


Systems

Each system in the engine corresponds to one type of functionality. This idea is best shown by example, so here are the various systems I usually have in engines I work on:

  • Graphics
  • Physics
  • GameLogic
  • Windowing/Input
  • UI
  • Audio
  • ObjectFactory – Creates objects and components from string or integral ID

Each system’s primary functionality is to operate upon game objects. You can think of a system as a transform function: data is input, modified somehow, and then data is output. The data passed to each system should be a list of game objects (or of components). However a system only updates components on game objects, and the components to be updated are the ones related to that system. For example the graphics system would only update sprite or graphics related components.

Here’s an example header file for a system:

The naive approach to a system update would be to pass a list of game objects like so:

The above code is assuming the ObjectFactory contains all game objects, and can be accessed somehow (perhaps by pointer). This code will work, and it’s exactly what I started with when I wrote my first engine. However you’ll soon realize the folly involved here.


Cache is King

That’s right, those who have the gold makes the rules; the golden rule. In a more serious sense, cache is king due to processing speed related to memory access speed. The bottleneck in all engines I have ever seen or touched in the past couple years has been due to poor memory access patterns. Not a single serious bottleneck was due computation.

Currently modern hardware performs very very fast. Reaching for data in memory (RAM, not just hard disk) is orders of magnitude slower. So caches come the rescue. A cache can be thought of, in a simplified sense, as a small chunk of memory right next to the CPU (or GPU). Accessing the cache memory is way faster than going all the way out to main RAM. Whenever memory is fetched from RAM memory around that RAM location is also placed into the CPU cache. The idea here is that when you retrieve something from RAM the likelyhood of requiring to fetch something very nearby is high, so all the data in that area is grabbed all at once.

Long story short, if you place things that need to be accessed at around the same time next to each other in memory, huge performance benefits will be reaped. The best performance comes from traversing memory linearly, as if iterating over an array. This means that if we can stick things into arrays and traverse these arrays linearly, there will be no faster form of memory access.

Fetching memory that does not exist in the cache is called a cache miss.


Cache and Components

Lets revisit the naive approach to updating systems. Assuming a system is handed a generic game object, that system must then retrieve its corresponding component(s) to update, like so:

As this loop is run the memory of every game object and every component type that corresponds to the system is touched. A cache miss will likely be incurred over and over as the loop runs bouncing around in memory. This is even worse if the ObjectFactory is just creating random objects with new, as every memory access to every object and every component will likely incur cache misses.

What do? The solution to all these memory access problems is to simplify the data into arrays.


Arrays GameObjects + Components

I suggest having every game object exist within a single giant array. This array should probably be contained within the ObjectFactory. Usage of std::vector for such a task is recommended. This keeps game objects together in memory, and even though deletion of a game object is of O(n) complexity, that O(n) operation traverses an array, and usually will turn out to be unnoticeable. A custom vector or array class can be created that avoids the O(n) operation entirely by taking the element at the end, and placing it into the deleted slot. This can only be done if references into the array are translated handles (more on handles momentarily).

Every component type should be in a giant array too. Each component array should be stored within their respective systems (but can be “created” from the Factory). Again, an array like data structure would be ideal.

This simple setup allows for linear traversal of most memory in the entire engine, so long as the update function of each system is redesigned slightly. Instead of handing a list of game objects to each system, the system can just iterate over its related components directly, since the components are stored within the systems already.


So, how are Game Objects “handled” now?

Since components have been moved into large arrays, and the game objects themselves are in a big array, what exactly should the relationship between a game object and a component be? In the naive implementation some sort of map would have worked perfectly fine, as the memory location of each component could be anywhere due to the use of new calls. However the relation isn’t so carefree.

Since things are stored in arrays its time to switch from pointer-centric relationships to handle based relationships. A handle can be thought of in its simplest form an index into an array. Since game objects and components are stored in arrays, it is only natural that to access a game object you do so by index. This allows for these giant arrays to grow and shrink as necessary without obliterating dangling pointers in the rest of the program.

Here’s a code example:

As you can see, an array of handles is stored to represent the containment of components. There is one slot in the array for each type of component. By design this limits each component to be of unique type within a game object. Each handle is an index into a large array of components. This index is used to retrieve components that correspond to a game object. A special value (perhaps -1, or by some other mechanism) can be used to denote “no component”.

Handles can get quite a bit more versatile than just a plain ol’ integer. I myself created a HandleManager for translating an integer into a pointer. Here’s a great resource for creating your own handle manager.

The idea of translating a handle into a pointer is such that once the pointer is used it is not kept around. Just let it be reclaimed back into the stack. This makes it so that every time a pointer is required there is a translation of handle to a single pointer somewhere in memory. This constant translation allows for the actual pointer value to be translated to, to be swapped for another pointer at any time without fear of leaving dangling pointers.


Where does the Code go?

Code for update routines can be put into either systems or components. The choice is yours entirely. A more data oriented approach would put as much code into systems as possible, and just use components as buckets of data. I myself prefer this approach. However once you hit game logic components virtual functionality is likely to be desired, and so code will likely be attached directly to such components.

The last engine I built used the naive approach to component based design, and it worked wonderfully. I used a block allocator so cache misses weren’t as high as with raw new calls.

The point is, do what makes most sense and keep things simple. If you want to store routines within your components and use virtual function calls, then you’ll probably have trouble storing things in an array unless you place all memory in the base class. If you can externalize as much code from your components as possible, it may be simpler to keep all your components in an array.

There is a tradeoff between flexibility and efficiency. My personal preference is to store performance sensitive components in huge arrays, and keep AI and game logic related things together in memory as much as possible, but not really stress too much about it. Game logic and AI should probably just be rather flexible, and so details about memory locations aren’t so important. One might just allocate these types of components with a block allocator and call it good.


Messaging

The last major devil in an engine is messaging. Messaging is transferring data from one location to another. In this sense the most basic form of messaging is a simple function call.

Taking this a step further, we’d like to be able to send messages over a connection in a generic manner. It should not matter what type of message we send; all messages should be sent the same way to reduce code duplication and complexity. The most basic form of this is dynamic dispatch, or virtual function calls. An ID is introduced to the message so the internal data can be typecasted to the correct type.

Still, we can do better. Lets imagine we have a sort of GameLogic component or system. We need a way to send a message to this object that contains some data. Lets not focus much on memory access patterns, as simplicity and flexibility are key here. Take a look at this code:

This code highlights the usage of messaging quite well. Say the player emits some messages as it walks around, perhaps something like “I’m here” to all nearby things in a level. The player can blindly send these messages across the SendMessage function without caring about whether or not it will respond or do anything. As you can see, the implementation of the SendMessage function ignores most message types and responds to a few.

In this example when the player nears the treasure chest it will glimmer a bit. Perhaps when the player gets closer it glimmers brighter and brighter. In order to do so, the MSG object sent to the treasure chest ought to contain the player coordinates, and so it can be typecasted to the appropriate message type.

The eActivate message may be emitted by the player whenever they hit the “e” button. Anything that could possibly respond to an eActive message will do so, and the rest of the objects receiving the message will safely ignore it.

This type of messaging is simple and easy to implement, quite efficient (if a block allocator or stack memory is used for the messages), and rather powerful.

A more advanced version of messaging makes heavy use of C++ introspection. A future article will likely be devoted to this topic, as it’s a hefty topic altogether. Edit: Here’s a link to a slideshow I presented at my university.


Conclusion and Resources

This was a rather whirlwind tour through a lot of different information -I hope it all came out coherent. Please don’t hesitate to ask any questions or add comments; I may even just update this post with more information or clarifications!

Resources:

Custom Physics Engine – Part 1: Impulse Resolution

EDIT:

This series ended up on Tuts+, and these are sort of deprecated. Please visit Tuts+ to see the finalized articles.

Personal Update

Beyond C++ reflection I’ve taken a huge liking to physics programming for games. Reflection in C++ is a largely “solved” area of study. Though resources on the internet may be few and far between for creating custom introspection, people that know how to create such systems have explored much of what is to be accomplished.

However physics is another story entirely. Up until just a few years ago physics for games was in a highly primitive state; techniques just hadn’t been created due to the inability of hardware to perform necessary computation. There are a lot of new and exciting problems to solve.

So this next year while attending DigiPen I’ll be focusing my studies around: engine architecture, data oriented design and optimization, C++ introspection and game physics. This last topic being the topic I’m going to start an article series on.

Game Physics High Level Detail

A game physics engine performs some functionality for ensuring that shapes behave in a particular way. To state this one could say: a physics engine removes degrees of freedom from moving bodies, and enforces these imposed rules.

From here on out, until specified otherwise I’ll be talking specifically about convex rigid bodies within a physics engine. A rigid body is just a shape that is implicitly rigid; the engine does not naturally support deformation of a set of points that make up a shape. Using this implicit definition the mathematics behind manipulating such shapes can be known intuitively and implemented efficiently.

Here’s a short feature list of some features a custom physics system may provide, assuming the engine uses rigid bodies:

  • Collision detection
  • Collision resolution
  • Linear movement, angular rotation and integration
  • Raycasting
  • Islanding/sleeping/portals
  • Friction simulation
  • Spatial partitioning/bounding volumes
  • Fracturing/splitting
  • Multi-part bodies
  • Various types of shapes
  • Advanced mathematical constraints (joints, motors, contact constraints, etc.)
Raycasting from Box2D.Raycasting from Box2D.

In this article series I will attempt to talk about all of the above topics in my own time. I’ve learned a lot about physics and physics engines in a short amount of time and by documenting what I have learned I hope to solidify my understanding, as well as help out others to achieve what I have. I would not have learned nearly as much as I currently know without help from others so it is only natural to want to do the same.

The best example of an open source physics engine that employs much of the feature list shown above would be Box2D by Erin Catto. The rest of this article series will be detailing the physics engine that I myself have written. There are of course other methods I choose not to talk about, or just don’t know about.

Architecture

There are two main objects that make up a physics engine: shapes and bodies. A body is a small package of data that defines intrinsic properties of a physics object. Properties such as density, restitution (elasticity), friction coefficients, inertia tensors, along with any other flags or settings should be stored within the body. These bits of data are properties that can be isolated away from the shape definition. The shape itself is contained with the body through a pointer.

The shape definition defines what sort of shape a physics object represents. Some physics engines can attach multiple shapes to a body, which are referred to as fixtures. A shape stores any data required to define the shape itself, and provides various functions to operate on the shape, such as testing for line or point intersection, or generating a bounding volume.

Together the body and shape represent a physics object, which by the end of this article series will be able to perform a lot of interesting interactions with other physics objects.

A tower of stacked oriented boxes within a custom physics engine.

A tower of stacked oriented boxes within a custom physics engine called iiD.

All bodies should be contained within what is known as a scene or world. I refer to this object as a scene. The scene should contain a list of all live objects, as well as functionality inserting or removing bodies from the scene. The scene should also have callbacks for processing shape or ray queries. A query just checks to see if any bodies intersect with something like a point or ray.

The scene has one particular function called step, which steps the scene forward in time by a single delta time (dt). This step function steps all objects forward in time by integration. The integration step just moves the objects forward by using their velocity, position and acceleration to determine their next position.

During the step collisions are detected and then resolved. Often times a broadphase of some sort is used to detect possible collisions, and expensive collisions operations are only used when really needed.

All of this organization allows the user of your physics engine to worry about three main operations: creating and removing bodies, and stepping the scene. The rest is automated and taken care of within the physic system’s internals.

The last major isolated system would be the broadphase. There are two major phases in collision detection: the broad and narrow phases. The narrow phase is the one which determines if two shapes intersect or not. The broad phase determines if two shapes can possibly be intersecting or not. The broadphase should be constructed such that intersection queries are very very fast and simple. An axis-aligned bounding box (AABB) will suffice perfectly.

Once the broadphase chooses which objects could perhaps be colliding, it sends them off to the narrow phase. The narrow phase performs much more intensive operations to determine if two objects are colliding or not. The whole point of this is to reduce the amount of times the narrow phase has to be used, as it is expensive to operate with.

Once the narrow phase finds a pair of bodies to be colliding information about the collision is gathered and placed into a small container called the manifold. Do not ask why it is called a manifold, for I have no idea and neither does anyone else seem to! The manifold contains three important pieces of information:

  • Collision penetration depth
  • Direction to resolve in
  • Points of contact

These pieces of information are used to fill in formulas that are used to resolve the penetration and solve for a single unknown: the magnitude of the resolution vector. Here’s a small diagram:

 

c - Collision contact n - Resolution normal d - Penetration distance

c – Collision contact
n – Resolution normal
d – Penetration distance

It is also useful to to store pointers or handles to the two objects that formed this collision info. This allows some useful functions to placed into the manifold object directly: solve and resolve. Solve would be the function to collect the three pieces of collision information. If no contact points are found, then there is no collision. If contact points are found, then resolving performs a resolution operation to force both objects to not be intersecting after integration.

Velocity

Complex physics manipulation is performed on the velocities of objects. Trying to manipulate the positions of objects directly is very difficult, as it poses a problem that isn’t linear. By using derived position equations for velocity, the problem is thus simplified. Most of the time we will be only dealing with velocity manipulation.

Impulse Resolution in 2D (No Rotation or Friction)

The act of resolving collisions is something that isn’t covered very well on the internet. There are some scattered documents and details, though the information isn’t always easy to find. Most of what I know I learned by talking with other people, but I know most people will not have such an opportunity. Hopefully this article series can provide a strong resource for understanding and constructing a simple physics engine.

The toughest place to code is in my opinion resolution of collision. There exists tons of information on collision detection and broadphase, and thus creating these portions of a physics engine is in my opinion not too difficult. Some resources for collision detection are: Real-Time Collision Detection by Christer Ericson, and Game Physics Engine Developement by Ian Millington. I have both of these books right next to me as I write this :)

Generating contact manifolds and resolving such manifolds are what most programmers get caught up in. So lets hit the ground running and tackle a portion of code that will bring your entire physics system to life: contact resolution.

The best type of contact resolution to start with is impulse resolution. The idea behind impulse resolution is to take your contact manifold and solve for a single velocity vector that can be used to add into an object’s current velocity, in order to make it not penetrating the other object during the next frame. The reason for starting with impulse resolution is that it’s quite simple and easy to get up and running, and more complicated and advanced techniques require you to understand impulse resolution anyway.

2D impulse simulation of AABBs without rotation.

2D impulse simulation.

Now the contact manifold is assumed to contain the direction of our velocity vector we are solving for. I will cover how to generate the contact manifold in another article in this series. The only unknown left to solve for is the magnitude of this vector. It so happens that it’s possible to solve for this magnitude in relation to both objects. If this magnitude is known, you add velocity along the normal scaled by the magnitude for one object, and you do the same operation to the other object in the direction opposite to the manifold normal. Lets start from the top.

We have two objects moving along in our scene, and there exists a relative velocity between the two, with object A as the reference object at the origin:

The relative velocity can be expressed in terms of the collision normal (from the collision manifold) with a dot product:

This can be thought of as the relative normal velocity between the two objects. The next thing to include in this derivation is the coefficient of restitution (elasticity factor). Newton’s Law of Restitution states that:

Often times the restitution identifier is specified by an e, or epsilon symbol. Knowing this it’s fairly simple to include it within our current equation:

Now we need to go to another topic and model an impulse. I have said the term “impulse” quite a few times without defining it, so here is the definition I use: an impulse is an instantaneous change in velocity. We will use an impulse to change the velocity of an object. Here’s how you could use an impulse to modify the velocity of a single object:

Here Impulse would be a scalar floating point value. This isn’t too useful however, as it only scales an object’s current velocity, and thusly makes the object move slower or faster along the positive or negative direction of the vector.

What is needed is a way to do component-wise modification of the vector, so we can make it point slightly in one direction or another, allowing objects to make turns and change directions.

In the above equation we can take a direction vector with a magnitude of 1, and scale it by our impulse. By adding this new vector to our velocity we can then modify the velocity in any way we wish. Our end goal is to solve for our Impulse scalar that will separate two objects from collision, so in the end we’ll need to distribute this scalar across two equations in terms of velocity.

Lets start with a simple momentum equation:

An impulse is defined to be a change in momentum. Thus we get:

To isolate our velocity after we can rearrange into:

Now lets change equation 4 into one that contains velocities under the influence of impulses. However we’ll want to express our VelocityNew as one that is acted upon by impulse, and substitute in equation 9:

Remember that the impulse is a scalar. Also note that all values on the right hand side of the equation are all known, including the Direction which was solved for by the collision detection.

All that is left here is to distribute this scalar impulse over each object’s velocity vector proportional to the total mass of the system (system being collision between both objects).

The total mass is MassA + MassB, so to get an even distribution you do: impulse * Mass / TotalMass. To simplify this one could use the following:

This can be done twice, once per object. The total impulse will be applied, except only a portion of the impulse will be applied to each object. This ensures smaller objects move more than larger ones during impact.

One thing you must ensure is that if the velocities are separating (objects moving away from one another) that you do nothing. Here’s a sample version of finalized code for impulse resolution in 2D without rotation or friction:

Rotation

Now that we have covered resolution without these two factors adding them in to our final equation (equation 10) will be quite a bit simpler. We will need to understand the concept of “mass” in terms of rotations. The inertia tensor of an object describes how “hard it is to turn” along some axis. In 2D there’s only a single axis of rotation (along the z) so a single tensor is all that’s needed. Here’s a new version of equation 11.

For the sake of brevity here’s the final equation, where r is the vector from center of mass to a point on the body (contact point). The velocity of a point on the body relative to it’s center is given by:

Final equation (Direction substituted for n):

And there we have it! This will solve for a separating impulse given a specific contact point. Now you might have noticed there are a couple cross products that are kinda strange in 2D. I won’t cover what they are here, but they still hold true. I’ll just give them to you:

Friction

Friction is the simplest thing to do in this entire resolution article, assuming we’re dealing with 2D! I actually haven’t derived this portion myself, so again I’m going to just throw the equations at you. Assuming we have our resolution direction in the manifold (the collision normal), we can calculate a tangent vector, which is a vector perpendicular to the collision normal. Just replace all instances of n in equation 14 with this tangent vector.

To solve for the tangent vector you do:

Again, just take the above TangentVector and replace it in equation 14 for n.

There is something I have missed. When solving for the force of friction there’s a max, which is the manifold normal * the coefficient of friction (from the body definition). This is due to the Coloumb friction law. Treat the coefficient of friction * normal as your “friction cap” when solving for your tangential impulse. This is just a simple capping of the final impulse vector.

Penetration Resolution

Due to floating point error energy will always be lost from the system over time. As such, when objects start coming to a rest they will sink into each other due to gravity. How to solve? Well the solution is to actually just handle the leftover penetration manually by just moving the objects apart directly. This will prevent objects from sinking into one another, though doesn’t add any energy into the system.

To resolve penetration, simply move each object along the manifold normal in opposite directions. However there’s an art to doing so; you need to be gentle. If you just resolve 100% of the penetration each frame objects underneath other objects will jitter violently due to the naive penetration resolution scheme I am presenting. To avoid this, try only resolving a percentage of the leftover penetration, perhaps 20 to 80%.

Additionally you only want to resolve penetration if the penetration depth after the impulse is applied is above some constant arbitrary (but small) threshold, (try 0.01 to 0.1). If the penetration is below this, then don’t move either object.

This method of penetration resolution is called linear projection. Here’s a snippet of C++ code demonstrating this:

Iterative Solving

There is one one additional tweak you can do to increase the believability of your physics simulation: iterate over all contacts and solve + resolve the impulses many times (perhaps 5 to 20 iterations). Since the large equation 14 has relative velocity within it, each iteration will feed in the previous result to come up with a new one.

BillardBalls

This will allow the step to propagate energy throughout multiple objects contacting one another within a single timestep. This is essential for allowing the “billiards balls” effect to ensue.

This simple iteration is a very easy way to vastly improve the results of resolution.

Resources/Links

  • http://chrishecker.com/images/e/e7/Gdmphys3.pdf
  • http://www.cs.cmu.edu/~baraff/sigcourse/notesd2.pdf

Windows Console Game: AsciiEngine

I’ve been creating a series of posts about creating a Window’s console game from scratch in C. This post will act as a culmination of many different posts throughout my blog in the form of an open source game engine called AsciiEngine.

AsciiEngine is a game engine for Windows XP, Vista, and Win7 that allows the user to easily create and display images within a Windows console. The engine also automates the tedious task of customizing aspects of the console, such as a font or palette color.


Here’s the link for AsciiEngine (visual studio 2010 project + source files): LINK



Man with sword!

Screenshot from older included demo~~

By using AsciiEngine, users can easily construct interactive programs (games!) without the overhead of setting up all of the various system components required to run a game within the Windows console.

Screenshot of the old AsciiEngine demo. Pressing enter pastes
sun images onto random locations.

AsciiEngine is documented heavily in-code and is open source – I want anyone willing to be able to learn from the example code provided.

Features include:

  • Complete game loop
    • Game loop integrated into Game State Manager via function pointers
  • Game State Manager
    • Allows for easy management/creation/deletion of game states
  • Functioning framerate controller
    • Allows the setting of framerate with a #define macro
    • Prevents large timesteps from passing through the program with a cap
  • Various console related functions for easy customization of the console window
  • Complete graphics functions set for drawing 2D images
  • Input template complete for simple keystroke detection and mouse event handling
  • Complete and very simple PRNG
  • Simple image format that allows for variable size
  • Integrated hash table for storing images
    • Allows for an optimized lookup, e.g.: TableLookup( “ImageName” )
    • Extremely simple creation/deletion of images
  • Implementation of my simple 2D collision library
  • Implementation of my simple 2D vector library
  • Highly organised object manager using the factory pattern
    • Allows for easy creation/handling/deletion of game objects
    • Incredibly simple to create new object types
  • Implemented my Tile mapping — Binary Collision library
  • Image editor
  • file output
  • Automatic image file loading and parsing
  • Messaging system Object to object + global messaging system
  • Component base game object system (now renamed to game entity)
  • New button class for easy UI creation
  • Integration of generic Hash Table and Linked Lists
  • Simple serialization and deserialization support.

Here’s the link for AsciiEngine (visual studio 2010 project + source files): LINK

Now hopefully I can see some console games created with true Ascii art! Please let me know if anyone creates a console game, or uses AsciiEngine to create a console game. I would be thrilled to see some projects from other people, as I just love Ascii art games, especially ones within the Windows console.

Series on creating a Windows Console game:

How to use AsciiEngine:
Using AsciiEngine is very easy. It’s available here on github.

Almost all code creation you’ll do with AsciiEngine will be in creating/modifying game state files. Since AsciiEngine uses a GameStateManager (GSM) you’ll have to create your own states. More information about what a GSM can be found here. Creating a state is as easy as copy/paste from the example state within the download archive of AsciiEngine. Integrating a new state into the GSM should be straightforward if you examine the currently existing code.

Once a state is created all that is left to do for the user is to simply write code within the state! Almost all code written will be within the Update function. During the Update function all game logic will occur. Drawing specific functions should occur only with the stat’s Draw function – this allows for easy implementation of the Painter’s Algorithm.


To switch states there are three global variables within the GameStateManager.c file. These are nextState, currentState and previousState. In order to switch states simply change nextState to the desired state to switch to. The main loop will then call the Unload and Free function automatically of the current state you are in, and then load and initialize the next state automatically as well.

Creation of Game Objects can be handled any way by the user, I’ve written documentation on a very simple way of creating and handling Game Objects here, and it works extremely well with the GSM organization throughout AsciiEngine. I’ve implemented my own method of handling objects with the Factory pattern! Using the ObjectFactory within AsciiEngine it’s very easy to handle game objects, as well as create new ones. See code for documentation — it should mostly be copy/paste to create a new object. UPDATE: Game objects are now called Game Entities. As such, all game entities are now component based! Please see the source on github for details. A post in the future about component-based architecture will likely be written.


Creating Images:
Creating images in Ascii art will require a good tool for more complicated images. Here‘s an interesting thread on a few different programs for such. Perhaps it might be a good idea to create your own tool in the Windows console with AsciiEngine! Here’s some additional documentation to pursue the idea of creating your own drawing tool: link.

Updating AsciiEngine
I’m completely open to most all suggestions on AsciiEngine. I’ve never written anything open-source before, so there may be good insight that’d help the project out! Feel free to contact me about questions on how to use AsciiEngine, or for feature requests, or just to talk/show off thing you’ve made :)

Basic 2D Vector Physics: Acceleration, Orientation and Friction

This post aims at covering the basics of 2D vector physics, that of which can be used in application to create something like this Asteroids project for my CS230 class.

The simplest way I know of to move an image across the screen over time is by using a static velocity and apply it to the the position of an image every time-step:

pos += vel * dt;

dt should be calculated every frame loop and passed to this equation, this way your displacement will be time-based instead of frame-based. To calculate dt you can use the following flowchart:



In order to have variable velocity you can apply the same idea from our displacement (position) equation. To change velocity over time and have acceleration and deceleration you can use:

vel += accel * dt;

Pretty simple! However in order to apply this in programming you’ll break up the x and y velocities into separate values like so:

pos.x += vel.x * dt;
pos.yx += vel.y * dt;
vel.x += accel.x * dt;
vel.y += accel.y * dt;

Now what about turning, and a sense of orientation? It’s no use if your object can only go in a single line, which is all the above equations will support if implemented alone. Your object should have a data member to hold it’s orientation in radians. If you don’t really have a mental grasp of radians, that’s fine. Take a look at the unit circle: link. In order to know the value of any given 2D direction relative to a standard axis (x and y plane not rotated or anything) just look on the graph in that direction. For example straight upward in radians is pi / 2. Straight downwards is 3 * pi / 2. Very simple. The unit circle is just a way of representing directions as a value. The range of this value is 0 through 2 * pi.

You can initialize your object’s direction value with a preset or randomized value within the range of zero through 2 * pi. However it’s easier to implement calculations in 2D if you set your range of values to pi to -pi (see below psuedo code for reason why). This means, for example, a full 360 degree angle is represented by either zero or -pi. The downward direction, for example, would be -pi / 2. Once you have this set up, you can easily use this radians orientation value to find a direction vector for your object. A direction vector is a vector whose length is 1, which allows you as a programmer to multiply it by a value and easily get a vector in a specific direction of a specific length.

For example say your object has an x velocity of 6 and  y velocity of 10. Every timestep you’ll move by a factor of 6 to the right and up by 10. This is all good, and the distance the ship will cover can be found with the Pythagorean theorem: sqrt( 6^2 + 10^2 ). But, what if you want the ship to move 5 units in a direction per timestep? What if you want to be able to easily move your object around in any direction by 5 units per timestep? This is going to be pretty difficult without doing what’s called normalization. Normalizing a vector is the process of taking a direction vector, like (6, 10) and generating a vector that points in the exact same direction, whose value is equal to 1.

If you are able to find a direction vector of the direction your object is going, you can easily multiply the x and y components by 5, and achieve your goal. If your direction vector is derived from your radians orientation (like I said we’d do), then you can get the direction vector no matter what direction you are going, all the while you can modify your orientation value however you like! In order to get your normalized direction vector from your angle of orientation, just use:

dirVect.x = cos( radianOrientation );
dirVect.y = sin( radianOrientation );

You now know all the necessary ideas needed to implement some simple 2D vector physics! You can rotate your object’s orientation with addition/subtraction on your radians value, and then move your ship according to the angle of orientation by a specific velocity value, all the while updating your velocity with a constant acceleration value.

Here’s a (psuedo) code example:

// Find current direction vector
dirVect.x = cos( radianOrientation );
dirVect.y = sin( radianOrientation );

// Apply forward acceleration
if(keypress( UP ))

  vel.x += ACCELERATION_FORWARD * dirVect.x * dt;
  vel.y += ACCELERATION_FORWARD * dirVect.y * dt;
  // Simulate friction
  vel.x *= .99
  vel.y *= .99


// Apply backward acceleration (negative forward)
if(keypress( DOWN ))
  vel.x += ACCELERATION_BACKWARD * dirVect.x * dt;
  vel.y += ACCELERATION_BACKWARD * dirVect.y * dt;

  // Simulate friction
  vel.x *= .99
  vel.y *= .99


// Add a value scaled by dt to rotate orientation
if(keypress( LEFT ))
  radianOrientation += ROTATION_SPEED * dt;
  // Bound checking for pi and -pi
  if radianOrientation > PI

    radianOrientation = -PI
  else if radianOrientation < -PI
    radianOrientation = PI


// Subtract a value scaled by dt to rotate orientation

if(keypress( RIGHT ))
  radianOrientation -= ROTATION_SPEED * dt;

  // Bound checking for pi and -pi

  if radianOrientation > PI
    radianOrientation = -PI
  else if radianOrientation < -PI
    radianOrientation = PI


// Update position with our new calculated values
pos.x += vel.x * dt
pos.y += vel.y * dt

Another thing to try to explain is the reason for the range of pi to -pi. Using a range of pi to -pi allows for easy calculations because it makes the lower half of the unit circle negative, which means you can directly apply resulting values from sin and cos onto your velocity/displacement, and move your image in all four directions (up, down, left, and right).

Now, what if you need to solve for the angle between two points? This could be useful for homing missiles, or AI. Knowing the angle between an enemy and the player, for instance, could be used to let the enemy know which direction to go from there. In order to solve for the angle between two points I used atan2:

angle = atan2( player.y - enemy.y, player.x - enemy.x )

This lets me find the angle between two points, namely between an enemy object and the player. You can then use this result and compare it with the angle of orientation of the enemy in order to deduce of the enemy should turn clockwise or counterclockwise, or anything else you'd want!

You may have noticed those lines that multiply the velocity by .99 after the update calculation was made. This actually simulates friction. The higher the velocity gets the greater the reduction per timestep! This will allow your object to accelerate slower the faster it goes, until it reaches an equilibrium. It should also seem to float friction-less at slower speeds. You can use a larger or smaller value for different amounts of simulated friction.

And there you have it -all the essential concepts required to implement a game using simple 2D vector physics!