Я несколько месяцев назад реализовывал нечто подобное для одной своей игрушки. На скриншоте карты видны оранжевые точки - деревья:

Они расставлены с разной плотностью. Сам алгоритм имеет сложность, соизмеримую с количеством сгенерированных деревьев. Я не знаю, подойдет ли вам такой способ, или нет, так как деревья генерируются для каждого "чанка" отдельно (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.: я не утверждаю, что такой вариант решения самый лучший и самый правильный. Однако он гораздо быстрее метода, который вы нашли в статье, и для меня он давал приемлимые результаты.