数学问题：星系的程序生成

Question

我将制作一个完全按程序生成的空间/交易/战斗游戏。 但是，我知道将整个星系的所有细节存储在内存中是不可行的。 因此，我一直认为我可以使用种子来生成太阳系，并且从该太阳系，您可以使用跳跃门前往其他太阳系。 问题是，如果我从起始太阳系跳转到另一个太阳系，我需要能够回到具有完全相同特征（行星、小行星等）的完全相同的起始太阳系。

本质上，我需要能够从一个数字生成整个星系。 从生成一个太阳系的那个数字中，我需要能够生成与第一个太阳系链接的所有其他太阳系以及与这些太阳系链接的所有太阳系，依此类推。 如果我回到它们的话，每个太阳系都必须保持完全相同的特征。 此外，每个太阳系的链接数量可以是随机的，也可以是固定的，由您选择。 不过随机的会更好。

Answer 1

如果你觉得自己很勇敢，你可以比看看 Ian Bell 是如何做到的更糟糕 适用于 Elite 的原始版本

Answer 2

查看 Gamasutra 上的这个系列：

A Real-Time Procedural Universe，前四个链接

另外，这个：无限宇宙的算法

Answer 3

这是我理解的基本想法。 假设你已经到达了 42 号恒星系统，你需要找出里面有什么。 它有 nplanet 行星 - 0 到 10 之间的数字，比如说：

>>> star_system = 42
>>> nplanets = hash('nplanets%d' % star_system) % (10 + 1)
>>> nplanets
4

好的，那么对于 2 号行星，游戏开始时有多少个空间站在轨道上？ 找出 0 到 3 之间的数字：

>>> planet = 2
>>> nstations = hash('nstations%d/%d' % (star_system, planet)) % (3 + 1)
>>> nstations
1

以此类推。 每个数字都是索引（在本例中为#42 恒星系统，#2 行星）的哈希函数，并缩小到适当的范围。 由于哈希函数是确定性但“随机”的，因此每次都是相同的，但对玩家来说是随机的。

当然，对具有长序列（如“nstations”）的字符串进行哈希处理并不是最快的方法，但它展示了这个想法。

Answer 4

看看原始的百战天虫游戏。
我认为它声称有大约 40 亿个可能的级别。
每个级别都是基于大约 20 个字符的短种子字符串生成的。
这决定了

• 关卡的主题（北极、森林等）、
• 景观的形状、
• 地面的光滑程度、
• 预建关卡细节的放置（雪人、岩石……）、
• 蠕虫、地雷团队的放置和武器箱。

如果您喜欢某个关卡，您可以写下种子字符串，并在以后使用它来重新生成相同的关卡。

这是一个非常复杂但确定性函数的示例，具有单个输入参数。 我认为这是您所需要的基本概念。

Answer 5

你不能只对星系 ID 进行 SHA1，例如：

Galaxy 1

Sha1(1) = 356a192b7913b04c54574d18c28d46e6395428ab

Galaxy 2

Sha1(2) = da4b9237bacccdf19c0760cab7aec4a8359010b0

Galaxy 3

Sha1(3) = 77de68daecd823babbb58edb1c8e14d7106e83bb

然后你可以对代码进行分段，即：

前 4 个字符 = 行星数量

356a
da4b
77de

你需要某种字符串到数字的算法，一个简单的算法是获取每个非数字字符的 ASCII 代码，然后将它们全部相乘或执行其他操作。

现在我们知道银河系中有多少颗行星，银河系的 x、y、z 维度又如何呢？

接下来的 9 个字符 = Galaxy Dimensions (x,y,z)

原理同上，将代码变成一个大数。 还要进行一些敏感性检查，您不会想要一个 10 英里 x 10 英里 x 10 英里、其中有 2000 万颗行星的星系。 采用某种加权算法，例如最小大小是行星数 * 10000。您需要使用数字来确保范围全部兼容，并且从哈希中选择的字符实际上为您提供了合理的范围。

