注意 ：本文在 DIP 上与其他图像和交互式内容一起发布
大小决定一切
我有一个家庭，抵押贷款和无法割草的草坪。 我是一个笨拙的老人，没有时间再玩电子游戏了。 这些天在游戏世界中发生的任何事情都倾向于让我过去。
电子游戏创造了整个虚拟世界，让您以其他媒介无法体验的方式体验它们。 现在， 我通常会想象一个世界，那里的婴儿会自己换尿布，割草，厨房的水龙头会分配清凉的啤酒。
值得庆幸的是，许多视频游戏的创造者比我更具想象力。他们给了我们无穷无尽的例子，这些世界完全来自于他们的想象力：鬼屋，幻想岛，覆盖虚拟平方英里的古老土地。 最好的例子细节丰富，制作精良。
考虑诸如侠盗猎车手 （ Grand Theft Auto）之类的东西，它有一个完整的，充满生机的城市，里面充满了汽车，建筑物，行人，带有自动武器的疯子以及所有您在任何大型城市中都可以找到的所有其他东西。 现在，尽管构建数字副本，纽约所需的工作量要比实际构建要少得多，但创建虚拟世界却需要大量的时间和精力。 软件需要编写，布局需要计划，对象需要绘制和动画，人物需要栩栩如生。 如今，视频游戏的制作类似于电影制作，来自不同部门的数十名人们一起工作。
这就是为什么最近发行的游戏《 无人的天空》如此吸引我。 这场比赛讨论得如此广泛，它成功地渗透了我自己的世界为保护我免受令人愉悦的事物而提出的防御措施。 No Man’s Sky是一款科幻游戏，您在其中扮演一个星际探险者，他从一个星球穿越到另一个星球，收集资源，与生物战斗并飞行航天器。 使这款游戏与众不同的是探险家所居住的宇宙的大小。
它包含18亿个行星[1]。
五百亿
五百亿 。
我没说那个话，是真的。 五分位数是1，后跟18个零。
因此，这个游戏有18万亿个行星需要探索。
毫无疑问，每个星球都是一个庞大而详细的世界，到处都是动物，动物和地形。
《 无人深空 》中的宇宙是如此巨大，以至于不可能访问其中的每个星球，或者所有星球附近的任何地方。 想一想。 如果您活到80岁，那么您将生活约4200万分钟。 如果您一生都在不停地玩这个游戏，只花一分钟就可以探索每个星球，那么您所看到的不到宇宙的1％。
实际上，您已经看到了大约0.0000000000001％。
要真正让您大吃一惊，请考虑一下：“ 无人深空”中的宇宙太大而无法放入出售的光盘中。 在撰写本文时，大容量的蓝光光盘可以存储大约100 GB的信息[2]-大约为1000亿（100,000亿）字节[3]。 因此，尝试将有关18亿五千万个行星的信息塞入Blu-Ray光盘中，将只能使您仅用一个字节的一小部分来描述整个行星。
与此相比，OpenStreetMap仅映射地球，并需要大约50 GB的压缩数据⁴
而且，只是为了炫耀，《 无人深空》的开发人员透露，大多数光盘还是空的。 整个游戏的大小约为6 GB，其中大部分用于存储音乐。
那有什么呢？ 侠盗猎车手（Grand Theft Auto）这样的游戏需要数十人组成一个团队，才能产生一个城市大小的世界。 No Man’s Sky的开发人员如何才能创建一个功能强大的宇宙，其规模如此之大，以至于无法使蓝光光盘表现得像Who Who’s TARDIS？
让相机完成工作
要开始回答这个问题，我们需要了解计算机如何创建视觉世界。 解决这个问题的第一批人之一是Adobe⁵的联合创始人约翰·沃诺克（John Warnock），这家公司为您带来了Acrobat，让您每天都在疯狂地更新程序。 故事是这样的，他的一位同事正试图找到一种方法，使计算机可以显示一艘过往船只看到的纽约港的图像。 该图像必须实时播放，这意味着随着船的移动，视图变化缓慢。 Warnock的同事为如何使计算机达到视差而感到困惑-也就是说，使离船较近的物体似乎在距离较远的物体前面通过。
实现此目的的一种方法是实际上船，从许多不同角度拍摄大量纽约港的照片，然后将这些数字图像放入数据库中。 当您希望计算机模拟驶过纽约的航行时，您只需指示计算机以正确的顺序播放这些图像，就像动画一样。
我说“简单”，但实际上并没有那么简单。 考虑到实际拍摄照片的后勤困难，这种方法带来了无数的技术问题。 首先是存储问题。 为了模拟沿整个港口的移动以及能够沿多个不同方向观察，您需要设计一条路线，将一系列点隔开几米，然后在每个点上从不同方向拍摄几张照片。 但是纽约港是一百平方英里，因此会有成千上万个点，因此要拍摄成千上万张照片。 如果我们保守地说每张照片将占用一兆字节的空间，那仍然需要GB的存储空间。 但是约翰·沃诺克（John Warnock）在1960年代后期解决了这个问题，当时即使最大的磁盘也无法存储接近此数量的数据。
尽管如此，技术仍在前进。 今天我们有更大的硬盘，那么我们现在可以使用这种方法吗？
我们可能确实有空间，但是用这种方法仍然无法解决最根本的问题，即它的局限性。 例如，当您“站立”在岸上时，如何看待船舶？ 您怎么能从自由女神像的顶部看到风景呢？ 答案是：您不能。 如果不拍照，则无法使计算机显示它。
Warnock采取了一种截然不同的方法，该方法具有双重优势：既节省了存储空间，又便宜又灵活。 他向计算机描述了纽约港，并告诉计算机为他绘制图像。 为此，Warnock将视图分解为组成元素（基本上是水，建筑物，船等），并教计算机如何绘制它们。 以水为例：它是蓝色的，平坦的，并向各个方向延伸。 建筑物本质上是长方体，有些是棕色的，有些是灰色的，有些是矮的，有些是高的。 定义元素只是用计算机可以理解的简单术语（例如大小，形状和颜色）来描述它。
与等价的图像数据相比，此类描述占用了空间的最小部分。 他只需要将它们全部放在正确的位置，然后告诉计算机从特定角度绘制它们即可。 结果是从海平面，海岸，自由女神像的鼻子或您想要的地狱的任何地方描绘了纽约港。
这个故事的寓意是：如果要在计算机上创建自己的虚拟世界，最好用模型描述您的世界，然后让计算机为您绘制模型。 然后，您可以通过在生成的环境中移动虚拟相机来探索世界。 电脑会照此调整风景。 计算机采用模型元素并将其绘制到屏幕上的过程称为渲染 。 渲染在本文中很重要，因为视频游戏在创建虚拟世界时会使用这种方法。
启动引擎
要渲染事物，程序员需要提供两件事：
- 定义环境的指令称为游戏引擎 。 这样可以解决诸如光在宇宙中的行为，重力如何工作，是否存在摩擦等问题。
- 生活在环境中的特定元素（水，建筑物，巨大的蘑菇，喷火的美洲驼）有时也称为内容 。
内容通常决定游戏的大小，而相比之下，引擎实际上可能很小。 实际上，内容可以不断增长，而引擎可以保持相同的大小。
所有这些都是侠盗猎车手的制造者创造城市的方式。 光盘的大部分内容充斥着：汽车，建筑物，枪支，妓女，行人平整的模型描述以及在下午的狂乱中看到的其他所有内容。
对于Grand Theft Auto的制造商来说，这一切都很好，但是对于No Man’s Sky来说 ，这仍然不是一个足够的解决方案。 别忘了，它的宇宙由18百万个行星组成，每个行星都有自己的动植物，人工制品。 光盘上没有足够的空间来描述所有这些内容。
那么，如何在提供很少或根本没有内容的情况下制作视频游戏呢？
欢迎来到程序生成的世界。
如果您采用通常的方法在视频游戏世界中创建星球，则需要建立如下描述：
*在位置432：221放一个绿色杂草
*将急救箱放在434：210的位置
*在435：213位置放置咆哮的小动物
*在436：218位置放一条备用裤子
... 等等。
您可以想象使用这种方法来描述充满杂草，野兽和脏内衣的整个星球会占用大量的光盘空间。
但是随着程序生成，您对计算机的指令更像是这样：
*做一个星球
而已。 他们实际上不是将游戏设计师利用自己的想象力来设计行星，而是将想象力的工作委托给计算机。 他们对数字媒体同行说：“疯狂。” “让我成为一颗面积达一百万平方英里的星球。 到处都是树木，河流和咆哮的野兽，然后将它们放置在您喜欢的任何地方。”
这听起来像是灾难和混乱的配方（特别是如果您曾经编程过计算机）。 在地球上-或在任何星球上，如何才能在没有给出具体的布局说明的情况下让计算机为您创建虚拟世界？
这就是产生过程的地方。这是一个棘手的话题，所以让我从一个简单的想法开始：分形。
分形地爱
即使您不知道实际的分形是什么，也很有可能已经以一种精致而迷幻的模式看到了它。 当显示在屏幕上时，它们通常是动画的，相机不断地“放大”到分形的特定区域，从而揭示出新的细节。 而且，无论相机放大了多远，它始终会显示出看起来相同的新分形。 分形由很多分形组成，每个分形都由许多分形组成，每个分形都由许多分形组成，每个分形都是。 这就像放大蕨叶以发现它由许多小蕨叶组成，每个小蕨叶都由许多小蕨叶组成，依此类推。
了解如何进行分形可以帮助您理解程序生成。 一个非常简单的是T平方⁶。 制作方法如下：
- 从正方形开始。
- 在每个凸角处（即，每个指向外部的角）放置另一个新正方形，其宽度为原始正方形的一半。 每个新正方形都应位于拐角处的中心。
- 返回步骤2。
您可以在动画中看到这些指令的前几次迭代。
那是如何进行分形的一个例子。 而且，如果您还没有弄清楚，分形就是程序生成的一个例子。 创建T形正方形时，将按程序创建复杂的形状，也就是说，您将按照说明来构建形状。
只是为了说明这一点，我将向您展示另一个称为科赫雪花的分形。 这是制作方法。
- 从等边三角形开始。
- 分别考虑形状的每一侧。
- 取形状的一侧并将线分成三个相等的部分。
- 拆下中间部分。
- 添加两条新线（与删除的部分长度相同），并使用它们使一个点突出到侧面。
- 对形状的所有其他边重复步骤3-5。
- 返回步骤2。
您可以在此处看到此过程的动画。
同样，这是程序生成：按照指示构建视觉效果。
建模雪花的另一种方法（类似于大多数视频游戏的工作方式）是将视觉布局存储为数据，并在渲染时解释该数据。 例如，渲染科赫雪花所需的数据可以是构成形状各边的一系列直线。 渲染它只是意味着绘制每条线。 在这种情况下，对于等边三角形的初始阶段，我们将需要存储六组坐标（因为每条线被定义为一对点）。 要在重复一次后渲染雪花，需要存储24组坐标（因为它有12条线）。 对于两次重复的雪花，需要96个坐标（48行）。 重复三遍后，有384个坐标（192行），依此类推。 如您所见，使用此方法意味着形状越大，越复杂，则需要更多的存储空间来描述它。
但是随着程序生成，您将不再具有指令和数据，而仅具有指令。 您可以根据需要构建任意多的复杂性，而无需花费额外的存储空间。 与“重复3 000次”相比，存储“重复3次”所需的空间量与计算机完全相同。
未来的流氓
现在，我们终于可以开始将程序生成与视频游戏结合起来了。 想象您正在创建一个视频游戏，它使用俯视图描绘游戏世界，就像您的角色在地图上奔跑一样。 您可以通过描述游戏引擎的线条来构建环境，然后将这些线条提取并渲染为墙。 这样，您可以创建2D，自上而下的视频游戏⁸。
使用T平方，我们可以在不使用任何数据的情况下生成地图的线条。 如果您想在游戏世界中放置一个简单的方形房间，则可以重复执行上述T形步骤。 如果进行第二次重复，您将获得一座带有四个炮塔的小巧城堡。 重复三遍将产生一个超级堡垒，该堡垒的四个主炮塔都有自己的微型炮塔。 等等。 您只需执行更多重复步骤，就可以为您的世界增加越来越多的复杂性。
您还可以在不使用更多存储空间的情况下，使游戏世界变得更大。 你要一个小房间吗？ 告诉引擎，地图中的每个像素对应于游戏世界中的一米。 对于更大的房间，告诉它每个像素映射到100米。 对于一个愚蠢的大房间，使每个像素等于一英里！
但是，不管它的大小如何，只有一个空房间的游戏都无法制作出非常有趣的游戏。 但是，您可能会想到采用这种方法的更复杂的变化来创建一个更加多样化和有趣的世界。 也许您可以调整以上步骤以生成三个房间。 也许是三座城堡。 您甚至可以将它们混合在一起，生成一个包含16个房间的城堡。 进一步修改这些说明也不必花费太多精力，从而使房间通过一条隧道（两条平行线）相连。
实际上，整个早期的计算机游戏都像这样工作。 在最早的例子之一Rogue之后，它们被称为“ roguelikes”。 在一个流氓般的游戏中，您扮演了一个冒险家，探索迷宫般的地牢，里面充满了危险的生物和神话般的宝藏。 这些游戏出现在1970年代末和1980年代初，当时计算机图形学还很粗糙。 游戏世界是使用自顶向下的视图呈现给您的，线条代表墙壁和简单的符号代表可怕的敌人（例如，凶恶的毒蛇毒蛇准备将其尖牙沉入您脆弱的肉体中……使用字母“ S”）。
当时，这样的游戏本身已经足够新颖，但是流氓类通常具有一个额外的卖点。 游戏的创建者没有手动设计游戏世界的布局。 它是程序生成的。 房间，连接的隧道，敌人和宝藏都是在新游戏开始时由计算机创建和定位的。
至关重要的是，每次玩游戏时，布局都是不同的，以确保玩家不断回头。
随机的力量
生成地牢的方法有很多种，每种“ roguelike”都使用自己的程序，尽管在基本层面上通常有两种方法：1）首先放置房间，然后尝试通过隧道连接它们，或者2）使用以下方法放置隧道迷宫生成算法，然后统一迷宫的各个部分以形成房间⁹。
一个示例按照以下方式生成游戏世界：
- 在地图中心生成一个房间。
- 选择房间的随机墙，然后在该墙上选择随机点（将从该点挖出一个隧道）。
- 验证是否有足够的空间来挖掘隧道（您不想挖掘已经存在的功能）。 如果空间不足，请返回步骤2。
- 生成隧道。
- 在此隧道的末端，生成一个与其连接的新房间。
- 如果此时地牢仍然不完整，请返回步骤2。
- 否则，在地牢周围的随机点生成一些怪物和宝藏。
- 完了 玩！
当然，该描述提供了非常简化的视图。 在某些时候，它使用了“生成”一词，并且隐藏了很多细节。 但是生成房间或隧道非常类似于创建分形，这在我们之前已经介绍过。 例如，生成房间仅是绘制形状的情况，您可以为此编写一组指令。 要在地牢中添加一些变化，您可以为每个房间的墙壁设置随机长度，或者使每个隧道的尺寸和形状随机。
随机性在程序生成的游戏中很重要，因为它可以确保每次玩游戏时环境都不同。 如果计算机遵循相同的指令集来创建每个房间，则所有房间最终将看起来相同。 但是，如果您在过程中注入一些随机性，则生成房间的说明应如下所示……
1.令X等于1到10之间的随机数。
2.令Y等于1到10之间的随机数。
3.绘制一个带有X和Y边的矩形。
…然后，您所有房间的形状和大小都会有所不同，有些很大，有些很小，有些正方形，有些又细长。 它使环境变得有趣而有机。
您可以在程序生成的游戏环境中通过几种不同的方法来处理随机性。 流氓类游戏的作者希望玩家能够继续获得更多收益，即使他们已经成功完成了游戏，因此这些作者编写的程序每次都会创造一个不同的世界。 这种永无止境的挑战和发现感确保玩家永远不会遭受社交生活带来的不便。
但是其他游戏则采取了不同的方法。 他们的作者希望每位玩家每次玩游戏时的游戏世界都一样。 他们随机生成了一个环境，以使其看起来变化多端且有趣，但是这样做的方式使得生成过程始终创建完全相同的环境。
每次随机生成完全相同的事物的想法似乎很奇怪且自相矛盾，但是由于确定性的计算概念，这完全有可能。 关键在于生成随机数的细节。 用于随机数生成的算法通常非常复杂（这会使它们难以理解），因此出于解释的目的，我将使用一种非常简单的算法。 这将生成一个介于1到10之间的随机数。
1.输入种子
2.令SUM =种子乘以5
3.当SUM除以11时，使结果=余数
“种子”是一个起始数字，是随后的数学杂技的起点。 不同的种子会产生不同的结果。 自己尝试。 如果使用1作为种子，则结果应为5； 用2作为种子可以得到10; 3产生4，依此类推。
现在，让我们回到之前的房间生成算法中，得出一个roguelike。 作者需要连续的随机数序列作为其房间尺寸。 理想情况下，他们需要一个混乱的源头，它会散发出无尽的，不可预测的随机数作为种子。 一个受欢迎的来源是计算机的时钟。 它坐在那里，实际上是在计算分钟（或更准确地说是毫秒），从而每秒更新时钟状态数百次。 该算法可以将时钟视为种子生成器，它抛出了无穷无尽的数字流。
假设第一条指令（让X等于1到10之间的随机数）是在时钟读取10：31：04.10111时执行的。 数字发生器剪掉最后一位数字（1），并将其用作随机数发生器的种子，结果为5 12。 当计算机执行第二条指令时（让Y等于1到10之间的随机数），时间已经提前-假设3毫秒变为10：31：04.104。 这次的种子是4； 将4插入随机数生成器将产生9。因此，当计算机到达第三条指令时，它将绘制5×9矩形。 继续这样做，他们最终将以各种无法预测的形状和大小进入房间。
精英一代
如果他们每次都想要一个不同的环境，那就很好用。 但是对于我们来说，我们希望环境是相同的。 在这种情况下，他们可以将随机数生成器的输出插回开头，以便一次运行的输出成为下一次运行的种子。 这样，该过程是不受指导的，但是只要您运行它，它总是会产生相同的结果。 如果就我们的随机数生成器而言，它以1作为种子开始，则得到5作为结果； 当种子产生3时，插入5； 3产生4，依此类推。 如果重复此过程，结果将是相同的。 要开始该过程，游戏作者必须提供1的初始种子（此数字将存储在游戏光盘上），但随后他们可以坐下来观察计算机搅动数字并建立游戏世界。 他们甚至可以尝试使用不同的种子，然后再选择能够获得自己喜欢的结果的初始种子。 最后重要的是，当玩家开始游戏时，游戏世界生成器会获取存储在光盘上的初始种子并创建相同的世界。
创造一个每次都一样的世界并不像看起来那样毫无意义。 当游戏具有一个一致的世界（无论是否生成）时，所有玩家都可以在共同的参照框架中分享他们的经验或相互竞争。 当玩家可能需要重新访问他们曾经去过的地方时，这也很重要，在这种情况下，生成过程必须以与以前完全相同的方式重建世界的那部分。
特别是一种早期的计算机游戏就依赖于此功能。 它被称为精英（Elite） ，允许玩家控制一个星际飞船，飞向世界，交易外来资源，与太空海盗作战并避开银河警察。 我们的目标是通过低价买入，高价卖出并一边进行一些“毫无疑问”的工作来致富。 这也是程序生成不仅限于图形的例子。
Elite于1984年为BBC Micro推出，它可以存储仅几十万个字节的软盘。 然而，这款游戏能够产生一个282万亿个星系的宇宙，每个星系都有256个命名的恒星系统。 没错：每个恒星系统都有一个名字，一个明显的名字（尽管是科幻小说）。 例子包括Lave，Diso或Leesti。 显然，所有这些数万亿个名称都无法存储在脆弱的软盘上，因此，就像银河的布局一样，这些名称也是按照程序生成的。
通过参考存储在光盘上的一长串字母来完成此操作：
“ LEXEZEZACEBISOUSESMANAINDIREAERATENBERALAVETIEDORQUANTSRION”
为了生成星系的名称，选择了一些随机数（其值不超过此字符串的长度）。 每个数字将对应于字符串中的一个字母，并且对于每个数字，游戏引擎将同时获取相应的字母及其直接后继字母。 当所有字母放在一起时，他们拼出了名字。 例如，可能会生成数字1、5和11。 结果，该算法将挑选出“ LE”，“ GE”和“ BE”，从而得到一个名为“ Legebi”的星系。
一个有趣的事实……尽管1984年的《 Elite》最初可以创建一个282万亿个星系的宇宙，给人以微不足道的感觉，但是却被游戏发行者的订单大大削弱了。 他们的观点是，如此巨大的宇宙会使玩家怀疑数学上的诡计背后的一切，并给人以强烈的人造感。 最后，该游戏仅包含八个星系。
相反，《 无人的天空》的作者并没有受到这种恐惧的束缚。 那是明智之举吗？ 我敢肯定，游戏玩家们会争论一段时间。
同时，我将修剪草坪。
综上所述
在本文中，我向您展示了如何绘制无尽大小和复杂性的形状，如何生成布满生物和宝藏的地图，甚至可以在短短的几毫秒内生成大量原始名称的可能性。 我使用的示例可能来自视频游戏的早期，但是使用程序生成的现代游戏（虽然更加复杂和美观）仍然遵循此处编写的基本思想。
我当然希望我已经揭开了像No Man’s Sky这样的程序生成游戏背后的魔力的神秘面纱。 游戏世界的巨大规模是由一些编程技巧造成的。 穿越宇宙类似于穿越分形。 随着您的前进，计算机会尽职尽责地继续创造您周围的世界，而无非就是一系列算法指令。 当您降落在下一个星球上时，游戏不会从游戏光盘加载该星球的数据。 通过选择一些基本的对象类型并提出无穷无尽的变化，眨眼间就可以将新世界实时地组合在一起。 毕竟，每个对象都有可操纵的属性，就像在无赖中一样，房间具有尺寸一样。 植物具有类型，大小，颜色等属性。 这里的植物是杂草，短的红色。 那棵植物有一棵树，高大，瘦瘦，紫色。 哦，有一种黄色的恐龙型生物，有六只脚被羽毛覆盖。 重复进行足够长的时间，最终您将找到一个人口众多的星球。
一旦您探索了那个，那下一步呢？ 好吧，这里有五百万种选择，而您的下一个目的地与上一个目的地的机会将大不相同。
注释和参考
¹http://www.polygon.com/2014/8/19/6045933/its-impossible-to-visit-every-planet-in-no-mans-sky
²http://www.blu-ray.com/faq/
³字节是计算机可以寻址的最小存储量，并且是存储一个字符所需的空间量。
⁴http://wiki.openstreetmap.org/wiki/Planet.osm
⁵Robert X. Cringely。 意外帝国 。 Addison-Wesley，1996年。
⁶http://mathtician.weebly.com/t-square-fractal.html
⁷http://math.rice.edu/~lanius/frac/koch.html
⁸出于您的兴趣，您还可以用这种方式制作伪3D游戏。 同样，线条会告诉计算机墙壁在哪里，但是通过将虚拟摄像机放置在地图上，它将从玩家的角度渲染世界。 如果摄像机指向一条直线，则计算机会在播放器前面渲染一堵墙。 这就是《毁灭战士》这样的游戏的运作方式。
⁹http://pcg.wikidot.com/pcg-algorithm:dungeon-generation
¹⁰http://www.roguebasin.com/index.php?title=Dungeon-Building_Algorithm
¹¹这是10小时31分4秒零101毫秒。
12 5 = 5 x 1，5 = 5除以11时的余数
¹³http://wiki.alioth.net/index.php/Oolite_planet_list#Where_do_these_crazy_names_come_from.3F
¹⁴https://www.theguardian.com/books/2003/oct/18/features.weekend
