I am trying to change my recursive coding part of a maze into a while loop

Question

Here is my code.

#include <iostream> using namespace std; enum Direction { EAST, NORTH, WEST, SOUTH }; const int size = 12; int xStart = 2; int yStart = 0; char *maze2[ ] = { "############", "#...#......#", "..#.#.####.#", "###.#....#.#", "#....###.#..", "####.#.#.#.#", "#..#.#.#.#.#", "##.#.#.#.#.#", "#........#.#", "######.###.#", "#......#...#", "############", }; void printMaze ( char maze[][ size ] ); void mazeTraverse( char maze[][ size ], int x, int y, int direction ); int main() { char maze[ size ][ size ]; for (int x = 0; x < size; x++ ) for (int y = 0; y < size; y++) maze[ x ][ y ] = maze2[ x ][ y ]; printMaze( maze ); mazeTraverse( maze, xStart, yStart, EAST); } void printMaze ( char maze[][ size ] ) { for ( int x = 0; x < size; x++) { for ( int y = 0; y < size; y++) cout << maze[ x ][ y ]; cout << endl; } cout << endl; cout << "\nHit return to see next move\n"; cin.get(); } bool validMove( char maze[][ size ], int x, int y ) { return x >= 0 && x < size && y >= 0 && y < size && maze[x][y] != '#'; } bool coordsAreEdge( int x, int y ) { return x== 0 || x== size - 1 || y == 0 || y== size - 1; } void mazeTraverse( char maze[][ size ], int x, int y, int direction ) { maze[ x ][ y ] = 'x'; printMaze( maze ); if (coordsAreEdge(x, y) && (x != xStart || y!= yStart )) { cout <<"\nMaze successfully exited!\n\n"; return; }else{ for ( int move = direction, count = 0; count < 4; count++, move++, move %=4 ) { int nextX; int nextY; switch ( move ) { case SOUTH: nextX = x + 1; nextY = y; break; case EAST: nextX = x; nextY = y + 1; break; case NORTH: nextX = x - 1; nextY = y; break; case WEST: nextX = x; nextY = y - 1; break; default: ; } if (validMove( maze, nextX, nextY )) { //Recursion move part 1 //mazeTraverse ( maze, nextX , nextY, (move + 3)%4 ); return; } } } } 

I am trying to make my void mazeTraverse a while loop function, not recursion, and I'm stuck.

Answer 1

Create a structure to hold X, Y, and direction (three things that change between calls). We will call it struct State ;

Create a std::stack<State> object. Push the current values ​​of X, Y, direction onto the stack, before changing them, pull them out after doing your job.

Consequently,

  while(.....) { push state Do work of mazeTraverse pop state } 

Answer 2

It would be nice if you described how the bypass works. If I do not read the code incorrectly, you basically move south / east / north / west to any position that does not contain # and is within the matrix.

You can do it iteratively using a BF search: http://en.wikipedia.org/wiki/Breadth-first_search or, applied to the matrix, the Lee algorithm: http://en.wikipedia.org/wiki/Lee_algorithm , which can be effectively implemented using the FIFO queue, which I will tell you about how to do this: Change the FloodFill Algorithm to get Voronoi territory for two data points?

Your validMove function will remain the same: you add a line item to the queue only if that line item is valid. Basically, all checks remain unchanged, you just use the FIFO queue to store your states instead of an implicit stack.

Answer 3

Instead, you can use a width search using the standard queue and while .

 typedef pair<int, int> Point; queue<Point> path; Point start(xStart, yStart); path.push(start); const int move_x[] = {-1, 0, 1, 0}; const int move_y[] = {0, -1, 0, 1}; while (!path.empty()) { Point p = path.front(); int x = p.first, y = p.second; maze[x][y] = 'x'; path.pop(); if (coordsAreEdge(x,y) && p != start) { // Finished break; } for (int i = 0; i < 4; ++i) { int newx = x + move_x[i]; int newy = y + move_y[i]; if (validMove(maze, newx, newy)) path.push(Point(newx, newy)); } } 

That should do the trick. Please note that it has not been tested.

You can improve your performance by using A * instead, but it is a bit more complicated. Let me know if you need to find the shortest path from this code.

EDIT: note that if you change the queue to stack (and change path.front() to path.top() ), you will get a depth search (DFS) instead, which is what your code does. However, DFS does not find the shortest path (if necessary).