fuzzyworld

herd / files / src / ai / Boids.ts

Boids.ts

Blame: the commit that last changed each line · file · history

5dab649a 2026-05-17 Pavel Safronov1import { Vec2 } from '../math/Vec2.ts'
2import type { Sheep } from '../entities/Sheep.ts'
3import type { Dog } from '../entities/Dog.ts'
4import type { Pen } from '../entities/Pen.ts'
5
21437a01 2026-05-18 Pavel Safronov6// ─── Base tuning constants (at reference scale = 1) ─────────────────────────
7// Radii in world pixels, speeds in px/s, forces in px/s².
8// All physical values are multiplied by the runtime `scale` factor inside
9// updateBoids so the game feels identical across screen sizes.
5dab649a 2026-05-17 Pavel Safronov10
21437a01 2026-05-18 Pavel Safronov11const BASE_SEPARATION_RADIUS = 35
12const BASE_ALIGN_RADIUS = 80
13const BASE_COHESION_RADIUS = 100
14const BASE_LONG_RANGE_RADIUS = 300 // beyond cohesion — lone sheep spot a distant group
5dab649a 2026-05-17 Pavel Safronov15
21437a01 2026-05-18 Pavel Safronov16const BASE_FLEE_RADIUS = 220 // sheep start reacting at this distance
5dab649a 2026-05-17 Pavel Safronov17
18// Flee formula is LINEAR: full W_FLEE at d=0, zero at FLEE_RADIUS.
21437a01 2026-05-18 Pavel Safronov19const BASE_W_FLEE = 80
20const BASE_W_SEPARATION = 30
21const BASE_W_ALIGNMENT = 12
22const BASE_W_COHESION = 12
23const BASE_W_LONG_RANGE = 5 // gentle pull toward a distant group
24const BASE_W_PEN = 3
5dab649a 2026-05-17 Pavel Safronov25
26// MAX_FORCE controls how fast sheep accelerate. At dt=16ms:
27// velocity gain per tick = MAX_FORCE * 0.016
28// time to reach MAX_SPEED = MAX_SPEED / MAX_FORCE ≈ 0.9 s at these values
21437a01 2026-05-18 Pavel Safronov29const BASE_MAX_SPEED = 90 // px/s (panic multiplier can push this up to ~162)
30const BASE_MAX_FORCE = 100 // px/s²
5dab649a 2026-05-17 Pavel Safronov31
21437a01 2026-05-18 Pavel Safronov32const FEAR_DECAY = 0.95 // per fixed tick (~60 Hz) — dimensionless, no scaling
5dab649a 2026-05-17 Pavel Safronov33
34// Wall repulsion: quadratic, peaks at BOUNDARY_PEAK right at the wall
21437a01 2026-05-18 Pavel Safronov35const BASE_BOUNDARY_MARGIN = 90
36const BASE_BOUNDARY_PEAK = 140 // must exceed flee force near wall
5dab649a 2026-05-17 Pavel Safronov37
38// Stubborn sheep: smaller flee radius so they require close, sustained pressure
21437a01 2026-05-18 Pavel Safronov39const BASE_STUBBORN_FLEE_RADIUS = 100
40const STUBBORN_COHESION_WEIGHT = 0.15 // relative to W_COHESION — dimensionless
5dab649a 2026-05-17 Pavel Safronov41
42// Leader sheep: others weight their position/velocity more heavily
21437a01 2026-05-18 Pavel Safronov43const LEADER_NEIGHBOR_WEIGHT = 3.0 // dimensionless
44
45const BASE_SHEEP_RADIUS = 9 // must match Sheep.draw arc radius
5dab649a 2026-05-17 Pavel Safronov46
47// ─── Helpers ─────────────────────────────────────────────────────────────────
48
49interface Obstacle { x: number; y: number; r: number }
50
21437a01 2026-05-18 Pavel Safronov51function wallPush(dist: number, margin: number, peak: number): number {
52 if (dist >= margin) return 0
53 const t = 1 - dist / margin
54 return t * t * peak
5dab649a 2026-05-17 Pavel Safronov55}
56
57// ─── Main update ─────────────────────────────────────────────────────────────
58
59export function updateBoids(
60 sheep: Sheep[],
61 dog: Dog,
62 pen: Pen,
63 canvasW: number,
64 canvasH: number,
65 obstacles: Obstacle[],
66 dt: number,
67 speedMult = 1,
21437a01 2026-05-18 Pavel Safronov68 scale = 1,
5dab649a 2026-05-17 Pavel Safronov69) {
21437a01 2026-05-18 Pavel Safronov70 // Derive all physical constants for this screen scale.
71 const SHEEP_RADIUS = BASE_SHEEP_RADIUS * scale
72 const MIN_SHEEP_DIST = SHEEP_RADIUS * 2
73 const SEPARATION_RADIUS_SQ = (BASE_SEPARATION_RADIUS * scale) ** 2
74 const ALIGN_RADIUS_SQ = (BASE_ALIGN_RADIUS * scale) ** 2
75 const COHESION_RADIUS_SQ = (BASE_COHESION_RADIUS * scale) ** 2
76 const LONG_RANGE_RADIUS_SQ = (BASE_LONG_RANGE_RADIUS * scale) ** 2
77 const FLEE_RADIUS = BASE_FLEE_RADIUS * scale
78 const FLEE_RADIUS_SQ = FLEE_RADIUS ** 2
79 const STUBBORN_FLEE_RADIUS = BASE_STUBBORN_FLEE_RADIUS * scale
80 const STUBBORN_FLEE_RADIUS_SQ = STUBBORN_FLEE_RADIUS ** 2
81 const W_FLEE = BASE_W_FLEE * scale
82 const W_SEPARATION = BASE_W_SEPARATION * scale
83 const W_ALIGNMENT = BASE_W_ALIGNMENT * scale
84 const W_COHESION = BASE_W_COHESION * scale
85 const W_LONG_RANGE = BASE_W_LONG_RANGE * scale
86 const W_PEN = BASE_W_PEN * scale
87 const MAX_SPEED = BASE_MAX_SPEED * scale
88 const MAX_FORCE = BASE_MAX_FORCE * scale
89 const BOUNDARY_MARGIN = BASE_BOUNDARY_MARGIN * scale
90 const BOUNDARY_PEAK = BASE_BOUNDARY_PEAK * scale
91 const OBSTACLE_MARGIN = 20 * scale
92 const WALL = 10 * scale
5dab649a 2026-05-17 Pavel Safronov93
94 for (const s of sheep) {
95 const fleeRadius = s.stubborn ? STUBBORN_FLEE_RADIUS : FLEE_RADIUS
96 const fleeRadiusSq = s.stubborn ? STUBBORN_FLEE_RADIUS_SQ : FLEE_RADIUS_SQ
97 const cohesionScale = s.stubborn ? STUBBORN_COHESION_WEIGHT : 1.0
98
99 // ── neighbor scan ──────────────────────────────────────────────────────
100 let sepForce = Vec2.ZERO
101 let alignSum = Vec2.ZERO
102 let cohSum = Vec2.ZERO
103 let longRangeSum = Vec2.ZERO
104 let sepCount = 0
105 let alignCount = 0
106 let cohCount = 0
107 let longRangeCount = 0
108
109 for (const other of sheep) {
110 if (other === s) continue
111 const dSq = s.pos.distanceSqTo(other.pos)
112
113 // sub-flock repulsion: different groups push apart harder (Two Tribes)
114 const sepWeight = other.subFlock === s.subFlock ? 1.0 : 3.0
115
116 if (dSq < SEPARATION_RADIUS_SQ) {
117 const away = s.pos.sub(other.pos).normalize().scale(1 / Math.sqrt(dSq + 0.01))
118 sepForce = sepForce.add(away.scale(sepWeight))
119 sepCount++
120 }
121
122 // leaders pull neighbors more strongly in alignment and cohesion
123 const nWeight = other.leader ? LEADER_NEIGHBOR_WEIGHT : 1.0
124
125 if (dSq < ALIGN_RADIUS_SQ) {
126 alignSum = alignSum.add(other.vel.scale(nWeight))
127 alignCount++
128 }
129 if (dSq < COHESION_RADIUS_SQ) {
130 cohSum = cohSum.add(other.pos.scale(nWeight))
131 cohCount++
132 } else if (dSq < LONG_RANGE_RADIUS_SQ) {
133 // outside normal cohesion but visible at long range — contribute to
134 // the distant-group centroid (leaders count more here too)
135 longRangeSum = longRangeSum.add(other.pos.scale(nWeight))
136 longRangeCount++
137 }
138 }
139
140 let steering = Vec2.ZERO
141
142 if (sepCount > 0)
143 steering = steering.add(sepForce.normalize().scale(W_SEPARATION))
144
145 if (alignCount > 0)
146 steering = steering.add(alignSum.scale(1 / alignCount).normalize().scale(W_ALIGNMENT))
147
148 if (cohCount > 0) {
149 const centroid = cohSum.scale(1 / cohCount)
150 steering = steering.add(centroid.sub(s.pos).normalize().scale(W_COHESION * cohesionScale))
151 } else if (longRangeCount > 0) {
152 // no nearby flock — pull toward the distant group centroid instead.
153 // only fires when cohesion has no neighbors, so it doesn't fight close-range flocking.
154 const distant = longRangeSum.scale(1 / longRangeCount)
155 steering = steering.add(distant.sub(s.pos).normalize().scale(W_LONG_RANGE))
156 }
157
158 // ── dog flee (linear gradient across flee radius) ─────────────────────
3ccad7d4 2026-05-18 Pavel Safronov159 // Sheep inside the pen ignore the dog — they've been herded and should
160 // stay calm. Fear decays normally so their eyes return to normal.
5dab649a 2026-05-17 Pavel Safronov161 const dogDSq = s.pos.distanceSqTo(dog.pos)
3ccad7d4 2026-05-18 Pavel Safronov162 if (!pen.contains(s.pos) && dogDSq < fleeRadiusSq) {
5dab649a 2026-05-17 Pavel Safronov163 const dogD = Math.sqrt(dogDSq)
164 const gradient = 1 - dogD / fleeRadius // 1 at dog, 0 at flee radius edge
165 steering = steering.add(
166 s.pos.sub(dog.pos).normalize().scale(W_FLEE * gradient)
167 )
168 s.fearLevel = Math.min(1, s.fearLevel + 0.12)
169 } else {
170 s.fearLevel *= FEAR_DECAY
171 }
172
173 // ── boundary repulsion (quadratic, peaks at BOUNDARY_PEAK) ───────────
174 steering = steering.add(new Vec2(
21437a01 2026-05-18 Pavel Safronov175 wallPush(s.pos.x, BOUNDARY_MARGIN, BOUNDARY_PEAK) - wallPush(canvasW - s.pos.x, BOUNDARY_MARGIN, BOUNDARY_PEAK),
176 wallPush(s.pos.y, BOUNDARY_MARGIN, BOUNDARY_PEAK) - wallPush(canvasH - s.pos.y, BOUNDARY_MARGIN, BOUNDARY_PEAK),
5dab649a 2026-05-17 Pavel Safronov177 ))
178
179 // ── obstacle repulsion ────────────────────────────────────────────────
180 for (const obs of obstacles) {
181 const ov = s.pos.sub(new Vec2(obs.x, obs.y))
182 const dist = ov.length()
183 const effectiveR = obs.r + OBSTACLE_MARGIN + 10
184 if (dist < effectiveR && dist > 0) {
185 const strength = (effectiveR - dist) / effectiveR * W_SEPARATION
186 steering = steering.add(ov.normalize().scale(strength))
187 }
188 }
189
c4a1cdd1 2026-05-18 Pavel Safronov190 // ── pen attraction (outside) / retention (inside) ────────────────────
191 if (pen.contains(s.pos)) {
192 // Inside: repel from all four walls so sheep stay put even when spooked.
193 // Peak is 3× max flee force so it dominates regardless of fear level.
194 const PEN_MARGIN = 22 * scale
195 const PEN_PEAK = 240 * scale
196 const dLeft = s.pos.x - pen.x
197 const dRight = (pen.x + pen.w) - s.pos.x
198 const dTop = s.pos.y - pen.y
199 const dBottom = (pen.y + pen.h) - s.pos.y
200 steering = steering.add(new Vec2(
201 wallPush(dLeft, PEN_MARGIN, PEN_PEAK) - wallPush(dRight, PEN_MARGIN, PEN_PEAK),
202 wallPush(dTop, PEN_MARGIN, PEN_PEAK) - wallPush(dBottom, PEN_MARGIN, PEN_PEAK),
203 ))
204 } else {
205 // Outside: gentle pull toward pen center to encourage herding.
206 steering = steering.add(pen.center().sub(s.pos).normalize().scale(W_PEN))
207 }
5dab649a 2026-05-17 Pavel Safronov208
209 // ── apply ─────────────────────────────────────────────────────────────
210 const panicMult = 1 + s.fearLevel * 0.8
211 steering = steering.limit(MAX_FORCE * panicMult)
212
213 // Friction: calm sheep (fearLevel≈0) decelerate to a stop quickly;
214 // frightened sheep retain momentum so they keep running after the dog passes.
215 // 0.88^60 ≈ 0.06% of speed after 1 s when calm → effectively stopped.
216 // 0.97^60 ≈ 16% after 1 s when fully scared → gradual coast.
217 const friction = 0.88 + s.fearLevel * 0.09
218 s.vel = s.vel.scale(friction)
219
220 s.vel = s.vel.add(steering.scale(dt))
221 s.vel = s.vel.limit(MAX_SPEED * panicMult * speedMult)
222 s.pos = s.pos.add(s.vel.scale(dt))
223
224 // hard wall — reflect the inward velocity component
225 let vx = s.vel.x, vy = s.vel.y
226 let px = s.pos.x, py = s.pos.y
227 if (px < WALL) { px = WALL; if (vx < 0) vx = -vx * 0.4 }
228 if (px > canvasW - WALL) { px = canvasW - WALL; if (vx > 0) vx = -vx * 0.4 }
229 if (py < WALL) { py = WALL; if (vy < 0) vy = -vy * 0.4 }
230 if (py > canvasH - WALL) { py = canvasH - WALL; if (vy > 0) vy = -vy * 0.4 }
231 s.pos = new Vec2(px, py)
232 s.vel = new Vec2(vx, vy)
233
234 if (s.vel.lengthSq() > 1) {
235 const target = Math.atan2(s.vel.y, s.vel.x)
236 let diff = target - s.facing
237 if (diff > Math.PI) diff -= Math.PI * 2
238 if (diff < -Math.PI) diff += Math.PI * 2
239 s.facing += diff * 0.2
240 }
241 }
242
243 // ── positional collision resolution ──────────────────────────────────────
244 // Runs after all sheep have moved. Pushes overlapping sheep apart by the
245 // overlap amount so they never visually intersect. O(n²) but n ≤ 30.
246 for (let i = 0; i < sheep.length; i++) {
247 for (let j = i + 1; j < sheep.length; j++) {
248 const a = sheep[i]!
249 const b = sheep[j]!
250 const diff = a.pos.sub(b.pos)
251 const distSq = diff.lengthSq()
252 if (distSq < MIN_SHEEP_DIST * MIN_SHEEP_DIST && distSq > 0) {
253 const dist = Math.sqrt(distSq)
254 const push = diff.scale((MIN_SHEEP_DIST - dist) / dist * 0.5)
255 a.pos = a.pos.add(push)
256 b.pos = b.pos.sub(push)
257 }
258 }
259 }
260}