或者，您可以使用随机数在星系的最小和最大大小之间选择一个数字，但使用恒定的 RNG 种子，例如星系 ID！ 这样，星系的大小对于观察者来说基本上是“随机的”，但每次都是相同的。

等等等等！

这是获取宇宙属性的一种方法，但是行星属性又如何呢？ 比如人口和其他东西？

如果您的 Galaxy 1 有 20,000 个行星，您可以这样做：

Sha1('1:340') = bc02ab36f163baee2a04cebaed8b141505cc26b5

即 Galaxy 1，行星 340。然后您可以随意拼接该代码。 使用哈希的好处是每个星球都应该有一个完全唯一的代码。

Answer 6

我认为值得注意的是，

1. 为相同输入产生相同随机输出的生成器称为伪随机数生成器，“PRNG”。 通常，您在一开始就给它一个“种子”输入数字，然后从中提取随机数字，调用它而无需进一步输入。 注意：您无法“返回”到较早的数字，至少不能从头开始。

2. 使用坐标作为每次调用的输入来调用的类似 PRNG 的函数通常是“噪声”函数。 在这里，您不会遇到“无法返回”的问题 - 只需再次使用“较早的”输入进行调用即可。
   噪声函数使用 PRNG（作为后端；或者至少可以），它仍然可以在一开始就播种，因此您不会失去“单一数字中的宇宙”功能。

3. 虽然您每次都可以使用 PRNG 并将星系坐标组合到“种子”中，但最多只能得到“白噪声”，而没有其他属性。 噪声函数更适合这项工作，因为可以选择甚至调整它来为您提供可平铺/平滑/螺旋状的外观/等。 结果。
   例如，搜索使用柏林噪声制作的纹理图像。
   我希望您看到，使用相同的噪声函数，您可以创建例如数千个随机云，但是通过根据您的需要（不仅仅是种子或坐标）调整噪声函数，您可能会得到熔岩或星系。 不过，调整它可能并不简单。

4. 每次调用的输入坐标数量决定了噪声函数的维数，因此对于二维贴图（或纹理等），您可以使用二维噪声函数。 然后你每次都像noise2d(x,y)一样调用它。

在你的情况下，我会尝试使用 3 维单纯形噪声函数（单纯形来自柏林噪声的作者，推荐为更好）。

然后，每个恒星系统坐标三元组都会为您提供一个结果编号。 下一个决定是：这个数字代表什么？ 为了充分利用单纯形噪声的平滑功能，我会将较低的数字映射到更空的太阳系，将较高的数字映射到质量更大的系统。
或者，也许更好的是，对于每个系统，使用子坐标多次调用单纯形噪声。 中等大小的结果数字是行星，小数字是真空或小行星。 大数字明星等。

该主题不活跃并且很旧，但搜索可能会在这里结束，就像我的那样。

Answer 7

每个太阳系的随机种子是一个可行的解决方案，但我有一种感觉，你在这里找错了树。

玩家可以做任何事情来改变那里的东西吗？ （比如说，建造一些东西，开采耗尽的资源等等？）如果是这样，你无论如何都必须保存状态。

玩家是否可以在不必实际返回那里的情况下查看该地点的情况？ （如果他不能，为什么不呢？！）你会去查找它，还是会重新生成整个太阳系只是为了找出有关它的一条信息？ （PRNG 解决方案不允许您仅获得太阳系的一部分，您必须制作整个系统。）

究竟有多少细节需要保存？

Answer 8

我认为“星系”中真的没有那么多信息无法存储在当今的计算机上。 假设一个星系有 100 颗恒星，每颗恒星有 10 颗行星，每颗行星有 3 个卫星。 您必须跟踪 100 颗恒星 + 1,000 个行星 + 3,000 个卫星，即 4,100 个天体。

以下是我们可能想要跟踪行星的事情。

大量的
X、Y、Z 位置
一天的长度（绕其自身轴旋转的时间）
年份长度
人口
50 个不同资源的资源量

