玩过RPG游戏的朋友一定遇到过各种各样的迷宫，迷宫道路错综复杂，千变万化，如《仙剑奇侠传》，那么这些迷宫是怎样生成的呢？生成迷宫的算法又是什么呢？下面就给出一个随机生成二维迷宫的方法，并用VC编程实现。

一、随机生成迷宫的方法

迷宫的本质就是一幅地图，因此程序的核心问题就是如何生成一幅二维地图。步骤如下：首先，生成地图的框架，即定义地图的大小，得到地图的外围边界；其次，在图中生成一条连接起点和终点的通路，保证玩家可以走出迷宫；然后，保证地图的强连通性，在图中尽可能多地生成一些围墙，构成多条“死”路，用于迷惑玩家；最后，用连线的方法画出迷宫。下面分别介绍各步骤的实现方法。

1.生成地图的框架

普通的地图都是按块来划分的，定义一个平面地图的大小其实只需定义一个二维数组即可，比如说定义一个6*4的地图，那么就得定义一个[4][6]的数组，数组的数据表示地图中的块，再加上地图的边界，所以一个ySize*xSize的地图由(xSize+2)*(ySize+2)个块构成，如图1所示。为图中每个块赋一个数值，表示块与块之间是否连通。外围的块赋值为-1，表示地图的边界，中间的块赋值为0，表示初始状态。

2.生成一条连接起点和终点的通路

    如图2所示，编号为1的块表示迷宫的起点，编号为21的块表示迷宫的终点，即玩家需要从地图的右下方走到左上方。设起点的坐标是（x1,y1），终点的坐标是(x2,y2)，(x,y)表示一个在图中移动的点，(x,y)的初始值等于起点坐标，即x=x1，y=y1，s代表点(x,y)移动的步数，s初始值为1，然后点（x,y）就从迷宫的起点开始移动，上、下、左、右方向分别由数值0、1、2、3表示，每走一步的方向由随机数0、1、2、3决定。如果有路可走，即前进方向的块的数值为零，则前进到新的块，并令s=s+1，将s赋值给新块。如果四周均已无路可走(四周无数值为零的变量)，则退回到s-1处，寻找s-1四周的变量还有没有路可走(s-1代表来时的路)，如找到，则s=s-1，并且退回先前位置，继续找路前进，否则便结束算法。如果点(x,y)已经到达终点，同样会结束算法。图2表示了一条按此算法随机生成的通路，由图2中的阴影方块表示，方块1为起点（x1,y1），方块21为终点（x2,y2），数值相差为1的方块连通，按数值递增1的顺序，从编号为1的方块到编号为21的方块，恰好生成一条通路。