1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
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);
}
|