We help IT Professionals succeed at work.

ASAP solving maze??

rickson
rickson asked
on
Medium Priority
640 Views
Last Modified: 2008-01-09
how can i solve this problem? i try to generate the function to solve maze but looks like doesn't work
?
can some one help me to solve it?


#include "Game.h"


Game::Game(int w,int h)
{
      //m = new struct maze[100][100];
      width = w;
      height = h;
      for(i=0;i<=width;i++){
            for(j=0;j<=height;j++){
                  mdimension[i][j].wall = 0;
                  mdimension[i][j].left = 0;
                  mdimension[i][j].right = 0;
                  mdimension[i][j].up = 0;
                  mdimension[i][j].down = 0;
                  mdimension[i][j].visit = 0;
                  mdimension[i][j].back = 0;
                  mdimension[i][j].path = 0;




            }
      }

}

Game::~Game()
{
}


void Game::solvemaze(int startx,int starty)
{
      int sx,sy;
      endposx = 5;
      endposy = 4;

      x=startx;
      y=starty;
      ex = endposx;
      ey = endposy;
      mdimension[x][y].path = 1;

      while(x!=ex && y!=ey)
      {
            path = 0;
            if(y!=0){
                  if((mdimension[x][y-1].wall == 0)&&(mdimension[x][y-1].path == 0)
                        &&(mdimension[x][y-1].back==0)){
                              spath[path++]=0;
                  }
            }

            if(x!=(width-1)){
                  if((mdimension[x+1][y].wall== 0)&&(mdimension[x+1][y].path == 0)
                        &&(mdimension[x+1][y].back==0)){
                        spath[path++]=1;
                  }
            }

            if(y!=(height-1)){
                  if((mdimension[x][y+1].wall== 0)&&(mdimension[x][y+1].path == 0)
                        &&(mdimension[x][y+1].back==0)){
                        spath[path++]=2;
                  }
            }
            if(x!=0){
                  if((mdimension[x-1][y].wall == 0)&&(mdimension[x-1][y].path == 0)
                        &&(mdimension[x-1][y].back==0)){
                        spath[path++]=3;
                  }
            }




            if(path>0)
            {
                  choice = spath[random(path)];
                  stack[stackptr++] = choice;
                  switch(choice)
                  {
               case 0: mdimension[x][y--].path= 1;
                              //      y--;
                       break ;

               case 1: mdimension[x++][y].path = 1 ;
                              //      x++;
                       break ;

               case 2: mdimension[x][y++].path = 1;
                              //      y++;
                       break ;

               case 3: mdimension[x--][y].path= 1;
                                    //x--;
                       break ;
            }
            }else{
                  choice = stack[--stackptr];
            switch (choice) {
               // switch off path, set backpath, change current cell
               case 0: mdimension[x][y].back = 1 ;
                                    y++;
                                    mdimension[x][y].path= 0 ;
                       break ;
               case 1: mdimension[x][y].back = 1 ;
                                    x--;
                                    mdimension[x][y].path= 0;
                       break ;
               case 2: mdimension[x][y].back = 1 ;
                                    y--;
                                    mdimension[x][y].path= 0 ;
                       break ;
               case 3: mdimension[x][y].back = 1 ;
                                 x++;
                                  mdimension[x][y].path= 0 ;
                       break ;
            }
            }
            
      }

}


