12
\$\begingroup\$

I am creating a randomly-generated environment for a game I'm developing. I am using OpenGL and coding in Java.

I am trying to randomly place trees in my world (to create a forest), but I don't want the models to overlap (which happens when two trees are placed too close to each other). Here's a picture of what I'm talking about:

enter image description here

I can provide more code if necessary, but here's the essential snippets. I am storing my objects in an ArrayList with List<Entity> entities = new ArrayList<Entity>();. I am then adding to that list using:

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

where each Entity follows the following syntax:

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

rotX is the rotation along the x-axis, and scaleX is the scale in the x-direction, etc.

You can see that I am placing these trees randomly with random.nextFloat() for the x and z positions, and bounding the range so the trees will appear in the desired location. However, I would like to somehow control these positions, so that if it tries to place a tree too close to a previously placed tree, it will recalculate a new random position. I was thinking that each tree Entity could have another field, such as treeTrunkGirth, and if a tree is placed in the distance between another tree's location and it's treeTrunkGirth, then it will recalculate a new position. Is there a way to accomplish this?

I am happy to add more code snippets and details as necessary.

\$\endgroup\$
5
  • 3
    \$\begingroup\$ Poisson disk sampling should do the work. Don't know if it's best for this and never really implemented/used it, but seems at least as a good start. Check this article: devmag.org.za/2009/05/03/poisson-disk-sampling \$\endgroup\$
    – Mars
    Sep 8, 2016 at 19:12
  • \$\begingroup\$ @Mars Wow, that link is super helpful, thanks. I'll see what I can do, and maybe come back with an answer of my own. \$\endgroup\$
    – wcarhart
    Sep 8, 2016 at 19:17
  • \$\begingroup\$ @Pikalek Yes, I think that question you linked is a duplicate. Would I just use the xz-plane as the area for the "star map," like in the other question? \$\endgroup\$
    – wcarhart
    Sep 8, 2016 at 19:38
  • \$\begingroup\$ Yes, use the xz plane in your case. Also, use treeTrunkGirth instead of a constant to determine the min distance for placing a tree if they need to vary. \$\endgroup\$
    – Pikalek
    Sep 8, 2016 at 21:02
  • \$\begingroup\$ @Pikalek If you add all that up in an answer, I'll select it as the best one. Thanks for the help. \$\endgroup\$
    – wcarhart
    Sep 8, 2016 at 21:04

1 Answer 1

15
+200
\$\begingroup\$

A Poisson-Disk sampling distribution will allow you to select random points a minimum distance apart. Your situation is similar to this question, but since your trees aren't idealized points you'll need to change the distance checking as follows: the distance between a potential new tree & an existing tree, must be less than the sum of their radii.

Bridson's algorithm can efficiently solve the problem in O(n), but it can be a bit fiddly to tweak it for variable distances. If your parameters are lowish &/or you are precomputing your terrain, a brute force solution may serve you just as well. Here's some sample code that brute forces the problem by checking every potential new tree placement against all prior placed trees:

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

With the following parameters:

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

I was able to randomly place & render between 400-450 trees in under a second. Here's an example: enter image description here

\$\endgroup\$
6
  • \$\begingroup\$ Is this using Poisson disk sampling? \$\endgroup\$
    – wcarhart
    Sep 10, 2016 at 14:17
  • \$\begingroup\$ Yes, I've edited to make that explicit. \$\endgroup\$
    – Pikalek
    Sep 10, 2016 at 15:23
  • \$\begingroup\$ Try to use math.pow on tree.r + other tree.r,2, instead of math.sqrt, sqrt is usually slower than pow \$\endgroup\$
    – Ferrybig
    Sep 18, 2016 at 10:21
  • 1
    \$\begingroup\$ @Ferrybig Comparing squared distances is faster, but that doesn't change the fact that it's a brute force algorithm & will still be O(n^2). If a faster solution is required, use Bridson's algorithm. Also, using Math.pow(x,2) isn't necessarily any better/different than using x*x as discussed here. \$\endgroup\$
    – Pikalek
    Sep 18, 2016 at 14:36
  • 1
    \$\begingroup\$ I've had a similar issue with terrain and ensuring some decent spread and no overlap. I had actually done a variation, in my version the tress/brush are randomly spread across the terrain area. I then run an function post this to check the distances of every item against each other, where they were too close I pushed them apart. This though will impinge possibly on other trees in the area. I repeated this until I had no collisions. it's slower but what I also had as a bonus were things such as clearings (not everywhere is covered!) and tree density seemed more "interesting". \$\endgroup\$
    – ErnieDingo
    Feb 18, 2019 at 21:11

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .