Handles, Not Pointers
Blocks and coins are created above the screen and destroyed after they leave the bottom. That happens several times a second for as long as the game runs.
Storage is a fixed array
A run of any length allocates once at startup, then never again. There is no allocator in the simulation, which is part of how it imports nothing.
Forty-eight slots is more than the field can hold. At the tightest spacing and the highest speed there are about nine rows on screen, with at most three entities each. A test asserts the peak stays under capacity and above six, so a change that quietly stops spawning shows up.
An index is not enough
The obvious way to refer to an entity is its index. That creates the kind of bug you almost never reproduce on purpose.
An event says “coin 12 was collected”. A frame later, slot 12 has been freed and given to a newly spawned block. Anything still holding 12 now reads a block and believes it is a coin. Nothing crashes. The score is just wrong about once an hour, and never while you are looking.
Storing a pointer instead of an index does not help, since the slot is reused either way.
Generational handles
A handle carries the slot index and the generation that slot was on when the handle was made. Freeing a slot bumps its generation, so every handle to the old occupant stops resolving.
pub fn Pool(comptime T: type, comptime capacity_in: u16) type {
return struct {
const Self = @This();
pub const capacity = capacity_in;
pub const Handle = struct {
index: u16,
generation: u32,
/// A handle that never resolves. Generation 0 is never handed out,
/// because live slots start at generation 1.
pub const none: Handle = .{ .index = 0, .generation = 0 };
pub fn eql(a: Handle, b: Handle) bool {
return a.index == b.index and a.generation == b.generation;
}
};
const Slot = struct {
value: T,
/// Odd while the slot is live, even while it is free.
generation: u32,
/// Index of the next free slot, valid only while this one is free.
next_free: u16,
};
slots: [capacity]Slot,
free_head: u16,
live: u16,
pub const empty = init: {
var self: Self = .{
.slots = undefined,
.free_head = 0,
.live = 0,
};
for (&self.slots, 0..) |*slot, i| {
slot.* = .{
.value = undefined,
.generation = 0,
.next_free = @intCast(i + 1),
};
}
break :init self;
};
/// Returns null when the pool is full. Callers decide what a full pool
/// means; the spawner treats it as back-pressure and skips the spawn,
/// which is always safe because the course stays solvable.
pub fn create(self: *Self, value: T) ?Handle {
if (self.free_head >= capacity) return null;
const index = self.free_head;
const slot = &self.slots[index];
self.free_head = slot.next_free;
slot.generation += 1; // even -> odd: now live
slot.value = value;
self.live += 1;
return .{ .index = index, .generation = slot.generation };
}
pub fn destroy(self: *Self, handle: Handle) void {
const slot = self.resolve(handle) orelse return;
slot.generation += 1; // odd -> even: now free
slot.next_free = self.free_head;
self.free_head = handle.index;
self.live -= 1;
}
pub fn get(self: *Self, handle: Handle) ?*T {
const slot = self.resolve(handle) orelse return null;
return &slot.value;
}
pub fn contains(self: *const Self, handle: Handle) bool {
if (handle.index >= capacity) return false;
const slot = &self.slots[handle.index];
return slot.generation == handle.generation and slot.generation % 2 == 1;
}
fn resolve(self: *Self, handle: Handle) ?*Slot {
if (handle.index >= capacity) return null;
const slot = &self.slots[handle.index];
if (slot.generation != handle.generation) return null;
if (slot.generation % 2 == 0) return null;
return slot;
}
pub const Entry = struct { handle: Handle, value: *T };
pub const Iterator = struct {
pool: *Self,
index: u16 = 0,
pub fn next(self: *Iterator) ?Entry {
while (self.index < capacity) {
const i = self.index;
self.index += 1;
const slot = &self.pool.slots[i];
if (slot.generation % 2 == 1) return .{
.handle = .{ .index = i, .generation = slot.generation },
.value = &slot.value,
};
}
return null;
}
};
pub fn iterator(self: *Self) Iterator {
return .{ .pool = self };
}
pub fn clear(self: *Self) void {
var it = self.iterator();
while (it.next()) |entry| self.destroy(entry.handle);
}
};
}The generation is odd while a slot is live and even while it is free. One counter answers both “which occupant” and “is anyone home”. Generation zero is never handed out, so a zeroed handle is a null handle.
create returns an optional rather than asserting. A full pool is not an error
here. The spawner treats it as back pressure and skips that spawn. That is safe
because the course stays solvable either way.
The test names the bug:
test "a stale handle does not resolve to the slot's new occupant" {
var pool: TestPool = .empty;
const old = pool.create(1).?;
pool.destroy(old);
const new = pool.create(2).?;
// The allocator reuses the slot, which is the point of the pool.
try std.testing.expectEqual(old.index, new.index);
// The stale handle must not see the new value.
try std.testing.expect(pool.get(old) == null);
try std.testing.expectEqual(@as(i32, 2), pool.get(new).?.*);
}The first assertion is there to prove the slot really was reused. Without it the test could pass because the pool handed out a fresh slot, which is not the case worth checking.
One pool, two users
The pool is generic because it is general. The particle system uses the same one with a capacity of 256 and a different element type, even though particles belong to the renderer rather than the simulation. Writing it once meant the renderer got fixed-capacity storage with no allocator for free.
Events
The simulation reports what happened. It does not know what anything will do about it.
/// What the simulation did this tick, for the parts of the program that react
/// to it: particles, screen shake, sound. The simulation does not know those
/// exist, which is why adding a sound cannot change the physics.
pub const Event = union(enum) {
started,
lane_changed: struct { from: u8, to: u8 },
coin: struct { x: f32, y: f32, combo: u32, points: u32 },
coin_missed,
near_miss: struct { x: f32, y: f32 },
crashed: struct { x: f32, y: f32 },
};Events accumulate in a fixed buffer, and the caller drains it once per frame. The buffer counts what it had to drop. A test asserts that count is zero across forty thousand ticks. A truncated event stream would show up as occasional missing particles and nothing else.
The whole reaction to a tick is one function:
/// Turn what the simulation reported into what the player sees and feels.
/// Nothing here can change the outcome of the run, which is the point.
fn react(A coin becomes ten amber dots and a small kick of screen shake. A crash becomes debris. None of that is visible to the simulation.
What this split buys
Sound was added after the game was already playable. It changed no rule, because it reads the same events the particles read.
/// The one entry point the game uses. Takes the same events the particles
/// and the screen shake take.
pub fn onEvent(self: *Audio, event: sim.Event) void {
switch (event) {
.coin => |c| {
// The combo ladder, as pitch rather than as eight recordings.
// A semitone is 2^(1/12); this is a little under one per step,
// so a full combo lands about a fifth above where it started.
const step = std.math.pow(f32, 2.0, @as(f32, @floatFromInt(c.combo - 1)) / 14.0);
self.cue(.coin, 0.85, step);
},
.near_miss => self.cue(.near_miss, 0.6, 1),
.lane_changed => self.cue(.lane, 0.5, 1),
.crashed => self.cue(.crash, 1, 1),
.started => self.cue(.start, 0.8, 1),
.coin_missed => {},
}
}Event systems are easy to over-build. Six variants in a tagged union, a fixed buffer and one loop are enough here. The useful question is whether adding a reaction means touching the thing that caused it. Here it does not. The same property lets the difficulty tests run the entire game with no renderer and no audio device.