Sugor Dev Almanac
doc 6 of 6

Part 05 — When the flock gets big

You will build: A timing harness that prints microseconds per frame spent finding neighbours, a spatial hash that replaces the every-agent-checks-every-agent loop, and a before-and-after table recorded at 100, 400 and 1000 agents on your own machine.

Part 04 handed collision to the avoidance server, which is the one part of this shelf you did not have to write. Everything else in the flock is still yours, and all of it shares a shape nobody has looked at yet: to steer, an agent has to know who is nearby, and the only way it knows that is by asking every other agent where it is.

At 60 agents that costs nothing you can perceive. The prototype runs, the flock looks alive, the work feels finished. This part is about the count where it stops being free, and about the fact that you cannot tell when that happens by looking at the screen.

Measure before you change anything#

Add 300 more agents to a working flock and the frame rate falls over. Ask three developers why and you get three answers: too many nodes, the renderer, the physics server. All three are plausible. One of them might even be right on your machine. None of them are worth acting on, because you can find out instead of guessing.

Make a new script, flock_perf.gd. It is a bag of static counters — every agent adds the time its own neighbour search took, and once per frame a total gets folded into a rolling average.

class_name FlockPerf
extends RefCounted

const SAMPLE_FRAMES: int = 60

static var _frame_usec: int = 0
static var _total_usec: int = 0
static var _worst_usec: int = 0
static var _frames: int = 0

static func reset() -> void:
	_frame_usec = 0
	_total_usec = 0
	_worst_usec = 0
	_frames = 0

static func add_usec(usec: int) -> void:
	_frame_usec += usec

static func end_frame(agent_count: int) -> void:
	_total_usec += _frame_usec
	if _frame_usec > _worst_usec:
		_worst_usec = _frame_usec
	_frame_usec = 0
	_frames += 1
	if _frames < SAMPLE_FRAMES:
		return
	var average: float = float(_total_usec) / float(_frames)
	print("%d agents | %.0f us/frame avg | %d us worst | %.2f ms avg" % [
		agent_count, average, _worst_usec, average / 1000.0
	])
	_total_usec = 0
	_worst_usec = 0
	_frames = 0

Two details in there are not decoration. The rolling average over 60 frames exists because a single frame's reading is noise — the operating system schedules other work, the editor repaints, and one bad sample will convince you of something false. The worst-frame number exists because an average hides spikes, and a spike is what a player feels.

reset() exists for a reason you will hit within ten minutes: static variables live as long as the process, not as long as the scene. Reload the scene from the editor and the counters keep accumulating from the previous run unless something clears them.

Time.get_ticks_usec() returns microseconds since the engine started, and it is monotonic — it never goes backwards. Microseconds, not milliseconds: at 60 agents the whole search is well under a millisecond, so a millisecond timer would report zero and you would conclude the search is free.

The agent side#

Here is the flock agent as it stands, with the timer wrapped around the part being measured. Nothing else about it has changed.

class_name Boid
extends CharacterBody2D

@export var neighbour_radius: float = 60.0
@export var max_speed: float = 180.0
@export var max_force: float = 600.0
@export var cohesion_weight: float = 1.0
@export var alignment_weight: float = 1.2
@export var separation_weight: float = 1.6

var flock: Array[CharacterBody2D] = []
var grid: FlockGrid = null
var area: Vector2 = Vector2(1152.0, 648.0)

func _physics_process(delta: float) -> void:
	var start: int = Time.get_ticks_usec()
	var steering: Vector2 = _cohesion() * cohesion_weight \
		+ _alignment() * alignment_weight \
		+ _separation() * separation_weight
	FlockPerf.add_usec(Time.get_ticks_usec() - start)

	var desired: Vector2 = steering.limit_length(max_speed)
	if desired.length_squared() < 1.0:
		desired = velocity
	velocity = velocity.move_toward(desired, max_force * delta)
	move_and_slide()
	_wrap()

func _cohesion() -> Vector2:
	var centre: Vector2 = Vector2.ZERO
	var count: int = 0
	for other: CharacterBody2D in flock:
		if other == self:
			continue
		if global_position.distance_to(other.global_position) <= neighbour_radius:
			centre += other.global_position
			count += 1
	if count == 0:
		return Vector2.ZERO
	return (centre / float(count) - global_position).limit_length(max_speed)

