Rekursives Floodfill nach Iteratives Floodfill, wie mache ich das?

[Ralph S. (jjflash)]

Ich möchte ein altes Minesweeper-Spieleprogramm von mir vom PC zu einem 
Mikrocontroller portieren.

Das ganze funktioniert auch gut, hat aber einen gewaltigen 
Schönheitsfehler. Ich verwende zum Suchen freier benachbarter 
Mienenfelder einen rekursiven Floodfillalgorithmus, prinzipiell genau 
so, wie ich auch eine umrandete Grafik mit einem Farbwert fülle.

Code hier und nicht als Anhang eingefügt, da ich denke dass das kein 
wirklich großes Listing ist:

#define mfeldx         18
#define mfeldy         18

#define mfsize        (mfeldx * mfeldy)

uint8_t mfeld[mfsize];

int     aktpos;

// markiert 8 Nachbarn eines Nullmienenfeldes
void mark8nb(int cpos, uint8_t *bptr);

/* ----------------------------------------------------------
        fill4
        
        Rekursive Suche nach benachbarten Leerfeldern
   ---------------------------------------------------------- */
void fill4(int cpos, uint8_t *bptr)
{
  uint8_t value, ovalue;

  value = *(bptr+cpos);

  if (!value)                     // ohne angrenzende Mienen
  {
    mark8nb(cpos, bptr);
    *(bptr+cpos)= 9;              // als Leerfeld markieren

    fill4(cpos + mfeldx, bptr);   // x, y+1
    fill4(cpos - mfeldx, bptr);   // x, y-1
    fill4(cpos -1, bptr);         // x-1, y
    fill4(cpos +1, bptr);         // x+1, y

  }
}

...
aktpos= 100;
fill4(aktpos, &mfeld[0]);

Das Mienenfeld ist nur in einem eindimensionalen Array mfeld[] abgelegt 
und eine x,y Koordinate berechnet sich dann aus einer Startposition 
aktpos relativ zu den Konstanten mfeldx und mfeldy. Im Array selbst ist 
ein Zahlenwert 0x10 für eine vorhandene Miene eingetragen, die 
Füllfunktion selbst legt im Array selbst den Zahlenwert 0x09 ab, wenn 
dieses als Leerfeld markiert wird.

Grenzt an ein Element eine oder mehrere Mienen, trägt mark8nb die 
Anzahl umliegender Mienen ins Array ein.

Wie gesagt funktioniert das ganze gut, allerdings ist der Rambedarf für 
einen Controller groß: Für ein 18x18 großes Feld benötigt mein Programm 
für die ungünstigste Konstellation (getestet mit nur einer einzigen 
eingetragenen Miene) einen Controller mit mindestens 7 kbyte Ram um das 
gesamte Feld auszufüllen. Hat der Controller weniger Ram, kommt es 
logischerweise zu einem Stack-Overflow.

Wie kann ich die Funktion fill4 iterativ definieren? Irgendwie stehe 
ich hier auf dem Schlauch.

Gruß,
Ralph

[Walter T. (nicolas)]

Ralph S. schrieb:
> Wie kann ich die Funktion fill4 iterativ definieren?

Gar nicht. Der Ansatz muss schon anders gewählt werden.

Du hast genug Speicherplatz, um die Zahl für jedes Feld zu speichern, 
und und kannst die Zahl einfach durch einen einzelnen Durchlauf durch 
alle Felder ermitteln.

Sprich: Du durchläufst alle Felder und zählst zusammen, wobei 
logischerweise die Felder, die noch nicht dran waren, noch nicht 
berücksichtigt werden. Wenn sich durch ein späteres Feld der Wert in 
einem vorhergegangenen Feld erhöht, wird das nachgetragen. Das können ja 
maximal 4 Felder sein.

Ralph S. schrieb:
> Miene

Trittst Du auf eine Mine, ist es zu spät, noch gute Miene zum bösen 
Spiel zu machen.

Nachtrag: Eigentlich brauchst Du die Zahl ja noch nicht einmal. Für das 
automatische Aufdecken reicht es ja aus zu wissen, ob überhaupt ein 
Nachbar mit Mine existiert.

Der obige Algorithmus kann aber sowohl die Anzeige der Anzahl als auch 
das automatische aufdecken, das Du bisher mit floodfill gelöst hast, 
realisieren.

[Rainer W. (rawi)]

Ralph S. schrieb:
> Ich verwende zum Suchen freier benachbarter
> Mienenfelder einen rekursiven Floodfillalgorithmus, prinzipiell genau
> so, wie ich auch eine umrandete Grafik mit einem Farbwert fülle.

Was ist ein Mienenfeld?
Eine blöde Miene macht der Spieler gewöhnlich erst, wenn er auf eine 
Mine tritt, d.h. es gibt genau eine Miene von jedem Spieler, wieso ein 
Array?

scnr

[Ralph S. (jjflash)]

Walter T. schrieb:
> Ralph S. schrieb:
>> Miene

Rainer W. schrieb:
> Was ist ein Mienenfeld?
> Eine blöde Miene macht der Spieler gewöhnlich erst, wenn er auf eine
> Mine tritt, d.h. es gibt genau eine Miene von jedem Spieler, wieso ein
> Array?
>
> scnr

:-) okay: Ich schreibe Mine nie mehr mit "ie", auch wenn ich gute Mine 
zum bösen (Mienen)Spiel mache... :-)

( irgendwie war da jetzt wieder etwas falsch, oder ? :-) )

Die Strafarbeit:

for (int i= 0; i< 100; i++) { printf("\n\rMine"); }

[Rainer W. (rawi)]

Ralph S. schrieb:
> :-) okay: Ich schreibe Mine nie mehr mit "ie", auch wenn ich gute Mine
> zum bösen (Mienen)Spiel mache... :-)

Das war nur der eine Aspekt ;-)
Ein Minenfeld bezeichnet im gewöhnlichen Sprachgebrauch eine verminte 
Fläche, nicht das einzelne Flächenelement (auf dem eine Mine liegen 
kann). Ein "benachbartes" Minenfeld wäre also ein weiteres Array, in dem 
es ebenfalls "Planstellen" für Minen gibt.

[Helmut H. (helmuth)]

Verständnisfrage: wird der Rand richtig berücksichtigt?
bei z.B. 18*18 Feldern folgende Feldanordnung:

0   1  2 ... 17
18 19 20 ... 35
36 37 ...
...

bptr z.B. auf 18 prüft Felder 36,0,17,19. 17 ist doch kein Nachbar?
Bei Feldern in der obersten und untersten Reihe wird ausserhalb des 
arrays geprüft? z.B. 1 prüft 19,-17,0,2.

[Michael B. (laberkopp)]

Ralph S. schrieb:
> Wie kann ich die Funktion fill4 iterativ definieren?

So nicht.

Wenn du die Rekursion in eune Schleife unwandelst, in dem du 3 der 4 
Azfrufe fur später in einen Speicher schreibst, dparst du keinen 
Speicher.

Du brauchst einen anderen Algorithmus.

Üblich ist der Lee-Algorithmus, ein Durchnumerieren der Felder, also 
iterieren uber das Brett und in jedem Feld eine Nummer speichern.

Da du das Feld sowieso hast, und hoffentlich 2 bit übrig, braucht das 
keinen weiteren Speicher, nur Laufzeit.

[Clemens S. (zoggl)]

du könntest den reservierten Speicherbereich besser nutzen.

Da deine Mienen eh im Array gespeichert sind, kannst du die 
Mienennachbarn einmal berechnen und darin codiert speichern.

0 verdecktes Feld
1-8 Mienen Anzahl offen
9 aktives Feld
10 Mine
11-19 mit mark8nb berechnete verdeckte Minen.
99 ausgelöste Mine

