• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 14475
  • Last Modified:

Maze Program in C++ using stack and array!


I am trying to write a maze program using stack in c++

I idea is that a user can call from a file a list of 1's and 0's that will be used as the maze. The maze is to work (in 4 directions) its way from the top to the bottom where the 0's are the open path and the 1's are the walls. When it encounters a 1, the program should automatically backtrack and go through a path of 0's. A sample input file is below. Also below is some pseudo code that I have written. Remember, the use does not decide the directions (this is not an interactive maze). The program automatically pulls the numbers into an array and puts it on a stack. Then automatically works through and outputs on the screen the path(s) that it took before it go down the maze. Please help asap!

struct coord //no member function
     {int row,
     int col;}
int myarray[10][10]
stack s //I will also have to predefine this
coord curr;
cur.row = cur.col = 0;
found = false; //logical variable
underflow = true; //no path condition
while ((!found) && (underflow))
     { if (cur.row == 9)
          found = true);
     else if (maze [cur.row + 1, cur.col==0)] //right direction
          {push(cur); maze (cur.row, cur.col)
          cur.col++;
     //same sort of algorithm for left, up, and down
     else {maze[cur.row, cur.col] = 1;
          (cur=pop(underflow);}

Thanks,
Ahmad


SAMPLE INPUT:
0 0 0 1 1 1 0 0 0 0
1 1 0 0 0 0 0 1 1 0
0 0 0 1 1 1 0 1 0 0
0 1 1 1 0 0 0 1 0 1
0 0 1 1 0 1 1 1 0 0
1 0 0 1 0 0 1 1 1 0
1 1 0 1 1 0 1 0 0 0
0 0 0 0 1 1 1 0 1 1
0 1 1 0 1 0 0 0 1 1
1 1 1 1 1 0 1 1 1 1
0
Aapkaahmad
Asked:
Aapkaahmad
  • 8
  • 6
  • 5
  • +3
1 Solution
 
n_fortynineCommented:
What r u specifically asking for? an algorithm using a stack is not very much divorced from one that uses recursion. have u tried writting any code for this?
0
 
DanRollinsCommented:
The trick is to include the logic to check whenever you have a decision point.  For instance, if you can go either left or right, then push the left and go right.  When you reach a dead end, pop the stack to get right back to the decision point and continue from there.

In the stack, you will need to maintain an x,y, and a direction-of-travel code (NSEW).

Actually, what I have done is this:
Upon entering a room, I push all possible exits except the one I came from and then leave the room by popping one off the top.  In a one-exit room, the effect is the same as just leaving by that single exit.  But in a multiple-exit room, it preserves the other one or two options for off-popping when you reach a dead-end (see, on a dead end, nothing gets pushed.  It is elegant beyond words, if I do say so myself.

-- Dan
0
 
SalteCommented:
Dan,

he should also watch out for 3 continuations. If he can go left, right and also straight he need to push two of them and walk the third. Then when getting to a dead-end as you say he pops a point and direction from the stack and continue in that direction.

He should probably also watch out for loops, unless the maze is made such that there are no loops. For the case of loop the best way is probably to have a third value, 'temporary wall' and set a point you are just leaving to 'temporary wall' if you meet such a 'temporary wall' you should treat it as a dead-end and set all the points in between this point and the decision point (the place where you pushed the stack) back to 'no wall' and then pop the stack and continue etc.

If you do not have loops in the maze you can of course omit such logic.

Alf
0
Never miss a deadline with monday.com

The revolutionary project management tool is here!   Plan visually with a single glance and make sure your projects get done.

 
Elias SalibaCommented:
there is a simple algorithm for walking through a maze that garantees finding the exit (assuming that there is one). if there is not an exit, you will arrive at the starting point again. here we go : place your right hand on the wall to your right and begin walking forward. NEVER remove your hand from the wall. if the maze turns to the right, you follow the wall to the right. as lonnnnng as you don't remove your hand from the wall, eventually you will arrive at the exit of the maze. there may be a shorter path than the one you have taken, but you are guaranteed to get out of the maze.

trinety
0
 
SalteCommented:
Actually, trinity, that algorithm does not work if you have loops, If you start out with your hand on the wall that form the inner wall of a loop, then you will walk around and around in circles and never get out :-)

The algorithm works fine if you are guaranteed there's no loop though.

Alf
0
 
AapkaahmadAuthor Commented:
I am getting some very good points from this discussion but can anyone get me the code needed for this? I must use the stack algorithm.

Thanks,
Ahmad
0
 
SalteCommented:
It is against EE policy to do your homework.

YOu get the code and then we can comment on it.

That's how it works. We can also give you hints but I believe we have already done that so the ball is now on your side to provide the code.

Alf
0
 
Elias SalibaCommented:
>>>Actually, trinity, that algorithm does not work if you have loops,


################
#.........#....#
#########.#.##.#
...............#
######.#.#######
#......#.#######
#.####.#.......#
#.####.#.#####.#
#......#.......#
##############.#
#...............
################


this is a sample maze .... i think it contain some loops ( as i understood from you:) ), and my methode still work fine...

i made a recursive function that can walk thrue any maze, based on my algorithm, and till no it has no problem in findng the exit..

trinety
0
 
Elias SalibaCommented:
ooopppss just copy and past that maze in the notepad to see it better

sorry for that ..
trinety
0
 
AapkaahmadAuthor Commented:

Trinety,

Can I see the code that you used? Thanks.

And Alf... I did originally post the code that I had written. This is as far as I got to solving the problem. If you don't want to help then don't, but don't stop others from doing so.
0
 
DanRollinsCommented:
See:
    http://home.earthlink.net/~danrollins/maze/maze.htm
Select 40 High, 75 wide, Tiny size.  Then click Create then click AutoSolve.  It's pretty cool.
0
 
n_fortynineCommented:
Aapkaahmad, if someone didn't want to help they wouldn't have commented your post at all. The problem is it seems that you are expecting someone to write it up for you. I see there are already useful inputs for you to start writing. And if you want to get help, please don't be rude.
0
 
keitha1Commented:
Use a wavefront. I wrote one that finds a path in a bitmap between any two points avoiding any non-white pixel.

I can post it but it has some dependencies on other stuff I wrote like lists and queues.

0
 
Elias SalibaCommented:
//this code will generate maze randomly and try to solve it
//by hitting on enter in the keybord
#include <iostream.h>
#include <stdlib.h>
#include <time.h>

enum Direction { DOWN, RIGHT, UP, LEFT };
const int MAX_DOTS = 100;  // maximum possible dots for maze

void mazeTraversal( char [][ 12 ], const int, const int, int, int, int );
void mazeGenerator( char [][ 12 ], 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, yStart, x, y;

   srand( time( 0 ) );

   for ( int loop = 0; loop < 12; ++loop )
      for ( int loop2 = 0; loop2 < 12; ++loop2 )
         maze[ loop ][ loop2 ] = '#';

   mazeGenerator( maze, &xStart, &yStart );

   x = xStart;  // starting row
   y = yStart;  // starting col

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

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

   maze[ row ][ col ] = 'x';  // insert X at current location
   printMaze( maze );

   if ( coordsAreEdge( row, col ) && row != xCoord && col != yCoord ) {
      cout << "Maze successfully exited!\n\n";
      return;   // maze is complete
   }
   else if ( row == xCoord && col == yCoord && flag ) {
      cout << "Arrived back at the starting location.\n\n";
      return;
   }
   else {
      flag = true;

      for ( int move = direction, count = 0; count < 4;
            ++count, ++move, move %= 4 )

         switch( move ) {
            case DOWN:
               if ( validMove( maze, row + 1, col ) ) { // move down
                  mazeTraversal( maze, xCoord, yCoord, row + 1, col, LEFT );
                  return;
               }
               break;
            case RIGHT:
               if ( validMove( maze, row, col + 1 ) ) { // move right
                  mazeTraversal( maze, xCoord, yCoord, row, col + 1, DOWN );
                  return;
               }
               break;
            case UP:
               if ( validMove( maze, row - 1, col ) ) { // move up
                  mazeTraversal( maze, xCoord, yCoord, row - 1, col, RIGHT );
                  return;
               }
               break;
            case LEFT:
               if ( validMove( maze, row, col - 1 ) ) { // move left
                  mazeTraversal( maze, xCoord, yCoord, row, col - 1, UP );
                  return;
               }
               break;
         }
   }
}

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

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;
}

