领土地图生成

Question

是否有一种简单的或至少相当直接的方法来生成领土地图（例如风险）？

我回顾过过去，我能找到的最好的就是对 Voronoi 图的模糊引用。Voronoi 图的一个示例如下：

.

这些很有希望，但我想我还没有看到任何直接的渲染它们的方法，更不用说以某种形式的数据结构保存它们以将每个区域视为一个对象。

另一种有希望的方法是洪水填充，但我再次不确定开始这种方法的最佳方法。

任何建议将不胜感激。

Answer 1

我见过的关于他们的最好的参考是 计算几何：算法与应用, ，其中涵盖了 Voronoi 图、Delaunay 三角剖分（类似于 Voronoi 图，并且可以相互转换）以及其他类似的数据结构。

他们讨论了您需要的所有数据结构，但没有为您提供实现它所需的代码（这可能是一个很好的练习）。在代码方面，亚马逊搜索显示了这本书 C 中的计算几何, ，它可能随代码一起提供（尽管由于您被困在 C 语言中，您也介意获得另一个并用您想要的任何语言实现它）。我对这本书也没有任何经验，只有第一本。

抱歉，只有书籍可以推荐！我见过的唯一像样的在线资源是两个 维基百科 文章, ，它并没有真正告诉您实现细节。 这个链接 不过可能会有帮助。

Answer 2

为什么不使用基元地图（三角形、正方形），分配国家/地区的起点（“首都”），然后通过向国家/地区添加随机相邻基元来随机扩展国家/地区。

Answer 3

CGAL 是一个 C++ 库，具有计算几何中使用的数据结构和算法。

Answer 4

事实上，我正在为我公司的视频游戏处理这类事情。我发现的最有用的信息位于这两个链接：

保罗·伯克在 UWA 的页面，其中包含他 1989 年关于 Delaunay 的论文以及一系列实施链接。

A 对伪代码和视觉效果的很好的解释 在 codeGuru.com 上做 Delaunay 的经历。

在渲染这些方面 - 我发现的大多数实现都需要按摩才能获得您想要的东西，但由于将其用于游戏地图会导致许多点加上它们之间的线，因此这可能是一个非常大的问题将其绘制到屏幕上很简单。