# How to randomly place entities that don't overlap?

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: 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.

• 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 – Mars Sep 8 '16 at 19:12
• @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. – wcarhart Sep 8 '16 at 19:17
• @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? – wcarhart Sep 8 '16 at 19:38
• 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. – Pikalek Sep 8 '16 at 21:02
• @Pikalek If you add all that up in an answer, I'll select it as the best one. Thanks for the help. – wcarhart Sep 8 '16 at 21:04

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

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){
}
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: • Is this using Poisson disk sampling? – wcarhart Sep 10 '16 at 14:17
• Yes, I've edited to make that explicit. – Pikalek Sep 10 '16 at 15:23
• Try to use math.pow on tree.r + other tree.r,2, instead of math.sqrt, sqrt is usually slower than pow – Ferrybig Sep 18 '16 at 10:21
• @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. – Pikalek Sep 18 '16 at 14:36
• 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". – ErnieDingo Feb 18 '19 at 21:11