void printMaze( const char maze[][ 12 ] )
{
   for ( int x = 0; x < 12; ++x ) {

      for ( int y = 0; y < 12; ++y )
         cout << maze[ x ][ y ] << ' ';

      cout << '\n';
   }

   cout << "Hit return to see next move";
   cin.get();
}

void mazeGenerator(char maze[][ 12 ], int *xPtr, int *yPtr )
{
   int a, x, y, entry, exit;

   do {
      entry = rand() % 4;
      exit = rand() % 4;
   } while ( entry == exit );

   // Determine entry position

   if ( entry == 0 ) {
      *xPtr = 1 + rand() % 10;    // avoid corners
      *yPtr = 0;
      maze[ *xPtr ][ 0 ] = '.';
   }
   else if ( entry == 1 ) {
      *xPtr = 0;
      *yPtr = 1 + rand() % 10;
      maze[ 0 ][ *yPtr ] = '.';
   }
   else if ( entry == 2 ) {
      *xPtr = 1 + rand() % 10;
      *yPtr = 11;
      maze[ *xPtr ][ 11 ] = '.';
   }
   else {
      *xPtr = 11;
      *yPtr = 1 + rand() % 10;
      maze[ 11 ][ *yPtr ] = '.';
   }

   // Determine exit location

   if ( exit == 0 ) {
      a = 1 + rand() % 10;
      maze[ a ][ 0 ] = '.';
   }
   else if ( exit == 1 ) {
      a = 1 + rand() % 10;
      maze[ 0 ][ a ] = '.';
   }
   else if ( exit == 2 ) {
      a = 1 + rand() % 10;
      maze[ a ][ 11 ] = '.';
   }
   else {
      a = 1 + rand() % 10;
      maze[ 11 ][ a ] = '.';
   }

   for ( int loop = 1; loop < MAX_DOTS; ++loop ) {   // add dots randomly
      x = 1 + rand() % 10;
      y = 1 + rand() % 10;
      maze[ x ][ y ] = '.';
   }
}

