Sign in to follow this  

maze: recursion question

This topic is 4481 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

ok so the latest exercise was to write a recursive function to walk through a maze. I got it to work after doing some reading on the technique but my question is why doesn't the array update with x's in directions it went that weren't the solution? maybe i'm looking at it wrong again but the first time where it can go left i expected it to be filled with x's but it doesnt do this. when it returns to start trying a different direction does it not save what it tried before that? well i hope i'm making sense. this recursive stuff tends to mix me up :P here is the code:
[source lang = "cpp"]
#include <iostream>
#include <ctime>

using std::cout;

void mazeTraverse( char [][12], int, int );

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

	return 0;

}	// end main

void mazeTraverse( char m[][12], int r, int c )
{
	static int update = time( 0 ) % 10;
	
	while ( time(0) % 10 != update )
		;	// wait
	
	if ( time( 0 ) % 10 == 9 )
		update = 0;
	else
		update = (time( 0 ) % 10) + 1;

	m[r][c] = 'x';	// mark spot visited

	system("cls");

	// print the maze
	for ( int row = 0; row < 12; row++ )
	{
		for ( int column = 0; column < 12; column++ )
			cout << m[row][column];

		cout << '\n';
	}

	if ( c == 11 )
	{
		cout << "\nsuccess!\n";
		return;
	}
	if ( m[r][c+1] == '.' )	// if can go right
		return mazeTraverse( m, r, c+1 );	// start going right

	if ( m[r+1][c] == '.' )	// if can go down
		return mazeTraverse( m, r+1, c );	// start going down

	if ( m[r-1][c] == '.' )	// if can go up
		return mazeTraverse( m, r-1, c );	// start going up

	if ( m[r][c-1] == '.' )	// if can go left
		return mazeTraverse( m, r, c-1 );	// start going left

	

}

Share this post


Link to post
Share on other sites
bah everytime i post i see the problem...it wasn't actually ever going left due to the way i wrote the function. also the function didnt really even work if i switch the order of directions to try so ive fixed it. also dunno why i had return before those function calls. told ya this stuff mixes me up :O

I do have a new problem though. what's the best way to get the function to stop once the solution is found?

updated:

#include <iostream>
#include <ctime>

using std::cout;

void mazeTraverse( char [][12], int, int );

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

mazeTraverse( maze, 2, 0 );

return 0;

} // end main

void mazeTraverse( char m[][12], int r, int c )
{
static int update = time( 0 ) % 10;

while ( time(0) % 10 != update )
; // wait

if ( time( 0 ) % 10 == 9 )
update = 0;
else
update = (time( 0 ) % 10) + 1;

m[r][c] = 'x'; // mark spot visited

system("cls");

// print the maze
for ( int row = 0; row < 12; row++ )
{
for ( int column = 0; column < 12; column++ )
cout << m[row][column];

cout << '\n';
}

if ( c == 11 )
{
cout << "\nsuccess!\n";
return;
}

if ( m[r-1][c] == '.' ) // if can go up
mazeTraverse( m, r-1, c ); // start going up

if ( m[r+1][c] == '.' ) // if can go down
mazeTraverse( m, r+1, c ); // start going down

if ( m[r][c-1] == '.' ) // if can go left
mazeTraverse( m, r, c-1 ); // start going left

if ( m[r][c+1] == '.' ) // if can go right
mazeTraverse( m, r, c+1 ); // start going right

return;

} // end function mazeTraverse

Share this post


Link to post
Share on other sites
nevermind i figured it out. was a simple fix. should of had that in from the beginning.

updated function:

void mazeTraverse( char m[][12], int r, int c )
{
static int update = time( 0 ) % 10;

while ( time(0) % 10 != update )
; // wait

if ( time( 0 ) % 10 == 9 )
update = 0;
else
update = (time( 0 ) % 10) + 1;

m[r][c] = 'x'; // mark spot visited

system("cls");

// print the maze
for ( int row = 0; row < 12; row++ )
{
for ( int column = 0; column < 12; column++ )
cout << m[row][column];

cout << '\n';
}

if ( m[r][c] == 'E' )
{
cout << "\nsuccess!\n";
return;
}
else
{
if ( m[r-1][c] == '.' || m[r-1][c] == 'E' ) // if can go up
mazeTraverse( m, r-1, c ); // start going up

if ( m[r+1][c] == '.' || m[r+1][c] == 'E' ) // if can go down
mazeTraverse( m, r+1, c ); // start going down

if ( m[r][c-1] == '.' || m[r][c-1] == 'E' ) // if can go left
mazeTraverse( m, r, c-1 ); // start going left

if ( m[r][c+1] == '.' || m[r][c+1] == 'E' ) // if can go right
mazeTraverse( m, r, c+1 ); // start going right

m[r][c] = '.';
return;
}

} // end function mazeTraverse



next i'm supposed to create a mazeGenerator function. anyone point me in the right direction with this? i'm not sure how to approach this one yet.

Share this post


Link to post
Share on other sites

This topic is 4481 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this