Idea: Guaranteed Dense Entities

[dmyyy]

What problem does this solve or what need does it fill?

Guaranteeing entities are densely packed together can open up some interesting optimizations - flat arrays with offsets are often used to optimize in-game tile/voxel storage/access - you can take the position and find exactly what index it belongs to per some agreed upon scheme. This happens to be similar to the way entities are stored and indexed today (Vec<EntityMeta>) - where the entity_index is the id!

However, since entities aren't guaranteed to be contiguous because entities from a freelist may be used, if a tilemap/voxel library wants the flexibility of using entities (type-erased data) for each tile/voxel of their world they need to maintain their own Vec<Entity>'s. This is wasteful - if we can guarantee spawned entities are contiguous/tightly packed at the call-site then that list already exists on the world! We can halve memory cost (useful if your'e pulling something like an 8x8x8 chunk of entity voxels often), and cut down on the double indirection here.

If you want to push the absolute limit on the number of tiles/voxels in your game, you're better served with some Vec<u8> or bit array - at the end of the day it's just a trade-off between data model flexibility, and speed. I would argue we want to encourage users towards using entities as much as possible since having one source of truth is helpful when prototyping.

What solution would you like?

Improve on the status quo - allow fast/memory-efficient AND flexible third party data structures to be built upon assuming a spawned batch of entities has their indices tightly packed, and sequential. Expose some way to spawn a batch of densely packed entities. Allow libraries to build data structures that can assume some batch of entities are densely packed. Get rid of the double indirection if you want a batch of entities to represent some spatial data structure.

This seems trivially doable by just allowing allocation of only new entities instead of ones from the freelist. The user-facing api and implementation details could use some bike-shedding. Could be something like fn spawn_batch_dense() or a boolean on spawn_batch.

This can also be framed as a "custom allocator for Entities" that allows someone to reserve a contiguous block of entities.

Alternatives

Maintain status quo. Force users to write their own index linearization data structures instead of just using World::Entities. If you want to linearize over a list of entities, force the double indirection and the user to construct their own Vec<Entity>, mapping a position -> vec index calculated via offset -> Entity.

Possible Issues

Possible memory bloat if chunks are allocated/de-allocated often and things in the free-list never end up used.

[dmyyy]

Exploration for a possible user-facing abstraction that can be built upon this.

/// Contiguous block of entities!
#[derive(Component)]
pub struct EntityChunk {
    start_entity_index: u32,
    len: u32,
}

impl EntityChunk {
    pub fn offset(self, other: Entity) -> u32
}

// user library code implementing a tilemap

pub trait TileEntityChunkExt: Clone + Copy {
    /// Local tilemap position relative to the root at (0,0).
    fn local_pos(self, entity: Entity) -> UVec2;

    /// World‐space position by translating the local position by `root_pos`.
    fn world_pos(self, entity: Entity, root_pos: UVec2) -> Vec2;

    /// One step in +X (right).
    fn pos_x(self, entity: Entity) -> Option<Entity>;

    /// One step in –X (left).
    fn neg_x(self, entity: Entity) -> Option<Entity>;

    /// One step in +Z (backward).
    fn pos_z(self, entity: Entity) -> Option<Entity>;

    /// One step in –Z (forward).
    fn neg_z(self, entity: Entity) -> Option<Entity>;
}

impl TileEntityChunkExt for EntityChunk {}

EntityChunk can be made more opinionated - we could also provide our own generic linearization impl on top for users as well. Now users can do

// before
pub struct EntityChunkMap(HashMap<UVec2, Vec<Entity>>);
// after
pub struct EntityChunkMap(HashMap<UVec2, EntityChunk>);

Also probably want to add an on_remove hook to the entity chunk root to clean up its children.