//this code will generate a maze 30x15
#include <iostream.h>
#include <stdlib.h>
#include <time.h>

enum Direction { DOWN, RIGHT, UP, LEFT };
const int ROWS = 15, COLS = 30;

void mazeTraversal( char [][ COLS ], const int, const int, int, int, int );
void mazeGenerator( char [][ COLS ], int *, int * );
void printMaze( const char[][ COLS ] );
bool validMove( const char [][ COLS ], int, int );
bool coordsAreEdge( int, int );

int main()
{
   char maze[ ROWS ][ COLS ];
   int xStart, yStart, x, y;

   srand( time( 0 ) );

   for ( int loop = 0; loop < ROWS; ++loop )
      for ( int loop2 = 0; loop2 < COLS; ++loop2 )
         maze[ loop ][ loop2 ] = '#';

   mazeGenerator( maze, &xStart, &yStart );

   x = xStart;  // starting row
   y = yStart;  // starting col

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

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

   maze[ row ][ col ] = 'x';  // insert x at current location
   printMaze( maze );

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

      for ( int move = direction, count = 0; count < 4;
            ++count, ++move, move %= 4 )
         switch( move ) {
            case DOWN:
               if ( validMove( maze, row + 1, col ) ) { // move down
                  mazeTraversal( maze, xCoord, yCoord, row + 1, col, LEFT );
                  return;
               }
               break;
            case RIGHT:
               if ( validMove( maze, row, col + 1 ) ) { // move right
                  mazeTraversal( maze, xCoord, yCoord, row, col + 1, DOWN );
                  return;
               }
               break;
            case UP:
               if ( validMove( maze, row - 1, col ) ) { // move up
                  mazeTraversal( maze, xCoord, yCoord, row - 1, col, RIGHT );
                  return;
               }
               break;
            case LEFT:
               if ( validMove( maze, row, col - 1 ) ) { // move left
                  mazeTraversal( maze, xCoord, yCoord, row, col - 1, UP );
                  return;
               }
               break;
         }
   }
}