func _alignment() -> Vector2:
	var heading: Vector2 = Vector2.ZERO
	var count: int = 0
	for other: CharacterBody2D in flock:
		if other == self:
			continue
		if global_position.distance_to(other.global_position) <= neighbour_radius:
			heading += other.velocity
			count += 1
	if count == 0:
		return Vector2.ZERO
	return (heading / float(count)).limit_length(max_speed)

func _separation() -> Vector2:
	var push: Vector2 = Vector2.ZERO
	for other: CharacterBody2D in flock:
		if other == self:
			continue
		var offset: Vector2 = global_position - other.global_position
		var distance: float = offset.length()
		if distance > 0.0 and distance <= neighbour_radius:
			push += offset / (distance * distance)
	if push.length_squared() == 0.0:
		return Vector2.ZERO
	return push.normalized() * max_speed

func _wrap() -> void:
	var half: Vector2 = area * 0.5
	var point: Vector2 = global_position
	if point.x < -half.x:
		point.x += area.x
	elif point.x > half.x:
		point.x -= area.x
	if point.y < -half.y:
		point.y += area.y
	elif point.y > half.y:
		point.y -= area.y
	global_position = point

The distance > 0.0 guard in separation is there because two agents at the exact same position produce a zero offset, and dividing by zero distance is not the failure you get — you get a vector that steers nowhere, so the pair stacks perfectly and never comes apart. That guard was earned earlier in the shelf; it is worth noticing that it survives every rewrite in this part.

velocity.move_toward(desired, max_force * delta) is the acceleration clamp. The second parameter is a distance, not a time, despite being named delta in the signature. Pass the frame delta by itself and the velocity crawls toward its target at 0.016 pixels per frame, which reads on screen as steering that stopped working.

The manager#

The manager spawns the flock, hands each agent the shared list, and closes out the frame for the timer.

class_name FlockManager
extends Node2D

@export var boid_scene: PackedScene
@export var spawn_count: int = 100
@export var area: Vector2 = Vector2(1152.0, 648.0)
@export var cell_size: float = 60.0
@export var use_grid: bool = false

var boids: Array[CharacterBody2D] = []
var grid: FlockGrid = null

func _ready() -> void:
	process_physics_priority = -10
	FlockPerf.reset()
	grid = FlockGrid.new(cell_size)
	var half: Vector2 = area * 0.5
	for _i: int in spawn_count:
		var boid: Boid = boid_scene.instantiate() as Boid
		add_child(boid)
		boid.global_position = Vector2(
			randf_range(-half.x, half.x),
			randf_range(-half.y, half.y)
		)
		boid.velocity = Vector2.RIGHT.rotated(randf_range(0.0, TAU)) * boid.max_speed
		boid.area = area
		boid.flock = boids
		boid.grid = grid if use_grid else null
		boids.append(boid)

func _physics_process(_delta: float) -> void:
	FlockPerf.end_frame(boids.size())
	if not use_grid:
		return
	var start: int = Time.get_ticks_usec()
	grid.rebuild(boids)
	FlockPerf.add_usec(Time.get_ticks_usec() - start)

FlockGrid does not exist yet — comment out the two lines that mention it for now, or write the class first from further down the page. The use_grid switch is what makes the whole measurement honest later: same scene, same spawn, one exported boolean between the two numbers you are going to compare.

process_physics_priority = -10 puts the manager ahead of the agents in the physics frame, because lower priorities process first. That matters once the grid exists: the rebuild has to happen before anything queries it. end_frame() runs at the top of the manager's _physics_process, which means it closes out the previous frame — every agent has already reported by then, and the ordering problem disappears without a second node.

boid.flock = boids hands every agent the same array, not a copy. Arrays are reference types in GDScript. One thousand agents, one list.

The scene, and one setting that matters#

The boid scene is a CharacterBody2D root with a CollisionShape2D (a CircleShape2D, radius around 8) and anything visible — a small Polygon2D triangle is enough. Set the root's Motion Mode to Floating; the default grounded mode applies floor and ceiling semantics that mean nothing to a top-down flock.

Put the manager at the origin and give it a Camera2D child at (0, 0). The world is centred on the origin here rather than starting at the top-left corner, and that choice pays off two sections from now in a way you will not enjoy.

