Design: N->N relationship

  • It's all about differentiating data and stable handles for dealing with references to data when the backing storage changes (add/remove/move/resize)

  • Important Notes :

    • Think in terms of storage structures (Sparse Sets), not in terms of ECS semantics.

    • Don't store pointers to data inside those data structures, as the data can be corrupted on add/remove/move/resize.

      • "Stable handles"

      • Ways to resolve this :

        1. Make that moving things inside this array doesn't corrupt the data:

          1. The data is not stored inside this array, but a different array that doesn't move.

            1. Handle_Map .

              • Uses a Handle  to get the data.

            2. Simple Array.

              • Just uses an index to get the data.

              • No generational tracking.

          2. The data is not stored inside this array, but on a data struct where the "key" is always valid regardless of the elements of the backing array move.

            1. Sparse Set (id -> T).

              • A generational system can be implemented.

              • Differently from a handle map, it enforces data packing at the cost of more memory usage for the .sparse  and .dense  arrays.

              • This doesn't enforce the concept of Entity or ECS. It's just a storage structure, just like a Handle_Map .

            2. Sparse Set (Component: Entity -> T).

              • A generational system can be implemented.

              • Using an entity as the key is tricky in some cases, as it makes the design too involved into ECS and the whole concept of "entity".

              • Enforcing the concept of "entity" when it doesn't actually fit, it's just weird.

              1. The Body  is an entity that sparse.add(&_transforms, entity_body, spatial.Transform2_Node{})

                • Makes the design too involved with the concept of components, making the Body  to be an entity. This can be weird as there's now a question of extra lifetime handling, etc.

                • In a way, this creates extra complexity in the ECS design.

              2. The Body  holds into an entity id to fetch the Transform2_Node

                • This basically means that the Body  will hold to the "key" for the Transform2_Node , but this is made in a way that the body seems to be holding into an entity inside of it, which is really weird. The ""entity_transform"" is not actually an entity semantically, but only a key to a transform storage structure.

                • In the end, it makes more sense to simply use a Sparse Set (id -> T)  as it doesn't make the design so confusing.

        2. Make the content not be stored inside an array.
          This goes against the ECS/DoD design.

  • If all data is stored sequentially in a data struct, I need an access key to get a specific entry, otherwise I'd have to iterate over the data struct to find a match.

    • array: index

    • sparse set: entity

    • map: key

    • handle_map: handle

  • Not using ECS had the advantage of the "object type" that had the timer indicate the "timer type", for example: a timer inside an AI component is understandably an AI timer; a timer inside a hitbox is considered a Hitbox Timer. Now with ECS I lost this hint. I need a way to improve these queries.

  • Major diferences between Handle_Map  and Sparse_Set :

    • The Handle_Map  requires the Handle  to be stored.

    • The Sparse_Set  doesn't require the entity_key  to be stored, as it stored this entity_key  within itself.

    • It could go as far as:

      • If it's directly stored: can be both Handle_Map  or Sparse_Set .

      • If it's not directly stored: is a Sparse_Set .

Adding one extra indirection

  • "Sparse Set to Sparse Set" / "Handle to Handle" / "Pointer to Pointer".

  • One way to think of it is a sparse.Sparse_Set(^T) , as there's an extra indirection in the sparse set.

SS -> T

  • The main ECS design is "SS -> T", where SS is a Sparse Set and T is the data.
    | sparse.Key  ( Entity ) | T  ( Sprite ) |
    |-------------------------|----------------|
    | 1                       | sprite1        |
    | 1                       | sprite2        |
    | 1                       | sprite3        |

  • Remove :

    • "Remove Entity  from SS(Sprite) ".

    • "Remove sparse.Key  from SS(T) ".

  • This brings a lot of problems if you want a N:N relationship, etc.

    • For example, one system my want to act on sprite2  in specific, but using "SS -> T" doesn't give any information that could help differentiate sprite2  from the other sprites.

    • Adding an extra level of indirection helps with that, as a SS could hold into sparse.key  for sprite2  and I could use that to filter the data.

