2

我正在尝试随机生成一个有向图，以制作类似于口袋妖怪的冰滑谜题的益智游戏。

这基本上是我希望能够随机生成的：http://bulbanews.bulbagarden.net/wiki/Crunching_the_numbers: _Graph_theory

我需要能够在 x 和 y 维度上限制图形的大小。在链接中的示例中，它将被限制为 8x4 网格。

我遇到的问题不是随机生成图形，而是随机生成一个图形，我可以在 2d 空间中正确绘制该图形，因为我需要在节点的另一侧有一些东西（比如石头）来制作它当你停止滑动时，视觉上是有意义的。这样做的问题是，有时岩石最终会出现在其他两个节点之间的路径中，或者可能位于另一个节点本身上，这会导致整个图被破坏。

在与我认识的几个人讨论了这个问题之后，我们得出了一些可能导致解决方案的结论。构建时将网格中的障碍物作为图形的一部分。从一个完全填充的网格开始，然后绘制一条随机路径并删除可以使该路径正常工作的块，尽管问题随后变成了找出要删除哪些块，这样您就不会意外引入额外的更短的路径。我们还认为动态规划算法可能是有益的，尽管我们都不太擅长从无到有创建动态规划算法。关于这个问题的正式名称（如果它是官方图形问题）的任何想法或参考将是最有帮助的。

4

2 回答 2

0

我不会将其视为图形问题，因为正如您所说，表示是不完整的。要生成一个谜题，我会直接在网格上工作，然后向后工作；首先固定目标点，然后以某种方式放置石头以从一个或多个点到达它，并迭代地添加石头以到达其他点，约束条件是您永远不会添加破坏所有路径的石头到目的地。

于 2012-02-25T11:51:18.897 回答
0

您可能想要生成一个平面图，这意味着该图的边缘不会在二维空间中相互重叠。平面图的另一个定义是每个平面图没有任何类型为 K_3,3（具有六个节点的完全二分图）或 K_5（具有五个节点的完全图）的子图。

有一篇关于平面图的快速生成的论文。

于 2012-06-29T14:03:22.253 回答