假设每个值都需要一个 double 来存储它，并且我们有 57 个值要存储（让我们四舍五入为 100），那么我们就有 100 个值 * 8 个字节 * 4100 个主体 = 3,280,000 个字节。 现在，这是 3 兆数据。 这可能看起来很多，但实际上并没有那么多。 另外，我不认为你真的想在一个星系中拥有这么多恒星。 游戏确实太大而无法探索，并且可能会变得难以管理，无法尝试实际模拟给定星系中正在发生的所有事情。

这么看吧。 如果您使用像《模拟城市》这样的游戏，将城市网格上的每个方块视为潜在的行星，然后您就会意识到一个小文件中可以存储多少信息，这样您就不必随机生成任何内容。

Answer 9

我使用梅森旋转器。 PRNG 接受任意长度的种子数组。
例如，我想在坐标 x=25,y=72 上生成星系。 我用种子重新初始化了twister [25,72]。
如果我想在这个星系中生成第 1138 颗行星，我使用 [25,72,1138]。
国家？ [25,72,1138,10]
城市？ [25,72,1138,10,32]
等等。
通过这种方法，您只需使用一个数字（x 坐标之前的数字，在我们的例子中是 25 之前）就可以生成数十亿、数万亿个对象。
现在有一些项目正在使用它。
Noctis：anynowhere.com/
无限宇宙：http://www.infiniverse-game.com/

Answer 10

假设你从一个星系种子开始，即1234，取这个种子，并生成10000个随机数，每个随机数代表一个恒星系统。 当您接近星星时，您会获取星星的随机数，并将其作为新随机函数的种子。 为围绕恒星运行的天体数量生成一个随机数，并为每个天体生成一个数字（始终使用第二个随机函数），依此类推。
我不知道这是否对您有帮助，但您需要记住，随机函数内部是混乱的，对于初始条件，整个函数都会发生变化。

星系中恒星的种子必须始终产生相同的恒星，恒星的种子必须产生相同的天体，等等。

您始终可以使用统计、密度计算、改进结果来使事情变得更有趣。 始终检查函数对于相同的输入是否会产生相同的结果。

抱歉，如果我的英语很糟糕，我来自阿根廷，英语不是我训练有素的素质之一：p

PD：我正在做同样类型的游戏；）

Answer 11

您可以从某个种子（“母数”）构建一个 N 位的伪随机数。 然后，您将数字分组并用它们来回答您的问题。

示例：N=20

-> 一位数字：有多少个额外的跳跃门？
-> 三位数：用于生成每个可用跳跃的相应长度的种子
-> 六位数字：产生这个太阳系的种子
-> 十位数字：种子，用于为每个链接的太阳系生成新的 20 位数字种子

然后递归。 每个系统（具有稳定轨道等）都会在时间 0 生成，您必须计算它现在的样子。

当然，这种从母系统开始的方法意味着当前系统距离母系统越远，生成数据所需的时间就越长。 另外，这种方式会形成一棵树，而不是一张网（我希望如此）。

我认为生成坐标会更好 - 在平面中使用极坐标，也许在三维空间中使用椭球体。

Answer 12

我依稀记得以前做过这样的事。 在 90 年代初期，分形非常流行，我记得有一家公司向游戏程序员提供世界。 他们创造了一个充满星系、太阳和行星的无限宇宙，甚至包括行星上的山谷和纹理。 他们为游戏开发商寻找合适的虚拟房地产。 游戏开发人员将获得软件来渲染和使用它，以及他们在这个分形宇宙中的属性的精确坐标。

我已经用谷歌搜索了几分钟“分形游戏世界行星宇宙”之类的东西，但还没有找到它们。 可能是Pandromeda，但我不太记得了。

为了这个想法，你应该研究分形。 您所需要的只是一个连续的数字字段，您可以从种子中重新创建它，然后将这些数字表示为具有不同属性的恒星、行星和卫星。

Answer 13

如果您真的想返回到固定状态，我认为从单个值进行程序生成不是正确的方法。

假设，每个平面都有一个由 256x256 系统组成的固定网格，宇宙中有 16 个平面。 每架飞机最多有 512 个交易站和最多 8 个与其他飞机的链接。 所有交易站和链接都位于固定位置。
您的初始种子值必须至少为 2^76 才能对所有可能的宇宙进行编码。
添加更多的物体（行星、船舶……），数量会呈指数级增长。

