Based on repository activity, growth velocity and community engagement.
24
Growth2/30
Activity4/25
Popularity6/25
Trust13/20
33
Stars
High
Sentiment
Votes
33
README.md
Longeron++ is a C++17 header-only library that provides simple solutions to help organize a program's state as arrays for more efficient use of memory. Motivated by Data-Oriented Design, this library works as a flexible, simple, and more performant alternative to traditional Object-Oriented Design.
Intended Applications:
ECS Game Engines
Desktop Applications
Managing index and vertex buffers for GPUs
Embedded Systems
anything really.
Careful, this library is still in early development! API is not stable. Contributions, bug reports, and suggestions are welcome!
Introduction
There are problems with how most (C++) software is written. Objects tend to be individually allocated structures that are addressed using a pointer.
Just to list a few issues:
Adding new features to the object often requires modifications to the object type itself.
Pointers are coupled to certain memory location. Extra caution is needed to copy, move, or serialize structures that rely on pointers.
OS-level allocations (new/malloc) are not known for good performance
Cache locality is not great, especially with a high object count
Fairly recently, 'Data-Oriented Design' started to gain some popularity (though it still is very obscure).
The rise of Data-Oriented Design highlights many unnecessary difficulties associated with (class-based) Object-Oriented Design. Not only in terms of performance, but also the explosive complexity of class hierarchies, scattered states, deep call stacks, tedious refactoring, tangled spaghetti messes of references everywhere, etc...
In short, object orientation is often not the best tool for your particular problem.
Many of the Data-Oriented Design resources go over the same ideas, such as CPU caches, structure of arrays, and data transformations. Their resulting solutions are simple, performant, and maintainable; however, a few admit to losing flexibility. The only well-known Data-Oriented alternative to 'objects' was realized in the form of the "Entity-Component-System" (ECS) architecture used in very modern game engines.
Personally I find that many ECS implementations don't really capture the true essence of what ECS should really be. Treating 'entities' as 'objects' led to many of the same problems in object-oriented. Almost all implementations feature a centralized registry/world class that handles everything, which need to be very complex to fit everyone's use cases. Additionally, trying to fit every problem around entities and components is a mistake. For example, trying to use EnTT for a Falling-Sand Game simply fell apart as 2D grids are just best represented by 2D arrays, not entities and components.
From working on a spaceflight simulator (specifically planet terrain mesh) and various circuit simulators, many ECS-like patterns started to emerge. It turns out the core ideas of ECS go far beyond just ECS and game development. This was the beginning of Longeron++.
Usage and Features
Longeron++ encourages the heavy use of integer IDs. They should be preferred over pointers for storing long-term references:
A single ID can refer to many arrays/containers of different types (aka: Structure of Arrays)
New arrays/containers can be easily added to associate additional data to IDs
Containers can reallocate safely without invalidating IDs
Damn easy to serialize
Manage Instances
Instead of individually allocating objects and using pointers, use an "Id Registry" to generate IDs. These IDs can be used as an index to a container to assign data.
// Id is just an integer.
using Id = uint32_t;
// Enum class as an Id works too, but is not quite ready due to excessive int casts needed
// enum class Id : { };
// STL-style Id Registry
// Internally, it's a single wrapped std::vector<uint64_t> used as a bitset
lgrn::IdRegistryStl<Id> registry;
// Reserve IDs for 64 objects (aka: a single 64-bit int)
registry.reserve(64);
// Allocate data for our potential 64 objects using std::vector
// Might want to use std::optional if constructors/destructors are important
std::vector<Data> data(64);
// Creating new objects is a matter of generating IDs
// All this does is look for set bits in a bitset, and flips them to zero
Id idA = registry.create(); // returns 0
Id idB = registry.create(); // returns 1
Id idC = registry.create(); // returns 2
do_something(data[idA]); // Our objects 'exist' now, do stuff!
registry.remove(idB); // Delete Id 1
int idD = registry.create(); // returns 1, Id has been reused
Instead of a vector, any container that associates data to an Id is a working one. Feel free to choose a container that best fits the task:
lgrn::BitViewIdRegistry is a mixin around an range of unsigned integers. Anything integer range with a standard begin() and end() can be used as an Id Registry:
// Zeros are taken IDs, ones are free IDs. Initialize all bits to ones
std::array<uint64_t, 2> idBits{~uint64_t(0), ~uint64_t(0)};
auto fixedRegistry = lgrn::bitview_id_reg(idBits, Id{});
Id idA = fixedRegistry.create(); // returns 0
Id idB = fixedRegistry.create(); // returns 1
Id idC = fixedRegistry.create(); // returns 2
// ...
Separate Relationships from Data
It's common to map objects to strings, or to arrange objects in a hierarchy:
// Case 1: Relationship in structure
// * Bloats the object
struct ObjectA
{
std::string m_myName; // name relationship
ObjectA *m_pParent; // parent relationship
};
// Case 2: Structure coupled to Relationship
// * Difficult to have many simultaneous relationships
struct ObjectB { /* ... */ };
std::map<std::string, ObjectB> m_objects;
// std::shared_ptr can potentially be used, but forces individual allocations and can be difficult to copy.
Along with IDs, these relationships can be cleanly separated from any object data.
Reference-counting and RAII-like safety without pointers
Reference counting often requires using a class that stores a pointer to the count, and accesses this count during construction and destruction. Due to side effects, overhead, and general rule of avoiding pointers, Longeron++ provides an alternative solution.
lgrn::IdOwner wraps a single integer ID type with some safety features:
Has a deleted copy constructor
Will assert if destructed or reassigned while containing a value
Internal state can only be modified by a single friend class specified by template
Safe reference-counted or unique Ids can be implemented by providing functions in this friend class that creates and or destroy IdOwners.
Bitsets can work great as dirty flags, as bit positions can be used to represent IDs. Iterating ones of a bitset is only slightly slower than iterating an array/vector of integers.
HierarchicalBitset (Deprecating soon! It's inefficient, and a non-owning replacement is coming): Uses a hierarchy of bit arrays to represent a range of integers with low memory usage ~~and fast iteration speeds~~.
lgrn::HierarchicalBitset bitset(512); // allocate space for 512 bits
bitset.set(69);
bitset.set(42);
bitset.set(420);
for (std::size_t bitNum : bitset)
{
// outputs 42, 69, then 420 (ascending order)
std::cout << bitNum << "\n";
}
IntArrayMultiMap: STL-style owning container. Uses internal integer arrays to map IDs (keys) to variable-sized arrays of data. Stored data is contiguous in memory, but can get fragmented when elements are removed.
// use ints as IDs, use float as data. 16 max floats, 4 max IDs
IntArrayMultiMap<int, float> multimap(16, 4);
// Emplace some 'partitions' associated with IDs 0 to 2
multimap.emplace(0, {1.0f, 2.0f});
multimap.emplace(1, {3.0f, 4.0f, 5.0f});
multimap.emplace(2, {6.0f, 7.0f, 8.0f, 9.0f});
// in memory: [1.0f, 2.0f, 3.0f, 4.0f, 5.0f, 7.0f, 8.0f, 9.0f, ... ]
std::cout << multimap[2][2] << "\n"; // prints 8.0f
// remove 1 and pack
multimap.erase(1);
multimap.pack();
// in memory: [1.0f, 2.0f, 6.0f, 7.0f, 8.0f, 9.0f, ... ]
If moving data during packing is a heavy operation, the pack(n) function accepts a max number of moves, intended to spread moves across a couple frames.
Entity Component System
A 'Longeron++ style' ECS goes something like this:
Entity: An integer Id representing the existence of a 'thing'.
Component: Data associated with an Entity, usually a container.
System: A function that operates on entities and components
A simple way to represent entities and components may resemble this:
Systems are the trickiest part to get, as it requires fully switching to a different mindset that focuses on how a world should behave as a whole instead of individual objects. In short, Don't use a 'per-entity' update function.
Consider some steps needed to update a simple particle system. Note that we don't want to have a particle.update() function:
Apply gravity to all particle velocities
Add all velocities to positions
Systems in ECS are simply just functions and nothing more, and are somewhat analogous to the real world laws of physics: real-life gravity will act on anything with a mass component. Some systems depend on the outputs of other systems; some don't interfere with each other and can be run in parallel.
Users are free to write abstractions to more easily manage systems and components, but please do that LAST and don't shoot your own foot :)
Possible ways to write systems:
// Pass the whole world, not recommended as it depends on World; do only out of laziness.
void system_a( World& rWorld )
{
for (...)
}
// Pass container(s) by reference
void system_b( Container& rComponentAs, Container& rComponentBs )
{
for (...)
}
// Also try spans or iterators
// Main loop
while (running)
{
system_a(world);
system_b(world.m_componentAs, world.m_componentBs);
}
Knowing exactly which components a system will modify will make parallelism nearly trivial.
Deleting entities
A common problem in ECS is how entities can be deleted along with all their associated components. Other ECS implementations may turn to some form of polymorphism, but of course we'd want to stay with a pure systems approach.
Entities that are going to be deleted can be added to a container, such as a vector or HierarchicalBitset. Individual systems can then delete their corresponding components.
// Perhaps make these for each thread that deletes entities and pass them into systems all at once?
lgrn::HierarchicalBitset m_toDelete;
while (running)
{
// Pass m_toDelete into a system that can request to delete entities
system_something(world.m_dataA, world.m_toDelete);
// Run delete systems, maybe in parallel?
system_delete_a(world.m_componentAs, world.m_toDelete);
system_delete_b(world.m_componentBs, world.m_toDelete);
// Delete the IDs
for (std::size_t entId : world.m_toDelete)
{
world.m_entities.remove(Entity(entId));
}
// clear deleted entities for next frame
world.m_toDelete.reset();
}
Systems that create entities
Solution: don't. Entity creation should happen in one place. Systems can return a value to request entities.
std::vector<ThingId> newIds;
while (running)
{
int entitiesRequired = system_create_calculate_required(world.m_componentAs);
if (entitiesRequired != 0)
{
newIds.clear();
newIds.resize(entitiesRequired);
// create multiple IDs, store in newIds
world.m_ids.create(std::begin(newIds), std::end(newIds));
// pass in newly created IDs to the next system
system_create_resume(world.m_componentAs, newIds);
}
}
Message passing
Real message passing this time. Dynamic Dispatch is Not Message Passing (DDINMP)
If you think about it very carefully, entities and components are simply persistent messages passed between systems. For example, entities and components that describe a solid cube is a way for a physics system to communicate with a render system.
Passing data structures or components to system functions is an excellent alternative to OOP-style event listeners, signals, or observers.
std::vector<SomeEvent> events; // can be dirty flags, commands, or really anything
system_a(world, events); // writes
// pass events into other systems (likely parallelizable)
system_b(world, events);
system_c(world, events);
system_d(world, events);
Centralized world?
Components containers can be easily stored in separate structures to isolate unrelated systems.
Engine Test Scene: Displays a spinning cube. Note how the rendering functions on the bottom half of the file accept the EngineTestScene as const. The scene is kept as raw data, allowing the renderer to be destructed and recreated without bothering the main scene.
Resources Class: see Unit Test and Explanation. The Resources class can store arbitrary types associated to Resource IDs, which feature reference counting using lgrn::IdOwner.
Notes
A longeron is one of the main structural elements of an aircraft or similar vehicle used in aerospace. This relates to the project's roots in OSP-Magnum, which is a spaceflight simulator.
Ecosystem Role
Standard MoltPulse indexed agent.
Embed Badge
Show off your Pulse Score in your GitHub README to build trust and rank higher.
