作者：Stuart Denman

目前我正在处理的问题是3D游戏世界中的对象分布和产生。从理论上来说，我正在构建的游戏世界的每个主方向都是无限的。随着玩家在世界中移动，游戏不断构建地形patch。地形上呈现的对象主要是发挥装饰作用，其存在的目标是使世界看起来更加具体而充实。

那么，要如何决定这些对象在地形中的位置呢？

Halton Sequence(from stuartdenman)

我首先尝试的是使用两个Halton序列生成坐标的伪随机分布方法。听起来感觉很怪异，但这确实是“类随机”值生成的过程，数值在0到1的范围内变动，这取决于你选择的数值基础。我使用2作为X的数值基础，3作为Y的数值基础。这种运算法则的好处在于，它创造横纵轴范围为[0,1]的一致分布。这与地形的其他patch很契合，比如谜题片段。通过这种数值序列，该运算法则能够避免重叠对象的出现。

我不得不感谢Andrew Willmott及其位于Maxis的团队，他们致力于Halton Sequence运算法则和许多其他绝妙的想法，将其运用于《孢子》和《Sigraph》等游戏中。你可以在网络上找到与他们有关的文章和视频。《孢子》是款罕见的游戏，它让人们看到程序生成内容和艺术化工程的潜力。

这种方法的效果确实很不错，但我的对象相当大，不像Andrew在《孢子》中添加的草和灌木。采用这种方法会让我的地形上布满各种各样的对象，从而导致游戏中没有足够的移动空间。

我觉得，我需要尝试将对象集中起来。这样，我能够在维持对象数量不变的前提下，营造出更具艺术性和国际化的视觉效果。我花了一天的时间来思考如何实现，睡过一觉后，我意识到使用简单的circle packing运算法则便可以解决这个问题。用圆圈来代表对象的“个体空间”。

正如所有构建对象视觉效果原型的工程师那样，我开始仿制原型（游戏邦注：作者无法在Gamasutra博文中添加Applet，但已将动作效果和源代码发布到其个人博客上）。

circles(from gamasutra)

在每次运行中，这个applet都会重复上百次，随后圆圈停止在某个地方。它的效果很像spring/particle physics系统，使用relaxation重复移动对象直到他们最终达到平衡。每个圆圈都会将对象相互远离，然后令对象向集中点靠近。我希望这个过程能够更快，而且它只需要处理少数对象即可。

所以我对其进行了些许修改，以下便是得到的结果。

iteration(from gamasutra)

在这个新原型中，圆圈以大小进行分类，这样relaxation算法就会将小圆圈向外推，这正是我想要的结果。对于为数不多的Halton Sequence坐标都会出现对应的集中效果，这样它们之间就能够保持一定的距离。

游戏邦注：本文发稿于2012年4月3日，所涉时间、事件和数据均以此为准。（本文为游戏邦/gamerboom.com编译，拒绝任何不保留版权的转载，如需转载请联系：游戏邦）

Object Clustering Using Circle Packing

Stuart Denman

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. (Source: Gamasutra)