mazemake.h

Visual C++ 游戏开发与设计实例 源代码(所有)

/////////////////////////////////////////////////////////////////////////

/*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.
*/ 

//////////////////////////////////////////////////////////////////////////
// Copyright: 胡小民，丁展 2002.5

#ifndef _MAZE_MAKE_H
#define _MAZE_MAKE_H

#include <iostream.h>
#include <stdlib.h>
#include "maze.h"
#include "head.h"


void pMazeMaker(int wall[CONST_MAZEX][CONST_MAZEY]);
bool newCell(int wall[CONST_MAZEX][CONST_MAZEY],int x,int y);
bool covered(int wall[CONST_MAZEX][CONST_MAZEY]);
bool legalArea(int x,int y); 

int rand(int type)
{
	return rand()+rand()+rand();
}

bool newCell(int wall[CONST_MAZEX][CONST_MAZEY],int x,int y)
{	
	if(wall[y*2-1][x*2-1]==0)
		return false;
	else 
		return true;
}

bool covered(int wall[CONST_MAZEX][CONST_MAZEY])
{
	for(int i=1;i<=col;i++)
	{
		for(int j=1;j<=row;j++)
		{
			if(newCell(wall,i,j)==true)
				return false;
		}
	}
	return true;
}

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

void pMazeMaker(int wall[CONST_MAZEX][CONST_MAZEY])
{
	int currX,currY;
	int temp1;
	int dir=0;
// wall[][] should be initialized to 1
// set the entrance to be (0,0) and the exit to be (row,col)
	wall[1][0]=0;
	wall[row*2-1][col*2]=0;
// begin from (1,1)
	wall[1][1]=0;
	currX=currY=1;
	for(int k=0;;k++)
	{
		dir=0;
		if(covered(wall)==true)
			break;
// if we do not cut some choice in the corner,it will take a lot of time to creat
		if(currX==1)
		{
			temp1=rand(1);
			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(1);
			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(1)%4;
		if(temp1==0 || dir==RIGHT)
		{
			if(dir==RIGHT)
				dir=0;
			currX++;
			if(legalArea(currX,currY)==false)
			{
				currX--;
				continue;
			}
			if(newCell(wall,currX,currY)==true)
			{
				wall[currY*2-1][currX*2-1]=0;	//set the newcell
				wall[currY*2-1][currX*2-2]=0;	//carved into from previous wall
			}
			continue;
		}
		else if(temp1==1 || dir==LEFT)
		{
			if(dir==LEFT)
				dir=0;
			currX--;
			if(legalArea(currX,currY)==false)
			{
				currX++;
				continue;
			}
			if(newCell(wall,currX,currY)==true)
			{
				wall[currY*2-1][currX*2-1]=0;	//set the newcell
				wall[currY*2-1][currX*2]=0;	//carved into from previous wall
			}
			continue;
		}
		else if(temp1==2 || dir==DOWN)
		{
			if(dir==DOWN)
				dir=0;
			currY++;
			if(legalArea(currX,currY)==false)
			{
				currY--;
				continue;
			}
			if(newCell(wall,currX,currY)==true)
			{
				wall[currY*2-1][currX*2-1]=0;	//set the newcell
				wall[currY*2-2][currX*2-1]=0;	//carved into from previous wall
			}
			continue;
		}
		else if(temp1==3 || dir==UP)
		{
			if(dir==UP)
				dir=0;
			currY--;
			if(legalArea(currX,currY)==false)
			{
				currY++;
				continue;
			}
			if(newCell(wall,currX,currY)==true)
			{
				wall[currY*2-1][currX*2-1]=0;	//set the newcell
				wall[currY*2][currX*2-1]=0;	//carved into from previous wall
			}
			continue;
		}
	}
	wall[1][0]=1;
	wall[row*2-1][col*2]=1;
}

#endif