Iterativer FloodFill mit einem Stapelspeicher

[Kampfheizung]

Moin Moin,

ich bin dabei das Spiel Qix zu programmieren und unser Dozent
hat vorgeschlagen das wir wenn wir das Feld verkleinern mit unserem
Spieler die gezeichnete Fläche iterativ mit einem Stack zu füllen.

Nun meine Frage :

Wie FloodFill rekursiv funktioniert weiß ich -
aber ich habe kein logisches Beispiel oder Erklärung dafür gefunden
wie ich mit einem Stack und iterativ meine gezeichnete Fläche füllen soll.

Wenn jemand die Güte hätte und auch die Zeit mir da ein
kleinen Stupps zu geben wäre ich echt glücklich.



PS : Nebenfrage - wie kann ich ein array of Record die Inhalte löschen und setlength(bla, 0) machen
zurzeit meckert er - wenn ich auf 'Neues Spiel' gehe und ganz einfach setlength(bla, 0) machen möchte.


Mit freundlichen Grüßen
Marcel.

[Medium]

Mit Stack ist hier, nehme ich an, die Datenstruktur gemeint, nicht der tatsächlich so genannte Speicherbereich (der bei der Rekursion eine tragende Rolle spielt). Grundsätzlich ist jede Rekursion in eine Iteration auflösbar, wobei manche Lösungen erfordern, dass man manuell eine Art "Ersatz-Stack" führt (, was bei der Rekursion der Compiler übernimmt, jedoch in der Regel weniger effizient bzw. mit anderen Mitteln). Um an dieser Stelle konkret helfen zu können, wäre es sehr hilfreich zu wissen, wie du es rekursiv umsetzen würdest - also als tatsächlicher Code, wie du ihn in deinem Programm schreiben würdest.
Allgemein könnte man ggf. sagen: Alles, was du bei einer Rekursion als Parameter an den nächsten Aufruf übergeben würdest, muss meistens (nicht immer) irgendwie zwischengespeichert werden. Ein Mal pro Schleifendurchlauf, und nachher wieder zurück. Das ist LiFo -> also Stack, aka Push&Pop. Nur ohne konkreten Code als Basis ist das schwer zu erklären :)

@PS: "Meckert" ist erheblich zu vage. Auch hier: Zeig mal Code, und die genaue Fehlermeldung.

PS: Es ist immer sehr ratsam gleich mit Code und Strg-C der Fehlermeldungen hier aufzuschlagen. Aus Prosa lässt sich in der Regel kaum verwertbare Info ziehen.

[Furtbichler]

Floodfill geht doch so (peudocode):

Delphi-Quellcode:

Procedure FloodFill (Canvas : TCanvas; P : TPoint; NewColor : TColor);
Var
 q : TPoint;

begin
  Foreach Neighpor q of P do 
    if not visited[q] then begin
      visited[q] := True;
      Canvas.Pixel[q.x, q.y] := NewColor;
      FloodFill(Canvas, q, NewColor);
    end
end

Eine iterative Umformung ginge so:

Delphi-Quellcode:

Procedure FloodFill (Canvas : TCanvas; P : TPoint; NewColor : TColor);
Var
  worktable: Stack of TPoint;
  Q : TPoint;

begin
  worktable.push(p):
  while not worktable.IsEmpty do begin
    q := worktable.pop;
    if not visited[q] then begin
      visited[q] := True;
      Canvas.Pixel[q.x, q.y] := NewColor;
      worktable.push(q);
    end
  end
end

[Kampfheizung]

Erst einmal zur "Nebenfrage" :

Delphi-Quellcode:

type
  Lines = record
   start : TPoint;
   ende : TPoint;
  end;
var Lines_points : array of Lines;

Wie bekomme ich wenn ich gespielt habe und dort verschieden viele Sätze an Daten drinne stehen
die wieder aus 'Lines_points' gelöscht so das die Länge wieder 0 ist. Weil ich kann ja mitten
im Spiel "Neues Spiel" drücken und da muss ja wieder alles auf den Anfang zurück gesetzt werden
so ja auch die Linien und die muss ich da ausm Speicher rausbekommen.


Dann zur Hauptfrage :

Ich habe mir jetzt eine Datenstruktur gebastelt in einer seperaten Unit und die Iterative Lösung
die vorgeschlagen wurde bereichert mich auch schon ein bisschen, jedenfalls sehe ich schon ein
bisschen klarer.

Aber ich weiß noch nicht so ganz wie ich nun da ran gehen soll weil -

Ich möchte ja in einer Paintbox ein Strich zb. von links nach Rechts durchziehen
und dann in der Paintbox die kleinere Hälfte die getrennt wird durch den Strich
in einer bestimmten Farbe färben die ich festgelegt habe. Das wäre ja noch das einfachste Beispiel
weil es hat nur ein Start und ein Endpunkt - aber der Spieler kann auch eine Pyramide zeichnen
mit beliebig vielen Ecken und dann sie am Rand schließen und das muss dann auch eingezeichnet werden
da würde ich gerade mit meiner Logik irgendwie auf Granit stoßen.

Rekursiv könnte man ja einfach die Kollisions-Farbe angeben - iterativ ist das ja ein bisschen
ausführlicher.

[Furtbichler]

Nö,

Code:

wenn pixel[x,y]<>Zielfarbe then einfärben