Introducktion

Eendgine is a 3D game engine I've been developing with the goal of producing Trey Simulator 4. It's written in C++ and based on OpenGL. So far I have multiple subsystems developed, but this post is about the entity batching system.

EntityBatch

Goals

The goal of this entity batching system was to create an entity system that increased cache locality and enabled the sorting of entities for performance optimizations, while keeping the system flexible and applicable to different entity types. By keeping all entities of a certain type in a single vector, their data is localized and sorting is made possible. Flexibility is made possible via C++ template metaprogramming. In addition it provides a way to hold a weak reference to an entity. Weak in the sense that one can check if it's still valid before trying to utilize it. This will cut down on complexity where entities are holding refrences to eachother.

In addition to being a functioning entity system for the long awaited successor to Trey Simulator 3, EntityBatch is my excuse to get comfortable with C++ templating and metaprogramming in general. While I have certainly gotten a little cozy, I have also seen the horrors of which C++ is capable. The value of Rust's impl for generic types is clear now. Despite said horrors, I chose to forgo the alternative of using inheritance. Templating provides more flexibility and learning the read convoluted errors is good for the soul.

Outline

Every EntityBatch has three major data structures

1. A vector of labeled entities (entity paired with 64 bit id)
2. An unordered map that maps entity IDs to indexs in the aforementioned entity vector
3. A vector of Ids to be erased

Insert

A new entity is emplaced at the back of the vector of entities.

Erase

The ID of the entity to be erased is added to the to erase vector and delt with during sorting.

GetRef

Uses the unordered map to provide a pointer to the entity from an ID. Returns NULL if not present in the map.

This does mean that one must check for NULL, but it seemed the most straightforward way to do things. C++ doesn't allow refrences to be wrapped in optionals like Rust does.

Sort

Sorting goes through the following steps, where most are occuring in linear time. However, sorting operates with a time complexity of O(nlog(n)). This leads me to believe that the performance hit will scale linearithmicly with the number of entities and linearly with the number of entites to be erased.

• Create a vector of entity indexes to be erased
• Sort the vector of IDs in decending index order
• Swap the entities to be erased to the end of the vector
• Delete entities to be erased from the end of the buffer
• Sort entities based on texture
• Draw entities

Draw

Sorts, then iterates through the vector of entities, binding the appropriate texture as it changes and drawing each entity. Since the entities are sorted by texture, the binding of textures in minimized.

Optimizations

I tried my hand at operator overloading, where I deleted the copy operator and implemented custom move operators for each of the four entity types. This greatly improved performance by avoiding copies during the sorting of entities. This brought frame rates from a handful of fps to about 30fps when processing 5k animated meshes Dolls and 10k static meshed Statues.

Looking forward

I wanted to get a post out about my entity batching system to start this devlog, as it's the core of Eendgine. However, in my next post I plan to detail somthing more unique, my terrain format. It is designed to utilize PNGs as much as possible. This will help me forgo writing my own level editing tools and use GIMP as much as possible in the creation of Trey Simulator 4.