Project Dusk #2 - Scene graphs

I struggled a lot last week due to sickness and being unmotivated in general. One reason is that I am currently not seeing results of what I am doing. And the type system didn't come along so well as it isn't a trivial system. Working in empty space isn't something I enjoy either (good choice I didn't become an astronaut). So I decided to work on something that delivers visible results.

Initially I thought I would use an ECS approach over a hierarchy graph, but so far, I didn't find compelling enough arguments for an ECS. I looked into the pico_ecs header only library and it looks really good. Very similar to my style of working. But at the same time, there are some points that I don't like about ECS in general (yeah, never really worked with one seriously, so what do I know?).

So let's note down the pros and cons of both approaches:

• Hierarchy: This is the biggest issue I have with ECS. Implementing a hierarchy in an ECS is not straightforward - and I really want to have this
• Component limitations: ECS implementations often have certain limitations, like for instance that only one component of a certain type can be attached to an entity. Not a great deal in general, but it's a limitation that needs to be considered when making an editor
• Systems first approach: When I work on a game, I often don't know exactly how my logic will work. I admit that I have no real experience here, but every time I tried to think in systems first, I failed to get started. With a hierarchy, I can just start with a simple script and add more complexity as I go. I don't need to think about how to structure my logic in the beginning. While this obviously doesn't lead to efficient code, I find it more important to get started and see results.

That doesn't mean I am not taking inspiration here and there. I keep thinking that a component on a scene graph entity could be treated like a system with two components that are required: The component and the scene graph entity. The component's methods like the update and draw methods can be treated like an ECS system function callback. So that is the approach that I am exploring right now:

• Component types are registered on the scene graph
• All components of a type are allocated in a single array, belonging to the component type
• This also means that finding all components of a certain type is a simple array iteration
• When executing a component function, I am not iterating through the scene graph, but through the component array
• Skipping inactive entities is a bit complex here, because the deactivation of a parent will deactivate every child; but this can be dealt with by a flag on the entity that is updated when the parent status changes. This makes status changes potentially slower.
• Scene entities and components are all allocated in separate contiguous memory blocks. Since those arrays are subject of resizing, it means that hard pointers aren't allowed and instead I am working with indices
• Contiguous memory blocks are a good thing for cache locality
• The index approach is actually also beneficial: Each reference is a 64 bit struct where 32 bits are the index and 32 bits are the generation / version. I only need to compare the generation value to validate the reference.
• This makes deletion and reuse of entities and components very simple: Setting the generation to 0 is enough to invalidate the reference. The next allocation will just increase the global generation value and reuse the index
• This solves a lot of problems I had with the previous approaches: Deletion is often a pain to get right; like: what should happen when a call deletes an entity that is currently processed in a loop? Most systems are keeping a queue of entities to delete and then delete them after the loops have finished. I currently don't see a need for this anymore. The invalidation of the generation instantly makes every reference invalid while not causing any memory access problems.
• For example: The iteration over the list of components triggers the deletion of the parent of the currently processed component. When the next component is processed, the reference of the component to its entity is invalid and the component is skipped.
• Since the iteration through the scene graph is linearly done, the code is very simple
• Another advantage is, that if there aren't many components, there won't be many iterations either. In such a system, entities without components don't cost much in terms of performance. Since my system calculates world positions on demand only (and only when the transform has changed), the additional cost of such empty entities should be minimal
• One tradeoff here is execution order - which could prove fatal for some cases, so I have to provide alternative execution models; for example, UI event handling and rendering demands that all elements are drawn in hierarchical order, which is not guaranteed with this approach.
• One approach could be that a component type can specify if it needs hierarchical order execution. In that case, the scene graph is traversed and the components are executed in the order defined by the graph. Scene graph iteration is very probably slower because cache locality is likely decreased or lost
• Another approach could be that entity data is kept in order. But that would break the referencing system.

What I intend to do is to at least initially compare pico_ecs and my system to check what the implications are. Making web builds and testing those is also part of this.