I'm trying to change my Maze traversal recursive coding part into a while loop.

Question

Here's 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'm trying to make my void mazeTraverse function a while loop, instead of the recursion and I'm stuck.

Answer 1

It would've been nice if you described how the traversal works. If I'm not reading the code wrong, you are basically moving south/east/north/west on any position that doesn't contain a # and is within the bounds of the matrix.

You can do this iteratively by using a BF search: http://en.wikipedia.org/wiki/Breadth-first_search or, applied to a matrix, the Lee algorithm: http://en.wikipedia.org/wiki/Lee_algorithm which can be efficiently implemented using a FIFO queue, which I describe how to do here: http://stackoverflow.com/questions/2288830/change-floodfill-algorithm-to-get-voronoi-territory-for-two-data-points/2288898#2288898

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

Answer 2

Create a struct to hold X, Y and direction (the three things that change between calls). We'll call that struct State;

Create a std::stack<State> object. Push the current values of X,Y, direction onto the stack before you change them, pop them after you do your work.

hence

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

Answer 3

You could use a breadth-first search instead using a standard queue and while loop.

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. Note that it's untested though.

You can improve its performance by using A* instead, but that's a little more complex. Let me know if you need to find the shortest path from this code as well.

EDIT: Note that if you change the queue to a stack (and change path.front() to path.top()) then you'll get a depth-first search (DFS) instead, which is what your code does. The DFS, however, doesn't find the shortest path (if that is necessary).