미로 생성

#ifndef MAZE_GEN_TREE_H

#ifndef TRUE
#define TRUE    1
#endif
#ifndef FALSE
#define FALSE   0
#endif

/* 미로의 크기, 폭과 높이를 가진 직사각형으로 제한 */
#define MAZE_WIDTH      20
#define MAZE_HEIGHT     20

/* 각 방이 가질 수 있는 방향에 대한 정의. 시각적으로 상하좌우를 갖는다고 가정함. */
typedef enum {
    MAZE_DIR_UP = 0,
    MAZE_DIR_DOWN,
    MAZE_DIR_LEFT,
    MAZE_DIR_RIGHT,
    MAZE_DIR_MAX
} MAZE_DIR;

/* 각 방을 중심으로 4가지 방향에 존재할 수 있는 종류. 미결정, 벽, 부모(들어오는 방향 표시), 자식 */
typedef enum {
    MS_UNDEF = 0,
    MS_WALL,
    MS_PARENT,
    MS_CHILD
} MAZE_STATUS;



/* 트리구조에 필요한 상수.
   4방향 중 하나는 미로로 들어오는 방향이므로 이를 부모 노드로 보고,
   최대 나머지 3방향으로 나갈 수 있으므로 이를 자식 노드로 본다. */
#define MAX_CHILD   3

typedef struct  _node {
    struct  _node *p_parent;

    int     maze_x, maze_y;
    MAZE_STATUS ms[MAZE_DIR_MAX];

    struct  _node *p_child[MAX_CHILD];
} node, *p_node;


#define INIT_NODE(node) \
    do {\
        (node)->p_parent = NULL;\
        (node)->maze_x = (node)->maze_y = 0;\
        (node)->ms[MAZE_DIR_UP] = (node)->ms[MAZE_DIR_DOWN] = (node)->ms[MAZE_DIR_LEFT] = (node)->ms[MAZE_DIR_RIGHT] = MS_UNDEF;\
        (node)->p_child[0] = (node)->p_child[1] = (node)->p_child[2] = NULL;\
    } while(0);\



int init_maze();
int generate_maze();
int gen_maze( node *mz );
node  *make_node();
int   delete_node( node *mz );


#endif  // MAZE_GEN_TREE_H

#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;
}