gamerboom.com订阅到鲜果订阅到抓虾google reader订阅到有道订阅到QQ邮箱订阅到帮看

阐述使用circle packing运算法则集中对象的方法

发布时间:2012-04-13 10:51:51 Tags:,,

作者:Stuart Denman



Halton Sequence(from stuartdenman)

Halton Sequence(from stuartdenman)


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


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


circles(from gamasutra)

circles(from gamasutra)

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


iteration(from gamasutra)

iteration(from gamasutra)

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


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)