math问题：一个星系的程序生成
我要制作完全由程序生成的空间/交易/战斗游戏。 但是，我知道将整个星系的所有细节都存储在内存中是不可行的。 因此，我一直认为我可以用种子生成一个太阳系，从这个太阳系，你可以使用跳闸到其他太阳系。 问题是，如果我从初始太阳系跳到另一个太阳系，我需要能够回到完全相同的特征（行星，小行星等）的完全相同的起始太阳系。
本质上，我需要能够从一个数字生成整个星系。 从这个生成一个太阳系的数字中，我需要能够生成所有其他连接第一个太阳系的太阳系和所有连接太阳系的太阳系，等等。 如果我回到他们身上，每个太阳系都必须保持完全相同的function。 此外，每个太阳能系统的链路数量可以是随机的，也可以是固定的。 随机会更好，但。
如果你觉得自己很勇敢，那么看看伊恩·贝尔（Ian Bell）如何为原始版本的精英（Elite） 做出这样的决定，可能会更糟糕
看看这个系列Gamasutra：
实时程序性宇宙，前四个环节
另外，这个： 无限宇宙的algorithm
这是我理解的基本思想。 假设你已经到达星级系统＃42，你需要找出它的内容。 它有nplanets行星 – 0到10之间的数字，说：
>>> star_system = 42 >>> nplanets = hash('nplanets%d' % star_system) % (10 + 1) >>> nplanets 4
那么，在第二号星球上，在游戏开始的时候有多less个太空站在轨？ find0到3之间的数字：
>>> planet = 2 >>> nstations = hash('nstations%d/%d' % (star_system, planet)) % (3 + 1) >>> nstations 1
等等。 这些数字每个都是指数的散列函数（星系统＃42，在这种情况下，星球2），减less到适当的范围。 由于散列函数是确定性的，但是是“随机的”，所以每次都是一样的，但随机地看着玩家。
当然，在其中使用像“nstations”这样的长序列来散列string并不是最快的方法，但它显示了这个想法。
看看最初的蠕虫游戏。 我认为它声称有大约40亿个可能的水平。 每个级别都是基于20个字符的短种子string生成的。 这确定了
- 水平的主题（北极，森林等）
- 景观的形状
- 地面的滑溜
- 预置级别细节（雪人，岩石…）
- 安置你的蠕虫，地雷和武器箱。
如果你喜欢一个级别，你可以写下种子string，并在以后使用它来重新生成相同的级别。
这是一个非常复杂但具有确定性function的例子，只有一个input参数。 我认为这是你所需要的基本概念。
你不能只是SHA1的银河ID，EG：
银河1
Sha1(1) = 356a192b7913b04c54574d18c28d46e6395428ab
银河2
Sha1(2) = da4b9237bacccdf19c0760cab7aec4a8359010b0
银河3
Sha1(3) = 77de68daecd823babbb58edb1c8e14d7106e83bb
您可以再将代码分段，IE：
前4个字符=行星数量
356a da4b 77de
你需要一些string到数字的algorithm，一个简单的就是把每个非数字字符的ASCII码，然后把它们全部相乘或者什么东西。
所以现在我们知道星系中有多less个行星，星系x，y，z尺寸如何？
下一个9个字符= Galaxy尺寸（x，y，z）
与上述原理相同，将代码转换为大量代码。 也有一些敏感性检查，你不希望有一个10milesx10milesx10miles与2000万行星在它的星系。 有一些加权algorithm，如最小尺寸是＃行星* 10000。你将需要玩的数字，以确保范围都是兼容的，从哈希选定的字符实际上给你一个合理的范围。
或者，也可以用一个随机数在银河系的最小和最大尺寸之间select一个数字，但是使用一个恒定的RNG种子，如银河系ID！ 这样，观测者的星系尺寸基本上是“随机的”，但每次都是一样的。
等等等等！
这是获得宇宙属性的一种方式，但是地球属性呢？ 像人口和其他东西？
如果你有银河1与20,000颗行星，你可以做：
Sha1('1:340') = bc02ab36f163baee2a04cebaed8b141505cc26b5
也就是说，星系一，行星340.然后，你可以只是拼凑起来的代码，但是你想要的。 使用散列的好处是每个星球都应该有一个完全独特的代码。
我认为值得注意的是
-
为相同input产生相同随机输出的发生器称为伪随机数发生器“PRNG”。 通常情况下，您在开始时给它一个“种子”input号码，然后从中随机抽取一个号码，在没有进一步input的情况下调用它。 注意：你不能“回头”到一个较早的号码，至less不能从头开始。
-
一个类似PRNG的函数被称为坐标作为每个调用的input，通常是一个“噪声”函数。 在这里你没有“不能回头”的问题 – 只需再次input“更早”的input。 一个噪声函数使用PRNG（作为后端;或者至less可以），它仍然可以在一开始就被播种，所以你不会失去你的“宇宙超出一个数字”的function。
-
虽然您可以使用PRNG，并且每次将星系坐标合并到“种子”，但您只能得到“白噪声”，而没有其他属性。 噪音function更适合这项工作，因为它可以select，甚至可以调整，让你看起来像/平滑/像螺旋状看/等。 结果。 例如search使用珀林噪声制作的纹理图像。 我希望你能看到，使用相同的噪声函数，你可以创build成千上万的随机云，但是通过调整噪声函数来满足你的需要（不仅仅是种子或坐标），你可能会得到熔岩或星系。 调整它可能不是微不足道的。
-
每次调用的input坐标数决定了噪声函数的维数，因此对于二维映射（或纹理等），可以使用二维噪声函数。 然后你每次调用它像noise2d（x，y）。
在你的情况下，我会尝试一个三维单纯形噪声函数（单纯是来自珀林噪声的作者，build议作为更好）。
每个星系坐标 – 三联体给你一个结果数字。 下一个决定是：这个数字代表什么？ 为了使单纯噪声的平滑特性得到很好的利用，我将把较低的数字映射到较空的太阳系，将较高的数映射到质量较大的系统。 或者，也许更好，每个系统用子坐标多次调用单工噪声。 中等大小的结果数字是行星，小数字是真空或小行星。 大数星星等
这个话题不是主动的，它是古老的，但search可能会在这里结束，就像我的做法一样。
我不认为在一个“银河系”中有太多的信息，你不能把它存储在今天的电脑上。 假设一个星系有100颗恒星，每颗恒星有10颗行星，每颗行星有3颗星。 这是100颗星+ 1,000颗行星+3000颗星，你必须跟踪，这是4100个机构。
以下是我们可能想要跟踪的一个星球的事情。
质量X，Y，Z位置一天的长度（在自己的轴上旋转的时间）年份长度人口50个不同资源的资源量
假设每个值都需要双重存储，并且我们有57个值来存储（让它四舍五入，然后说100），那么我们有100个值* 8字节* 4100个物体= 3,280,000字节。 现在，那3兆的数据。 这可能看起来很多，但实际上并不多。 另外，我不认为你真的想在一个星系中有这么多星星。 这个游戏真的太大了，无法探索，而且可能会难以pipe理，试图模拟一个特定星系中正在发生的所有事情。
这样看。 如果你参加模拟城市游戏，把城市网格上的每个广场看作是一个潜在的星球，然后你意识到在一个小文件中可以存储多less信息，所以你不必随意产生任何东西。
每个太阳系的随机种子是一个可行的解决scheme，但我有一种感觉，你在这里吠叫错误的树。
玩家可以做任何改变那里的东西吗？ （说，build立一个东西，挖掘一个耗尽的资源等）？如果是这样，你将不得不拯救国家。
玩家可以在没有真正回去的情况下查看这个地方是什么吗？ （如果他不能，为什么不呢？）你要去查看它，还是要重新整个太阳系来找出关于它的一些信息？ （PRNG解决scheme不允许你只获得太阳系的一部分，你必须做好整个事情。）
无论如何，你需要保存多less细节？
假设你从一个星系的种子开始，即1234，取这个种子，产生10000个随机数，每个代表一个星系。 当你接近这颗恒星时，你将这颗恒星的随机数作为一个新的随机函数的种子。 生成一个随机数，用于绕恒星运行的天体数量，并为每个物体生成一个数字（总是使用第二个随机函数）等等。 我不知道这是否有助于你，但是你需要记住，随机函数是内部混沌的，对于初始条件，整个函数都会改变。
星系中的恒星的种子必须总是产生相同的恒星，恒星的种子必须产生相同的恒星等。
您可以使用统计，密度计算，改善结果，使事情变得更加有趣。 总是检查function将产生相同的input相同的结果。
对不起，如果我的英语很烂，我来自阿根廷，英语不是我训练有素的人物之一
PD：我正在做同样types的游戏;）
我使用Mersenne Twister。 PRNG接受任何长度的种子数组。
例如，我想要在坐标x = 25，y = 72上生成星系。 我用种子重新启动了扭转者[25,72]。
如果我想在这个星系中产生第1138个星球，我使用[25,72,1138]。
国家？ [25,72,1138,10]
市？ [25,72,1138,10,32]
等等。
使用这种方法，您可以使用一个数字（x坐标之前的那个数字，在我们的情况下是25之前）生成数十亿亿万亿的对象。
现在有一些项目正在使用它。
Noctis：anynowhere.com/
Infiniverse： http : //www.infiniverse-game.com/
您可以从某个种子（“母亲号码”）build立一个N位的伪随机数。 然后，将这些数字分组，并用它们来回答你的问题。
例如： N = 20
– >一位数字：还有多less跳门？
– >三位：用于生成每个可用跳转的相应长度的种子
– >六位数字：产生这个太阳系的种子
– >十位数字：为每个连接的太阳系生成一个新的20位数种子的种子
然后recursion。 每个系统（具有稳定的轨道等）在0时刻产生，你将不得不计算它现在的样子。
当然，这种从母系统开始的方法，意味着当前系统离母系统越远，生成数据所需的时间就越长。 此外，这种方式使树，而不是一个networking（我期望）。
我认为最好是生成坐标 – 在平面上使用极坐标，也可以在三维中使用椭球。
我可以隐约回忆起之前做过的事情。 在90年代初期，分形风靡一时，我记得有一家公司向游戏程序员提供世界。 创造了一个完整无限的宇宙，充满了有太阳和行星的星系，一直到行星上的山谷和纹理。 他们正在向游戏开发商提供合适的虚拟房地产。 游戏开发者将得到软件来渲染和使用它，以及在这个分形宇宙中精确的坐标。
我已经search了几分钟“分形游戏世界星球宇宙”等，但没有find它们。 这可能是Pandromeda ，但我不记得。
你应该研究这个想法的分形。 所有你需要的是一个连续的数字领域，你可以从一个种子重新创build，然后将这些数字作为具有不同属性的恒星，行星和卫星。
如果你真的想回到一个固定的状态，我不认为从一个单一的价值观的程序生成是正确的路要走。
我们假设，在每个平面上有一个256×256的系统，在宇宙中有16个平面。 每架飞机有多达512个交易站，多达8个连接其他飞机。 所有的交易站和链接都是固定的。 您的初始种子值必须至less为2 ^ 76才能编码所有可能的Universe。 增加一些物体（行星，船，…），数量呈指数增长。
编辑：如果您不允许在每个系统中使用多个交易站或链接，则会less一些。 我会使用一些永久存储，也许像Firebird或SQLite的embedded式数据库。 顺便说一句，我目前正在开发这样一个游戏。
这是我所想到的。 不知道，如果它将是最终版本。
想象一下六angular形网格，在每个顶点，一个太阳系。 因为我们在一个六边形网格上，所以从顶点只有三条线。 一个总是水平的，另外两个是对angular线。 如果我们给出的起始种子的值为n，我们可以给出水平连接到起始点的太阳系n + 1的值，其他值得到n + 2和n-2的值。
哦，废话。 我们不一定会得到一个网格。 该死的。 让我们再试一次。
如果您使用伪随机数发生器，您可以保证您生成的每个随机数将以与给定种子相同的顺序出现。 生成由给定号码播种的系统的代码每次生成时都会显示相同的代码。
使用伪随机数字stream中的第一个数字来生成“门”的数量。 浏览每个门，从数字stream中获取一个值，分配给每个目标系统。
根据该种子生成每个系统的特征。
有几种已知的生成随机种子的algorithm。
给梅森扭曲者一个裂缝
只要你使用相同的种子来调用srandom（），你将会从random（）中得到相同的值。 所以，只需要把所有的东西都放在一个星系中，然后再调用srandom（）…然后，你只需要为整个星系存储一个整数（种子）。 现在就是压缩！
这是我第二个改进的解决scheme。 玩家将从随机产生的太阳系中开始。 每个系统连接到1到4个其他系统之间。 把它们想象成北，南，东，西系统。 如果一个玩家要通过北跳门，他将被带到一个比以前系统多一个种子的系统。 如果他南下，这个系统的种子就less一个。 2+和2-分别为东和西。 这些系统的距离（在parsecs或lightyears或其他）是用系统的种子和你到达的方向来计算的。 这样，星系的大小只受限于用来保持种子的数量的最大值和最小值。
去其他星系的经线孔将与起始系统相距一定的距离。 下一个星系就像这个星系的延续，因为种子数量将以相同的方式递增，并且位于银河经线孔另一端的系统将只是一个“东”或“北” “从起始系统连接。
顺便说一下，与上述解决scheme不同的是，增量种子的这种使用导致networking。 此外，您可以看到，这种方法使用四边形，而上述解决scheme使用六边形，这使得无法创build一个networking。
当然，所有这些都是基于这样的假设，即所有的种子都会产生一个与其他序列不同的随机数字序列。 这使得每个系统都是独一无二的。
我怀疑你要面对的最大的问题是命名系统以一种对玩家一致和有意义的方式命名所有这些对象 – 尽pipe我们有系统地命名实际对象的scheme。 我忘了Elite的命名惯例是否在某个点之后崩溃了…
在math上，你想随机/伪随机生成一个无向图，连通图。 在这个图中，每个节点将是一个太阳系，每个边都是一个跳门。
1）创buildN个节点并随机分配每个空间坐标。 这些节点将最终成为您的太阳能系统。
2）使用Deluanay三angular测量algorithm生成边缘。 我build议Deluanay三angular测量，因为它会创build一个相当漂亮的地图，没有任何门相互交叉，但你可以使用任何你想要的algorithm。 我真的不知道你在找什么
3）如果你使用Deluanay三angular剖分，我build议你消除一定数量的边缘来创build“稀疏”。 这将使地图更有趣，因为某些地点将成为交通枢纽，而另一些则只是进站点。
4）保存此图。 这是你的宇宙。 不要错放或丢弃你的宇宙。 尽可能高效地存储它，但不要删除任何信息。
5）为每个节点分配一个种子，并使用这个种子生成每个太阳系。
6）恭喜，你现在有一个任意数量的太阳系和跳闸的宇宙。
