Usuwanie wysp
Robiłem takie rzeczy wcześniej w jednej z moich gier. Aby pozbyć się zewnętrznych wysp, proces polegał zasadniczo na:
- 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).
- 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”.
- 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ż).