构建游戏地图有向图（Python）的好策略是什么？

Question

我正在用 Python 开发一个程序生成的游戏世界。世界的结构将类似于房间和出口排列为有向图的 MUD/MUSH 范式（房间是节点，出口是边缘）。（请注意，这是 不是 必然是一个非循环图，尽管我愿意考虑非循环解决方案。）

对于世界生成算法，不同类型的房间将通过每个房间的“标签”属性（一组字符串）来区分。一旦实例化，就可以通过标签（单标签、标签交集、标签联合、最佳候选）查询和选择房间。

我将使用模板对象和工厂方法的美化系统来创建特定类型的房间——我认为细节在这里并不重要，因为当前的实现可能会改变以匹配所选的策略。（例如，可以向房间模板系统添加标签和标签查询。）

例如，我将拥有以下类型的房间：

side_street, main_street, plaza, bar, hotel, restaurant, shop, office

最后，问题：实例化和排列这些房间以创建可能符合给定规则的图表的好策略是什么？

一些规则可能包括：每万人拥有一个广场； main_street 连接到 plaza; side_street 连接到 main_street 或者 side_street; hotel 恩惠 main_street 或者 plaza 连接，并相应地接收更多标签；ETC。

如果建议的策略能够实现数据驱动的实施，那就加分。

Answer 1

首先，您需要一些位置感。您的各种对象占据一定量的坐标空间。

你必须决定这些不同的事情有多规律。在简单的情况下，您可以将它们作为简单的矩形（或长方体）放入坐标空间中，以使位置更易于规划。

如果事物不规则且密集，生活就会变得更加复杂。

定义一个地图来包含位置。每个位置都有一个坐标范围；如果您使用简单的矩形，那么每个位置都可以有一个（左、上、右、下）元组。

您的地图将需要方​​法来确定谁居住在给定空间中，以及该空间附近有什么，等等。

然后，您可以使用您已经计算出的一组固定位置进行单元测试，这些位置都可以放入地图中，并通过一些基本的健全性检查以确保不冲突、相邻等。

---

其次，你需要一种“迷宫生成器”。简单连接的迷宫很容易生成为折叠到给定空间的树结构。

迷宫/树有一个“根”节点，它将成为迷宫的中心。不一定是空间的物理中心，但根节点将是迷宫结构的中间。

理想情况下，该节点的一个分支包含整个空间的一个“入口”。

该节点的另一个分支包含整个空间的一个“出口”。

有人可能会从入口走到出口，沿途参观了许多“死胡同”的地方。

为根节点选择一种空间。将其放入您的地图空间中。

这将有 1 - n 每个入口都是一个子树，有一个根节点和 1 - n 入口。正是这种多入口业务使树非常适合这种结构。此外，一棵合适的树总是连接良好的，因为永远不会有无法到达的孤立部分。

您将从根节点递归地扇出，选择位置并将它们放入可用空间中。

对其进行单元测试，以确保它能够很好地填充空间。

---

您的其余要求是根据迷宫生成器选择位置的方式进行微调。

最简单的是有一个权重表和随机选择。选择一个随机数，将其与权重进行比较，以查看识别出哪种位置。

---

你对空间的定义可以是 2D 或 3D——两者都是相当合理的。为了获得奖励积分，请考虑如何实现用六边形而不是正方形平铺的 2D 空间。

这个“几何图形”可以是 战略 各种算法的插件。如果你能用二维六边形代替二维正方形，那么你就已经完成了良好的 OO 设计。

Answer 2

查看关于 MUD连接器的讨论 - 有关于世界布局和生成的一些很好的讨论，以及“高级编码和设计”中的不同类型的坐标/导航系统。 （或类似的）论坛。