Thread: the maze

  1. #1
    Registered User
    Join Date
    Feb 2006
    Posts
    11

    the maze

    hi techies

    i needed a game program that generates a maze using c++ with all its lines parralel to either x-axis or y-axis
    iwhat i did was to type individual line commands

    eg. line(540,67,540,67);
    but the program was too lengthy
    can you suggest a shorter way and i don't prefer using class concept which i don't know
    looks like i am trapped in a maze can u please help me? :-0

  2. #2
    Supermassive black hole cboard_member's Avatar
    Join Date
    Jul 2005
    Posts
    1,709
    Quote Originally Posted by nikhil_trichy
    hi techies

    i needed a game program that generates a maze using c++ with all its lines parralel to either x-axis or y-axis
    iwhat i did was to type individual line commands

    eg. line(540,67,540,67);
    but the program was too lengthy
    can you suggest a shorter way and i don't prefer using class concept which i don't know
    looks like i am trapped in a maze can u please help me? :-0
    Post what you did so we can help you.
    Good class architecture is not like a Swiss Army Knife; it should be more like a well balanced throwing knife.

    - Mike McShaffry

  3. #3
    Registered User
    Join Date
    Feb 2006
    Posts
    11
    i had given an example
    its too long to be typed here i typed individual line(x1,y1,x2,y2) commands
    for example
    :
    line(20,40,20,60);
    line(40,80,80,120);
    and so on

  4. #4
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    Store all the endpoints in an array of some sort, then use a loop to iterate over the array to draw all the lines
    Code:
    typedef struct point {
      int x;
      int y;
    } point;
    typedef struct line {
      point start;
      point end;
    } line;
    
    line lineArray[] = {
     { { 20, 40 }, { 20, 60 } },
     { { 40, 80 }, { 80, 120 } },
    };
    
    for ( i = 0 ; i < 2 ; i++ ) {
      line ( lineArray[i].start.x, lineArray[i].start.y, 
             lineArray[i].end.x, lineArray[i].end.y );
    }

  5. #5
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    First each maze cell can have the following common characteristics.

    1. Each one can have up to 4 border lines.
    2. Each one is a perfect square.
    3. The determining factor if a line is drawn is whether or not the neighboring cell for the line is empty or can be moved into/onto.

    So:

    Code:
    struct MazeCell
    {
       bool bNorth;
       bool bSouth;
       bool bEast;
       bool bWest;
    
       MazeCell(void):bNorth(true),bSouth(true),bEast(true),bWest(true) {}
    };
    
    void RenderMaze(int iStartX,int iStartY,int iMazeWidth,int iMazeHeight,int iCellSize,MazeCell *pMaze)
    {
      int iMapOffset=0;
    
      iStartX+=(iCellSize)>>1;
      iStartY+=(iCellSize)>>1;
    
      int x=0;
      int x2=0;
      int y=0;
      int y2=0;
    
      for (int i=iStartY;i<(iStartY+iMazeHieght)-iCellSize;i+=iCellSize)
      {
         for (int j=iStartX;j<(iStartX+iMazeWidth)-iCellSize;j+=iCellSize)
         {
            x=j;
            y=i,
            x2=j+iCellSize;
            y2=i+iCellSize;
    
            if (pMaze[iMapOffset].bNorth) DrawLine(x,y,x2,y);
            if (pMaze[iMapOffset].bSouth) DrawLine(x,y2,x2,y2);
            if (pMaze[iMapOffset].bEast) DrawLine(x2,y,x2,y2);
            if (pMaze[iMapOffset].bWest) DrawLine(x,y,x,y2);
    
            iMapOffset++;
         }
       }
    }
    I leave it to you to create the maze. Note that the following must be true:

    (iMazeWidth/iCellSize) == iMazeMapWidth
    (iMazeHeight/iCellSize) == iMazeMapHeight

    Or the code will crash.
    Last edited by VirtualAce; 02-26-2006 at 04:37 PM.

  6. #6
    GA ichijoji's Avatar
    Join Date
    Nov 2002
    Posts
    179
    As far as generating the maze, I think you could do pretty good with a bfs kind of algorithm. One way to do it would be to keep a stack of paths and expand them into a tree using several constraints that you determine. I would implement it like this:
    Code:
    struct Point {
        int x, y;
    };
    
    Point* expandPoint(Point& point, int dir) {
        static int dx[4] = {1,0,-1,0};
        static int dy[4] = {0,1,0,-1};
    
        Point* ret = new Point;
        ret->x = point.x + dx[dir%4];
        ret->y = point.y + dy[dir%4];
        return ret;
    }
    
    struct path {
        int pointCount, childrenCount;
        Point pointList[BUFSIZE];
        Path* childrenList[BUFSIZE];
    
        Point linkPoint;
        Path* parent;
    };
    
    Path* makeChildPath(Path* parent) {
        Path *path = new Path;
        path->linkPoint = parent->pointList[parent->pointCount-1];
        path->pointCount = 1;
        path->childrenCount = 0;
        path->parent = parent;
        parent->children[parent->childrenCount++] = path;
        return path;
    }
    
    bool pointCollidesWithPath(Point& point, Path& path) {
        for (int i = 0; i < path.pointCount; ++i)
            if (pointList[i].x == point.x && pointList[i].y == point.y)
                return true;
        return false;
    }
    
    Path* genMaze(int w, int h, Point startPoint) {
        int i, j;
    
        //adjustment vars
        int branchProb = 5, maxBranchLength = 5;
    
        int pathListLength = 1, pathStackLength = 1;
        Path *pathList[BUFSIZE]; //list of all paths for collision direction
        Path *pathStack[BUFSIZE]; //stack of paths for traversal
    
        Path* startPath = new Path;
        startPath->pointList[0] = startPoint;
        startPath->pointCount = 1;
        startPath->childrenCount = 0;
    
        pathList[0] = startPath;
        pathStack[0] = startPath;
    
        //breadth first traversal
        while (pathStackLength > 0) {
            Path* path  = pathStack[rand()%pathStack.length];
    
            //branch
            if (!(rand()%branchProb)) {
                Path* newPath = makeChildPath(path);
                pathList[pathListLength++] = newPath;
                pathStack[pathStackLength++] = newPath;
                path = newPath;
            }
    
            //expand
            int branchLength = rand()%maxBranchLength/2+maxBranchLength/2;
            bool turned = true;
            for (i = 0; i < branchLength && true; ++i) {
                turned = false;
                int turnOffset = rand()%4;
                for (j = turnOffset; j < turnOffset+4 && !turned; ++j) {
                    Point* newPoint = expandPoint(path->pointList[path->pointCount-1],j);
                    bool collides = newPoint->x >= w || newPoint->x < 0 || newPoint->y >= h || newPoint->y < 0;
                    for (k = 0; k < pathListLength && !collides; ++k)
                        if (pointCollidesWithPath(*newPoint,pathList[k]))
                            collides = true;
                    if (!collides) {
                        path->pointList[path->pointCount++] = *newPoint;
                        turned = true;
                    } else
                        delete newPoint;
                }
            }
            if (i < branchLength) { //got stuck
                remove path from pathStack
        }
    
        return pathList[0]; //return root of maze tree
    }
    I hope that's helpful. It's just a traversal across the tree picking a random path to expand and expanding it in random directions without colliding until you get stuck or go a certain distance, then it stops when it can't expand any more paths (ie the board is full). This has will always generate a maze that covers every available place, and returns the maze as a tree of paths. To render to maze, you would just have to do something like this:
    Code:
    void renderPath(Path* path) {
        int i, j;
        //render this path
        for (j = 0; j < path->pointCount-1; ++j)
            remove the edge between path->pointList[j] and path->pointList[j+1]
    
        //render children
        for (j = 0; j < path->childrenCount; ++j) {
            remove the edge between path->children[j]->pointList[0] and path->children[j].linkPoint to connect the paths
            renderPath(path->children[j]);
        }
    }
    
    void renderMaze(Path* mazeRoot) {
        render the board as a grid of boxes
        renderPath(mazeRoot); //start rendering paths with the root 
    }
    There are definitely better ways to write this (I would especially look at dynamically allocating and managing all your lists so that you don't overrun your arrays), but the idea should work. I think.

    edit:
    I just rewrote this whole thing to not use classes. See? It's easy to switch back and forth, don't be intimidated!
    Last edited by ichijoji; 02-26-2006 at 11:54 PM.
    Illusion and reality become impartiality and confidence.

  7. #7

  8. #8
    Registered User
    Join Date
    Feb 2006
    Posts
    11
    i trie d this
    Code:
    #include<graphics.h>
    #define player circle(x1,y1,10)
    
    int x2={ 40,80,37,....}
    int y2={48,82,93...}
    int x3={40,87,290,93...}
    int y3={........}
    
    void main()
    {
     
    display maze();
    check();//to check whether the line is touching any lines of the maze
    }
    
    
    display maze
    {
    for(some loop)
    {line[x2[i],y2[i],x3[i],y3[i])
    }
    
    void check(void)
    {
    
    if (x2[i]==x3[i])  //if the line is parallel to y axis
    {
        if y2[i]>y3[i]
    {
        if(x1==(x2[i]-10)||x`==x2[i]+10)&&(y1>=y3{i]&&(y1<=y2[i])   
    
         {
           something will happen     
     }
    
    // to check whether the y   coordinate of the circle is in between the y coordinates of the line
    similarly y2<y3 andfor line parallel to x axis and x2>x3 and x3>x2
    display maze is working properly but not the function check()


    in short(??)
    i want to move a circle through the maze maze and find out whether the circle
    is touching the lines or not
    can you please suggest corrections or alternatives to the above coding

  9. #9
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    We already told you several ways to do it. Try those. I can't even understand what yours is doing.

  10. #10
    Registered User
    Join Date
    Feb 2006
    Posts
    11
    u all have told me how to generate a maze and thanx a lot for it
    but i had a brainwave(???) and decided to render the maze in the way i hav already mentioned but now comes the problem .
    i want to check if the object i am moving is touching the lines of the maze or not
    can you help me??

    i am moving the circle by using the code given below
    Code:
    :
    :
    ch=getch();
    if(ch==some ascii value)
    {
    increment or decrement x or y coordinates
    }
    similarly for other cases
    }

  11. #11
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    Not with that kind of information I can't.

  12. #12
    Registered User
    Join Date
    Feb 2006
    Posts
    11
    i will post my problem in short for u all once again(how many agains more)
    i use a function to display a maze. the working of thye function i have already explained.
    then i tried to check whether the object i am moving is touching lines of the maze or not,
    by calling the function check() the working of which i explained in my prev messages
    but the object is being checked only for certain lines and not for the others
    can you help me??

  13. #13
    Registered User
    Join Date
    Feb 2006
    Posts
    11
    i am a student and has to complete a project in which i have to generate amaze and
    check whether the object i am moving is touching the lines of the maze or not . the rule is that i can use only c++ functions and not classes structures or anyother concepts
    i tried a program but it is workuing only partly



    using only c++)
    Code:
    #define player circle(x1,y1,10)
    x1=20;
    y1=415;
    int x2={ 40,80,37,....}  //array to store initial x coordinates of lines
    int y2={48,82,93...}	//array tro store initial y coordinates of lines that form the maze
    int x3={40,87,290,93...}//final points
    int y3={........}//final points
    
    	void main()
    	{
    		 char ch;
    		while(1)
    		{
    			display_maze();
    		        ch=getch();
    			if(ch==27)//ASCII value for esc
    				exit(0);
    			if(ch==72)	//
    			etc..
    			//different ASCII values are checked and the coordinates x1 y1 are incremented
    			//to move the circle
    
    
    
    			check();//to check whether the line is touching any lines of the maze
    }
    
    
    void display_maze(void)
    {
    for(int i=0; i<60; ++i)
    
    {line[x2[i],y2[i],x3[i],y3[i])
    }
    
    void check(void)
    {
    for(int i=0 ; i<60; i++)
    {
    if (x2[i]==x3[i])  //if the line is parallel to y axis
    {
        if y2[i]>y3[i]
    {
        if(x1==(x2[i]-10)||x`==x2[i]+10)&&(y1>=y3{i]&&(y1<=y2[i])   
    
         {
           x1=20;//initial positions
    	y1=415;//of the circle
    	chances--;
     }
    
    
    // to check whether the y   coordinate of the circle is in between the y coordinates of the line
    similarly the loop contains code for checking y2<y3 and for line parallel to x axis and x2>x3 and x3>x2

    }


    the function display maze()is working but not the function check()- it is only checking some lines
    and not the others

    in short(??)
    i want to move a circle through the maze maze and find out whether the circle
    is touching the lines or not
    can you please suggest corrections or alternatives to the above coding
    Last edited by Salem; 03-02-2006 at 01:41 AM. Reason: delete email address

  14. #14
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    ...only c++ functions
    Ok.....

    I will help one more time. Anything more than this and I might as well write the program for you.

    Just for kicks you can alter the structure approach I used and instead use bit masks to represent directions.

    Code:
    #define DIR_NORTH 0x01
    #define DIR_SOUTH 0x02
    #define DIR_EAST 0x04
    #define DIR_WEST 0x08
    
    #define DIR_ALL  (NORTH) | (SOUTH) | (EAST) | (WEST)
    And just in case your teacher wont let you use bit masks you can look at this map in memory and use a different approach.

    1 1 1 1 1 1 1 1 1 1 1 1
    1 0 1 0 0 0 0 0 0 0 0 0
    1 0 1 0 0 0 0 0 0 0 0 1
    1 2 1 1 1 1 0 1 1 1 1 1
    1 0 0 0 0 1 0 0 0 0 0 1
    0 0 0 0 0 0 0 0 0 0 0 1
    1 1 1 1 1 1 1 1 1 1 1 1
    0 = empty
    1 = wall
    2 = player position


    Code:
    #define PLAYER_PIECE 0x02
    
    
    ....
    int offset=iMapWidth+2;
    int x=0,y=0;
    
    for (int i=1;i<iMapHeight-2;i+=2)
    {
      for (int j=1;j<iMapWidth-2;j+=2)
      {
         int offsetLeft=offset-1;
         int offsetUp=offset-iMapWidth;
         int offsetDown=offset+iMapWidth;
         int offsetRight=offset+1;
      
         if (Map[offsetLeft]) DrawLine(x,y,x,y+iCellSize);
         if (Map[offsetRight) DrawLine(x+iCellSize,y,x+iCellSize,y+iCellSize);
         if (Map[offsetUp)) DrawLine(x,y,x+iCellSize,y);
         if (Map[offsetDown) DrawLine(x,y+iCellSize,x+iCellSize,y+iCellSize);
    
    
         if (Map[offset]==PLAYER_PIECE) DrawCircle(x,y,iCellSize/2);
    
         x+=iCellSize;
      }
      x=0;
      y+=iCellSize;
    }
    ...
    You could use both methods and use the above routine to instead use bitwise operations to compute the directions and save them in another map. Then it would be easier to check for directions.

    Code:
    bool MoveLeft(int px,int py,int iMapWidth,int &outOffset)
    {
      //Bail on error
      if ((px-1)<1) return true;
    
      int offset=py*iMapWidth_px;
      
      if ((DirectionMap[offset-1] & DIR_EAST) == DIR_EAST)
      {
         return true;  //Cannot move here
      }
      else outOffset=offset-1;
    
      return false;
    }
    No matter what limits your teacher puts on the project, I could code this. It would just be uglier and less efficient the more tools they took away from me.

    So stick it to your teacher and code this using several methods. Make it look easy.
    Last edited by VirtualAce; 03-02-2006 at 12:38 AM.

  15. #15
    Registered User
    Join Date
    Feb 2006
    Posts
    11
    what if i wanted to put hte player to the initial position when he touches the wall of the maze??

    and of course as it always happens with me another brainwave( oh my god!! not again)
    can getpixel() be of any help???

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Having trouble solving maze.
    By eurus in forum C Programming
    Replies: 3
    Last Post: 02-17-2006, 01:52 AM
  2. Q: Recursion to find all paths of a maze
    By reti in forum C Programming
    Replies: 7
    Last Post: 11-26-2002, 09:28 AM
  3. My Maze Game --- A Few Questions
    By TechWins in forum Game Programming
    Replies: 18
    Last Post: 04-24-2002, 11:00 PM
  4. Algorithm to walk through a maze.
    By Nutshell in forum C Programming
    Replies: 30
    Last Post: 01-21-2002, 01:54 AM
  5. Maze game, complete with maze editor and an example maze!
    By Brian in forum A Brief History of Cprogramming.com
    Replies: 2
    Last Post: 01-20-2002, 03:27 AM