Как случайно разместить объекты, которые не перекрываются?

11

Я создаю случайно сгенерированную среду для игры, которую разрабатываю. Я использую OpenGLи кодирую Java.

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

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

Я могу предоставить больше кода, если это необходимо, но вот основные фрагменты. Я храню свои объекты в ArrayListс List<Entity> entities = new ArrayList<Entity>();. Затем я добавляю в этот список, используя:

Random random = new Random();
for (int i = 0; i < 500; i++) {
    entities.add(new Entity(tree, new Vector3f(random.nextFloat() * 800 - 400, 
    0, random.nextFloat() * -600), 0, random.nextFloat() * 360, 0, 3, 3, 3);
}

где каждый Entityпридерживается следующего синтаксиса:

new Entity(modelName, positionVector(x, y, z), rotX, rotY, rotZ, scaleX, scaleY, scaleZ);

rotXвращение вдоль оси x, scaleXмасштаб в направлении x и т. д.

Вы можете видеть , что я помещаю эти деревья в случайном порядке с random.nextFloat()для xи zпозиций, и ограничивающая диапазон так , деревья будут появляться в нужном месте. Однако я хотел бы как-то контролировать эти позиции, чтобы, если он попытается разместить дерево слишком близко к ранее размещенному дереву, он пересчитает новую случайную позицию. Я думал, что у каждого дерева Entityможет быть другое поле, например treeTrunkGirth, и если дерево находится на расстоянии между местоположением другого дерева и оно treeTrunkGirth, то оно пересчитает новую позицию. Есть ли способ сделать это?

Я рад добавить больше фрагментов кода и деталей по мере необходимости.

wcarhart
источник
3
Выборка диска Пуассона должна сделать работу. Не знаю, лучше ли это для этого, и никогда по-настоящему не реализовывал / не использовал это, но, по крайней мере, кажется хорошим началом. Проверьте эту статью: devmag.org.za/2009/05/03/poisson-disk-sampling
Марс
@ Mars Wow, эта ссылка очень полезна, спасибо. Я посмотрю, что я могу сделать, и, возможно, вернусь с ответом самостоятельно.
wcarhart
@Pikalek Да, я думаю, что вопрос, который вы связали, является дубликатом. Я бы просто использовал плоскость xz в качестве области для «звездной карты», как в другом вопросе?
wcarhart
Да, используйте плоскость XZ в вашем случае. Кроме того, используйте treeTrunkGirthвместо константы, чтобы определить минимальное расстояние для размещения дерева, если они должны варьироваться.
Пикалек
@Pikalek Если вы добавите все это в ответ, я выберу его как лучший. Спасибо за помощь.
wcarhart

Ответы:

15

А Пуассона-диск Отбор проб распределение позволит выбрать случайные точки минимальное расстояние друг от друга. Ваша ситуация похожа на этот вопрос , но поскольку ваши деревья не являются идеализированными точками, вам нужно изменить проверку расстояния следующим образом: расстояние между потенциальным новым деревом и существующим деревом должно быть меньше суммы их радиусов ,

Алгоритм Бридсона может эффективно решить проблему в O (n), но его может быть немного сложно настроить для переменных расстояний. Если ваши параметры невелики и / или вы предварительно рассчитываете свою местность, то решение с использованием грубой силы также может вам пригодиться. Вот некоторый пример кода, который грубо заставляет проблему, проверяя каждое потенциальное новое размещение дерева против всех ранее размещенных деревьев:

public static class SimpleTree{
    float x;
    float z;
    float r;

    public SimpleTree(Random rng, float xMax, float zMax, float rMin, float rMax){
        x = rng.nextFloat() * xMax;
        z = rng.nextFloat() * zMax;
        r = rng.nextFloat() * (rMax-rMin) + rMin;
    }
}

private static ArrayList<SimpleTree> buildTreeList(float xMax, float zMax, 
        float rMin, float rMax, int maxAttempts, Random rng) {
    ArrayList<SimpleTree> result = new ArrayList<>();

    SimpleTree currentTree = new SimpleTree(rng, xMax, zMax, rMin, rMax);
    result.add(currentTree);

    boolean done = false;
    while(!done){
        int attemptCount = 0;
        boolean placedTree = false;
        Point nextPoint = new Point();
        SimpleTree nextTree = null;
        while(attemptCount < maxAttempts && !placedTree){
            attemptCount++;
            nextTree = new SimpleTree(rng, xMax, zMax, rMin, rMax);
            if(!tooClose(nextTree, result)){
                placedTree = true;
            }
        }
        if(placedTree){
            result.add(nextTree);
        }
        else{
            done = true;
        }
    }

    return result;
}

private static boolean tooClose(SimpleTree tree, ArrayList<SimpleTree> treeList) {
    for(SimpleTree otherTree : treeList) {
        float xDiff = tree.x - otherTree.x;
        float zDiff = tree.z - otherTree.z;

        float dist = (float)Math.sqrt((xDiff * xDiff) + (zDiff * zDiff));
        if(dist < tree.r + otherTree.r){
            return true;
        }
    }        
    return false;
}

Со следующими параметрами:

 maxAttempts = 500;
 width = 300;
 height = 200;
 minSize = 2;
 maxSize = 15;

Я был в состоянии произвольно разместить и визуализировать между 400-450 деревьями менее чем за секунду. Вот пример: введите описание изображения здесь

Pikalek
источник
Использует ли это сэмплирование диска Пуассона?
wcarhart
Да, я отредактировал, чтобы сделать это явным.
Пикалек
Попробуйте использовать math.pow tree.r + other tree.r, 2 вместо math.sqrt, sqrt обычно медленнее, чем pow
Ferrybig
1
@Ferrybig Сравнение квадратов расстояний быстрее, но это не меняет того факта, что это алгоритм грубой силы и все равно будет O (n ^ 2). Если требуется более быстрое решение, используйте алгоритм Бридсона. Кроме того, использование Math.pow(x,2)не обязательно лучше / отличается от использования, x*xкак описано здесь .
Пикалек
1
У меня была похожая проблема с ландшафтом и обеспечением некоторого приличного распространения и без перекрытия. Я на самом деле сделал вариант, в моей версии тресс / кисть случайным образом распределены по местности. Затем я запускаю функцию, публикуя эту функцию, чтобы проверить расстояния каждого элемента друг против друга, где они были слишком близко, и я раздвинул их. Это, однако, может столкнуться с другими деревьями в этом районе. Я повторял это, пока у меня не было никаких столкновений. это медленнее, но в качестве бонуса у меня были такие вещи, как расчистка (не везде покрыто!) и плотность деревьев, которые казались более «интересными».
ErnieDingo