Existe-t-il un algorithme pour détecter le «continent» sur une carte 2D?

28

Sur cette carte, le «continent» est tout le territoire qui peut être connecté au centre de la carte dans les quatre directions cardinales (nord, sud, est, ouest - pas en diagonale). entrez la description de l'image ici

Je voudrais détecter le continent et y combler les trous. J'ai pensé à trois choses:

  1. Recherchez dans chaque cellule autre que l'eau (cellules sombres) si elle peut être connectée au centre de la carte à l'aide d'un algorithme de recherche de chemin. Trop cher! Mais cela pourrait fonctionner pour les îles.

  2. Le continent est rempli d'un seau de peinture verte. Chaque trou est entouré de peinture ... et maintenant? Si je vérifie la contiguïté de chaque point d'eau à l'intérieur du continent, je supprimerai certaines péninsules et autres caractéristiques géographiques affichées sur le rivage.

  3. Une sorte de détection de bord pour comprendre le continent. Gardez tout ce qui est à l'intérieur, remplissez-le si c'est de l'eau, retirez ce qui est à l'extérieur. Complexe?

Peut-être qu'un développeur expérimenté dans le jeu peut m'aider avec cela, en me donnant éventuellement le nom d'un algorithme ou d'une technique connue?

Gabriel A. Zorrilla
la source
4
Je me demande simplement si vous avez utilisé une sorte d'algorithme pour générer cette carte. Et si oui, qu'avez-vous utilisé?
jgallant
L' algorithme Marching Squares mérite d'être étudié lorsque vous travaillez dans des environnements à base de tuiles . Avec lui, vous pouvez également détecter et conserver les plus petites îles, puis trier par taille en éliminant les îles à cellule unique, ou tout autre critère que vous pourriez avoir.
William Mariager
@Jon oui! algorithme de carré de diamant pour générer une carte de hauteur, puis tout ce qui suit est l'eau, le reste, la terre. Je prévois d'utiliser cela comme forme de continent, puis un autre col pour ajouter des détails sur le terrain.
Gabriel A. Zorrilla
@Mind Marching Squares Algorithm sera utile pour peindre la frontière du continent. Merci belle suggestion!
Gabriel A. Zorrilla

Réponses:

32

Suppression d'îles

J'ai déjà fait ce genre de chose dans l'un de mes jeux. Pour se débarrasser des îles extérieures, le processus était essentiellement:

  1. Tout d'abord, il doit y avoir une garantie que le centre de la carte appartiendra toujours à la terre principale, et chaque pixel commence soit par "Terre" ou "Eau" (c'est-à-dire différentes couleurs).
  2. Faites ensuite un remplissage à quatre directions en commençant par le centre de la carte et en vous étalant sur toutes les tuiles "Terre". Marquez chaque pixel visité par ce remplissage comme un type différent tel que "MainLand".
  3. Enfin, parcourez toute la carte et convertissez tout pixel "Terre" restant en "Eau" pour vous débarrasser des autres îles.

Suppression des lacs

Quant à se débarrasser des trous (ou lacs) à l'intérieur de l'île, vous effectuez un processus similaire, mais en partant des coins de la carte et en vous propageant à travers les tuiles "Eau" à la place. Cela vous permettra de distinguer la "mer" des autres tuiles d'eau, et vous pourrez ensuite vous en débarrasser comme vous vous êtes débarrassé des îles auparavant.

Exemple

Permettez-moi de creuser ma mise en œuvre du remblai d'inondation que j'ai ici quelque part (avertissement, je ne me souciais pas de l'efficacité, donc je suis sûr qu'il existe de nombreuses façons plus efficaces de le mettre en œuvre):

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

J'ai utilisé cela comme une première étape pour se débarrasser des lacs dans mon jeu. Après avoir appelé cela, tout ce que j'avais à faire était quelque chose comme:

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

modifier