bool validMove( const char maze[][ COLS ], int r, int c )
{
   return ( r >= 0 && r <= ROWS - 1 && c >= 0 && c <= COLS - 1 &&
           maze[ r ][ c ] != '#' );  // a valid move
}

bool coordsAreEdge( int x, int y )
{
   if ( ( x == 0 || x == ROWS - 1 ) && ( y >= 0 && y <= COLS - 1 ) )
      return true;
   else if ( ( y == 0 || y == COLS - 1 ) && ( x >= 0 && x <= ROWS - 1 ) )
      return true;
   else
      return false;
}

void printMaze( const char maze[][ COLS ] )
{
   for ( int x = 0; x < ROWS; ++x ) {

      for ( int y = 0; y < COLS; ++y )
         cout << maze[ x ][ y ] << ' ';

      cout << '\n';
   }

   cout << "\nHit return to see next move";
   cin.get();
}

void mazeGenerator( char maze[][ COLS ], int *xPtr, int *yPtr )
{
   int a, x, y, entry, exit;

   do {
      entry = rand() % 4;
      exit = rand() % 4;
   } while ( entry == exit );

   // Determine entry position
   if ( entry == 0 ) {
      *xPtr = 1 + rand() % ( ROWS - 2 );    // avoid corners
      *yPtr = 0;
      maze[ *xPtr ][ *yPtr ] = '.';
   }
   else if ( entry == 1 ) {
      *xPtr = 0;
      *yPtr = 1 + rand() % ( COLS - 2 );
      maze[ *xPtr ][ *yPtr ] = '.';
   }
   else if ( entry == 2 ) {
      *xPtr = 1 + rand() % ( ROWS - 2 );
      *yPtr = COLS - 1;
      maze[ *xPtr ][ *yPtr ] = '.';
   }
   else {
      *xPtr = ROWS - 1;
      *yPtr = 1 + rand() % ( COLS - 2 );
      maze[ *xPtr ][ *yPtr ] = '.';
   }

   // Determine exit location
   if ( exit == 0 ) {
      a = 1 + rand() % ( ROWS - 2 );
      maze[ a ][ 0 ] = '.';
   }
   else if ( exit == 1 ) {
      a = 1 + rand() % ( COLS - 2 );
      maze[ 0 ][ a ] = '.';
   }
   else if ( exit == 2 ) {
      a = 1 + rand() % ( ROWS - 2 );
      maze[ a ][ COLS - 1 ] = '.';
   }
   else {
      a = 1 + rand() % ( COLS - 2 );
      maze[ ROWS - 1 ][ a ] = '.';
   }

   for ( int loop = 1; loop < ( ROWS - 2 ) * ( COLS - 2 ); ++loop ) {
      x = 1 + rand() % ( ROWS - 2 );    // add dots to maze
      y = 1 + rand() % ( COLS - 2 );
      maze[ x ][ y ] = '.';
   }
}
0
 
Elias SalibaCommented:
pls note that the above comment contains two codes, actually they do the same job but with diff sizes ...
sorry it was a mistake posting two codes :)..
trinety
0
 
