Reference
Maze generation
Prim O(V log V) · division O(V) · blocks O(V)
Prim's algorithm grows a maze outward from one cell, always opening a random wall on the boundary of what it has already reached. The result is dense and even: one-cell corridors, no long straight runs, and exactly one route between any two points.
Recursive division works the other way round. It starts with an empty room, drops a wall across it with a single doorway, and recurses into both halves. It builds architecture rather than a burrow, and the parity rule — walls only on even coordinates, doorways only on odd — is what stops a later wall from sealing an earlier doorway shut.
A perfect maze makes every pathfinder draw the same picture, because there is only one route to find. Braiding knocks out a share of the dead ends, which puts alternative routes back in and is what lets the searches next door actually disagree with each other.
Pathfinding
Dijkstra & A* O(E log V) · BFS/DFS O(V + E)
Every search here is the same loop with a different rule for which cell to open next. Breadth-first takes the oldest, depth-first the newest, Dijkstra the cheapest so far, greedy best-first the one that looks closest to the goal, and A* the one with the best total of both. Watching the expanded region grow is watching that rule make its decisions.
Terrain matters. With flat costs, Dijkstra and breadth-first expand identically and the distinction between them is a claim you have to take on faith. Turn terrain on and the hatched cells cost four times as much to cross: Dijkstra now bends around them, breadth-first walks straight through, and the difference is on the screen instead of in a sentence.
Heuristic choice is a real trade. Octile is admissible on an eight-neighbour grid and A* stays optimal. Manhattan over-estimates diagonal moves, so A* gets faster and stops being guaranteed correct — the path cost counter is where you see what that bought and what it cost.
Race
Both lanes advance one step per tick
Both lanes get a byte-identical field, because the field is rebuilt from the same seed rather than copied, and both advance exactly one step per tick. A step is one cell opened or one cell expanded, so the race measures work rather than wall-clock time and the result does not depend on how fast your machine is.
The useful comparison is rarely who finishes first. Greedy best-first almost always wins the race and almost always brings back a worse path; the path cost counter is where that shows up. A* against Dijkstra is the honest matchup: identical cost, and A* gets there having opened far fewer cells.
This module is about thirty lines of interleaving on top of the pathfinding module. It exists because the algorithms are pure step generators — nothing here reaches inside a search or copies one, it just pulls two streams in lockstep and sends each step to the state it belongs to.
Wave function collapse
O(V · d · |T|) per collapse · arc consistency is complete here
Every cell starts holding all sixteen tiles at once. The algorithm repeatedly picks the cell with the fewest options left, commits it to one of them, and then propagates that decision outward — each neighbour discards every tile whose shared edge no longer agrees. Choosing the most constrained cell first is what keeps the pattern coherent instead of turning into noise.
The dots are entropy. A cell with every option open draws nothing; as its possibilities drain away the dot grows, so the propagation wave is visible running ahead of the collapse rather than being something you have to take on trust.
Wave function collapse is usually described as needing to backtrack, and this one never does. That is a property of the tileset rather than good luck: a tile here is fully determined by its four edge bits, and each shared edge constrains exactly one bit, so propagating until nothing changes leaves the grid arc-consistent — and for constraints this shape, arc-consistent is already the same thing as solvable. Measured over 120 runs across three tilesets, contradictions: zero.
The restart path is still in the code, because the moment a tileset stops being pure edge matching — a rule about what may appear twice in a row, a tile whose identity is not implied by its edges — that guarantee is gone and the algorithm can paint itself into a corner. This build restarts rather than backtracks, which is cheaper to write and worse at the job, and that trade is worth stating rather than hiding.
Sorting
Merge/heap O(n log n) · quick O(n log n) avg · the rest O(n²)
Bars alone teach almost nothing — every sort looks like the same wobble. Counting comparisons and writes separately is what makes the difference legible, because that is where these algorithms genuinely disagree. Selection sort compares constantly and writes barely at all; insertion sort does the opposite; merge sort pays a write for every element on every level of the recursion and never varies.
Change the distribution and the ranking changes with it. On nearly-sorted input insertion sort finishes in close to linear time and beats every O(n log n) algorithm here, which is exactly why real library sorts fall back to it for small or almost-ordered runs. On reversed input the same algorithm is the worst on the list.
Quicksort takes the last element as its pivot, which is the naive choice and deliberately so: run it on already-sorted or reversed input and watch the comparison counter go quadratic. That failure is the reason median-of-three and introsort exist.
Flow field
One O(E log V) sweep · O(1) per agent per tick
Running A* once per unit is what makes crowd movement expensive. A flow field turns the problem inside out: one Dijkstra sweep outward from the destination costs every reachable cell, and then each cell simply records which neighbour is cheapest. After that an agent never searches — it stands on a cell, reads the arrow, and moves.
The counter that matters is the one that does not move. Raise the agent count from twenty to two hundred and the cells-costed figure is identical, because the field was already built and adding agents adds no search at all. That is the entire argument for the technique, and it is the reason it is in real games and rarely in visualisers.
The trade is that the field belongs to one destination. Every agent here is heading for the same ring, and a second destination means a second sweep. When the target moves every tick you want incremental replanning instead — D* Lite is the usual answer, and it is the obvious next module for this spine.
Quadtree
Build O(n log n) · query O(log n + k)
The tree subdivides wherever points crowd together: any node holding more than four points splits into quadrants and hands them down. Empty space stays one large rectangle, dense space shatters into small ones, and the picture is a map of where the data actually is.
The second phase is the one worth watching. Query rectangles land at random and each one walks the tree, opening only the nodes it overlaps — those get outlined — and testing only the points inside them. Everything left un-outlined was discarded by a single rectangle comparison. The tag at the top left keeps score against testing every point against every query, which is what a collision loop with no spatial index does.
Clustered points are used deliberately. A uniform cloud subdivides into an even grid and the quadtree looks like an expensive way to draw graph paper — the structure only earns itself when the data is uneven, which is what real data usually is.
Boids
O(n · k) per tick with the hash · O(n²) without
Each agent looks only at the flockmates inside one radius and applies three rules: steer away from anyone too close, match the average heading, drift towards the average position. Nothing coordinates them and no agent knows where the flock is going. The flock is what the rules add up to.
Finding those neighbours is the expensive part, and doing it honestly means comparing every agent against every other one — the brute-force figure in the counters. Instead, positions are bucketed into a grid whose cell is exactly one perception radius, so an agent only ever examines the nine buckets around it. Both numbers are counted every tick, and the gap between them widens as the square of the agent count.
The amber circle is one agent's perception radius, drawn so the claim can be checked rather than believed. Nothing outside it influences that agent at all.