Object Clustering 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?

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.

I have to stop and give credit to Andrew Willmott and the team at Maxis, who contributed the Halton Sequence algorithm and many other great ideas from Spore to Sigraph in 2007. Their papers and videos can be found here. Spore is one of those rare games that really pushed the envelope of what's possible with procedurally-generated content and art-minded engineering.

This worked great, but my objects are fairly large, not like the grass and shrubs that Andrew was placing on the terrain in Spore. On my landscape, this tended to produce a "noise" of objects, and didn't allow enough space for movement in between them.

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.

As any engineer who wants to prototype something visual will do, I pulled up my copy of Processing and started mocking something up. I can't include Applets in Gamasutra blogs, so you can see the demo in action and get the source code on my blog here.

For each run, this applet iterates a hundred times before the circles come to rest in an optimal packing. It works very much like spring/particle physics systems, using relaxation - moving objects around repeatedly, until they finally reach an equilibrium. Each cycle pushes intersecting objects away from one another and then moves the objects closer to the center of the cluster. I want something much faster, and it only needs to work for a small handful of objects.

So I tweaked it a bit and here are the results... Well, again, I can't include Applets in Gamasutra, so you can see the final prototype in action and get the source code on my blog here.

In this new prototype, the circles are sorted by size such that the relaxation algorithm tends push the smaller ones to the outside, which is what I want. A cluster like this would then be created for each of the first handful of Halton Sequence coordinates, which will space them at a good distance appart from one another.

I'll post images of the results on my blog at a later date.
 
Follow the blog at www.stuartdenman.com