noobie maze program

This is a discussion on noobie maze program within the C Programming forums, part of the General Programming Boards category; Im working on a maze solving program and i'm a little lost. It should just follow the maze walls to ...

  1. #1
    Registered User
    Join Date
    Oct 2005
    Posts
    53

    noobie maze program

    Im working on a maze solving program and i'm a little lost. It should just follow the maze walls to the right and find the exit using: west=0, north=1,east=2,south=3.

    The '.' represent open spaces in the maze, and the '#' represent walls.

    I have the maze and i have it printing but i am not sure how to do a solving function. I have searched but everything i found just confuses me and i cant figure out how to implement it in my program . Please help


    code
    Code:
    #include <stdio.h>
    #include <string.h>
    
     
     
    void display( char maze[12][12],int row, int column )
    {
    int i,j;
    for( i = 0; i<12; i++)
    {
    for( j = 0; j<12; j++)
    {
    printf( "%c", maze[i][j]);
    }
    printf("\n");
    }
    
    
    
    
    
    int main()
    {
    int row = 2;
    int column = 0;
    int direction; 
    char maze[12][12] = {'#','#','#','#','#','#','#','#','#','#','#','#',
    	             '#','.','.','.','#','.','.','.','.','.','.','#',
    	             'x','.','#','.','#','.','#','#','#','#','.','#',
    	             '#','#','#','.','#','.','.','.','.','#','.','#',
    	             '#','.','.','.','.','#','#','#','.','#','.','.',
    	             '#','#','#','#','.','#','.','#','.','#','.','#',
    	             '#','.','.','#','.','#','.','#','.','#','.','#',
    	             '#','#','.','#','.','#','.','#','.','#','.','#',
    	             '#','.','.','.','.','.','.','.','.','#','.','#',
    	             '#','#','#','#','#','#','.','#','#','#','.','#',
    	             '#','.','.','.','.','.','.','#','.','.','.','#',
    	             '#','#','#','#','#','#','#','#','#','#','#','#',};
    
    
     
    
    
    return 0;
    
          
    }
    Last edited by stormfront; 11-28-2005 at 01:52 PM.

  2. #2
    Registered User
    Join Date
    Sep 2003
    Posts
    34
    I've been working on a little maze solving program of my own, I'm at work so I don't have any code to show but you have looked at the A* path finding algorythm at all? Here's a good link ..

    http://www.policyalmanac.org/games/aStarTutorial.htm

    If you need any more help, I'll see what I can do.
    -gunder

    if (problem)
    postcount++;

  3. #3
    Gawking at stupidity
    Join Date
    Jul 2004
    Location
    Oregon, USA
    Posts
    3,163
    One way would be to always try the same direction in every room until you hit a wall. Then try another direction until you hit a wall. If you reach a dead-end back up until you reach a room with a direction you haven't tried. This is pretty easy to implement with a recursive function, but some people might argue that a recursive solution isn't the best.

    So the algorithm might look something like:
    - if no wall to the east, enter the room to the east and loop, otherwise go back to the last room
    - if no wall to the north, enter the room to the north and loop, otherwise go back to the last room
    - if no wall to the west, enter the room to the west and loop, otherwise go back to the last room
    - if no wall to the south, enter the room to the south and loop, otherwise go back to the last room
    - else, nowhere to go, return to last room

    The reason recursive functions work so well here is because it's easy to get back to the last room by just returning. Instead of looping at each step you just call your recursive function with the new room coordinates.

    This doesn't exactly meet your requirements, but here's a simple maze program I wrote to help someone else on this board:
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    #define W_EAST  0x1
    #define W_SOUTH 0x2
    #define W_WEST  0x4
    #define W_NORTH 0x8
    #define CHECKED 0x10
    
    unsigned char **maze = NULL;
    int dimx, dimy;
    int curx, cury;
    int goalx, goaly;
    
    char *dirs = NULL;
    int curdir;
    
    void read_file(void)
    {
      char *vals = "0123456789ABCDEF";
      char buf[4096];
      FILE *fp;
      int i, j;
    
      if(!(fp = fopen("maze.txt", "r")))
      {
        puts("Couldn't open maze.txt for reading!");
        exit(EXIT_FAILURE);
      }
    
      fgets(buf, sizeof(buf), fp);
      sscanf(buf, "%d %d", &dimx, &dimy);
      fgets(buf, sizeof(buf), fp);
      sscanf(buf, "%d %d", &curx, &cury);
      fgets(buf, sizeof(buf), fp);
      sscanf(buf, "%d %d", &goalx, &goaly);
    
      printf("Maze is %d by %d. Attempt to go from %d,%d to %d,%d\n",
        dimx, dimy, cury, curx, goaly, goalx);
    
      if(!(maze = malloc(sizeof(char *) * dimy)))
      {
        puts("Memory allocation error!");
        exit(EXIT_FAILURE);
      }
    
      for(i = 0;i < dimy;++i)
      {
        if(!(maze[i] = malloc(dimx)))
        {
          puts("Memory allocation error!");
          exit(EXIT_FAILURE);
        }
    
        fgets(buf, sizeof(buf), fp);
    
        for(j = 0;j < dimx;++j)
          maze[i][j] = strchr(vals, buf[j]) - vals;
      }
    
      fclose(fp);
    }
    
    void print_maze(void)
    {
      int i, j;
    
      for(i = 0;i < dimy;++i)
      {
        for(j = 0;j < dimx;++j)
          printf("%X ", maze[i][j]);
        putchar('\n');
      }
    }
    
    int try_coord(int y, int x)
    {
      unsigned char val = maze[y][x];
    
      maze[y][x] |= CHECKED;
    
      if(y == goaly && x == goalx)
        return 1;
    
      if(!(val & W_NORTH) && !(maze[y - 1][x] & CHECKED))
        if(try_coord(y - 1, x))
        {
          dirs[curdir++] = 'N';
          return 1;
        }
      if(!(val & W_SOUTH) && !(maze[y + 1][x] & CHECKED))
        if(try_coord(y + 1, x))
        {
          dirs[curdir++] = 'S';
          return 1;
        }
      if(!(val & W_EAST) && !(maze[y][x + 1] & CHECKED))
        if(try_coord(y, x + 1))
        {
          dirs[curdir++] = 'E';
          return 1;
        }
      if(!(val & W_WEST) && !(maze[y][x - 1] & CHECKED))
        if(try_coord(y, x - 1))
        {
          dirs[curdir++] = 'W';
          return 1;
        }
    
      return 0;
    }
    
    void print_solution(void)
    {
      puts("\nSolution:");
      while(--curdir > -1)
        printf("%c ", dirs[curdir]);
      putchar('\n');
    }
    
    int main(void)
    {
      read_file();
    
      if(!(dirs = calloc(1, dimx * dimy)))
      {
        puts("Memory allocation error!");
        return 0;
      }
      curdir = 0;
    
      print_maze();
    
      if(!try_coord(cury, curx))
        puts("No solution found");
      else
        print_solution();
    
      return EXIT_SUCCESS;
    }
    maze.txt looks like:
    Code:
    5 5
    0 4
    4 1
    DC8AB
    575CB
    4A15F
    5C169
    776A3
    Hopefully the try_coord() function will help you. That's where the whole solution-finding happens.
    Last edited by itsme86; 11-28-2005 at 02:06 PM.
    If you understand what you're doing, you're not learning anything.

  4. #4
    cwr
    cwr is offline
    Registered Luser cwr's Avatar
    Join Date
    Jul 2005
    Location
    Sydney, Australia
    Posts
    868
    Here's far more than you ever wanted to know about mazes, including many solving algorithms.

  5. #5
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,590
    The recursive method can also be implemented via a stack. The stack keeps track of previous maze cells.

    1. Choose a direction.
    2. If direction is available, push current cell to stack, goto 1, else 3.
    3. Pop cell off of stack and goto 1

    Final stack is solution.

  6. #6
    Registered User
    Join Date
    Oct 2005
    Posts
    53
    wow, thx for the info everyone. Ill get to work on some of these ideas tommorow and see what i can come up with.

  7. #7
    Registered User
    Join Date
    Oct 2005
    Posts
    53
    Quote Originally Posted by gunder
    I've been working on a little maze solving program of my own, I'm at work so I don't have any code to show but you have looked at the A* path finding algorythm at all? Here's a good link ..

    http://www.policyalmanac.org/games/aStarTutorial.htm

    If you need any more help, I'll see what I can do.
    wow A* seems interesting but i dont have enough time to dive into it at the moment. Everyone keeps telling me this is easy, but im not getting anywhere. Im having trouble assigning directions to number like i want 0,1,2,3, and following the right wall....not real sure how to go about it. I havent learned stacks yet, so i kinda want to avoid them right now.

    I came across this but i am not sure how to utilize and adjust it for my program, any ideas?

    Code:
    if( north != been_there_done_that )
        recursive( here->north );
    if( east != been_there_done_that )
        recursive( here->east );
    if( south != been_there_done_that )
        recursive( here->south );
    if( west != been_there_done_that )
        recursive( here->west );
    return at_a_dead_end;
    Last edited by stormfront; 11-29-2005 at 02:48 PM.

  8. #8
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,590
    A stack is simple.

    A pop removes the top item from the stack.
    A push places an item on top of top item on the stack.

    Essentially like a stack of plates.

    Pop - take top plate off of the stack of plates.
    Push - add a plate to the top of the stack of plates.


    The STL has an excellent class just for this.

    But if you want to, you can use a vector from the STL.
    You could use an array, but you don't know how many moves will be in the final array so it would be a waste of space and would not be any fun attempting to resize the array to fit more elements.

  9. #9
    Registered User
    Join Date
    Oct 2005
    Posts
    53
    man, im so lost on this....im gonna have hell tommorow tryin to write this in lab.

  10. #10
    Registered User
    Join Date
    Oct 2005
    Posts
    53
    eh, i figured it out. yay for me. If anyone wants me to post the final code i will. it now displays the graph after each move and counts the total number of times moved north south east and west.
    Last edited by stormfront; 11-30-2005 at 12:21 PM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. BOOKKEEPING PROGRAM, need help!
    By yabud in forum C Programming
    Replies: 3
    Last Post: 11-16-2006, 10:17 PM
  2. Can someome help me with a program please?
    By WinterInChicago in forum C++ Programming
    Replies: 3
    Last Post: 09-21-2006, 10:58 PM
  3. Need help with my program...
    By Noah in forum C Programming
    Replies: 2
    Last Post: 03-11-2006, 06:49 PM
  4. my server program auto shut down
    By hanhao in forum Networking/Device Communication
    Replies: 1
    Last Post: 03-13-2004, 09:49 PM
  5. My program, anyhelp
    By @licomb in forum C Programming
    Replies: 14
    Last Post: 08-14-2001, 10:04 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21