Flood-It from scratch: flood-fill, and why greedy isn't quite optimal

Day 28 of my "build a small game a day, from nothing" run. Flood-It looks like a toddler's colour toy and hides a genuinely hard problem underneath. You flood a grid of coloured tiles until the whole board is one colour, in as few moves as you can. Trivial to play, and — it turns out — NP-hard to play perfectly.

Play it (LOOK / UNDERSTAND / BUILD tabs) here: https://dev48v.infy.uk/game/day28-flood-it.html

The rules in one breath

You own the connected clump of same-coloured tiles in the top-left corner — your territory. Pick a colour, and your whole territory repaints to it, swallowing any neighbouring tiles that already had that colour. Repeat until the board is a single colour. Beat the move limit and you win.

That's the whole game. Everything else is just being precise about "the connected corner clump, and how it grows."

The board is a graph wearing a disguise

Store the board as a 2-D array of small integers, each one an index into a palette:

let grid = [];   // grid[r][c] = colour id 0..COLORS-1

That array is really a graph. Every cell is a node; edges connect orthogonal neighbours that share a colour. Your territory isn't "every red tile" — it's only the red tiles you can reach from the corner by walking through red neighbours. A red blob on the far side of the board is a different connected component, and it doesn't count until your flood actually touches it. Getting that distinction right is the entire game.

Flood-fill is the whole engine

Finding the territory is a flood-fill — the exact breadth-first search a paint-bucket tool runs. Start a stack with the corner, mark it seen, then keep popping a cell and pushing its unvisited, same-coloured neighbours:

const DIRS = [[1,0],[-1,0],[0,1],[0,-1]];
function originRegion(){
  const target = grid[0][0];
  const seen = Array.from({length:SIZE}, () => Array(SIZE).fill(false));
  const stack = [[0,0]]; seen[0][0] = true;
  const cells = [[0,0]];
  while (stack.length){
    const [r,c] = stack.pop();
    for (const [dr,dc] of DIRS){
      const nr=r+dr, nc=c+dc;
      if (inB(nr,nc) && !seen[nr][nc] && grid[nr][nc]===target){
        seen[nr][nc]=true; stack.push([nr,nc]); cells.push([nr,nc]);
      }
    }
  }
  return cells;   // exactly the connected origin region
}

Every cell gets visited at most once, so it's O(cells). This single routine does everything: it highlights your territory, applies a move, tests the win, and scores hints.

A move is almost nothing

Find your region, paint every cell in it the new colour, done:

function play(newColor){
  if (newColor === grid[0][0]) return false;   // no-op, not a move
  const region = originRegion();
  for (const [r,c] of region) grid[r][c] = newColor;
  moves++;
  return true;
}

The "absorption" people find satisfying is free. After you repaint, tiles that sat next to your region and already had the new colour are now the same colour as you — so the next flood-fill walks straight into them. Nothing merged. Your connected component just got bigger because the colours match at the boundary now.

Win detection reuses the same idea instead of inventing a new check: you've won when one flood covers everything.

const won = () => originRegion().length === SIZE * SIZE;

The hint, and where it falls short

How do you choose a colour? The cheap, strong move is greedy: try each colour on a copy of the board, keep whichever grows your territory the most this turn.

function greedyBest(){
  const cur = grid[0][0]; let best=-1, bestSize=-1;
  for (let col=0; col<COLORS; col++){
    if (col === cur) continue;
    const copy = grid.map(row => row.slice());
    floodGrid(copy, col);                 // flood the copy with col
    const size = regionOf(copy).length;   // resulting territory size
    if (size > bestSize){ bestSize = size; best = col; }
  }
  return best;
}

Here's the honest bit I put right in the UNDERSTAND tab: greedy is not optimal. Sometimes the fewest-moves solution needs a move that grabs almost nothing now to set up a huge grab next turn — a sacrifice greedy will never make, because it only ever maximises the immediate gain. Finding the true minimum is a search over sequences of moves, and Flood-It is NP-hard in general. Real solvers use lookahead or A*/beam search over board states, with a heuristic like "how many colours are still left on the board."

So I did the pragmatic thing. The game simulates the greedy solver on your exact board, then sets the move limit a couple above it. Every board is winnable — greedy itself fits — and beating greedy is the real bragging-rights challenge.

The takeaway

The mechanics of a grid game are almost always linear in the number of cells. It's the search for the best play that gets expensive. Flood-It is the cleanest example of that gap I've built so far: a five-line move, and an optimal strategy nobody knows how to compute quickly.

Vanilla JS, no libraries, runs offline. Tomorrow: Maze — carve one with randomised DFS, solve it with BFS.