Maze поколение - рекурсивное подразделение (как это работает?)

Question

Я хотел бы узнать, как создать идеальный лабиринт. Я пытаюсь понять алгоритм рекурсивного отдела. Я не могу понять, как реализовать этот алгоритм. Это мой код:

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

Существует что-то не так с этим кодом, так как он часто замерзает программу (бесконечный цикл где-то), но если он работает она генерирует «лабиринт», как это: Generated 'maze'

Я не хочу спрашивать вас о моем коде. Я просто хочу понять, как реализовать этот алгоритм, где я ошибаюсь и что я должен делать. Мне нужно создать идеальный лабиринт без закрытых областей.

Answer 1

Сначала вы должны решить, как вы проектируете свой лабиринт. Вы используете целые ячейки, чтобы представлять стены или проходы. Это означает, что у вас есть некоторые ограничения на номера, которые вы выбираете как новые стены и проходы. Толстые стены в вашем примере, где две вертикальные стены смежны без прохода между ними, не должны создаваться.

С вашей методикой: N × N лабиринт представлен массивом (2*N + 1) × (2*N + 1). У вас есть координаты «лабиринта» от 0 до N и координаты «сетки» от 0 до 2*N + 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) - это координаты лабиринта. Хеш-метки # - это всегда стены, но плюсы + заканчиваются либо проходами, либо стенами.

Вторая проблема заключается в самой рекурсии. Когда вы построили стену, вы разделили активное пространство на две области. Теперь вы должны применить алгоритм к обоим новым регионам.

Таким образом, вместо:

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

Конечно, вы должны иметь условие, чтобы остановить рекурсию, но у вас есть уже: Вы надеваете» t строить дальнейшие стены, когда пространство слишком мало.

Большие комнаты в вашем примере показывают, что вы только перечислили в один новый подраздел лабиринта. Большие комнаты - это те, в которые вы не зачислялись.