Flood Fill

Statement zur DSGVO im Forum

Alles zur DSGVO und zur Umsetzung im Forum hier: Statement zur DSGVO (letztes Update: 30.05.2018)
  • Da ist in der Tat böses im Busch. Ein Kamm in Y Richtung ist für die Scanline Methode außerdem der Laufzeit Worst Case :D

  • wzbw...höhö, **huuuusssttt**8o


    Ich bin jetzt kurz vorm ASM, soweit haste mich schon =O

    Vorerst aber nur eine "reale" Bitmap, mit bissl Takte zählen komme ich auf eine Laufzeit für ein FloodFill mit meiner Methode für eine Bitmap von 800x800 Pixeln von ca 0,2Sekunden. (plusminus eine Zehnerpotenz :o) )

    Annahme dabei der "worst case" mit cachemisses bei jedem Speicherzugriff :party:

    Du kannst ja mal deine Methode für die "reale Bitmap" umbauen, sollte ja nur die entsprechende READ/WRITE-Funktion für das Pixel sein


    Fast Flood Fill 800x800 reale Bitmap2.au3

  • Ich glaube ich bin hier Opfer eines XY Problems geworden und mit meinem Tunnelblick habe ich es selbst nicht bemerkt.

    Ich will X, suche Y, bekomme irgendwas zwischen Y und Z mit einer Prise X und frage mich was X eigentlich war :D


    -> +


    X: (Das habe ich gesucht)

    Ein mit einer ein Pixel breiten schwarzen (0xFF000000) Linie begrenztes Gebiet identifizieren/kopieren/schwerpunkt.

    - identifizieren: Im Anhangbild sind 2 gebiete. Es sollen beide getrennt wahrgenommen werden. (daher kein FloodFill durch diagonalen)

    - kopieren: Es soll eine Bitmap die genau Breite und Höhe des Gebiets hat geben die eine Kopie des Gebiets enthält. Da man vorher nicht weiß wie groß das Gebiet ist kann man zuerst eine zu große Bitmap (Gebietgröße ist immer kleiner als irgendeine Vorgabe z.B. 256px) erstellen, kopieren und nachher die Ränder abschneiden/extrahieren/etc.

    - schwerpunkt: Einfach der Mittelwert aller Positionen aller Pixel des Gebiets.


    Y: (Danach habe ich gefragt)

    FloodFill mit zugänglicher R/W Funktion. Mein bisheriges Programm verwendet FloodFill und vergleicht Werte wie xMin und xMax und y mit einem übergeordneten x, y, w, h für das Gebiet um herauszufinden wie groß das Gebiet ist. Gleichzeitig kann man mit der Write Funktion die einzelnen Pixel in eine 2te Bitmap kopieren, aus der man dann, mit den ermittelten Werten zur Gebietsgröße (und mit dem Startwert wo FloodFill angesetzt wurde) das Gebiet direkt extrahieren (DrawRectRect) kann. Da man ggf. hunderte oder "viele große" Gebiete hat muss die Funktion möglichst schnell sein.


    Z: (Das wurde entwickelt)

    Schnelle FloodFill Methoden die in ASM wahrscheinlich überragend schnell sind und schnelle FloodFill Methoden die in AutoIt sehr schnell (die schnellste ist fehlerhaft) sind.


    Alternative/Erweiterung zu X: (das wurde noch garnicht erwähnt)

    Sinnvoller ist eigentlich sogar eine Vektorisierung des Gebiets, da man dann transformationen wie z.B. Breite * 1.5 oder Rotation um 15° fehlerfrei durchführen kann, während man für Pixelgebilde immer anschließend auf Artefaktbeseitigungstour gehen muss. Da hatte ich geplant, diese anschließend aus den einzelnen Bitmaps mit den einzelnen Gebieten anzufertigen (Rand ablaufen und überall Punkte setzen, sodass man später mit Draw/Fill Polygon das Gebiet EXAKT (nur das Gebiet, nicht der Rand, den braucht niemand) rekonstruieren kann, hier darf es zumindest ohne Transformation keinen einzigen Pixel Abweichung geben).


    Das Problem wollte ich möglichst klein halten und habe mich daher auf die FloodFill Komponente beschränkt, aber bevor Andy jetzt ambitioniert eine Lösung für Y findet will ich ihn bremsen. Die Verwirrung war mein Fehler, entschuldigt bitte...


    Falls sich jemand fragt für was man so einen Unfug braucht: Googelt mal das DOS Spiel Conquest. Der Hersteller davon hat vor 10+ Jahren eine Windows Version geschrieben die unvorstellbarer Schrott ist, das kann ich mit Sicherheit wesentlich besser. Dafür will ich auf einen Mapeditor verzichten, eine Map wird mit Paint gemalt und vom Programm analysiert, sodass JEDER eine Map machen kann ohne von irgendwas irgendeine Ahnung zu haben.



    (Beispiel der Standardmap aus dem Originalspiel. Statt einen Mapeditor zu verwenden kann man diese Karte auch mit Paint malen, sofern man sich ein ein paar Farbvorgaben hält (z.B. Gebietbonus hat gleiche Farbe wie zugehöriges Gebiet, Hintergrund hat dieses seltsame Blau, Verbindungslinien sind Weiß, usw usw.).



    lg

    M