我正在用 Java 编写类似 Risk 的棋盘游戏。一个特点是玩家可以设计自己的 map ，并将其存储在文本文件中。该文本文件列出了世界地图中的所有领土(== 国家)及其直接邻居。然后，游戏会扫描该文件并创建一个区域集合及其相应的邻接列表。
下一步是将此图转换为图形表示。这意味着我想用矩形或其他一些简单的形状来表示每个区域。我还不想进入领土之间复杂、前卫的边界。所以基本上这些领土看起来像一些具有水平和垂直边界的非洲或北美国家。
现在我的问题是:虽然很容易想象一个图形，其中边界由它们之间的绘制边表示，但我发现很难将区域(== 顶点)彼此直接相邻放置。换句话说，领土应该像在现实世界中一样相互“接触”。
尤其是在这样的地方，有 4 个或更多的领土彼此接壤(考虑美国的四个角落，亚利桑那州、科罗拉多州、新墨西哥州和犹他州)，这很困难。
现在我想知道是否有人曾尝试过类似的事情，或者是否存在处理此问题的现有算法。我将不胜感激任何帮助和创造性的投入。谢谢!
最佳答案
如果您可以使用图形布局工具(如 graphviz)来获得图形的平面投影，那么您可以考虑计算图形上各点的 voronoi 图，然后您可以对其进行扭曲以使事情在视觉上更有趣。 (您可能还需要注意确保在计算 voronoi 图时不会最终更改邻接属性，因为它取决于点的相对间距。您可能还必须检测为了使两个领土不相邻，必须插入“海洋”单元格。)
关于算法:从邻接表到视觉 map ，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/5074024/