Имеется конечный 2D мир, состоящий из чанков, каждый из которых содержит в себе 16x16 тайлов. Размер мира - до 32к x 16к тайлов. Для генерации использую шум перлинга. Мир генерируется не весь сразу, а по мере передвижения игрока. Существуют различные биомы, у каждого из которых имеется некоторый набор тайлов. Например: почва тундры, песок пустыни и так далее.
Пример карты биомов:
И необходимо на определённых тайлах расставить объекты (upd: деревья, камни) с какой-то минимальной дистанцией между друг другом, да так, что бы в определённых участках, задаваемых специальной картой плотности (upd: влажность для деревьев, расстояние до гор для камней), эту дистанцию можно было менять. Для этих целей вполне себе может подойти алгоритм Poisson Disk, и я даже его реализовал:
Однако, есть проблема. Для работы алгоритма необходимо задать ширину и высоту рабочей области, а я не могу себе позволить генерировать poisson disk для всей карты, потому что она достаточно большая и на генерацию уйдёт непростительно много времени. Мне же необходимо генерировать маленькие кусочки карты, да так, чтобы при повторной генерации одного куска, результат не изменился, и между данным куском и остальными не было заметно швов. Можно ли модифицировать алгоритм Poisson Disk для решения этой задачи, или необходимо искать другой вариант? Если да, то какой?
UPD:
Пример того, чего я хочу добиться
Здесь точки - это деревья. Как видите, в разных местах плотность деревьев различается. Именно в этом примере плотность зависит лишь от биома. Мне бы хотелось иметь возможность привнести некий элемент случайности, как в примере с Poisson Disk выше. Т. е. иметь в одном биоме поляны с малым кол-вом деревьев, густые леса и так далее.
Источник
В источнике алгоритм крайне неэффективный, и автор сам об этом говорит
Ответ
Я несколько месяцев назад реализовывал нечто подобное для одной своей игрушки. На скриншоте карты видны оранжевые точки - деревья:
Они расставлены с разной плотностью. Сам алгоритм имеет сложность, соизмеримую с количеством сгенерированных деревьев. Я не знаю, подойдет ли вам такой способ, или нет, так как деревья генерируются для каждого "чанка" отдельно (per-chunk).
Небольшое предисловие. Я в своем алгоритме различные структуры генерировал по-разному, но что касается ландшафта и деревьев - они генерировались для каждого чанка отдельно.
У каждого чанка был свой seed, по которому этот чанк генерировался. Сид я брал из шума перлина по координатам чанка, к примеру: seed = getPerlin(chunkX, chunkY). Дальше уже используя этот сид я генерировал все структуры на чанке.
А теперь к деревьям. Для начала я выбрал алгоритм, которым можно псевдорандомно расставить деревья. Выбор пал на halton sequence. Тут все просто:
getHalton(index, base) {
var result = 0;
var f = 1 / base;
var i = index;
while(i > 0) {
result = result + f * (i % base);
i = Math.floor(i / base);
f = f / base;
}
return result;
}
index - номер в последовательности, base - основание. Для того, чтобы расставить точки в двухмерном пространстве, я использовал основания 2 и 3. Как-то так:
var x = getHalton(index, 2) * chunkSize;
var y = getHalton(index, 3) * chunkSize;
Здесь chunkSize - размер чанка (т.к. значения getHalton в интервале [0, 1]). Для того, чтобы получать в зависимости от сида различные вариации расстановки деревьев, я вводил переменную indexShift. Это просто целое число, сгенерированное по seed'у. И мы просто добавляем его к index'у.
Для наглядности введем некую функцию setTree(x, y), которая будет устанавливать деревья в той точке чанка, в которой нам нужно. Тогда генерация деревьев будет выглядеть так:
for (var i = 0; i < treesCount; ++i) {
var x = getHalton(i + indexShift, 2) * chunkSize;
var y = getHalton(i + indexShift, 3) * chunkSize;
setTree(x, y);
}
Хорошо. Теперь у нас есть псевдорандомно расставленные деревья. Но этого же нам не хватит, верно?
И тогда на помощь приходит все тот же шум перлина. Так как я использовал в своем проекте шум, который возвращал значения в диапазоне [-1, 1], а я хотел получить значения между [0, 1], то брал я значение вот так:
var value = getPerlin(x * noiseScale, y * noiseScale) * 0.5 + 0.5;
Переменная noiseScale использовалась для настройки масштаба шума. Хорошо, теперь у нас есть значение в диапазоне [0; 1]. Но как это нам поможет? А давайте модифицируем код генерации деревьев вот так!:
for (var i = 0; i < treesCount; ++i) {
var x = getHalton(i + indexShift, 2) * chunkSize;
var y = getHalton(i + indexShift, 3) * chunkSize;
var densityInPoint = getPerlin(x * noiseScale, y * noiseScale) * 0.5 + 0.5;
if (i < treesCount * densityInPoint) setTree(x, y);
}
Таким образом, мы отсеиваем некоторую часть деревьев в тех местах, где шум перлина имеет низкие значения.
Итак, что мы имеем: некоторый алгоритм. Результат его работы зависит от трех переменных:
treesCount - чем больше, тем больше общая плотность деревьев.
noiseScale - чем больше, тем быстрее меняется плотность на единицу расстояния (тем менее плотность однородна).
densityInPoint - разные значения дают в целом разный результат.
P.S.: кстати, мне показалось, что линейное значение densityInPoint дает не очень хороший результат, так что я дополнительно возводил его в квадрат.
P.P.S.: на карте видна разная плотность деревьев в разных биомах. Для такого результата я просто задавал разные значения treesCount для каждого биома.
P.P.P.S.: если у вас деревья выставляются в матрицу, то значения x и y должны быть целыми. Тогда просто берите целую их часть:
setTree(Math.floor(x), Math.floor(y));
P.P.P.P.S.: я не утверждаю, что такой вариант решения самый лучший и самый правильный. Однако он гораздо быстрее метода, который вы нашли в статье, и для меня он давал приемлимые результаты.
Комментариев нет:
Отправить комментарий