Каким образом процедурно расставлять объекты в 2D мире?

#алгоритм #разработка_игр

Имеется конечный 2D мир, состоящий из чанков, каждый из которых содержит в себе 16x16
тайлов. Размер мира - до 32к x 16к тайлов. Для генерации использую шум перлинга. Мир
генерируется не весь сразу, а по мере передвижения игрока. Существуют различные биомы,
у каждого из которых имеется некоторый набор тайлов. Например: почва тундры, песок
пустыни и так далее.

Пример карты биомов:


И необходимо на определённых тайлах расставить объекты (upd: деревья, камни) с какой-то
минимальной дистанцией между друг другом, да так, что бы в определённых участках, задаваемых
специальной картой плотности (upd: влажность для деревьев, расстояние до гор для камней),
эту дистанцию можно было менять. Для этих целей вполне себе может подойти алгоритм
Poisson Disk, и я даже его реализовал:


Однако, есть проблема. Для работы алгоритма необходимо задать ширину и высоту рабочей
области, а я не могу себе позволить генерировать poisson disk для всей карты, потому
что она достаточно большая и на генерацию уйдёт непростительно много времени. Мне же
необходимо генерировать маленькие кусочки карты, да так, чтобы при повторной генерации
одного куска, результат не изменился, и между данным куском и остальными не было заметно
швов. Можно ли модифицировать алгоритм Poisson Disk для решения этой задачи, или необходимо
искать другой вариант? Если да, то какой?

UPD:
Пример того, чего я хочу добиться


Здесь точки - это деревья. Как видите, в разных местах плотность деревьев различается.
Именно в этом примере плотность зависит лишь от биома. Мне бы хотелось иметь возможность
привнести некий элемент случайности, как в примере с Poisson Disk выше. Т. е. иметь
в одном биоме поляны с малым кол-вом деревьев, густые леса и так далее.

Источник

В источнике алгоритм крайне неэффективный, и автор сам об этом говорит
    

Ответы

Ответ 1

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



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