herd / commit
Add Boids flocking AI with flee, boundary, and collision resolution
src/ai/Boids.ts | 224 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 224 insertions(+) diff --git a/src/ai/Boids.ts b/src/ai/Boids.ts new file mode 100644 index 0000000..e2dcc65 --- /dev/null +++ b/src/ai/Boids.ts @@ -0,0 +1,224 @@ +import { Vec2 } from '../math/Vec2.ts' +import type { Sheep } from '../entities/Sheep.ts' +import type { Dog } from '../entities/Dog.ts' +import type { Pen } from '../entities/Pen.ts' + +// ─── Tuning constants ──────────────────────────────────────────────────────── +// Radii in world pixels, speeds in px/s, forces in px/s² + +const SEPARATION_RADIUS_SQ = 35 * 35 +const ALIGN_RADIUS_SQ = 80 * 80 +const COHESION_RADIUS_SQ = 100 * 100 +const LONG_RANGE_RADIUS_SQ = 300 * 300 // beyond cohesion — lone sheep spot a distant group + +const FLEE_RADIUS = 220 // sheep start reacting at this distance +const FLEE_RADIUS_SQ = FLEE_RADIUS * FLEE_RADIUS + +// Flee formula is LINEAR: full W_FLEE at d=0, zero at FLEE_RADIUS. +// This gives a smooth, readable gradient — sheep visibly start moving when the +// dog enters range, not only when it's almost on top of them. +const W_FLEE = 80 + +const W_SEPARATION = 30 +const W_ALIGNMENT = 12 +const W_COHESION = 12 +const W_LONG_RANGE = 5 // gentle pull toward a distant group +const W_PEN = 3 + +// MAX_FORCE controls how fast sheep accelerate. At dt=16ms: +// velocity gain per tick = MAX_FORCE * 0.016 +// time to reach MAX_SPEED = MAX_SPEED / MAX_FORCE ≈ 0.9 s at these values +const MAX_SPEED = 90 // px/s (panic multiplier can push this up to ~162) +const MAX_FORCE = 100 // px/s² — previous value of 6 meant ~15 s to full speed + +const FEAR_DECAY = 0.95 // per fixed tick (~60 Hz) + +// Wall repulsion: quadratic, peaks at BOUNDARY_PEAK right at the wall +const BOUNDARY_MARGIN = 90 +const BOUNDARY_PEAK = 140 // must exceed flee force near wall + +// Stubborn sheep: smaller flee radius so they require close, sustained pressure +const STUBBORN_FLEE_RADIUS = 100 +const STUBBORN_FLEE_RADIUS_SQ = STUBBORN_FLEE_RADIUS * STUBBORN_FLEE_RADIUS +const STUBBORN_COHESION_WEIGHT = 0.15 // relative to W_COHESION + +// Leader sheep: others weight their position/velocity more heavily +const LEADER_NEIGHBOR_WEIGHT = 3.0 + +// ─── Helpers ───────────────────────────────────────────────────────────────── + +interface Obstacle { x: number; y: number; r: number } + +function wallPush(dist: number): number { + if (dist >= BOUNDARY_MARGIN) return 0 + const t = 1 - dist / BOUNDARY_MARGIN + return t * t * BOUNDARY_PEAK +} + +const SHEEP_RADIUS = 9 // must match Sheep.draw arc radius +const MIN_SHEEP_DIST = SHEEP_RADIUS * 2 + +// ─── Main update ───────────────────────────────────────────────────────────── + +export function updateBoids( + sheep: Sheep[], + dog: Dog, + pen: Pen, + canvasW: number, + canvasH: number, + obstacles: Obstacle[], + dt: number, + speedMult = 1, +) { + const OBSTACLE_MARGIN = 20 + const WALL = 10 + + for (const s of sheep) { + const fleeRadius = s.stubborn ? STUBBORN_FLEE_RADIUS : FLEE_RADIUS + const fleeRadiusSq = s.stubborn ? STUBBORN_FLEE_RADIUS_SQ : FLEE_RADIUS_SQ + const cohesionScale = s.stubborn ? STUBBORN_COHESION_WEIGHT : 1.0 + + // ── neighbor scan ────────────────────────────────────────────────────── + let sepForce = Vec2.ZERO + let alignSum = Vec2.ZERO + let cohSum = Vec2.ZERO + let longRangeSum = Vec2.ZERO + let sepCount = 0 + let alignCount = 0 + let cohCount = 0 + let longRangeCount = 0 + + for (const other of sheep) { + if (other === s) continue + const dSq = s.pos.distanceSqTo(other.pos) + + // sub-flock repulsion: different groups push apart harder (Two Tribes) + const sepWeight = other.subFlock === s.subFlock ? 1.0 : 3.0 + + if (dSq < SEPARATION_RADIUS_SQ) { + const away = s.pos.sub(other.pos).normalize().scale(1 / Math.sqrt(dSq + 0.01)) + sepForce = sepForce.add(away.scale(sepWeight)) + sepCount++ + } + + // leaders pull neighbors more strongly in alignment and cohesion + const nWeight = other.leader ? LEADER_NEIGHBOR_WEIGHT : 1.0 + + if (dSq < ALIGN_RADIUS_SQ) { + alignSum = alignSum.add(other.vel.scale(nWeight)) + alignCount++ + } + if (dSq < COHESION_RADIUS_SQ) { + cohSum = cohSum.add(other.pos.scale(nWeight)) + cohCount++ + } else if (dSq < LONG_RANGE_RADIUS_SQ) { + // outside normal cohesion but visible at long range — contribute to + // the distant-group centroid (leaders count more here too) + longRangeSum = longRangeSum.add(other.pos.scale(nWeight)) + longRangeCount++ + } + } + + let steering = Vec2.ZERO + + if (sepCount > 0) + steering = steering.add(sepForce.normalize().scale(W_SEPARATION)) + + if (alignCount > 0) + steering = steering.add(alignSum.scale(1 / alignCount).normalize().scale(W_ALIGNMENT)) + + if (cohCount > 0) { + const centroid = cohSum.scale(1 / cohCount) + steering = steering.add(centroid.sub(s.pos).normalize().scale(W_COHESION * cohesionScale)) + } else if (longRangeCount > 0) { + // no nearby flock — pull toward the distant group centroid instead. + // only fires when cohesion has no neighbors, so it doesn't fight close-range flocking. + const distant = longRangeSum.scale(1 / longRangeCount) + steering = steering.add(distant.sub(s.pos).normalize().scale(W_LONG_RANGE)) + } + + // ── dog flee (linear gradient across flee radius) ───────────────────── + const dogDSq = s.pos.distanceSqTo(dog.pos) + if (dogDSq < fleeRadiusSq) { + const dogD = Math.sqrt(dogDSq) + const gradient = 1 - dogD / fleeRadius // 1 at dog, 0 at flee radius edge + steering = steering.add( + s.pos.sub(dog.pos).normalize().scale(W_FLEE * gradient) + ) + s.fearLevel = Math.min(1, s.fearLevel + 0.12) + } else { + s.fearLevel *= FEAR_DECAY + } + + // ── boundary repulsion (quadratic, peaks at BOUNDARY_PEAK) ─────────── + steering = steering.add(new Vec2( + wallPush(s.pos.x) - wallPush(canvasW - s.pos.x), + wallPush(s.pos.y) - wallPush(canvasH - s.pos.y), + )) + + // ── obstacle repulsion ──────────────────────────────────────────────── + for (const obs of obstacles) { + const ov = s.pos.sub(new Vec2(obs.x, obs.y)) + const dist = ov.length() + const effectiveR = obs.r + OBSTACLE_MARGIN + 10 + if (dist < effectiveR && dist > 0) { + const strength = (effectiveR - dist) / effectiveR * W_SEPARATION + steering = steering.add(ov.normalize().scale(strength)) + } + } + + // ── weak pen attraction ─────────────────────────────────────────────── + steering = steering.add(pen.center().sub(s.pos).normalize().scale(W_PEN)) + + // ── apply ───────────────────────────────────────────────────────────── + const panicMult = 1 + s.fearLevel * 0.8 + steering = steering.limit(MAX_FORCE * panicMult) + + // Friction: calm sheep (fearLevel≈0) decelerate to a stop quickly; + // frightened sheep retain momentum so they keep running after the dog passes. + // 0.88^60 ≈ 0.06% of speed after 1 s when calm → effectively stopped. + // 0.97^60 ≈ 16% after 1 s when fully scared → gradual coast. + const friction = 0.88 + s.fearLevel * 0.09 + s.vel = s.vel.scale(friction) + + s.vel = s.vel.add(steering.scale(dt)) + s.vel = s.vel.limit(MAX_SPEED * panicMult * speedMult) + s.pos = s.pos.add(s.vel.scale(dt)) + + // hard wall — reflect the inward velocity component + let vx = s.vel.x, vy = s.vel.y + let px = s.pos.x, py = s.pos.y + if (px < WALL) { px = WALL; if (vx < 0) vx = -vx * 0.4 } + if (px > canvasW - WALL) { px = canvasW - WALL; if (vx > 0) vx = -vx * 0.4 } + if (py < WALL) { py = WALL; if (vy < 0) vy = -vy * 0.4 } + if (py > canvasH - WALL) { py = canvasH - WALL; if (vy > 0) vy = -vy * 0.4 } + s.pos = new Vec2(px, py) + s.vel = new Vec2(vx, vy) + + if (s.vel.lengthSq() > 1) { + const target = Math.atan2(s.vel.y, s.vel.x) + let diff = target - s.facing + if (diff > Math.PI) diff -= Math.PI * 2 + if (diff < -Math.PI) diff += Math.PI * 2 + s.facing += diff * 0.2 + } + } + + // ── positional collision resolution ────────────────────────────────────── + // Runs after all sheep have moved. Pushes overlapping sheep apart by the + // overlap amount so they never visually intersect. O(n²) but n ≤ 30. + for (let i = 0; i < sheep.length; i++) { + for (let j = i + 1; j < sheep.length; j++) { + const a = sheep[i]! + const b = sheep[j]! + const diff = a.pos.sub(b.pos) + const distSq = diff.lengthSq() + if (distSq < MIN_SHEEP_DIST * MIN_SHEEP_DIST && distSq > 0) { + const dist = Math.sqrt(distSq) + const push = diff.scale((MIN_SHEEP_DIST - dist) / dist * 0.5) + a.pos = a.pos.add(push) + b.pos = b.pos.sub(push) + } + } + } +}