Поиск хорошего мирового [закрытого] алгоритма поколения карты

Просто подумайте о манжете здесь:

Выберите несколько начальных точек и назначьте каждой случайно выбранный (ожидаемый) размер. При желании вы можете создать отдельный размер для запланированных континентов и запланированных островов.

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

1. Расстояние до ближайшей "другой" земли. Дальше лучше всего порождает обширные океанические пространства. Чем ближе, тем лучше узкие каналы. Вы должны решить, собираетесь ли вы также позволить битам сливаться.
2. Расстояние от семени. Чем ближе, тем лучше - компактные участки земли, чем дальше, тем лучше - длинные участки
3. Количество существующих прилегающих участков земли. Если поставить вес в пользу множества прилегающих квадратов, у вас будет гладкое побережье, а если вы предпочтете несколько, то у вас будет много бухт и полуостровов.
4. Наличие рядом «ресурсных» квадратов? Зависит от правил игры, когда вы генерируете ресурсный квадрат, и если вы хотите, чтобы это было проще.
5. Вы позволите битам приблизиться или соединиться с полюсами?
6. ??? не знаю, что еще

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

Обратите внимание, что изменение параметра этих весовых коэффициентов позволяет вам настраивать тип создаваемого мира, что мне понравилось в некоторых цивилизациях.

Таким образом, вам нужно будет произвести генерацию ландшафта для каждого бита отдельно.

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

Изменить: Вот еще один способ сделать это, в комплекте с реализацией - Генерация полигональной карты для игр .

Я думаю, вы можете использовать здесь подход в стиле "динамического программирования".

Сначала решайте небольшие проблемы и разумно комбинируйте решения, чтобы решить большую проблему.

A1= [elliptical rectangular random ... ]// list of continents with area A1 approx. 
A2= [elliptical rectangular random ... ]// list of continents with area A2 approx.
A3= [elliptical rectangular random ... ]// list of continents with area A3 approx.
...
An= [elliptical rectangular random ... ]// list of continents with area An approx.

// note that elliptical is approximately elliptical in shape and same for the other shapes.

Choose one/more randomly from each of the lists (An).

Now you have control over number and area of continents.

You can use genetic algorithm for positioning them 
as you see "fit" ;)

Было бы очень хорошо взглянуть на некоторые «Алгоритмы компоновки графиков»

• Алгоритмы на основе силы
• Генетический алгоритм компоновки графов

Вы можете изменить их в соответствии с вашими целями.

Я бы посоветовал вам вернуться и

1. Подумать, что делает континенты "хорошими".
2. Напишите алгоритм, который отличит хорошую континентальную планировку от плохой.
3. Уточните алгоритм, чтобы вы могли количественно оценить, насколько хорош хороший макет.

Как только вы это сделаете, вы можете приступить к реализации алгоритма, который должен иметь такую ​​форму:

• Создавайте дрянные континенты, а затем улучшайте их.

Для улучшения вы можете попробовать всевозможные стандартные приемы оптимизации, будь то имитация отжига, генетическое программирование или что-то полностью специальное , например, перемещение случайно выбранного граничного квадрата из любого места на континенте в край, противоположный центру масс континента. Но главное - уметь написать программу , которая может отличать хорошие континенты от плохих. Начните с рисованных континентов, а также ваших тестовых континентов, пока не получите то, что вам нравится.

Я бы разместил фрактальный ландшафт в соответствии с некоторым макетом, который, как вы знаете, «работает» (например, сетка 2x2, ромб и т. Д., С некоторым дрожанием), но с Затухание гауссова распределения достигает максимума к краям центров континентов. Поместите уровень воды ниже, чтобы он был в основном на суше, пока не приблизитесь к краям.

