summaryrefslogtreecommitdiff
path: root/examples/noc/src/bin_lattice.zig
diff options
context:
space:
mode:
authorGabriel Schneider <[email protected]>2026-11-16 21:28:20 -0300
committerGabriel Schneider <[email protected]>2026-11-16 21:28:20 -0300
commit6933f99ddb2d7103515d26838496309a807bba26 (patch)
tree991c2fe7d4a57957222876e190fa4d16a0fb889c /examples/noc/src/bin_lattice.zig
parent82fca5c9f29124f37f6dcd08e73e6999ce44a69d (diff)
downloadsketchbook-6933f99ddb2d7103515d26838496309a807bba26.tar.gz
sketchbook-6933f99ddb2d7103515d26838496309a807bba26.zip
Move standalone sketches into sketchbook examples
Diffstat (limited to 'examples/noc/src/bin_lattice.zig')
-rw-r--r--examples/noc/src/bin_lattice.zig192
1 files changed, 192 insertions, 0 deletions
diff --git a/examples/noc/src/bin_lattice.zig b/examples/noc/src/bin_lattice.zig
new file mode 100644
index 0000000..4766f6c
--- /dev/null
+++ b/examples/noc/src/bin_lattice.zig
@@ -0,0 +1,192 @@
+//! Nature of Code, Example 5.12: Bin-lattice spatial subdivision. The
+//! flocking of 5.11, but each boid looks only at the boids in its own and
+//! the eight surrounding cells of a 40-pixel grid, so 2000 boids cost about
+//! what 200 did with every pair. The shaded cells are the pointer's
+//! neighbourhood; drag to add boids.
+const std = @import("std");
+const sk = @import("sketch");
+const vec = sk.math;
+
+pub const name = "bin_lattice";
+pub const width = 640;
+pub const height = 360;
+
+const max_boids = 4096;
+const resolution = 40;
+const cols = width / resolution;
+const rows = height / resolution;
+
+const Boid = struct {
+ position: vec.Vec,
+ velocity: vec.Vec,
+ const r = 3.0;
+ const maxspeed = 3;
+ const maxforce = 0.05;
+
+ fn init(rng: std.Random, x: f32, y: f32) Boid {
+ return .{ .position = .{ x, y }, .velocity = .{ std.math.lerp(-1, 1, rng.float(f32)), std.math.lerp(-1, 1, rng.float(f32)) } };
+ }
+
+ fn seek(self: *const Boid, target: vec.Vec) vec.Vec {
+ const desired = vec.withLength(target - self.position, maxspeed);
+ return vec.clampLength(desired - self.velocity, maxforce);
+ }
+
+ fn borders(self: *Boid) void {
+ const p = &self.position;
+ if (p[0] < -r) p[0] = width + r;
+ if (p[1] < -r) p[1] = height + r;
+ if (p[0] > width + r) p[0] = -r;
+ if (p[1] > height + r) p[1] = -r;
+ }
+};
+
+/// The bin lattice as a counting sort: boid indices ordered by cell, and
+/// where each cell's run of them starts. Indices, not pointers or per-cell
+/// lists: two fixed arrays that save, scrub and migrate like any other
+/// State. It is derived data, rebuilt from the positions at every step, so
+/// a reload that changes `resolution` (and the array sizes) loses nothing.
+const Grid = struct {
+ /// The boids in cell `c` (row-major) are `order[start[c]..start[c + 1]]`,
+ /// in boid order.
+ start: [cols * rows + 1]u16 = @splat(0),
+ order: [max_boids]u16 = @splat(0),
+
+ /// The cell a boid is binned in; boids just off the edge go in the edge
+ /// cells, as `constrain` does in the original.
+ fn binOf(p: vec.Vec) usize {
+ const col: usize = @intFromFloat(std.math.clamp(@floor(p[0] / resolution), 0, cols - 1));
+ const row: usize = @intFromFloat(std.math.clamp(@floor(p[1] / resolution), 0, rows - 1));
+ return row * cols + col;
+ }
+
+ fn build(g: *Grid, boids: []const Boid) void {
+ @memset(&g.start, 0);
+ for (boids) |b| g.start[binOf(b.position) + 1] += 1;
+ for (1..g.start.len) |c| g.start[c] += g.start[c - 1];
+ var next = g.start;
+ for (boids, 0..) |b, i| {
+ const c = binOf(b.position);
+ g.order[next[c]] = @intCast(i);
+ next[c] += 1;
+ }
+ }
+
+ fn cell(g: *const Grid, col: usize, row: usize) []const u16 {
+ const c = row * cols + col;
+ return g.order[g.start[c]..g.start[c + 1]];
+ }
+};
+
+pub const State = struct {
+ rng: std.Random.Xoshiro256 = .init(512),
+ boids: sk.List(Boid, max_boids) = .{},
+ grid: Grid = .{},
+ clock: sk.Clock = .{},
+};
+
+pub fn init(s: *State) void {
+ const rng = s.rng.random();
+ for (0..2000) |_| {
+ const x = rng.float(f32) * width;
+ const y = rng.float(f32) * height;
+ s.boids.appendBounded(.init(rng, x, y)) catch {};
+ }
+}
+
+pub fn update(s: *State, in: *const sk.Input) void {
+ // mouseDragged: a boid per pointer move with the button down.
+ if (in.buttons & 1 != 0) for (in.events) |e| if (e.kind == .mouse_move) {
+ s.boids.appendBounded(.init(s.rng.random(), e.x, e.y)) catch {};
+ };
+ for (0..s.clock.steps(in)) |_| {
+ // Binned once per step, from where the boids were; each then moves
+ // in turn, seeing the ones before it where they have moved to.
+ const boids = s.boids.slice();
+ s.grid.build(boids);
+ for (boids) |*boid| flock(boid, boids, &s.grid);
+ }
+}
+
+/// flock() + update() + borders() over the 3x3 cells around the boid:
+/// separation, alignment and cohesion summed in one pass over them.
+fn flock(self: *Boid, boids: []const Boid, grid: *const Grid) void {
+ const desired_separation = 25;
+ const neighbor_distance = 50;
+ var away: vec.Vec = .{ 0, 0 };
+ var close: f32 = 0;
+ var velocities: vec.Vec = .{ 0, 0 };
+ var positions: vec.Vec = .{ 0, 0 };
+ var near: f32 = 0;
+ const col: i32 = @intFromFloat(@floor(self.position[0] / resolution));
+ const row: i32 = @intFromFloat(@floor(self.position[1] / resolution));
+ for ([_]i32{ -1, 0, 1 }) |dc| for ([_]i32{ -1, 0, 1 }) |dr| {
+ const c = col + dc;
+ const r = row + dr;
+ if (c < 0 or c >= cols or r < 0 or r >= rows) continue;
+ for (grid.cell(@intCast(c), @intCast(r))) |j| {
+ const other = boids[j];
+ const d = vec.distance(self.position, other.position);
+ if (d > 0 and d < desired_separation) {
+ away += vec.scale(vec.normalize(self.position - other.position), 1 / d);
+ close += 1;
+ }
+ if (d > 0 and d < neighbor_distance) {
+ velocities += other.velocity;
+ positions += other.position;
+ near += 1;
+ }
+ }
+ };
+ var sep: vec.Vec = .{ 0, 0 };
+ if (close > 0) away = vec.scale(away, 1 / close);
+ if (vec.length(away) > 0) sep = vec.clampLength(vec.withLength(away, Boid.maxspeed) - self.velocity, Boid.maxforce);
+ var ali: vec.Vec = .{ 0, 0 };
+ var coh: vec.Vec = .{ 0, 0 };
+ if (near > 0) {
+ ali = vec.clampLength(vec.withLength(vec.scale(velocities, 1 / near), Boid.maxspeed) - self.velocity, Boid.maxforce);
+ coh = self.seek(vec.scale(positions, 1 / near));
+ }
+ self.velocity = vec.clampLength(self.velocity + vec.scale(sep, 1.5) + ali + coh, Boid.maxspeed);
+ self.position += self.velocity;
+ self.borders();
+}
+
+const shape = [_]vec.Vec{ .{ Boid.r * 2, 0 }, .{ -Boid.r * 2, -Boid.r }, .{ -Boid.r * 2, Boid.r } };
+
+/// The grid, the pointer's neighbourhood, then every body in one shape and
+/// every outline in another: four `shape` commands for any number of boids.
+pub fn draw(s: *const State, f: *sk.Frame) void {
+ f.clear(sk.Color.white);
+ var lines: sk.draw.Tessellation = .empty;
+ var cells: sk.draw.Tessellation = .empty;
+ var bodies: sk.draw.Tessellation = .empty;
+ var outlines: sk.draw.Tessellation = .empty;
+ const gpa = f.scratch;
+ for (0..cols + 1) |i| {
+ const x: f32 = @floatFromInt(i * resolution);
+ lines.strokeLine(gpa, .{ x, 0 }, .{ x, height }, 1, .identity) catch return;
+ }
+ for (0..rows + 1) |j| {
+ const y: f32 = @floatFromInt(j * resolution);
+ lines.strokeLine(gpa, .{ 0, y }, .{ width, y }, 1, .identity) catch return;
+ }
+ const mouse_col: i32 = @intFromFloat(@floor(std.math.clamp(f.in.mouse_x, -1e6, 1e6) / resolution));
+ const mouse_row: i32 = @intFromFloat(@floor(std.math.clamp(f.in.mouse_y, -1e6, 1e6) / resolution));
+ for ([_]i32{ -1, 0, 1 }) |dc| for ([_]i32{ -1, 0, 1 }) |dr| {
+ const c = mouse_col + dc;
+ const r = mouse_row + dr;
+ if (c < 0 or c >= cols or r < 0 or r >= rows) continue;
+ const rect: vec.Rect = .{ .x = @floatFromInt(c * resolution), .y = @floatFromInt(r * resolution), .w = resolution, .h = resolution };
+ cells.fillRect(gpa, rect, .identity) catch return;
+ };
+ for (s.boids.constSlice()) |boid| {
+ const xf: vec.Affine = .place(boid.position, vec.angle(boid.velocity));
+ bodies.fillPolygon(gpa, &shape, xf) catch break;
+ outlines.strokePolygon(gpa, &shape, 1, xf) catch break;
+ }
+ f.shape(&lines, .gray(200));
+ f.shape(&cells, sk.Color.hex(0xff3232).alpha(100));
+ f.shape(&bodies, .gray(127));
+ f.shape(&outlines, .black);
+}