Jak losowo umieszczać elementy, które się nie nakładają?

Tworzę losowo generowane środowisko dla gry, którą tworzę. Używam OpenGLi koduję Java.

Staram się losowo umieszczać drzewa w moim świecie (aby utworzyć las), ale nie chcę, aby modele nakładały się (co dzieje się, gdy dwa drzewa są umieszczone zbyt blisko siebie). Oto zdjęcie tego, o czym mówię:

W razie potrzeby mogę podać więcej kodu, ale oto niezbędne fragmenty. I 'm przechowywanie moje obiekty w ArrayListz List<Entity> entities = new ArrayList<Entity>();. Następnie dodaję do tej listy, używając:

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);
}

gdzie każdy Entityma następującą składnię:

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

rotXoznacza obrót wzdłuż osi x, i scaleXjest skalą w kierunku x itp.

Widać, że jestem umieszczenie tych drzew losowo z random.nextFloat()za xi zstanowisk, a ograniczająca zakres więc drzewa pojawią się w odpowiednim miejscu. Chciałbym jednak jakoś kontrolować te pozycje, aby jeśli spróbuje umieścić drzewo zbyt blisko poprzednio umieszczonego drzewa, przeliczy nową pozycję losową. Myślałem, że każde drzewo Entitymoże mieć inne pole, na przykład treeTrunkGirth, a jeśli drzewo zostanie umieszczone w odległości między lokalizacją innego drzewa, a ono treeTrunkGirth, wówczas ponownie obliczy nową pozycję. Czy istnieje sposób na osiągnięcie tego?

W razie potrzeby chętnie dodam więcej fragmentów kodu i szczegółów.

A Poissona-Disk Sampling dystrybucja pozwoli Ci wybrać losowo punktów minimalnej odległości od siebie. Twoja sytuacja jest podobna do tego pytania , ale ponieważ twoje drzewa nie są wyidealizowanymi punktami, musisz zmienić sprawdzanie odległości w następujący sposób: odległość między potencjalnym nowym drzewem a istniejącym drzewem musi być mniejsza niż suma ich promieni .

Algorytm Bridsona może skutecznie rozwiązać problem w O (n), ale może być nieco kłopotliwy, aby dostosować go do zmiennych odległości. Jeśli twoje parametry są niskie i / lub wstępnie obliczasz swój teren, rozwiązanie brutalnej siły może ci również służyć. Oto przykładowy kod, który brutalnie zmusza problem, sprawdzając każde potencjalne umiejscowienie nowego drzewa względem wszystkich wcześniej umieszczonych drzew:

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;
}

Z następującymi parametrami:

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

Byłem w stanie losowo umieścić i renderować od 400 do 450 drzew w ciągu sekundy. Oto przykład: