goodmaze.cpp

maze目录下包含了4个迷宫相关的源代码：简单的迷宫生成算法、复杂的迷宫生成算法、简单的迷宫搜索算法、复杂的迷宫搜索算法

// GoodMaze.cpp : Defines the entry point for the console application.
//
/************************** Generate Maze Algorithm Copyright**************************/
/*You can distributed this algorithm as you like only saving this declaration above*/
/********************Date: 2002.5     Author: 胡小民 丁展**************************/

#include "stdafx.h"
#include <iostream.h>
#include <fstream.h>
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <time.h>

/*Aldus-Broder algorithm: The nice thing about this algorithm is it generates all
 possible Mazes of a given size with equal probability. It also requires no extra
 storage or stack. Pick a point, and move to a neighboring cell at random. If an
 uncarved cell is entered, carve into it from the previous cell. Keep moving to
 neighboring cells until all cells have been carved into. This algorithm yields 
 Mazes with a low "river" factor, only slightly higher than Kruskal's algorithm.
 (This means for a given size there are more Mazes with a low "river" factor than 
 high "river", since an average equal probability Maze has low "river".) The bad 
 thing about this algorithm is that it's very slow, since it doesn't do any 
 intelligent hunting for the last cells, where in fact it's not even guaranteed to
 terminate. However since the algorithm is simple it can move over many cells 
 quickly, so finishes faster than one might think. On average it takes about seven 
 times longer to run than the above algorithms, although in bad cases it can take
 much longer if the random number generator keeps making it avoid the last few cells.
*/ 

//////////////////////////////////////////////////////////////////////////
int row=50;
int col=50;
int SIZEX_MAZE=row*2+1;
int SIZEY_MAZE=col*2+1;
const int CONST_MAZEX=101;
const int CONST_MAZEY=101;

#define RIGHT 2
#define LEFT -2
#define DOWN  1
#define UP   -1

int maze[CONST_MAZEX][CONST_MAZEY]={1};

void GenerateMaze();
bool IsNewCell(int x,int y);
bool IsCovered();
bool IsLegalArea(int x,int y);

bool IsNewCell(int x,int y)
{
	if(maze[y*2-1][x*2-1]==0)
		return false;
	else
		return true;
}

bool IsCovered()
{
	for(int i=1;i<=col;i++)
	{
		for(int j=1;j<=row;j++)
		{
			if(IsNewCell(i,j)==true)
				return false;
		}
	}
	return true;
}

bool IsLegalArea(int x,int y)
{
	if(x>col || x<1 || y>row || y<1)
		return false;
	return true;
}

void GenerateMaze()
{
	//step1:  设置随机种子
	srand(time(NULL));
	//step2:  初始化
	for(int i=0;i<SIZEX_MAZE;i++)
		for(int j=0;j<SIZEY_MAZE;j++)
			maze[i][j]=1;
	int currX,currY;
	int temp1;
	int dir=0;
	//step3:  设置入迷宫口处(1,1) and the exit to be (row,col)
	maze[1][1]=0;
	currX=currY=1;
	for(int k=0;;k++)
	{
		dir=0;
		if(IsCovered()==true)
			break;
// if we do not cut some choice in the corner,it will take a lot of time to create
		if(currX==1)
		{
			temp1=rand();
			if(currY==1)
			{
				if(temp1%2==0)
					dir=RIGHT;
				else
					dir=DOWN;
			}
			else if(currY==row)
			{
				if(temp1%2==0)
					dir=RIGHT;
				else
					dir=UP;
			}
		}
		if(currX==col)
		{
			temp1=rand();
			if(currY==1)
			{
				if(temp1%2==0)
					dir=LEFT;
				else
					dir=DOWN;
			}
			else if(currY==row)
			{
				if(temp1%2==0)
					dir=LEFT;
				else
					dir=UP;
			}	
		}
		temp1=rand()%4;
		if(temp1==0 || dir==RIGHT)
		{
			if(dir==RIGHT)
				dir=0;
			currX++;
			//如果当前位置在边界，则回退到刚才的位置
			if(IsLegalArea(currX,currY)==false)
			{
				currX--;
				continue;
			}

			//对角区域(currY*2-1,currX*2-1)是墙，则打通相应位置
			if(IsNewCell(currX,currY)==true)
			{
				maze[currY*2-1][currX*2-1]=0;	//set the newcell
				maze[currY*2-1][currX*2-2]=0;	//carved into from previous maze
			}
			continue;
		}
		else if(temp1==1 || dir==LEFT)
		{
			if(dir==LEFT)
				dir=0;
			currX--;
			//如果当前位置在边界，则回退到刚才的位置
			if(IsLegalArea(currX,currY)==false)
			{
				currX++;
				continue;
			}
			//对角区域(currY*2-1,currX*2-1)是墙，则打通相应位置
			if(IsNewCell(currX,currY)==true)
			{
				maze[currY*2-1][currX*2-1]=0;	//set the newcell
				maze[currY*2-1][currX*2]=0;		//carved into from previous maze
			}
			continue;
		}
		else if(temp1==2 || dir==DOWN)
		{
			if(dir==DOWN)
				dir=0;
			currY++;
			//如果当前位置在边界，则回退到刚才的位置
			if(IsLegalArea(currX,currY)==false)
			{
				currY--;
				continue;
			}
			//对角区域(currY*2-1,currX*2-1)是墙，则打通相应位置
			if(IsNewCell(currX,currY)==true)
			{
				maze[currY*2-1][currX*2-1]=0;	//set the newcell
				maze[currY*2-2][currX*2-1]=0;	//carved into from previous maze
			}
			continue;
		}
		else if(temp1==3 || dir==UP)
		{
			if(dir==UP)
				dir=0;
			currY--;
			//如果当前位置在边界，则回退到刚才的位置
			if(IsLegalArea(currX,currY)==false)
			{
				currY++;
				continue;
			}
			//对角区域(currY*2-1,currX*2-1)是墙，则打通相应位置
			if(IsNewCell(currX,currY)==true)
			{
				maze[currY*2-1][currX*2-1]=0;	//set the newcell
				maze[currY*2][currX*2-1]=0;	//carved into from previous maze
			}
			continue;
		}
	}
}
void ShowMaze()
{
	int i,j;
	ofstream file("MazeData.txt",ios::out);
	assert(!file.fail());
	for(i=0;i<CONST_MAZEX;i++)
	{
		for(j=0;j<CONST_MAZEY;j++)
		{
			cout<<maze[i][j];
			file<<maze[i][j];
		}
		cout<<endl;
		file<<endl;
	}
	file.close();
}
int main(int argc, char* argv[])
{
	GenerateMaze();
	ShowMaze();
	return 0;
}