O(1) collisions with an incremental spatial hash

July 2026 · growordie · engine internals

The first playable version of growordie fell over at about fifteen snakes. Not crashed, just molasses. The server would spend so long every tick asking "is anybody touching anybody?" that the whole world started to stutter. I spent an embarrassing evening convinced it was a memory leak before I did the actual math and realized the loop itself was the bug. This is the story of the little data structure that fixed it, and why it's the boring one on purpose.

I'll keep the code to the single line that matters and let a handful of animated diagrams carry the rest. If you'd rather see the whole engine at a glance first, there's a tour of all five mechanisms and a write-up on the numbers, this page just zooms all the way in on the one thing they only sketch.

• 01 The problem: collision is O(N²) if you let it be
• 02 A flat uniform grid: a Map, not a quadtree
• 03 The incremental trick: +1 head, −1 tail
• 04 The query: scan a 3×3 neighborhood, ignore the world
• 05 Why not a quadtree?
• 06 The honest asterisks on "O(1)"

01 · Why it fell over

Here's the shape of the problem. A snake in growordie isn't a sprite, it's a trail: a chain of little sample points, one dropped every 10 units behind the head. A modest 10-meter snake is around a hundred of those points. A 100-meter monster is a thousand. Put a few hundred snakes in one arena and you're suddenly tracking tens of thousands of body points, and every single one of them is moving.

Every tick (30 times a second) the server has to answer one question: does any head touch any body? The way I wrote it first was the way anyone writes it first. Two nested loops: for each head, walk every point in the world and check the distance. It's clean, it's obviously correct, and it's quadratic. The work grows with the square of how much stuff is in the world, so it's fine with two snakes and a disaster with two hundred. That's why fifteen was the wall, I was doing tens of millions of pointless distance checks a second, the overwhelming majority of them between two snakes on opposite sides of the map that could never possibly touch.

That last part is the tell. The fix everyone reaches for is a broadphase, a fancy word for a cheap index that, given a head, hands you back only the handful of points that could plausibly be near it, so the real distance test runs a few times instead of ten thousand. The catch, and the thing that took me a couple of tries to appreciate, is that a broadphase you have to rebuild from scratch every tick can quietly cost as much as the problem it solves. In a game where everything moves constantly, keeping the index current is the whole ballgame.

Before I show you the fix, here is the disaster and the cure in one picture. On the left is the loop I wrote first, on the right is the grid, running the same snakes. Watch what the counters do as snakes trickle in.

02 · A grid, not a tree

The broadphase I landed on is the least clever one that works: a uniform grid. Picture the arena as a city carved into equal square blocks, each one 64 units on a side. Every body point is filed under the block it happens to sit in, and when a head wants to know who is nearby it only knocks on its own block and the eight around it, never the whole city. No quadtree, no R-tree, nothing that ever has to "re-balance" itself. Just a flat map from a block to the list of points parked in it.

The only real question is how you name a block so you can look it up fast. A point carries a raw (x, y) in world units; the grid wants one tidy label for the cell it falls in. That whole translation is a single line of arithmetic, and it is the "hash" in "spatial hash":

Two small things hide in that one line. Flooring the coordinate is just a fast way to snap a position down to its cell index. And multiplying the column by 100000 before adding the row is what squishes two numbers into one, so the pair can be a Map key directly. My first version instead built a little string like "12,41" for every point every tick, which meant allocating and garbage-collecting thousands of tiny strings a second, and the garbage collector hated me for it. Packing the pair into a single number made that whole class of garbage vanish. (100000 is just a stride comfortably wider than the arena is in cells, so a column and a row can never collide on the same key.)

The arena's a circle about 40,000 units across, so roughly 625 cells to a side and maybe 9,000 non-empty buckets when it's busy. It's small, it's flat, and (the part that actually matters for speed) it's friendly to the CPU cache: a bucket is a plain contiguous array of points, and a query only ever touches a few neighbouring buckets. That's the whole structure. Honestly the grid is the boring half. The half I like is what happens next.

03 · The trick I actually like: +1 head, −1 tail

Okay, this is the part I got excited about, so bear with me. The naive instinct with a grid is: every tick, throw the whole thing away and rebuild it from all the snakes' current positions. And that works! But it's secretly the O(N²) monster wearing a hat, you're still touching every point in the world every tick, you've just moved the cost from the collision check to the bookkeeping.

Then it clicked one night that a snake doesn't teleport. It crawls. Between one tick and the next its body barely changes at all: it grows exactly one new point at the head, and drops exactly one old point off the tail. Everything in the middle is byte-for-byte identical to last tick. So why on earth am I re-filing all of it?

So I stopped rebuilding. The grid just gets nudged: shove the new head point into its bucket, pluck the departed tail point out of its bucket, done. Two tiny operations. It maps almost word-for-word to how the body is stored, which is a plain queue: new point pushed on the back, oldest point shifted off the front. Stripped all the way down, the whole update the grid needs each tick is this:

const CELL = 64;                       // one cell = 64 world units
const key = (x, y) => (x / CELL | 0) * 100000 + (y / CELL | 0);
const grid = new Map();                // key -> body points in that cell

// Every tick, per snake: two nudges, and never a rebuild.
grid.get(key(head.x, head.y)).push(head);          // +1 at the head
tailCell.splice(tailCell.indexOf(tail), 1);        // −1 at the tail

In the real server those two moves live in a gridAdd and a gridRemove helper, called from inside the movement step. A fresh head point is filed only once the head has actually travelled a full 10 units (no sense stacking points on top of each other), and the tail is trimmed back to match the snake's current length. Each point also remembers which bucket it landed in, so pulling it back out later is a direct lookup instead of a hunt. But peel all that away and it is still the same two moves: one point in at the head, one point out at the tail.

That's genuinely the entire maintenance story. No timer that periodically re-hashes everything, no "dirty" flags, no rebuild pass hiding somewhere. The grid is just a spatial index riding on top of the body queue, kept in lockstep with two lines. Watch it move below: the head lights a cell as it enters (that's a gridAdd), the tail flashes a cell clear as it leaves (a gridRemove), and over on the right the Map gains a point in one bucket and loses its last one in another. What I love about it is that the giant and the rookie cost exactly the same to maintain (one insert, one remove) no matter how long they are.

04 · Asking the grid a question

Maintenance keeps the index honest; the query is what I actually pay for 30 times a second. And now it's almost anticlimactic. For a given head I don't go near the rest of the world, I just work out which cells that head could possibly reach this tick and look only in those. The reach is the head's own radius plus a little slack, one cell's worth (in the code, range = r + 65). I turn the corners of that little box into cell columns and rows, walk the handful of buckets it covers, and test the head against only the points that actually live there. It is the difference between shouting a question across a packed stadium and quietly turning to ask the nine people sitting nearest you.

In the real source there's a comment right above that loop that just says "the hottest loop in the server," which is me leaving a note to future-me not to get cute here. It's a flat inlined double-for rather than something tidier with a generator, and that's deliberate: generators allocate, and anything that allocates in this loop shows up in the frame times. For an ordinary snake, r is small, so range = r + 65 reaches about one cell each way, a 3×3 block, nine buckets, a couple dozen points tops. That's the whole shortlist for that head. The other 99.9% of the arena might as well not exist.

Put both halves together and the collision system is cheap coming and going. Keeping the index current: one insert, one remove per snake per tick. Asking it a question: a scan of a tiny local neighborhood, however crowded or empty the rest of the map is. Nothing in that loop grows with the total number of bodies in the world, and that single property is the entire reason one CPU core can now hold a thousand snakes instead of fifteen.

05 · "But why not a quadtree?"

I know. Every time I say "spatial index" out loud someone asks why it isn't a quadtree, and for a while I second-guessed it myself. So let me be fair to the quadtree, because it's a genuinely lovely structure, just for a different game than mine.

