再帰バックトラッカー迷路生成アルゴリズムスタックループ

Question

ascii mazeを作成するために書いたアルゴリズムに問題があります。コードは、再帰的なバックトラッカーを使用している、との擬似コードは、本質的である：

1. Make the initial cell the current cell and mark it as visited 
2. While there are unvisited cells 
    1. If the current cell has any neighbours which have not been visited 
     1. Choose randomly one of the unvisited neighbours 
     2. Push the chosen cell to the stack 
     3. Remove the wall between the current cell and the chosen cell 
     4. Make the chosen cell the current cell and mark it as visited 
    2. Else 
     1. Pop a cell from the stack 
     2.Make it the current cell 

コードをスタックに追加し、スタックをポップのループ内で立ち往生していることである私が午前問題を。誰もがあなたが（isGood機能であれば最初にxとyを入れ替え

#include<iostream> 
#include<cstdlib> 
#include<stack> 
#include<ctime> 

#define NORTH 0 
#define SOUTH 1 
#define EAST 2 
#define WEST 3 
#define SIZEX 20 
#define SIZEY 20 

using namespace std; 

int nGood = 0; 
int locX = 1, locY = 1; 

void printGrid(char grid[SIZEY][SIZEX]){ 
system("clear"); 
for (int i = 0; i < SIZEY; i++){ 
    for(int j = 0; j < SIZEX; j++){ 
     cout << grid[i][j]; 
    } 
    cout << endl; 
} 
} 

int moveEW(int direction, int x){ 
    if (direction == EAST) 
      return x + 1; 
    else if (direction == WEST) 
      return x - 1; 
    else 
      return x; 
} 

int moveNS(int direction, int y){ 
    if (direction == NORTH) 
      return y - 1; 
    else if (direction == SOUTH) 
      return y + 1; 
    else 
      return y; 
} 

bool isGood(int x, int y, int direction, char grid[SIZEY][SIZEX]){ 
x = moveEW(direction,x); 
y = moveNS(direction,y); 

if (grid[x][y] == '.' || x >= (SIZEX - 1) || x <= 0 || y <= 0 || y >= (SIZEY - 1)){ 
    return false; 
} 

// check cardinal directions 
if (direction == NORTH){ 
    if (grid[y][x-1] != '.' && grid[y-1][x] != '.' && grid[y][x+1] != '.' && grid[y-1][x-1] != '.' && grid[y-1][x+1] != '.'){ 
     return true; 
    } 
} 
if (direction == SOUTH){ 
      if (grid[y][x-1] != '.' && grid[y+1][x] != '.' && grid[y][x+1] != '.' && grid[y+1][x-1] != '.' && grid[y+1][x+1] != '.'){ 
        return true; 
      } 
    } 
if (direction == EAST){ 
      if (grid[y][x+1] != '.' && grid[y-1][x] != '.' && grid[y+1][x] != '.' && grid[y-1][x+1] != '.' && grid[y+1][x+1] != '.'){ 
        return true; 
      } 
    } 
if (direction == WEST){ 
      if (grid[y][x-1] != '.' && grid[y-1][x] != '.' && grid[y+1][x] != '.' && grid[y-1][x-1] != '.' && grid[y+1][x-1] != '.'){ 
        return true; 
      } 
    } 
return false; 
} 

main(){ 
char grid[SIZEY][SIZEX]; 

// init grid 
for (int i = 0; i < SIZEY; i++){ 
      for(int j = 0; j < SIZEX; j++){ 
        grid[i][j] = '#'; 
      } 
    } 

//init rand 
srand(time(0)); 

//init stacks for xy coords 
stack<int> xValues; 
stack<int> yValues; 

nGood = 0; 
int direction = 0; 

do{ 
    //find n good moves 
    for (int i = 0; i < 4; i++){ 
     if (isGood(locX,locY,i,grid)) 
      nGood++; 
    } 

    // if only 1 good move, move there 
    if (nGood == 1){ 
     if (isGood(locX,locY,NORTH,grid)) 
      locY = moveNS(NORTH,locY); 
     else if (isGood(locX,locY,SOUTH,grid)) 
      locY = moveNS(SOUTH,locY); 
     else if (isGood(locX,locY,EAST,grid)) 
          locX = moveEW(EAST,locX); 
        else if (isGood(locX,locY,WEST,grid)) 
          locX = moveEW(WEST,locX); 
    } 

    // if no good moves, move back in stack 
    else if (nGood == 0){ 
     locX = xValues.top(); 
     locY = yValues.top(); 
     xValues.pop(); 
     yValues.pop(); 
    } 

    //if more than 1 good move, push stack 
    else if (nGood > 1){ 
     xValues.push(locX); 
     yValues.push(locY); 

     //direction to move randomly chosen 
     do{ 
      direction = rand() % 4; 
     }while (!isGood(locX,locY,direction,grid)); 

     locX = moveEW(direction,locX); 
     locY = moveNS(direction,locY); 
    } 

    // set grid 
    grid[locY][locX] = '.'; 
    //output grid to show creation 
    printGrid(grid); 
    //reset nGood value 
      nGood = 0; 

}while(!xValues.empty()); 

//final maze output 
printGrid(grid); 
return 0; 
} 

Answer 1

Windowsマシンのためにそれを変更する必要がある場合のコードは、現在のライン19上のLinux用の一つのシステムコマンドを使用して、グリッド[X] [Y]の代わりに、グリッド[y] [x]）。これは少なくとも時々問題を引き起こします。