Flood-It: A Game as an Architecture Lens
A board of numbers, a move as a pure function and a greedy solver show on a small scale what gets blurry in large systems: the separation of core logic, strategy and presentation.
Flood-It: A Game as an Architecture Lens
var board = [
[2, 1, 1, 3],
[1, 2, 3, 0],
[0, 1, 2, 2],
[3, 3, 0, 1]
];
function flood(board, color) {
// returns a new board where the top-left region
// has captured all adjacent cells of the picked color
}
Flood-It does not need more of a model than that. The game is quickly explained: a board of colored cells, with a region in the top left that initially consists of a single cell. Each move, you pick a color. The region takes on that color and swallows all orthogonally adjacent cells that already have it. The goal is a single-colored board – in as few moves as possible.
A good two weeks ago, I created the repository kata-flood-it for this, a fresh kata in JavaScript. So far the README consists of a single line, and I do not promise more here either: not a finished product, but a small experiment. The appeal is not in the game itself anyway – Flood-It has long been on every smartphone. The appeal is that such a tiny program works like a lens. There is no database, no framework, no network layer behind which bad splits could hide. What remains are exactly three things: a model, a strategy and a presentation. And the question of where the boundaries between them run.
The board is a decision#
The first decision is made before a single line of game logic exists: what is the board? My answer is at the top – a two-dimensional array of numbers. That looks trivial, but it is not. You see the obvious alternative in many small browser games: the board exists only as a collection of div elements, and the truth about the game state is hidden in CSS class names. If you want to know which color a cell has, you ask the DOM. The presentation has thereby become the model, and all logic has to go through it.
The second, smaller decision: numbers instead of color names. In the model there is no "red" and no "#ff0000", only 0 to 5. Which number corresponds to which shade is a question of presentation – on the console perhaps a letter, in the browser a CSS class, on a canvas a fill style. The model knows nothing about it, and that is exactly what makes it hold up.
While writing, I noticed how much material for discussion is in these two lines alone. In a review of a large system we talk about the same questions – where does the leading state live, who may read it, who may change it – just spread across dozens of files. Here the whole question fits on one screen.
The move as a function#
The core of the game is a flood fill: starting from the top left, all connected cells of the old color are collected and recolored. Classically, you solve this recursively (depth-first search) or with a queue (breadth-first search). I chose breadth-first search because it gets by without deep call stacks – on large boards, naive recursion in JavaScript eventually topples over with a stack overflow.
function flood(board, color) {
var next = board.map(function (row) { return row.slice(); });
var target = next[0][0];
if (target === color) return next;
var queue = [[0, 0]];
while (queue.length > 0) {
var cell = queue.shift();
var row = cell[0];
var col = cell[1];
if (row < 0 || col < 0 || row >= next.length || col >= next[0].length) continue;
if (next[row][col] !== target) continue;
next[row][col] = color;
queue.push([row - 1, col], [row + 1, col], [row, col - 1], [row, col + 1]);
}
return next;
}
The most important property is in the first line: flood does not change the board it is given but returns a new one. That costs a few copies, and queue.shift() is not the fastest operation in the world on long arrays either – for a 14×14 board, neither matters at all. What I get in return is considerable: a move is a value. The game history is simply an array of boards, undo is an index that jumps back by one, and a replay is a loop. I did not have to build any of this separately.
On top of that comes a second pure function that detects the end of the game:
function isSolved(board) {
return board.every(function (row) {
return row.every(function (cell) {
return cell === board[0][0];
});
});
}
Neither function knows about move limits, buttons or scores. Each answers exactly one question about the board. Everything else – how many moves are allowed, whether the game is lost, what happens next – belongs somewhere else.
Tests against the logic, not against the DOM#
Testing browser UIs is tedious in 2014: you need a real or headless browser, the runs are slow, and the tests break as soon as a CSS class changes. The kata shows the way out on a small scale: if the core logic consists of pure functions in CommonJS modules, the tests run with Mocha directly on Node – in milliseconds, without a browser. For delivery, Browserify then bundles the same modules for the browser. One module format, two runtimes.
var assert = require('assert');
var flood = require('./flood');
describe('flood', function () {
it('captures adjacent cells of the picked color', function () {
var board = [
[0, 1],
[1, 1]
];
assert.deepEqual(flood(board, 1), [
[1, 1],
[1, 1]
]);
});
it('does not mutate the given board', function () {
var board = [
[0, 1],
[1, 1]
];
flood(board, 1);
assert.deepEqual(board, [
[0, 1],
[1, 1]
]);
});
});
The second example matters more to me than the first. Whether a function changes its input is a question of contract, and contracts belong in tests – not in comments. In a larger project, I once spent two days chasing a bug that came from exactly this: a helper function that sorted an array passed to it and thereby silently rearranged the caller’s state. The test above costs six lines and rules out this entire class of bugs.
What is also striking is what does not appear in the tests: no document, no selector, no simulated click. If the tests for the game rules need a browser, that is not a testing problem but an architectural finding – it means logic is stuck in the presentation.
The strategy is a layer of its own#
Besides the rules, Flood-It has a second domain level: how do you play well? The obvious heuristic is greedy – try every color, count how large the region would be afterwards, and take the color with the largest gain.
function countCaptured(board) {
var marked = flood(board, -1);
var count = 0;
marked.forEach(function (row) {
row.forEach(function (cell) {
if (cell === -1) count += 1;
});
});
return count;
}
function bestMove(board, colors) {
var best = { color: null, captured: -1 };
colors.forEach(function (color) {
if (color === board[0][0]) return;
var captured = countCaptured(flood(board, color));
if (captured > best.captured) {
best = { color: color, captured: captured };
}
});
return best.color;
}
Two observations. First: countCaptured does not invent its own traversal, but misuses flood with a color that does not occur in the game and counts the markings. That only works because flood is pure – I can safely call it “on trial” as often as I like. Exactly this trial run is prohibitively expensive in systems with scattered, mutable state: if you want to ask a what-if question there, you need mocks, transaction rollbacks or a staging environment.
Second: the greedy strategy is measurably not optimal, and that is not sloppiness on my part. Clifford, Jalsenius, Montanaro and Sach showed in 2010 that Flood-It is NP-hard from three colors on – so an efficient optimal strategy is not to be expected. For the architecture, that means: the strategy will change. Greedy today, perhaps with two moves of lookahead tomorrow. That is why it is a layer of its own that talks to the core only through flood, countCaptured and isSolved. The move counter and the move limit belong here too, not in the rules and not in the UI – they are game mode, not game law.
The presentation as an exchangeable skin#
The presentation sits on the very outside. It reads the board and draws it – nothing more:
function render(board, element) {
element.innerHTML = '';
board.forEach(function (row) {
var line = document.createElement('div');
row.forEach(function (cell) {
var field = document.createElement('span');
field.className = 'cell color-' + cell;
line.appendChild(field);
});
element.appendChild(line);
});
}
The click handler on the color buttons translates a DOM event into a call to the core logic and re-renders the result. The presentation never tinkers with the board itself; it is a skin you can peel off and replace. A canvas instead of the div soup? Only render changes. A console version with letters instead of colors to play through the kata in Node? Again only render. I did not even bring in jQuery – for twenty lines of DOM work it contributes nothing, and the temptation to park state in data attributes stays outside.
flowchart TB
subgraph ui["Presentation"]
H[Click handler] --> R[render]
end
subgraph strategy["Strategy / game mode"]
G[bestMove] --> Z[Move counter +<br/>move limit]
end
subgraph core["Core logic (pure functions)"]
F[flood] --> I[isSolved]
F --> C[countCaptured]
end
ui --> strategy
strategy --> core
ui --> coreThe arrows all point inward. The core logic knows nobody, the strategy knows only the core, the presentation may use both. There is no way back – flood cannot even know whether it was just called by a test, by the greedy solver or by a click.
What gets blurry at scale#
Nothing about this split is new. Layers, pure core logic, thin edges – that has been in every architecture book for years. What is interesting is why it still blurs so often at scale and stays so clear on a small scale. My observation: in large systems there is always a convenient reason for the small boundary violation. Validation ends up in the controller because the request object is already lying around there. The discount is calculated in the template because the number is only needed there. Every single shortcut is understandable, and in sum, after two years, nobody can say anymore where the business rules actually live.
The kata does not have these excuses. If I build a move counter into flood, I see the foreign body immediately, because the function used to have seven lines. That is exactly what I mean by a lens: the small program does not magnify the solution, but the violation.
I take a few questions from the game straight into project work:
- What is our “board” – the one data structure that holds the leading state – and how many places may change it?
- Which operation is our “move,” and is it tangible as a value – traceable, repeatable, reversible?
- Can we work through a decision “on trial” without touching real state?
- Do the tests for the rules run without a browser, without a database, without a network?
If you cannot answer these questions for a large system, you do not have a tooling problem. What is missing is the boundary that is four function names wide in the kata.
The bottom line#
The kata has deliberately stayed small, and the repository will not become a library either – it is a finger exercise with a finding. The finding: the separation of core logic, strategy and presentation is not a question of system size and not a question of framework. It is just as present or absent in eighty lines of ES5 as in an application with eighty thousand lines. The only difference is that in eighty lines you cannot overlook it.
That is why such a game is worth it precisely when you do not really need it. Not as algorithm training – the flood fill is written in an evening. But as a test bench for your own habits: where do I put state when nobody gives me a structure? Do I write the UI first or the contract first? The answers you give yourself in a color flood game are the same ones you give later under deadline pressure – just more honest.
Further reading#
- Repository for the kata: https://github.com/MikeBild/kata-flood-it
- Flood fill (algorithm overview): https://en.wikipedia.org/wiki/Flood_fill
- Clifford, Jalsenius, Montanaro, Sach: “The Complexity of Flood Filling Games” (2010): https://arxiv.org/abs/1001.4420
- Mocha (test framework): https://mochajs.org/
- Browserify: http://browserify.org/
Revised and translated from German with the help of AI.