OpenGL——随机迷宫生成问题

这个东西不难，但由于思路的理清和OpenGL的不太熟练，还是让我断断续续的弄了几天。

这是我的策略：

1、画网格线。

2、生成一系列的cell[][]作为单元格

3、定义吃墙老鼠，让老鼠先从cell[0][0]出发，采取随机顺序的策略来吃墙（方向我用rand()来表示。。。好吧，我承认这是个伪随机数 |||= =），到[VERTICAL_NUMBER-1][HORIZONTAL_NUMBER-1]。
其中，VERTICAL_NUMBER和HORIZONTAL_NUMBER是纵向格子数和横向格子数。

被吃过的格子标记已吃过，并标记那个方向的墙吃过,同时标记原来的墙的位置如果这个cell出现了周围所有的墙都吃过的情况，就需要退回原来的墙来操作。对了，还需要考虑一下在四个顶角的情况。

4、对吃掉的墙用覆盖底色的操作来进行迷宫的填充。

整个思路走下来，其实就是个算法问题，OpenGL并不很多，玩一玩，图个乐子~
后来我索性利用双缓存做成了一个简单的动画效果，每一步延迟500ms，写出来以后，看着小老鼠一步一步吃墙的效果，我觉得自己非常无聊，果断恢复。。。

以下是效果图：（左下角是出口，右上角是入口，分别用缺口来表示）

下面着重一下存在的问题——伪随机性。
对的，虽然用rand来随机出小老鼠每一步的方向，但是这是个确定的值，除非人为的设置种子（srand），这样就可以出现完全不同的造型。我考虑过用系统时间做种子的方法，但不对。原因很简单，系统运算速度非常快，1s中的时间，随机数根本不会发生变化。否则，就像我之前写的小老鼠吃墙的动画效果一样，一秒钟一步慢慢来。以网格20*30的规模来构造迷宫的话，一共2000多步，也就是40分钟左右。。。这是一种伤不起的行为
所以暂时拿不出一个更好的方法来生成随机迷宫，如果把它作为抛砖引玉的话，可以引申考虑一下。

/////////////////////////////////////////////部分代码//////////////////////////////////////////////
构建部分 ：

	/***********************开始构建迷宫*********************************/
	int direction;									//0 == down, 1 == up, 2 == right, 3 == left
	int temp_x = 0;									//定义出发点相对坐标
	int temp_y = 0;
	int before_x = 0;
	int before_y = 0;
	cell[temp_x][temp_y].eaten = true;				//定义出发格为已访问
	cell[temp_x][temp_y].x = START_X ;				//定义出发格为[0][0]
	cell[temp_x][temp_y].y = START_Y ;
	cell[temp_x][temp_y].point.x = 10.0;			//定义出发格的视图坐标（10,20）
	cell[temp_x][temp_y].point.y = 20.0;
	cell[temp_x][temp_y].before = &cell[temp_x][temp_y];
	cell[temp_x][temp_y].before -> x = START_X;
	cell[temp_x][temp_y].before -> y = START_Y;
	glColor3f(0.1, 0.1, 0.1);						//设置覆盖颜色为背景色
	glRectf(10 + 2, 20 + SIZE/2, 10 + SIZE - 2, 20 - SIZE/2);	//显示起始位置		
	glRectf(10 + (VERTICAL_NUMBER - 1) * SIZE + SIZE/2, 20 + (HORIZONTAL_NUMBER - 1) * SIZE + 2, 10 + VERTICAL_NUMBER * SIZE + SIZE/2, 20 + HORIZONTAL_NUMBER * SIZE - 2);

只列出判断老鼠的方向向下部分：

		direction = random(4);						//随机设定方向
		//if (temp_x == EXIT_X && temp_y == EXIT_Y) break;//如果到终点了，就结束
		if (direction == 0)			//下
		//1、是否向下 
		{
			if (temp_x > 0)	//2、如不在下边界 
			{
				if (cell[temp_x - 1][temp_y].eaten == false)	//3、如左边的格未访问过
				{
					cell[temp_x][temp_y].left = 1;							 //将本格左边设定为eaten
					cell[temp_x - 1][temp_y].right = 1;						 //将下一格右边设定为eaten
					cell[temp_x - 1][temp_y].eaten = true;					 //将下一格设定为eaten
					cell[temp_x - 1][temp_y].before = &cell[temp_x][temp_y]; //将即将当前格设定为before
					cell[temp_x - 1][temp_y].x = temp_x - 1;				 //记录下一格的坐标存到下一格的（x,y）中
					cell[temp_x - 1][temp_y].y = temp_y;
					cell[temp_x - 1][temp_y].point.x = cell[temp_x][temp_y].point.x;
					cell[temp_x - 1][temp_y].point.y = cell[temp_x][temp_y].point.y - SIZE;
					glRectf(cell[temp_x][temp_y].point.x + 2, cell[temp_x][temp_y].point.y + SIZE/2, cell[temp_x - 1][temp_y].point.x + SIZE - 2, cell[temp_x - 1][temp_y].point.y + SIZE/2);						//填充
					temp_x -= 1;
				}
				else//3、如下边的格已访问过,判断周围是否已访问，若都访问，回退，若存在未访问，进入下一循环
					if( cell[temp_x][temp_y - 1].eaten == true &&			
						cell[temp_x][temp_y + 1].eaten == true &&
						cell[temp_x + 1][temp_y].eaten == true &&
						cell[temp_x - 1][temp_y].eaten == true)
					{
						before_x = temp_x;
						before_y = temp_y;
						temp_x = cell[before_x][before_y].before -> x;
						temp_y = cell[before_x][before_y].before -> y;
					}//end 3
				//cout<<direction<<"("<< temp_x <<","<<temp_y<<")"<<" -> "; 
				continue;
			}
			else//2、如在下边界，判断周围是否已访问，若都访问，回退，若存在未访问，进入下一循环
				if( cell[temp_x][temp_y - 1].eaten == true &&			
					cell[temp_x][temp_y + 1].eaten == true &&
					cell[temp_x + 1][temp_y].eaten == true)
				{
					before_x = temp_x;
					before_y = temp_y;
					temp_x = cell[before_x][before_y].before -> x;
					temp_y = cell[before_x][before_y].before -> y;
				}//end 2
			//cout<<direction<<"("<< temp_x <<","<<temp_y<<")"<<" -> "; 
			continue;
		}//end 1

-----------------------------------------------——————————————————————————————
关于迷宫解法是个典型深度优先搜索问题。现在脑袋跟不上，回头弄了。。。