algorithm - 我如何才能采用在 2D 空间中运行良好的算法并使其适应 3D 环境？

Question

我喜欢 technique Spelunky 过去用于生成游戏中的关卡，我想将其调整为 3D 空间，以便我可以使用它来帮助我在该 3D 空间中设计一些东西。我只是不确定如何解决此类问题。我觉得这种特定方法的直接翻译是不可能的，但我仍然希望有一些感觉相似的东西，具有相同的曲折路径。

Answer 1

这是一个有趣的问题，因为当您开始将算法移动到更高维度时会出现一些挑战。

问题 1:主路径占用空间小

让我们从一个简单的数学观察开始。级别生成算法的工作原理是计算从世界顶行到世界底行的随机路径。在每一步，该路径可以向左、向右或向下移动，但绝不会退回到起点。假设这三个选项的可能性相等，特定级别的第一步有 2/3 的机会保持在同一级别，随后的每个步骤最多有 1/2 的机会保持在同一级别。 (它是 50%，忽略墙壁)。这意味着每个级别的预期瓷砖数量最多为

1 × (1/3) + (2/3) × (1 + 2) (since there's 1/3 chance to move down immediately, otherwise (2/3) chance to get one room, plus the number of rooms you get from a random process that halts with 50% probability at each step)

= 2.5

这很重要，因为这意味着如果你的世界是一个 n × n 的网格，你希望世界上每层只有大约 2.5 个“使用过的”单元格，而路径上总共有大约 2.5n 个“使用过的”单元格.鉴于世界是 n × n，这意味着 a

2.5n / n² = 2.5 / n

世界的一部分细胞将在主要路径上，因此 n 必须很小，以便世界上不在主要路径上的部分不会变得太大。您链接的视频选择了 n = 4，因此世界上 2.5/4 = 62.5% 的一小部分将在主要路径上。这是“我想取得进步”和“我想要我的支线任务，拜托”之间的完美结合。请记住，这个数字高估了路径单元与支线任务单元的数量。

现在，让我们从三个维度来做这件事。和以前一样，我们从顶部的“切片”开始，然后在每一步随机向前、向后、向左、向右或向下移动。这使我们在第一步时最多有 4/5 的机会保持在我们的水平上，然后从那时起最多有 3/4 的机会保持在水平上。 (同样，这是高估了。)再次进行数学计算可以得出

1 × 1/5 + (4/5) × (1 + 4)

= 1/5 + (4/5) × 5

= 4.2

所以这意味着如果我们高估的话，平均每个级别有 4.2 个单元格将在主路径中，总路径长度为 4.2n，平均而言。在 n × n × n 世界中，这意味着“路径上”站点到“路径外”站点的比例是

4.2n / n³

= 4.2 / n²

这意味着您的世界需要非常小，以便主路径不会成为整个空间的一小部分。例如，选择 n = 3 意味着您将有不到 50% 的世界远离主要路径并可供探索。选择 n = 4 将使您远离主要路径的世界的 75%，而选择 n = 5 将使您远离主要路径的世界的 80%。

所有这一切都是说，马上，您需要减小世界的大小，以便基于主路径的算法不会使世界大部分为空。这不一定是坏事，但需要注意。

问题 2:模板空间增加

您遇到的下一个问题是为房间配置构建"template"库。如果您在 2D 空间中，则每个单元格有四个可能的入口和导出，并且这四个入口的任何子集(可能，完全没有入口的单元格除外)可能需要一个模板。那给你

2⁴ - 1 = 15

可能使用的入口/导出模板，这只是为了涵盖所有可能的选项集。

在三个维度上，每个单元格有六个可能的入口和导出，所以有

2⁶ - 1 = 63

要考虑可能的入口/导出组合，因此您需要大量模板来解决这个问题。您可能可以通过利用旋转对称来减少这种情况，但这是要记住的重要一点。

问题 3:陷入困境

您链接的视频提到 2D 生成算法的优点是

it creates fun and engaging levels that the player can't easily get stuck in.

在 2D 空间中，除了少数异常(exception)，大多数单元格将与主路径相邻。在 3D 空间中，除了少数异常(exception)，大多数单元不会与主路径相邻。而且，在2D空间中，如果迷路了，找回来的路也不难——能走的方向就这么多，一下子就可以看到整个世界。在 3D 中，迷路要容易得多，这既是因为与 2D 空间相比，您可以采取使您远离主要路径的步骤，而且因为如果您迷路了，还有更多选择可以考虑如何回溯。 (另外，您可能无法在 3D 空间中同时看到整个世界。)

您可以通过不使用访问地点填充单元格的完整 3D 空间来解决此问题。相反，只允许在离主要路径一两步远的单元格中填充有趣的支线任务，因为这样玩家就不会在杂草中迷失方向。

总结

这三点表明，要在 3D 中使用这种方法，您可能需要执行以下操作。

保持世界比您认为可能需要的小，因为否则路径上单元格与路径外单元格的比率会变大。

或者，只考虑填充与主路径相邻的单元格，而其他单元格无法访问，以便玩家可以快速返回到之前的位置。

准备好创建大量模板，或者弄清楚如何使用旋转使您的模板适用于更多地方。

祝你好运!