2b:null 2c:["$","title",null,{"children":"The Nature of Code - 5 - Autonomous Agents | Adam Jurczyk | Observable"}] 31:T4db,# The Nature of Code - 5 - Autonomous Agents _Deeper into dynamic code, with https://natureofcode.com/ _ This notebook follows fourth chapter https://natureofcode.com/autonomous-agents/ > _An autonomous agent is an entity that makes its own choices about how to act in its environment, without any influence from a leader or global plan. In this book, acting typically means moving. For example, instead of simulating a particle that’s passively drawn toward or repelled by another shape because of a force like gravity, I’d now like to design an entity that has the ability—or even the “desire”—to make decisions about its movements. It could decide to move toward or away from a target, like a moth drawn to a flame or a small fish evading a predator._ Here are three key components of autonomous agents to keep in mind: * **An autonomous agent has a limited ability to perceive its environment.** Where _environment_ is understand not only as an external "world" state, but also agent's internal state. * **An autonomous agent processes the information from its environment and calculates an action.** Here action will mostly mean some force. * **An autonomous agent has no leader.** At least for most of the examples here.32:T7d5,/** sparce 2d grid allowing for infinite and negative indexes */ class InfiniField { // to make it easier for myself, i consider this grid to be divided on 4 regions on screen coords // (but screen like, so y axis grows to bottom) #regionsSigns = [ [0, 0], [-1, 0], [-1, -1], [0, -1] ]; #regions; constructor(resolutionX = 1, resolutionY) { // resolution makes it easier to map pixel dimensions to smaller grids this.resX = resolutionX; this.resY = resolutionY || resolutionX; this.reset(); } getAt({ x, y }) { return this.get(Math.floor(x / this.resX), Math.floor(y / this.resY)); } setAt({ x, y }, val) { return this.set(Math.floor(x / this.resX), Math.floor(y / this.resY), val); } #getRegSign(n) { return Math.sign(n - Math.abs(n)); } #getRegColRow(col, row) { const colS = this.#getRegSign(col); const rowS = this.#getRegSign(row); const reg = this.#regions[`${rowS},${colS}`]; if (!reg) throw new Error(`no region found ${rowS},${rowS}`); return [reg, Math.abs(col) + colS, Math.abs(row) + rowS]; } get(col, row) { const [reg, c, r] = this.#getRegColRow(col, row); return reg?.[r]?.[c]; } set(col, row, val) { const [reg, c, r] = this.#getRegColRow(col, row); if (reg[r] === undefined) reg[r] = []; reg[r][c] = val; return this; } reset() { this.#regions = Object.fromEntries( this.#regionsSigns.map((a) => [a.join(","), []]) ); } getCellPos(col, row) { return vec2(col * this.resX, row * this.resY); } getCellCenter(col, row) { return vec2((col + 0.5) * this.resX, (row + 0.5) * this.resY); } *iterator() { for (const [rowS, colS] of this.#regionsSigns) { const reg = this.#regions[`${rowS},${colS}`]; for (let row = 0; row < reg.length; ++row) { for (let col = 0; col < reg[row].length; ++col) { yield [reg[row][col], vec2(col, row), this.getCellCenter(col, row)]; } } } } }33:T515,{ const height = followFlowFieldSpec.height; const ff = flowField( { res: followFlowFieldSpec.res, gen: ({ x, y }) => vec2(1, 0).rotateAround( vec2.ZERO, MathUtils.lerp( 0, TWO_PI, noise2D(x * followFlowFieldSpec.dt, y * followFlowFieldSpec.dt) - 0.5 ) ) }, tag("changeFlowOnClick") ); const createVehicle = () => { const maxSpeed = random(...followFlowFieldSpec.smaxR); const maxForce = random(...followFlowFieldSpec.fmaxR); const [smaxMin, smaxMax] = followFlowFieldSpec.smaxR; const clr = tinycolor("#f3fa").spin( MathUtils.mapLinear(maxSpeed, ...followFlowFieldSpec.smaxR, -100, 0) ); return vehicle( { pos: vec2(random(0, width), random(0, height)), fill: clr, maxSpeed, maxForce }, force(vec2().random()), onStageExit("wrap"), followFlow(ff) ); }; return sim({ width, height: height, visibility, systems: [ changeFlowOnClickSys, followFlowSys, angularMovement, movement, onStageExitSys, renderer ], entities: [ ff, ...Array.from({ length: followFlowFieldSpec.vnum }, createVehicle) ] }); }34:T4ed,{ const height = 700; const ff = flowField( { res: 5, gen: ({ x, y }) => vec2(1, 0).rotateAround( vec2.ZERO, MathUtils.lerp(0, TWO_PI, noise2D(x * 0.02, y * 0.02) - 0.5) ) }, hidden, changeFlowInTime(0.00005) ); return sim({ width, height: height, visibility, clearCanvas: false, pauseOnClick: true, bgColor: "#11002c", systems: [ changeFlowInTimeSys, followFlowSys, angularMovement, movement, onStageExitSys, (env) => { env.ctx.fillStyle = "#11002c06"; env.ctx.fillRect(0, 0, width, height); }, renderer, showStats ], entities: [ ff, ...Array.from({ length: 10000 }, () => vehicle( { pos: vec2(random(0, width), random(0, height)), maxSpeed: random(1, 2), maxForce: random(0.01, 0.03) }, force(vec2().random()), onStageExit("wrap"), followFlow(ff), graphics({ lineWidth: 0, draw: (ctx, { rect }) => { ctx.fillStyle = "#f2448940"; ctx.fillRect(0, 0, 1, 1); } }) ) ) ] }); }35:T42b,justCanvas({ width, visibility }, (ctx, { height, mouse }) => { const center = vec2(width / 2, height / 2); const v0 = vec2(100, 0); const v1 = v0.clone(); if (mouse.pos) { const mousePos = mouse.pos.clone().sub(center); v1.copy(mousePos).setLength(100); } ctx.clearRect(0, 0, width, height); ctx.save(); ctx.lineWidth = 5; ctx.lineCap = "round"; ctx.translate(width / 2, height / 2); ctx.strokeStyle = "#000000"; ctx.beginPath(); ctx.moveTo(0, 0); ctx.lineTo(v0.x, v0.y); ctx.stroke(); ctx.strokeStyle = "#990000"; ctx.beginPath(); ctx.moveTo(0, 0); ctx.lineTo(v1.x, v1.y); ctx.stroke(); let angle = Math.acos(v0.dot(v1) / (v0.length() * v1.length())); if (v1.y < 0) { angle = -angle; } ctx.lineWidth = 1; ctx.lineCap = "butt"; ctx.beginPath(); ctx.arc(0, 0, 20, 0, angle, angle < 0); ctx.stroke(); ctx.restore(); ctx.fillText(`angle: ${angle}`, 10, 250); ctx.fillText(`angle deg: ${angle * (180 / PI)}`, 10, 260); ctx.fillText(`Vector2.angleTo: ${v0.angleTo(v1)}`, 10, 270); })36:T571,drawPath = (ctx, { position, path, graphics, circle }) => { ctx.lineCap = "round"; ctx.lineJoin = "round"; ctx.lineWidth = path.radius * 2; ctx.strokeStyle = graphics.fillColor; ctx.beginPath(); ctx.moveTo(0, 0); for (const v of path.vertices) { ctx.lineTo(v.x, v.y); } ctx.stroke(); ctx.lineWidth = graphics.lineWidth; ctx.strokeStyle = graphics.lineColor; ctx.beginPath(); ctx.moveTo(0, 0); for (const v of path.vertices) { ctx.lineTo(v.x, v.y); } ctx.stroke(); if (path.editable) { const printPos = (v, atPos = null) => { const at = atPos ?? v; ctx.fillText( `${Math.round(v.x)},${Math.round(v.y)}`, at.x + circle.radius, at.y - circle.radius ); }; ctx.fillStyle = "#f00"; ctx.beginPath(); ctx.arc(0, 0, circle.radius, 0, TWO_PI); ctx.fill(); printPos(position, vec2.ZERO); ctx.fillStyle = "#0b0"; ctx.beginPath(); const marker = path.vertices[1].clone().negate().setLength(path.radius); ctx.arc(marker.x, marker.y, circle.radius, 0, TWO_PI); ctx.fill(); const vlen = path.vertices.length - (path.closed ? 1 : 0); for (let i = 1; i < vlen; ++i) { ctx.fillStyle = "#00f"; ctx.beginPath(); ctx.arc(path.vertices[i].x, path.vertices[i].y, circle.radius, 0, TWO_PI); ctx.fill(); printPos(path.vertices[i]); } } }37:T1026,pathEditingSys = (env, ents) => { if (env.__dragging?.type === "pathVertex") { env.mouse.handled = true; const { ent, vert, vertStart, start } = env.__dragging; if (!env.mouse.down || !ent || !vert || !vertStart || !start) { delete env.__dragging; } else { const move = env.mouse.pos.clone().sub(start); vert.copy(move.add(vertStart)); } return; } if (env.__dragging?.type === "pathRadius") { env.mouse.handled = true; const { ent, r, baseDist } = env.__dragging; if (!env.mouse.down || !ent) { delete env.__dragging; } else { const curDist = env.mouse.pos.distanceTo(ent.position); const distDiff = curDist - baseDist; ent.path.radius = r + distDiff; } return; } if (!env.__dragging && env.mouse.pos && !env.mouse.handled) { for (let i = ents.length - 1; i >= 0; --i) { const ent = ents[i]; if (!ent.position || !ent.path?.editable || !ent.circle?.radius) { continue; } const localMouse = vec2().subVectors(env.mouse.pos, ent.position); const verts = ent.path.vertices; let pathMouseNormal; let pathMouseNormalSegmentIdx; for (let i = 1; i < verts.length; ++i) { const normal = getNormalOnSegment(localMouse, verts[i - 1], verts[i]); const dist = normal?.distanceTo(localMouse) ?? Infinity; if (dist < ent.circle.radius) { pathMouseNormal = normal; pathMouseNormalSegmentIdx = i; env.ctx.save(); env.ctx.translate(ent.position.x, ent.position.y); env.ctx.fillStyle = "#f0f"; env.ctx.beginPath(); env.ctx.arc(normal.x, normal.y, ent.circle.radius, 0, TWO_PI); env.ctx.fill(); env.ctx.restore(); break; } } if (env.mouse.click) { if ( ent.position.distanceTo(env.mouse.pos) < ent.circle.radius && env.mouse.second ) { if (ent.path.closed) { ent.path.closed = false; ent.path.vertices.pop(); } else { ent.path.closed = true; ent.path.vertices.push(vec2()); } env.mouse.handled = true; return; } for ( let vi = 1; vi < ent.path.vertices.length - (ent.path.closed ? 1 : 0); ++vi ) { const v = ent.path.vertices[vi]; const vPos = ent.position.clone().add(v); const dist = vPos.distanceTo(env.mouse.pos); if (dist < ent.circle.radius) { env.mouse.handled = true; if ( env.mouse.second && ent.path.vertices.length > (ent.path.closed ? 3 : 2) ) { ent.path.vertices.splice(vi, 1); return; } else { env.__dragging = { type: "pathVertex", ent, vert: v, vertStart: v.clone(), start: env.mouse.pos.clone() }; return; } } } const marker = ent.path.vertices[1] .clone() .negate() .setLength(ent.path.radius) .add(ent.position); if (marker.distanceTo(env.mouse.pos) < ent.circle.radius) { env.__dragging = { type: "pathRadius", ent, r: ent.path.radius, baseDist: env.mouse.pos.distanceTo(ent.position) }; env.mouse.handled = true; return; } if ( env.mouse.main && pathMouseNormal && pathMouseNormalSegmentIdx !== undefined ) { ent.path.vertices.splice( pathMouseNormalSegmentIdx, 0, pathMouseNormal ); env.__dragging = { type: "pathVertex", ent, vert: pathMouseNormal, vertStart: pathMouseNormal.clone(), start: env.mouse.pos.clone() }; env.mouse.handled = true; return; } } } } }38:T582,followFirstPathSegmentSys = (env, ents) => { for (let entIdx = 0; entIdx < ents.length; ++entIdx) { const ent = ents[entIdx]; if (ent.position && ent.velocity && ent.followPath?.path) { const future = ent.position .clone() .add(ent.velocity.clone().setLength(ent.followPath.maxFuture)); env.ctx.beginPath(); env.ctx.moveTo(ent.position.x, ent.position.y); env.ctx.lineTo(future.x, future.y); env.ctx.stroke(); const pth = ent.followPath.path; future.sub(pth.position); const normal = getNormalToSegment( future, pth.path.vertices[0], pth.path.vertices[1] ); if (!normal) { continue; } const normalDist = normal.distanceTo(future); env.ctx.beginPath(); env.ctx.fillStyle = "#f0f"; env.ctx.arc( pth.position.x + normal.x, pth.position.y + normal.y, 3, 0, TWO_PI ); env.ctx.fill(); const target = pth.path.vertices[1] .clone() .setLength(ent.followPath.maxFuture) .add(normal) .add(pth.position); env.ctx.beginPath(); env.ctx.fillStyle = "#333"; env.ctx.arc(target.x, target.y, 3, 0, TWO_PI); env.ctx.fill(); if (normalDist > pth.path.radius) { applySeekForce(ent, target, { weight: ent.followPath.weight }); } } } }39:T9f7,followPathSys = (env, ents) => { for (let entIdx = 0; entIdx < ents.length; ++entIdx) { const ent = ents[entIdx]; if (ent.position && ent.velocity && ent.followPath?.path) { const future = ent.position .clone() .add(ent.velocity.clone().setLength(ent.followPath.maxFuture)); if (ent.debug) { env.ctx.beginPath(); env.ctx.moveTo(ent.position.x, ent.position.y); env.ctx.lineTo(future.x, future.y); env.ctx.stroke(); } const pth = ent.followPath.path; future.sub(pth.position); const [normal, dist, segmentIdx] = getNormalOnPath( future, pth.path.vertices ); if (!normal) { continue; } if (ent.debug) { env.ctx.beginPath(); env.ctx.fillStyle = "#f0f"; env.ctx.arc( pth.position.x + normal.x, pth.position.y + normal.y, 3, 0, TWO_PI ); env.ctx.fill(); } let target; let seekTarget = dist > pth.path.radius; const segment = vec2().subVectors( pth.path.vertices[segmentIdx + 1], pth.path.vertices[segmentIdx] ); const isLastSegment = segmentIdx + 2 === pth.path.vertices.length; const segToNormDist = pth.path.vertices[segmentIdx].distanceTo(normal); let futureDist = segToNormDist + ent.followPath.maxFuture; if (futureDist <= segment.length()) { target = segment .setLength(futureDist) .add(pth.path.vertices[segmentIdx]); } else if (isLastSegment && !pth.path.closed) { target = segment .setLength(futureDist) .add(pth.path.vertices[segmentIdx]); if (normal.equals(pth.path.vertices[segmentIdx + 1])) { seekTarget = false; } } else { futureDist -= segment.length(); const nextSegIdx = isLastSegment ? 0 : segmentIdx + 1; const nestSegStart = pth.path.vertices[nextSegIdx]; target = pth.path.vertices[nextSegIdx + 1] .clone() .sub(nestSegStart) .setLength(futureDist) .add(pth.path.vertices[nextSegIdx]); seekTarget = true; } target.add(pth.position); if (ent.debug) { env.ctx.beginPath(); env.ctx.fillStyle = seekTarget ? "#a33" : "#333"; env.ctx.arc(target.x, target.y, 3, 0, TWO_PI); env.ctx.fill(); } if (seekTarget) { applySeekForce(ent, target, { weight: ent.followPath.weight }); } } } }3a:T4a9,separateSys = (env, ents) => { for (let entIdx = 0; entIdx < ents.length; ++entIdx) { const ent = ents[entIdx]; if (!ent.position || !ent.vehicle || !ent.separate) continue; const minDist = ent.separate.dist || Math.max( ent.rect?.w ?? 0, ent.rect?.h ?? 0, (ent.circle?.radius ?? 0) * 2 ); let sum = vec2(); let count = 0; const entsToCheck = env.query.pointsInRange(ent.position, minDist); let otherIdx, other; for (otherIdx = 0; otherIdx < entsToCheck.length; ++otherIdx) { other = entsToCheck[otherIdx]; if (ent === other || other.dead || !other.separate || !other.position) continue; const dist = ent.position.distanceTo(other.position) || 0.1; const diff = vec2() .subVectors(ent.position, other.position) .setLength(1 / dist); if (vec2.ZERO.equals(diff)) diff.random(); sum.add(diff); ++count; } if (count > 0) { ent.force.add( sum .setLength(ent.vehicle.maxSpeed) .sub(ent.velocity) .clampLength(0, ent.vehicle.maxForce) .multiplyScalar(ent.separate.weight) ); } } }3b:T41f,{ const height = 400; const pathOffset = 60; const pathToFollow = path({ pos: vec2(pathOffset, pathOffset), vs: [ vec2(width - pathOffset * 2, 0), vec2(width - pathOffset * 2, height - pathOffset * 2), vec2(width / 2 - pathOffset, height - pathOffset * 3.5), vec2(0, height - pathOffset * 2) ], closed: true // editable: true }); const createVehicle = () => vehicle( { pos: vec2(random(width), random(height)), maxSpeed: random(1, 2), maxForce: random(0.4, 0.7) }, velocity(vec2().random()), onStageExit("bounce"), separate({ dist: 25 }), // debug, followPath(pathToFollow, { maxFuture: random(25, 35) }) ); return sim({ width, height, visibility, systems: [ entityDragging, pathEditingSys, separateSys, followPathSys, angularMovement, movement, onStageExitSys, renderer ], entities: [pathToFollow, ...Array.from({ length: 100 }, createVehicle)] }); }3c:T75b,{ const height = 400; const pointer = entity( position(400, 100), circle(20), graphics(), atMousePos, // debug, collisions({ layer: 1, mask: 1, onCollide: (ent, collided, env) => { if (env.mouse.pos) return; ent.position.set(random(width), random(height)); } }) ); const wanderer = vehicle( { pos: vec2(width / 2, height / 2), w: 40, h: 20, fill: "#9e9", maxSpeed: 1, maxForce: 0.02 }, velocity(2, 0), onStageExit("wrap"), wander(), collisions({ layer: 1, mask: 0 }), seekEntity(pointer), stayWithinWalls({ weight: 2 }) ); const localSystem = (env, ents) => { const dx = 0.01; const dy = 0.1; env._local_x = (env._local_x ?? 0) + dx; let _y = 0; for (let entIdx = 0; entIdx < ents.length; ++entIdx) { const ent = ents[entIdx]; _y += dy; if (ent.separate) { ent.separate.weight = 2 * noise2D(env._local_x, _y); } if (ent.seekEntity) { ent.seekEntity.weight = 1 + Math.sin(env._local_x); } } }; return sim({ width, height: height, visibility, systems: [ localSystem, atMousePosSys, wanderSys, stayWithinWallsSys, seekEntitySys, separateSys, angularMovement, movement, testCollisions, onStageExitSys, renderer // stateDump ], entities: [ pointer, ...Array.from({ length: 100 }, () => vehicle( { pos: vec2(random(width), random(height)), maxSpeed: 2, maxForce: 0.02, r: 8 }, rotation(random(TWO_PI)), onStageExit("wrap"), separate({ weight: 1.5 }), seekEntity(wanderer, { weight: 0.5 }) ) ), wanderer ] }); }3d:T692,alignSys = (env, ents) => { for (let entIdx = 0; entIdx < ents.length; ++entIdx) { const ent = ents[entIdx]; if (!ent.position || !ent.vehicle || !ent.align) continue; const { viewDist, weight, fov, debug } = ent.align; let fovMin = 0, fovMax = TWO_PI; if (fov > 0) { const fovr = MathUtils.degToRad(fov) / 2; fovMin = ent.rotation - fovr; fovMax = ent.rotation + fovr; } if (debug) { env.ctx.fillStyle = "#6c62"; env.ctx.beginPath(); env.ctx.moveTo(ent.position.x, ent.position.y); env.ctx.arc(ent.position.x, ent.position.y, viewDist, fovMin, fovMax); env.ctx.closePath(); env.ctx.fill(); } const sum = vec2(); const entsToCheck = env.query.pointsInRange(ent.position, viewDist); let otherIdx, other; for (otherIdx = 0; otherIdx < entsToCheck.length; ++otherIdx) { other = entsToCheck[otherIdx]; if (ent !== other && other.align && other.velocity) { if (fov > 0) { const a = vec2().subVectors(other.position, ent.position).angle(); if (a < fovMin || a > fovMax) continue; } sum.add(other.velocity); if (debug) { env.ctx.strokeStyle = "#0a09"; env.ctx.beginPath(); env.ctx.moveTo(ent.position.x, ent.position.y); env.ctx.lineTo(other.position.x, other.position.y); env.ctx.stroke(); } } } if (!vec2.ZERO.equals(sum)) { ent.force.add( sum .setLength(ent.vehicle.maxSpeed) .sub(ent.velocity) .clampLength(0, ent.vehicle.maxForce) .multiplyScalar(weight) ); } } }3e:T485,viewof exercise_5_18_form = Inputs.form({ vehicle: Inputs.form({ speed: Inputs.range([0.1, 10], { label: "Max speed", step: 0.01, value: 2 }), force: Inputs.range([0.01, 1], { label: "Max force", step: 0.001, value: 0.02 }) }), separate: Inputs.form({ dist: Inputs.range([0, 100], { label: "Separation distance", step: 1, value: 25 }), weight: Inputs.range([0, 3], { label: "Separation weight", step: 0.01, value: 1.5 }) }), align: Inputs.form({ dist: Inputs.range([1, 200], { label: "Alignment view distance", step: 1, value: 50 }), fov: Inputs.range([0, 180], { label: "Alignment field of view", step: 1, value: 0 }), weight: Inputs.range([0, 3], { label: "Alignment weight", step: 0.01, value: 1.0 }) }), cohere: Inputs.form({ dist: Inputs.range([1, 200], { label: "Coherence view distance", step: 1, value: 50 }), weight: Inputs.range([0, 3], { label: "Coherence weight", step: 0.01, value: 1.0 }) }) })3f:T402,{ const height = 300; const createBoid = (pos) => vehicle( { pos: pos?.clone() ?? vec2(random(width), random(height)), maxSpeed: 1, maxForce: 0.02, fill: "#faaa" }, force(vec2().random().subScalar(0.5)), onStageExit("wrap"), separate({ dist: 25, weight: 1.5 }), align({ viewDist: 50, fov: 120, weight: 1, debug: true }), cohere({ viewDist: 50, weight: 1 }) ); const addBoidOnMouseDown = (env, ents) => { if (env.mouse.main) { env.addEntity(createBoid(env.mouse.pos.clone())); } }; return sim({ width, height: height, visibility, queryEngine: new BinLatticeQueryEngine(width, height, 25), systems: [ addBoidOnMouseDown, exercise_5_15_formSystem, entityEraserSys(), separateSys, alignSys, cohereSys, angularMovement, movement, onStageExitSys, renderer, showStats ], entities: [...Array.from({ length: 100 }, createBoid)] }); }40:Tcdd,{ const height = 600; const pathToFollow1 = path({ color: "#faf", pos: vec2(0, 160), vs: [vec2(width * 0.3, 100), vec2(width * 0.7, -45), vec2(width, 0)] }); const pathToFollow2 = path({ color: "#ffa", r: 50, pos: vec2(width / 2 - 50, 0), vs: [vec2(50, height)] }); const createPredator = ({ pos } = {}) => vehicle( { pos: pos || vec2(width / 2, height / 2), w: 45, h: 25, fill: "#e99", maxSpeed: 1.5, maxForce: 0.03 }, velocity(vec2(random(-1, 1), random(-1, 1))), onStageExit("wrap"), wander(), detector({ range: 70, mask: 1, onDetect: onDetectFollowWeek }), stayWithinWalls({ weight: 2 }) ); const createPathFollowingBoid = ({ pos, pth, fill }) => vehicle( { fill, w: 25, h: 12, pos: pos ?? vec2(random(width), random(height)), maxSpeed: random(1, 2), maxForce: random(0.01, 0.03) }, velocity(vec2(random(-1, 1), random(-1, 1))), onStageExit("wrap"), separate({ dist: 25, weight: 1.5 }), align({ viewDist: 50, weight: 0.3 }), cohere({ viewDist: 50, weight: 0.7 }), followPath(pth, { weight: 1.7 }), detector() ); const createBoid = ({ pos, fill = "#3ffa" } = {}) => vehicle( { fill, pos: pos?.clone() ?? vec2(random(width), random(height)), maxSpeed: random(1, 2), maxForce: random(0.01, 0.03) }, velocity(vec2(random(-1, 1), random(-1, 1))), onStageExit("wrap"), separate({ dist: 25, weight: 1.5 }), align({ viewDist: 50, weight: 1.2 }), cohere({ viewDist: 50, weight: 1 }), detector() ); const addMoreBoids = (env, ents) => { if (env.mouse.down && env.mouse.main && !env.mouse.handled) { if (env.mouse.alt || env.mouse.ctrl) { env.addEntity( createPathFollowingBoid({ pos: env.mouse.pos.clone(), pth: env.mouse.alt ? pathToFollow1 : pathToFollow2, fill: env.mouse.alt ? "#f3fa" : "#ff3a" }) ); } else if (env.mouse.shift) { if (env.mouse.click) env.addEntity(createPredator({ pos: env.mouse.pos.clone() })); } else { env.addEntity(createBoid({ pos: env.mouse.pos.clone() })); } env.mouse.handled = true; return; } }; return sim({ width, height: height, visibility, queryEngine: new BinLatticeWithCircQueryEngine(width, height, 50), systems: [ // entityDragging, // pathEditingSys, detectorSys, followPathSys, separateSys, alignSys, cohereSys, wanderSys, stayWithinWallsSys, angularMovement, movement, onStageExitSys, renderer, addMoreBoids, entityEraserSys(), showStats // stateDump ], entities: [ pathToFollow1, pathToFollow2, ...Array.from({ length: 60 }, () => createPathFollowingBoid({ pth: pathToFollow1, fill: "#f3fa" }) ), ...Array.from({ length: 40 }, () => createPathFollowingBoid({ pth: pathToFollow2, fill: "#ff3a" }) ), ...Array.from({ length: 600 }, createBoid), createPredator() ] }); }41:T45e,{ const height = 300; const createBoid = (pos) => vehicle( { pos: pos?.clone() ?? vec2(random(width), random(height)), maxSpeed: 1, maxForce: 0.02, fill: "#faaa" }, force(vec2().random().subScalar(0.5)), onStageExit("wrap"), separate({ dist: 25, weight: 1.5 }), align({ viewDist: 50, weight: 1 }), cohere({ viewDist: 50, weight: 1 }), freeView({ viewDist: 50, fov: 120, weight: 1.5, debug: false }) ); const addBoidOnMouseDown = (env, ents) => { if (env.mouse.main) { env.addEntity(createBoid(env.mouse.pos.clone())); } }; return sim({ width, height: height, visibility, // stepByStep: true, queryEngine: new BinLatticeQueryEngine(width, height, 25), systems: [ addBoidOnMouseDown, exercise_5_17_formSystem, entityEraserSys(), separateSys, alignSys, cohereSys, angularMovement, freeViewSys, movement, onStageExitSys, renderer, showStats ], entities: [...Array.from({ length: 100 }, createBoid)] }); }42:T89c,freeViewSys = (env, ents) => { for (let entIdx = 0; entIdx < ents.length; ++entIdx) { const ent = ents[entIdx]; if (!ent.position || !ent.vehicle || !ent.freeView) continue; const { viewDist, weight, fov, debug } = ent.freeView; let fovMin = 0, fovMax = TWO_PI; if (fov > 0) { const fovr = MathUtils.degToRad(fov) / 2; fovMin = ent.rotation - fovr; fovMax = ent.rotation + fovr; } if (debug) { env.ctx.fillStyle = "#66c2"; env.ctx.beginPath(); env.ctx.moveTo(ent.position.x, ent.position.y); env.ctx.arc(ent.position.x, ent.position.y, viewDist, fovMin, fovMax); env.ctx.closePath(); env.ctx.fill(); } const sum = vec2(); const entsToCheck = env.query.pointsInRange(ent.position, viewDist); let otherIdx, other; for (otherIdx = 0; otherIdx < entsToCheck.length; ++otherIdx) { other = entsToCheck[otherIdx]; if (ent !== other && other.freeView && other.velocity && fov > 0) { const otherVec = vec2().subVectors(other.position, ent.position); const dist = otherVec.length(); const otherVecAngle = otherVec.angle(); if (otherVecAngle < fovMin || otherVecAngle > fovMax) continue; otherVec .rotateAround( vec2.ZERO, HALF_PI * (otherVecAngle < ent.rotation ? 1 : -1) ) .setLength(1 - dist / viewDist); sum.add(otherVec); if (debug) { env.ctx.strokeStyle = "#00a9"; env.ctx.beginPath(); env.ctx.moveTo(ent.position.x, ent.position.y); env.ctx.lineTo(other.position.x, other.position.y); env.ctx.stroke(); env.ctx.beginPath(); env.ctx.moveTo(ent.position.x, ent.position.y); env.ctx.lineTo( ent.position.x + otherVec.x * 50, ent.position.y + otherVec.y * 50 ); env.ctx.stroke(); } } } if (!vec2.ZERO.equals(sum)) { ent.force.add( sum .setLength(ent.vehicle.maxSpeed) .sub(ent.velocity) .clampLength(0, ent.vehicle.maxForce) .multiplyScalar(weight) ); } } }43:T720,{ const height = 500; const createCentralBoid = (pos) => vehicle( { pos: pos?.clone() ?? vec2(random(width), random(height)), maxSpeed: 2, maxForce: 0.02, r: 25, fill: "#000", draw: () => {} }, sprite(starSprite, { scale: vec2(0.7), blendMode: "destination-out" }), rotation(random(TWO_PI)), onStageExit("wrap"), detector({ layer: 2, mask: 2, range: 150, onDetect: (detectedIds, env, self) => { for (const id of detectedIds) { const entPos = env.getEntity(id)?.position; if (entPos) applyFleeForce(self, entPos, { weight: 3 }); } } }), separate({ dist: 15, weight: 0.5 }), align({ viewDist: 50, weight: 1.5 }), cohere({ viewDist: 50, weight: 2 }) ); const createBoid = (pos) => vehicle( { pos: pos?.clone() ?? vec2(random(width), random(height)), maxSpeed: 2, maxForce: 0.02, r: 10, fill: "#fff", draw: () => {} }, sprite(blueCircleSprite, { blendMode: ex_5_19_blenMode, scale: vec2(2) }), rotation(random(TWO_PI)), onStageExit("wrap"), separate({ dist: 20, weight: 1.5 }), align({ viewDist: 50, weight: 1 }), cohere({ viewDist: 50, weight: 1 }) ); return sim({ width, height: height, visibility, bgColor: "#000", queryEngine: new BinLatticeQueryEngine(width, height, 25), systems: [ detectorSys, separateSys, alignSys, cohereSys, angularMovement, movement, onStageExitSys, renderer, showStats ], entities: [ ...Array.from({ length: 300 }, createBoid), ...Array.from({ length: 5 }, createCentralBoid) ] }); }44:T8c5,{ const height = 300; const rnx = d3.randomNormal(width / 2, 150); const rny = d3.randomNormal(height / 2, 50); const createPoint = (pos) => entity(position(pos ?? vec2(rnx(), rny())), circle(2), graphics()); let lastPointTime = performance.now(); const onMouse = (env, ents) => { if (env.mouse.down && performance.now() - lastPointTime > 70) { lastPointTime = performance.now(); env.addEntity(createPoint(env.mouse.pos.clone())); } if (env.mouse.pos) { const ctx = env.ctx; ctx.save(); ctx.font = "bold 12px sans-serif"; const boxW = 120; const boxH = 100; const box = box2.centered(env.mouse.pos, boxW, boxH); box.translate(vec2(-boxW / 2 - 10, 0)); ctx.strokeStyle = "#99f"; ctx.strokeRect(box.min.x, box.min.y, boxW, boxH); const inBox = env.query.pointsInBox(box); for (let i = 0; i < inBox.length; ++i) { const ent = inBox[i]; ctx.fillStyle = "#99f"; ctx.beginPath(); ctx.arc(ent.position.x, ent.position.y, 5, 0, TWO_PI); ctx.fill(); } ctx.fillStyle = "#99f"; ctx.fillText(`in rectangle: ${inBox.length}`, 10, 50); const r = 60; const o = env.mouse.pos.clone(); o.x += r + 10; ctx.strokeStyle = "#f9f"; ctx.beginPath(); ctx.arc(o.x, o.y, r, 0, TWO_PI); ctx.stroke(); const inRange = env.query.pointsInRange(o, r); for (let i = 0; i < inRange.length; ++i) { const ent = inRange[i]; ctx.fillStyle = "#f9f"; ctx.beginPath(); ctx.arc(ent.position.x, ent.position.y, 5, 0, TWO_PI); ctx.fill(); } ctx.fillStyle = "#f9f"; ctx.fillText(`in circle: ${inRange.length}`, 10, 70); ctx.restore(); } }; return sim({ width, height: height, visibility, queryEngine: new BinLatticeQueryEngine(width, height, 25, true), systems: [ onMouse, exercise_5_18_formSystem, entityEraserSys(), separateSys, alignSys, cohereSys, angularMovement, movement, onStageExitSys, renderer, // stateDump, showStats ], entities: Array.from({ length: 500 }, createPoint) }); }45:Tccd,class BinLatticeQueryEngine extends QueryEngine { constructor(width, height, resolution = 25, debug = false) { super(); this.resolution = resolution; this.cols = Math.ceil((width + 1) / resolution); this.rows = Math.ceil((height + 1) / resolution); this.bins = Array.from({ length: this.cols * this.rows }, (_, i) => { const bin = []; const r = Math.floor(i / this.cols); const c = i % this.cols; bin.aabb = box2( c * resolution, r * resolution, (r + 1) * resolution, (c + 1) * resolution ); return bin; }); this.crBox = box2(this.cols - 1, this.rows - 1); this.debug = debug; this.__tmpBox = box2(); this.__tmpVec = vec2(); } bin(col, row) { return this.bins[row * this.cols + col]; } binAt(v) { const pos = this.__tmpVec .copy(v) .divideScalar(this.resolution) .floor() .clamp(this.crBox.min, this.crBox.max); return this.bins[pos.y * this.cols + pos.x]; } add(ent) { if (ent.position && !ent.dead) { this.binAt(ent.position)?.push(ent); } } onLoopStart(env, ents) { for (let i = 0; i < this.bins.length; ++i) { this.bins[i].length = 0; } for (let i = 0; i < ents.length; ++i) { this.add(ents[i]); } if (this.debug) this.drawDebug(env, ents); } pointsInBox(box) { const crBox = this.__tmpBox.copy(box); crBox.min.divideScalar(this.resolution).floor(); crBox.max.divideScalar(this.resolution).ceil(); crBox.intersect(this.crBox); const out = []; let r, c, i; for (r = crBox.min.y; r <= crBox.max.y; ++r) { for (c = crBox.min.x; c <= crBox.max.x; ++c) { const bin = this.bin(c, r); const fullyContained = box.containsBox(bin.aabb); for (i = 0; i < bin.length; ++i) { const ent = bin[i]; if ( ent?.dead === false && (fullyContained || box.containsPoint(ent.position)) ) { out.push(bin[i]); } } } } return out; } pointsInRange(pos, range) { const crBox = this.__tmpBox.setFromCenterAndSize( pos, this.__tmpVec.setScalar(range * 2) ); crBox.min.divideScalar(this.resolution).floor(); crBox.max.divideScalar(this.resolution).ceil(); crBox.intersect(this.crBox); const rangeSq = range * range; const out = []; let r, c, i; for (r = crBox.min.y; r <= crBox.max.y; ++r) { for (c = crBox.min.x; c <= crBox.max.x; ++c) { const bin = this.bin(c, r); for (i = 0; i < bin.length; ++i) { const ent = bin[i]; if ( ent?.dead === false && pos.distanceToSquared(ent.position) <= rangeSq ) { out.push(bin[i]); } } } } return out; } drawDebug(env, ents) { env.ctx.strokeStyle = "#ddd"; env.ctx.beginPath(); for (let r = 0; r < this.rows; ++r) { env.ctx.moveTo(0, r * this.resolution); env.ctx.lineTo(env.width, r * this.resolution); } for (let c = 0; c < this.cols; ++c) { env.ctx.moveTo(c * this.resolution, 0); env.ctx.lineTo(c * this.resolution, env.height); } env.ctx.stroke(); } }46:T8c2,{ const height = 300; const rnx = d3.randomNormal(width / 2, 150); const rny = d3.randomNormal(height / 2, 50); const createPoint = (pos) => entity(position(pos ?? vec2(rnx(), rny())), circle(2), graphics()); let lastPointTime = performance.now(); const onMouse = (env, ents) => { if (env.mouse.down && performance.now() - lastPointTime > 70) { lastPointTime = performance.now(); env.addEntity(createPoint(env.mouse.pos.clone())); } if (env.mouse.pos) { const ctx = env.ctx; ctx.save(); ctx.font = "bold 12px sans-serif"; const boxW = 120; const boxH = 100; const box = box2.centered(env.mouse.pos, boxW, boxH); box.translate(vec2(-boxW / 2 - 10, 0)); ctx.strokeStyle = "#99f"; ctx.strokeRect(box.min.x, box.min.y, boxW, boxH); const inBox = env.query.pointsInBox(box); for (let i = 0; i < inBox.length; ++i) { const ent = inBox[i]; ctx.fillStyle = "#99f"; ctx.beginPath(); ctx.arc(ent.position.x, ent.position.y, 5, 0, TWO_PI); ctx.fill(); } ctx.fillStyle = "#99f"; ctx.fillText(`in rectangle: ${inBox.length}`, 10, 50); const r = 60; const o = env.mouse.pos.clone(); o.x += r + 10; ctx.strokeStyle = "#f9f"; ctx.beginPath(); ctx.arc(o.x, o.y, r, 0, TWO_PI); ctx.stroke(); const inRange = env.query.pointsInRange(o, r); for (let i = 0; i < inRange.length; ++i) { const ent = inRange[i]; ctx.fillStyle = "#f9f"; ctx.beginPath(); ctx.arc(ent.position.x, ent.position.y, 5, 0, TWO_PI); ctx.fill(); } ctx.fillStyle = "#f9f"; ctx.fillText(`in circle: ${inRange.length}`, 10, 70); ctx.restore(); } }; return sim({ width, height: height, visibility, queryEngine: new QuadTreeQueryEngine(width, height, 4, true), systems: [ onMouse, exercise_5_18_formSystem, entityEraserSys(), separateSys, alignSys, cohereSys, angularMovement, movement, onStageExitSys, renderer, // stateDump, showStats ], entities: Array.from({ length: 500 }, createPoint) }); }47:T61c,class QuadTreeQueryEngine extends QueryEngine { constructor( width, height, limit = 4, debug = false, Impl = QuadTreeNoContains ) { super(); this.bounds = box2(width, height); this.limit = limit; this.debug = debug; this.qtree = new Impl(this.bounds, this.limit); this.outOfBounds = []; this.__tmpBox = box2(); this.__tmpVec = vec2(); } add(ent) { if (!this.qtree.add(ent)) { this.outOfBounds.push(ent); } } onLoopStart(env, ents) { this.qtree.clear(); this.outOfBounds.length = 0; for (let i = 0; i < ents.length; ++i) { const ent = ents[i]; if (ent?.dead === false && ent.position) { this.add(ents[i]); } } if (this.debug) this.drawDebug(env, ents); } pointsInBox(box) { const out = []; this.qtree.queryBox(box, out); for (let i = 0; i < this.outOfBounds.length; ++i) { const ent = this.outOfBounds[i]; if (ent?.position && box.containsPoint(ent.position)) out.push(ent); } return out; } pointsInRange(pos, range) { const out = []; const circ = circle2(pos, range); this.qtree.queryCircle(circ, out); for (let i = 0; i < this.outOfBounds.length; ++i) { const ent = this.outOfBounds[i]; if (ent?.position && circ.containsPoint(ent.position)) out.push(ent); } return out; } drawDebug(env, ents) { const ctx = env.ctx; ctx.save(); ctx.strokeStyle = "#ddd"; ctx.lineWidth = 1; this.qtree?.drawDebug(ctx); ctx.restore(); } }48:Tae0,class QuadTree { constructor(bounds, limit = 4) { this.bounds = bounds; this.limit = limit; this.entities = []; } clear() { this.entities.length = 0; delete this.nw; delete this.ne; delete this.sw; delete this.se; } add(entity) { if (!this.bounds.containsPoint(entity.position)) { return false; } if (this.entities.length < this.limit) { this.entities.push(entity); return true; } if (!this.nw) { this.split(); } return ( this.nw.add(entity) || this.ne.add(entity) || this.sw.add(entity) || this.se.add(entity) ); } getAll(out) { for (let i = 0; i < this.entities.length; ++i) { out.push(this.entities[i]); } if (this.nw) { this.nw.getAll(out); this.ne.getAll(out); this.sw.getAll(out); this.se.getAll(out); } return out; } queryBox(box, out) { if (!this.bounds.intersectsBox(box)) return; if (box.containsBox(this.bounds)) return this.getAll(out); let i, ent; for (i = 0; i < this.entities.length; ++i) { ent = this.entities[i]; if (ent?.position && box.containsPoint(ent.position)) out.push(ent); } if (this.nw) { this.nw.queryBox(box, out); this.ne.queryBox(box, out); this.sw.queryBox(box, out); this.se.queryBox(box, out); } return out; } queryCircle(circ, out) { if (!this.bounds.intersectsBox(circ.outerAABB)) return; if (circ.containsIntersectingBox(this.bounds)) return this.getAll(out); let i, ent; for (i = 0; i < this.entities.length; ++i) { ent = this.entities[i]; if (ent?.position && circ.containsPoint(ent.position)) out.push(ent); } if (this.nw) { this.nw.queryCircle(circ, out); this.ne.queryCircle(circ, out); this.sw.queryCircle(circ, out); this.se.queryCircle(circ, out); } return out; } split() { const center = this.bounds.getCenter(vec2()); this.nw = new this.constructor(box2(this.bounds.min, center), this.limit); this.ne = new this.constructor( box2( vec2(center.x, this.bounds.min.y), vec2(this.bounds.max.x, center.y) ), this.limit ); this.sw = new this.constructor( box2( vec2(this.bounds.min.x, center.y), vec2(center.x, this.bounds.max.y) ), this.limit ); this.se = new this.constructor(box2(center, this.bounds.max), this.limit); } drawDebug(ctx) { const size = this.bounds.getSize(vec2()); ctx.strokeRect(this.bounds.min.x, this.bounds.min.y, size.x, size.y); if (this.nw) { this.nw.drawDebug(ctx); this.ne.drawDebug(ctx); this.sw.drawDebug(ctx); this.se.drawDebug(ctx); } } }49:Tb31,{ const height = 400; const createBoid = (pos) => vehicle( { pos: pos?.clone() ?? vec2(random(width), random(height)), maxSpeed: 2, maxForce: 0.02 }, rotation(random(TWO_PI)), onStageExit("wrap"), separate({ dist: 25, weight: 1.8 }), align({ viewDist: 50, weight: 1 }), cohere({ viewDist: 50, weight: 1 }) ); const addBoidOnMouseDown = (env, ents) => { if (env.mouse.main && !env.mouse.handled) { env.addEntity(createBoid(env.mouse.pos.clone())); } }; const avgFpsTimer = (env) => { env.__avgFpsTimer ??= { start: performance.now(), m1: null, m5: null }; const diff = performance.now() - env.__avgFpsTimer.start; if (!env.__avgFpsTimer.m1 && diff > 1000 * 60) { env.__avgFpsTimer.m1 = env.clock.avgFps; } if (!env.__avgFpsTimer.m5 && diff > 1000 * 60 * 5) { env.__avgFpsTimer.m5 = env.clock.avgFps; } env.stats?.push(`time: ${Math.floor(diff / 1000)}s`); if (env.__avgFpsTimer.m1) env.stats?.push(`avg fps 1min: ${env.__avgFpsTimer.m1}`); if (env.__avgFpsTimer.m5) env.stats?.push(`avg fps 5min: ${env.__avgFpsTimer.m5}`); }; const qEngines = { none: undefined, binLattice: new BinLatticeQueryEngine( width, height, spatialSubdivision.blRes, spatialSubdivision.debug ), binLatticeBetterCirc: new BinLatticeWithCircQueryEngine( width, height, spatialSubdivision.blRes, spatialSubdivision.debug ), quadtree: new QuadTreeQueryEngine( width, height, spatialSubdivision.qtLmit, spatialSubdivision.debug ), quadtreeNoSkip: new QuadTreeQueryEngine( width, height, spatialSubdivision.qtLmit, spatialSubdivision.debug, QuadTreeNoContains ), quadtreeOnlyLeaves: new QuadTreeQueryEngine( width, height, spatialSubdivision.qtLmit, spatialSubdivision.debug, QuadTreeOnlyLeaves ), quadtreeWithPool: new QuadTreeQueryEngine( width, height, spatialSubdivision.qtLmit, spatialSubdivision.debug, QuadTreeWithPool ), quadtreeSimpleSkip: new QuadTreeQueryEngine( width, height, spatialSubdivision.qtLmit, spatialSubdivision.debug, QuadTreeSimplerSkip ) }; return sim({ width, height: height, visibility, queryEngine: qEngines[spatialSubdivision.engine], systems: [ avgFpsTimer, addBoidOnMouseDown, exercise_5_18_formSystem, entityEraserSys(), separateSys, alignSys, cohereSys, angularMovement, movement, onStageExitSys, renderer, showStats // stateDump ], entities: [...Array.from({ length: spatialSubdivision.bnum }, createBoid)] }); }4a:T409,Summary of results on my machine for provided versions: Few notes before: - Provided values are after other performance improvements (more on that later). - Description for other versions are near its implementation. - There are three numbers: - First column is number of boids it took to lower fps below my max (120) - Second column is avarage fps (after ~1min) for 2000 boids | subdivision type | to drop | 2k boids | comments | | --- | --- | --- | --- | | none | 370 | 4 | (sic!) didn't even waited full minute :/ | | Bin-lattice | 1000 | 42 | get huge perf hits when boids are clustered | | Bin-lattice w circle checks | 1000 | 53 | better results with higher resolution | | QuadTree | 700 | 25 | perform even worse than bin-lattice when clustered | | QuadTree w no skip | 700 | 26 | no significant difference | | QuadTree w simple skip | 700 | 23 | no significant difference | | QuadTree only leafs | 720 | 25 | but drops even harder for clusters | | QuadTree w pooling | 980 | 38 | slightly better when not hit by gc | 4b:Te34,class BinLatticeWithCircQueryEngine extends QueryEngine { constructor(width, height, resolution = 25, debug = false) { super(); this.resolution = resolution; this.cols = Math.ceil((width + 1) / resolution); this.rows = Math.ceil((height + 1) / resolution); this.bins = Array.from({ length: this.cols * this.rows }, (_, i) => { const bin = []; const r = Math.floor(i / this.cols); const c = i % this.cols; bin.aabb = box2( c * resolution, r * resolution, (r + 1) * resolution, (c + 1) * resolution ); return bin; }); this.crBox = box2(this.cols - 1, this.rows - 1); this.debug = debug; this.__tmpBox = box2(); this.__tmpVec = vec2(); } bin(col, row) { return this.bins[row * this.cols + col]; } binAt(v) { const pos = this.__tmpVec .copy(v) .divideScalar(this.resolution) .floor() .clamp(this.crBox.min, this.crBox.max); return this.bins[pos.y * this.cols + pos.x]; } add(ent) { if (ent.position && !ent.dead) { this.binAt(ent.position)?.push(ent); } } onLoopStart(env, ents) { for (let i = 0; i < this.bins.length; ++i) { this.bins[i].length = 0; } for (let i = 0; i < ents.length; ++i) { this.add(ents[i]); } if (this.debug) this.drawDebug(env, ents); } pointsInBox(box) { const crBox = this.__tmpBox.copy(box); crBox.min.divideScalar(this.resolution).floor(); crBox.max.divideScalar(this.resolution).ceil(); crBox.intersect(this.crBox); const out = []; let r, c, i; for (r = crBox.min.y; r <= crBox.max.y; ++r) { for (c = crBox.min.x; c <= crBox.max.x; ++c) { const bin = this.bin(c, r); const fullyContained = box.containsBox(bin.aabb); for (i = 0; i < bin.length; ++i) { const ent = bin[i]; if ( ent?.dead === false && (fullyContained || box.containsPoint(ent.position)) ) { out.push(bin[i]); } } } } return out; } pointsInRange(pos, range) { const circ = circle2( pos.x / this.resolution, pos.y / this.resolution, range / this.resolution ); const crBox = this.__tmpBox .setFromCenterAndSize(pos, this.__tmpVec.setScalar(range * 2)) .clone(); crBox.min.divideScalar(this.resolution).floor(); crBox.max.divideScalar(this.resolution).ceil(); crBox.intersect(this.crBox); const rangeSq = range * range; const out = []; let r, c, i; for (r = crBox.min.y; r <= crBox.max.y; ++r) { for (c = crBox.min.x; c <= crBox.max.x; ++c) { this.__tmpBox.min.set(c, r); this.__tmpBox.max.set(c + 1, r + 1); if (!circ.intersectsBox(this.__tmpBox)) continue; const fullyContains = circ.containsBox(this.__tmpBox); const bin = this.bin(c, r); for (i = 0; i < bin.length; ++i) { const ent = bin[i]; if ( ent?.dead === false && (fullyContains || pos.distanceToSquared(ent.position) <= rangeSq) ) { out.push(bin[i]); } } } } return out; } drawDebug(env, ents) { env.ctx.strokeStyle = "#ddd"; env.ctx.beginPath(); for (let r = 0; r < this.rows; ++r) { env.ctx.moveTo(0, r * this.resolution); env.ctx.lineTo(env.width, r * this.resolution); } for (let c = 0; c < this.cols; ++c) { env.ctx.moveTo(c * this.resolution, 0); env.ctx.lineTo(c * this.resolution, env.height); } env.ctx.stroke(); } }4c:Ta9e,class QuadTreeNoContains { constructor(bounds, limit = 4) { this.bounds = bounds; this.limit = limit; this.entities = []; } clear() { this.entities.length = 0; delete this.nw; delete this.ne; delete this.sw; delete this.se; } add(entity) { if (!this.bounds.containsPoint(entity.position)) { return false; } if (this.entities.length < this.limit) { this.entities.push(entity); return true; } if (!this.nw) { this.split(); } return ( this.nw.add(entity) || this.ne.add(entity) || this.sw.add(entity) || this.se.add(entity) ); } getAll(out) { for (let i = 0; i < this.entities.length; ++i) { out.push(this.entities[i]); } if (this.nw) { this.nw.getAll(out); this.ne.getAll(out); this.sw.getAll(out); this.se.getAll(out); } return out; } queryBox(box, out) { if (!this.bounds.intersectsBox(box)) return; if (box.containsBox(this.bounds)) return this.getAll(out); let i, ent; for (i = 0; i < this.entities.length; ++i) { ent = this.entities[i]; if (ent?.position && box.containsPoint(ent.position)) out.push(ent); } if (this.nw) { this.nw.queryBox(box, out); this.ne.queryBox(box, out); this.sw.queryBox(box, out); this.se.queryBox(box, out); } return out; } queryCircle(circ, out) { if (!this.bounds.intersectsBox(circ.outerAABB)) return; let i, ent; for (i = 0; i < this.entities.length; ++i) { ent = this.entities[i]; if (ent?.position && circ.containsPoint(ent.position)) out.push(ent); } if (this.nw) { this.nw.queryCircle(circ, out); this.ne.queryCircle(circ, out); this.sw.queryCircle(circ, out); this.se.queryCircle(circ, out); } return out; } split() { const center = this.bounds.getCenter(vec2()); this.nw = new this.constructor(box2(this.bounds.min, center), this.limit); this.ne = new this.constructor( box2( vec2(center.x, this.bounds.min.y), vec2(this.bounds.max.x, center.y) ), this.limit ); this.sw = new this.constructor( box2( vec2(this.bounds.min.x, center.y), vec2(center.x, this.bounds.max.y) ), this.limit ); this.se = new this.constructor(box2(center, this.bounds.max), this.limit); } drawDebug(ctx) { const size = this.bounds.getSize(vec2()); ctx.strokeRect(this.bounds.min.x, this.bounds.min.y, size.x, size.y); if (this.nw) { this.nw.drawDebug(ctx); this.ne.drawDebug(ctx); this.sw.drawDebug(ctx); this.se.drawDebug(ctx); } } }4d:Tae9,class QuadTreeSimplerSkip { constructor(bounds, limit = 4) { this.bounds = bounds; this.limit = limit; this.entities = []; } clear() { this.entities.length = 0; delete this.nw; delete this.ne; delete this.sw; delete this.se; } add(entity) { if (!this.bounds.containsPoint(entity.position)) { return false; } if (this.entities.length < this.limit) { this.entities.push(entity); return true; } if (!this.nw) { this.split(); } return ( this.nw.add(entity) || this.ne.add(entity) || this.sw.add(entity) || this.se.add(entity) ); } getAll(out) { for (let i = 0; i < this.entities.length; ++i) { out.push(this.entities[i]); } if (this.nw) { this.nw.getAll(out); this.ne.getAll(out); this.sw.getAll(out); this.se.getAll(out); } return out; } queryBox(box, out) { if (!this.bounds.intersectsBox(box)) return; if (box.containsBox(this.bounds)) return this.getAll(out); let i, ent; for (i = 0; i < this.entities.length; ++i) { ent = this.entities[i]; if (ent?.position && box.containsPoint(ent.position)) out.push(ent); } if (this.nw) { this.nw.queryBox(box, out); this.ne.queryBox(box, out); this.sw.queryBox(box, out); this.se.queryBox(box, out); } return out; } queryCircle(circ, out) { if (!this.bounds.intersectsBox(circ.outerAABB)) return; if (circ.innerAABB.containsBox(this.bounds)) return this.getAll(out); let i, ent; for (i = 0; i < this.entities.length; ++i) { ent = this.entities[i]; if (ent?.position && circ.containsPoint(ent.position)) out.push(ent); } if (this.nw) { this.nw.queryCircle(circ, out); this.ne.queryCircle(circ, out); this.sw.queryCircle(circ, out); this.se.queryCircle(circ, out); } return out; } split() { const center = this.bounds.getCenter(vec2()); this.nw = new this.constructor(box2(this.bounds.min, center), this.limit); this.ne = new this.constructor( box2( vec2(center.x, this.bounds.min.y), vec2(this.bounds.max.x, center.y) ), this.limit ); this.sw = new this.constructor( box2( vec2(this.bounds.min.x, center.y), vec2(center.x, this.bounds.max.y) ), this.limit ); this.se = new this.constructor(box2(center, this.bounds.max), this.limit); } drawDebug(ctx) { const size = this.bounds.getSize(vec2()); ctx.strokeRect(this.bounds.min.x, this.bounds.min.y, size.x, size.y); if (this.nw) { this.nw.drawDebug(ctx); this.ne.drawDebug(ctx); this.sw.drawDebug(ctx); this.se.drawDebug(ctx); } } }4e:Tc1c,class QuadTreeOnlyLeaves { constructor(bounds, limit = 4) { this.bounds = bounds; this.limit = limit; this.entities = []; } clear() { this.entities = []; delete this.nw; delete this.ne; delete this.sw; delete this.se; } add(entity) { if (!this.bounds.containsPoint(entity.position)) { return false; } if (this.nw) { return ( this.nw.add(entity) || this.ne.add(entity) || this.sw.add(entity) || this.se.add(entity) ); } else { this.entities.push(entity); if (this.entities.length > this.limit) { this.split(); } return true; } } getAll(out) { if (this.nw) { this.nw.getAll(out); this.ne.getAll(out); this.sw.getAll(out); this.se.getAll(out); } else { for (let i = 0; i < this.entities.length; ++i) { out.push(this.entities[i]); } } return out; } queryBox(box, out) { if (!this.bounds.intersectsBox(box)) return; if (box.containsBox(this.bounds)) return this.getAll(out); let i, ent; if (this.nw) { this.nw.queryBox(box, out); this.ne.queryBox(box, out); this.sw.queryBox(box, out); this.se.queryBox(box, out); } else { for (i = 0; i < this.entities.length; ++i) { ent = this.entities[i]; if (ent?.position && box.containsPoint(ent.position)) out.push(ent); } } return out; } queryCircle(circ, out) { if (!this.bounds.intersectsBox(circ.outerAABB)) return; if (circ.containsBox(this.bounds)) return this.getAll(out); let i, ent; if (this.nw) { this.nw.queryCircle(circ, out); this.ne.queryCircle(circ, out); this.sw.queryCircle(circ, out); this.se.queryCircle(circ, out); } else { for (i = 0; i < this.entities.length; ++i) { ent = this.entities[i]; if (ent?.position && circ.containsPoint(ent.position)) out.push(ent); } } return out; } split() { const center = this.bounds.getCenter(vec2()); this.nw = new this.constructor(box2(this.bounds.min, center), this.limit); this.ne = new this.constructor( box2( vec2(center.x, this.bounds.min.y), vec2(this.bounds.max.x, center.y) ), this.limit ); this.sw = new this.constructor( box2( vec2(this.bounds.min.x, center.y), vec2(center.x, this.bounds.max.y) ), this.limit ); this.se = new this.constructor(box2(center, this.bounds.max), this.limit); for (let i = 0; i < this.entities.length; ++i) { const entity = this.entities[i]; this.nw.add(entity); this.ne.add(entity); this.sw.add(entity); this.se.add(entity); } delete this.entities; } drawDebug(ctx) { const size = this.bounds.getSize(vec2()); ctx.strokeRect(this.bounds.min.x, this.bounds.min.y, size.x, size.y); if (this.nw) { this.nw.drawDebug(ctx); this.ne.drawDebug(ctx); this.sw.drawDebug(ctx); this.se.drawDebug(ctx); } } }4f:Tcbc,class QuadTreeWithPool { static pool = []; static nextIdx = 0; static getFree(bounds, limit) { let next = this.pool[this.nextIdx]; if (next) { next.bounds = bounds; next.limit = limit; next.entities.length = 0; next.nw = null; next.ne = null; next.sw = null; next.se = null; } else { next = new this(bounds, limit); this.pool.push(next); } ++this.nextIdx; return next; } constructor(bounds, limit = 4) { this.bounds = bounds; this.limit = limit; this.entities = []; } clear() { this.entities.length = 0; this.nw = null; this.ne = null; this.sw = null; this.se = null; this.constructor.nextIdx = 0; } add(entity) { if (!this.bounds.containsPoint(entity.position)) { return false; } if (this.entities.length < this.limit) { this.entities.push(entity); return true; } if (!this.nw) { this.split(); } return ( this.nw.add(entity) || this.ne.add(entity) || this.sw.add(entity) || this.se.add(entity) ); } getAll(out) { for (let i = 0; i < this.entities.length; ++i) { out.push(this.entities[i]); } if (this.nw) { this.nw.getAll(out); this.ne.getAll(out); this.sw.getAll(out); this.se.getAll(out); } return out; } queryBox(box, out) { if (!this.bounds.intersectsBox(box)) return; if (box.containsBox(this.bounds)) return this.getAll(out); let i, ent; for (i = 0; i < this.entities.length; ++i) { ent = this.entities[i]; if (ent?.position && box.containsPoint(ent.position)) out.push(ent); } if (this.nw) { this.nw.queryBox(box, out); this.ne.queryBox(box, out); this.sw.queryBox(box, out); this.se.queryBox(box, out); } return out; } queryCircle(circ, out) { if (!this.bounds.intersectsBox(circ.outerAABB)) return; if (circ.containsIntersectingBox(this.bounds)) return this.getAll(out); let i, ent; for (i = 0; i < this.entities.length; ++i) { ent = this.entities[i]; if (ent?.position && circ.containsPoint(ent.position)) out.push(ent); } if (this.nw) { this.nw.queryCircle(circ, out); this.ne.queryCircle(circ, out); this.sw.queryCircle(circ, out); this.se.queryCircle(circ, out); } return out; } split() { const center = this.bounds.getCenter(vec2()); this.nw = new this.constructor(box2(this.bounds.min, center), this.limit); this.ne = new this.constructor( box2( vec2(center.x, this.bounds.min.y), vec2(this.bounds.max.x, center.y) ), this.limit ); this.sw = new this.constructor( box2( vec2(this.bounds.min.x, center.y), vec2(center.x, this.bounds.max.y) ), this.limit ); this.se = new this.constructor(box2(center, this.bounds.max), this.limit); } drawDebug(ctx) { const size = this.bounds.getSize(vec2()); ctx.strokeRect(this.bounds.min.x, this.bounds.min.y, size.x, size.y); if (this.nw) { this.nw.drawDebug(ctx); this.ne.drawDebug(ctx); this.sw.drawDebug(ctx); this.se.drawDebug(ctx); } } }50:[{"id":"bcc8c17b9a0338dd4d0b02b865f5dc1a1709903b2dbc57d2c519c9cbcdd9094e45b8337984131125f2d37e8152bda12ffa266211f8fe869467f589aab24b06d8","href":"https://static.observableusercontent.com/files/bcc8c17b9a0338dd4d0b02b865f5dc1a1709903b2dbc57d2c519c9cbcdd9094e45b8337984131125f2d37e8152bda12ffa266211f8fe869467f589aab24b06d8","name":"Slim Arrow Icon.png","type":"image/png","lastModified":1712090474650.324,"size":1360},{"id":"99a88779297bac2a97396f14f6013a8bd9d3a7c2499c117eff1e5f9f8bb6f371ce33309c9630b2c8c14eb543ef65aaf2280071e30ab66d03d5d3328d2540e769","href":"https://static.observableusercontent.com/files/99a88779297bac2a97396f14f6013a8bd9d3a7c2499c117eff1e5f9f8bb6f371ce33309c9630b2c8c14eb543ef65aaf2280071e30ab66d03d5d3328d2540e769","name":"particles2@2.png","type":"image/png","lastModified":1740659532966.804,"size":8861}] 2f:{"id":"84629e809ef7931e","slug":"the-nature-of-code-5-autonomous-agents","title":"The Nature of Code - 5 - Autonomous Agents","thumbnail":"21e66d0ba4179bed748e2a16fed56777d1c6131cbd0c514bb65e2ebd32198f05","access_level":"public","create_time":"$D2024-04-02T16:07:47.547Z","update_time":"$D2026-03-12T10:09:49.644Z","view_time":null,"first_public_time":"$D2025-03-01T23:53:12.547Z","fork":false,"stars":3,"starred":false,"owner":{"type":"team","id":"e59cfabcc8cf2053","login":"ajur","name":"Adam Jurczyk","avatar_url":"https://avatars-next.observableusercontent.com/9780c718edee977389e5a921151fad79009484346784f63edc44894bfc64c5cd","tier":"starter_2024"},"version":4050,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"316e3341b439aa13","login":"ajur","name":"Adam Jurczyk","avatar_url":"https://avatars-next.observableusercontent.com/9780c718edee977389e5a921151fad79009484346784f63edc44894bfc64c5cd","tier":null}],"members":[{"type":"individual","id":"316e3341b439aa13","login":"ajur","name":"Adam Jurczyk","avatar_url":"https://avatars-next.observableusercontent.com/9780c718edee977389e5a921151fad79009484346784f63edc44894bfc64c5cd","tier":null,"role":"editor"},{"type":"team","id":"e59cfabcc8cf2053","login":"ajur","name":"Adam Jurczyk","avatar_url":"https://avatars-next.observableusercontent.com/9780c718edee977389e5a921151fad79009484346784f63edc44894bfc64c5cd","tier":"starter_2024","role":"viewer"}],"comments":[],"custom_thumbnail":true,"trashed":false,"subscribed":null,"forks":2,"collection":{"id":"fe7a597113ba6d01","slug":"the-nature-of-code","title":"The Nature of Code","owner":{"id":"e59cfabcc8cf2053","login":"ajur","name":"Adam Jurczyk"}},"type":"notebook","body":{"title":"The Nature of Code - 5 - Autonomous Agents","cells":[{"id":0,"value":"$31","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":64,"value":"## Vehicles and Steering\n\nA lot of this chapter is referencing works of [Craig Reynolds](https://www.red3d.com/cwr/) who developed algorithmic **steering** behaviors for animated characters. Reynolds uses the word vehicle to describe his autonomous agents.\n\nReynolds described motion of idealized vehicles, with three layers:\n\n1. **Action selection**: A vehicle has a goal (or goals) and can choose an action (or a combination of actions) based on that goal.\n2. **Steering**: Once an action has been selected, the vehicle has to calculate its next move. Reynolds has developed a simple steering force formula that is used throughout the examples in this chapter: **steering force = desired velocity – current velocity**.\n3. **Locomotion**: or, _how_ the object moves, aka movement animation.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":71,"value":"vehicle = (\n {\n pos,\n fill = \"#f3fa\",\n w = 20,\n h = 10,\n r = 0,\n maxSpeed = 4,\n maxForce = 0.2,\n draw\n } = {},\n ...components\n) =>\n entity(\n position(pos),\n velocity(),\n acceleration(),\n rotation(),\n rotateWithDirection,\n graphics({\n fillColor: fill,\n draw: draw ?? (r > 0 ? drawCircle : drawTriangle)\n }),\n r > 0 ? circle(r) : rect(-w / 2, -h / 2, w, h),\n mass(),\n force(),\n {\n vehicle: {\n maxSpeed,\n maxForce\n }\n },\n ...components\n )","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":120,"value":"drawTriangle = (ctx, { rect }) => {\n const { x, y, w, h } = rect;\n ctx.beginPath();\n ctx.moveTo(x, y);\n ctx.lineTo(x + w, y + h / 2);\n ctx.lineTo(x, y + h);\n ctx.closePath();\n ctx.fill();\n ctx.stroke();\n ctx.closePath();\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":134,"value":"### Example 5.1: Seeking a Target","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":86,"value":"{\n const target = entity(position(400, 100), circle(20), graphics(), atMousePos);\n const seeker = vehicle({ pos: vec2(50, 50) }, seekEntity(target));\n return sim({\n width,\n visibility,\n systems: [\n atMousePosSys,\n seekEntitySys,\n movement,\n angularMovement,\n renderer\n ],\n entities: [target, seeker]\n });\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2204,"value":"applySeekForce = (ent, target, { arriveDist = 0, weight = 1 }) => {\n if (!ent.force || !ent.position || !ent.velocity || !ent.vehicle || !target) {\n return;\n }\n\n const desired = target.clone().sub(ent.position);\n\n let speed = ent.vehicle.maxSpeed;\n if (arriveDist > 0) {\n const dvl = desired.length();\n speed =\n dvl > arriveDist\n ? ent.vehicle.maxSpeed\n : MathUtils.mapLinear(dvl, 0, arriveDist, 0, ent.vehicle.maxSpeed);\n }\n\n ent.force.add(\n desired\n .setLength(speed)\n .sub(ent.velocity)\n .clampLength(0, ent.vehicle.maxForce)\n .multiplyScalar(weight)\n );\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1095,"value":"seekEntity = (target, { arriveDist = 0, weight = 1 } = {}) => ({\n seekEntity: {\n target,\n arriveDist,\n weight\n }\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1099,"value":"seekEntitySys = (env, ents) => {\n for (let entIdx = 0; entIdx < ents.length; ++entIdx) {\n const ent = ents[entIdx];\n if (ent.seekEntity?.target?.position) {\n const { target } = ent.seekEntity;\n applySeekForce(ent, target.position, ent.seekEntity);\n }\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":155,"value":"atMousePos = tag(\"atMousePos\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":159,"value":"atMousePosSys = (env, ents) => {\n for (let entIdx = 0; entIdx < ents.length; ++entIdx) {\n const ent = ents[entIdx];\n if (ent.atMousePos && ent.position && env.mouse.pos) {\n ent.position.copy(env.mouse.pos);\n }\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1329,"value":"### Example 5.2: How change in maxSpeed and maxForce affect movement","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":1341,"value":"example_5_2 = {\n const target = entity(\n position(400, 100),\n circle(20),\n graphics(),\n // debug,\n collisions({\n onCollide: (ent, _, env) => {\n ent.position.set(\n random(50, env.width - 50),\n random(30, env.height - 30)\n );\n }\n })\n );\n const seeker = vehicle(\n {\n pos: vec2(50, 50),\n maxSpeed: seekExampleFormSpec.maxSpeed,\n maxForce: seekExampleFormSpec.maxForce\n },\n seekEntity(target)\n );\n return sim({\n width,\n height: 400,\n visibility,\n systems: [\n testCollisions,\n seekEntitySys,\n movement,\n angularMovement,\n renderer\n // stateDump\n ],\n entities: [target, seeker]\n });\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1349,"value":"viewof seekExampleFormSpec = Inputs.form({\n maxSpeed: Inputs.range([0.01, 20], {\n label: \"Field resolution\",\n value: 3,\n step: 0.01\n }),\n maxForce: Inputs.range([0.001, 1], {\n label: \"Number of vehicles\",\n value: 0.2,\n step: 0.001\n })\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":192,"value":"### Exercise 5.1\n\n_Implement a fleeing steering behavior (the desired velocity is the same as seek, but pointed in the opposite direction)._\n\nTo have more control, vehicle will flee only when mouse is down.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":203,"value":"{\n const target = entity(position(400, 100), circle(20), graphics(), atMousePos);\n const runner = vehicle(\n { pos: vec2(50, 50) },\n fleeEntity(target, { maxDist: 100 }),\n onStageExit(\"wrap\")\n );\n return sim({\n width,\n visibility,\n systems: [\n onStageExitSys,\n atMousePosSys,\n fleeEntitySys,\n movement,\n angularMovement,\n renderer\n ],\n entities: [target, runner]\n });\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2228,"value":"applyFleeForce = (ent, target, { maxDist = 0, weight = 1 }) => {\n if (!ent.force || !ent.position || !ent.velocity || !ent.vehicle || !target) {\n return;\n }\n\n const desired = target.clone().sub(ent.position).negate();\n\n let speed = ent.vehicle.maxSpeed;\n if (maxDist > 0) {\n const dvl = desired.length();\n if (dvl > maxDist) {\n // do not flee from far enough target\n return;\n }\n speed = MathUtils.mapLinear(dvl, 0, maxDist, ent.vehicle.maxSpeed, 0);\n }\n\n ent.force.add(\n desired\n .setLength(speed)\n .sub(ent.velocity)\n .clampLength(0, ent.vehicle.maxForce)\n .multiplyScalar(weight)\n );\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":200,"value":"fleeEntity = (target, { maxDist = 0, weight = 1 } = {}) => ({\n fleeEntity: {\n target,\n maxDist,\n weight\n }\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":197,"value":"fleeEntitySys = (env, ents) => {\n for (let entIdx = 0; entIdx < ents.length; ++entIdx) {\n const ent = ents[entIdx];\n if (ent.fleeEntity?.target?.position) {\n applyFleeForce(ent, ent.fleeEntity.target.position, ent.fleeEntity);\n }\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":214,"value":"### Exercise 5.2\n\n_Create a sketch in which a vehicle’s maximum force and maximum speed don’t remain constant but vary according to environmental factors._\n\nSo, I've changed it a bit, and now both max speed and max force depend on environment, end this one is based on noise2d. Also, for fun, like fog of war, you wont see how env looks like until you enter it ;)","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":218,"value":"{\n const height = 300;\n const noiseXOffset = random(0, 1000);\n const noiseYOffset = random(0, 1000);\n const noiseScale = 0.1;\n const field = entity(\n position(),\n colorFieldGraphics,\n dataField(40, ({ x, y }, res) =>\n noise2D(noiseXOffset + x * noiseScale, noiseYOffset + y * noiseScale)\n )\n );\n const target = entity(position(400, 100), circle(20), graphics(), atMousePos);\n const seeker = vehicle(\n { pos: vec2(50, 50) },\n seekEntity(target),\n seekSpeedByDataField(field)\n );\n return sim({\n width,\n height,\n visibility,\n systems: [\n atMousePosSys,\n seekSpeedByDataFieldSys,\n seekEntitySys,\n movement,\n angularMovement,\n renderer\n ],\n entities: [field, target, seeker]\n });\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":355,"value":"seekSpeedByDataField = (field) => ({\n seekSpeedByDataField: field?.dataField\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":353,"value":"seekSpeedByDataFieldSys = (env, ents) => {\n for (let entIdx = 0; entIdx < ents.length; ++entIdx) {\n const ent = ents[entIdx];\n if (ent.seekSpeedByDataField && ent.vehicle) {\n const v = ent.seekSpeedByDataField.getAt(ent.position);\n ent.vehicle.maxForce = 0.2 * (1 - v);\n ent.vehicle.maxSpeed = 1 + 3 * v;\n }\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":277,"value":"colorFieldGraphics = graphics({\n draw: (ctx, self, env) => {\n const { field } = self.dataField;\n const w = field.resX;\n const h = field.resY;\n const cols = Math.ceil(env.width / w);\n const rows = Math.ceil(env.height / h);\n\n for (let col = 0; col < cols; ++col) {\n for (let row = 0; row < rows; ++row) {\n const v = field.get(col, row);\n if (v != null) {\n ctx.fillStyle = tinycolor\n .fromRatio({ r: 0.3, g: v, b: 0.3, a: 0.2 })\n .toString();\n ctx.fillRect(col * w, row * h, w, h);\n }\n }\n }\n }\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":750,"value":"dataField = (resolution, generator) => {\n const field = new InfiniField(resolution);\n const dataFieldProps = {\n dataField: {\n resolution,\n generator,\n field,\n getAt: (pos) => {\n let resp = dataFieldProps.dataField.field.getAt(pos);\n if (resp == null) {\n const vCell = vec2(\n Math.floor(pos.x / resolution),\n Math.floor(pos.y / resolution)\n );\n const cellCenter = vCell\n .clone()\n .addScalar(0.5)\n .multiplyScalar(resolution)\n .round();\n resp = dataFieldProps.dataField.generator(\n vCell,\n resolution,\n cellCenter\n );\n dataFieldProps.dataField.field.set(vCell.x, vCell.y, resp);\n }\n return resp;\n }\n }\n };\n return dataFieldProps;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":386,"value":"$32","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":480,"value":"### Exercise 5.3\n\n_Implement a seeking behavior with a moving target, often referred to as pursuit. In this case, your desired vector won’t point toward the object’s current position, but rather its future position as extrapolated from its current velocity._","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":484,"value":"{\n const target = entity(\n position(400, 100),\n velocity(2, 1),\n circle(20),\n graphics(),\n onStageExit(\"wrap\"),\n collisions({\n onCollide: (ent, coll, env) => {\n ent.position.set(\n random(50, env.width - 50),\n random(30, env.height - 30)\n );\n ent.velocity.set(random(-3, 3), random(-3, 3));\n }\n })\n );\n const seeker = vehicle({ pos: vec2(50, 50) }, pursueEntity(target), debug);\n return sim({\n width,\n height: 400,\n visibility,\n systems: [\n testCollisions,\n pursueEntitySys,\n movement,\n angularMovement,\n onStageExitSys,\n renderer\n ],\n entities: [target, seeker]\n });\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1375,"value":"pursueEntity = (ent, { futureSteps = 50, weight = 1 } = {}) => ({\n pursueEntity: {\n ent,\n futureSteps,\n weight\n }\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":486,"value":"pursueEntitySys = (env, ents) => {\n for (let entIdx = 0; entIdx < ents.length; ++entIdx) {\n const ent = ents[entIdx];\n if (\n ent.force &&\n ent.position &&\n ent.pursueEntity?.ent?.position &&\n ent.pursueEntity?.ent?.velocity\n ) {\n const { position: tPos, velocity: tVel } = ent.pursueEntity.ent;\n const steps = clamp(\n Math.floor(ent.position.distanceTo(tPos) / ent.vehicle.maxSpeed),\n 1,\n ent.pursueEntity.futureSteps\n );\n const target = tPos.clone().addScaledVector(tVel, steps);\n applySeekForce(ent, target, { weight: ent.pursueEntity.weight });\n\n if (ent.debug) {\n const { x, y } = target;\n env.ctx.strokeStyle = \"#f00\";\n env.ctx.beginPath();\n env.ctx.moveTo(x - 5, y);\n env.ctx.lineTo(x + 5, y);\n env.ctx.moveTo(x, y - 5);\n env.ctx.lineTo(x, y + 5);\n env.ctx.stroke();\n }\n }\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":542,"value":"### Example 5.1: Arriving at Target","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":546,"value":"{\n const target = entity(position(400, 100), circle(20), graphics(), atMousePos);\n const seeker = vehicle(\n { pos: vec2(50, 50), maxSpeed: 5 },\n seekEntity(target, { arriveDist: 100 })\n );\n return sim({\n width,\n visibility,\n systems: [\n atMousePosSys,\n seekEntitySys,\n movement,\n angularMovement,\n renderer\n ],\n entities: [target, seeker]\n });\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":580,"value":"### Exercise 5.4\n\n_Write the code for Reynolds’s wandering behavior. \nUse polar coordinates to calculate the vehicle’s target along a circular path._","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":595,"value":"{\n return sim({\n width,\n height: 400,\n visibility,\n systems: [wanderSys, angularMovement, movement, onStageExitSys, renderer],\n entities: [\n vehicle(\n { pos: vec2(200, 200), maxSpeed: 3, maxForce: 0.02 },\n velocity(2, 0),\n onStageExit(\"wrap\"),\n wander(),\n debug\n )\n ]\n });\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":589,"value":"wander = ({ offset = 100, radius = 30, dt = 0.005, weight = 1 } = {}) => ({\n wander: {\n offset,\n radius,\n dt,\n __nt: 0,\n weight\n }\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":620,"value":"wanderSys = (env, ents) => {\n for (let entIdx = 0; entIdx < ents.length; ++entIdx) {\n const ent = ents[entIdx];\n if (ent.velocity && ent.position && ent.wander) {\n ent.wander.__nt = ent.wander.__nt + ent.wander.dt;\n\n const t0 = ent.velocity\n .clone()\n .setLength(ent.wander.offset)\n .add(ent.position);\n\n const target = ent.velocity\n .clone()\n .setLength(ent.wander.radius)\n .rotateAround(\n vec2.ZERO,\n MathUtils.lerp(0, TWO_PI, noise1D(ent.wander.__nt))\n )\n .add(t0);\n\n applySeekForce(ent, target, { weight: ent.wander.weight });\n\n if (ent.debug) {\n env.ctx.strokeStyle = \"#aaa\";\n env.ctx.beginPath();\n env.ctx.moveTo(ent.position.x, ent.position.y);\n env.ctx.lineTo(t0.x, t0.y);\n env.ctx.lineTo(target.x, target.y);\n env.ctx.stroke();\n\n env.ctx.beginPath();\n env.ctx.arc(t0.x, t0.y, ent.wander.radius, 0, TWO_PI);\n env.ctx.stroke();\n }\n }\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":673,"value":"### Example 5.3 Stay within walls","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":685,"value":"{\n return sim({\n width,\n visibility,\n systems: [stayWithinWallsSys, movement, angularMovement, renderer],\n entities: [\n vehicle({ pos: vec2(150, 150) }, velocity(1, 2), stayWithinWalls())\n ]\n });\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":681,"value":"stayWithinWalls = ({ offset = 25, weight = 1 } = {}) => ({\n stayWithinWalls: {\n offset,\n weight\n }\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":675,"value":"stayWithinWallsSys = (env, ents) => {\n for (let entIdx = 0; entIdx < ents.length; ++entIdx) {\n const ent = ents[entIdx];\n if (ent.stayWithinWalls && ent.position) {\n const { offset, weight } = ent.stayWithinWalls;\n const { maxSpeed, maxForce } = ent.vehicle;\n let desired = null;\n if (ent.position.x < offset) desired = vec2(maxSpeed, ent.velocity.y);\n if (ent.position.x > env.width - offset)\n desired = vec2(-maxSpeed, ent.velocity.y);\n if (ent.position.y < offset) desired = vec2(ent.velocity.x, maxSpeed);\n if (ent.position.y > env.height - offset)\n desired = vec2(ent.velocity.x, -maxSpeed);\n\n if (desired) {\n ent.force.add(\n desired\n .setLength(maxSpeed)\n .sub(ent.velocity)\n .clampLength(0, maxForce)\n .multiplyScalar(weight)\n );\n }\n }\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":12,"value":"## Flow fields\n\nFlow field is basically grid with vectors pointing to some direction, with given resolution.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":734,"value":"sim({\n width,\n height: 100,\n visibility,\n systems: [renderer],\n entities: [flowField({ gen: () => vec2(1, 0) })]\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":738,"value":"But that was boring, lets add some randomness...","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":19,"value":"sim({\n width,\n height: 160,\n visibility,\n systems: [renderer],\n entities: [\n flowField({\n gen: () => vec2(1, 0).rotateAround(vec2.ZERO, random(0, TWO_PI))\n })\n ]\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":742,"value":"Ok, what about using Noise?","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":744,"value":"{\n return sim({\n width,\n visibility,\n systems: [renderer],\n entities: [\n flowField({\n res: noiseFlowFieldSpec.res,\n gen: ({ x, y }) =>\n vec2(1, 0).rotateAround(\n vec2.ZERO,\n MathUtils.lerp(\n 0,\n TWO_PI,\n noise2D(x * noiseFlowFieldSpec.dt, y * noiseFlowFieldSpec.dt) -\n 0.5\n )\n )\n })\n ]\n });\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":780,"value":"viewof noiseFlowFieldSpec = Inputs.form({\n res: Inputs.range([5, 50], {\n label: \"Field resolution\",\n value: 20,\n step: 1\n }),\n dt: Inputs.range([0.001, 0.1], {\n label: \"Noise density\",\n value: 0.05,\n step: 0.001\n })\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":768,"value":"flowField = ({ res = 20, gen }, ...comps) =>\n entity(position(0), dataField(res, gen), flowFieldGraphics, ...comps)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":21,"value":"// NOTE it will \"pre-fill\" field for whole visible area\nflowFieldGraphics = graphics({\n draw: (ctx, self, env) => {\n const { resolution, field, getAt } = self.dataField;\n const sprite = arrowSprite.withScale(resolution / arrowSprite.width);\n const r_half = resolution / 2;\n const cols = Math.ceil(env.width / resolution);\n const rows = Math.ceil(env.height / resolution);\n\n for (let col = 0; col < cols; ++col) {\n for (let row = 0; row < rows; ++row) {\n const x = col * resolution;\n const y = row * resolution;\n const v = getAt({ x, y });\n ctx.save();\n ctx.translate(x + r_half, y + r_half);\n ctx.rotate(v.angle());\n sprite.draw(ctx);\n ctx.restore();\n }\n }\n }\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":824,"value":"### Exercise 5.6\n\n_Write the code to calculate a flow field so that the vectors swirl in circles around the center of the canvas._ \nLets make it more fun, and swirl around mouse position!","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":827,"value":"{\n const height = 300;\n const center = vec2(width / 2, height / 2).round();\n return sim({\n width,\n height,\n visibility,\n systems: [centerFieldAtMousePosSys, renderer],\n entities: [\n flowField(\n {\n res: 25,\n gen: (_, res, pos) =>\n pos.clone().sub(center).normalize().rotateAround(vec2.ZERO, HALF_PI)\n },\n tag(\"centerFieldAtMousePos\")\n )\n ]\n });\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":853,"value":"centerFieldAtMousePosSys = (env, ents) => {\n for (let entIdx = 0; entIdx < ents.length; ++entIdx) {\n const ent = ents[entIdx];\n if (ent.centerFieldAtMousePos && ent.dataField && env.mouse.pos) {\n if (ent._lastMousePos && env.mouse.pos.equals(ent._lastMousePos))\n continue;\n ent._lastMousePos = env.mouse.pos;\n ent.dataField.generator = (_cr, _r, pos) =>\n pos\n .clone()\n .sub(env.mouse.pos)\n .normalize()\n .rotateAround(vec2.ZERO, HALF_PI);\n ent.dataField.field.reset();\n }\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":980,"value":"### Example 5.4 Flow-field following","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":994,"value":"$33","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":996,"value":"viewof followFlowFieldSpec = Inputs.form({\n vnum: Inputs.range([1, 1000], {\n label: \"Number of vehicles\",\n value: 200,\n step: 1\n }),\n res: Inputs.range([5, 50], {\n label: \"Field resolution\",\n value: 25,\n step: 1\n }),\n dt: Inputs.range([0.001, 0.3], {\n label: \"Noise density\",\n value: 0.02,\n step: 0.001\n }),\n height: Inputs.range([100, 1000], {\n label: \"Field height\",\n value: 400,\n step: 20\n }),\n smaxR: interval([0.1, 20], {\n label: \"Vehicle max Speed\",\n value: [3, 5],\n step: 0.1\n }),\n fmaxR: interval([0.01, 1], {\n label: \"Vehicle max follow force\",\n value: [0.1, 0.2],\n step: 0.01\n })\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":983,"value":"followFlow = (flowFieldEntity, { weight = 1 } = {}) => ({\n followFlow: {\n target: flowFieldEntity,\n weight\n }\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":989,"value":"followFlowSys = (env, ents) => {\n for (let entIdx = 0; entIdx < ents.length; ++entIdx) {\n const ent = ents[entIdx];\n if (\n !ent.force ||\n !ent.position ||\n !ent.vehicle ||\n !ent.followFlow?.target?.dataField\n ) {\n continue;\n }\n\n const desired = ent.followFlow.target.dataField.getAt(ent.position);\n\n ent.force.add(\n desired\n .clone()\n .setLength(ent.vehicle.maxSpeed)\n .sub(ent.velocity)\n .clampLength(0, ent.vehicle.maxForce)\n .multiplyScalar(ent.followFlow.weight)\n );\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1038,"value":"changeFlowOnClickSys = (env, ents) => {\n for (let entIdx = 0; entIdx < ents.length; ++entIdx) {\n const ent = ents[entIdx];\n if (ent.dataField && ent.changeFlowOnClick && env.mouse.click) {\n const offX = random(0, 1000000);\n const offY = random(0, 1000000);\n ent.dataField.generator = ({ x, y }) =>\n vec2(1, 0).rotateAround(\n vec2.ZERO,\n MathUtils.lerp(\n 0,\n TWO_PI,\n noise2D(\n offX + x * followFlowFieldSpec.dt,\n offY + y * followFlowFieldSpec.dt\n ) - 0.5\n )\n );\n ent.dataField.field.reset();\n }\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1054,"value":"### Exercise 5.7\n_Adapt the flow-field example so the vectors change over time. (Hint: Try using the third dimension of Perlin noise!)_","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":1056,"value":"{\n const height = 300;\n const ff = flowField(\n {\n res: 25,\n gen: ({ x, y }) =>\n vec2(1, 0).rotateAround(\n vec2.ZERO,\n MathUtils.lerp(0, TWO_PI, noise2D(x * 0.02, y * 0.02) - 0.5)\n )\n },\n changeFlowInTime()\n );\n return sim({\n width,\n height: height,\n visibility,\n systems: [\n changeFlowInTimeSys,\n followFlowSys,\n angularMovement,\n movement,\n onStageExitSys,\n renderer\n ],\n entities: [\n ff,\n ...Array.from({ length: 200 }, () =>\n vehicle(\n {\n pos: vec2(random(0, width), random(0, height)),\n maxSpeed: random(1, 2),\n maxForce: random(0.01, 0.03)\n },\n force(vec2().random()),\n onStageExit(\"wrap\"),\n followFlow(ff)\n )\n )\n ]\n });\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1059,"value":"changeFlowInTimeSys = (env, ents) => {\n for (let entIdx = 0; entIdx < ents.length; ++entIdx) {\n const ent = ents[entIdx];\n if (ent.dataField && ent.changeFlowInTime) {\n ent.dataField.generator = ({ x, y }) =>\n vec2(1, 0).rotateAround(\n vec2.ZERO,\n MathUtils.lerp(\n 0,\n TWO_PI,\n noise3D(\n x * followFlowFieldSpec.dt,\n y * followFlowFieldSpec.dt,\n performance.now() * ent.changeFlowInTime.changeFactor\n ) - 0.5\n )\n );\n ent.dataField.field.reset();\n }\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1266,"value":"changeFlowInTime = (changeFactor = 0.0001) => ({\n changeFlowInTime: {\n changeFactor: changeFactor\n }\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1203,"value":"### Bonus - flow field generative art","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":1207,"value":"$34","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1551,"value":"## Path Following\n\nNext steering behavior. The book also here explains the _dot product_ of two vectors, _normals_, distance to line and way to compute angle between vectors.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":1480,"value":"### Excercise 5.9\n_Create a sketch that shows the angle between two vectors._ \n**Note:** I've added extra handling of direction with sign, so its similar to example in book. \n**Note 2:** Sign is reversed in comparison to cartesian, as we have y axis going down, not up.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":1482,"value":"$35","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1555,"value":"### Example 5.5 & 5.7: Creating a Path Object & multiple segments\n\nWith a twist - lets make it editable and add few more configs.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":1566,"value":"sim({\n width,\n height: 200,\n visibility,\n systems: [entityDragging, pathEditingSys, renderer],\n entities: [\n path({\n pos: vec2(50, 50),\n vs: [vec2(150, 50), vec2(400, -20), vec2(width - 100, 100)],\n editable: true,\n closed: true\n })\n ]\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1728,"value":"I _might_ have gone a little bit overboard with the editing capabilities 😅\n\n- right dot is start and moves whole path when dragged\n- blue dots are editable (draggable) vertices\n- right click on blue vertex to remove it (if more than one)\n- left click on path (when purple dot visible) to add vertex (click and drag on purple dot to add and edit vertex in single move)\n- green dot changes path _radius_ (or max follow distance)","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":1558,"value":"path = (\n { pos, vs, r = 25, color = \"#33f\", closed = false, editable = false } = {},\n ...components\n) =>\n entity(\n position(pos),\n graphics({\n lineColor: tinycolor(color).toHexString(),\n fillColor: tinycolor(color).setAlpha(0.2).toHex8String(),\n draw: drawPath\n }),\n editable && draggable,\n circle(6),\n {\n path: {\n vertices: [vec2(), ...vs, ...(closed ? [vec2()] : [])],\n radius: r,\n closed,\n editable\n }\n },\n ...components\n )","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1564,"value":"$36","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1611,"value":"$37","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1735,"value":"These two functions will be useful also for path following.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":1700,"value":"getNormalToSegment = (pos, start, end) => {\n const va = vec2().subVectors(pos, start);\n const vb = vec2().subVectors(end, start).normalize();\n vb.multiplyScalar(va.dot(vb));\n vb.add(start);\n return vb;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1704,"value":"getNormalOnSegment = (pos, start, end) => {\n const n = getNormalToSegment(pos, start, end);\n if (\n n.x < Math.min(start.x, end.x) ||\n n.x > Math.max(start.x, end.x) ||\n n.y < Math.min(start.y, end.y) ||\n n.y > Math.max(start.y, end.y)\n ) {\n return null;\n }\n return n;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1737,"value":"### Example 5.6: Simple Path Following","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":1750,"value":"{\n const pathToFollow = path({\n pos: vec2(0, 100),\n vs: [vec2(width, 30)]\n });\n return sim({\n width,\n height: 300,\n visibility,\n systems: [\n entityDragging,\n pathEditingSys,\n followFirstPathSegmentSys,\n angularMovement,\n movement,\n onStageExitSys,\n renderer\n ],\n entities: [\n pathToFollow,\n vehicle(\n { pos: vec2(200, 200), maxSpeed: 3, maxForce: 0.05 },\n velocity(2, 0),\n onStageExit(\"wrap\"),\n followPath(pathToFollow)\n ),\n vehicle(\n { pos: vec2(100, 200), maxSpeed: 3, maxForce: 0.05 },\n velocity(2, 0),\n onStageExit(\"wrap\"),\n followPath(pathToFollow)\n )\n ]\n });\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1741,"value":"followPath = (path, { maxFuture = 30, weight = 1 } = {}) => ({\n followPath: {\n path,\n maxFuture: maxFuture,\n weight\n }\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1744,"value":"$38","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1832,"value":"### Example 5.8: Path Following","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":1859,"value":"{\n const pathToFollow = path({\n pos: vec2(30, 115),\n vs: [vec2(220, -40), vec2(400, -40), vec2(600, 80), vec2(788, 44)],\n editable: true\n });\n return sim({\n width,\n height: 300,\n visibility,\n systems: [\n entityDragging,\n pathEditingSys,\n followPathSys,\n angularMovement,\n movement,\n renderer,\n onStageExitSys\n ],\n entities: [\n pathToFollow,\n vehicle(\n { pos: vec2(200, 200), maxSpeed: 3, maxForce: 0.05 },\n velocity(2, 0),\n onStageExit(\"wrap\"),\n debug,\n followPath(pathToFollow, { maxFuture: 50 })\n ),\n vehicle(\n { pos: vec2(100, 200), maxSpeed: 2, maxForce: 0.1 },\n velocity(2, 0),\n onStageExit(\"wrap\"),\n debug,\n followPath(pathToFollow)\n )\n ]\n });\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1837,"value":"getNormalOnPath = (pos, pathVertices) => {\n let i,\n minNormal,\n segIdx,\n minDist = Infinity;\n for (i = 0; i < pathVertices.length - 1; ++i) {\n const normal =\n getNormalOnSegment(pos, pathVertices[i], pathVertices[i + 1]) ||\n pathVertices[i + 1];\n const ndist = normal?.distanceTo(pos);\n if (normal && ndist < minDist) {\n minNormal = normal;\n minDist = ndist;\n segIdx = i;\n }\n }\n return [minNormal, minDist, segIdx];\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1834,"value":"$39","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1907,"value":"## Complex Systems\n\n_A complex system is typically defined as a system that’s more than the sum of its parts. While the individual elements of the system may be incredibly simple and easily understood, the behavior of the system as a whole can be highly complex, intelligent, and difficult to predict._","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":1911,"value":"### Example 5.9: Separation\n\n_Avoid colliding with your neighbors!_","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":1915,"value":"{\n const height = 200;\n return sim({\n width,\n height: height,\n visibility,\n systems: [separateSys, angularMovement, movement, onStageExitSys, renderer],\n entities: [\n ...Array.from({ length: 200 }, () =>\n vehicle(\n {\n pos: vec2(random(width), random(height)),\n maxSpeed: 2,\n maxForce: 0.02\n },\n rotation(random(TWO_PI)),\n onStageExit(\"wrap\"),\n separate()\n )\n )\n ]\n });\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1918,"value":"separate = ({ dist = 0, weight = 1 } = {}) => ({\n separate: {\n dist,\n weight\n }\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1922,"value":"$3a","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1966,"value":"### Exercise 5.12\n_Create a cohere() method that follows the opposite logic of separate(): if a vehicle is beyond a certain distance, steer toward that vehicle. This will keep the group together._","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":1976,"value":"{\n const height = 200;\n return sim({\n width,\n height: height,\n visibility,\n systems: [\n simpleCohereSys,\n angularMovement,\n movement,\n onStageExitSys,\n renderer\n ],\n entities: [\n ...Array.from({ length: 200 }, () =>\n vehicle(\n {\n pos: vec2(random(width), random(height)),\n maxSpeed: 2,\n maxForce: 0.02\n },\n rotation(random(TWO_PI)),\n onStageExit(\"wrap\"),\n simpleCohere()\n )\n )\n ]\n });\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1970,"value":"simpleCohere = (dist = 0, { weight = 1 } = {}) => ({\n cohere: {\n dist,\n weight\n }\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1973,"value":"simpleCohereSys = (env, ents) => {\n for (let entIdx = 0; entIdx < ents.length; ++entIdx) {\n const ent = ents[entIdx];\n if (!ent.position || !ent.vehicle || !ent.cohere) continue;\n\n const minDist =\n ent.cohere.dist ||\n 4 * Math.max(ent.rect?.w ?? 0, ent.rect?.h ?? 0, ent.circle?.radius ?? 0);\n\n let sum = vec2();\n let count = 0;\n\n for (const other of ents) {\n if (ent === other || !ent.cohere) continue;\n const dist = ent.position.distanceTo(other.position) || 0.1;\n if (dist <= minDist) continue;\n const diff = vec2().subVectors(other.position, ent.position);\n sum.add(diff);\n ++count;\n }\n\n if (count > 0) {\n ent.force.add(\n sum\n .setLength(ent.vehicle.maxSpeed)\n .sub(ent.velocity)\n .clampLength(0, ent.vehicle.maxForce)\n .multiplyScalar(ent.cohere.weight)\n );\n }\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1980,"value":"### Exercise 5.13\n_Add the separation force to path following to create a simulation of Reynolds’s group path following._","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":1983,"value":"$3b","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2299,"value":"## Combining Behaviors\n\nBefore this chapter, I had different approach to applying `seek` and `flee` forces. In contrast to book, as in general I don't follow code exactly, as I'm using home brew ECS not classes and methods.\n\nBefore, `seek` had its own component with target, `seekSys` applied seeking force, and other systems (like path following etc) changed the target on the seek component.\n\nBut for this chapter, where there where introduced not only weights but also potentially multiple seek targets, i made a huge refactor to move applying seek logic to separate function, that is only called within behavioral systems. (Although, I still placed weights in separate components, not in some single function).\n\n(This is also why code at the beginning of a chapter might be a lot more complicated than examples from book at that point, as I refactor it while progressing with content, and it is evolving with each new example and exercise.)","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":2310,"value":"### Example 5.10: Combining Steering Behaviors (Seek and Separate)","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":2312,"value":"{\n const height = 400;\n const target = entity(\n position(400, 100),\n circle(20),\n graphics(),\n atMousePos,\n hidden\n );\n return sim({\n width,\n height: height,\n visibility,\n systems: [\n example_5_10_formSystem,\n atMousePosSys,\n seekEntitySys,\n separateSys,\n angularMovement,\n movement,\n onStageExitSys,\n renderer\n ],\n entities: [\n target,\n ...Array.from({ length: 100 }, () =>\n vehicle(\n {\n pos: vec2(random(width), random(height)),\n maxSpeed: 2,\n maxForce: 0.02,\n r: 10\n },\n rotation(random(TWO_PI)),\n onStageExit(\"wrap\"),\n separate({ weight: 1.5 }),\n seekEntity(target, { weight: 0.5 })\n )\n )\n ]\n });\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2357,"value":"viewof example_5_10_form = Inputs.form({\n separateWeight: Inputs.range([0, 2], {\n label: \"Separate weight\",\n step: 0.01,\n value: 1.5\n }),\n seekWeight: Inputs.range([0, 2], {\n label: \"Seek weight\",\n step: 0.01,\n value: 0.5\n })\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2556,"value":"#### Form without simulation restart\n\nUsually forms in Observable just reset whole cell, thus preventing changes from inputs in time with state intact. To overcome this (usually useful) feature, we have to make indirect relation between form and simulation cell.\n\nFor this, I created the update system, that exposes 'update' method taking in value of input form, and performs the state change.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":2527,"value":"example_5_10_formSystem = {\n let change = null;\n const sys = (env, ents) => {\n if (!change) return;\n for (let entIdx = 0; entIdx < ents.length; ++entIdx) {\n const ent = ents[entIdx];\n ent.separate && (ent.separate.weight = change.separateWeight);\n ent.seekEntity && (ent.seekEntity.weight = change.seekWeight);\n }\n change = null;\n };\n sys.update = (newVal) => (change = newVal);\n return sys;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2561,"value":"Single cell that calls update method with form value, is bound to form, so reevaluates on form changes, but doesn't change directly the system cell, so doesn't force simulation restart.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":2541,"value":"example_5_10_formSystem.update(example_5_10_form)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2365,"value":"### Exercise 5.14\n_Modify Example 5.10 so that the behavior weights change over time. For example, what if the weights were calculated according to a sine wave or Perlin noise? Or what if some vehicles are more concerned with seeking and others are more concerned with separating? Can you introduce other steering behaviors as well?_","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":2367,"value":"$3c","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2420,"value":"## Flocking\n\n_**Flocking** is a group animal behavior found in many living creatures, such as birds, fish, and insects. In 1986, Reynolds created a computer simulation of flocking behavior and documented the algorithm in his paper “Flocks, Herds, and Schools: A Distributed Behavioral Model.”_\n\nReynolds uses the term boid (a made-up word that refers to a birdlike object) to describe the elements of a flocking system.\n\nThree rules govern flocking:\n- **Separation** (aka avoidance): Steer to avoid colliding with your neighbors.\n- **Alignment** (aka copy): Steer in the same direction as your neighbors.\n- **Cohesion** (aka center): Steer toward the center of your neighbors (stay with the group).\n\n![rules image](https://natureofcode.com/static/8ae3ebaa63c1251f94d0c761e3979ada/e1a67/05_steering_36.webp)","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":2425,"value":"_Separation_ was already done for example 5.9.\n\nWe are left with _alignment_, and _cohesion_ (this was attempted in exercise 5.12 but in flocking it has different definition that in example).\n\nBoth are also detecting items only within some view distance.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":2440,"value":"align = ({ viewDist = 50, fov = 0, weight = 1, debug = false } = {}) => ({\n align: {\n viewDist,\n weight,\n fov,\n debug\n }\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2445,"value":"$3d","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2454,"value":"cohere = ({ viewDist = 50, weight = 1 } = {}) => ({\n cohere: {\n viewDist,\n weight\n }\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2458,"value":"cohereSys = (env, ents) => {\n for (let entIdx = 0; entIdx < ents.length; ++entIdx) {\n const ent = ents[entIdx];\n if (!ent.position || !ent.vehicle || !ent.cohere) continue;\n\n const { viewDist, weight } = ent.cohere;\n\n const sum = vec2();\n let count = 0;\n\n const entsToCheck = env.query.pointsInRange(ent.position, viewDist);\n\n let otherIdx, other;\n for (otherIdx = 0; otherIdx < entsToCheck.length; ++otherIdx) {\n other = entsToCheck[otherIdx];\n if (ent !== other && other.cohere && other.velocity) {\n sum.add(other.position);\n ++count;\n }\n }\n\n if (count > 0) {\n sum.divideScalar(count);\n applySeekForce(ent, sum, { weight });\n }\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2734,"value":"### Example 5.11: Flocking\n_(hold mouse to add more boids)_\n\nAlso, added controls for simulation, so this is also solution for **exercise 5.18**","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":2467,"value":"{\n const height = 500;\n const createBoid = (pos) =>\n vehicle(\n {\n pos: pos?.clone() ?? vec2(random(width), random(height)),\n maxSpeed: 2,\n maxForce: 0.02\n },\n rotation(random(TWO_PI)),\n onStageExit(\"wrap\"),\n separate({ dist: 25, weight: 1.5 }),\n align({ viewDist: 50, weight: 1 }),\n cohere({ viewDist: 50, weight: 1 })\n );\n const addBoidOnMouseDown = (env, ents) => {\n if (env.mouse.main && !env.mouse.handled) {\n env.addEntity(createBoid(env.mouse.pos.clone()));\n }\n };\n return sim({\n width,\n height: height,\n visibility,\n queryEngine: new BinLatticeQueryEngine(width, height, 20),\n systems: [\n addBoidOnMouseDown,\n exercise_5_18_formSystem,\n entityEraserSys(),\n separateSys,\n alignSys,\n cohereSys,\n angularMovement,\n movement,\n onStageExitSys,\n renderer,\n showStats\n ],\n entities: [...Array.from({ length: 300 }, createBoid)]\n });\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2817,"value":"$3e","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2820,"value":"exercise_5_18_formSystem = {\n let change = null;\n const sys = (env, ents) => {\n if (!change) return;\n for (let entIdx = 0; entIdx < ents.length; ++entIdx) {\n const ent = ents[entIdx];\n if (ent.vehicle) {\n ent.vehicle.maxSpeed = change.vehicle.speed;\n ent.vehicle.maxForce = change.vehicle.force;\n }\n if (ent.align) {\n ent.align.viewDist = change.align.dist;\n ent.align.fov = change.align.fov;\n ent.align.weight = change.align.weight;\n }\n if (ent.separate) {\n ent.separate.dist = change.separate.dist;\n ent.separate.weight = change.separate.weight;\n }\n if (ent.cohere) {\n ent.cohere.viewDist = change.cohere.dist;\n ent.cohere.weight = change.cohere.weight;\n }\n }\n change = null;\n };\n sys.update = (newVal) => (change = newVal);\n return sys;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2822,"value":"exercise_5_18_formSystem.update(exercise_5_18_form)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2632,"value":"### Exercise 5.15\n\n_Can you rewrite the align() method so that boids see only other boids that fall within a direct line of sight?_\n\nSo, I've added `fov` param to `align` (plus debug drawning), that is degrees of field of view for our boid.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":2569,"value":"$3f","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2801,"value":"viewof exercies_5_15_form = Inputs.form({\n viewDist: Inputs.range([1, 200], {\n label: \"View distance\",\n step: 1,\n value: 40\n }),\n fov: Inputs.range([1, 180], { label: \"Field of view\", step: 1, value: 100 }),\n weight: Inputs.range([0, 3], { label: \"Weight\", step: 0.01, value: 1.5 }),\n debug: Inputs.toggle({ label: \"Enable debug\", value: true })\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2805,"value":"exercise_5_15_formSystem = {\n let change = null;\n const sys = (env, ents) => {\n if (!change) return;\n for (let entIdx = 0; entIdx < ents.length; ++entIdx) {\n const ent = ents[entIdx];\n if (ent.align) {\n ent.align.viewDist = change.viewDist;\n ent.align.fov = change.fov;\n ent.align.weight = change.weight;\n ent.align.debug = change.debug;\n }\n }\n change = null;\n };\n sys.update = (newVal) => (change = newVal);\n return sys;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2809,"value":"exercise_5_15_formSystem.update(exercies_5_15_form)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2653,"value":"### Exercise 5.16\n\n_Combine flocking with other steering behaviors._","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":2655,"value":"$40","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2724,"value":"- basic flocking (blue boids - hold mouse to add more)\n- path following (yellow/pink boids - hold mouse with ctrl/alt to add more)\n- Predator seeking slowest boid, and applying fleeing to other boids (red boids - click mouse with shift to add more)\n\n_right click to remove boids_\n\nAlso, this one shows how not under-performant my simulation is, with ~300 boids causing frame drop on my machine.\n\nBtw, frame drop shows also that my sim is frame-dependant, not time-dependant.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":2946,"value":"onDetectFollowWeek = (detectedIds, env, self) => {\n let lowEnt = null;\n let lowVel = Infinity;\n for (const id of detectedIds) {\n const ent = env.getEntity(id);\n const vel = ent?.velocity?.lengthSq();\n if (vel < lowVel) {\n lowVel = vel;\n lowEnt = ent;\n }\n applyFleeForce(ent, self.position, { weight: 2.5 });\n }\n if (lowEnt?.position) {\n applySeekForce(self, lowEnt.position, { weight: 1.5 });\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2737,"value":"### Exercise 5.17\n\n_In his book The Computational Beauty of Nature (Bradford Books, 2000), Gary Flake describes a fourth rule for flocking, view: “Move laterally away from any boid that blocks the view.” Have your boids follow this rule._","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":2739,"value":"$41","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2785,"value":"viewof exercies_5_17_form = Inputs.form({\n viewDist: Inputs.range([1, 200], {\n label: \"View distance\",\n step: 1,\n value: 50\n }),\n fov: Inputs.range([1, 180], { label: \"Field of view\", step: 1, value: 120 }),\n weight: Inputs.range([0, 3], { label: \"Weight\", step: 0.01, value: 1.5 }),\n debug: Inputs.toggle({ label: \"Enable debug\", value: false })\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2742,"value":"freeView = ({ viewDist = 50, fov = 0, weight = 1, debug = false } = {}) => ({\n freeView: {\n viewDist,\n weight,\n fov,\n debug\n }\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2744,"value":"$42","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2779,"value":"exercise_5_17_formSystem = {\n let change = null;\n const sys = (env, ents) => {\n if (!change) return;\n for (let entIdx = 0; entIdx < ents.length; ++entIdx) {\n const ent = ents[entIdx];\n if (ent.freeView) {\n ent.freeView.viewDist = change.viewDist;\n ent.freeView.fov = change.fov;\n ent.freeView.weight = change.weight;\n ent.freeView.debug = change.debug;\n }\n }\n change = null;\n };\n sys.update = (newVal) => (change = newVal);\n return sys;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2795,"value":"exercise_5_17_formSystem.update(exercies_5_17_form)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3063,"value":"### Exercise 5.19\n_Visualize the flock in an entirely different way._","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":2974,"value":"$43","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3070,"value":"viewof ex_5_19_blenMode = Inputs.radio(\n [\n \"lighter\",\n \"screen\",\n \"multiply\",\n \"overlay\",\n \"darken\",\n \"color-dodge\",\n \"color-burn\",\n \"hard-light\",\n \"soft-light\"\n ],\n { label: \"Blend mode\", value: \"lighter\" }\n)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3079,"value":"## Algorithmic Efficiency (or: Why Does My Sketch Run So Slowly?)\n\nGroup behavior are kinda heavy, not only there is lot to draw, but there is also a lot of computation.\n\nMy simplistic ECS is built from systems, where each system is at least of ${tex`O(N)`} complexity, due to passing through all entities. But group flocking systems have to not only go through all boids, but also for each boid check relation to other boids, thus having ${tex`O(n^2)`} complexity. Even if most checks stops at distance check, it still kills performance when for _1000_ boids there is at least _3000000_ checks (3 sub systems x 1000 boids x 1000 checks for other boids).\n\nHeck, most of my recent examples are dying with more than 300 boids :/\n","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":3225,"value":"### Bin-lattice Spatial subdivision\n\nIn paper from 2000 Reynolds proposed **[bin](https://en.wikipedia.org/wiki/Bin_%28computational_geometry%29)-lattice spatial subdivision** for optimizing flocking and other group simulations. It relies on dividing space in grid, or _bins_, and for each boid check only relevent bins (that depends on range of check and grid resolution, but assuming that any given detector range is lower than grid resolution, than it is enough to check 9 bins - the one containing, and neighbors).","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":3492,"value":"$44","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3468,"value":"$45","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3222,"value":"### QuadTree\n\nA [quadtree](https://en.wikipedia.org/wiki/Quadtree) data structure is another useful spatial partitioning method, that is also better for cases of non-even distribution of points/objects.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":3329,"value":"$46","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3600,"value":"$47","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3603,"value":"$48","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3555,"value":"### Example 5.12: Bin-Lattice Spatial Subdivision & Exercise 5.20 Quad tree - Flocking simulation\n\nI've moved it down to better compare all the different approaches.\n\nOverall, spatial subdivision allows for easy tripled or even quadrupled number of boids without dropping frame rates! (on my machine, baseline is 120fps). Thats significant improvement!","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":3098,"value":"$49","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3793,"value":"viewof spatialSubdivision = Inputs.form({\n engine: Inputs.radio(\n [\n \"none\",\n \"binLattice\",\n \"binLatticeBetterCirc\",\n \"quadtree\",\n \"quadtreeNoSkip\",\n \"quadtreeSimpleSkip\",\n \"quadtreeOnlyLeaves\",\n \"quadtreeWithPool\"\n ],\n {\n label: \"Spatial sub division type\",\n value: \"binLatticeBetterCirc\"\n }\n ),\n blRes: Inputs.range([1, 200], {\n label: \"Bin-Lattice resolution\",\n step: 1,\n value: 50\n }),\n qtLmit: Inputs.range([1, 20], { label: \"QuadTree limit\", step: 1, value: 4 }),\n debug: Inputs.toggle({ label: \"Debug\", value: true }),\n bnum: Inputs.range([100, 2000], {\n label: \"Initial boids\",\n step: 10,\n value: 1000\n })\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3965,"value":"$4a","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":4014,"value":"Alt version of Bin-lattice, that uses slightly optimized circle containment checks - performs a bit better, especially with higher resolutions.\nThis is also the only version that allowed me to add almost 3k boids before dropping below 30fps.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":3845,"value":"$4b","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":4020,"value":"QuadTree version with no check for circle.contains for skipping checks at all","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":3816,"value":"$4c","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":4025,"value":"QuadTree version with checking only circle inner box for skipping","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":3906,"value":"$4d","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":4029,"value":"QuadTree version with points stored only in leave nodes (so, on split they are redistributed)","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":3825,"value":"$4e","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":4031,"value":"Best of all QuadTree versions, resolves issue with creating lots of new objects when recreating tree on each frame. Could be combined with some versions of NoSkip/SimpleSkip for even a bit better results, but still lower than `BinLatticeWithCircQueryEngine`;","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":3868,"value":"$4f","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":4038,"value":"### Other optimizations\n\nAs in book, I've also went through past code and tried to minimize creation of new vector objects and used squared values for comparing distances.\n\nBut biggest change I introduced everywhere, as it turned out to be a huge hit on performance, was to get rid of iterators!\n\nAt first I've noticed it when I used generator for quad tree - it was even slower than without it! Than after some reading and checks, turned out that `for...of` is also a no-no as it also internally calls iterator, thus I replaced almost all of it with classic `for` loop. This was a huge boost in speed.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":7,"value":"## Appendix","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":9,"value":"import {\n vec2,\n box2,\n PI,\n TWO_PI,\n HALF_PI,\n random,\n sim,\n tag,\n entity,\n rect,\n circle,\n position,\n rotation,\n graphics,\n drawCircle,\n movement,\n angularMovement,\n rotateWithDirection,\n velocity,\n clamp,\n clampVelocity,\n acceleration,\n mass,\n force,\n hidden,\n renderer,\n customRenderer,\n onStageExit,\n onStageExitSys,\n collisions,\n testCollisions,\n detector,\n detectorSys,\n draggable,\n entityDragging,\n entityEraserSys,\n debug,\n stateDump,\n showStats,\n ImgSprite,\n sprite,\n noise2D,\n noise1D,\n noise3D,\n tinycolor,\n MathUtils,\n justCanvas,\n QueryEngine,\n circle2\n} from \"@ajur/the-nature-of-code-tools\"","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3381,"value":"d3 = require(\"d3-random\")","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":39,"value":"slimArrowIcon = FileAttachment(\"Slim Arrow Icon.png\").image()","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":41,"value":"arrowSprite = ImgSprite.fromSprite(slimArrowIcon)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1161,"value":"import { interval } from \"@mootari/range-slider\"","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3017,"value":"particles22 = FileAttachment(\"particles2@2.png\").image()","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3018,"value":"particlesSprite = (col, row) => ImgSprite.fromTile(particles22, col, row, 64)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3021,"value":"starSprite = particlesSprite(1, 0)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3026,"value":"blueCircleSprite = particlesSprite(0, 1)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"}],"files":"$W50","stdlib":"1","titling":"auto"}} 30:"$2f:body"