随机地图生成浅析

·使用《英雄无敌》用脚本和模版做随即扩展的地图，实现成本和时间复杂度也很高，我们游戏不也不需要mod扩展。

·地下城类似的封闭空间的二维迷宫地图，其tile组织结构和我们需求非常类似。实现和时间复杂度都在可控范围内。

所以，抛弃上流和华丽的浮云，我们先从满足最基本需求入手，快速开发一个原型来验证我们的gameplay。

2、技术原型

一个二维的M*N矩阵，矩阵中每一项为0表示不可通过，1表示可通过。通过算法在该矩阵中生成一个全连通(每个可通过节点到另一个可通过节点有且只有一个通路)的拓扑树(树的定义？在图论中，树是任意两个顶点间有且只有一条路径的图。或者说，只要没有回路的连通图就是树)。

遍历树的算法：深度优先遍历或广度优先遍历每一个tx的程序员在学习数据结构时都应该有所了解，(忘了？请参考 深度优先搜索)。

生成全连通的迷宫就是求解一个随机生成树。可以使用某一遍历方法遍历寻访以下图中的空白节点，并将访问过程中经过的非空白节点清为路径。当每个空白节点都访问到了，迷宫就生成了。