void Game::mazegenerator()
{
      visit = 1;
      stackptr=0;
      x = random(width);
      y = random(height);
      totalcell = width*height;

      mdimension[0][0].wall = 1;
      mdimension[0][1].wall = 1;
      mdimension[1][1].wall = 1;
      mdimension[2][1].wall = 1;
      mdimension[2][2].wall = 1;
      mdimension[2][3].wall = 1;
      mdimension[3][3].wall = 1;
      mdimension[3][4].wall = 1;
      mdimension[3][5].wall = 1;


/*            
      while(x!=ex && y!=ey){
            cand = 0;
            if(y!=0)
                  if((mdimension[x][y].up !=2)&&(mdimension[x][y-1].wall ==0))
                        direction[cand++] = 0;
            if(x!=(width-1))
                  if((mdimension[x][y].right !=2)&&(mdimension[x+1][y].wall ==0))
                        direction[cand++] = 1;
            if(y!=(height-1))
                  if((mdimension[x][y].down !=2)&&(mdimension[x][y+1].wall ==0))
                        direction[cand++] = 2;
            if(x!=0)
                  if((mdimension[x][y].left !=2)&&(mdimension[x-1][y].wall ==0))
                        direction[cand++] = 3;

            if(cand !=0){
                  choice = direction[random(cand)];
                  stack[stackptr++] = choice;

                  switch(choice){
                  case 0: mdimension[x][y].up = 1;
                              mdimension[x][--y].down = 1;
                              mdimension[x][y].wall = 1;
                              break;
                  case 1: mdimension[x][y].right = 1;
                              mdimension[++x][y].left = 1;
                              mdimension[x][y].wall = 1;

                              break;
                  case 2: mdimension[x][y].down = 1;
                              mdimension[x][++y].up = 1;
                              mdimension[x][y].wall = 1;

                              break;
                  case 3: mdimension[x][y].left = 1;
                              mdimension[--x][y].right = 1;
                              mdimension[x][y].wall = 1;

                              break;
                  }
                  visit++;

            }else{
                  switch(stack[--stackptr]){
                  case 0:
                        y++;
                        //mdimension[x][y].up = 0;
                        //mdimension[x][--y].down = 1;
                        //mdimension[x][y].wall = 1;            
                        break;
                  case 1:
                        x--;
                        break;
                  case 2:
                        y--;
                        //mdimension[x][y].down = 1;
                        //mdimension[x][++y].up = 0;
                        //mdimension[x][y].wall = 1;
                        break;
                  case 3:
                        x++;
                        break;
                  }
            }
      }
      */
}

int Game::checkpath(int x,int y)
{
      int value;
      value = mdimension[x][y].path;
      return value;

}

int Game::checkright(int x,int y)
{
      int value;
      value = mdimension[x][y].right;
      return value;

}
int Game::checkdown(int x,int y)
{
      int value;
      value = mdimension[x][y].down;
      return value;

}

int Game::checkup(int x,int y)
{
      int value;
      value = mdimension[x][y].up;
      return value;

}

int Game::checkwall(int x,int y)
{
      int value;
      value = mdimension[x][y].wall;
      return value;

}

int Game::checkbackpath(int x,int y)
{
      int value;
      value = mdimension[x][y].back;
      return value;

}

void Game::setright(int x,int y,int value)
{
      mdimension[x][y].right = value;
}

void Game::setleft(int x,int y,int value)
{
      mdimension[x][y].left = value;
}

void Game::setup(int x,int y,int value)
{
      mdimension[x][y].up = value;
}

void Game::setback(int x,int y,int value)
{
      mdimension[x][y].back = value;
}

void Game::setdown(int x,int y,int value)
{
      mdimension[x][y].down = value;
}

void Game::setpath(int x,int y,int value)
{
      mdimension[x][y].path = value;
}


int Game::random(int limit)
{
      int res;
      res = rand()%limit;
      return res;
}



void Game::clearsolve()
{
      for(i=0;i<width;i++){
            for(j=0;j<height;j++){
                  mdimension[i][j].path = 0;
                  mdimension[i][j].back = 0;
            }
      }
}



/*
void Game::declaresize(int sz)
{
      template <class T,int sz>;

      int T[sz];
}
*/


////otehr files
#include<stdlib.h>
#include<stdio.h>

#include "Game.h"


Game *maze;

void main()
{
      maze = new Game(6,4);
      maze->mazegenerator();
      maze->solvemaze(0,0);

      for(int i=0;i<4;i++)
            for(int j=0;j<6;j++){
                  if(maze->checkwall(i,j)==0) printf("1");
                  else if(maze->checkpath(i,j)==1) printf("+");
                  else printf(" ");
                  if(j==5) printf("\n");
                  
            }
      

      //return 0;
}





//header file
/#include<stdlib.h>

class Game
{
private:
      struct maze{
            int visit;
            int left;
            int right;
            int up;
            int down;
            int path;
            int back;
            int wall;
      };

      struct maze mdimension[50][50];
      struct maze *mazeflex;
      int i,j;
      int width,height;
      int totalcell;
      int visit;
      int direction[4];
      int cand;
      int choice;
      int stack[2500];
      int stackptr;
      int x,y;
      int spath[4];
      int path;
      int rx,ry;
      int numwall;
      int k,l;
      int cexist;
      int startposx,startposy,endposx,endposy;
      int ex,ey;



public:

      int value;
      Game::Game(int,int);
      Game::~Game();
      void Game::mazegenerator();
      int Game::random(int);

      int Game::checkpath(int x,int y);
      int Game::checkup(int x,int y);
      int Game::checkdown(int x,int y);
      int Game::checkright(int x,int y);
      int Game::checkwall(int x,int y);
      int Game::checkbackpath(int x,int y);
      void Game:: setleft(int x,int y,int value);
      void Game:: setright(int x,int y,int value);
      void Game:: setup(int x,int y,int value);
      void Game:: setdown(int x,int y,int value);
      void Game:: setback(int x,int y,int value);
      void Game:: setpath(int x,int y,int value);

