迷路生成 - 再帰的分割（それはどのように動作するのですか）

Question

私は完全な迷路を生成する方法を学びたいと思います。私は再帰的分割アルゴリズムを理解しようとしています。私はこのアルゴリズムを実装する方法を理解できません。これは私のコードです： Generated 'maze'

：それは多くの場合、プログラム（どこかで無限ループ）をフリーズし、それが動作するかどうか、それはこのような「迷路」を生成するので、このコードと間違って何かが、あり

bool maze[20][20]; 

void initMaze() 
{ 
    for(int i = 0; i < 20; i++) 
     for(int j = 0; j < 20; j++) 
      maze[i][j] = false; 

    for(int i = 0; i < 20; i++) 
     maze[0][i] = true; 

    for(int i = 0; i < 20; i++) 
     maze[19][i] = true; 

    for(int i = 0; i < 20; i++) 
     maze[i][0] = true; 

    for(int i = 0; i < 20; i++) 
     maze[i][19] = true; 
} 

int randNum(int min, int max) 
{ 
    return rand()%(max-min+1)+min; 
} 

void drawVWall(int minY, int maxY, int x) 
{ 
    int passage = randNum(minY, maxY); 

    for(int i = minY; i <= maxY; i++) 
     if(i != passage) 
      maze[i][x] = true; 
} 

void drawHWall(int minX, int maxX, int y) 
{ 
    int passage = randNum(minX, maxX); 

    for(int i = minX; i <= maxX; i++) 
     if(i != passage) 
      maze[y][i] = true; 
} 

void divison(int x, int y, int maxx, int maxy, int h) 
{ 
    if(h) 
    { 
     if(maxx <= 2) 
      return; 

     int wallY = randNum(y, maxy); 
     drawHWall(x, maxx, wallY); 

     if(wallY < maxy - wallY) 
      divison(x, wallY, maxx, maxy, !h); 
     else if(wallY > maxy - wallY) 
      divison(x, y, maxx, wallY, !h); 
    } 
    else 
    { 
     if(maxy <= 2) 
      return; 

     int wallX = randNum(x, maxx); 
     drawVWall(y, maxy, wallX); 

     if(wallX < maxx - wallX) 
      divison(wallX, y, maxx, maxy, !h); 
     else if(wallX > maxx - wallX) 
      divison(x, y, wallX, maxy, !h); 
    } 
} 

initMaze(); 
divison(2, 2, 18, 18, true); 

私は自分のコードについて質問したくありません。私はちょうど私が間違っていると私は何をすべきか、このアルゴリズムを実装する方法を理解したい。閉じた領域なしで完璧な迷路を生成する必要があります。

Answer 1

まず、迷路のデザイン方法を決めなければなりません。壁や通路を表現するために、全体のセルを使用します。つまり、あなたは新しい壁と通路として選んだ数にいくつかの制限があります。 2つの垂直な壁がそれらの間を通らずに隣接しているあなたの例の厚い壁は、作成されてはなりません。あなたの方法で

、N × N迷路は(2*N + 1) × (2*N + 1)の配列によって表されます。あなたは0からNの "迷路"座標と0から2*N + 1の "グ​​リッド"座標を持っています。アルゴリズムを迷路座標で行い、壁を作成するときにグリッド座標を使用します。

グリッド座標では、壁は偶数のインデックスでなければならず、コリドーは奇数のインデックスでなければなりません。両方のインデックスは最終迷路の壁でもあり、両方のインデックスは常にフリーセルです。 1つの偶数が壁を通過する可能性があることを意味します。

はここA4 ×だ、例示するために4迷路：

X 0 1 2 3 

x 0 1 2 3 4 5 6 7 8 

    # # # # # # # # # 0 
    # + + + # 1 0 
    # + # + # + # # # 2 
    # + + + # 3 1 
    # + # + # + # # # 4 
    # + + + # 5 2 
    # + # + # + # # # 6 
    # + + + # 7 3 
    # # # # # # # # # 8 

         y Y 

小文字（x、y）グリッド座標です。大文字（X,Y）は迷路の座標です。ハッシュマーク#は常に壁ですが、壁は壁または壁のどちらかになります。+

2番目の問題は再帰そのものです。壁を作成したら、アクティブな空間を2つの領域に細分しました。アルゴリズムを新しいリージョンの両方に適用する必要があります。 「あなたはドン：

ので、代わりの：

if (wallY < maxy - wallY) 
     divison(x, wallY, maxx, maxy, !h); 
    else if (wallY > maxy - wallY) 
     divison(x, y, maxx, wallY, !h); 

あなたはこのような何か行う必要があります。もちろん

divison(x, wallY, maxx, maxy, !h); 
    divison(x, y, maxx, wallY, !h); 

を、あなたの再帰を停止する条件を持っている必要がありますが、すでにことを持っていますスペースが小さすぎると、さらに壁を作りません。

あなたの例の大きな部屋は、あなたが迷路の1つの新しいサブセクションに再帰したことを示しています。大きな部屋はあなたが回帰しなかったものです。