One of the cool 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. More on that in a later post. 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 some of the sketches 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. Here’s my first attempt below. Wait for the circles to appear below in the Java Applet box (give it permission to run first!), then click on the box and press SPACE to generate a new cluster of objects.
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.
Here is my final prototype, which only spawns between 3-7 objects and goes through a mere 10 iterations before stopping:
The circles are sorted in the code 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 at a later date.