#include #include #include #include using namespace std; // The maze generator algorithm is based on Daniel Shiffman's The Coding Train youtube tutorial on maze generation using Depth-first search and Recursive backtracking. //This is my first C++ code so it's not optimized. // Created by Jonathan Pizarra // Finished on March 30, 2018. 1:20AM. // Inputs should be higher than 10 to get better mazes //==== global vars char b = char(219); // int w = 41; //width int h = 21; //height vector >arr = {}; vector > arr2 = {}; vector arr3 = {}; vector > neigh = {}; int r = 1; //row int c = 1; //column vector nxt = {}; int count = 1; // ===== SOLVING FUNC ====== int solve() { if(r == h-1 && c == w-2){ // cout << "THE MAZE IS NOW SOLVED!"; return 0; } if(arr[r][c] == 0){ arr[r][c] = 2; arr2.push_back({r,c}); } if(arr[r-1][c] == 0){ r--; solve(); } else if(arr[r][c+1] == 0){ c++; solve(); } else if(arr[r+1][c] == 0){ r++; solve(); } else if(arr[r][c-1] == 0){ c--; solve(); } else{ arr[r][c] = 4; arr2.pop_back(); r = arr2[arr2.size()-1][0] ; c = arr2[arr2.size()-1][1] ; solve(); } //return 0; } // ====== MAZE GENERATOR FUNC ======== int create(){ neigh.clear(); //== counter to end recursive call quickly if(count >= (h/2)*(w/2) ){return 0;} //==== getting the unvisited neighbors if( r+2 < h-1 && arr[r+2][c] == 0){ neigh.push_back({r+2,c});//down } if( r-2 > 0 && arr[r-2][c] == 0 ){ neigh.push_back({r-2,c});//up } if( c+2 < w-1 && arr[r][c+2] == 0 ){ neigh.push_back({r,c+2});//right } if( c-2 > 0 && arr[r][c-2] == 0 ){ neigh.push_back({r,c-2});//left } //=== forward if(neigh.size() > 0){ nxt.clear(); nxt = neigh[rand()%neigh.size()]; //mark it as visited arr[nxt[0]][nxt[1]] = 2; //counter to know if all cells are already visited count++; //push to the stack arr2.push_back(nxt); //remove the walls if(c-nxt[1] < 0){ arr[r][c+1] = 0; c+=2;create(); } else if( c-nxt[1] > 0 ){ arr[r][c-1] = 0; c-= 2; create(); } else if( r-nxt[0] < 0 ){ arr[r+1][c] = 0; r+= 2;create(); } else if( r-nxt[0] > 0 ){ arr[r-1][c] = 0; r-= 2;create(); } } //==== backtrack else if(arr2.size() > 0){ arr2.pop_back(); r = arr2[arr2.size()-1][0] ; c = arr2[arr2.size()-1][1] ; create(); } } int main() { //=== inputs for maze size cin >> h; cin >> w; //adjusting the size if(h%2 == 0){h++;} if(w%2 == 0){w++;} // getting time as seed time_t seed; seed = time(0); srand(seed%1000); //===== creating the base of the maze arr.resize(h); for(int j=0; j

Maze Generator & Solver