A quadtree shines when your data mostly sits still and clumps unevenly, and your queries are big and varied: "everything within 500 units," "the nearest thing to this point." It adaptively subdivides, spending its detail where the crowd is, so a query into empty space bails instantly and a query into a dense corner still has a sane depth. It's a beautiful answer when you build the tree once and then ask it a thousand questions.

My game is the exact opposite on every axis that matters, and it took me actually trying to picture a quadtree here to see it:

Since everything moves every tick, a tree would spend its whole life re-inserting and re-balancing itself, which is precisely the thing trees are worst at. The grid just doesn't have that problem to have: there are no branches to split or merge, so a snake moving is "pull from the old bucket, drop in the new one," two array pokes and no drama. And the quadtree's superpower (cheaply skipping enormous empty regions for a big sweeping query) is a superpower I never once use, because I never do a big query. Every question I ask is that same little 3×3 window.

The other thing, the one you don't see in a textbook, is how the two feel to the machine. My flat map of little arrays sits nicely in cache and makes almost no garbage. A tree of node objects is pointers chasing pointers all over the heap, and it litters. Run that 30 times a second over hundreds of thousands of points and "makes no garbage, stays in cache" wins going away. The grid isn't the smart choice. It's the boring choice. It just happens that boring is exactly what this loop wanted, and I've made my peace with that.

If I'd built a strategy game instead (a static map, units doing long line-of-sight checks) this whole section would flip and I'd be gushing about my quadtree. The data shape picks the structure, not the other way around. Mine is mobile, evenly spread, and asked only tiny local questions. So: grid.

06 · Where I'm fudging the "O(1)"

I put "O(1) collisions" in the title and I should come clean, because the fudge is where the actual engineering lives.

The constant-time part is the maintenance: the insert at the head, the remove at the tail. That really is O(1) per snake per tick. The query is not; it's O(k), where k is however many points are sitting in the neighborhood I scan. Usually that's tiny. But when a dozen snakes coil into the same few cells for a big kill, k spikes and those heads genuinely do more work that tick. What I care about is that k is set by the local crowd and never by the arena's total headcount, a brawl on the far side of the map costs your head precisely nothing. That's the property I was really chasing, not literal constant time.

And even the "O(1)" remove is fibbing a little. Look again at gridRemove: it does an indexOf then a splice, both of which walk the bucket. It's only fast because the buckets stay short, and keeping them short is the entire job of the cell size.

Which is the one knob I actually agonized over: CELL = 64. There's a way to be wrong in each direction.

• Too small and the grid shatters into a zillion tiny buckets, a single snake smears across loads of cells, and every query plods through more of them just to pay the Map.get tax on each.
• Too big and every bucket turns into a crowd, the query slides back toward "check everything nearby" (O(N) all over again, locally), and that indexOf/splice in the remove gets slower with every extra point in the bucket.

At 64 units, with a point every 10, a straight stretch of body drops about six points into a cell before it crosses into the next. Buckets stay short, a normal query pokes a 3×3 of them, removes stay basically free. I'd love to tell you I derived that number. I didn't. I nudged it and watched the tick-time graph until it stopped complaining. The one honest wrinkle: a giant snake has a fat radius, so its range = r + 65 reaches further and it might scan a 5×5 instead of a 3×3. But that's capped by the biggest a snake can get, not by how many snakes showed up. The ceiling holds no matter how packed the server is.

And that, really, is the whole trick the game is built on: reach for the boring structure, stay honest about which part is actually constant, and pour the cycles you saved into more players. If you're curious where those cycles go from here (the binary snapshots, the viewport culling that leans on this exact same grid, the collision math that runs on the points it hands back) the animated engine tour and the architecture write-up carry straight on. And that favorite-bug of mine, the one where people kept driving clean through each other and living? That's its own story: killing the tunnel bug.

Made solo, in Node.js, probably at 2am · growordie