AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren
Zurück Delphi-PRAXiS Sprachen und Entwicklungsumgebungen Object-Pascal / Delphi-Language Delphi Iterativer FloodFill mit einem Stapelspeicher

Iterativer FloodFill mit einem Stapelspeicher

Ein Thema von Kampfheizung · begonnen am 6. Jul 2012 · letzter Beitrag vom 7. Jul 2012
Antwort Antwort
Kampfheizung

Registriert seit: 6. Jul 2012
8 Beiträge
 
#1

Iterativer FloodFill mit einem Stapelspeicher

  Alt 6. Jul 2012, 21:29
Delphi-Version: XE2
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.
  Mit Zitat antworten Zitat
Medium

Registriert seit: 23. Jan 2008
3.686 Beiträge
 
Delphi 2007 Enterprise
 
#2

AW: Iterativer FloodFill mit einem Stapelspeicher

  Alt 7. Jul 2012, 00:55
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.
"When one person suffers from a delusion, it is called insanity. When a million people suffer from a delusion, it is called religion." (Richard Dawkins)
  Mit Zitat antworten Zitat
Furtbichler
(Gast)

n/a Beiträge
 
#3

AW: Iterativer FloodFill mit einem Stapelspeicher

  Alt 7. Jul 2012, 08:33
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
  Mit Zitat antworten Zitat
Kampfheizung

Registriert seit: 6. Jul 2012
8 Beiträge
 
#4

AW: Iterativer FloodFill mit einem Stapelspeicher

  Alt 7. Jul 2012, 14:51
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.
  Mit Zitat antworten Zitat
Furtbichler
(Gast)

n/a Beiträge
 
#5

AW: Iterativer FloodFill mit einem Stapelspeicher

  Alt 7. Jul 2012, 18:21
Nö,
Code:
wenn pixel[x,y]<>Zielfarbe then einfärben
  Mit Zitat antworten Zitat
Themen-Optionen Thema durchsuchen
Thema durchsuchen:

Erweiterte Suche
Ansicht

Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 06:42 Uhr.
Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz