Comment placer au hasard des entités qui ne se chevauchent pas?

11

Je crée un environnement généré aléatoirement pour un jeu que je développe. J'utilise OpenGLet je code Java.

J'essaie de placer au hasard des arbres dans mon monde (pour créer une forêt), mais je ne veux pas que les modèles se chevauchent (ce qui se produit lorsque deux arbres sont placés trop près l'un de l'autre). Voici une photo de ce dont je parle:

entrez la description de l'image ici

Je peux fournir plus de code si nécessaire, mais voici les extraits essentiels. Je stocke mes objets dans un ArrayListavec List<Entity> entities = new ArrayList<Entity>();. J'ajoute ensuite à cette liste en utilisant:

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

où chacun Entitysuit la syntaxe suivante:

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

rotXest la rotation le long de l'axe x, et scaleXest l'échelle dans la direction x, etc.

Vous pouvez voir que je suis placer ces arbres au hasard avec random.nextFloat()les xet zpositions, et délimitant la plage de sorte que les arbres apparaissent à l'endroit désiré. Cependant, je voudrais en quelque sorte contrôler ces positions, de sorte que s'il essaie de placer un arbre trop près d'un arbre précédemment placé, il recalculera une nouvelle position aléatoire. Je pensais que chaque arbre Entitypourrait avoir un autre champ, tel que treeTrunkGirth, et si un arbre est placé à la distance entre l'emplacement d'un autre arbre et le sien treeTrunkGirth, il recalculera une nouvelle position. Existe-t-il un moyen d'y parvenir?

Je suis heureux d'ajouter plus d'extraits de code et de détails si nécessaire.

wcarhart
la source
3
L'échantillonnage sur disque de Poisson devrait faire le travail. Je ne sais pas si c'est mieux pour cela et jamais vraiment mis en œuvre / utilisé, mais cela semble au moins un bon début. Consultez cet article: devmag.org.za/2009/05/03/poisson-disk-sampling
Mars
@Mars Wow, ce lien est super utile, merci. Je verrai ce que je peux faire et je reviendrai peut-être avec ma propre réponse.
wcarhart
@Pikalek Oui, je pense que la question que vous avez liée est un doublon. Aurais-je simplement utiliser le plan xz comme zone pour la "carte des étoiles", comme dans l'autre question?
wcarhart
Oui, utilisez le plan xz dans votre cas. En outre, utilisez treeTrunkGirthau lieu d'une constante pour déterminer la distance minimale pour placer un arbre s'ils doivent varier.
Pikalek
@Pikalek Si vous ajoutez tout cela dans une réponse, je la sélectionnerai comme la meilleure. Merci pour l'aide.
wcarhart

Réponses:

15

Une distribution d' échantillonnage Poisson-Disk vous permettra de sélectionner des points aléatoires à une distance minimale. Votre situation est similaire à cette question , mais comme vos arbres ne sont pas des points idéalisés, vous devrez modifier la vérification de la distance comme suit: la distance entre un nouvel arbre potentiel et un arbre existant doit être inférieure à la somme de leurs rayons .

L'algorithme de Bridson peut résoudre efficacement le problème dans O (n), mais il peut être un peu fastidieux de le régler pour des distances variables. Si vos paramètres sont faibles et / ou si vous précalculez votre terrain, une solution de force brute peut également vous être utile. Voici un exemple de code qui force le problème en vérifiant chaque nouveau placement d'arbre potentiel par rapport à tous les arbres placés précédemment:

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

Avec les paramètres suivants:

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

J'ai pu placer et rendre au hasard entre 400 et 450 arbres en moins d'une seconde. Voici un exemple: entrez la description de l'image ici

Pikalek
la source
S'agit-il d'un échantillonnage de disque de Poisson?
wcarhart
Oui, j'ai édité pour rendre cela explicite.
Pikalek
Essayez d'utiliser math.pow sur tree.r + other tree.r, 2, au lieu de math.sqrt, sqrt est généralement plus lent que pow
Ferrybig
1
@Ferrybig La comparaison des distances au carré est plus rapide, mais cela ne change pas le fait qu'il s'agit d'un algorithme de force brute et sera toujours O (n ^ 2). Si une solution plus rapide est requise, utilisez l'algorithme de Bridson. De plus, l'utilisation Math.pow(x,2)n'est pas nécessairement meilleure / différente que l'utilisation x*xcomme indiqué ici .
Pikalek
1
J'ai eu un problème similaire avec le terrain et assurant une répartition décente et aucun chevauchement. J'avais en fait fait une variation, dans ma version les tress / brush sont répartis aléatoirement sur toute la surface du terrain. J'ai ensuite exécuté une fonction post-this pour vérifier les distances de chaque élément les uns par rapport aux autres, où ils étaient trop proches, je les ai écartés. Cependant, cela affectera peut-être d'autres arbres de la région. J'ai répété cela jusqu'à ce que je n'aie pas eu de collisions. c'est plus lent mais ce que j'avais aussi en bonus, c'était des choses comme les clairières (pas partout couvert!) et la densité des arbres semblaient plus "intéressantes".
ErnieDingo