SS -> SS -> T

  • One way I like to think of this strategy is:

    • The inner SS is what holds the raw data, requiring a key to access the data.

    • The outer SS holds a key to a key (akin to a pointer to a pointer), grouping keys based on specialization criteria.

  • Interpretation: Extra level of indirection :

    • Mapping Table ( Entity  -> Sprite_Key )

      • Primary Key :

        1. Composite PK ( Entity , Sprite_Key ) — each row is an association/ membership row; this is the usual pattern for an association table, and it allows multiple rows and prevents duplicate identical associations; recommended default.

        2. If you insist each Sprite_Key  appears at most once in the mapping, then Sprite_Key  can be declared unique in the mapping table (making it effectively the PK there). This choice changes cardinality.

          • This is not the case, as different Entity  can have the same Sprite , sharing the resource.

      • Foreign Key :

        • Sprite_Key  is a foreign key that references the Sprite_Key  primary key in the "Sprite Table".

        • Entity  is a foreign key that references the entity identity (the "Entity Table", if exists).

      • Cardinality :

        • 1:N - one Entity  maps to many Sprite_Key  rows.

        • N:N - if multiple Entity  may reference the same Sprite_Key .

          • The "Mapping Table" is then a true association/join table.

        • The composed relationship Entity  â†’ Sprite  (through the mapping) is (1:N) (one Entity  has many Sprite s).

        • Whether a particular mapping behaves like 1:1, 1:N, N:1 or N:N is determined by additional uniqueness constraints you choose to add on Entity or Sprite_Key.
          | sparse.Key  ( Entity ) | sparse.Key  ( Sprite_Key ) |
          |-------------------------|-----------------------------|
          | 1                       | 1                           |
          | 1                       | 2                           |
          | 1                       | 3                           |

    • Sprite Table ( Sprite_Key  -> T )

      • Primary Key :

        • Sprite_Key ; each slot id uniquely identifies one sprite row.

      • Foreign Key :

        • No FK.

      • Cardinality :

        • 1:1 - each Sprite_Key  maps to exactly one Sprite.

      • Typically 1:1: Slots.slot_id is the PK and Sprites.slot_id is a PK/FK pointing to Slots. Each slot holds exactly one dense row (or points to it).

      • You can make Sprites shared by multiple slots if you change the model (e.g., multiple slot_ids referencing a single sprite_data_id): that would be N:1 from Slot to Sprite (slots referencing a shared immutable resource).
        | sparse.Key  ( Sprite_Key ) | T  ( Sprite ) |
        |-----------------------------|----------------|
        | 1                           | sprite1        |
        | 2                           | sprite2        |
        | 3                           | sprite3        |

    • Remove :

      • "Remove Entity  from SS(Sprite_Key)  and Sprite_Key  from SS(Sprite) ".

      • "Remove sparse.Key  from SS(sparse.Key)  and sparse.Key  from SS(T) ".

  • Interpretation: Hierarchical Structure :

    • Sprite is an "Entity", in this scenario.

    • Children Table ( Entity  -> Sprite_Entity )

      • Could be interpreted as table of "children of Entity ".
        | sparse.Key  ( Entity ) | sparse.Key  ( Sprite_Entity ) |
        |-------------------------|-----------------------------|
        | 1                       | 1                           |
        | 1                       | 2                           |
        | 1                       | 3                           |

    • Sprite Entity Table ( Sprite_Entity  -> T )
      | sparse.Key  ( Sprite_Entity ) | T  ( Sprite ) |
      |--------------------------------|----------------|
      | 1                              | sprite1        |
      | 2                              | sprite2        |
      | 3                              | sprite3        |

    • Remove :

      • "Remove Entity  from SS(Sprite_Entity)  and Sprite_Entity  from SS(Sprite) ".

      • "Remove sparse.Key  from SS(sparse.Key)  and sparse.Key  from SS(T) ".

    • Discussion :

      • Funny enough, a hierarchical structure like this has the exact same layout as the strategy shown just above.

  • Discussion with ChatGPT :

    • It is exactly the same pattern as a normalized SQL schema: one table (Sprite_Key) of stable keys/slots and a separate table of actual data (Sprite). Entities reference keys (foreign keys); keys point to rows of Sprite.

    • That indirection gives you stable handles that survive reallocation/moves of the dense backing store, and it gives you a place to put per-key metadata (generation, refcount, tags, indices) so references remain valid or can be detected stale.

    • Referential integrity is enforced by generation checks and by explicit refcount or cascade-delete semantics.

    • Use single-level (Entity -> index into dense T) when:

      • There is one owner per data row.

      • You don't need stable external references to rows.

      • You can avoid moving rows (or you accept updating entity->index on swap).

    • Use two-level when:

      • You need stable handles that persist across moves/resizes.

      • Multiple owners or external references must remain valid.

      • You want to store metadata per-slot (generation, tags, refcount) separate from data.

      • You want to model shared resources (textures, meshes) and have many lightweight references.

    • The SS -> SS -> T  pattern with a small slot/meta table and a dense data array is the pragmatic, normalized approach that gives stable external references, safe lifetime semantics (via generation) and the flexibility to group/filter/share data.

    • If you need absolute highest throughput for iteration and you never need external stable handles, the simpler SS -> T (entity->index) is slightly faster, but it complicates external references and reuse handling.

  • Discussion with ChatGPT on N:N :

    • N:N join/association tables are standard for modelling many-to-many relationships. They’re expected and correct when multiple owners reference the same target and vice-versa.

    • Table size grows with number of associations; queries that join through the mapping require index lookups or scans; indexes (on entity and sprite_key) are required for efficient lookups in both directions.

    • N:N gets a bad reputation because it introduces an extra layer of indirection and operational cost (joins, indexes, churn), and because beginners sometimes model multivalued attributes directly instead of normalizing. It’s not inherently wrong — it’s the correct, normalized representation for many real relationships — but it does demand deliberate engineering for performance and lifecycle.

    • Canonical ways to break down and manage N:N in SQL:

      • Normalize with a junction (association) table.

        • That is the standard decomposition: represent the many-to-many as two 1:N relationships with an explicit mapping table. (In your ECS this is already the Mapping table.) This is the correct, normalized model.

        • A mapping (junction/association) table is a dedicated table whose only job is to record pairs (or tuples) that link rows from two other tables.

        • Conceptually it turns a many-to-many relationship into two one-to-many relationships: 'A → mapping' and 'mapping → B'.

        • In your ECS terms: the mapping table holds pairs ( Entity , Sprite_Key ); each row says “this entity has (or references) this sprite slot.”

        • Why use it (the normalization reason):

          • It avoids embedding multiple values in a single column (no lists in one field).

          • It prevents duplication of the sprite rows while allowing many entities to share the same sprite slot.

          • It makes the relationship explicit and enforces integrity via keys and constraints, so you don’t get orphaned or inconsistent references.

        • Caio: The whole point is that if I were to do " Entity  -> Sprite " directly, while I want to preserve a N:N relationship, I would have duplicated sprites which is not acceptable.

          • Yes. In a situation like this you have two choices :

            1. Duplicate the sprite data for every entity that needs it (store by-value on the entity).

              • Consequences: more memory, slower writes when you want to change the sprite globally, and risk of inconsistent copies if you forget to update every duplicate.

            2. Introduce indirection so entities point to a single canonical sprite record instead of embedding the data :

              • That indirection is precisely what the mapping (junction) table or slot/handle layer provides .

          • Caio: Cool =)

      • Add constraints.

      • Promote the association to a first-class entity.

        • Instead of treating the mapping row as “just a pair”, give it its own identity and metadata (a slot row). That lets you store lifecycle fields (generation, refcount, timestamps) on the association and treat changes atomically.

    • For ECS, this enables sharing component instances or resources across entities (many entities → same slot) and allowing entities to hold multiple component instances of that type (the mapping table holds many rows per entity). Useful for shared meshes, shared sprite resources, decals, or when an entity can legitimately have multiple components of the same type.

SS -> HM -> T

  • Sparse_Set  to a Handle  to a Handle_Map .
    Problems :
    The data T  is not packed, as HM  purposely doesn't pack the data to avoid breaking the handles.
    This defeats a bit of the performance improvements with ECS.
    Layout :
    Handle_Map :
    Stores the data.
    hm.Handle_Map(T, Handle_To_T, SIZE)
    Handle :
    Access to the data.
    Sparse_Set
    Storage of the Handle.
    sparse.Sparse_Set(Handle_To_T)
    Usages as a Handle :
    Damage_Indicator :
    odin Damage_Indicator :: struct { sprite: rd.Sprite_Handle, timer:  timer.Timer_Handle, }
    AI_State_Machine :
    odin AI_State_Machine :: struct { timer_ptr:  timer.Timer_Handle, is_stopped: bool, }
    Usages as a Sparse_Set  to a Handle :
    Projectile:
    odin _projectiles_trans: sparse.Sparse_Set(spatial.Transform2_Node_Handle)
    Sprite :
    odin _sprites_bouncy: sparse.Sparse_Set(rd.Sprite_Handle)
    Sprite  is stored inside a Handle_Map .
    The sprite_component  is a Sparse Set for Sprite_Handle s.

HM -> SS -> T

  • Problems :

    • In this case the concept of an "entity" with SS doesn't exist anymore and you only work with handles to HM.

      • This can be bad, as some "sparse sets"/"components" might not care for this extra indirection level.

      • This simply goes against the main design. "If you have SS -> T, the entity is a sparse.Key , but if you have an extra indirection, the entity becomes a hm.Handle ".