Czy istnieje algorytm do wykrywania „lądu stałego” na mapie 2D?

Na tej mapie „stały ląd” to cały ląd, który można połączyć ze środkiem mapy w czterech głównych kierunkach (północ, południe, wschód, zachód - nie po przekątnej).

Chciałbym wykryć kontynent i wypełnić w nim dziury. Myślałem o trzech rzeczach:

1. Szukaj w każdej komórce innej niż woda (ciemne komórki), jeśli można ją połączyć ze środkiem mapy za pomocą algorytmu znajdowania ścieżki. Za drogie! Ale to może zadziałać na wyspach.

2. Kontynent jest wypełniony wiadrem zielonej farby. Każda dziura jest otoczona farbą ... co teraz? Jeśli sprawdzę sąsiedztwo każdego punktu wody na kontynencie, usunę niektóre półwyspy i inne elementy geograficzne wyświetlane na linii brzegowej.

3. Jakiś rodzaj wykrycia krawędzi, aby dowiedzieć się o kontynencie. Trzymaj wszystko, co jest w środku, napełnij je wodą, usuń to, co jest na zewnątrz. Złożony?

Być może jakiś doświadczony programista może mi w tym pomóc, podając nazwę znanego algorytmu lub techniki?

Usuwanie wysp

Robiłem takie rzeczy wcześniej w jednej z moich gier. Aby pozbyć się zewnętrznych wysp, proces polegał zasadniczo na:

1. Po pierwsze musi istnieć gwarancja, że ​​środek mapy zawsze będzie należeć do głównego lądu, a każdy piksel zaczyna się albo jako „Kraina”, albo „Woda” (tj. Różne kolory).
2. Następnie wykonaj czterokierunkowe wypełnienie powodziowe, zaczynając od środka mapy i rozlewając się po dowolnych kafelkach „Lądu”. Oznacz każdy piksel odwiedzany przez to wypełnienie zalewowe jako inny typ, np. „MainLand”.
3. Na koniec przejrzyj całą mapę i przekonwertuj pozostały piksel „Lądowy” na „Woda, aby pozbyć się innych wysp.

Usuwanie jezior

Jeśli chodzi o pozbycie się dziur (lub jezior) na wyspie, wykonujesz podobny proces, ale zaczynasz od narożników mapy i zamiast tego rozprzestrzeniasz się przez kafelki „Wody”. Pozwoli ci to odróżnić „Morze” od innych kafelków wody, a następnie możesz się ich pozbyć, tak jak wcześniej wysp.

Przykład

Pozwól mi wykopać moją implementację wypełnienia zalewowego, które gdzieś tu mam (zrzeczenie się odpowiedzialności, nie dbałem o wydajność, więc jestem pewien, że istnieje wiele bardziej wydajnych sposobów na jej wdrożenie):

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);
}

Wykorzystałem to jako pierwszy krok do pozbycia się jezior w mojej grze. Po nazwaniu tego, wszystko co musiałem zrobić, to:

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;
}

Edytować

Dodanie dodatkowych informacji na podstawie komentarzy. W przypadku zbyt dużej przestrzeni wyszukiwania może wystąpić przepełnienie stosu podczas korzystania z rekurencyjnej wersji algorytmu. Oto link na stackoverflow (zamierzone słowo :-)) do nierekurencyjnej wersji algorytmu, używając Stack<T>zamiast tego (również w języku C #, aby dopasować moją odpowiedź, ale powinna być łatwa do dostosowania do innych języków, a istnieją inne implementacje na ten temat link też).

Zmodyfikuj cztero-kierunkowy algorytm wypełniania zalania http://en.wikipedia.org/wiki/Flood_fill

Jest to standardowa operacja przetwarzania obrazu. Używasz operacji dwufazowej.

Zacznij od utworzenia kopii mapy. Z tej mapy zamień w piksele morskie wszystkie piksele lądowe, które graniczą z morzem. Jeśli zrobisz to raz, wyeliminuje 2x2 wyspy i zmniejszy większe wyspy. Jeśli zrobisz to dwa razy, wyeliminuje wyspy 4x4 itp.

W fazie drugiej robisz prawie odwrotnie: zamieniaj w piksele lądowe wszystkie piksele morskie, które graniczą z lądem, ale tylko wtedy, gdy były pikselami lądowymi na oryginalnej mapie (dlatego wykonałeś kopię w fazie 1). Spowoduje to przywrócenie wysp do ich pierwotnej postaci, chyba że zostaną całkowicie wyeliminowane w fazie 1.

Miałem podobny problem, ale nie w rozwoju gier. Musiałem znaleźć piksele na obrazie, które sąsiadowały ze sobą i miały tę samą wartość (połączone regiony). Próbowałem użyć rekurencyjnego wypełniania, ale ciągle powodowałem przepełnienie stosu (jestem początkującym programistą: P). Następnie wypróbowałem tę metodę http://en.wikipedia.org/wiki/Connected-component_labeling , w rzeczywistości była o wiele bardziej wydajna, jak na mój problem.