damit ersparst du dir schonmal die Mehrfachberechnung der Nachbarfelder

und dann einen iterativen Floodfill starten:

https://stackoverflow.com/questions/1257117/a-working-non-recursive-floodfill-algorithm-written-in-c

[Rainer W. (rawi)]

Michael B. schrieb:
> Wenn du die Rekursion in eune Schleife unwandelst, in dem du 3 der 4
> Azfrufe fur später in einen Speicher schreibst, dparst du keinen
> Speicher.

Schreib einfach nicht ganz so hektisch ...
Ist es dir nicht peinlich, so einen Text zu veröffentlichen?

[Helmut H. (helmuth)]

Clemens S. schrieb:
> 0 verdecktes Feld
> 1-8 Mienen Anzahl offen
> 9 aktives Feld
> ...

Noch besser die Zahl der Nachbarminen
 0-8 Minen Anzahl offen
 9 Mine offen
 10 - 19 verdecktes Feld Typ 0-9

Die kleinlichen Rechtschreibkorrekturen stören.

[Michael B. (laberkopp)]

Helmut H. schrieb:
> Die kleinlichen Rechtschreibkorrekturen stören.

Rainer stört immer.

[Daniel A. (daniel-a)]

Da scheinen auch noch bound checks zu fehlen. Wenn du z.B. am linken 
Rand bist, und eins weiter Links gehst, kommst du eins weiter oben 
rechts raus. Und wenn du bei Position 0 warst, und eins links gehst, 
bist du im nirgendwo.

Ralph S. schrieb:
> Das Mienenfeld ist nur in einem eindimensionalen Array mfeld[] abgelegt
> und eine x,y Koordinate berechnet sich dann aus einer Startposition
> aktpos relativ zu den Konstanten mfeldx und mfeldy.

Warum machst du das so? Das Array wird dadurch nicht kleiner.
Ich würde das eher so machen: https://godbolt.org/z/3q9zGEjYW 
https://godbolt.org/z/KPczs5f4n

Ralph S. schrieb:
> Wie kann ich die Funktion fill4 iterativ definieren? Irgendwie stehe
> ich hier auf dem Schlauch.

Naja, du must halt nebeneinander liegende Felder in einer Schleife 
markieren. z.B. alle links vom Momentanen, dann die nächste Zeile, usw. 
Dann auf die andere Richtung. Aber ganz ohne Stack geht das so halt auch 
nicht, wenn es um ne Mauer rum muss, muss man sich dann merken, da 
wieder zurück zu kommen. In welcher Reihenfolge man die markiert, da 
gibt es viele Möglichkeiten.

Der Englische Wikipedia Artikel hat da mehr Algorithmen als der 
Deutsche: https://en.wikipedia.org/wiki/Flood_fill

[Walter T. (nicolas)]

Rainer W. schrieb:
> Ein Minenfeld bezeichnet im gewöhnlichen Sprachgebrauch eine verminte
> Fläche, nicht das einzelne Flächenelement (auf dem eine Mine liegen
> kann).

Ein Feld mit einer Mine ist ein Minenfeld. Ein Feld mit vielen Minen ist 
auch ein Minenfeld. Ein Spielfeld mit vielen Feldern mit jeweils keiner 
oder einer Mine ist auch ein Minenfeld.

Und wer schon einmal im ehemaligen Jugoslawien war weiß: Ein Feld, von 
dem man nicht weiß, ob da eine Mine ist, ist auch ein Minenfeld. Sicher 
ist sicher.

[Ben B. (Firma: Funkenflug Industries) (stromkraft)]

µC.net ist ein Minenfeld. Wie man sehr gut an diesem Thread sieht.
Irgendwas geht immer hoch.

[Ralph S. (jjflash)]

