?
Solved

Maze Program in C++ using stack and array!

Posted on 2003-03-25
25
Medium Priority
?
12,984 Views
Last Modified: 2012-06-22

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
Comment
Question by:Aapkaahmad
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 8
  • 6
  • 5
  • +3
25 Comments
 
LVL 4

Expert Comment

by:n_fortynine
ID: 8209244
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
 
LVL 49

Expert Comment

by:DanRollins
ID: 8209530
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
 
LVL 12

Expert Comment

by:Salte
ID: 8209619
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
Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
LVL 2

Expert Comment

by:Elias Saliba
ID: 8210239
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
 
LVL 12

Expert Comment

by:Salte
ID: 8210293
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
 

Author Comment

by:Aapkaahmad
ID: 8210471
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
 
LVL 12

Expert Comment

by:Salte
ID: 8211064
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
 
LVL 2

Expert Comment

by:Elias Saliba
ID: 8212499
>>>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
 
LVL 2

Expert Comment

by:Elias Saliba
ID: 8212509
ooopppss just copy and past that maze in the notepad to see it better

sorry for that ..
trinety
0
 

Author Comment

by:Aapkaahmad
ID: 8212778

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
 
LVL 49

Expert Comment

by:DanRollins
ID: 8212865
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
 
LVL 4

Expert Comment

by:n_fortynine
ID: 8213017
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
 
LVL 1

Expert Comment

by:keitha1
ID: 8213103
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
 
LVL 2

Accepted Solution

by:
Elias Saliba earned 375 total points
ID: 8213149
//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
 
LVL 2

Expert Comment

by:Elias Saliba
ID: 8213190
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
 
LVL 49

Expert Comment

by:DanRollins
ID: 8214018
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
 
LVL 12

Expert Comment

by:Salte
ID: 8216299
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
 
LVL 2

Expert Comment

by:Elias Saliba
ID: 8220547
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
 
LVL 49

Expert Comment

by:DanRollins
ID: 8220926
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
 
LVL 49

Expert Comment

by:DanRollins
ID: 8220932
Maybe this is better:
    ###########
    #                  exit
###   ###   ####
           x          #
##########




0
 
LVL 12

Expert Comment

by:Salte
ID: 8223455
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
 
LVL 2

Expert Comment

by:Elias Saliba
ID: 8234617
>>>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
 
LVL 49

Expert Comment

by:DanRollins
ID: 8259729
Sadly, it would appear that Aapkaahmad has forgotten how to type.  Aapkaahmad, if you are listening, then please respond.
-- Dan
0
 

Author Comment

by:Aapkaahmad
ID: 8261890
Thanks everyone for your help, especially Trinety and Dan. This should help me finish the program up.
0
 
LVL 2

Expert Comment

by:Elias Saliba
ID: 8264298
thanks
0

Featured Post

Free Tool: SSL Checker

Scans your site and returns information about your SSL implementation and certificate. Helpful for debugging and validating your SSL configuration.

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.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

When writing generic code, using template meta-programming techniques, it is sometimes useful to know if a type is convertible to another type. A good example of when this might be is if you are writing diagnostic instrumentation for code to generat…
Go is an acronym of golang, is a programming language developed Google in 2007. Go is a new language that is mostly in the C family, with significant input from Pascal/Modula/Oberon family. Hence Go arisen as low-level language with fast compilation…
The goal of the tutorial is to teach the user how to use functions in C++. The video will cover how to define functions, how to call functions and how to create functions prototypes. Microsoft Visual C++ 2010 Express will be used as a text editor an…
The viewer will learn how to user default arguments when defining functions. This method of defining functions will be contrasted with the non-default-argument of defining functions.
Suggested Courses

800 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question