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

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

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?

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

Modifiez l'algorithme de remplissage de l'inondation à quatre directions http://en.wikipedia.org/wiki/Flood_fill

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.

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.