August 29, 2014
Press Releases
August 29, 2014
PR Newswire
View All
View All     Submit Event

If you enjoy reading this site, you might also want to check out these UBM Tech sites:

Object Clustering Using Circle Packing
by Stuart Denman on 04/03/12 08:00:00 am

The following blog post, unless otherwise noted, was written by a member of Gamasutra’s community.
The thoughts and opinions expressed are those of the writer and not Gamasutra or its parent company.

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.

### Related Jobs

Insomniac Games — Burbank , California, United States
[08.29.14]

Senior Engine Programmer
[08.29.14]

3D Application Programmer
Glu Mobile — Bellevue, Washington, United States
[08.29.14]

Nexon America, Inc. — El Segundo , California, United States
[08.29.14]

Front-End Developer

 Gerald Belman
 It's good to know that there is weird free software out there like a "Circle Packing Algorithm". You'll have to tell us how you export the circles data into a modeling program. Does Processing allow you to export in a standard modeling format? Once you get the circles into a modeling program I'm sure you could use some form of mass extrusion on all of them. I'm sure their is a way to do this procedurally using a modelling tool. For example in blender, you could extrude all the circles upward to form cylinders - and then you could put creases on the base vertices/edges to prevent them from being affected by subsurf. Then you could subsurf all the cylinders. This would give you a nice rounded(or pointed) shape at the top and keep the base radius the same. It would probably even give you heights that are a factor of the radius of base of the stalks. I'm sure your well on you way to converting the circles to 3d models, but it's an interesting problem. Definitly want to see the final results.

 Stuart Denman
 In my case, Processing is just a prototyping language. Once I prove the algorithm is fast and produces nice results in the 2D prototype, I move the code to C++ and use the circle packing to cluster the objects in my 3D world. All this means is picking a center point and then positioning 3D meshes on the terrain relative to that point, according to the results of the circle packing. I use an instance-renderer to draw them in real-time using prebuilt meshes, such as a pointy rock mesh in my sketch.

 Gerald Belman
Ok, I understand. It's more about the placement and distribution of premade models than it is about the creation of premade models. Your way ahead of me. Procedural stuff is cool. Especially for people who's programming skills outclass their art skills (take minecraft for example) or for people who's programming skills make up for a lack of time to spend on art.

Unfortunately, for people who have a low amount of both programming and art skill (take myself for example) we are forced to just crappily do one or the other. Yesterday, I finished modeling what was supposed to be an overweight human female I have been working on for a few days - and I'm looking at it - and I realize that it looks like a damn teletubby. It's got a big creepy smile and ridiculously short arms - the head's way too damn big and round. Art for me is "not so much good" as my slovakian friend would say.

 Stuart Denman
 What will help a lot on the art side is just drawing on paper first. Do 5-10 sketches of the thing before you attempt anything in 3D. Practice makes perfect, both in art and programming.

 Joshua Darlington
Have you tried looking at biology or ecology to see what mathmatical models they use?

 Stuart Denman
 No, but interesting direction to look into for similar problems in the future. Cellular automata certainly derived from biological ideas, but these are not very efficient to calculate. Once I find something simple that solves my problem, looks good and has optimal performance, I tend to stop looking. :-( I wonder if there might be some biological systems that are good for procedural mesh generation?

 none Comment: