Генерация дороги / реки на 2-й карте сетки

12

Это вопрос новичка, но здесь он идет:

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

Есть ли стандартный алгоритм для такого рода вещей?

Ура!

ОБНОВИТЬ:

Это результат игры с весами на сетке и применения алгоритма кратчайшего пути (Беллмана-Форда) с использованием библиотеки jgrapht. Я пошел с ответом Donutz в конце концов.

http://pastebin.com/AGQGK5ik

Маркос Фрагкакис
источник
Есть ли какие-либо препятствия на карте?
MichaelHouse
Пока нет, река будет первым препятствием на пути.
Маркос Фрагкакис

Ответы:

18

Вы можете создать оптимальный путь, используя A *, а затем исказить его смещением средней точки.

введите описание изображения здесь

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

Убедитесь, что если на вашей карте есть препятствия, вы проверяете после каждой итерации, что вы не пересекаете эти препятствия.

Другим методом будет генерирование шума Перлина после нахождения оптимального пути, а затем смещение точек на основе генерируемого шума. Например, используя этот шум:

введите описание изображения здесь

Затем покажите с оптимальным путем красным и смещенным путем синим:

введите описание изображения здесь

Обратите внимание, как смещенный путь «обосновался» в более темных областях шума. Точно так же река может течь через долину.

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

MichaelHouse
источник
1
Как вы делаете эту точку смещения базы на шум?
Хой
1
Это зависит от того, как вы храните шум и генерируемую линию. Сначала вы можете найти ближайший / самый низкий шум перпендикулярно линии в центре, затем в средних точках между центром и концами и так далее.
MichaelHouse
3

Алгоритм A * также позволит вам присваивать значения плиткам, указывая их пригодность. Например, вы можете назначить самые низкие показатели стоимости для низменных земель для рек, для равнинных земель (но не болот) для дорог, и генерировать на основе этого. Это не самый короткий маршрут, но самый эффективный. Примените небольшую случайность к вашим значениям плитки, и вы можете получить некоторые неоптимальные маршруты.

Donutz
источник
2

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

Я также думал о поиске нормалей для каждой плитки. Если 2 нормали указывают друг на друга, то это должна быть долина. Вода будет собираться в долине. Если они указывают в одном направлении или друг от друга, вода не будет собираться. Это, вероятно, будет быстрее, чем метод итерации, но может сделать не озера, а только реки. Я должен был бы поиграть с этим, чтобы не превращать каждый экземпляр плиток, указывающих друг на друга, в реку.

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