Daniel A. schrieb:
> Da scheinen auch noch bound checks zu fehlen. Wenn du z.B. am linken
> Rand bist, und eins weiter Links gehst, kommst du eins weiter oben
> rechts raus. Und wenn du bei Position 0 warst, und eins links gehst,
> bist du im nirgendwo.

Das 18x18 Array beherbergt ein 16x16 Minenfeld. Der Rand oben, unten, 
links und rechts wird mit einem Wert belegt, bei dem der Floodfill 
garantiert anhält.

Der Rand gehört somit nicht zum Spiel

[Yalu X. (yalu) (Moderator)]

Ralph S. schrieb:
> Für ein 18x18 großes Feld benötigt mein Programm
> für die ungünstigste Konstellation (getestet mit nur einer einzigen
> eingetragenen Miene) einen Controller mit mindestens 7 kbyte Ram um das
> gesamte Feld auszufüllen. Hat der Controller weniger Ram, kommt es
> logischerweise zu einem Stack-Overflow.

Ralph S. schrieb:
> Das 18x18 Array beherbergt ein 16x16 Minenfeld.

Im schlimmsten Fall braucht der Algorithmus eine Rekursionsebene pro
Feld, das sind 16·16=256. Bei jedem Aufruf werden die beiden
Funktionsargumente, die Rücksprungadresse und Zwischenergebnisse auf den
Stack geschoben. Da du offensichtlich eine 32-Bit-MCU verwendest, wo
Adressen und int-Werte 4 Bytes groß sind, kommen da schnell mehrere KB
an Stack-Daten zusammen.

Du kannst versuchen, ein paar Variablen vom Stack fernzuhalten:

- ovalue: entfernen, weil ungenutzt

- value: als static deklarieren, da sein Inhalt in den rekursiven
  Aufrufen problemlos überschrieben werden darf

- bptr: aus der Argumentliste entfernen und global machen, da sich der
  Inhalt sowieso nie ändert

Es kann aber gut sein, dass der Compiler das alles schon vorweggenommen
hat, so dass du damit keine (oder nur eine marginale) Verbesserung
erreichst.

Der einfachste Weg, das Ganze ohne Rekursion zu machen, ist hier
beschrieben:

  https://en.wikipedia.org/wiki/Flood_fill#Moving_the_recursion_into_a_data_structure

Statt des riesigen Programmstacks, auf den alles Mögliche geschoben
wird, gibt es hier einen dedizierten Daten-Stack, der nur die relevanten
Dinge, nämlich die Indizes der noch zu bearbeitenden Feldelemente,
enthält. Dieser Stack kann nicht größer als die Anzahl der Feldelemente
(256) werden. Bei der Verwendung von 16-Bit-Integers sind das gerade mal
512 Bytes.

Nimmst du statt des Stacks (FIFO) eine Queue (LIFO), kommst du evtl. mit
noch weniger Speicherplatz aus. Vermutlich reichen 61 Queue-Elemente,
also 122 Bytes.

Sowohl den Stack als auch die Queue kannst du auch einfache Weise als
Array plus einer (Stack) bzw. zwei (Queue) Indexvariablen, über die das
Array gelesen und beschrieben wird, implementieren.

[Daniel A. (daniel-a)]

Ich hab mir gerade eben mal diesen Algorithmus ausgedacht: 
https://godbolt.org/z/vjfG797jK

Ich bin mir aber noch nicht ganz sicher, ob der Algorithmus immer geht, 
und wie gross das Spielfeld da maximal sein dürfte.
Die Idee ist jedenfalls, erst mal alle zusammenhängenden Bereiche zu 
finden, jedem eine eigene ID zu geben, und dann später einfach alle 
Felder mit der ID zu ersetzen.

[Ralph S. (jjflash)]

Daniel A. schrieb:
> Die Idee ist jedenfalls, erst mal alle zusammenhängenden Bereiche zu
> finden, jedem eine eigene ID zu geben, und dann später einfach alle
> Felder mit der ID zu ersetzen.

