소개

처리 내용

코드

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define M_WIDTH     59
#define M_HEIGHT    25
#define M_ARRLEN    (M_WIDTH*M_HEIGHT)
#define GetX(A)     ((A)%M_WIDTH)
#define GetY(A)     ((A)/M_WIDTH)
#define GetIdx(X,Y) ((Y)*M_WIDTH+(X))
#define rnd(A)      (rand()%(A))
#define randomize() (srand((unsigned)time(NULL)))

// 迷路のフィールド属性
enum maze {
    M_FLOOR, // 床
    M_WALL   // 壁
};

// 迷路のフィールド
int Fld[M_ARRLEN];

// 配列の要素を縮小し、配列の最終位置を返す
int arr_shrink(int *arr,int idx,int max){
    for(int i=idx;i<max;i++) arr[i]=arr[i+1];
    return --max;
}

// 迷路フィールド配列を初期化する
void init_maze(void){
    // 外枠以外を壁で埋める
    for(int i=0;i<M_ARRLEN;i++){
        if(i>=M_WIDTH&&(i%M_WIDTH>0&&i%M_WIDTH<M_WIDTH-1)&&i<M_ARRLEN-M_WIDTH) Fld[i]=M_WALL;        
    }
}

// DIG法を用いて迷路を作成する
void make_maze(int x,int y){
    int lidx=0;
    const int vvx[]={1,0,-1,0},vvy[]={0,1,0,-1};
    int vx[4],vy[4];
    int lf[M_ARRLEN/2+1];

    randomize();
    init_maze();
    while(1){
        // 進める(2ブロック先までが壁)方向リストを作成する
        int vidx=0;
        for(int i=0;i<4;i++){
            const int x1=GetIdx(x+vvx[i],y+vvy[i]);
            const int x2=GetIdx(x+(vvx[i]*2),y+(vvy[i]*2));
            if(Fld[x1]&&Fld[x2]){
                vx[vidx]=vvx[i];
                vy[vidx++]=vvy[i];
            }
        }
        if(vidx){ // 進める方向がある場合
            // ランダムに壁を掘り進める
            const int r=rnd(vidx);
            int fidx;
            for(int i=0;i<=2;i++){
                fidx=GetIdx(x+(vx[r]*i),y+(vy[r]*i));
                Fld[fidx]=M_FLOOR;
            }
            // 掘り進めた終点の座標を始点リストに追加する
            lf[lidx++]=fidx;
            // 現在位置を更新する
            x=GetX(fidx);
            y=GetY(fidx);
        }else if(lidx){ // 始点リストがある場合
            // 始点リストからランダムに始点を選択し、現在位置とする
            const int r=rnd(lidx);
            x=GetX(lf[r]);
            y=GetY(lf[r]);
            // 選択された始点リストの要素を配列から削除する
            lidx=arr_shrink(lf,r,lidx);
        }else{ // 進める方向も始点リストも枯渇した場合
            // ループから抜ける
            break;
        }
    }
    // 床に設定しておいた外枠を壁にしなおす
    for(int i=0;i<M_WIDTH;i++){
        Fld[GetIdx(i,0)]=Fld[GetIdx(i,M_HEIGHT-1)]=M_WALL;
    }
    for(int i=0;i<M_HEIGHT;i++){
        Fld[GetIdx(0,i)]=Fld[GetIdx(M_WIDTH-1,i)]=M_WALL;
    }
}

// 迷路を表示する
void print_maze(void){
    for(int i=0;i<M_ARRLEN;i++){
        if(i>0&&i%M_WIDTH==0) printf("\n");
        if(Fld[i]){
            printf("@@");
        }else{
            printf("  ");
        }
    }
    printf("\n");
}

// エントリポイント
int main(void){
    make_maze(1,1);
    print_maze();
    return 0;
}

실행 결과