过去的几周里，我一直在努力做服务端方面的工作。有很多项目都在进行中，特别是群集构架。但其中最有意思的一部分是星系过程生成器。在这一辑中，我将与大家探讨生成这些恒星的运算法则和各种我做过的用来测试这个星系生成器的性能/内存实验。
概览
注意：文末有视频！
我们的星系——银河，由大约一千到四千亿的恒星组成。你可以想象，通过预运算来生成它们是不可能完成的任务。星系过程生成器必须要能够在“感兴趣的区域”——通常是在玩家（或者NPC，亦或有事件发生的恒星系）周围，生成恒星数据。
跃迁系统允许玩家选择跃迁至任何恒星，远近不是问题，重要的是目标的质量和相对的距离。让我们用一个简单的线性公式打个比方，成功跃迁到一个地方的可能性为M/D的函数（M是目标质量，D为距离）。当然，“真实”的公式要远比这复杂，而且不是线性的，这里暂且不管它。
根据这个简单的公式，一个10光年远、1单位质量的恒星与一个100光年远、10单位质量的恒星相比，跃迁成功的概率是一样的……
恒星的质量（对于那些在他们主星序的恒星而言）也就意味着它们的颜色。质量比太阳大很多倍的恒星是蓝色；跟太阳差不多的是白或黄色；低质量的的恒星偏暗红，也就是红矮星。
这些跟星系生成器有什么关系呢？呃……这些定义了它的基本约束条件：生成器必须是分层的。换句话说，大质量蓝色恒星即使很远也必须生成，同时较轻的红矮星只需要在距玩家较近的区域生成。
如果你对前面所说的还不太理解，反复去读，直到你完全理解了，因为这很重要！远处的红矮星根本不会被生成。它们不但不会被显示，而且根本不存在于内存中，自然也就不占内存了。更微妙的是，除非你“物理上”接近它们，否则你无论如何也看不到它。这也暗示了你将无法通过一个名称来搜索一个恒星，除非它是一个储存在数据库中的“特殊”恒星。
生成星系的点阵
算法基于八叉树。还记得刚才所说的恒星必须分层的生成吗？当达到最大深度层（12）时，玩家周围的八叉树细分进行递归运算。八叉树的每个结点都有一个深度层（从0算起），每个递归层增加1（所以最大值为12）。此深度层很重要，因为它决定了在那个结点上生成的恒星的类型。
这个层被用作一个概率表的索引。这个表储存了不同深度的各种恒星类型的分布概率。比如说根节点（第0层），有40%的可能性生成O类（蓝热）恒星，40%的可能生成B类恒星，还有20%的可能生成A类恒星。
这样一来，就能够让算法均衡的去生成各类恒星。
每一个节点恒星的潜在数目只是深度层值的一个函数。在根层，有五千万颗恒星。在最深的层（第12），有200颗恒星。注意，真正生成的恒星数量将比这要少，因为恒星要通过一个减密测试(decimation test)。也就是根据一个密度函数来塑造星系形状。
密度函数就是通过输入一些星系内的3D坐标，然后返回一个0到1之间的概率，看这个坐标上的恒星是否存在。
为了生成球状环，需要算出距离星系中心的距离，并带入一个倒幂指数（通过一些参数来控制形状）。
为了生成旋臂，需要从一个“密度图”上查询概率（类似灰度高度图）。然后2D坐标和距星系平面的距离被用来决定密度。
为了生成球状簇，计算与球状环类似，除了每个簇有一个非零起点和一个大约几十光年的半径。
最终的密度函数为这些密度的最大值。
为了生成给定节点的恒星，在节点范围内为每一个潜在的恒星生成一个随机3D坐标。估算这一位置的密度，然后生成一个随机数，如果这个数字低于密度，便生成恒星并被储存在节点中。
当节点递归分成8个子节点，来自父节点所有恒星再正确的分布到子节点中（通过坐标选择）。
提醒一下，所有的节点被作为“种子”分配，并且当一个节点再细分了，每个子代又产生了一个新的种子。当需要随机数产生时这个种子被多处使用。因此，玩家离开时，节点合并；玩家回来时，节点分裂，完全相同的恒星又会生成。它们会有完全相同的地点、颜色、类型等等……
过程生成的缺点是任何对运算规则参数的改变（比如每个节点恒星的数量，或者概率表）都将导致一个完全不同的星系。所有的恒星位置都将与之前不同（也可能有，但那只是巧合）。因此所有的概率和参数最好在游戏发布前正确的矫正，否则将导致世界毁灭、重生……
性能考虑
上面所描述的算法有个性能问题。原因很简单：如果一个给定的节点有1000颗潜在的恒星，那么你需要生成1000组坐标，并通过密度函数逐一测试，以确定是否要生成一颗恒星。
我马上意识到，在终端节点上密度很低。想想一个100X100X100光年的立方体位于星系环上，远离中心：这个体积上的密度函数将很连续，并很低（我算过了，大约10%）。这意味着对于1000个潜在的恒星，这个算法将生成1000个坐标，评估1000次，10%的候选者通过测试，最终得到100个恒星。会不会仅生成100个候选者好一些呢？这将快10倍啊！
幸运的是，可以用一个简单的方法。假定密度函数在一定体积上是相对一致的：10%。统计学上，生成1000个恒星再十里挑一与生成100个恒星再十里挑十是一样的。换句话说，当密度一致时，你可以通过正确的比率（1/密度）简单的减少恒星的数量，或者说，恒星的数量乘以密度！1000恒星 * 10% = 100恒星。
大多数时候，密度并不一致。节点的深度层越低，体积越大，一定体积上的密度一致性也就越低。但即使密度不一致，你仍然能用最大的可能性去减少潜在候选者的数量。
让我们选定一个有1000个候选者的节点，这里一个角落里有1%的密度，另一个角落有20%的密度（最大值）。在统计学上这依然与一个具有200个候选者（1000X20%），而一个角落有5%的密度，另一个角落有100%的密度的节点相同。
如你所见，不可能用密度公式评估每一个候选者，但候选者的数量减少到了原来的五分之一，同时密度函数的概率增加五倍。更少的行星，更高的测试通过的概率：双赢！
内存考虑
到这里为止，我已经解释了如何生成星系模型，并且恒星是如何在没有预运算的情况下即时分布的。但记住算法主要在服务器运行，并且不可能只有一个玩家，而是成千上万。在这么多视点下星系生成是如何工作的呢？
简而言之，我修改了标准的八叉树算法，当需要时才分裂，只到内存不足时才进行节点归并。
星系管理器作为一个“近期使用最少”(LRU)缓存。恒星数据和节点消耗内存。当目标内存预算达到后，一个“垃圾收集器”例行程序启动。这个例行程序检查所有节点并确定哪些节点最近被使用最少（也就是说：这些节点很久以前生成，但到现在为止从未被使用）。然后这些节点归并，释放内存。
对多人状况下的性能和内存负载测试有点复杂，因为很大程度上取决于玩家在星系的哪些位置。最糟糕的情况可能是玩家随机的分布于星系中，相互都距离很远。但是有根据的猜想一下，我不认为这会是玩家们真实的行为模式：大多数的玩家会趋向于集中在核心周围，或相互聚集，组成一些组织。但即使那样，我们能确定90%的玩家会在距离核心1000光年以内吗？在公测前可能估计得到吗？
星系地图的考量
我注意到玩家们关于星系地图的有趣建议，还有星图应该是什么样子。但是测试了星系生成器后，我得出结论，所有人都严重的低估了你周围恒星的数量。比如，100光年的半径内，平均密度的旋臂上，有5000个恒星不是什么奇怪的事。
记住跃迁引擎不限制半径。或者更确切的说，距离只是一个参考因素，而没有上限。这表示跃迁至5000光年远的红矮星还是有可能的，不过成功的概率很低（高于赢彩票），但不是0。当然，对于星图来说，这说明再远的恒星也应该被显示（如果你没过滤掉他们的话）。你的地图上将出现多到令人发疯的点……
一种更有效的过滤，我想，是跃迁可能性过滤。也就是这样：只显示跃迁成功率50%以上的恒星。
下面的截图中，你可以看到带网格的蓝色球体，定义了恒星显示的范围。这只是个实验，为了让人们认识到在一定范围内有多少恒星：但这绝不是将来星图的样子（另外，这些都是在服务器上！）
我能通过按一个键选定任一恒星，并粉红色高亮。在左上方，你可以看到一些有关选定的恒星的信息：第一项是一个独一无二的数字，它表明了它在星系中的“地址”。下一行，这三个值是恒星相对星系中心的XYZ坐标。接着，恒星的类，距离，最后是跃迁成功概率。
接下来的几周，我可能会将星系算法转移到客户端，在恒星或尘埃上加入一些体积/粒子特效来美化它们。算法也将运行于客户端的原因是为了避免玩家每次打开星图时不得不将上百万的坐标从服务器转移到客户端。那对我们的带宽是很悲哀的……
视频
高清视频下载720P(58.27MB)：
http://www.infinity-game.com/fil … me_galaxy_model.mp4
（服务端测试，没有进行任何渲染处理，仅为色点。在游戏中每个点都将是一个可探索恒星系！）
在线播放：（高清）
可以翻墙的看这个：http://www.youtube.com/watch?v=P0-lsyo28SU
不能翻墙的看这个：http://www.vimeo.com/4733711
非高清：
http://player.youku.com/player.php/sid/XOTI2OTQ3MTY=/v.swf
文章翻译：persionmoon1，润色校对：Infinity汉化组 lalgai
原文链接：http://www.infinity-universe.com/Infinity/index.php?option=com_content&task=view&id=106&Itemid=27