... genau daran werkel ich im Moment und lustigerweise hantiere ich auch 
mit Bit 7 eines Chars als Kennung für ein Leerfeld. Komplett 
funktioniert es aber leider noch nicht.

Yalu X. schrieb:
> Im schlimmsten Fall braucht der Algorithmus eine Rekursionsebene pro
> Feld, das sind 16·16=256. Bei jedem Aufruf werden die beiden
> Funktionsargumente, die Rücksprungadresse und Zwischenergebnisse auf den
> Stack geschoben. Da du offensichtlich eine 32-Bit-MCU verwendest, wo
> Adressen und int-Werte 4 Bytes groß sind, kommen da schnell mehrere KB
> an Stack-Daten zusammen.

... das ganze habe ich so auch "gesehen" gehabt und hier grundsätzlich 
überlegt: 2 Argumente zu 4 Bytes plus den 4 Bytes für die 
Rücksprungadresse plus 4 Bytes für Funktionsergebnis machen für den Kopf 
16 Bytes aus.

Hinzu dann noch die lokale Variable.

Yalu X. schrieb:
> - ovalue: entfernen, weil ungenutzt
>
> - value: als static deklarieren, da sein Inhalt in den rekursiven
>   Aufrufen problemlos überschrieben werden darf
>
> - bptr: aus der Argumentliste entfernen und global machen, da sich der
>   Inhalt sowieso nie ändert

ovalue habe ich schlicht vergessen zu entfernen und war in einer frühen 
Version verwendet (wie gesagt fällt das auf einem PC so gar nicht auf, 
weil für so eine kleines Feld bei einem PC der Speicherbedarf lächerlich 
ist, obgleich das nicht die Schlampigkeit des Nichtentfernens 
entschuldigt).

Value als static und bptr global werde ich machen und sehen wie sich der 
Speicherbedarf ändert.

Vielen Dank für die Hinweise. Vielleicht ist es dann doch nicht 
notwendig, große Klimmzüge zu machen um das auf kleineren Controllern 
zum Laufen zu bringen.

[Yalu X. (yalu) (Moderator)]

Ralph S. schrieb:
> ovalue habe ich schlicht vergessen zu entfernen und war in einer frühen
> Version verwendet (wie gesagt fällt das auf einem PC so gar nicht auf,

Das ovalue sollte vom Compiler ohnehin wegoptimiert werden und führt
allenfalls zu einer Warnung "unused variable".

Ralph S. schrieb:
> Vielleicht ist es dann doch nicht notwendig, große Klimmzüge zu machen
> um das auf kleineren Controllern zum Laufen zu bringen.

Große Klimmzüge sind für einen anderen Algorithmus ja auch nicht
erforderlich. Hier ist die primitivste Variante, die ohne Rekursion
auskommt:

void fill4(int cpos, uint8_t *bptr) {
  static uint16_t stack[407];
  int ssize = 0;

  stack[ssize++] = cpos;
  while (ssize) {
    cpos = stack[--ssize];
    if (!bptr[cpos]) {
      mark8nb(cpos, bptr);
      bptr[cpos] = 9;              // als Leerfeld markieren

      stack[ssize++] = cpos - 1;        // x-1, y
      stack[ssize++] = cpos + mfeldx;   // x, y+1
      stack[ssize++] = cpos - mfeldx;   // x, y-1
      stack[ssize++] = cpos + 1;        // x+1, y
    }
  }
}

Streng genommen ist das kein anderer Algorithmus, sondern nur eine
andere (rekursionsfreie) Implementierung des von dir bereits verwendeten
Algorithmus.

Er arbeitet mit einem Daten-Stack für die noch zu bearbeitenden Felder.
Die Rekursion wird dadurch eliminiert, dass

- die rekursiven Funktionsaufrufe mit den Feldern als Argument durch
  Pushes der Felder auf den Stack ersetzt werden,

- das jeweils als nächstes zu bearbeitende Feld nicht als
  Funktionsargument empfangen, sondern vom Stack gepoppt wird und

- das Ganze in eine Schleife eingebettet wird, die so lange iteriert,
  bis der Stack leer ist, d.h. keine weiteren Felder mehr bearbeitet
  werden müssen.

Ich bin mir etwas unsicher bzgl. der maximalen Stack-Größe. Sie wird
vermutlich dann benötigt, wenn das Spielbrett komplett leer ist. Aus
dieser Ausgangssituation heraus habe ich den Algorithmus für alle 256
möglichen Startfelder durchlaufen lassen und und das Maximum von ssize
(der jeweils aktuellen Stack-Größe) bestimmt. Das Ergebnis ist 407, d.h.
so groß sollte das Stack-Array mindestens dimensioniert werden.

Die Reihenfolge der Push-Operationen in den Zeilen 12-15 habe ich
gegenüber deinem Programm etwas geändert, da sich dies leicht positiv
auf die erforderliche maximale Stack-Größe auswirkt.

Außerdem habe ich deine

*(bptr+cpos)

mit etwas syntaktischem Zucker versüßt und durch das äquivalente

bptr[cpos]

ersetzt ;-)

