asked on

ASAP solving maze??

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();

};

AlexVirochovsky

example of maze programm see in
http://www.programmersheaven.com/zone8/cat121/13274.htm

rickson

ASKER

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?

ASKER CERTIFIED SOLUTION

DanRollins

membership

This solution is only available to members.

To access this solution, you must be a member of Experts Exchange.

Start Free Trial

rickson

ASKER

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?

AlexVirochovsky

>>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?

DanRollins

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

rickson

ASKER

I expect to give the points to someone else who solve this new problems.
this previous question that i ask already solve by myself.

DanRollins

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

rickson

ASKER

I'm using deep first search algorithm.
it's waste my time the whole night to solve it.

DanRollins

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

rickson

ASKER

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.
:)

griessh

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

rickson

ASKER

answer solved already

Netminder

Force-accepted by
Netminder
Community Support Moderator
Experts Exchange