Gibt es einen Algorithmus, um das „Festland“ auf einer 2D-Karte zu erkennen?

28

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. Bildbeschreibung hier eingeben

Ich möchte das Festland erkennen und die Löcher darin füllen. Ich dachte an drei Dinge:

  1. 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.

  2. 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.

  3. 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?

Gabriel A. Zorrilla
quelle
4
Ich frage mich nur, ob Sie einen Algorithmus verwendet haben, um diese Karte zu erstellen. Und wenn ja, was hast du benutzt?
Jgallant
Bei der Arbeit in fliesenbasierten Umgebungen lohnt es sich, den Marching Squares-Algorithmus zu untersuchen . Damit können Sie auch die kleineren Inseln erkennen und behalten und dann nach Größe sortieren, indem Sie einzelne Zelleninseln oder andere Kriterien verwerfen.
William Mariager
@ Jon ja! Diamantquadrat-Algorithmus, um eine Höhenkarte zu generieren, dann ist alles unter einem Wert Wasser, der Rest Land. Ich plane, dies als Kontinentform zu verwenden und dann einen weiteren Durchgang, um Geländedetails hinzuzufügen.
Gabriel A. Zorrilla
@ Mind Marching Squares Algorithmus wird nützlich sein, um die Kontinentgrenze zu malen. Danke netter Vorschlag!
Gabriel A. Zorrilla

Antworten:

32

Inseln entfernen

Ich habe so etwas schon in einem meiner Spiele gemacht. Um die äußeren Inseln loszuwerden, war der Prozess im Grunde:

  1. Zunächst muss gewährleistet sein, dass das Zentrum der Karte immer zum Hauptland gehört und jedes Pixel entweder als "Land" oder "Wasser" (dh in verschiedenen Farben) beginnt.
  2. Dann fülle die Karte von der Mitte aus in vier Richtungen und verteile sie auf allen "Land" -Kacheln. Markieren Sie jedes Pixel, das von dieser Überflutungsfüllung besucht wird, als einen anderen Typ, z. B. "MainLand".
  3. Gehen Sie schließlich über die gesamte Karte und konvertieren Sie alle verbleibenden "Land" -Pixel in "Wasser", um andere Inseln zu entfernen.

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):

private void GenerateSea()
{
    // Initialize visited tiles list
    visited.Clear();

    // Start generating sea from the four corners
    GenerateSeaRecursive(new Point(0, 0));
    GenerateSeaRecursive(new Point(size.Width - 1, 0));
    GenerateSeaRecursive(new Point(0, size.Height - 1));
    GenerateSeaRecursive(new Point(size.Width - 1, size.Height - 1));
}

private void GenerateSeaRecursive(Point point)
{
    // End recursion if point is outside bounds
    if (!WithinBounds(point)) return;

    // End recursion if the current spot is a land
    if (tiles[point.X, point.Y].Land) return;

    // End recursion if this spot has already been visited
    if (visited.Contains(point)) return;

    // Add point to visited points list
    visited.Add(point);

    // Calculate neighboring tiles coordinates
    Point right = new Point(point.X + 1, point.Y);
    Point left = new Point(point.X - 1, point.Y);
    Point up = new Point(point.X, point.Y - 1);
    Point down = new Point(point.X, point.Y + 1);

    // Mark neighbouring tiles as Sea if they're not Land
    if (WithinBounds(right) && tiles[right.X, right.Y].Empty)
        tiles[right.X, right.Y].Sea = true;
    if (WithinBounds(left) && tiles[left.X, left.Y].Empty)
        tiles[left.X, left.Y].Sea = true;
    if (WithinBounds(up) && tiles[up.X, up.Y].Empty)
        tiles[up.X, up.Y].Sea = true;
    if (WithinBounds(down) && tiles[down.X, down.Y].Empty)
        tiles[down.X, down.Y].Sea = true;

    // Call the function recursively for the neighboring tiles
    GenerateSeaRecursive(right);
    GenerateSeaRecursive(left);
    GenerateSeaRecursive(up);
    GenerateSeaRecursive(down);
}

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:

private void RemoveLakes()
{
    // Now that sea is generated, any empty tile should be removed
    for (int j = 0; j != size.Height; j++)
        for (int i = 0; i != size.Width; i++)
            if (tiles[i, j].Empty) tiles[i, j].Land = true;
}

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).

David Gouveia
quelle
11
Wenn Sie nicht garantieren können, dass das mittlere Feld immer Land und Teil des Festlandes ist, markieren Sie jedes Feld mit einer Überflutung als zu einer bestimmten Insel gehörig das gleiche Blobid, wenn es noch keines gibt). Dann entfernen Sie alle bis auf den Klecks mit den meisten Kacheln.
George Duckett
In Anlehnung an die Aussage von George Duckett können Sie auch die Algorithmen zur Erkennung von Googling-Blobs ausprobieren: Dies ist ein häufiges Problem bei der Verwendung von FTIR mit mehreren Berührungen. Ich erinnere mich, dass ich einen intelligenteren Algorithmus entwickelt habe, aber ich kann mich nicht erinnern, wie er funktioniert hat.
Jonathan Dickinson
Da ich Stapelprobleme in PHP hatte, implementierte ich die LIFO-Flood-Füllung, die wunderbar funktionierte.
Gabriel A. Zorrilla
Handelt es sich nicht nur um eine Überflutungsfüllung, wenn ein DFS-Algorithmus von einem BFS-Algorithmus aufgerufen wird? Bitte erkläre es jemandem.
Jcora
@Bane Was meinst du? Der Unterschied zwischen DFS oder BFS besteht lediglich in der Reihenfolge, in der die Knoten besucht werden. Ich glaube nicht, dass der Flood-Fill-Algorithmus die Reihenfolge der Durchquerung angibt - es ist egal, solange er die gesamte Region ausfüllt, ohne die Knoten erneut aufzurufen. Die Reihenfolge hängt von der Implementierung ab. Im unteren Teil des Wikipedia-Eintrags finden Sie ein Bild, in dem die Reihenfolge der Durchquerung bei Verwendung einer Warteschlange mit der eines Stapels verglichen wird. Die rekursive Implementierung kann auch als Stapel betrachtet werden (da sie den Aufrufstapel verwendet).
David Gouveia
5

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.

MSalters
quelle
1

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.

Elegant_Cow
quelle
Sie sollten die Stapelversion des Flood Algo ausprobiert und die Stapelprobleme gespeichert haben. Das Ergebnis war viel einfacher als CCL (an dem ich in den letzten 2 Wochen ohne Glück gearbeitet habe.)
Gabriel A. Zorrilla
Ja, ich habe beide ausprobiert, aber ich habe die CCL zuerst zum Laufen gebracht: P und dachte, es sei eine gute Idee.
Ich bin