Category Archives: Articles

Component Based Design – Lua Components and Coroutines

logo

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.

Protip: How to be a Physics Dev – Debug Rendering

Spent a lot of time creating Maya-like camera controls with orbiting.

Today I figured out the single most important tip I could ever give anyone in regards to being a competent physics engine developer. I will share this tip right here on my humble blog:

Your skills as a physics developer will grow at a rate proportional to how good your debug draw information is. I’d actually argue that your skills as a physics developer are proportional to how good your debug draw is.

I feel I’m at a decent place in my skills, as I feel my debug draw has become decent. Lets get some screenshots going!

Initial simplex during Quick Hull.

Initial simplex during Quick Hull.

Stack of polyhedron (OBB meshes). The blue and red contacts are warm started (red is warm started consistently over many frames).

Stack of polyhedron (OBB meshes). The blue and red contacts are warm started (red is warm started consistently over many frames).

Spent a lot of time creating Maya-like camera controls with orbiting.

Spent a lot of time creating Maya-like camera controls with orbiting.

I digress. I didn’t figure out this simple fact on my own; I gleaned this wisdom off of my friend Nathan Carlson. He pointed out that the reason a lot of students at DigiPen have trouble with computational geometry and general physics engine development due to a lack of debug rendering.

Just take a look at Dirk Gregorius’s sample demo from his GDC 2013 lecture. He fully renders Gauss maps, a minkoswki difference, and has glorius camera controls. I actually copied his camera design and implemented it myself. You can see that he has Ant Tweakbar integrated as well, for various tweaking tasks. Erin Catto has lots and lots of different tests, asserts, and most important of all tons of debug drawing for his Box2D library. The Zero team on the third floor of DigiPen definitely has the craziest debug draw I’ve ever heard of!

Hopefully I can achieve something at least in the likeness of all these other developers, and I recommend readers do the same; intuition is often best built visually when it comes to geometry.

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

Game Programming Primer

I’ve spent quite a bit of time writing a fairly long article over at a website I frequent TeamLiquid.

Now it’s time to share the article in finished form here for all to see! The article is called Game Programming Primer, and here’s an excerpt from the introduction detailing what the article is all about:

Hello! My name is Randy Gaul, and I am a computer science student. I study at DigiPen Institute of Technology, and am majoring in Real-Time Interactive Simulation (a fancy way of saying game programming). I’d like to share my know-how in the ways of game programming as a profession for anyone interested in learning. I encourage anyone interested in programming or creating games, no matter how little knowledge you have in either topic, to check out this article.

And here’s the finished article:

Download (PDF, Unknown)