|
3.保证地图的强连通性
当生成一条由起点到终点的随机路线后，地图上仍有封闭的区域，为了尽可能多地生成一些“死”路，用于迷惑玩家，需要生成强连通图。强连通图的概念是，在一个有向图G中，对于G的任意两个不同的顶点vi和vj，都存在从vi到vj以及从vj到vi的路径。因此，需要遍历地图上所有未赋值的点，随机地为这些点赋值，生成更多的路线，注意赋值应大于1000，以便区分上一步得到的那些表示通路的块，如图3所示。
|
-1 |
-1 |
-1 |
-1 |
-1 |
-1 |
-1 |
-1 |
|
-1 |
1003 |
21 |
20 |
19 |
18 |
17 |
-1 |
|
-1 |
9 |
10 |
11 |
12 |
13 |
16 |
-1 |
|
-1 |
8 |
5 |
4 |
1002 |
14 |
15 |
-1 |
|
-1 |
7 |
6 |
3 |
2 |
1 |
1001 |
-1 |
|
-1 |
-1 |
-1 |
-1 |
-1 |
-1 |
-1 |
-1 |
图3 生成强连通路
4.画出迷宫
现在，已经得到了表示迷宫的数据，下面的任务就是把迷宫画出来。在平面图中用线段表示迷宫中的围墙，因此迷宫可用画线的方法画出。首先，设置两个二维数组HWall[][]和VWall[][]，分别表示水平方向的线段和垂直方向的线段。例如，HWall[i][j]表示块（i-1,j）和块(i,j)之间是否有连线，然后，根据相邻块的数值决定HWall或VWall的值，以图3为例，块(3,1)的值为20，块(4,1)的值为19，两值相差1，两块连通，于是HWall[i][j]=0，表示不用画线，块(1,3)的值为8，块(2,3)的值为5，差值大于1，两块不通，于是HWall[i][j]=1，表示需要画线。
二、程序实现
下面给出迷宫的程序实现。选用VC++6.0作为程序开发平台，建立基于对话框的工程。程序设计的关键是，（1）编写迷宫类CMaze，用于实现生成迷宫的算法；（2）编写在对话框中显示迷宫的代码；（3）编写人机交互代码，即玩家可以使用方向键控制目标在迷宫中移动。
1.迷宫类CMaze
迷宫类CMaze的定义如下：
class CMaze : public CObject
{
public:
CMaze();
virtual ~CMaze();
int ** InitWall(int ,int); //初始化迷宫中的围墙
int SetMaze(int **Maze,int s,int x,int y); //设置迷宫中的路径
int **CreateMaze(); //创建迷宫
int DestroyMaze(); //销毁迷宫
BOOL InitMaze(); //初始化迷宫
|
