Featured Blog | This community-written post highlights the best of what the game industry has to offer. Read more like it on the Game Developer Blogs or learn how to Submit Your Own Blog Post
Introducing an efficient and attractive method for procedural placement of organic objects in a game world using circle packing.
One of the problems I'm working on now is object distribution/spawning in my 3D game world. For some background, the game world I'm building is, in theory, endless in each of the cardinal directions. The game builds terrain patches on-the-fly, procedurally, as the player moves around the world. Placed onto the terrain are objects, of a mostly decorative sort, whose purpose is to make the world look friendly and, well, occupied.
So how does one go about determining where to place these objects once you've rented a spot to put them from your game engine?
Halton Distribution
The first thing I tried is a pseudo-random distribution using coordinates generated from two Halton sequences. Sounds scary, but really these are just a progression of "random-like" values in the range of 0 to 1 that cycle, depending on what radix (or numerical base) you choose. I am using base 2 for X and base 3 for Y. The great thing about this algorithm is that it produces a nice uniform distribution in the range of [0,1] horizontally and vertically (see image on right). This fits nicely next to another patch of terrain, like a puzzle piece. The algorithm avoids overlapping objects just by the elegant nature of the numerical sequences.
A Clustering of Rocks
I decided that I needed to try clustering the objects. Then I could maintain the same count of objects, but create a look that was a bit more artistic and intentional. As an example of what I was going for, check out the sketch on this page. I spent about a day thinking about how to do this, then after a good night's sleep, I realized that this could be solved with a simple circle-packing algorithm. Each circle represents the "personal space" of an object in a cluster from a top-down perspective.
Read more about:
Featured BlogsYou May Also Like
.png?width=300&auto=webp&quality=80&disable=upscale)
