迷路自動生成アルゴリズムを書いてみた。

はじめに

ちょいと興味がわいたので、迷路自動生成アルゴリズムをC言語で実装してみた。

処理内容

一般的にDIG(穴掘り)法といわれる超有名なアルゴリズム。
以下におおまかな処理内容を記載する。

1. 縦横共に奇数のフィールドを用意する。
2. 外周は通路とし、外周以外は壁で埋める。
3. 基準点から2ブロック先までが全て壁になっている方向のリストを作成する。
4. 作成したリストの中からランダムに掘る方向を決め、2ブロック先までを掘る。
5. 掘り終わった時点の座標を開始座標リストに追加する。
6. どこにも進めなくなったら、作成した開始座標リストの中からランダムに掘り始める座標を選ぶ。
7. 開始座標リストがなくなったら終了。
8. 最後に外周の通路を壁に書き換える。

コード

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

実行結果