Clear the boid's collision mask for these runs. You are timing the neighbour search. Leaving 1000 bodies solving against each other buries the number you came for under a number from a different system. Turn the mask back on at the end, watch the frame time, and you will have learned something separate and also true.

Run it#

Set spawn_count to 100, play, read the console. Then 400. Write both numbers down somewhere you will still have them in twenty minutes — a scratch text file, a comment at the bottom of the manager script, anywhere.

A number you produced on your hardware beats any claim anyone makes about your bottleneck, including the claim in the next paragraph.

Name the shape you just measured#

Every agent scans every other agent. Three times, in fact, since cohesion, alignment and separation each walk the whole flock independently. The scan count is agents times agents:

  • 100 agents: 10,000 distance checks per rule, 30,000 per frame
  • 400 agents: 160,000 per rule, 480,000 per frame
  • 1000 agents: 1,000,000 per rule, 3,000,000 per frame

Four times the agents, sixteen times the work. That is the whole prediction, and it is falsifiable. Put your 100-agent number and your 400-agent number side by side and divide. If the ratio lands somewhere between 10 and 20, the model holds and you now know the shape of your problem rather than suspecting it.

If the ratio came out near 4 instead of near 16, something is wrong with the harness, not with the mathematics — the usual cause is that the timer is not wrapped around all three rules, or that end_frame is being called more than once per frame.

Notice what this shape means for planning. Going from 400 to 500 agents costs more than going from 100 to 200 did. The flock does not get gradually worse; it gets worse faster the worse it gets.

A cheaper loop is not a smaller loop#

There are two honest wins available before touching the algorithm, and both are worth taking, and neither changes the curve.

Drop the square root. distance_to() computes a square root you immediately throw away by comparing it against a threshold. distance_squared_to() skips it. Compare against radius * radius instead. This is only valid for comparisons — feed a squared distance into a falloff formula expecting real distance and the falloff is wrong in a way that looks like tuning.

Gather once, steer once. Three rules scanning the same flock for the same neighbours is three times the work for one answer. Build the neighbour list once per agent per frame and hand it to all three rules.

Replace the three rule functions and the top of _physics_process with this:

var _neighbours: Array[CharacterBody2D] = []

func _physics_process(delta: float) -> void:
	var start: int = Time.get_ticks_usec()
	_gather_neighbours()
	var steering: Vector2 = _steer()
	FlockPerf.add_usec(Time.get_ticks_usec() - start)

	var desired: Vector2 = steering.limit_length(max_speed)
	if desired.length_squared() < 1.0:
		desired = velocity
	velocity = velocity.move_toward(desired, max_force * delta)
	move_and_slide()
	_wrap()

func _gather_neighbours() -> void:
	_neighbours.clear()
	var radius_squared: float = neighbour_radius * neighbour_radius
	for other: CharacterBody2D in flock:
		if other == self:
			continue
		if global_position.distance_squared_to(other.global_position) <= radius_squared:
			_neighbours.append(other)

func _steer() -> Vector2:
	if _neighbours.is_empty():
		return Vector2.ZERO
	var centre: Vector2 = Vector2.ZERO
	var heading: Vector2 = Vector2.ZERO
	var push: Vector2 = Vector2.ZERO
	for other: CharacterBody2D in _neighbours:
		centre += other.global_position
		heading += other.velocity
		var offset: Vector2 = global_position - other.global_position
		var distance_squared: float = offset.length_squared()
		if distance_squared > 0.0:
			push += offset / distance_squared
	var count: float = float(_neighbours.size())
	var cohesion: Vector2 = (centre / count - global_position).limit_length(max_speed)
	var alignment: Vector2 = (heading / count).limit_length(max_speed)
	var separation: Vector2 = Vector2.ZERO
	if push.length_squared() > 0.0:
		separation = push.normalized() * max_speed
	return cohesion * cohesion_weight \
		+ alignment * alignment_weight \
		+ separation * separation_weight

_neighbours is a member, cleared and refilled, not a fresh array every frame. At 1000 agents an array allocated per agent per frame is 60,000 throwaway allocations a second for no benefit.

Measure again at 100 and 400. The numbers drop — on most machines by something between half and two thirds. Now divide the 400 number by the 100 number again.

It is still about 16.

That is the lesson worth more than the speedup. You made the loop cheaper. You did not make it smaller. The constant factor moved and the curve did not, so every win you took here gets eaten again by the next few hundred agents. Cheap loops buy you a fixed multiple. Smaller loops buy you a different shape.

The deciding question, when you are choosing between the two: do you know the final agent count? If the flock is capped at 80 forever because that is what the level design calls for, constant-factor work is the correct and complete answer, and everything below this line is over-engineering. If the count is a number someone will want to raise later, the shape is the thing to fix.

The grid#

Here is the observation the naive loop ignores: an agent 900 pixels away cannot possibly be a neighbour of an agent with a 60-pixel radius, and the loop asks about it anyway, every frame, forever.

So sort agents into buckets by position, once per frame, and let each agent read only the buckets that could contain a neighbour. Cut the world into square cells. Each cell is a key. Each key maps to the list of agents standing in that cell. To find neighbours, read the agent's own cell and the eight around it — a 3x3 block.

Vector2i is the key type: a pair of integers, exact, with no floating-point rounding that could make two names for the same cell compare unequal.

Cell size is a correctness decision before it is a speed one#

The obvious advice is that cell size should sit at roughly the neighbour radius. The reason it is not merely advice:

  • Cell smaller than the radius and the 3x3 block no longer covers the search radius. Neighbours that are genuinely in range sit two cells away and are never seen. The flock does not slow down — it fragments into cell-sized clumps that drift past each other without reacting, which reads exactly like a broken separation rule.
  • Cell much larger than the radius and each bucket holds a large slice of the flock, so every query walks most of the agents again. That is the naive loop wearing a hat, plus the cost of building the buckets.

Cell size equal to the neighbour radius is the default worth starting from. It is the smallest size that still guarantees the 3x3 block covers the radius.

The class#

class_name FlockGrid
extends RefCounted

var cell_size: float = 60.0

var _cells: Dictionary[Vector2i, Array] = {}

func _init(size: float) -> void:
	cell_size = maxf(size, 1.0)

func cell_of(point: Vector2) -> Vector2i:
	return Vector2i(point / cell_size)

func rebuild(agents: Array[CharacterBody2D]) -> void:
	_cells.clear()
	for agent: CharacterBody2D in agents:
		var bucket: Array = _cells.get_or_add(cell_of(agent.global_position), [])
		bucket.append(agent)

func query(point: Vector2, radius: float, exclude: CharacterBody2D, out: Array[CharacterBody2D]) -> void:
	out.clear()
	var radius_squared: float = radius * radius
	var origin: Vector2i = cell_of(point)
	for x: int in range(origin.x - 1, origin.x + 2):
		for y: int in range(origin.y - 1, origin.y + 2):
			var cell: Vector2i = Vector2i(x, y)
			if not _cells.has(cell):
				continue
			for other: CharacterBody2D in _cells[cell]:
				if other == exclude:
					continue
				if point.distance_squared_to(other.global_position) <= radius_squared:
					out.append(other)

Three things in that file are doing more than they look like they are doing.

get_or_add(cell, []) followed by bucket.append(agent). get_or_add inserts the default when the key is missing and returns the value either way, so one call replaces a check-then-create pair of lookups. The append lands in the stored array rather than in a discarded copy because arrays are reference types — bucket is the array in the dictionary, not a snapshot of it. Rely on that here, and stay aware of it everywhere else.

_cells.clear() rather than _cells = {}. Clearing keeps the dictionary's allocated storage and hands the engine less garbage every frame. At 60 rebuilds a second the difference shows up.

has(cell) rather than get(cell, []). get() with a default looks tidier, but the default argument is evaluated eagerly — every call allocates a fresh empty array whether or not it is needed. Nine cells per agent, 1000 agents, 60 frames: over half a million pointless arrays a second, inside the function you wrote to make things faster.

The out parameter is the same trick as _neighbours being a member. The caller owns the array, the grid fills it, nothing is allocated per query.

Wiring it up#

The agent's gather function grows a branch, and that branch is the entire A/B test:

func _gather_neighbours() -> void:
	if grid != null:
		grid.query(global_position, neighbour_radius, self, _neighbours)
		return
	_neighbours.clear()
	var radius_squared: float = neighbour_radius * neighbour_radius
	for other: CharacterBody2D in flock:
		if other == self:
			continue
		if global_position.distance_squared_to(other.global_position) <= radius_squared:
			_neighbours.append(other)

Uncomment the grid lines in the manager. Set cell_size to match neighbour_radius. Tick use_grid and play.

Note where the rebuild is timed: inside the manager, added to the same accumulator the agents use. The rebuild is part of what the grid costs. Leave it out of the measurement and the comparison is a lie you told yourself on purpose.

Dictionaries are passed by reference. Always.#

Before the next section breaks something, know how the sneakiest version of it happens.

A dictionary handed to a function is not copied. The function receives the same dictionary. If a helper calls clear() or erase() on what it thinks is its own working copy, the caller's grid empties underneath it, and the symptom is that every query returns nothing while the rebuild code looks perfectly correct. duplicate() is how you get a copy that can be modified independently.

This is why FlockGrid keeps _cells private and exposes rebuild and query instead of handing the dictionary out. The encapsulation is not ceremony — it is the thing that makes the reference semantics safe to ignore for the rest of the file.

One consequence of dictionaries worth banking while you are here: insertion order is preserved. Iterate the grid and the sequence is the same every run, so a flock built on it behaves identically across runs given identical input. The first time you have to reproduce a bug that only happens after 40 seconds, that property is worth more than the speedup was.

The bug worth writing on purpose#

Look at cell_of again.

func cell_of(point: Vector2) -> Vector2i:
	return Vector2i(point / cell_size)

That is wrong, and it was written that way on purpose — because what it does when it goes wrong is not what you would guess.

Vector2i(Vector2) truncates toward zero. It does not floor. With a 60-pixel cell, an agent at x = -30 divides to -0.5 and truncates to cell 0. An agent at x = +30 divides to +0.5 and truncates to cell 0 as well. Cell 0 therefore spans -60 to +60 while every other cell spans 60 pixels — the strip from -60 to 0, which should have been its own cell, has been swallowed. The cell to the left picks up at -120 to -60, so nothing overlaps and nothing is skipped. One cell is twice as wide on that axis, and the same happens on the other axis.

Now run it and go looking for the symptom, because finding out there isn't one is the lesson.

The flock is fine. Not subtly fine — identical. query() ends every candidate with an exact distance_squared_to test against the real radius, so the cell layout can only ever change which agents get tested, never which ones pass. And the 3x3 block still reaches far enough: a wider cell reaches further, not less far, so no genuine neighbour ever falls outside it. Every agent gets exactly the neighbour list it would have got from the naive double loop.

What did change is the bill. Twice as wide on each axis is four times the area in 2D, so the origin cell holds roughly four times as many agents as a normal one, and every agent whose 3x3 block touches it scans all of them. Watch the printed microseconds instead of the screen and put the flock over the origin: the number climbs, and the behaviour does not budge.

Sit with that, because it is a worse bug than a visible one. A defect with a symptom gets found. This one has no symptom — it is a correct flock that costs more than it should, in a region of the map that depends on where the camera happens to be. It will not show up in a playtest, it will not show up in a bug report, and it will sit in your codebase until someone profiles the right frame. The only thing that catches it is knowing the conversion is suspect and checking it.

Floor the components before converting:

func cell_of(point: Vector2) -> Vector2i:
	return Vector2i((point / cell_size).floor())

Vector2.floor() rounds both components down toward negative infinity, and converting an already-whole float loses nothing. Every cell is now genuinely the same size, and the timing flattens out across the map.

The general form of this lesson: any time integer coordinates get derived from world positions, ask what happens on the negative side of the origin. Tile lookups, chunk indices, minimap cells, quantised pathfinding keys — same conversion, same mistake. The spatial hash got off lightly because it re-checks every candidate against the real distance afterwards, so the oversized cell only costs time. Most of those other lookups have no such second check: whatever the integer key says is the answer, and two different world strips collapsing onto one index is a wrong tile, a wrong chunk, a wrong waypoint. Whether your version of this bug is a slowdown or a corruption depends entirely on whether something downstream verifies the result.

Worth holding onto when you reach the set-comparison assert in the stretch list below. That assert catches every bug that loses a neighbour, which is most of them. It will pass on this one, every frame, for the whole session — because this one never loses a neighbour. A test that checks the answer cannot catch a bug in the price.

Measure again, and write it down#

Same scene. Toggle use_grid and change spawn_count. Six runs, and 30 seconds each is plenty since the harness prints every 60 frames.

AgentsNaive double loop (us/frame)Spatial hash (us/frame)Ratio
100
400
1000

Two things to read out of your own table.

The shape changed. Read it one transition at a time, because the rows are not evenly spaced. 100 to 400 is four times the agents; 400 to 1000 is only two and a half. Quadratic cost squares that, so the naive column should grow about 16x on the first step and about 6x on the second. Near-linear cost tracks it directly, so the grid column should grow about 4x and then about 2.5x. What you are checking is not any single number but the gap between the two columns' growth — the naive one compounding, the grid one keeping pace with the agent count, because each agent's query walks a roughly constant number of nearby agents no matter how large the flock is.

If you would rather have one number to look for on every row, run 100 / 400 / 1600 instead. Then it is 16x and 4x the whole way down, and the arithmetic stops getting in the way of the point.

Find the crossover. Run both at 40 agents. On most machines the grid is slower there, because rebuilding the dictionary and its forty bucket arrays every frame costs more than 1,600 distance checks. There is a count below which the grid is a loss, and now you can state that count for your hardware instead of arguing about it. Shipping a spatial hash for a 40-agent flock is a real cost — more code, more state, more to get wrong — bought with a negative return.

One caveat on all six numbers: running from the editor is a debug build with the profiler attached. It is slower than an exported build, sometimes considerably. That does not damage the comparison, because both sides paid the same tax. It does mean these numbers are not the numbers your players will get, and the direction of the error is in your favour.

When the grid is not enough#

The grid moves the ceiling. It does not remove it. Three directions from here, each with a real cost — say the cost out loud before you take the option.

Stagger the updates. Have each agent recompute its steering every Nth physics frame, on an offset so the work spreads evenly instead of all landing on the same frame.

@export var update_every: int = 3
var _phase: int = 0
var _steering: Vector2 = Vector2.ZERO

func _ready() -> void:
	_phase = randi() % maxi(update_every, 1)

func _physics_process(delta: float) -> void:
	if Engine.get_physics_frames() % maxi(update_every, 1) == _phase:
		var start: int = Time.get_ticks_usec()
		_gather_neighbours()
		_steering = _steer()
		FlockPerf.add_usec(Time.get_ticks_usec() - start)
	var desired: Vector2 = _steering.limit_length(max_speed)
	if desired.length_squared() < 1.0:
		desired = velocity
	velocity = velocity.move_toward(desired, max_force * delta)
	move_and_slide()
	_wrap()

Divide the search cost by N for free — except it is not free. The agent is steering on information up to N-1 frames stale, so it reacts late. Cohesion and alignment tolerate this well; nobody sees a flock turn 30 milliseconds late. Separation does not, because separation is the rule with a deadline. At update_every = 4 and high speeds, agents interpenetrate before their next update arrives. If you take this option, consider running separation every frame on the cached neighbour list and staggering only the other two.

Cap the neighbour count. Stop the query after k neighbours regardless of how many are in range. This is exactly what the built-in avoidance from Part 04 does — max_neighbors defaults to 10, which is why dense crowds degrade gracefully there instead of quadratically. The cost is bias: the agents you keep are the ones whose bucket happened to be scanned first, not the nearest ones. Sorting by distance to get the true k-nearest costs more than the cap saved. In a dense uniform flock the bias is invisible; at the boundary between a dense clump and open space it is not.

Take the loop out of the nodes entirely. One manager holding positions and velocities in PackedVector2Arrays, iterating them in a single loop, drawing the whole flock through one MultiMeshInstance2D. This is the largest win available and the largest thing to give up: no per-agent script, no per-agent signals, no CharacterBody2D collision, and every agent behaviour becomes an index into parallel arrays rather than a property you can inspect in the remote scene tree. Reach for it when the flock is decoration — fish, birds, embers — and never when individual agents need to be interacted with.

Order of operations, if it is not obvious: measure, then take the cheapest option that clears your target, then measure again. A frame budget you have not measured against cannot be cleared.

