Algorithms and data structures
What we took from existing engines, what we wrote ourselves, and why. The details of each part are in its design
document, linked from every row.
The ECS
The engine is an Entity Component System: the subject recommends it, and it gives the decoupling the subject asks for
(a renderer reads a sprite and a position, nothing else). We compared five existing ECSs (Unity DOTS, Unreal Mass,
flecs, Bevy, EnTT) part by part; the full comparison is ecs/design.md.
| Part |
Options |
Our choice |
Why |
| Entity |
Plain index; index + generation; pointer |
32-bit index + 32-bit generation |
A stale handle is detected (isAlive()), ids are reused safely |
| Storage |
Archetype tables (flecs, DOTS); sparse sets (EnTT); both (Bevy) |
Sparse sets with tick columns today; archetype tables designed as a per-component option (05) |
R-Type's entities change composition often (bullets, states, script components): sparse sets make adding and removing cheap. Tables would iterate faster for large stable sets, for later games |
| Sparse array |
Flat array; hash map; paged array |
Paged sparse array, pages of 4096 entries, allocated on first use |
O(1) lookup without reserving memory for every possible entity |
| Queries |
Typed only; dynamic only |
Typed queries compiled down to dynamic queries |
One iteration algorithm to test and optimize, and Luau and tools use the same one |
| Change detection |
Dirty flags; per-system ticks; per-instance ticks |
Per-instance added/changed ticks (Bevy) |
Exact "what changed since this system last ran", and exactly "send this component of this entity" for replication |
| Commands |
Immediate changes; deferred buffer |
Deferred buffer flushed in recording order at the end of each phase; spawn() reserves an id at once |
Iterating a query while spawning stays safe |
| Events |
Observers (immediate callbacks); queues |
Double-buffered queues (Bevy) |
All logic stays in scheduled systems, in a predictable order |
| Scheduler |
Free order; phases; dependency graph |
Phases + explicit ordering + fixed timestep; access sets recorded |
Deterministic order now, a parallel scheduler possible later |
| Hierarchy |
Relationship pairs (flecs); parent/children components |
Parent / Children kept by the World, plus a propagation system |
Covers UI, scenes and attached objects without a relationship engine |
| Reflection |
Compile-time only; runtime type info |
A runtime TypeInfo per type: fields, offsets, types |
One description serves scripts, scene files, the editor and the network |
Time. Gameplay runs on a fixed timestep (60 ticks per second by default), decoupled from the frame rate, as the
subject requires: the starfield and every entity move by elapsed time, never by frame.
Replication
Full design: network/design.md; wire format: network/protocol.md.
| Problem |
Options |
Our choice |
Why |
| What to send |
Full state every tick; deltas from the previous tick; deltas from the last acknowledged tick |
States changed since the last snapshot the client acknowledged (Quake 3, bevy_replicon), per entity and per component |
A lost snapshot is repaired by the next one with no resend logic; nothing is sent twice once confirmed |
| Bullets |
Replicate every tick; spawn only |
kSpawnOnly components: sent at spawn, then simulated on both sides |
Hundreds of bullets cost ~20 bytes each once, instead of every tick |
| Smooth display |
Show the latest snapshot; extrapolate; interpolate |
Interpolate ~100 ms in the past between two snapshots (designed, not implemented yet) |
No stutter when snapshots arrive unevenly |
| The local ship |
Wait for the server; predict |
Client-side prediction with server reconciliation: each snapshot carries the last input the server applied (lastProcessedInput), the client replays the later ones (physics moveAndSlide) |
Movement answers at once; the server still decides |
| Inputs |
Events ("pressed"); states ("held") |
Held states, the last 3 samples in every message |
A lost datagram is covered by the next one, with no resend delay |
| Agreeing on the game |
Trust; a version number; a manifest of layouts |
A manifest of components and actions, with layout hashes, sorted by name |
Short ids on the wire; a client with other scripts is refused instead of misreading bytes |
Reliability over UDP
| Mechanism |
Algorithm |
Notes |
| Sequence numbers |
16-bit, compared with wrap-around (isNewer) |
RFC 1982 serial number arithmetic |
| Acknowledgements |
ack + 32 ackBits in every datagram |
Each datagram acknowledges 33; lost acknowledgements are covered by the next ones (Gaffer On Games) |
| Reliable channel |
Message ids, resend after ~1 RTT, a receive window of 256, in-order delivery |
A ring buffer (SequenceBuffer) indexed by sequence modulo its size, O(1) |
| Keepalive and timeout |
Empty datagram after 100 ms idle, lost after 2 s |
Values are settings |
| Anti-spoofing |
Challenge, random session token, padded requests |
From the netcode standard |
Custom algorithms, and why we wrote them
| What |
Why not a library |
| The ECS itself |
The subject asks for an engine of our own; and only our own ECS could carry per-component replication modes, Luau-declared components and capsules natively |
| The reliability layer |
ENet and the like do not know about snapshots and acknowledged ticks; ours is about 700 lines and tested with a simulated lossy link (network/simulation/LinkSimulator) |
| The bounds-checked byte reader/writer |
Every read is checked and a failed read invalidates the reader, so a decoder reads a whole message and checks once: no exceptions on network data |
| Input quantization |
Axes in [-1, 1] as i16 (×32767): half the bytes of a float, with a precision far below what a stick reports |
| Name hashes |
FNV-1a 64-bit of a component's name identifies it across shared libraries (plugins), where a per-type counter would differ per library |
| The scene file format |
Keeps the file's order so an editor's save changes only what was edited; compared with TOML in ../benchmarks/capsule-format.md |
| Signed-distance-field text |
One small atlas per font stays sharp from 12 to 200 pixels (Text.md) |
| GPU particles |
Simulated in compute shaders, with a CPU fallback (particles/design.md) |
Design patterns
| Pattern |
Where |
| Entity Component System |
The whole engine |
| Plugin (with a dependency graph, no cycles) |
Engine features (plugin-*), loaded from shared libraries |
| Abstract factory + registry |
Backends behind contracts (IRenderer, IPlatform, audio): chosen by name in project.luau |
| Mediator / event bus |
ECS events between systems that do not know each other |
| Command |
Commands buffers deferred world changes |
| Result type |
Failures a correct program can hit are returned (Result, expected), misuse throws |
| Producer / consumer queues |
The server's network thread and room threads exchange messages through two queues |