Como colocar aleatoriamente entidades que não se sobrepõem?

11

Estou criando um ambiente gerado aleatoriamente para um jogo que estou desenvolvendo. Estou usando OpenGLe codificando Java.

Estou tentando colocar aleatoriamente árvores no meu mundo (para criar uma floresta), mas não quero que os modelos se sobreponham (o que acontece quando duas árvores são colocadas muito próximas uma da outra). Aqui está uma imagem do que estou falando:

insira a descrição da imagem aqui

Posso fornecer mais código, se necessário, mas aqui estão os trechos essenciais. Estou armazenando meus objetos em um ArrayListcom List<Entity> entities = new ArrayList<Entity>();. Estou adicionando a essa 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);
}

em que cada um Entitysegue a seguinte sintaxe:

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

rotXé a rotação ao longo do eixo x, e scaleXé a escala na direção x, etc.

Você pode ver que eu estou colocando estas árvores aleatoriamente com random.nextFloat()os xe zposições, e delimita o intervalo para as árvores aparecerá no local desejado. No entanto, eu gostaria de controlar de alguma forma essas posições, para que, se tentar colocar uma árvore muito perto de uma árvore anteriormente colocada, recalcule uma nova posição aleatória. Eu estava pensando que cada árvore Entitypoderia ter outro campo, como treeTrunkGirth, e se uma árvore for colocada à distância entre a localização de outra árvore e ela treeTrunkGirth, ela recalculará uma nova posição. Existe uma maneira de conseguir isso?

É um prazer adicionar mais trechos de código e detalhes conforme necessário.

wcarhart
fonte
3
Amostragem de disco de Poisson deve fazer o trabalho. Não sei se é melhor para isso e nunca realmente o implementou / usou, mas parece pelo menos como um bom começo. Confira este artigo: devmag.org.za/2009/05/03/poisson-disk-sampling
Marte
@ Mark Wow, esse link é super útil, obrigado. Vou ver o que posso fazer e talvez voltar com uma resposta minha.
wcarhart 8/09/16
@Pikalek Sim, acho que a pergunta que você vinculou é uma duplicata. Eu usaria o plano xz como área para o "mapa estelar", como na outra pergunta?
wcarhart 8/09/16
Sim, use o plano xz no seu caso. Além disso, use em treeTrunkGirthvez de uma constante para determinar a distância mínima para colocar uma árvore, se ela precisar variar.
Pikalek 8/09/16
@Pikalek Se você adicionar tudo isso em uma resposta, selecionarei a melhor. Obrigado pela ajuda.
wcarhart 8/09/16

Respostas:

15

Uma distribuição de amostragem Poisson-Disk permitirá que você selecione pontos aleatórios a uma distância mínima. Sua situação é semelhante a esta pergunta , mas como suas árvores não são pontos idealizados, você precisará alterar a verificação da distância da seguinte maneira: a distância entre uma nova árvore em potencial e uma árvore existente deve ser menor que a soma dos raios .

O algoritmo de Bridson pode resolver com eficiência o problema em O (n), mas pode ser um pouco complicado ajustá-lo para distâncias variáveis. Se seus parâmetros são baixos e / ou você está pré-computando seu terreno, uma solução de força bruta também pode atendê-lo. Aqui está um código de exemplo que força bruta o problema, verificando cada nova colocação potencial de árvore em relação a todas as árvores colocadas 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;
}

Com os seguintes parâmetros:

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

Consegui colocar e renderizar aleatoriamente entre 400-450 árvores em menos de um segundo. Aqui está um exemplo: insira a descrição da imagem aqui

Pikalek
fonte
Isso está usando amostragem de disco Poisson?
Wcarhart
Sim, editei para tornar isso explícito.
Pikalek
Tente usar math.pow em tree.r + other tree.r, 2, em vez de Math.sqrt, sqrt é geralmente mais lento do que pow
Ferrybig
1
@Ferrybig A comparação de distâncias quadradas é mais rápida, mas isso não muda o fato de que é um algoritmo de força bruta e ainda será O (n ^ 2). Se uma solução mais rápida for necessária, use o algoritmo de Bridson. Além disso, usar Math.pow(x,2)não é necessariamente melhor / diferente do que usar x*xcomo discutido aqui .
Pikalek 18/09/16
1
Eu tive um problema semelhante com o terreno e garanti uma propagação decente e nenhuma sobreposição. Na verdade, eu havia feito uma variação. Na minha versão, as árvores são espalhadas aleatoriamente pela área do terreno. Em seguida, executo uma função postar isso para verificar as distâncias de cada item um contra o outro, onde eles estavam muito próximos, eu os afastei. Isso, porém, poderá afetar outras árvores da região. Repeti isso até não ter colisões. é mais lento, mas o que eu também tinha como bônus eram coisas como clareiras (nem todos os lugares são cobertos!) e a densidade das árvores parecia mais "interessante".
ErnieDingo 18/02/19