编辑：
如果您不允许每个系统中存在多个交易站或链接，则费用会少一些。
我会使用一些永久存储，可能是像 Firebird 或 sqlite 这样的嵌入式数据库。 顺便说一句，我目前正在开发这样的游戏。

Answer 14

这就是我的想法。 不知道这是否是最终版本。

想象一个六边形网格，每个顶点都有一个太阳系。 由于我们处于六边形网格上，因此从任何顶点出发只有三条线。 一个始终是水平的，另外两个是对角线的。 如果我们给起始种子取值为n，那么我们可以给与起始点水平连接的太阳系取值n+1，其他取值n+2和n-2。

噢，糟糕。 我们不一定会得到一个网格。 该死的。 让我们再试一次。

Answer 15

如果您使用伪随机数生成器，则可以保证生成的每个随机数将按照给定种子的相同顺序出现。
每次生成由给定数字生成种子的系统的代码都会显示相同的代码。

使用伪随机数流中的第一个数字来生成“门”的数量。
通过每个门并从数字流中获取一个值以分配给每个目标系统并为其播种。

基于该种子生成每个系统的特征。

有几种已知的用于生成随机种子的算法。

尝试一下梅森扭曲器

Answer 16

只要您使用相同的种子调用 srandom()，您就会从 random() 中获得相同的值。 因此，只需将星型系统中的所有内容都建立在对 srandom() 的一次调用之上...然后，您只需要为整个星型系统存储 1 个整数（种子）。 现在这就是压缩！

Answer 17

这是我的第二个改进的解决方案。 玩家将从随机生成的太阳系开始。 每个系统都连接到 1 到 4 个其他系统。 将它们视为北、南、东、西系统。 如果玩家要通过北跳跃门，他将被带到一个种子比之前的系统多一个的系统。 如果他南下，该系统的种子就会少一个。 2+ 和 2- 分别代表东和西。 到这些系统的距离（以秒差距或光年或其他单位为单位）是根据系统的种子和您到达的方向来计算的。 这样，星系的大小仅受用于容纳种子的最大和最小数量的限制。

通往其他星系的曲速孔将放置在距起始系统一定距离的位置。 下一个星系将像这个星系的延续一样，种子数量将以同样的方式增加，并且位于星系曲速孔另一端的系统将只是“东”或“北” “从启动系统连接。

顺便说一句，与上述解决方案不同，这种增加种子的使用会导致形成网。 另外，您可以看到该方法使用四边形，而上述解决方案使用六边形，这使得无法创建网络。

当然，所有这一切都基于这样的假设：所有种子都会生成与任何其他序列不同的随机数字序列。 这使得每个系统都是独一无二的。

Answer 18

我怀疑您将面临的最大问题是拥有一个命名系统，以对玩家一致且有意义的方式命名所有这些对象 - 尽管我们确实有 系统地命名真实物体。 我忘记了 Elite 的命名约定是否在某个点后崩溃了......

Answer 19

从数学上讲，您想要随机/伪随机生成一个无向连通图。 在此图中，每个节点都是一个太阳系，每条边都是一个跳跃门。

1）创建N个节点并随机分配每个节点一个空间坐标。 这些节点最终将成为你们的太阳系。

2）使用Deluanay三角剖分算法生成边。 我建议 Deluanay 三角测量，因为它会创建一个相当漂亮的地图，没有任何门相互交叉，但您实际上可以使用您想要的任何算法。 我真的不知道你在找什么。

3）如果您使用Deluanay三角剖分，我建议您消除一定数量的边以创建“稀疏”。 这将使地图变得更加有趣，因为某些地点将成为交通枢纽，而其他地点则只是停靠站。

4) 保存该图。 这是你的宇宙。 不要放错地方或扔掉你的宇宙。 按照您想要的方式高效存储，但不要删除任何信息。

5) 为每个节点分配一个种子，并使用该种子生成每个太阳系。

6) 恭喜，您现在拥有一个具有任意数量的太阳系和跳跃门的宇宙。