Existe um algoritmo para detectar o "continente" em um mapa 2D?

28

Neste mapa, o "continente" é toda a terra que pode ser conectada ao centro do mapa nas quatro direções principais (norte, sul, leste, oeste - não na diagonal). insira a descrição da imagem aqui

Gostaria de detectar o continente e preencher os buracos. Eu pensei em três coisas:

  1. Pesquise em cada célula que não seja água (células escuras) se puder ser conectada ao centro do mapa usando um algoritmo de localização de caminho. Muito caro! Mas isso poderia funcionar para as ilhas.

  2. O continente está cheio de um balde de tinta verde. Cada buraco é cercado por tinta ... e agora? Se eu verificar todos os pontos de água dentro do continente em busca de adjacência, excluirei algumas penínsulas e outras características geográficas exibidas na costa.

  3. Algum tipo de detecção de borda para descobrir o continente. Mantenha o que estiver dentro, encha-o se for água, remova o que está do lado de fora. Complexo?

Talvez algum desenvolvedor com experiência em jogos possa me ajudar com isso, possivelmente me dando o nome de algum algoritmo ou técnica conhecida?

Gabriel A. Zorrilla
fonte
4
Só estou imaginando se você usou algum tipo de algoritmo para gerar esse mapa. E se sim, o que você usou?
jgallant
Vale a pena examinar ao trabalhar em ambientes com base em til é o algoritmo Marching Squares . Com ele, você também pode detectar e manter as ilhas menores e, em seguida, classificar por tamanho, descartando ilhas de célula única ou qualquer critério que possa ter.
William Mariager
@ Jon yes! algoritmo quadrado de diamante para gerar um mapa de altura, então todos abaixo de um valor é água, o resto, terra. Eu pretendo usar isso como forma de continente e depois outro passe para adicionar detalhes do terreno.
Gabriel A. Zorrilla
O algoritmo @Mind Marching Squares será útil para pintar a fronteira do continente. Obrigado boa sugestão!
Gabriel A. Zorrilla

Respostas:

32

Removendo Ilhas

Eu já fiz esse tipo de coisa antes em um dos meus jogos. Para se livrar das ilhas externas, o processo foi basicamente:

  1. Primeiro, deve haver uma garantia de que o centro do mapa sempre pertence à terra principal e cada pixel começa como "Terra" ou "Água" (ou seja, cores diferentes).
  2. Em seguida, faça um preenchimento de quatro direções, começando no centro do mapa e se espalhando por todos os ladrilhos "Terreno". Marque cada pixel visitado por esse preenchimento como um tipo diferente, como "MainLand".
  3. Por fim, percorra o mapa inteiro e converta qualquer pixel "Land" restante em "Water" para se livrar de outras ilhas.

Remoção de lagos

Quanto a se livrar dos buracos (ou lagos) dentro da ilha, você faz um processo semelhante, mas partindo dos cantos do mapa e se espalhando pelos ladrilhos "Água". Isso permitirá que você diferencie o "Mar" dos outros ladrilhos de água, e então você pode se livrar deles da mesma maneira que antes.

Exemplo

Deixe-me desenterrar minha implementação do preenchimento de inundação que tenho aqui em algum lugar (isenção de responsabilidade, não me importei com eficiência, por isso tenho certeza de que existem muitas maneiras mais eficientes de implementá-lo):

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

Eu usei isso como um primeiro passo para me livrar de lagos no meu jogo. Depois de chamar isso, tudo o que eu precisava fazer era algo como:

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

Editar

Adicionando algumas informações extras com base nos comentários. Caso seu espaço de pesquisa seja muito grande, poderá ocorrer um estouro de pilha ao usar a versão recursiva do algoritmo. Aqui está um link no stackoverflow (trocadilho pretendido :-)) para uma versão não recursiva do algoritmo, usando uma Stack<T>alternativa (também em C # para corresponder à minha resposta, mas deve ser fácil de se adaptar a outros idiomas, e há outras implementações nesse link também).

David Gouveia
fonte
11
Se você não pode garantir que o ladrilho central seja sempre terra e parte do continente, use o preenchimento de inundação para marcar cada mosaico como pertencente a uma ilha específica (preenchimento de inundação de cada mosaico sem ID de blob no mapa, marcando os mosaicos preenchidos com o mesmo blobid se ainda não tiver um). Em seguida, remova todos, exceto o blob, com o maior número de peças.
George Duckett
De acordo com o que GeorgeDuckett disse - você pode experimentar os algoritmos de detecção de blobs no Google: é um problema comum no multitoque usando o FTIR. Lembro-me de ter criado um algoritmo mais inteligente, mas não consigo me lembrar por toda a vida como ele funcionou.
Jonathan Dickinson
Como eu tenho problemas com a pilha no PHP, implementei o preenchimento de inundação LIFO, que funcionou maravilhosamente.
Gabriel A. Zorrilla
Não é um preenchimento de inundação apenas quando um algoritmo DFS é chamado de um algoritmo BFS? Por favor, explique alguém.
jcora
@Bane O que você quer dizer? A diferença entre DFS ou BFS é apenas a ordem em que os nós são visitados. Eu não acho que o algoritmo de preenchimento especifique a ordem da travessia - ele não se importa, desde que preencha toda a região sem revisar os nós. A ordem depende da implementação. Veja na parte inferior da entrada da Wikipedia uma imagem comparando a ordem de passagem ao usar uma fila versus usar uma pilha. A implementação recursiva também pode ser considerada uma pilha (já que ela usa a pilha de chamadas).
David Gouveia
5

Esta é uma operação padrão no processamento de imagens. Você usa uma operação de duas fases.

Comece criando uma cópia do mapa. Nesse mapa, transforme em pixels do mar todos os pixels terrestres que fazem fronteira com o mar. Se você fizer isso uma vez, ele eliminará 2x2 ilhas e encolherá ilhas maiores. Se você fizer isso duas vezes, eliminará ilhas 4x4, etc.

Na fase dois, você faz quase o contrário: transforma em pixels da terra todos os pixels do mar que fazem fronteira com a terra, mas apenas se fossem pixels da terra no mapa original (foi por isso que você fez uma cópia na fase 1). Isso recupera as ilhas para sua forma original, a menos que tenham sido totalmente eliminadas na fase 1.

MSalters
fonte
1

Eu tive um problema semelhante, mas não no desenvolvimento de jogos. Eu tive que encontrar pixels em uma imagem adjacentes e com o mesmo valor (regiões conectadas). Tentei usar um preenchimento recursivo, mas continuei causando estouros de pilha (sou um programador iniciante: P). Então tentei este método http://en.wikipedia.org/wiki/Connected-component_labeling , na verdade, era muito mais eficiente, para o meu problema de qualquer maneira.

Elegant_Cow
fonte
Você deveria ter tentado a versão da pilha do algo de flood e salvar os problemas da pilha. Resultou ser muito mais simples do CCL (que eu tenho trabalhado nas últimas 2 semanas sem sorte.)
Gabriel A. Zorrilla
Sim, eu tentei os dois, mas consegui que o CCL funcionasse primeiro: P e achei que era uma boa idéia. Fico feliz que você resolveu seu problema :)
Elegant_Cow