7-Colouring Explained — How Distance-2 Safety Works

The Problem

Two animals move at the same time. Both target the same cell. The GPU has thousands of threads running simultaneously — there is no "first" or "second." Both write. One wins. The other's data vanishes. No error. No crash. Just gone.

1 / 6

Distance-1 Safety (The Easy Part)

If we just needed adjacent cells to be different colours, 4 colours would suffice — like a map. But we need 7. Why? Because of movement. An animal does not just sit on its cell — it WRITES to a neighbour. That is distance-2.

2 / 6

Distance-2 — Why 7, Not 4

A and B are not adjacent — they are separated by one cell, T. But both can MOVE to T. If A and B share the same colour, they fire in the same GPU dispatch. Both write to T simultaneously. Collision. With 7 colours, no two cells that share ANY common neighbour can have the same colour. They always fire in different phases. When A moves to T, B has already moved or has not yet fired. No conflict possible.

3 / 6

How the GPU Fires

TICK (one simulation step): Phase 1: Fire all Color 1 cells ← 150,000 cells, ALL AT ONCE on GPU (wait for GPU to finish) Phase 2: Fire all Color 2 cells ← 150,000 cells, ALL AT ONCE (wait) Phase 3: Fire all Color 3 cells ← ALL AT ONCE (wait) Phase 4: Fire all Color 4 cells Phase 5: Fire all Color 5 cells Phase 6: Fire all Color 6 cells Phase 7: Fire all Color 7 cells Total: 7 sequential phases × 150K parallel cells = 1M cells per tick WITHIN each phase: every cell runs simultaneously. No waiting. BETWEEN phases: sequential. GPU waits for one to finish before next. This is Chromatic Gauss-Seidel: Each colour sees the LATEST state from previous colours. Information propagates faster than pure synchronous update.

The GPU does not fire all million cells at once. It fires them in 7 waves. Each wave contains only cells of the same colour. Within a wave, every cell runs simultaneously — truly parallel, thousands of GPU cores. Between waves, the GPU synchronises. This means Color 2 cells see the results of Color 1's movements. Information flows forward through the tick.

4 / 6

The Formula

color = (col + row + 4 × (col & 1)) mod 7

What each part does:

col + row
  Creates a diagonal gradient across the grid.
  Every step right or down shifts the colour by 1.

4 × (col & 1)
  This is the hex stagger correction.
  Odd columns are shifted down by half a cell.
  This shift breaks the simple diagonal pattern.
  The "4" compensates: it jumps 4 colours on odd columns
  to maintain distance-2 safety across the stagger boundary.

mod 7
  Wraps to 7 colours. The cycle repeats every 7 cells.

Why 7 and not 6?
  6 colours can do distance-1 (adjacent cells different).
  But some distance-2 pairs (sharing a common neighbour)
  would collide. 7 is the mathematical minimum.
  Proven: Molloy & Salavatipour, 2005.

Found by: exhaustive search over all (a×col + b×row + d×(col&1)) mod 7
Result: 12 valid formulas. This is the simplest.
Verified: zero conflicts on 64×64 grid, distance-1 AND distance-2.
  

The formula assigns a number 0 through 6 to every cell based on its column and row. The col-and-one term is the key — it handles the hex grid stagger where odd columns are offset by half a row. Without it, the diagonal pattern would break at column boundaries and two same-coloured cells would share a neighbour. The 4 is not arbitrary — it was found by testing all possible values 0 through 6 and checking which ones produce zero conflicts.

5 / 6

Your Fibonacci Spiral Intuition

You asked: could you unfurl the grid as a spiral from the center? Yes — as a rendering transform. Currently the grid is stored in memory as a flat row-major matrix: index = row × width + col. Simple. Predictable. Neighbours are at fixed offsets (~width apart). A Morton Z-curve or Fibonacci spiral could reorder memory so spatial neighbours are even closer in the buffer. HexGrid.swift computes Morton codes but the GPU pipeline does not use them yet — it runs on flat row-major indices. The 7-colouring is independent of memory layout. The colour is computed from (col, row) coordinates. Reordering memory changes cache performance, not safety. A Fibonacci spiral on a hex lattice would naturally visit cells in an order where neighbours are close in sequence. This is an alternative memory layout — or purely visual. The colouring still applies: same formula, different order of storage or rendering. GPU clock: You asked about the GPU oscillator. Within one dispatch (one colour group), ALL threads fire on the same clock edge. There is no sequential ordering within a group. That is why the colouring must guarantee no conflicts — because there is literally no "first" thread. They are all first. Simultaneously.

Memory layout and execution scheduling are orthogonal. Currently we use flat row-major storage. Morton Z-curve code exists in HexGrid.swift but is not yet wired into the GPU pipeline. Your Fibonacci spiral intuition maps to the memory layout side — a reordering where spatial neighbours are stored close in memory. The GPU hardware does not spiral. It fires all threads in a group at the exact same clock cycle. No sequence. No order. All at once. That is why the colouring must be perfect.

6 / 6