Algorithms, data structures and storage¶
Entity-Component-System storage¶
The engine models every game object (ship, missile, Bydo, explosion) as an entity: an
id with components (Transform, Velocity, Sprite, Collider, Health...)
processed by systems.
| Approach | Iteration | Add/remove component | Fit |
|---|---|---|---|
Inheritance tree (GameObject → Ship...) |
Virtual call per object, scattered memory | Impossible at runtime | Rigid: a "missile that is also a power-up" needs a new class |
| Archetype ECS (EnTT groups, flecs, Unity DOTS) | Fastest: entities with the same components stored together | Moves the entity between tables | Most complex to write correctly |
| Sparse-set ECS (chosen, planned) | Fast: each component type is a packed array | O(1) add and remove | Simple enough to write, test and explain, fast enough for thousands of entities |
Sparse set: a dense array holds the components contiguously and a sparse array maps an entity index to its position in the dense array. Removal swaps the last element into the hole, so the dense array stays packed and iteration touches only live data. Iterating entities that own several components walks the smallest pool and checks the others in O(1).
Entity ids are 32 bits: a 24-bit index (up to 16 million entities) and an 8-bit generation. Destroyed indices go to a free list and come back with a new generation, so a stale id held by a system is detected instead of silently pointing to another entity.
Collision detection¶
| Approach | Cost per frame | Fit |
|---|---|---|
| Brute force, every pair | O(n²) | Fine below a hundred entities, too slow with missile spam |
| Quadtree | O(n log n), rebuilds as things move | Good for uneven densities; more code and allocations |
| Uniform grid (chosen, planned) | ≈ O(n) | The play area is a fixed rectangle with objects of similar sizes: a fixed grid is the simplest structure with near-linear cost |
The grid is the broad phase (candidate pairs); an axis-aligned bounding box test with layer masks is the narrow phase (enemies ignore enemies, missiles hit only their targets). Tests compare grid results with brute force on random scenes.
Time and simulation¶
- Fixed time step with an accumulator (planned): the simulation advances in steps of exactly 1/60 s whatever the frame rate, so movement, cooldowns and spawns never depend on CPU speed (a subject requirement) and the server and clients compute the same thing. Rendering interpolates between steps.
- Seeded pseudo-random generator on the server (planned): enemy spawns use a seeded PRNG, so a game can be replayed and tested deterministically.
Concurrency¶
- Lock-free SPSC ring buffers (planned) between the network thread and the game thread: one producer, one consumer, a fixed-size array and two atomic indices. No locks, no allocation on the hot path, and the producer never waits on the consumer.
- Typed event bus (planned): systems publish events (
EntityDestroyed,PlayerFired) that other subsystems subscribe to, so audio or visual effects react without gameplay code knowing them (Mediator/Observer pattern, as the subject suggests).
Storage¶
| Data | Format | Why | Alternatives |
|---|---|---|---|
| Client and server settings (ports, window size, key bindings, volumes, accessibility options) | JSON with nlohmann-json (in place as a dependency) | Human-readable, editable by hand, nested structures, one header-only library | INI (too flat for bindings), YAML (heavier parser, whitespace pitfalls), TOML (good, but one more dependency) |
| Enemy waves and levels | JSON data files (planned) | Game designers add waves without recompiling | Lua scripts (more power, more integration work), binary formats (not editable) |
| Sprites and sounds | PNG and WAV/OGG files loaded at runtime (planned) | Standard formats, editable with any tool | Embedding assets in the binary (rebuild for every change) |
| Live game state | In memory only (server) | A game lasts minutes; nothing has to survive a restart | A database would add latency and failure modes for no benefit |
Reliability and constraints (planned)
- Settings files are written to a temporary file and renamed over the old one, so a crash while saving never leaves a half-written file; unknown or invalid values fall back to defaults instead of aborting.
- Data files are validated when loaded (types, ranges, required fields) and rejected with a clear log message, never trusted blindly, the same way network input is.
- Persistent data that would need concurrent access and history (accounts, global scoreboard: Part 2 topics) would move to an embedded database such as SQLite, which adds transactions and crash safety without a server process.