Floodfill ohne Stack: 16 Farben ersetzen den gesamten Rekursionsspeicher

A Stackless Floodfill Automaton

Nils M Holm zeigt, wie sich der klassische rekursive Floodfill ohne Stack und ohne jede andere dynamische Datenstruktur umsetzen lässt: Statt Koordinaten zu speichern, kodiert jeder Pixel seinen eigenen Zustand in einer von 16 ungenutzten Farben – Richtung zum Ursprung und nächste zu probierende Richtung. Entstanden ist die Variante für ein textbasiertes Minesweeper auf einem BASIC-System mit nur 7K Byte Programmspeicher und 30 Verschachtelungsebenen. Die Komplexität bleibt linear, O(4n).