In my current game project, I recently ran into a bit of a snag. I needed a way to generate a natural looking distribution of trees, as my current method of randomly placing them within a disk wasn't working out too well. This article means to quickly discuss my attempted methods of tree placement, as well as the solution to my troubles: Poisson disk sampling.
As mentioned above, the first method I tried was simply random placement within a disk. The image below shows this in action.
It doesn't look too good. It's easy to keep trees from spawning on top of each other(I just check that the position is clear before placing a tree), but that still doesn't solve the issue of the painfully non-uniform placement. Some trees are bunched up right next to each other, and other trees are spaced out too much. It doesn't look as natural as I'd like. I had to go back to the drawing board.
After that experiment, I went off on a bit of a tangent, and ended up writing an entire implementation of Perlin noise generation. Using this, I generated some noise, then placed the trees in a grid like fashion. As a finishing touch, I added small, random, offsets to help make them look more naturally placed. As you can see in the image below, It ended up working quite well.
However, it was a little bit too uniform for my taste. I was ending up with a "blocky" forest. It seems to me that Perlin noise is much more suited towards terrain generation than individual tree placement. Alas, it was a fun experiment.
Poisson Disk Sampling
Poisson disk sampling isn't terribly difficult to implement. Below is an image of the implementation in action.
Poisson disk sampling(or distribution) is similiar to random placement, however a certain level of uniformity is enforced. Sample points that are generated cannot be too close or too far from each other, and they are generated within the annulus around a certain point in the sample set, which will be explained a little bit more below. As you can see, this method produced a nice, natural, dense forest, which is just what I wanted. The most simple form of the implementation is pretty much as follows:
1. Choose an initial point, and add it to an output list and a processing list. 2. While the processing list still has points to be processed: a. Pop an "origin" point off the back of the processing list. b. For this point, generate k sample points within the annulus around it. c. For each generated point: I. Check for other points near this point. II. If the area around this point is clear, add it to the output list and the processing list. 3. Return the output list.
I can easily tweak the distribution as well, just by changing the inner and outer radius of the annulus, and also by changing k, the number of sample points to process per point. 30 is a good number, and results in dense distributions.
Now this version, while easy to implement, is not very optimized at all. The "true" way to implement Poisson distribution is to break up the sample zone(in my case, the entire game map) into equal sized cells, where each cell contains, at most, one sample point. Then, when checking for surrounding points(step I in the above walkthrough), you only have to investigate the surrounding cells, rather than every single sample point in the output. This optimization results in a rather large speed boost.
After some experimentation, it seems like Poisson Disk sampling is currently the best way for me to generate forests for my project. In fact, I will probably end up using this same method for some other sort of uniform distribution in the future. Upon further thought, however, I have realized that a mixture of Perlin noise and Poisson sampling could be extremely powerful, as you would get the natural "forest area" generation from the Perlin, and the natural distribution from the Poission sampling. Maybe one day I will give it a shot.
If you want more alot more information and examples of this method, check out this article by Herman Tulleken, as it was the inspiration and guide for my personal implementation.