Wie platziere ich Objekte, die sich nicht überlappen, zufällig?

11

Ich erstelle eine zufällig generierte Umgebung für ein Spiel, das ich entwickle. Ich benutze OpenGLund codiere in Java.

Ich versuche, zufällig Bäume in meiner Welt zu platzieren (um einen Wald zu erstellen), aber ich möchte nicht, dass sich die Modelle überlappen (was passiert, wenn zwei Bäume zu nahe beieinander stehen). Hier ist ein Bild von dem, wovon ich spreche:

Geben Sie hier die Bildbeschreibung ein

Ich kann bei Bedarf mehr Code bereitstellen, aber hier sind die wesentlichen Ausschnitte. Ich lagere meine Objekte in einem ArrayListmit List<Entity> entities = new ArrayList<Entity>();. Ich füge dieser Liste dann Folgendes hinzu:

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

Dabei Entityfolgt jeder der folgenden Syntax:

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

rotXist die Drehung entlang der x-Achse und scaleXist die Skala in x-Richtung usw.

Sie können sehen , dass ich diese Bäume zufällig bin Platzierung random.nextFloat()für die xund zPositionen, und begrenzen den Bereich , so dass die Bäume in der gewünschten Position angezeigt werden. Ich möchte diese Positionen jedoch irgendwie steuern, sodass beim Versuch, einen Baum zu nahe an einem zuvor platzierten Baum zu platzieren, eine neue zufällige Position neu berechnet wird. Ich dachte, dass jeder Baum Entityein anderes Feld haben könnte, wie zum Beispiel treeTrunkGirth, und wenn ein Baum in der Entfernung zwischen dem Standort eines anderen Baums und treeTrunkGirthseinem Platz platziert wird, berechnet er eine neue Position neu. Gibt es eine Möglichkeit, dies zu erreichen?

Gerne füge ich bei Bedarf weitere Codefragmente und Details hinzu.

wcarhart
quelle
3
Poisson Disk Sampling sollte die Arbeit erledigen. Ich weiß nicht, ob es das Beste dafür ist und habe es nie wirklich implementiert / verwendet, aber es scheint zumindest ein guter Anfang zu sein. Überprüfen Sie diesen Artikel: devmag.org.za/2009/05/03/poisson-disk-sampling
Mars
@ Mars Wow, dieser Link ist super hilfreich, danke. Ich werde sehen, was ich tun kann, und vielleicht mit einer eigenen Antwort zurückkommen.
Wcarhart
@Pikalek Ja, ich denke, diese Frage, die Sie verlinkt haben, ist ein Duplikat. Würde ich einfach die xz-Ebene als Fläche für die "Sternenkarte" verwenden, wie in der anderen Frage?
wcarhart
Ja, verwenden Sie in Ihrem Fall die xz- Ebene. Verwenden Sie treeTrunkGirthanstelle einer Konstante auch den Mindestabstand zum Platzieren eines Baums, wenn dieser variieren muss.
Pikalek
@Pikalek Wenn Sie das alles in einer Antwort zusammenfassen, werde ich es als die beste auswählen. Danke für die Hilfe.
Wcarhart

Antworten:

15

Mit einer Poisson-Disk-Sampling- Verteilung können Sie zufällige Punkte in einem Mindestabstand auswählen. Ihre Situation ähnelt dieser Frage , aber da Ihre Bäume keine idealisierten Punkte sind, müssen Sie die Entfernungsprüfung wie folgt ändern: Die Entfernung zwischen einem potenziellen neuen Baum und einem vorhandenen Baum muss kleiner sein als die Summe ihrer Radien .

Der Bridson-Algorithmus kann das Problem in O (n) effizient lösen, aber es kann etwas umständlich sein, es für variable Entfernungen zu optimieren. Wenn Ihre Parameter niedrig sind und / oder Sie Ihr Gelände vorberechnen, kann Ihnen eine Brute-Force-Lösung genauso gut helfen. Hier ist ein Beispielcode, der das Problem durch Brute erzwingt, indem jede potenzielle neue Baumplatzierung mit allen zuvor platzierten Bäumen verglichen wird:

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

Mit folgenden Parametern:

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

Ich konnte in weniger als einer Sekunde zwischen 400 und 450 Bäume zufällig platzieren und rendern. Hier ist ein Beispiel: Geben Sie hier die Bildbeschreibung ein

Pikalek
quelle
Verwendet dies Poisson Disk Sampling?
Wcarhart
Ja, ich habe bearbeitet, um dies explizit zu machen.
Pikalek
Versuchen Sie, math.pow on tree.r + other tree.r, 2, anstelle von math.sqrt zu verwenden, sqrt ist normalerweise langsamer als pow
Ferrybig
1
@Ferrybig Der Vergleich von quadratischen Entfernungen ist schneller, aber das ändert nichts an der Tatsache, dass es sich um einen Brute-Force-Algorithmus handelt und immer noch O (n ^ 2) ist. Wenn eine schnellere Lösung erforderlich ist, verwenden Sie den Bridson-Algorithmus. Auch die Verwendung Math.pow(x,2)ist nicht unbedingt besser / anders als die Verwendung von x*xwie hier diskutiert .
Pikalek
1
Ich hatte ein ähnliches Problem mit dem Gelände und sorgte für eine anständige Ausbreitung und keine Überlappung. Ich hatte tatsächlich eine Variation gemacht, in meiner Version sind die Locken / Pinsel zufällig über das Gelände verteilt. Ich führe dann eine Funktion aus, um die Abstände jedes Gegenstands gegeneinander zu überprüfen, wo sie zu nahe waren. Ich schob sie auseinander. Dies wird jedoch möglicherweise andere Bäume in der Umgebung treffen. Ich wiederholte dies, bis ich keine Kollisionen mehr hatte. Es ist langsamer, aber was ich auch als Bonus hatte, waren Dinge wie Lichtungen (nicht überall ist bedeckt!) und Baumdichte schienen "interessanter".
ErnieDingo