Ajout d'informations supplémentaires sur la base des commentaires. Dans le cas où votre espace de recherche est trop grand, vous pourriez rencontrer un débordement de pile lors de l'utilisation de la version récursive de l'algorithme. Voici un lien sur stackoverflow (jeu de mots prévu :-)) vers une version non récursive de l'algorithme, en utilisant à la Stack<T>place (également en C # pour correspondre à ma réponse, mais devrait être facile à adapter à d'autres langages, et il existe d'autres implémentations à ce sujet lien aussi).

David Gouveia
la source
11
Si vous ne pouvez pas garantir que la tuile centrale sera toujours un terrain et une partie du continent, utilisez le remplissage par inondation pour marquer chaque tuile terrestre comme appartenant à une île particulière (remplissage par inondation de chaque tuile sans identifiant de goutte sur la carte, en marquant les tuiles remplies avec le même blobid s'il n'en a pas déjà un). Ensuite, supprimez tout sauf le blob avec le plus de tuiles.
George Duckett
Conformément à ce que GeorgeDuckett a dit - vous pourriez essayer les algorithmes de détection de blob Googling: c'est un problème courant en multi-touch utilisant FTIR. Je me souviens avoir créé un algorithme plus intelligent, mais je ne me souviens pas de la façon dont il a fonctionné.
Jonathan Dickinson
Comme j'ai eu des problèmes de pile en PHP, j'ai implémenté le remplissage d'inondation LIFO, a fonctionné à merveille.
Gabriel A. Zorrilla
N'est-ce pas un remplissage d'inondation uniquement lorsqu'un algorithme DFS est appelé à partir d'un algorithme BFS? Veuillez expliquer quelqu'un.
jcora
@Bane Que voulez-vous dire? La différence entre DFS ou BFS est simplement l'ordre dans lequel les nœuds sont visités. Je ne pense pas que l'algorithme de remplissage d'inondation spécifie l'ordre de traversée - il s'en fiche tant qu'il remplit toute la région sans revoir les nœuds. L'ordre dépend de la mise en œuvre. Voir le bas de l' entrée wikipedia pour une image comparant l'ordre de traversée lors de l'utilisation d'une file d'attente par rapport à l'utilisation d'une pile. L'implémentation récursive peut également être considérée comme une pile (car elle utilise la pile des appels).
David Gouveia
5

Il s'agit d'une opération standard dans le traitement d'image. Vous utilisez une opération en deux phases.

Commencez par créer une copie de la carte. À partir de cette carte, transformez en pixels de mer tous les pixels de terre qui bordent la mer. Si vous faites cela une fois, cela éliminera les îles 2x2 et réduira les îles plus grandes. Si vous le faites deux fois, cela éliminera les îles 4x4, etc.

Dans la phase deux, vous faites presque l'inverse: transformez en pixels terrestres tous les pixels marins qui bordent la terre, mais seulement s'ils étaient des pixels terrestres dans la carte d'origine (c'est pourquoi vous avez fait une copie dans la phase 1). Cela fait repousser les îles à leur forme d'origine, sauf si elles ont été entièrement éliminées en phase 1.

MSalters
la source
1

J'ai eu un problème similaire mais pas dans le développement de jeux. J'ai dû trouver des pixels dans une image qui étaient adjacents les uns aux autres et avaient la même valeur (régions connectées). J'ai essayé d'utiliser un floodfill récursif mais j'ai continué à provoquer des débordements de pile (je suis un programmeur débutant: P). Ensuite, j'ai essayé cette méthode http://en.wikipedia.org/wiki/Connected-component_labeling, elle était en fait beaucoup plus efficace, pour mon problème de toute façon.

Elegant_Cow
la source
Vous devriez avoir essayé la version de pile de l'inondation et enregistrer les problèmes de pile. S'est avéré être beaucoup plus simple que CCL (que j'ai travaillé les 2 dernières semaines sans chance.)
Gabriel A. Zorrilla
Oui, j'ai essayé les deux, mais j'ai d'abord fait fonctionner le CCL: P et j'ai pensé que c'était une bonne idée. Heureux que vous ayez résolu votre problème :)
Elegant_Cow