Ebenso kannst du in deinem Hauptprogramm gerne

&mfeld[0]

durch

mfeld

ersetzen.

[Ralph S. (jjflash)]

Hey, vielen Dank Yalu... leider komme ich nicht dazu das alles 
auszupropieren, weil ich leider wieder einmal mit der doofen COPD im 
Krankenhaus liege. Das letzte mal konnte ich das planen und hatte meine 
Spielzeuge mit im Krankenhaus, dieses mal leider nicht.

[Ralph S. (jjflash)]

... so, das war jetzt mal Denksportaufgabe für mich und ich denke ich 
habe das in Trockenübung verstanden.

Umsonst hast du dein Array nicht Stack getauft, ausgehend davon, dass 
alles von der Position 0 ausgeht und ssize (was hier dann der 
Stackpointer ist) eben entsprechend inkrementiert / dekrementiert wird.

Smile, ein "gespieltes" HRMPF, weil hier wohl alle meine Bemühungen 
davor abosolet werden, da mir das hier als eleganteste Lösung erscheint

[Michael B. (laberkopp)]

Yalu X. schrieb:
> Streng genommen ist das kein anderer Algorithmus, sondern nur eine
> andere (rekursionsfreie) Implementierung des von dir bereits verwendeten
> Algorithmus

Eben, daher Unsinn.

Es gibt ihn ja, den ohne Stack.

[Sigi S. (sermon)]

Erst mal ein bischen Grammatik lernen?!!

[Ralph S. (jjflash)]

Sigi S. schrieb:
> Erst mal ein bischen Grammatik lernen?!!

.. und warum? Hier ist ein technisches Forum gegeben und kein Forum für 
"Deutsch Leistungskurs"! Solange alle wissen um was es geht ist doch 
niemandem geschadet (außer den Deutsch-Pedanten denen ein unkorrektes 
Deutsch Tränen in die Augen treibt).

Grundsätzlich finde ich das Herumreiten auf Schreibfehlern oder 
grammatikalischen Schwächen sogar für eine "Schlechtigkeit", zeigt es 
doch meistens (nicht immer) auf, dass sich jemand nur aufgrund der 
Deutschfähigkeiten über jemand anderen stellen mag.

Lustig darauf hinweisen geht, aber "Erst mal ein bischen Grammatik 
lernen?!!" ist schon der Oberlehrerzeigefinger

Yalu X. schrieb:
> Streng genommen ist das kein anderer Algorithmus, sondern nur eine
> andere (rekursionsfreie) Implementierung des von dir bereits verwendeten
> Algorithmus.
>
> Er arbeitet mit einem Daten-Stack für die noch zu bearbeitenden Felder.
> Die Rekursion wird dadurch eliminiert, dass
>
> - die rekursiven Funktionsaufrufe mit den Feldern als Argument durch
>   Pushes der Felder auf den Stack ersetzt werden,
>
> - das jeweils als nächstes zu bearbeitende Feld nicht als
>   Funktionsargument empfangen, sondern vom Stack gepoppt wird und
>
> - das Ganze in eine Schleife eingebettet wird, die so lange iteriert,
>   bis der Stack leer ist, d.h. keine weiteren Felder mehr bearbeitet
>   werden müssen.

Weil mich das ganze auch im Krankenhaus nicht in Ruhe lässt, hat mir 
meine Frau ihr (Windows) Notebook mitgebracht und ich habe mir hier dann 
kurzerhand in einer Virtualbox mein Linux-Livesystem installiert und mir 
von meinem Server die Dateien des Minesweeper gezogen, :-) nur um Yalu's 
Verbesserungen auszuprobieren.

Jetzt bin ich am Spielen und wie es ausschaut funktioniert das ganze. 
Herzlichen Dank. Schade, dass ich meinen Mikrocontrollerboards nicht 
hier habe. Theoretisch müßte das jetzt auch auf einem CH32V003 laufen.

[Rolf (rolf22)]

Sigi S. schrieb:
> Erst mal ein bischen Grammatik lernen?!!

Lern du erst mal, weniger als zwei Rechtschreibfehler pro Satz zu 
machen!

[Walter T. (nicolas)]

Ralph S. schrieb:
> Jetzt bin ich am Spielen und wie es ausschaut funktioniert das ganze.

Sehr schön!

Gute Besserung!

[Yalu X. (yalu) (Moderator)]

Michael B. schrieb:
> Yalu X. schrieb:
>> Streng genommen ist das kein anderer Algorithmus, sondern nur eine
>> andere (rekursionsfreie) Implementierung des von dir bereits verwendeten
>> Algorithmus
>
> Eben, daher Unsinn.

Kein Unsinn, sondern Lösung des vorliegenden Problems.

Das Problem:

Ralph S. schrieb:
> Für ein 18x18 großes Feld benötigt mein Programm für die ungünstigste
> Konstellation (getestet mit nur einer einzigen eingetragenen Miene)
> einen Controller mit mindestens 7 kbyte Ram um das gesamte Feld
> auszufüllen. Hat der Controller weniger Ram, kommt es logischerweise
> zu einem Stack-Overflow.

Die Verwendung eines reinen Datenstacks ohne Rekursion spart fast 90%
des RAM-Bedarfs. Dabei bleibt die Laufzeitkomplexität unverändert O(n)
(n ist die Anzahl der Felder), und die Laufzeit selber ist sogar
deutlich kürzer, da der Overhead für die Funktionsaufrufe wegfällt.

Bei nur 16×16 Feldern läuft natürlich auch eine Hauruckmehtode mit O(n²)
(wie sie dir vermutlich vorschwebt) ausreichend schnell. Dass Ralph das
Spiel aber auf einem Mikrocontroller implementiert, legt die Vermutung
nahe, dass er daraus irgendwann ein batteriebetriebenes Gimmick für
unterwegs machen will, und für die Batterielaufzeit spielen die
verbrauchten Taktzyklen eine wesentliche Rolle.

Natürlich kann man die Sache sowohl bzgl. der Geschwindigkeit als auch
des Speicherbedarfs weiter optimieren. Der Hinweis auf mögliche Ansätze
wurde ja bereits gegeben:

Daniel A. schrieb:
> Der Englische Wikipedia Artikel hat da mehr Algorithmen als der
> Deutsche: https://en.wikipedia.org/wiki/Flood_fill


@Ralph: Auch ich wünsche dir eine schnelle Genesung!