      void Game::solvemaze(int,int);
      void Game::clearsolve();


};

Comment
Watch Question

Author

Commented:
I have try it. but it's quite strange when it's random selected case. can someone suggest using the recursive ways
to help me solve thie problems?
CERTIFIED EXPERT
Author of the Year 2009
Commented:
I'm not going to go over all of that code, but here is how to use recursion to solve a maze:

Your maze array describes each room in such a way that you can tell which directions have doors.

You will use a search pattern as follows:
When you enter a room, you first try to go left.  If not possible, you straight ahead, if not possible, go to the right.  If not possible, go back to the previous room and try the next direction.

Here is pseudo code for your recursive fn:

global var fSolved= FALSE;

SolveFromHere(x,y, nDirection )
     if (gfSolved) {
          return  // pop back through all levels of recursion
               // note: you could record the solution on "the way back"
     }
     Check for completion (X,Y is the desired exit from the maze.
     If so you are done: {
          gfSolved= TRUE;
          return
     }
     If there is a door in nDirection.... {
          move into that room (update x,y)
          SolveFromHere( x,y, LEFT )
          if (gfSolved) {
               return  
          }
     }
     if there is no door in nDirection, swing one notch clockwise:
     if nDir==LEFT nDir=FORWARD
     if nDir==FORWARD nDir=RIGHT
     if nDir==RIGHT there is no place else to try... {
          return
          (to try a different direction in the previous room)
     }
}

It is elegant in its simplicity.  It will use up a lot of stack space fro large mazes, but nothing to worry about in C++.  

This algorithm also requires that the maze be constructed in such a way that tthere is exactly one solution (most maze-generation algorithms are like that).  If there are "islands" of rooms, the algorithm could get stuck cycling endlessly around the island.

For an alternative (stateless, non-recursive) technique see my JavaScript at:

http://home.earthlink.net/~danrollins/maze/maze.htm

-- Dan

Author

Commented:
thanks anyone i have solve it. for spending a night on it.
but now i got another problem.
can u guys help me to solve it?
>>now i got another problem.
can u guys help me to solve it?
EE rule: only 1 question in your Question.
Close this Q. and open next. Is my/DanRollings comments
helps you?
CERTIFIED EXPERT
Author of the Year 2009

Commented:
>> thanks anyone i have solve it.

Are you saying that you solved it on your own?  Or do you expect to award points?  

If you award the points to me, and if your next question is about this maze problem, I will continue helping with it.

-- Dan

Author

Commented:
I expect to give the points to someone else who solve this new problems.
this previous question that i ask already solve by myself.
CERTIFIED EXPERT
Author of the Year 2009

Commented:
I am so happy that you solved the problem.  I could just dance with joy!  How did you solve it?  What was the solution?

-- Dan

Author

Commented:
I'm using deep first search algorithm.
it's waste my time the whole night to solve it.
CERTIFIED EXPERT
Author of the Year 2009

Commented:
Well then perhaps you could apply the same algorithm to solve your next problem:

1) create a question on EE
2) post a bunch of code and ask "why doesn't this work"
3) Don't bother replying in any detail when an expert asks you a question
4) Stay up all night
5) repeat steps 1-4 until the solution is reached.

That should solve your next question, too.  Good luck!

-- Dan

Author

Commented:
haha....
why someone is so curious to get tjhose points.
I  will give the point if it's really helpful.
I think previously i can't solve it that's why I quickly post the question.
but what i can say, instead i put this question.
it's better for me to ask another question.
if someone really want this point, I will give it, i just know that In this EE some of them just want to get point for not answering some question. but want to get a points.
and then points is given depends on the person not the answer.
:)

Commented:
I think you forgot this question. I will ask Community Support to close it unless you finalize it within 7 days. Unless there is objection or further activity,  I will suggest to refund the points and delete this question.

rickson
You have 5 questions out of 8 that need your attention! Please take some time to either accept an answer or provide feddback when needed. As the experts remineded you here, please don't change the topic within a question. Instead finish the old one and post a new question.

PLEASE DO NOT ACCEPT THIS COMMENT AS AN ANSWER!
======
Werner

Author

Commented:
answer solved already
Force-accepted by
Netminder
Community Support Moderator
Experts Exchange

Explore More ContentExplore courses, solutions, and other research materials related to this topic.