Checkpoint — definition of done#

  • The console prints a rolling average every 60 physics frames, with the agent count in the line, and the number is stable to within about 20% between prints.
  • You have written down the naive 100-agent and 400-agent numbers, and the 400 number is between 10x and 20x the 100 number.
  • Switching to distance_squared_to and one shared neighbour list lowers both numbers, and the ratio between them stays near 16.
  • With use_grid on and cell_size equal to neighbour_radius, the 400-agent number is lower than the naive 100-agent number.
  • Setting cell_size to a quarter of neighbour_radius visibly breaks the flock — it fragments into small clumps that ignore each other — and setting it to four times the radius makes the timing number climb back toward the naive one.
  • With the truncating version of cell_of, the flock looks and behaves exactly as it does with the floored version, and the timing number is higher when the flock sits over the origin.
  • The three-row table is filled in from your own runs, and you can state the agent count at which the grid stops being a loss on your machine.
  • You can explain: why the spatial hash can be slower than the double loop at 40 agents even though every query touches fewer agents.

Stretch (no instructions)#

  • Sweep cell_size from 0.25x to 4x the neighbour radius in steps and find the minimum on your machine. It is rarely exactly 1.0x, and where it lands tells you something about how densely your flock packs.
  • Assert the grid against the naive search: at each frame, gather both ways for one agent and compare the resulting sets. Any mismatch is a grid bug that lost a neighbour — an undersized cell, an off-by-one in the 3x3 loop. Then extend it to also record how many candidates each side scanned, and watch that second number catch the bugs the first one is blind to.
  • Make the harness measure three phases separately — rebuild, query, steering maths — and find out which one you actually optimised.
  • Turn the collision mask back on and measure how much of the frame the physics server takes at 400 agents. Decide whether the flock needs bodies at all.

If you get stuck#

  • Nothing prints → the manager's _physics_process is not running, or boids is empty. Confirm boid_scene is assigned in the inspector and that the spawn loop ran.
  • The printed time is 0 or 1 microsecond at every count → the timer is not wrapped around the search. Check that add_usec receives Time.get_ticks_usec() - start and not the raw tick value, and that _gather_neighbours() sits between the two readings.
  • The number keeps climbing across scene reloads → FlockPerf.reset() is not being called in _ready. Static variables outlive the scene.
  • The 400/100 ratio is near 4 instead of near 16 → end_frame is being called more than once per frame, or a second node is also calling add_usec. Only the manager should end the frame.
  • Every grid query returns nothing → the rebuild is running after the agents query. Confirm process_physics_priority = -10 on the manager, and that _cells.clear() runs at the start of rebuild, not the end.
  • The flock fragments into small clumps after switching to the grid → cell_size is smaller than neighbour_radius, so the 3x3 block does not cover the search radius and real neighbours are being missed.
  • The grid is no faster than the naive loop → cell_size is far larger than the radius, so each bucket holds most of the flock. Print _cells.size() and the average bucket size; a healthy grid at 400 agents has hundreds of buckets holding a handful each.
  • The grid's timing is worse than the table predicts, and worst when the flock crosses the middle of the world → cell_of is truncating instead of flooring, so the cell straddling the origin is four times the area of every other one. Behaviour is unaffected; only the cost is wrong.
  • The grid and the naive search disagree on neighbour counts at the same positions → the 3x3 bounds are off by one. range(origin.x - 1, origin.x + 2) yields -1, 0, +1; range(origin.x - 1, origin.x + 1) silently drops a column.
  • Agents crawl at roughly a sixtieth of their speed → velocity is being multiplied by delta before move_and_slide(). The method applies the physics step itself.
  • Steering appears frozen → move_toward is receiving the frame delta as its second argument instead of max_force * delta. That parameter is a distance.
  • The timing is fine but the game still stutters → the search is no longer your bottleneck. Time something else before changing anything; the whole point of the harness is that it works on the next suspect too.

Next: State Machines — behaviour that changes its mind. Steering answers where an agent moves; it has nothing to say about when the flock should stop flocking and start fleeing, regrouping, or hunting. That shelf gives you the structure for switching between whole behaviours without a boolean per mood, and it composes with everything here — a state selects the steering rules, the grid keeps feeding them neighbours.