Что хороший путь состоит в том, чтобы генерировать случайные кластеры и пути?
Я играю вокруг с записью случайного генератора карты и не совсем уверен, как случайным образом генерировать реалистические среды. Я работаю с этими видами карт локального масштаба, который представляет некоторые интересные проблемы.
Один из самых простых случаев является лесом:
Sparse Medium Dense
Typical trees 50% 70% 80%
Massive trees — 10% 20%
Light undergrowth 50% 70% 50%
Heavy undergrowth — 20% 50%
Деревья и подлесок могут существовать в том же пространстве, таким образом, средний редкий лес имеет 25%-е типичные деревья и легкий подлесок, 25%-е типичные деревья, 25%-й легкий подлесок и 25%-е открытое пространство. Средние и густые леса возьмут немного больше взглядов, но это не, где моя проблема заключается также, поскольку это все равномерно рассеивается.
Моя проблема заключается в генерации кластеров и путей при хранении ограничений процента. Болота являются хорошим примером этого:
Moor Swamp
Shallow bog 20% 40%
Deep bog 5% 20%
Light undergrowth 30% 20%
Heavy undergrowth 10% 20%
Глубокие квадраты трясины обычно кластеризируются вместе и окружаются неправильным кольцом мелких квадратов трясины.
Дополнительный элемент карты, живая изгородь, может также присутствовать, а также путь открытого пространства, ползущего через трясину. Оба из этих типов элементов карты (кластеры и пути) существующие проблемы, поскольку общий состав карты должен содержать X % элемента, но это не равномерно распределяется. Другим элементам, таким как потоки, водоемы и плывун нужно или поколение кластерного или типа тракта также.
Какую технику я могу использовать для генерации реалистических карт, учитывая эти ограничения?
Я использую C#, к вашему сведению (но это не вопрос C#-specific.)
5 ответов
Реалистичное «случайное» распределение часто выполняется с использованием шума Перлина , который можно использовать для получения распределения с «сгустками», как вы упомянули. Он работает путем суммирования / объединения нескольких слоев линейно интерполированных значений из случайных точек данных. Каждый слой (или «октава») имеет вдвое больше точек данных, чем последний, и ограничен более узким диапазоном значений. В результате получается "реалистичная" случайная текстура.
Вот прекрасная демонстрация теории шума Перлина Хьюго Элиаса.
Вот первое, что я нашел на Perlin Noise в C # .
Что вы можете сделать, так это сгенерировать изображение Perlin Noise и установить «порог», при котором все, что выше значения, будет «включено», а все, что ниже этого значения, - «выключено». В итоге вы получите сгустки, расположенные выше порога, которые выглядят необычно и потрясающе. Просто назначьте те, которые выше порога, там, где вы хотите, чтобы ваш рельеф был.
Здесь демонстрируется , если программа генерирует битовую карту шума Перлина и затем регулирует порог отсечки с течением времени. Видно четкое «комкование». Это могло быть именно то, что вы хотели.
Обратите внимание, что при высоком пороге очень мало точек превышает его, и это немного. Но при понижении порога эти точки «разрастаются» в сгустки (по природе шума Перлина), и некоторые из этих сгустков соединяются друг с другом, создавая что-то очень естественное и похожее на местность.
Обратите внимание, что вы также можете установить «фактор слипания» или тенденцию к слипанию объектов, установив «турбулентность» вашей функции шума Perlin, которая в основном приводит к тому, что пики и спады вашей функции PN становятся более четкими и близкими. вместе.
А где установить порог? Чем выше порог, тем ниже процент объекта на окончательной карте. Чем ниже порог, тем выше процент. С ними можно повозиться. Вероятно, вы могли бы получить точные проценты, повозившись с небольшой математикой (кажется, что распределение значений соответствует нормальному распределению ; я могу ошибаться). Настраивайте его, пока он не станет правильным :)
РЕДАКТИРОВАТЬ Как указано в комментариях, вы можете найти точный процент, создав кумулятивную гистограмму (индекс того, какой% карты находится ниже порогового значения) и выберите порог это дает вам нужный процент.
Самым крутым здесь является то, что вы можете тривиально создавать элементы, которые объединяются вокруг некоторых других функций (например, ваших болотных функций) - просто используйте одну и ту же карту шума Perlin дважды - во второй раз, понижая порог. Первый будет бугристым, а второй будет бугристым вокруг тех же областей, но с увеличенными глыбами (см. Флеш-анимацию, размещенную ранее).
Что касается других функций, таких как живые изгороди, вы можете попробовать смоделировать простые линии случайного блуждания , которые имеют более высокую тенденцию идти прямо, чем поворот, и разместить их в произвольном месте на вашей карте на основе Perlin.
samples
Вот образец мозаичной карты разреженного леса 50x50.Подлесок окрашен в коричневый цвет, а деревья - в синий (извините), чтобы было понятно, что есть что.
Для этой карты я не устанавливал точных пороговых значений для соответствия 50%; Я только установил порог на уровне 50% от максимума. По статистике, каждый раз это будет в среднем ровно 50%. Но этого может быть недостаточно для ваших целей; см. предыдущее примечание о том, как это сделать.
Вот демонстрация особенностей вашего болота (не включая подлесок, для ясности), с мелким болотом в сером цвете и глубоким болотом сзади:
Это всего лишь 50x50, поэтому есть некоторые артефакты, но вы можете Посмотрите, как легко вы можете заставить мелкое болото «вырасти» из глубокого болота - просто отрегулировав порог на той же карте Перлина. Для этого я оценил пороговый уровень, чтобы получить наиболее приятные для глаз результаты, но для ваших собственных целей вы можете делать то, что упоминалось ранее.
Вот карта болота, созданная из той же карты шума Perlin, но вместо нее растянута на мозаичную карту 250x250:
Чтобы расширить комментарии AcadeRobot, вы можете начать с болотного или лесного семени по умолчанию в некоторых ячейках сетки и позволить им расти из источника, используя коррелированное случайное число. Например, болото может иметь восемь смежных ячеек сетки, каждая из которых с вероятностью 90% также является болотом, но с вероятностью 10% является чем-то другим. Вы можете позволить экосистеме сформироваться из семени и настроить корреляцию, пока не получите что-то, что выглядит правильно. Наверное, довольно легко реализовать даже в электронной таблице.
Вы можете начать читать ссылки здесь . Я помню, как смотрел документ намного лучше. Выложу, если найду (он тоже был основан на L-системах).
Но это общая сторона; по конкретной проблеме, с которой вы сталкиваетесь, я думаю, вам следует смоделировать ее в терминах
- процентов
- других правил (кластеры и пути)
Дело в том, что даже если вы не знаете, как построить карту с заданными properties, если вы можете оценить свойства (коэффициент кластеризации; удобство пути) и оценить их, вы можете затем применить грубую силу или выполнить какое-либо другое пересечение проблемного пространства.
Если вы все еще хотите использовать генеративный подход, вам придется изучить генеративные правила немного подробнее; вот идея, которую я преследовал
- , создавая шаблоны различных ландшафтов и покрытий местности, которые имеют требуемые свойства «кластеризации», «траектории» или однородности
- , создают шаблоны таким образом, что значения для глубокого болота не соответствуют сдержанно, но присвоить значение вероятности; после того, как шаблон был создан, вы можете нормализовать эту вероятность таким образом, чтобы он обеспечил необходимый процент покрытия
- , смешав разные шаблоны вместе
У вас может быть некоторый успех для определенных типов областей с узор Вороного . Я никогда не видел, чтобы он использовался для создания карт, но видел, как он используется в ряде аналогичных полей.
Я никогда не занимался подобными вещами, но вот некоторые мысли.
Вы можете получить кластеры путем смещения случайного выбора к местам на сетке, которые находятся рядом с существующими элементами этого типа. Присвойте всем квадратам значение по умолчанию 1. Для квадратов с существующими кластеризованными элементами добавьте значение кластеризации к соседним квадратам (чем выше значение кластеризации, тем сильнее будет кластеризация). Затем сделайте случайный выбор следующего элемента этого типа по функции распределения вероятностей всех квадратов.
Для путей можно использовать аналогичную процедуру, за исключением того, что пути будут расширяться пошагово (вероятность пути конечна в квадратах рядом с концом пути и равна нулю везде). Направленные пути могут быть сделаны путем увеличения вероятности выбора в направлении пути. Меандрирующие пути могли бы иметь направление, которое меняется в ходе случайного расширения (new_direction = mf * old_direction + (1-mf) * rand_direction, где mf - коэффициент импульса от 0 до 1).