为游戏地图构建有向图的好策略是什么(在Python中)？

我正在用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关联,并相应地接收更多标签; 等等

如果建议的策略能够实现数据驱动的实施,则奖励积分.

首先,您需要一些位置感.您的各种对象占用了一定的坐标空间.

你必须决定这些不同的东西是多么规律.在简单的情况下,您可以将它们作为简单的矩形(或矩形实体)放入坐标空间,以使位置更容易规划.

如果事情不规则 - 而且密集 - 生活有点复杂.

定义Map以包含位置.每个位置都有一个坐标范围; 如果你使用简单的矩形,那么每个位置都可以有一个(左,上,右,下)元组.

您的地图需要方法来确定谁住在给定的空间,以及与空间相邻的内容等.

然后,您可以使用一组固定的位置进行单元测试,这些位置可以全部放入地图中,并为非冲突,相邻等传递一些基本的健全性检查.

其次,你需要一种"迷宫发生器".简单连接的迷宫很容易生成一个折叠到给定空间的树形结构.

迷宫/树有一个"根"节点,它将成为迷宫的中心.不一定是你的空间的物理中心,但根节点将是迷宫结构的中间.

理想情况下,此节点的一个分支包含整个空间的一个"入口".

此节点的另一个分支包含整个空间的一个"出口".

有人可以从入口到出口漫步,沿途可以参观很多"死胡同"的地方.

为根节点选择一种空间.将其放入地图空间.

这将有1到n个入口,每个入口都是一个带有根节点和1到n个入口的子树.正是这种多入口业务使树木成为这种结构的自然之选.另外,正确的树总是连接良好,因为您永远不会有无法到达的孤立部分.

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

对此进行单元测试以确保其填充空间相当合理.

其余的要求是对迷宫发生器选择位置的方式进行微调.

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

您对空间的定义可以是2D或3D - 两者都非常合理.对于奖励积分,请考虑如何实现平铺六边形而不是正方形的二维空间.

这种"几何"可以是各种算法的策略插件.如果您可以用六边形2D替换方形2D,那么您已经很好地完成了OO设计.