language-agnostic - 领土地图生成

Question

是否有一种微不足道的或至少适度直接的方式来生成领土地图（例如风险）？

我过去看过，我能找到的最好的是对 Voronoi 图的模糊参考。Voronoi 图的示例如下：

.

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

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

任何建议将不胜感激。

Answer 1

我在它们上看到的最好的参考资料是Computational Geometry: Algorithms and Applications，它涵盖了 Voronoi 图、Delaunay 三角剖分（类似于 Voronoi 图，每个都可以转换成另一个）和其他类似的数据结构。

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

抱歉，只有书可以推荐！我在它们上看到的唯一不错的在线资源是两篇Wikipedia 文章，它们并没有真正告诉您实现细节。不过，此链接可能会有所帮助。

Answer 2

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

Answer 3

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

Answer 4

我实际上正在为我公司的视频游戏处理这类东西。我发现的最有用的信息在这两个链接中：

Paul Bourke在西澳大学的页面，以及他 1989 年关于 Delaunay 的论文和一系列实施链接。

在codeGuru.com 上对伪代码和Delaunay 进行了很好的解释。

在渲染这些方面 - 我发现的大多数实现都需要按摩以获得你想要的东西，但是由于将它用于游戏地图会导致它们之间有许多点加线，这可能是一个非常做简单的事情把它画到屏幕上。