10
\$\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\$
  • 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 '16 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 '16 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 '16 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 '16 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 '16 at 21:04
14
+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\$
  • \$\begingroup\$ Is this using Poisson disk sampling? \$\endgroup\$ – wcarhart Sep 10 '16 at 14:17
  • \$\begingroup\$ Yes, I've edited to make that explicit. \$\endgroup\$ – Pikalek Sep 10 '16 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 '16 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 '16 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 '19 at 21:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.