Auf dieser Karte ist das "Festland" das gesamte Land, das in den vier Hauptrichtungen (Norden, Süden, Osten, Westen - nicht diagonal) mit dem Zentrum der Karte verbunden werden kann.
Ich möchte das Festland erkennen und die Löcher darin füllen. Ich dachte an drei Dinge:
Suchen Sie in jeder Zelle, die kein Wasser ist (dunkle Zellen), wenn Sie mithilfe eines Pfadsuchalgorithmus eine Verbindung zur Kartenmitte herstellen können. Zu teuer! Aber das könnte für die Inseln funktionieren.
Das Festland ist mit einem Eimer grüner Farbe gefüllt. Jedes Loch ist von Farbe umgeben ... was nun? Wenn ich jeden Wasserpunkt auf dem Festland auf Angrenzung überprüfe, lösche ich einige Halbinseln und andere geografische Merkmale, die an der Küste angezeigt werden.
Eine Art Kantenerkennung, um das Festland zu erkennen. Behalten Sie, was drinnen ist, füllen Sie es auf, wenn es Wasser ist, und entfernen Sie das, was draußen ist. Komplex?
Vielleicht kann mir ein spielerfahrener Entwickler dabei helfen und mir möglicherweise den Namen eines bekannten Algorithmus oder einer bekannten Technik geben?
Antworten:
Inseln entfernen
Ich habe so etwas schon in einem meiner Spiele gemacht. Um die äußeren Inseln loszuwerden, war der Prozess im Grunde:
Seen entfernen
Um die Löcher (oder Seen) auf der Insel zu beseitigen, gehen Sie ähnlich vor, beginnen jedoch an den Ecken der Karte und breiten sich stattdessen über die "Wasser" -Kacheln aus. Auf diese Weise können Sie das "Meer" von den anderen Wasserplättchen unterscheiden und Sie können sie dann genauso entfernen, wie Sie die Inseln zuvor beseitigt haben.
Beispiel
Lassen Sie mich meine Umsetzung der Flußfüllen ausgraben , dass ich hier irgendwo (Disclaimer, scherte ich nicht um Effizienz, also bin ich sicher , es gibt viele effizientere Wege zu ihrer Umsetzung):
Ich habe dies als ersten Schritt benutzt, um die Seen in meinem Spiel loszuwerden. Nachdem ich das angerufen hatte, musste ich nur noch Folgendes tun:
Bearbeiten
Hinzufügen einiger zusätzlicher Informationen basierend auf den Kommentaren. Falls Ihr Suchraum zu groß ist, kann es bei Verwendung der rekursiven Version des Algorithmus zu einem Stapelüberlauf kommen. Hier ist ein Link zum Stackoverflow (Wortspiel beabsichtigt :-)) zu einer nicht rekursiven Version des Algorithmus. Verwenden Sie
Stack<T>
stattdessen einen (auch in C #, um meiner Antwort zu entsprechen), der sich leicht an andere Sprachen anpassen lässt, und es gibt andere Implementierungen dazu Link auch).quelle
Ändern Sie den Flood-Fill-Algorithmus in vier Richtungen ( http://en.wikipedia.org/wiki/Flood_fill)
quelle
Dies ist eine Standardoperation in der Bildverarbeitung. Sie verwenden einen Zweiphasenbetrieb.
Erstellen Sie zunächst eine Kopie der Karte. Verwandle auf dieser Karte alle Landpixel, die an das Meer grenzen, in Seepixel. Wenn Sie dies einmal tun, werden 2x2 Inseln entfernt und größere Inseln verkleinert. Wenn Sie es zweimal tun, werden 4x4-Inseln usw. beseitigt.
In Phase zwei machen Sie fast das Gegenteil: Verwandeln Sie alle Seepixel, die das Land begrenzen, in Landpixel, aber nur dann, wenn es sich um Landpixel auf der ursprünglichen Karte handelt (aus diesem Grund haben Sie in Phase 1 eine Kopie erstellt). Dadurch werden die Inseln wieder in ihre ursprüngliche Form zurückversetzt, es sei denn, sie wurden in Phase 1 vollständig beseitigt.
quelle
Ich hatte ein ähnliches Problem, aber nicht in der Spieleentwicklung. Ich musste Pixel in einem Bild finden, die nebeneinander lagen und denselben Wert hatten (verbundene Bereiche). Ich habe versucht, ein rekursives Floodfill zu verwenden, verursachte aber weiterhin Stapelüberläufe (ich bin ein Anfänger in der Programmierung: P). Dann habe ich diese Methode ausprobiert http://en.wikipedia.org/wiki/Connected-component_labeling es war eigentlich viel effizienter, für mein Problem sowieso.
quelle