Я на самом деле не пробовал это, но это было вдохновлено ответом Дэвида Джонстона относительно тектонических плит. Я сам пробовал реализовать это в своем старом проекте Civ, и когда дело дошло до обработки столкновений, у меня появилась другая идея. Вместо того, чтобы генерировать плитки напрямую, каждый континент состоит из узлов. Распределите массу по каждому узлу, затем сгенерируйте серию континентов-капель, используя двухмерный метабаллический подход. Тектонику и дрейф континентов было бы до смешного легко «подделать», просто перемещая узлы. В зависимости от того, насколько сложным вы хотите заниматься, вы даже можете применить такие вещи, как токи, для управления движением узлов и создания горных хребтов, соответствующих перекрывающимся границам плит. Наверное, не добавило бы так много к геймплею, но это могло бы сделать создание карты интересным с чисто академической точки зрения :)

Хорошее объяснение метабаллов, если вы раньше с ними не работали:

http://www.gamedev.net/page/resources/_//feature/fprogramming/exploring-metaballs-and-isosurfaces-in-2d-r2556

Я написал нечто похожее на то, что вам нужно для автоматический клон Civilization 1 в стиле скринсейвера. Для записи я написал это на VB.net, но, поскольку вы ничего не упоминаете о языке или платформе в своем вопросе, я оставлю это абстрактным.

«Карта» указывает количество континентов, разницу в размерах континентов (например, 1,0 сохранит все континенты с одинаковой приблизительной площадью суши, при уменьшении до 0,1 материки будут существовать с массой, составляющей 1/10 массы самого большого континента), максимальная площадь земли (в процентах) для создания и центральный уклон земли. «Семя» случайным образом распределяется по карте для каждого континента, взвешенное по направлению к центру карты в соответствии с центральным смещением (например, низкое смещение создает распределенные континенты, более похожие на Землю, тогда как высокое центральное смещение будет больше напоминать Пангея).Затем для каждой итерации роста «семена» назначают тайлы земли в соответствии с алгоритмом распределения (подробнее об этом позже), пока не будет достигнута максимальная площадь земли.

Алгоритм распределения земли может быть сколь угодно точным, но я нашел более интересные результаты, применяя различные генетические алгоритмы и бросая кости.«Игра жизни» Конвея действительно легко начать. Вам нужно будет добавить НЕКОТОРАЯ глобально осведомленную логику, чтобы избежать врастания континентов друг в друга, но по большей части вещи сами о себе позаботятся. Проблема, которую я обнаружил с более фрактальными подходами (что было моим первым желанием), заключалась в том, что результаты либо выглядели слишком шаблонно, либо приводили к слишком большому количеству сценариев, требующих хакерских обходных правил для получения результата, который все еще не казался достаточно динамичным. В зависимости от алгоритма, который вы используете, вы можете применить «размытие» к результату, чтобы исключить такие вещи, как обильные одноквадратные плитки океана и клетчатые береговые линии. В случае появления чего-то вроде континента в окружении нескольких других, которому некуда больше расти, переместите семя в новую точку на карте и продолжите прохождение роста. Да, это может означать, что иногда у вас оказывается больше континентов, чем планировалось, но если это действительно то, чего вы категорически не хотите, тогда еще один способ помочь избежать этого - смещать алгоритмы роста, чтобы они поддерживали рост в направлении с наименьшей близостью к другим. семена. В худшем случае (во всяком случае, на мой взгляд) вы можете пометить серию как недействительную, когда семени некуда вырасти, и сгенерировать новую карту. Просто убедитесь, что вы установили максимальное количество попыток, чтобы, если указано что-то нереалистичное (например, уместить 50 равных по весу континентов на доске 10x10), он не тратит вечно на попытки найти верное решение.

Я не могу поручиться за то, как Civ и т. Д. Это делают, и, конечно, не касается таких вещей, как климат, возраст земли и т. Д., Но, поиграв с алгоритмом роста семян, вы можете получить довольно интересные результаты, которые напоминают континенты, архипелаги и т. Д. Вы можете использовать тот же подход для создания «органических» рек, горных хребтов и т. Д.