//! 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); }