bevyengine / bevyengine/bevy

Idea: Guaranteed Dense Entities

Open
#18,861 1 comment 1 reaction 0 assignees View on GitHub
A-ECS C-Feature C-Performance S-Needs-Design-Doc X-Needs-SME
Dominant language
Rust
Stars
48.2k
Forks
4.8k
Avg merge
3d 22h
Merged PRs (30d)
161

Description

## 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`) - 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`'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` 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`, 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.

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.