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


28

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). wprowadź opis zdjęcia tutaj

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?


4
Zastanawiam się tylko, czy użyłeś jakiegoś algorytmu do wygenerowania tej mapy. A jeśli tak, to czego użyłeś?
jgallant

Podczas pracy w środowisku opartym na kafelkach warto przyjrzeć się algorytmowi Marching Squares . Dzięki niemu możesz wykryć i zatrzymać mniejsze wyspy, a następnie sortować według wielkości, odrzucając wyspy jednokomórkowe lub według dowolnych kryteriów.
William Mariager,

@Jon tak! algorytm kwadratu diamentowego do generowania mapy wysokości, a następnie wszystkie poniżej jednej wartości to woda, reszta, ląd. Planuję użyć tego jako kształtu kontynentu, a następnie kolejnego przejścia, aby dodać szczegóły terenu.
Gabriel A. Zorrilla,

@Mind Marching Squares Algorytm przyda się do pomalowania granicy kontynentu. Dzięki miła sugestia!
Gabriel A. Zorrilla

Odpowiedzi:


32

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


11
Jeśli nie możesz zagwarantować, że środkowy kafelek zawsze będzie lądem i częścią kontynentu, użyj wypełnienia zalewowego, aby oznaczyć każdy kafelek ziemi jako należący do konkretnej wyspy (wypełnienie zalewowe z każdego kafelka bez identyfikatora kropli na mapie, oznaczając wypełnione kafelki ten sam blobid, jeśli jeszcze go nie ma). Następnie usuń wszystkie oprócz kropli z największą liczbą płytek.
George Duckett,

Zgodnie z tym, co powiedział GeorgeDuckett - możesz wypróbować algorytmy wykrywania kropelek Googlinga: jest to powszechny problem w trybie wielodotykowym za pomocą FTIR. Pamiętam, że wymyśliłem mądrzejszy algorytm, ale nie pamiętam przez całe życie, jak to działało.
Jonathan Dickinson

Ponieważ miałem problemy ze stosami w PHP, zaimplementowałem wypełnienie zalewowe LIFO, zadziałało cudownie.
Gabriel A. Zorrilla

Czy to nie jest wypełnienie zalewowe tylko wtedy, gdy algorytm DFS jest wywoływany z algorytmu BFS? Proszę wytłumacz komuś.
jcora

@Bane Co masz na myśli? Różnica między DFS lub BFS polega tylko na kolejności odwiedzania węzłów. Nie sądzę, że algorytm wypełniania zalewowego określa kolejność przechodzenia - nie ma znaczenia, dopóki wypełnia cały region bez odwiedzania węzłów. Kolejność zależy od realizacji. Zobacz na dole wpisu na Wikipedii obrazek przedstawiający porównanie kolejności przechodzenia podczas korzystania z kolejki w porównaniu ze stosem. Implementację rekurencyjną można również uznać za stos (ponieważ używa stosu wywołań).
David Gouveia


5

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.


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.


Powinieneś wypróbować wersję algo powodziową i zapisać problemy ze stosem. Rezultat był znacznie prostszy niż CCL (który pracowałem przez ostatnie 2 tygodnie bez powodzenia).
Gabriel A. Zorrilla

Tak, próbowałem obu, ale najpierw uruchomiłem CCL: P i pomyślałem, że to dobry pomysł. Cieszę się, że rozwiązałeś problem :)
Elegant_Cow
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.