构建游戏地图有向图（Python）的好策略是什么？
我正在用 Python 开发一个程序生成的游戏世界。 世界的结构将类似于房间和出口排列为有向图的 MUD/MUSH 范例（房间是节点，出口是边）。 （请注意，这不一定是非循环图，尽管我愿意考虑非循环解决方案。）
对于世界生成算法，不同类型的房间将通过每个房间的“标签”属性来区分（一组字符串）。 一旦实例化，就可以通过标签（单标签、标签交集、标签联合、最佳候选）查询和选择房间。
我将使用模板对象和工厂方法的美化系统来创建特定类型的房间——我认为细节在这里并不重要，因为当前的实现可能会改变以匹配所选的策略。 （例如，可以向房间模板系统添加标签和标签查询。）
例如，我将拥有以下类型的房间：
side_street,main_street, plaza, bar, hotel, restaurant, shop, office
最后的问题是：实例化和排列这些房间以创建可能对应于给定规则的图表的好策略是什么？
一些规则可能包括： 每 10,000 人拥有一个广场； main_street 连接到 plaza； side_street 连接到 main_street 或 side_street； hotel 倾向于 main_street 或 plaza 连接，并相应地接收更多标签； 。
如果建议的策略能够实现数据驱动的实施，则可获得加分
I'm developing a procedurally-generated game world in Python. The structure of the world will be similar to the MUD/MUSH paradigm of rooms and exits arranged as a directed graph (rooms are nodes, exits are edges). (Note that this is not necessarily an acyclic graph, though I'm willing to consider acyclic solutions.)
To the world generation algorithm, rooms of different sorts will be distinguished by each room's "tags" attribute (a set of strings). Once they have been instantiated, rooms can be queried and selected by tags (single-tag, tag intersection, tag union, best-candidate).
I'll be creating specific sorts of rooms using a glorified system of template objects and factory methods--I don't think the details are important here, as the current implementation will probably change to match the chosen strategy. (For instance, it would be possible to add tags and tag-queries to the room template system.)
For an example, I will have rooms of these sorts:
side_street,main_street, plaza, bar, hotel, restaurant, shop, office
Finally, the question: what is a good strategy for instantiating and arranging these rooms to create a graph that might correspond to given rules?
Some rules might include: one plaza per 10,000 population; main_street connects to plaza; side_street connects to main_street or side_street; hotel favors main_street or plaza connections, and receives further tags accordingly; etc.
Bonus points if a suggested strategy would enable a data-driven implementation.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
首先，您需要一些位置感。 您的各种对象占据一定量的坐标空间。
你必须决定这些不同的事情有多规律。 在简单的情况下，您可以将它们作为简单的矩形（或长方体）放入坐标空间中，以使位置更易于规划。
如果事物不规则且密集，生活就会变得更加复杂。
定义一个地图来包含位置。 每个位置都有一个坐标范围； 如果您使用简单的矩形，那么每个位置都可以有一个（左、上、右、下）元组。
您的地图将需要方法来确定谁居住在给定空间中，以及与该空间相邻的区域等。然后，
您可以使用您已经计算出的一组固定位置进行单元测试，这些位置都可以放入地图中，并且通过一些基本的健全性检查，以确保不冲突、相邻等。
其次，你需要一种“迷宫生成器”。 简单连接的迷宫很容易生成为折叠到给定空间的树结构。
迷宫/树有一个“根”节点，它将成为迷宫的中心。 不一定是空间的物理中心，但根节点将是迷宫结构的中间。
理想情况下，该节点的一个分支包含整个空间的一个“入口”。
该节点的另一个分支包含整个空间的一个“出口”。
有人可能会从入口走到出口，沿途参观了许多“死胡同”的地方。
为根节点选择一种空间。 将其放入您的地图空间中。
这将有 1 - n 个入口，每个入口都是一个带有根节点和 1 - n 个入口的子树。 正是这种多入口业务使树非常适合这种结构。 此外，一棵合适的树总是连接良好的，因为永远不会有无法到达的孤立部分。
您将从根节点递归地扇出，选择位置并将它们放入可用空间中。
对其进行单元测试，以确保它能够很好地填充空间。
您的其余要求是根据迷宫生成器选择位置的方式进行微调。
最简单的是有一个权重表和随机选择。 选择一个随机数，将其与权重进行比较，以查看识别出哪种位置。
你对空间的定义可以是 2D 或 3D——两者都是相当合理的。 为了获得奖励积分，请考虑如何实现用六边形而不是正方形平铺的 2D 空间。
这个“几何”可以是各种算法的策略插件。 如果你能用二维六边形代替二维正方形，那么你就已经完成了良好的 OO 设计。
First, you need some sense of Location. Your various objects occupy some amount of coordinate space.
You have to decide how regular these various things are. In the trivial case, you can drop them into your coordinate space as simple rectangles (or rectangular solids) to make locations simpler to plan out.
If the things are irregular -- and densely packed -- life is somewhat more complex.
Define a Map to contain locations. Each location has a span of coordinates; if you work with simple rectangles, then each location can have a (left, top, right, bottom) tuple.
Your Map will need methods to determine who is residing in a given space, and what's adjacent to the space, etc.
You can then unit test this with a fixed set of locations you've worked out that can all be dropped into the map and pass some basic sanity checks for non-conflicting, adjacent, and the like.
Second, you need a kind of "maze generator". A simply-connected maze is easily generated as a tree structure that's folded up into the given space.
The maze/tree has a "root" node that will be the center of the maze. Not necessarily the physical center of your space, but the root node will be the middle of the maze structure.
Ideally, one branch from this node contains one "entrance" to the entire space.
The other branch from this node contains one "exit" from the entire space.
Someone can wander from entrance to exit, visiting a lot of "dead-end" locations along the way.
Pick a kind of space for the root node. Drop it into your Map space.
This will have 1 - n entrances, each of which is a sub-tree with a root node and 1 - n entrances. It's this multiple-entrance business that makes a tree a natural fit for this structure. Also a proper tree is always well-connected in that you never have isolated sections that can't be reached.
You'll -- recursively -- fan out from the root node, picking locations and dropping them into the available space.
Unit test this to be sure it fills space reasonably well.
The rest of your requirements are fine-tuning on the way the maze generator picks locations.
The easiest is to have a table of weights and random choices. Choose a random number, compare it with the weights to see which kind of location gets identified.
Your definition of space can be 2D or 3D -- both are pretty rational. For bonus credit, consider how you'd implement a 2D-space tiled with hexagons instead of squares.
This "geometry" can be a Strategy plug-in to the various algorithms. If you can replace square 2D with hexagonal 2D, you've done a good job of OO Design.
查看关于 The MUD Connector 的讨论 - 有一些关于世界布局和生成以及不同类型的精彩讨论“高级编码和设计”（或类似）论坛中的坐标/导航系统。
Check out the discussions on The MUD Connector - there are some great discussions about world layout and generation, and different types of coordinate / navigation systems in the "Advanced Coding and Design" (or similar) forum.