Какой хороший способ генерировать случайные кластеры и пути?

Question

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

Одним из самых простых случаев является лес :

                    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 # вопрос.)

Answer 1

Реалистичное «случайное» распределение часто выполняется с использованием Perlin Noise , которое можно использовать для получения распределения с «скоплениями», как вы упомянули.Он работает путем суммирования / объединения нескольких слоев линейно интерполированных значений из случайных точек данных.Каждый слой (или «октава») имеет в два раза больше точек данных, чем последний, и ограничен более узким диапазоном значений.В результате получается «реалистично» выглядящая случайная текстура.

Вот прекрасная демонстрация теории Perlin Noise от Hugo Elias.

Здесьэто первое, что я нашел в Perlin Noise в C # .

Что вы можете сделать, это сгенерировать изображение Perlin Noise и установить «порог», где все, что выше значения, «включено»и все под ним "выключено".То, что вы в итоге получите, это комки, где вещи выше порога, которые выглядят нерегулярно и потрясающе.Просто присвойте те, которые выше порогового значения, где вы хотите, чтобы ваша функция ландшафта была.

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

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

Обратите внимание, чтоВы также можете установить «коэффициент сгущения» или тенденцию к слипанию функций, установив «турбулентность» функции Perlin Noise, которая в основном приводит к тому, что пики и впадины вашей функции PN акцентируются и сближаются.

Теперь, где установить порог?Чем выше пороговое значение, тем ниже процентное содержание объекта на конечной карте.Чем ниже порог, тем выше процент.Вы можете возиться с ними.Вы могли бы, вероятно, получить точные проценты, поигравшись с небольшой математикой (кажется, что распределение значений следует за Normal Distribution ; я могу ошибаться).Изменяйте его до тех пор, пока оно не станет правильным:)

EDIT Как указано в комментариях, вы можете найти точный процент, создав кумулятивную гистограмму (индекс того, какой% карты находится подпорог) и выберите порог, который дает вам процент, который вам нужен.

Самое классное здесь то, что вы можете создавать функции, которые объединяются вокруг некоторых других функций (например, ваши болотные функции) здесь тривиально - просто используйте тот жеPerlin Noise map дважды - второй раз, понизив порог.Первый будет комковатым, а второй - комковатым в тех же областях, но с увеличенными скоплениями (см. Флэш-анимацию, опубликованную ранее).

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

---

samples

Вот образец плитки 50x50 Sparse Forest Map.Подлесок окрашен в коричневый цвет, а деревья окрашены в синий цвет (извините), чтобы было ясно, какой именно.

Редкий лес http://img688.imageshack.us/img688/7005/forestmap.png

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

---

Вот демонстрация ваших особенностей болота (не включая подлесок, для ясности) с мелким болотом серого цвета и глубоким болотом сзади:

Болота http://img202.imageshack.us/img202/5092/marshdemo.png

Это всего лишь 50x50, поэтому есть некоторые артефакты, но вы можете видеть, как легко вы можете заставить мелкое болото «расти» из глубокого болота - просто отрегулировав порог на той же карте Perlin.Для этого я намерил пороговый уровень, чтобы получить наиболее приятные для глаз результаты, но в своих собственных целях вы могли бы сделать то, что упоминалось ранее.

Вот карта болота, созданная из той же карты Perlin Noise, но вместо этого на растянутой более 250х250 плиточной карте:

Болота 250х250 http://img251.imageshack.us/img251/2867/marshdemo250.png

Answer 2

Я никогда такого не делал, но вот некоторые мысли.

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

Для путей вы можете использовать аналогичную процедуру, за исключением того, что пути будут расширяться пошагово (вероятность пути конечна в квадратах рядом с концом пути и в нуле везде). Направленные пути могут быть сделаны путем увеличения вероятности выбора в направлении пути. Извивающиеся пути могут иметь направление, которое изменяется в ходе случайного расширения (new_direction = mf * old_direction + (1-mf) * rand_direction, где mf - коэффициент импульса между 0 и 1).

Answer 3

Чтобы расширить комментарии AcadeRobot, вы можете начать с болота или семени по умолчанию в некоторых ячейках сетки и позволить им расти из источника, используя коррелированное случайное число.Например, болото может иметь восемь соседних ячеек сетки, каждая из которых имеет 90% вероятности того, что она также является болотом, но 10% вероятность быть чем-то другим.Вы можете позволить экосистеме формироваться из семени и корректировать корреляцию, пока не получите то, что выглядит правильно.Вероятно, довольно легко реализовать даже в электронной таблице.

Answer 4

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

Answer 5

Вы можете начать читать ссылки здесь .Я помню, как смотрел на гораздо лучший документ.Опубликует это, если я найду это (это было также основано на L-системах).

Но это на общей стороне;по конкретной проблеме, с которой вы столкнулись, я думаю, вам следует смоделировать ее с точки зрения

• процентов
• других правил (кластеров и путей)

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

Если вы все еще хотите использовать генеративный подход, вам придется изучить генеративные правила немного ближе;вот идея, которую я бы преследовал

• создавать шаблоны различных ландшафтов и рельефов местности, которые имеют требуемые свойства 'кластерность', 'траектория' или однородность
• создавать шаблоны в таком видеспособ, которым значения для глубокого болота не являются дискретными, но назначают значение вероятности;после того, как шаблон был создан, вы можете нормализовать эту вероятность таким образом, чтобы она давала требуемый процент покрытия
• , смешивая различные образцы вместе