DanRollinsCommented:
The recursive algorithm uses a stack -- the function return stack.  Each call to mazeTraversal "pushes" the current location and direction moves into a new room.  Each return from that procedure "pops" that data and makes it current again.

If the school assignment requires the use of an explicit stack, then you'll need to work on an algorithm like the one I described.

-- Dan
0
 
SalteCommented:
Trinity it works if your hand is on the outer wall of the loop, but if you start out with your hand on the inner wall, you will never get out following your algorithm. Just put your hand on a pillar and follow it around and around and you'll see you can walk around without ever removing your hand from the pillar. Now that pillar can be streched and bent and turned into a part of a maze but it will still be true that you can hold your hand onto that "pillar" and never leave it and walk in circles.

If you then discover you walk in circles you can remove your hand from that wall and put your hand on the opposite wall and you should be able to get out sooner or later, that is true.

Also, if you already start out not holding your hand on such a place you will never enter it and so then too will you be able to get out.

The problem is if you initially start out holding your hand on a wall that form a closed curve or closed figure.

Alf
0
 
Elias SalibaCommented:
i still don't get your point Salte it can't be that your hand will be in the inner wall of the loop ...
the inner is not connected to any wall so it is impossible to get stuck in a loop ....
pls draw a maze for just to clarify your point ...

 #######
 #00000#
 #0###0#
->00000#
 #######

your hand will never get in the inner wall ..
trinety
0
 
DanRollinsCommented:
The wall-following algorithm will fail in two situations (I hope this proportional font trick works:

     ###########
     #                  exit
 ###   ###   ####
         x      #
 ##########
In this example, the maze solver starts at position x (and not at the 'entrance'.  He loops endlessly.

          v--hole in the wall to chamber of death
     ##  ########
     #                   <--- real exit
 ###   ###   ####
  x             #
 ##########
In this example, there are two exits... one to a chamber of death and the other to the actual exit.  

The algorithm also assumes that the maze never changes while solving (but that goes without saying, so it does not count).

You can avoid encountering either scenario by constructing the maze using normal technques.  Or you can "drop bread crumbs" to keep track of where you have been and switch walls whenever you encounter a bread crumb (though I think I can show a situation where that fails...

-- Dan







0
 
DanRollinsCommented:
Maybe this is better:
    ###########
    #                  exit
###   ###   ####
           x          #
##########




0
 
SalteCommented:
Dan explained the situation.

Yes, if you start at an entrance point you will never enter the situation I describe, the problem is if you start at a position inside the maze and then touch a wall and that wall happened to form a closed figure.

Also, the other situation that Dan describes where you have traps etc the hand on wall solution can prove fatal but that sort of goes without saying.

Another situation where it fails is if a maze has teleport points so that you are immediately transported somewhere else, that can cause funny things to happen if you follow the strategy of hand in wall.

However, in a real maze there are no teleport so it is not a problem for real mazes. It is a problem in magical fantasy mazes and game mazes though. In these situations the traps etc will also typically pose problems.

Alf
0
 
Elias SalibaCommented:
>>>Another situation where it fails is if a maze has teleport points so that you are immediately transported somewhere else, that can cause funny things to happen if you follow the strategy of hand in wall.

Got your point .. :)
trinety
0
 
DanRollinsCommented:
Sadly, it would appear that Aapkaahmad has forgotten how to type.  Aapkaahmad, if you are listening, then please respond.
-- Dan
0
 
AapkaahmadAuthor Commented:
Thanks everyone for your help, especially Trinety and Dan. This should help me finish the program up.
0
 
Elias SalibaCommented:
thanks
0

Featured Post

Free Tool: IP Lookup

Get more info about an IP address or domain name, such as organization, abuse contacts and geolocation.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

  • 8
  • 6
  • 5
  • +3
Tackle projects and never again get stuck behind a technical roadblock.
Join Now