Question on Solving a maze using recursion.

[Jmartian]

Ok so i wrote this program, and it finds the exit of the maze, but it has alot of if statements, I would like to know if there is a more compact/efficient way of doing this.

Code:

#include<iostream>
using namespace std;


void printMaze(char a[12][12])
{

for(int i=0;i<12;i++)
{

cout<<" ";

for(int j=0;j<12;j++)
{
cout<<a[i][j]<<" ";
}

cout<<endl<<endl;
}
}


void mazeTraverse(char a[12][12], int i, int j)
{
cout<<endl;
printMaze(a);

if(a[i-1][j]=='#' && a[i][j-1]=='.')
{
a[i][j]='x';
mazeTraverse(a,i,j-1);
}

if(a[i-1][j]=='.')
{
a[i][j]='x';
mazeTraverse(a,i-1,j);
}

if( a[i][j-1]=='#' && a[i][j+1]=='.')
{
a[i][j]='x';
mazeTraverse(a,i,j+1);
}

if(a[i-1][j]=='#' && a[i+1][j]=='.')
{
a[i][j]='x';
mazeTraverse(a,i+1,j);
}

if(a[i][j-1]=='#' && a[i+1][j]=='.' && i!=4 && j!=11)
{
a[i][j]='x';
mazeTraverse(a,i+1,j);
}



if(a[i+1][j]=='#' && a[i][j+1]=='.')
{
a[i][j]='x';
mazeTraverse(a,i,j+1);
}

if(a[i][j+1]=='#' && a[i+1][j]=='.' || a[i+1][j]=='x')//ojo
{
a[i][j]='x';
mazeTraverse(a,i+1,j);
}


if(a[i][j+1]=='#' && a[i][j-1]=='.')
{
a[i][j]='x';
mazeTraverse(a,i,j-1);
}

if(a[i][j+1]=='#' && a[i-1][j]=='#' && a[i][j-1]=='#')
{
a[i][j]='x';
mazeTraverse(a,i+1,j);
}

if(a[i][j-1]=='#' && a[i+1][j]=='x')
{
mazeTraverse(a,i+1,j);
}

if(a[i][j-1]=='.' && a[i+1][j]=='.')
{
mazeTraverse(a,i,j-1);
}

if(i==2 && j==0)
{
a[i][j]='x';
cout<<"MAZE solved!\n\n";
}
}


int main()
{

char a[12][12]=
{{'#','#','#','#','#','#','#','#','#','#','#','#'},
{'#','.','.','.','#','.','.','.','.','.','.','#'},
{'.','.','#','.','#','.','#','#','#','#','.','#'},
{'#','#','#','.','#','.','.','.','.','#','.','#'},
{'#','.','.','.','.','#','#','#','.','#','.','.'},
{'#','#','#','#','.','#','.','#','.','#','.','#'},
{'#','.','.','#','.','#','.','#','.','#','.','#'},
{'#','#','.','#','.','#','.','#','.','#','.','#'},
{'#','.','.','.','.','.','.','.','.','#','.','#'},
{'#','#','#','#','#','#','.','#','#','#','.','#'},
{'#','.','.','.','.','.','.','#','.','.','.','#'},
{'#','#','#','#','#','#','#','#','#','#','#','#'}};


mazeTraverse(a,4,11);

return 0;
}

[helios]

The main problem is how you're representing the maze. You're representing it as a bitmap, instead of the more efficient graph.

http://en.wikipedia.org/wiki/Maze_solving_algorithm

[Jmartian]

Thanks helios but the thing is that I have to stick with the bitmap approach, it is required for this assignment.

[Jmartian]

Finally i found this solution at google. I'm trying to digest it.

#include <iostream>
using std::cin;
using std::cout;

enum Direction { DOWN, RIGHT, UP, LEFT };

// function prototypes
void mazeTraversal( char [][ 12 ], const int, const int, int, int, int );
void printMaze( const char[][ 12 ] );
bool validMove( const char [][ 12 ], int, int );
bool coordsAreEdge( int, int );

int main()
{
char maze[ 12 ][ 12 ] =
{ {'#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#'},
{'#', '.', '.', '.', '#', '.', '.', '.', '.', '.', '.', '#'},
{'.', '.', '#', '.', '#', '.', '#', '#', '#', '#', '.', '#'},
{'#', '#', '#', '.', '#', '.', '.', '.', '.', '#', '.', '#'},
{'#', '.', '.', '.', '.', '#', '#', '#', '.', '#', '.', '.'},
{'#', '#', '#', '#', '.', '#', '.', '#', '.', '#', '.', '#'},
{'#', '.', '.', '#', '.', '#', '.', '#', '.', '#', '.', '#'},
{'#', '#', '.', '#', '.', '#', '.', '#', '.', '#', '.', '#'},
{'#', '.', '.', '.', '.', '.', '.', '.', '.', '#', '.', '#'},
{'#', '#', '#', '#', '#', '#', '.', '#', '#', '#', '.', '#'},
{'#', '.', '.', '.', '.', '.', '.', '#', '.', '.', '.', '#'},
{'#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#'} };

int xStart = 2; // starting X and Y coordinates for maze
int yStart = 0;
int x = xStart; // current X and Y coordinates
int y = yStart;

mazeTraversal( maze, xStart, yStart, x, y, RIGHT );
return 0;
} // end main

// Assume that there is exactly 1 entrance and exactly 1 exit to the maze.
void mazeTraversal( char maze[][ 12 ], const int xStart, const int yStart,
int xCoord, int yCoord, int direction )
{
static bool flag = false;

maze[ xCoord ][ yCoord ] = 'x';
printMaze( maze );

if ( coordsAreEdge( xCoord, yCoord ) && xCoord != xStart &&
yCoord != yStart )
{
cout << "\nMaze successfully exited!\n\n";
return; // maze is complete
} // end if
else if ( xCoord == xStart && yCoord == yStart && flag )
{
cout << "\nArrived back at the starting location.\n\n";
return;
} // end else if
else
{
flag = true;

// for loop uses switch to determine appropriate move
for ( int move = direction, count = 0; count < 4; count++,
move++, move %= 4 )
{
switch( move )
{
case DOWN: // move down
if ( validMove( maze, xCoord + 1, yCoord ) )
{
mazeTraversal(
maze, xStart, yStart, xCoord + 1, yCoord, LEFT );
return;
} // end if
break;
case RIGHT: // move right
if ( validMove( maze, xCoord, yCoord + 1 ) )
{
mazeTraversal(
maze, xStart, yStart, xCoord, yCoord + 1, DOWN );
return;
} // end if
break;
case UP: // move up
if ( validMove( maze, xCoord - 1, yCoord ) )
{
mazeTraversal(
maze, xStart, yStart, xCoord - 1, yCoord, RIGHT );
return;
} // end if
break;
case LEFT: // move left
if ( validMove( maze, xCoord, yCoord - 1 ) )
{
mazeTraversal(
maze, xStart, yStart, xCoord, yCoord - 1, UP );
return;
} // end if
break;
} // end switch
} // end for
} // end else
} // end function mazeTraversal

// validate move
bool validMove( const char maze[][ 12 ], int r, int c )
{
return
( r >= 0 && r <= 11 && c >= 0 && c <= 11 && maze[ r ][ c ] != '#' );
} // end function validate

// function to check coordinates
bool coordsAreEdge( int x, int y )
{
if ( ( x == 0 || x == 11 ) && ( y >= 0 && y <= 11 ) )
return true;
else if ( ( y == 0 || y == 11 ) && ( x >= 0 && x <= 11 ) )
return true;
else
return false;
} // end function coordsAreEdge

// print the current state of the maze
void printMaze( const char maze[][ 12 ] )
{
// nested for loops to iterate through maze
for ( int x = 0; x < 12; x++ )
{
for ( int y = 0; y < 12; y++ )
cout << maze[ x ][ y ] << ' ';

cout << '\n';
} // end for

cout << "\nHit return to see next move\n";
cin.get();
} // end function printMaze