search

Capital-Asterisk / longeronpp

"Longeron++" C++17 library for simple memory-efficient or 'data-oriented' structures
MIT License
32 stars 4 forks source link
c-plus-plus c-plus-plus-17 cmake containers cpp cpp17 data-oriented-design entity-component-system header-only memory-management modern-cpp structure-of-arrays

readme

# longeron++

Windows Linux Mac OS X

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:

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:

Fairly recently, 'Data-Oriented Design' started to gain some popularity (though it still is very obscure).

See: Data Oriented Design Resources

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.

See: Entity Component System FAQ

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:

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:

Who cares about performance, just use a map lol:

std::unordered_map<Id, Data> data;

Use EnTT's basic_storage. It's pretty cool.

entt::basic_storage<Id, Data> data;

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.

std::map<std::string, Id> m_nameToObject; // :)

std::vector<Id> m_parents; // parent of objId = m_parents[id]

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:

Safe reference-counted or unique Ids can be implemented by providing functions in this friend class that creates and or destroy IdOwners.

lgrn::IdRefCount<Id> refCounts;
using Owner_t = lgrn::IdOwner< Id, lgrn::IdRefCount<Id> >;

Owner_t ownerA;
Owner_t ownerB;

ownerA.has_value(); // returns false
ownerB.has_value(); // returns false

ownerA = refCounts.ref_add( Id(1337) );

ownerA.value();     // returns 1337
ownerB.has_value(); // returns false

std::swap(ownerA, ownerB);

ownerA.has_value(); // returns false
ownerB.value();     // returns 1337

// only refCount is allowed to create new values
ownerA = refCounts.ref_add(ownerB.value());

ownerA.value();     // returns 1337
ownerB.value();     // returns 1337

refCounts.ref_release(std::move(ownerA)); // safely clear value
ownerB = Owner_t{}; // KABOOM!!!! ABORT!!

Since IdOwners are just a single integer internally, there is theoretically no overhead in release builds.

Useful Containers

Entity Component System

A 'Longeron++ style' ECS goes something like this:

A simple way to represent entities and components may resemble this:


using Entity = uint32_t;

struct ComponentA { /* ... */ };
struct ComponentB { /* ... */ };

struct World
{
    lgrn::IdRegistryStl<Entity> m_entities;

    std::vector< std::optional<ComponentA> > m_componentAs;
    std::vector< std::optional<ComponentB> > m_componentBs;
}

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:

  1. Apply gravity to all particle velocities
  2. 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.


struct World
{
    lgrn::IdRegistryStl<Entity> m_entities;

    std::vector< std::optional<ComponentA> > m_componentAs;
    std::vector< std::optional<ComponentA> > m_componentBs;
}

// Separate the entire renderer, ez.
struct WorldRendererOpenGL
{
    std::vector< std::optional<GlTransform> > m_transforms;
    std::vector< std::optional<GlTexture> > m_texture;
}

// :)
struct WorldRendererVulkan { ... };
struct WorldRendererDirectX { ... };

// ...

main_render_function_gl(world, worldRendererGl);

Examples

More examples coming soon: a falling sand game? a voxel game?

OSP-Magnum

OSP-Magnum is a work-in-progress spaceflight simulator that Longeron++ originated from. It uses EnTT and other 3rd party libraries.

OSP-Magnum

Specific files that may be worth looking through:

Notes