DigiPen Game Engine Post Mortem

The summer semester has finally ended and so I wanted to give a rough postmortem of the engine I worked on as well as describe some cool features.

Architecture
First of all, we made the physics engine more component based than anything I had done before. We split the main components up into the following categories: Collider, Rigid Body, Constraint, Controller, Region, Effects and Spaces.

The collider and rigid body were the two main components. The collider contained the collision data as well as a position. The rigid body contained the center of mass and velocity. Each one also contained more data, but that was the main differentiation. The idea behind the separation was to split the functionality in a logical way. If a collider and a rigid body were placed on an object, then it would behave just as one would expect. However, if no rigid body was present then the object would be static and considered to have infinite mass. Unfortunately, despite trying to separate out functionality, there was still a strange dependency that the rigid body had on the collider. Most notably, a rigid body requires a collider and it also has to be initialized after the collider. Overall, I think this is a better structure than one massive physics object, but further experimentation and tweaks are still in order.
One benefit that we have not pursued yet is to have multi-object bodies. Currently, an object can only have one collider. The plan for this next semester is to extend objects to have one body for a set of colliders. This is a very nice component driven method of handling the non-convex object issue. I personally plan to implement this the upcoming fall semester.

The space component basically replaced a normal engine. The engine still exists, but now it does very little. The engine has a list of spaces and does almost no work apart from updating each space. Each space then in turn updates all its objects. This provides a very clean way to separate out rooms or other such physical space separations. This also allows different spaces to operate on different time scales. We had a timespace component that each space would use to figure out its update speed. This meant we could pause physics but still have UI running in a very clean manner. And yes, we enjoyed making lots of naming puns with the space component such as timespace, spacelink, geospace, etc...

The region was a nifty idea we had to make an area that would affect objects in various ways. How it would affect something was based upon what effects were placed on it, such as a drag or a random force. On top of this, effects could be placed on spaces and colliders. Collider effects would only be applied on the object while space effects would be global. This becomes very useful to apply gravity or drag globally to the world. The one thing we plan to change is to actually remove regions all together. A region basically kept a record of what was inside of the collider that defined it and applied the effects, however we can actually just have a collider do this with less work due to some things mentioned in the constraint layout section below.

The constraint component was exactly as one would expect, a constraint. This made adding all constraints much easier and allowed for constraints to actually be objects themselves. Along with constraints, we created a new system component called a connection to replace the transform. A constraint tends to not have a position, but two objects that it is connected to. This allowed the engine and other systems to understand this connection better, as well as deal with serialization cleanly.

The controller is what would be used by logic to control something, however this is not a component we actually implemented this semester.

Broadphase Tracker
One the coolest features we made we dubbed the broadphase tracker. The idea was to make a manager of sorts for the testing of broadphases. The tracker has two sets of broadphases, static and dynamic. The separation is a commonly made one since some structures can be more efficiently created if they are given a chunk of time up front.

One of the most useful features of the tracker was to track the accuracy of multiple broadphases and compare them. We did this by determining how often the broadphase and narrowphase agreed. This allowed us to figure out how useful a broadphase may be in a given scenario. Also, this allowed us to check if any broadphases had an error. If any broadphase reported that there was no collision but the narrowphase said otherwise, then there is an error since there should only be false positives. Therefore, the implementation of a new broadphase would be less frustrating as a basic N-squared could be used as a comparison to make sure no false negatives were ever reported. This was actually useful as we found an error in my old Sweep and Prune code both by it missing a test and by noticing that its accuracy was not the same as an N-squared bounding box test.

Another benefit that was not fully implemented was the timing of each broadphase. The one other thing we still want to add is a analyzer of sorts. the analyzer would load up lots of broadphases and tracker how well they do. Over the course of time it would drop bad ones and then at the end of a run it would provide the top 3. This would make finding the best broadphase for a game much easier.

Constraint System
The constraint system was what I spent most of my time on. My code was also very heavily influenced by Erin Catto's Box2D. One of the best designs in implementing this system was in the use of an Intrusive Linked List (InList) courtesy of Chris Peters (my boss). This allowed really quick insertion and removal of objects. This was also helpful in the overall structure. Unfortunately, it is a bit hard to describe this structure but I will try anyways. One day I'll make a nice picture or maybe even an ascii picture in the comments...

Each collider has an InList of edges. An edge then points to the constraint it is a part as well as the collider it is attached to. Each constraint then has two edges, one for each object. The edge that is in the collider's InList is one of the ones that the collider owns. From this crazy structure, a collider can figure out all of the objects it has a constraint with which allows islanding. Also, a constraint can remove and add itself to objects in constant time.

One other thing I did for future console extension was to remove as many virtual calls as I could. This was done by putting each constraint into a separate InList on the solver. The main disadvantage to this is the maintenance, but I spent some time to reduce this with macros. The idea was to make the solver define a macro then use it. The thing is that the macro was used in a header that just had all of the name of the constraints. This header would then be included so that some functionality could be done for all types of constraints. This was used for creating add and remove functions, iteration solving and more. If any macro did a large amount of work, a template function was made which did all the real work, such as solving constraints. This also meant that when updating, some of the templates could be specialized if a constraint, such as a contact, needed special behavior. Because of this the work to add new constraints is greatly reduced.
The problem is, due to islanding, constraints have to be added to the solver each frame and I have to figure out which InList to add it to. Because of this a virtual add call is used. This means each constraint still has a virtual call, but it is only once per frame instead of for every call during iteration. To further help this issue, contact constraints were separated and put in its own edge InList. Contacts are the most plentiful constraint, therefore separating it should take care of more than half of all constraints. This also means that it can be easier to check contact only relationships between objects such as the region effects mentioned above.

Materials
We decided to create a material system to define what each collider is made of. The system is rather simple, but it makes life for designers much easier. The material includes friction, restitution and density. We might add more terms later, but this is what seemed useful now. Because of this we can define soft objects or bouncy objects which is what a designer would really want to add. The one main problem is that we can have bouncy heavy or bouncy light, so defining all different types could be painful. To make matters worse, the bouncy heavy could be expanded to be slippery or rough due to friction. Because of this, we decided to only define a few materials and let it be configurable for the user. We thought of maybe using names like stone, but we wanted to avoid names that implied textures since they are completely different systems.

Recap
We did a lot of cool things in this project, most notably is the broadphase tracker. The component splitting also worked very well, but a lot of refining is still needed. As for the constraints, the system works very well overall, but I would like to spend some time to make it simpler and more readable.

I would like to put up a video of some of the cool stuff we have, but I have just recently reformatted my computer and so I do not have fraps or anything at the moment. Hopefully I'll get around to that within the next week.

As for what's next, I plan to continue working on this project next semester, although this is a little contingent on what happens with finding a job. My main tasks for next semester will probably be to clean up and polish some of the constraints and motors, add multiple colliders per body and work on a new broadphase. We might also work on a SSE math library.