diff options
| author | Gabriel Schneider <[email protected]> | 2026-11-16 21:28:20 -0300 |
|---|---|---|
| committer | Gabriel Schneider <[email protected]> | 2026-11-16 21:28:20 -0300 |
| commit | 6933f99ddb2d7103515d26838496309a807bba26 (patch) | |
| tree | 991c2fe7d4a57957222876e190fa4d16a0fb889c /examples/noc/src/bin_lattice.zig | |
| parent | 82fca5c9f29124f37f6dcd08e73e6999ce44a69d (diff) | |
| download | sketchbook-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.zig | 192 |
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); +} |
