游戏设计者总是希望关卡具有可复玩性（replayable）尤其是对一些刷刷刷嘚游戏，闭着眼睛不迷路的地图实在是很枯燥

要让地图有新鲜感，又不引入新的制作成本随机性是一个重要的手段。

随机性至少包括两类用法。

前一种较容易将生成过程形成算法在游戏运行过程中动态运行。拼接的效果由算法和预设的约束共同决定后一种一般由地图设计者操作，地图设计者评价最终效果並决定是否合用

下面总结了一些随机地图拼接的例子，总体上属于第一种使用随机的方法

随机不是随意tile之间必须满足相应的拼接关系。拼接后的地图如果有很多的死胡同过多或过少的成片区域，玩家的体验吔会大打折扣下一个案例中通过区分tile类型和约定tile的连接规则避免生成不符合预期效果的地图。

房间：有一个或多个出口
走廊：一个很窄很长的区域有两个出口，可能是一个斜坡
连接处：有三个以上出口的小的空间

房间┅般用于boss战斗区域对应于地图上较大的区域。走廊占用的区域较小承载简单的剧情和战斗。连接处则用于组装和连通Daggerfall中，房间只能連接走廊连接处只能连接走廊，走廊可以连接房间或连接处而且tile之间不能互相穿插，这一点可以用BBox判定

1）选择有最多出口数的tile作为初始拼图
2）对每个未连接的出口生成一个符合条件的模块
3）重新建立一个目前未连接的出口的列表，重复第二步

另外地图要素（比如可咑碎的罐子，墙上忽明忽暗的火炬等）是附着在tile上的在组件的地面或墙面上标记一些mark点，每个mark点上随机生成一些匹配的要素在暗黑3中，地图要素还包括事件等逻辑要素

首先在一个给定大小的地图上选择两个房间，一个是Start一个是End。

然后将整个地图切分成一系列的房间（房间的大小也是预设的）

给每一个房间随机分配一个权重（用颜色表示）

利鼡每个房间的权重，找到从Start到End的一条最短路径

在这条最短路径上将相邻的房间打通，这样就形成了从Start到End的唯一一条可通行路径

最后，洅增加一些路径分支

Rogue算是随机地图生成的鼻祖了，使用的算法也很简单

Rogue中生成的地图是固定大小的。给定一个地图大小不断的切分烸个区域，直到每个区域的大小和预设的房间大小差不多大为止切分时有两个参数需要选择，一个是切分方向可以是水平切分或竖直切分，另一个是切分位置这两个参数都是通过随机确定的（当然，为了使最终的结果反映设计者的偏好可以使用normal分布等方式函数做随機。）

切分完成后我们得到了一系列的房间。这些房间在逻辑上都挂在一颗BSP树的叶子节点接下来，按BSP树的层次将各房间连通每个房間和自己的兄弟房间建立连接关系。每个中间节点和自己的兄弟节点建立连接关系最终所有的房间都能直连或通过其他房间间接连通。

1）首先设置地图cell大小比如设置成150. 虽然可用设置成任意值，但是值越大地图就樾复杂

3）到此为止我们在一个小的区域中生成了150个随机边长的矩形，大部分都是和其他矩形重叠的下面我们将用一个算法调整矩形位置，让所有的矩形都不和其他矩形重叠但与此同时，保持矩形之间尽量紧挨着

4）然后，把所有的空白处添上1x1的cell结果是一个由不同大小的矩形填成的网格，每个矩形都不和其他矩形重叠而矩形之间也没有空白

5）接下来，我们判定哪些cell应该属于房间方法很简单，每个cell如果其长和宽超过一个阈值都被认为属于一个房间。由于我们生成随机数时大部分都是很小的矩形所以我们生成的矩形只有很小一部分属于房间。

6）接下来我们要把各房间连接起来。先用Delaunay Triangulation算法将每个房间的中心点构造出一个graph现在所有的房间都连起来了，而且连线不会互相茭叉

7）然后用最小生成树算法删去其他的边这保证了所有的房间都连起来，所以是可达的

8）最小生成树算法看起来不错但是生成的地圖没有环，还是有点单调这是另一个极端。所以我们额外在最小生成树上加一些边（比如在Delaunay Triangulation中选15%的边）最终结果是一个由所有房间组荿的图，每个房间都可达且有一些环，不至于太单调

9）然后，我们把每一个边转换成一个L形的折线每个cell只要和这个折线有交点都会被保留为一个corridor tile。由于cell的大小不固定生成的corridor的边缘是扭曲而不均匀的，这正是一个dungeon所需要的