Flood-It: ein Spiel als Architektur-Lupe

Diesen Beitrag anhören (10 Min.)

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
}

Mehr Modell braucht Flood-It nicht. Das Spiel ist schnell erklärt: ein Brett aus Farbfeldern, oben links sitzt eine Region, die anfangs aus einem einzigen Feld besteht. Pro Zug wählt man eine Farbe. Die Region nimmt diese Farbe an und schluckt dabei alle orthogonal angrenzenden Felder, die bereits so gefärbt sind. Ziel ist ein einfarbiges Brett – in möglichst wenigen Zügen.

Vor gut zwei Wochen habe ich dafür das Repository kata-flood-it angelegt, eine frische Kata in JavaScript. Das README besteht bisher aus einer einzigen Zeile, und mehr verspreche ich hier auch nicht: kein fertiges Produkt, sondern ein kleines Experiment. Der Reiz liegt ohnehin nicht im Spiel selbst – Flood-It gibt es längst auf jedem Smartphone. Der Reiz liegt darin, dass so ein winziges Programm wie eine Lupe wirkt. Es gibt keine Datenbank, kein Framework, keinen Netzwerk-Layer, hinter dem sich schlechte Schnitte verstecken könnten. Was übrig bleibt, sind genau drei Dinge: ein Modell, eine Strategie und eine Darstellung. Und die Frage, wo die Grenzen zwischen ihnen verlaufen.

Das Brett ist eine Entscheidung

Die erste Entscheidung fällt, bevor eine Zeile Spiellogik existiert: Was ist das Brett? Oben steht meine Antwort – ein zweidimensionales Array aus Zahlen. Das wirkt banal, ist es aber nicht. Die naheliegende Alternative sieht man in vielen kleinen Browser-Spielen: Das Brett existiert nur als Sammlung von div-Elementen, und die Wahrheit über den Spielzustand steckt in CSS-Klassennamen. Wer wissen will, welche Farbe ein Feld hat, fragt das DOM. Damit ist die Darstellung zum Modell geworden, und jede Logik muss durch sie hindurch.

Die zweite, kleinere Entscheidung: Zahlen statt Farbnamen. Im Modell gibt es kein "red" und kein "#ff0000", nur 0 bis 5. Welche Zahl welchem Farbton entspricht, ist eine Frage der Darstellung – auf der Konsole vielleicht ein Buchstabe, im Browser eine CSS-Klasse, auf einem Canvas ein Füllstil. Das Modell weiß davon nichts, und genau das macht es tragfähig.

Mir ist beim Schreiben aufgefallen, wie viel Diskussionsstoff allein in diesen zwei Zeilen steckt. In einem Review über ein großes System reden wir über dieselben Fragen – wo liegt der führende Zustand, wer darf ihn lesen, wer ihn ändern –, nur verteilt über Dutzende Dateien. Hier passt die ganze Frage auf einen Bildschirm.

Der Zug als Funktion

Der Kern des Spiels ist ein Flood-Fill: Von oben links aus werden alle zusammenhängenden Felder der alten Farbe eingesammelt und umgefärbt. Klassisch löst man das rekursiv (Tiefensuche) oder mit einer Warteschlange (Breitensuche). Ich habe die Breitensuche gewählt, weil sie ohne tiefe Aufrufstapel auskommt – bei großen Brettern kippt die naive Rekursion in JavaScript irgendwann mit einem Stack Overflow um.

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;
}

Die wichtigste Eigenschaft steht in der ersten Zeile: flood verändert das übergebene Brett nicht, sondern liefert ein neues. Das kostet ein paar Kopien, und queue.shift() ist auf langen Arrays auch nicht die schnellste Operation der Welt – für ein 14×14-Brett ist beides völlig egal. Was ich dafür bekomme, ist erheblich: Ein Zug ist ein Wert. Die Spielhistorie ist schlicht ein Array von Brettern, Undo ist ein Index, der um eins zurückspringt, und ein Replay ist eine Schleife. Nichts davon musste ich extra bauen.

Dazu kommt eine zweite reine Funktion, die das Spielende feststellt:

function isSolved(board) {
  return board.every(function (row) {
    return row.every(function (cell) {
      return cell === board[0][0];
    });
  });
}

Beide Funktionen kennen weder Züge-Limits noch Buttons noch Punktestände. Sie beantworten genau eine Frage über das Brett. Alles andere – wie viele Züge erlaubt sind, ob das Spiel verloren ist, was danach passiert – gehört woanders hin.

Tests gegen die Logik, nicht gegen das DOM

Browser-Oberflächen zu testen ist 2014 mühsam: Man braucht einen echten oder kopflosen Browser, die Läufe sind langsam, und die Tests brechen, sobald sich eine CSS-Klasse ändert. Die Kata zeigt den Ausweg im Kleinen: Wenn die Kernlogik aus reinen Funktionen in CommonJS-Modulen besteht, laufen die Tests mit Mocha direkt auf Node – in Millisekunden, ohne Browser. Für die Auslieferung bündelt Browserify dieselben Module dann für den Browser. Ein Modulformat, zwei Laufzeitumgebungen.

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]
    ]);
  });
});

Das zweite Beispiel ist mir wichtiger als das erste. Ob eine Funktion ihre Eingabe verändert, ist eine Vertragsfrage, und Verträge gehören in Tests – nicht in Kommentare. In einem größeren Projekt habe ich einmal zwei Tage einem Fehler hinterhergesucht, der genau daher kam: eine Hilfsfunktion, die ein übergebenes Array sortierte und damit still den Zustand des Aufrufers umbaute. Der Test oben kostet sechs Zeilen und schließt diese ganze Fehlerklasse aus.

Auffällig ist auch, was in den Tests nicht vorkommt: kein document, kein Selektor, kein simulierter Klick. Wenn die Tests für die Spielregeln einen Browser brauchen, ist das kein Test-Problem, sondern ein Architektur-Befund – dann steckt Logik in der Darstellung.

Die Strategie ist eine eigene Schicht

Flood-It hat neben den Regeln noch eine zweite fachliche Ebene: Wie spielt man gut? Die naheliegende Heuristik ist gierig – probiere jede Farbe, zähle, wie groß die Region danach wäre, und nimm die Farbe mit dem größten Zuwachs.

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;
}

Zwei Beobachtungen. Erstens: countCaptured erfindet keine eigene Traversierung, sondern missbraucht flood mit einer Farbe, die im Spiel nicht vorkommt, und zählt die Markierungen. Das geht nur, weil flood rein ist – ich kann es gefahrlos „auf Probe" aufrufen, so oft ich will. Genau dieser Probelauf ist in Systemen mit verstreutem, veränderlichem Zustand unbezahlbar teuer: Wer dort eine Was-wäre-wenn-Frage stellen will, braucht Mocks, Transaktions-Rollbacks oder eine Staging-Umgebung.

Zweitens: Die gierige Strategie ist messbar nicht optimal, und das ist keine Schludrigkeit meinerseits. Clifford, Jalsenius, Montanaro und Sach haben 2010 gezeigt, dass Flood-It ab drei Farben NP-schwer ist – eine effiziente optimale Strategie ist also nicht zu erwarten. Für die Architektur heißt das: Die Strategie wird sich ändern. Heute gierig, morgen vielleicht mit zwei Zügen Vorausschau. Deshalb ist sie eine eigene Schicht, die nur über flood, countCaptured und isSolved mit dem Kern spricht. Auch der Zugzähler und das Zug-Limit gehören hierher, nicht in die Regeln und nicht in die Oberfläche – sie sind Spielmodus, nicht Spielgesetz.

Die Darstellung als austauschbare Haut

Ganz außen sitzt die Darstellung. Sie liest das Brett und zeichnet es – mehr nicht:

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);
  });
}

Der Klick-Handler auf den Farbknöpfen übersetzt ein DOM-Ereignis in einen Aufruf der Kernlogik und rendert das Ergebnis neu. Die Darstellung schreibt nie selbst am Brett herum; sie ist eine Haut, die man abziehen und ersetzen kann. Ein Canvas statt der div-Suppe? Nur render ändert sich. Eine Konsolen-Version mit Buchstaben statt Farben, um die Kata in Node durchzuspielen? Wieder nur render. jQuery habe ich gar nicht erst hereingeholt – für zwanzig Zeilen DOM-Arbeit trägt es nichts bei, und die Versuchung, Zustand in data-Attributen zu parken, bleibt draußen.

flowchart TB
  subgraph ui["Darstellung"]
    H[Click-Handler] --> R[render]
  end
  subgraph strategy["Strategie / Spielmodus"]
    G[bestMove] --> Z[Zugzähler +<br/>Zug-Limit]
  end
  subgraph core["Kernlogik (pure Funktionen)"]
    F[flood] --> I[isSolved]
    F --> C[countCaptured]
  end
  ui --> strategy
  strategy --> core
  ui --> core

Die Pfeile zeigen alle nach innen. Die Kernlogik kennt niemanden, die Strategie kennt nur den Kern, die Darstellung darf beide benutzen. Rückwärts gibt es keinen Weg – flood kann gar nicht wissen, ob es gerade von einem Test, vom Greedy-Löser oder von einem Klick aufgerufen wurde.

Was im Großen verschwimmt

Nichts an dieser Aufteilung ist neu. Schichten, reine Kernlogik, dünne Ränder – das steht seit Jahren in jedem Architektur-Buch. Interessant ist, warum es im Großen trotzdem so oft verwischt und im Kleinen so klar bleibt. Meine Beobachtung: In großen Systemen gibt es immer einen bequemen Grund für den kleinen Grenzverstoß. Die Validierung landet im Controller, weil dort das Request-Objekt schon herumliegt. Der Rabatt wird im Template ausgerechnet, weil die Zahl nur dort gebraucht wird. Jede einzelne Abkürzung ist verständlich, und in Summe kann nach zwei Jahren niemand mehr sagen, wo die Geschäftsregeln eigentlich stehen.

Die Kata hat diese Ausreden nicht. Wenn ich in flood einen Zugzähler einbaue, sehe ich den Fremdkörper sofort, weil die Funktion vorher sieben Zeilen hatte. Genau das meine ich mit Lupe: Das kleine Programm vergrößert nicht die Lösung, sondern den Verstoß.

Ein paar Fragen nehme ich aus dem Spiel direkt mit in die Projektarbeit:

Was ist unser „Brett" – die eine Datenstruktur, die den führenden Zustand hält – und wie viele Stellen dürfen sie verändern?
Welche Operation ist unser „Zug", und ist sie als Wert greifbar – nachvollziehbar, wiederholbar, rückgängig zu machen?
Können wir eine Entscheidung „auf Probe" durchrechnen, ohne echten Zustand anzufassen?
Laufen die Tests für die Regeln ohne Browser, ohne Datenbank, ohne Netz?

Wer diese Fragen für ein großes System nicht beantworten kann, hat kein Tooling-Problem. Es fehlt die Grenze, die in der Kata vier Funktionsnamen groß ist.

Unterm Strich

Die Kata ist bewusst klein geblieben, und das Repository wird auch keine Bibliothek werden – es ist eine Fingerübung mit Befund. Der Befund: Die Trennung von Kernlogik, Strategie und Darstellung ist keine Frage der Systemgröße und keine Frage des Frameworks. Sie ist in achtzig Zeilen ES5 genauso vorhanden oder abwesend wie in einer Anwendung mit achtzigtausend Zeilen. Der Unterschied ist nur, dass man sie in achtzig Zeilen nicht übersehen kann.

Deshalb lohnt sich so ein Spiel gerade dann, wenn man es eigentlich nicht nötig hat. Nicht als Algorithmus-Training – der Flood-Fill ist an einem Abend geschrieben. Sondern als Prüfstand für die eigenen Gewohnheiten: Wo lege ich Zustand ab, wenn mir niemand eine Struktur vorgibt? Schreibe ich zuerst die Oberfläche oder zuerst den Vertrag? Die Antworten, die man sich bei einem Farbflut-Spiel gibt, sind dieselben, die man später unter Termindruck gibt – nur ehrlicher.

Weiterführende Quellen

Repository zur Kata: https://github.com/MikeBild/kata-flood-it
Flood Fill (Algorithmus-Überblick): 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/