¿Cómo colocar al azar entidades que no se superponen?

11

Estoy creando un entorno generado aleatoriamente para un juego que estoy desarrollando. Estoy usando OpenGLy codificando Java.

Estoy tratando de colocar árboles al azar en mi mundo (para crear un bosque), pero no quiero que los modelos se superpongan (lo que sucede cuando dos árboles se colocan demasiado cerca el uno del otro). Aquí hay una foto de lo que estoy hablando:

ingrese la descripción de la imagen aquí

Puedo proporcionar más código si es necesario, pero aquí están los fragmentos esenciales. Estoy almacenando mis objetos en un ArrayListcon List<Entity> entities = new ArrayList<Entity>();. Luego estoy agregando a esa lista usando:

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

donde cada uno Entitysigue la siguiente sintaxis:

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

rotXes la rotación a lo largo del eje xy scaleXes la escala en la dirección x, etc.

Se puede ver que estoy colocando estos árboles al azar con random.nextFloat()los xy las zposiciones, y que limita la gama de modo que los árboles van a aparecer en la ubicación deseada. Sin embargo, me gustaría controlar de alguna manera estas posiciones, de modo que si intenta colocar un árbol demasiado cerca de un árbol colocado previamente, volverá a calcular una nueva posición aleatoria. Estaba pensando que cada árbol Entitypodría tener otro campo, como treeTrunkGirth, y si un árbol se coloca en la distancia entre la ubicación de otro árbol y es treeTrunkGirth, entonces volverá a calcular una nueva posición. ¿Hay alguna manera de lograr esto?

Me complace agregar más fragmentos de código y detalles según sea necesario.

wcarhart
fuente
3
El muestreo de disco de Poisson debería hacer el trabajo. No sé si es mejor para esto y nunca lo implementó / usó realmente, pero parece al menos un buen comienzo. Consulte este artículo: devmag.org.za/2009/05/03/poisson-disk-sampling
Mars
@Mars Wow, ese enlace es muy útil, gracias. Veré qué puedo hacer y tal vez vuelva con una respuesta propia.
wcarhart
@Pikalek Sí, creo que esa pregunta que vinculaste es un duplicado. ¿Usaría simplemente el plano xz como el área para el "mapa estelar", como en la otra pregunta?
wcarhart
Sí, use el plano xz en su caso. Además, use en treeTrunkGirthlugar de una constante para determinar la distancia mínima para colocar un árbol si necesita variar.
Pikalek
@Pikalek Si agrega todo eso en una respuesta, lo seleccionaré como el mejor. Gracias por la ayuda.
wcarhart

Respuestas:

15

Una distribución de muestreo de Poisson-Disk le permitirá seleccionar puntos aleatorios a una distancia mínima de distancia. Su situación es similar a esta pregunta , pero dado que sus árboles no son puntos idealizados, deberá cambiar la distancia comprobando de la siguiente manera: la distancia entre un árbol nuevo potencial y un árbol existente, debe ser menor que la suma de sus radios .

El algoritmo de Bridson puede resolver eficientemente el problema en O (n), pero puede ser un poco complicado ajustarlo para distancias variables. Si sus parámetros son bajos y / o está precalculando su terreno, una solución de fuerza bruta también puede servirle. Aquí hay un código de muestra que el bruto fuerza el problema al verificar cada posible colocación de nuevos árboles contra todos los árboles colocados anteriormente:

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

Con los siguientes parámetros:

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

Pude colocar aleatoriamente y renderizar entre 400-450 árboles en menos de un segundo. Aquí hay un ejemplo: ingrese la descripción de la imagen aquí

Pikalek
fuente
¿Está usando el muestreo de disco de Poisson?
wcarhart
Sí, he editado para hacerlo explícito.
Pikalek
Intente usar math.pow on tree.r + other tree.r, 2, en lugar de math.sqrt, sqrt suele ser más lento que pow
Ferrybig
1
@Ferrybig Comparar distancias al cuadrado es más rápido, pero eso no cambia el hecho de que es un algoritmo de fuerza bruta y seguirá siendo O (n ^ 2). Si se requiere una solución más rápida, use el algoritmo de Bridson. Además, usar Math.pow(x,2)no es necesariamente mejor / diferente que usar x*xcomo se discutió aquí .
Pikalek
1
He tenido un problema similar con el terreno y asegurando una extensión decente y sin superposición. Realmente había hecho una variación, en mi versión, el mechón / cepillo se distribuyen aleatoriamente en el área del terreno. Luego ejecuto una función post this para verificar las distancias de cada elemento uno contra el otro, donde estaban demasiado cerca, los separé. Sin embargo, esto afectará posiblemente a otros árboles en el área. Repetí esto hasta que no tuve colisiones. es más lento, pero lo que también tuve como extra fueron cosas como los claros (¡no todos están cubiertos!) y la densidad de los árboles parecía más "interesante".
ErnieDingo