Evenly distributing trees on terrain

I was recently trying to write algorithm, which would distribute trees (and some other objects) evenly on the terrain. I used nearest neighbour checking conditions - if NN is more far away from the point, which I am checking, than critical distance, then put the tree there. If NN is more close than critical distance, don’t place tree and re-roll random position point. This simple approach allows to distribute trees quite nicely.

However, than going to higher densities, failures (non-suitable points, which needs re-rolling) are increasing dramatically, or in other words it needs much longer times to cover terrain nicely. Are there some well known better algorithms, which would distribute points evenly (at least in Vector2 plane at the beginning)?

I wrote a script that I’ll try to find. I used it for randomly generating any sort of forest (Dense or thin).

I attached a rigidbody with a very high mass (~2000) to the very bottom of the tree, and also attached a trigger collider (I used capsule but I’m sure box would work just as well for low density). The rigidbody keeps the tree upright, but also lets it take the angle of the terrain.

Then, I used a for loop to generate trees at a random location between 0,0 (or your chosen starting Vector2) and 100,100 (or your ending vector2). Now, I dropped the trees at a height of about 20 above the highest hill in my terrain. This may vary for you, but I’m sure you can come up with some code that will check the highest point and add 20.

I added a tree script that, after 10 seconds, checked to see if it was colliding with a couple of things. (Mainly rocks, other trees, water, etc.) If it was, it moved itself to the edge of the map and waited to be “respawned” (or in this case, repositioned). Provided it wasn’t colliding with anything, I then set the rigidbody to Kinematic so that it didn’t move. I also checked the rotation to make sure it was relatively upright. If not, I reset the position to (0,0,0).

I also added a terrain detection script which got the dominant texture underneath the tree. This would let the tree know what sort of soil it was under, which can either tell the tree script to reposition it (if it’s on stone, gravel, places a tree wouldn’t normally grow) or to change the tree type (swamp terrain? swamp tree. Forest terrain? Pine tree).

Hope this gives you some good ideas! It may not be the most efficient way, but it certainly worked for me, and this was all done in around 10 seconds while the scene loaded.