소개

조금 흥미가 나서 미로 자동 생성 알고리즘을 C 언어로 구현해 보았다.

처리 내용

일반적으로 DIG(구멍 파기)법이라고 하는 초유명한 알고리즘.
이하에 대략적인 처리 내용을 기재한다.

종횡 모두 홀수의 필드를 준비한다.

외주는 통로로 하고, 외주 이외는 벽으로 메운다.

기준점에서 2 블록 끝까지 모두 벽이 되어 있는 방향의 리스트를 작성한다.

작성한 리스트 중에서 랜덤으로 파는 방향을 결정해, 2 블록 끝까지를 파낸다.

파고나간 시점의 좌표를 개시 좌표 리스트에 추가한다.

어디에도 진행되지 않게 되면, 작성한 개시 좌표 리스트중에서 랜덤으로 파기 시작하는 좌표를 선택한다.

시작 좌표 리스트가 없어지면 종료.

마지막으로 외주 통로를 벽에 다시 씁니다.

코드

mazetest.c

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

실행 결과