#include
#include
#include "maze_gen_tree.h"
char isAlloc[MAZE_WIDTH][MAZE_HEIGHT];
node mz_start;
int init_maze()
{
int x, y;
INIT_NODE( &mz_start );
for( x = 0 ; x < MAZE_WIDTH ; x++ )
for( y = 0 ; y < MAZE_HEIGHT ; y++ )
isAlloc[x][y] = FALSE;
isAlloc[0][0] = TRUE;
mz_start.maze_x = mz_start.maze_y = 0;
mz_start.ms[MAZE_DIR_UP] = mz_start.ms[MAZE_DIR_LEFT] = MS_WALL;
return TRUE;
}
int generate_maze()
{
node *mz = &mz_start;
init_maze();
gen_maze( mz );
return TRUE;
}
int gen_maze( node *mz )
{
int i, j, rnd, num_child = 0;
node *n;
MAZE_DIR dir[MAZE_DIR_MAX] = { MAZE_DIR_MAX, MAZE_DIR_MAX, MAZE_DIR_MAX, MAZE_DIR_MAX };
/* 현재 노드 '*mz'의 주변 상태를 설정한다. 위,아래,좌,우가 벽인지 아닌지, 출발점인지 도착점인지 */
if( mz->maze_x == 0 )
{
if( mz->maze_y == 0 ) // Special Case : Maze Start
mz->ms[MAZE_DIR_UP] = mz->ms[MAZE_DIR_LEFT] = MS_WALL;
else if( mz->maze_y == MAZE_HEIGHT-1 )
mz->ms[MAZE_DIR_DOWN] = mz->ms[MAZE_DIR_LEFT] = MS_WALL;
else
mz->ms[MAZE_DIR_LEFT] = MS_WALL;
}
else if( mz->maze_x == MAZE_WIDTH-1 )
{
if( mz->maze_y == 0 )
mz->ms[MAZE_DIR_UP] = mz->ms[MAZE_DIR_RIGHT] = MS_WALL;
else if( mz->maze_y == MAZE_HEIGHT-1 ) // Special Case : Maze Exit
{
mz->ms[MAZE_DIR_DOWN] = mz->ms[MAZE_DIR_RIGHT] = MS_WALL;
return num_child;
}
else
mz->ms[MAZE_DIR_RIGHT] = MS_WALL;
}
else
{
if( mz->maze_y == 0 )
mz->ms[MAZE_DIR_UP] = MS_WALL;
else if( mz->maze_y == MAZE_HEIGHT-1 )
mz->ms[MAZE_DIR_DOWN] = MS_WALL;
}
/*
재귀함수이기에 depth-first의 방식으로 미로를 만들어 나가게 된다.
이 경우에 첫번째에 선택되는 방향이 출구로 향하는 경로가 되므로, 선택하는 방향의 순서를 난수화 해야 한다.
따라서 dir[]에 4가지 방향을 위한 배열을 만들고 각 방향의 순서를 난수로 만들되, 중복되지 않도록 하는 것이다.
*/
for( i = MAZE_DIR_UP ; i < MAZE_DIR_MAX ; i++ )
{
while( 1 )
{
rnd = rand()%MAZE_DIR_MAX;
if( dir[rnd] == MAZE_DIR_MAX )
{
dir[rnd] = i;
break;
}
}
}
for( i = 0 ; i < MAZE_DIR_MAX ; i++ )
{
if( mz->ms[dir[i]] != MS_UNDEF )
continue;
switch( dir[i] )
{
case MAZE_DIR_UP :
if( isAlloc[mz->maze_x][mz->maze_y-1] == FALSE )
{
n = make_node();
if( n == NULL )
{
fprintf( stderr, "make_node() failed : %s(%d)\n", __FILE__, __LINE__ );
return num_child;
}
n->maze_x = mz->maze_x;
n->maze_y = mz->maze_y-1;
n->p_parent = mz;
n->ms[MAZE_DIR_DOWN] = MS_PARENT;
j = 0;
while( mz->p_child[j] ) j++;
mz->p_child[j] = n;
mz->ms[MAZE_DIR_UP] = MS_CHILD;
isAlloc[mz->maze_x][mz->maze_y-1] = TRUE;
num_child++;
gen_maze( n );
}
break;
case MAZE_DIR_DOWN :
if( isAlloc[mz->maze_x][mz->maze_y+1] == FALSE )
{
n = make_node();
if( n == NULL )
{
fprintf( stderr, "make_node() failed : %s(%d)\n", __FILE__, __LINE__ );
return num_child;
}
n->maze_x = mz->maze_x;
n->maze_y = mz->maze_y+1;
n->p_parent = mz;
n->ms[MAZE_DIR_UP] = MS_PARENT;
j = 0;
while( mz->p_child[j] ) j++;
mz->p_child[j] = n;
mz->ms[MAZE_DIR_DOWN] = MS_CHILD;
isAlloc[mz->maze_x][mz->maze_y+1] = TRUE;
num_child++;
gen_maze( n );
}
break;
case MAZE_DIR_LEFT :
if( isAlloc[mz->maze_x-1][mz->maze_y] == FALSE )
{
n = make_node();
if( n == NULL )
{
fprintf( stderr, "make_node() failed : %s(%d)\n", __FILE__, __LINE__ );
return num_child;
}
n->maze_x = mz->maze_x-1;
n->maze_y = mz->maze_y;
n->p_parent = mz;
n->ms[MAZE_DIR_RIGHT] = MS_PARENT;
j = 0;
while( mz->p_child[j] ) j++;
mz->p_child[j] = n;
mz->ms[MAZE_DIR_LEFT] = MS_CHILD;
isAlloc[mz->maze_x-1][mz->maze_y] = TRUE;
num_child++;
gen_maze( n );
}
break;
case MAZE_DIR_RIGHT :
if( isAlloc[mz->maze_x+1][mz->maze_y] == FALSE )
{
n = make_node();
if( n == NULL )
{
fprintf( stderr, "make_node() failed : %s(%d)\n", __FILE__, __LINE__ );
return num_child;
}
n->maze_x = mz->maze_x+1;
n->maze_y = mz->maze_y;
n->p_parent = mz;
n->ms[MAZE_DIR_LEFT] = MS_PARENT;
j = 0;
while( mz->p_child[j] ) j++;
mz->p_child[j] = n;
mz->ms[MAZE_DIR_LEFT] = MS_CHILD;
isAlloc[mz->maze_x+1][mz->maze_y] = TRUE;
num_child++;
gen_maze( n );
}
break;
default :
fprintf( stderr, "gen_maze() : dir[] has invalid value : %s(%d)\n", __FILE__, __LINE__ );
} // switch(dir[i])
} // for(i)
return num_child;
}
node *make_node()
{
node *mz;
mz = (p_node)malloc(sizeof(node));
if(!mz)
return NULL;
INIT_NODE(mz);
return mz;
}
int delete_node( node *mz )
{
free(mz);
return TRUE;
}
+-+GVIM.png)
