Существует ли алгоритм обнаружения «материка» на 2D-карте?

На этой карте «материк» - это вся земля, которая может быть соединена с центром карты в четырех основных направлениях (север, юг, восток, запад - не по диагонали).

Я хотел бы обнаружить материк и заполнить в нем дыры. Я думал о трех вещах:

1. Поиск в каждой неводной (темной ячейке) ячейке, если она может быть подключена к центру карты с использованием алгоритма поиска пути. Слишком дорогой! Но это может работать на острова.

2. Материк заполнен ведром с зеленой краской. Каждая дыра окружена краской ... что теперь? Если я проверю каждую водную точку внутри материка на смежность, я удалю некоторые полуострова и другие географические объекты, отображаемые на береговой линии.

3. Какое-то обнаружение края, чтобы выяснить материк. Держите все, что есть внутри, заполните его водой, удалите то, что снаружи. Сложный?

Возможно, какой-нибудь опытный разработчик игр может помочь мне с этим, возможно, дав мне название какого-нибудь известного алгоритма или техники?

Удаление островов

Я делал подобные вещи раньше в одной из моих игр. Чтобы избавиться от внешних островов, процесс был в основном:

1. Во-первых, должна быть гарантия, что центр карты всегда будет принадлежать основной земле, и каждый пиксель начинается с «Земли» или «Воды» (т.е. разных цветов).
2. Затем выполните заливку в четырех направлениях, начиная с центра карты и распространяя ее по всем клеткам «Земли». Пометить каждый пиксель, который посещает эта заливка, как другой тип, такой как «MainLand».
3. Наконец, просмотрите всю карту и преобразуйте любой оставшийся пиксель «Земли» в «Вода», чтобы избавиться от других островов.

Удаление озер

Что касается избавления от дыр (или озер) внутри острова, вы делаете аналогичный процесс, но начинаете с углов карты и вместо этого растягиваетесь по плиткам «Вода». Это позволит вам отличить «Море» от других водных плиток, и тогда вы сможете избавиться от них так же, как раньше избавились от островов.

пример

Позвольте мне выкопать мою реализацию заливки, которая у меня где-то здесь (отказ от ответственности, я не заботился об эффективности, поэтому я уверен, что есть много более эффективных способов реализовать это):

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

Я использовал это в качестве первого шага, чтобы избавиться от озер в моей игре. После этого мне нужно было сделать что-то вроде:

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

редактировать

Добавление дополнительной информации на основе комментариев. Если ваше пространство поиска слишком велико, вы можете столкнуться с переполнением стека при использовании рекурсивной версии алгоритма. Вот ссылка на stackoverflow (каламбур предназначен :-)) на нерекурсивную версию алгоритма, использующую Stack<T>вместо этого (также в C #, чтобы соответствовать моему ответу, но должна быть легко адаптируемой к другим языкам, и есть другие реализации на этом ссылка тоже).

Измените алгоритм заполнения потока в четырех направлениях http://en.wikipedia.org/wiki/Flood_fill

Это стандартная операция при обработке изображений. Вы используете двухфазную операцию.

Начните с создания копии карты. С этой карты превратите в морские пиксели все пиксели суши, которые граничат с морем. Если вы сделаете это один раз, это исключит 2x2 острова и уменьшит большие острова. Если вы сделаете это дважды, это устранит 4x4 острова и так далее.

На втором этапе вы делаете почти обратное: превращаете в пиксели земли все морские пиксели, которые граничат с землей, но только в том случае, если они были пикселями земли на исходной карте (поэтому вы сделали копию на этапе 1). Это возвращает острова в их первоначальную форму, если они не были полностью устранены в фазе 1.

У меня была похожая проблема, но не в разработке игр. Я должен был найти пиксели в изображении, которые были смежны друг с другом и имели одинаковое значение (соединенные области). Я пытался использовать рекурсивное заполнение, но продолжало вызывать переполнение стека (я начинающий программист: P). Затем я попробовал этот метод http://en.wikipedia.org/wiki/Connected-component_labeling, на самом деле он был гораздо более эффективным, в любом случае для моей проблемы.