生成随机聚类和路径的好方法是什么？

Question

我是一名有用的助手，可以为您翻译以下内容：

我正在尝试编写一个随机地图生成器，但不确定如何随机生成逼真的地形。我正在处理这些类型的局部地图，这带来了一些有趣的问题。

其中最简单的情况之一是森林:

                    Sparse  Medium  Dense
Typical trees       50%     70%     80%
Massive trees       —       10%     20%
Light undergrowth   50%     70%     50%
Heavy undergrowth   —       20%     50%

树木和灌木可以共存于同一空间，因此平均稀疏森林有25%的典型树木和轻度灌木丛、25%的典型树木、25%的轻度灌木丛和25%的开阔空间。中等和密集的森林需要更多思考，但问题不在于这里，因为它们都是均匀分布的。

我的问题在于生成聚类和路径，同时保持百分比约束。沼泽地 是一个很好的例子：

                    Moor  Swamp
Shallow bog         20%   40%
Deep bog            5%    20%
Light undergrowth   30%   20%
Heavy undergrowth   10%   20%

深泥坑通常聚集在一起，并被浅泥坑的不规则环包围。

另外一个地图元素——树篱，可能也存在，以及一条穿过沼泽的开放地路径。这两种地图元素（聚集和路径）都存在问题，因为地图的总体组成应该包含X％的元素，但它们并不均匀分布。其他元素，如小溪、池塘和流沙，也需要聚集或路径类型的生成。

在这些限制条件下，我可以使用什么技术来生成逼真的地图？

---

我正在使用C#，供您参考（但这不是一个特定于C#的问题）。

- dlras2

---

这些是基于网格的地图吗？从您的描述或链接中我无法确定。 - academicRobot

是的，基于网格的，可能不小于20x20（尽管更可能更大，大约50x50左右？） - dlras2

Answer 1

实现真实的“随机”分布通常使用Perlin Noise，它可以用于生成像您提到的“块状”分布。它通过将来自随机数据点的多个线性插值值的多个层次（或“八度”）相加/组合。每个层次都比上一个层次多两倍的数据点，并且限制在更窄的值范围内。结果看起来是“逼真”的随机纹理。

这里有一个由Hugo Elias漂亮演示的Perlin Noise背后的理论。

这是我在C#中的Perlin Noise上找到的第一件事。

您可以生成一个Perlin Noise图像并设置“阈值”，其中任何高于某个值的内容都是“开启”的，而低于该值的则是“关闭”的。这样会形成具有不规则和可观的“块状”形态的区域。只需将高于阈值的部分指定为您想要的地形特征即可。

这里是演示一个程序如何生成Perlin噪声位图，并随着时间调整截止阈值。可以看到明显的“聚集”。这可能正是你想要的。

请注意，对于高阈值，很少有点在其上方，而且它们是稀疏的。但是随着阈值降低，这些点会“成长”为聚集（通过Perlin噪声的本质），其中一些聚集将彼此连接，并创建非常自然和地形般的东西。

请注意，您还可以通过设置Perlin Noise函数的“湍流”来设置“聚集因子”或特征聚集的倾向，这基本上会导致您的PN函数的峰值和谷底被强调并更加接近。

现在，该在哪里设置阈值呢？阈值越高，最终地图上的特征百分比就越低。阈值越低，百分比就越高。您可以尝试进行调整。您可能可以通过稍微调整一下数学公式来获得精确的百分比（似乎值的分布遵循正态分布；我可能是错的）。调整它，直到它完美无缺 :)

编辑 如评论所指出的那样，您可以创建累积直方图（处于阈值以下的地图百分比索引），并选择给您所需百分比的阈值。

这里最酷的事情是，你可以在特定的其他特征（例如沼泽特征）周围轻松创建聚集的特征，只需使用相同的Perlin噪声地图两次 - 第二次降低阈值。第一个将是聚集的，第二个将在相同的区域周围聚集，但聚集会变大（请参考早期发布的Flash动画）。

至于其他特征，如树篱，您可以尝试建模简单的随机行走线条，这些线条更容易直线前进而不是转弯，并随机放置在基于Perlin的地图上的任何位置。

---

示例

这是一个50x50的稀疏森林地图样本。灌木丛为褐色，树木为蓝色（抱歉），以便清楚区分。

对于这张地图，我没有制定精确的阈值来匹配50％；我只将阈值设置为最大值的50％。从统计学角度来看，这将平均每次恰好达到50％。但是这可能不足以满足您的要求；请参见早期注释以了解如何做到这一点。

---

这是您的沼泽功能的演示（不包括下层植被，以保持清晰），浅色沼泽为灰色，深色沼泽为黑色：

这只是一个50x50的示例，因此存在一些伪影，但您可以看到通过调整同一Perlin地图上的阈值，您可以轻松地使浅水沼泽“生长”成深水沼泽。对于这个示例，我通过目测阈值水平来获得最美观的结果，但是对于您自己的目的，您可以按照之前提到的做法进行操作。

这是从相同的Perlin噪声地图中生成的沼泽地图，但在250x250平铺地图上拉伸：

- Justin L.

Answer 2

我从未做过这种事情，但以下是一些想法。

您可以通过将随机选择偏向于与该类型现有元素接近的网格位置来获得聚类。将所有正方形的默认值设为1。对于具有现有聚类元素的正方形，将聚类值添加到相邻的正方形中（聚类值越高，聚类就越强）。然后，在所有正方形的概率分布函数上进行下一个该类型元素的随机选择。

对于路径，您可以采用类似的程序，只是路径会逐步扩展（路径在靠近路径末端的正方形处的概率有限，在其他地方为零）。定向路径可以通过增加沿路径方向的选择概率来完成。蜿蜒的路径可能会在随机扩展过程中改变方向（新方向= mf *旧方向+（1-mf）* rand_direction，其中mf是0到1之间的动量因子）。

- academicRobot

Answer 3

为了进一步解释academicRobot的评论，您可以从一些网格单元格中的默认沼泽或森林种子开始，并使用相关的随机数让它们从源头生长。例如，沼泽可能有八个相邻的网格单元格，每个单元格有90％的概率也是沼泽，但有10％的概率是其他东西。您可以让生态系统从种子形成，并调整相关性，直到获得看起来正确的东西。即使在电子表格中，这也可能非常容易实现。

- Grembo

Answer 4

你可以从这里开始阅读链接。我记得看到了更好的文档。如果我找到它，我会发布的（它也基于L系统）。

但这是一般性的；对于你面临的特定问题，我想你应该用以下术语建模：

• 百分比
• 其他规则（聚类和路径）

关键是，即使你不知道如何构建具有给定属性的地图，如果你能够评估属性（聚类比率；路径美观度）并对其进行评分，那么你就可以粗略地强制执行或进行一些其他问题空间遍历。

如果你仍然想采用生成式方法，那么你将不得不更仔细地研究生成规则；这里是一个我会追求的想法：

• 创建具有所需“聚集性”、“路径性”或均匀性属性的不同地形和地形覆盖的模式
• 以这样的方式创建模式，使得深泥沼的值不是离散的，而是分配概率值；在创建模式后，你可以将这种概率归一化，以产生所需的覆盖百分比
• 混合不同的模式

- Unreason

Answer 5

对于某些类型的区域，您可能会使用 Voronoi模式取得一定的成功。我从未见过它用于创建地图，但我在许多类似领域中看到过它的应用。

- Ian Turner