Ich habe ein Problem in meinem Go-Game-Projekt.
Ich habe ein Board (Goban), dargestellt durch 2D Array von Zeichen. Vor jedem nächsten Zug möchte ich nach "Blasen" im Array suchen. Bubble sollte ein 4-zusammenhängender Bereich identischer Zeichen sein, der in 4 Richtungen von einer anderen Gruppe spezifischer identischer Zeichen umgeben ist. Wenn diese "Blase" existiert, sollten die Charaktere im Inneren durch andere ersetzt werden. Aber es könnte mehr Gebiete geben und nicht alle sind eingeschlossen. Zum Beispiel habe ich dieses Board:
%Vor%Und ich würde gerne die Blase von Xs finden, sie zählen und sie durch 'Z's ersetzen.
Ich habe es gegoogelt und ich denke, dass einige Connected-Komponenten-Beschriftungsalgorithmen oder FloodFill die Arbeit erledigen können, aber ich bin mir nicht sicher, wie ich es implementieren soll. Ist das der Weg oder etwas weniger Kompliziertes könnte es lösen? Danke
Bearbeiten: Ich habe versucht, ein Muster zu finden, das die Bereiche mit spezifischem Charakter finden und ihre Freiheiten zählen kann, aber es scheiterte immer, wenn der Ort vielschichtig war. Ändern der Datenstruktur könnte die Lösung sein, aber wenn es möglich ist, möchte ich es so machen, wie es jetzt ist.
Meine aktuelle Lösungsidee:
%Vor%Sie können das mit einer rekursiven Methode tun, in der Tat mit der FloodFill Theorie.
Im Grunde gehen Sie durch Ihr Gitter und jedes Mal, wenn Sie ein X finden, ersetzen Sie es durch ein Z, sowie seine 4 Nachbarn (falls zutreffend). Aber der Trick ist: Anstatt sie nur zu ersetzen und jedes Mal neu zu durchlaufen, rufen Sie erneut die gleiche (Aufruf-) Methode auf, um das zu tun. Die Rekursivität wird den Rest erledigen.
Hier ist eine Pseudo-Code-Version (schnell gemacht): (Angenommen, Ihr Gitter ist von 0 bis xmax, von 0 bis ymax indiziert)
%Vor%Soweit ich weiß, ist dies die einzige Lösung für dieses Problem, die funktioniert, egal wie komisch Ihre Blase ist. Die Komplexität ist auch nicht schlecht.
Dies kann weiter optimiert werden, da es derzeit nach Zeichen sucht, die offensichtlich kein X mehr enthalten (weil sie gerade durch Z ersetzt wurden). Dies ist eine Übung für den Leser:)
(NB: Das minesweeper Spiel basiert unter anderem auf dieser Lösung)
Hier ist ein Algorithmus (in Pseudocode), den ich für ähnliche Bildanalyse Bedürfnisse verwendet habe:
%Vor%Im Grunde behalten Sie eine Sammlung von Punktmengen bei, wobei jede Menge eine "Blase" zusammenhängender Punkte auf der Tafel darstellt. Scannen Sie jeden Ort auf der Tafel und wenn es ein "X" ist und es nicht bereits in einer Region ist, dann erstellen Sie eine neue Region und einen Stapel mit dem Ort und besuchen Sie die Nachbarn, die nach nicht besuchten "X" suchen , sie zur neuen Region hinzufügen und als entdeckt stapeln.
Am Ende haben Sie eine Sammlung von Punktmengen, die jeweils eine "Blase" darstellen.