Это вопрос новичка, но здесь он идет:
Моя карта - это двумерная сетка, и я хочу создавать дороги и реки. Маршрут от начальной до конечной точки не должен быть оптимальным по количеству плиток. Вместо этого они должны иметь определенный уровень случайности (повороты).
Есть ли стандартный алгоритм для такого рода вещей?
Ура!
ОБНОВИТЬ:
Это результат игры с весами на сетке и применения алгоритма кратчайшего пути (Беллмана-Форда) с использованием библиотеки jgrapht. Я пошел с ответом Donutz в конце концов.
Ответы:
Вы можете создать оптимальный путь, используя A *, а затем исказить его смещением средней точки.
Это обеспечит достижение ваших конечных точек и позволит вам в значительной степени контролировать случайность. Например, я бы не разбирал дороги так, как реки. Какой бы интеллект ни строил дороги, обычно он пытается быть оптимальным.
Убедитесь, что если на вашей карте есть препятствия, вы проверяете после каждой итерации, что вы не пересекаете эти препятствия.
Другим методом будет генерирование шума Перлина после нахождения оптимального пути, а затем смещение точек на основе генерируемого шума. Например, используя этот шум:
Затем покажите с оптимальным путем красным и смещенным путем синим:
Обратите внимание, как смещенный путь «обосновался» в более темных областях шума. Точно так же река может течь через долину.
Одним из преимуществ выбора шума Perlin является то, что вы можете учитывать свои препятствия и избегать их как часть алгоритма.
источник
Алгоритм A * также позволит вам присваивать значения плиткам, указывая их пригодность. Например, вы можете назначить самые низкие показатели стоимости для низменных земель для рек, для равнинных земель (но не болот) для дорог, и генерировать на основе этого. Это не самый короткий маршрут, но самый эффективный. Примените небольшую случайность к вашим значениям плитки, и вы можете получить некоторые неоптимальные маршруты.
источник
Как насчет того, когда рост является фактором? Я могу сделать карту высот с помощью алгоритма алмазного квадрата. Я думал о добавлении некоторой случайной воды к каждой плитке, а затем итерации и перемещении воды на более низкие возвышения до тех пор, пока все не уладится, но это замедлится и, вероятно, приведет к образованию озер, а не рек.
Я также думал о поиске нормалей для каждой плитки. Если 2 нормали указывают друг на друга, то это должна быть долина. Вода будет собираться в долине. Если они указывают в одном направлении или друг от друга, вода не будет собираться. Это, вероятно, будет быстрее, чем метод итерации, но может сделать не озера, а только реки. Я должен был бы поиграть с этим, чтобы не превращать каждый экземпляр плиток, указывающих друг на друга, в реку.
источник