Thread: Maze traversal in c

  1. #1
    Registered User
    Join Date
    Mar 2019
    Posts
    15

    Thumbs up Maze traversal in c

    I believe i have done most of it but to be honest i am not sure . the logic really hurts my head. the numbers in the first line of maze03.txt file are the rows and column of the maze, entry column and entry row of the maze and the exit row and exit column. I m good with reading from the file and outputting the maze. I believe I am also good with defining direction in the maze. After that I am not too sure. I under stand you should look for a wall(Hashtags) and not go over it but only spaces are walk able. Please any Guidance will be appreciated thank you.
    Attached Files Attached Files

  2. #2
    Programming Wraith GReaper's Avatar
    Join Date
    Apr 2009
    Location
    Greece
    Posts
    2,739
    When do you thing this will stop looping?
    Code:
    while ( (currentX != rowEnd) || (currentY != columnEnd))
    Hint: When neither of them is true.
    Devoted my life to programming...

  3. #3
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    My suggestion is that you create some really simple mazes in say a 10x10 grid.

    Really simple mazes like:
    - Straight line from in to out.
    - A single turn.
    - A tee junction.

    The point of doing this is that it's a lot easier to see what your logic is up to when you only have one case to observe at once.

    Progressively build a library of test case mazes you can feed into your program when you make changes.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  4. #4
    Registered User
    Join Date
    Mar 2019
    Posts
    15
    so It should be and not or?

  5. #5
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    Well here is your code, nicely formatted.
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <stdbool.h>
    
    int main()
    {
      // all variables declared
      int rows, columns, r, c, i, rowStart, columnStart, rowEnd, columnEnd, currentX, currentY;
      char **mazeblock;
      char orientation;
      FILE *fPointer;               // file pointer
    
      //read file into array
      fPointer = fopen("maze01.txt", "r");
      if (fPointer == NULL) {
        printf("Error in opening file\n");
        exit(1);                    // help check opening error
      }
      fscanf(fPointer, " %d %d %d %d %d %d \n", &rows, &columns, &rowStart, &columnStart, &rowEnd, &columnEnd);
    
      // Dynamically allocate memory
      mazeblock = (char **) malloc(sizeof(char *) * rows);
    
      // failure to allocate memory
      if (!mazeblock) {
        printf("memmory allocation failed");
      }
    
      for (i = 0; i < rows; i++) {
        mazeblock[i] = (char *) malloc(sizeof(char) * columns);
      }
    
      // to read in the maze
      for (r = 0; r < rows; r++) {
        for (c = 0; c < columns; c++) {
          fscanf(fPointer, "%c", &mazeblock[r][c]);
        }
      }
      fclose(fPointer);
    
      // Defining direction
      if (rowStart == 0) {
        orientation = 'S';
      } else if (rowStart == (rows - 1)) {
        orientation = 'N';
      } else if (columnStart == 0) {
        orientation = 'E';
      } else {
        orientation = 'W';
      }
    
      // to hold direction
      currentX = rowStart;
      currentY = columnStart;
    
      //
      // for going south rules
      while ((currentX != rowEnd) || (currentY != columnEnd)) {
        if (orientation == 'S') {
          if ((currentY > 0) && (mazeblock[currentX][currentY - 1] == ' ' || mazeblock[currentX][currentY - 1] == '#')) {
            mazeblock[currentX][currentY] = '#';
            --currentY;
            orientation = 'W';
          } else if ((currentX < (rows - 1))
                     && (mazeblock[currentX + 1][currentY] == ' ' || mazeblock[currentX + 1][currentY] == '#')) {
            mazeblock[currentX][currentY] = '#';
            ++currentX;
            orientation = 'S';
          } else if ((currentY < (columns - 1))
                     && (mazeblock[currentX][currentY + 1] == ' ' || mazeblock[currentX][currentY + 1] == '#')) {
            mazeblock[currentX][currentY] = '#';
            ++currentY;
            orientation = 'E';
          } else {
            mazeblock[currentX][currentY] = '#';
            --currentX;
            orientation = 'N';
          }
        }
        //for going North
        else if (orientation == 'N') {
          if ((currentY < (columns - 1))
              && (mazeblock[currentX][currentY + 1] == ' ' || mazeblock[currentX][currentY + 1] == '#')) {
            mazeblock[currentX][currentY] = '#';
            ++currentY;
            orientation = 'E';
          } else if ((currentX > 0)
                     && (mazeblock[currentX - 1][currentY] == ' ' || mazeblock[currentX - 1][currentY] == '#')) {
            mazeblock[currentX][currentY] = '#';
            --currentX;
            orientation = 'N';
          } else if ((currentY > 0)
                     && (mazeblock[currentX][currentY - 1] == ' ' || mazeblock[currentX][currentY - 1] == '#')) {
            mazeblock[currentX][currentY] = '#';
            --currentY;
            orientation = 'W';
          } else {
            mazeblock[currentX][currentY] = '#';
            currentX++;
            orientation = 'S';
          }
        }
        //for going West
        else if (orientation == 'W') {
          if ((currentX > 0) && (mazeblock[currentX - 1][currentY] == ' ' || mazeblock[currentX - 1][currentY] == '#')) {
            mazeblock[currentX][currentY] = '#';
            --currentX;
            orientation = 'N';
          } else if ((currentY > 0)
                     && (mazeblock[currentX][currentY - 1] == ' ' || mazeblock[currentX][currentY - 1] == '#')) {
            mazeblock[currentX][currentY] = '#';
            --currentY;
            orientation = 'W';
          } else if ((currentX < (rows - 1))
                     && (mazeblock[currentX + 1][currentY] == ' ' || mazeblock[currentX + 1][currentY] == '#')) {
            mazeblock[currentX][currentY] = '#';
            ++currentX;
            orientation = 'S';
          } else {
            mazeblock[currentX][currentY] = '#';
            currentY++;
            orientation = 'E';
          }
        }
        //For going east
        else {
          if ((currentX < (rows - 1))
              && (mazeblock[currentX + 1][currentY] == '0' || mazeblock[currentX + 1][currentY] == 'W')) {
            mazeblock[currentX][currentY] = 'W';
            ++currentX;
            orientation = 'S';
          } else if ((currentY < (columns - 1))
                     && (mazeblock[currentX][currentY + 1] == ' ' || mazeblock[currentX][currentY + 1] == '#')) {
            mazeblock[currentX][currentY] = '#';
            ++currentY;
            orientation = 'E';
          } else if ((currentX > 0)
                     && (mazeblock[currentX - 1][currentY] == ' ' || mazeblock[currentX - 1][currentY] == '#')) {
            mazeblock[currentX][currentY] = '#';
            --currentX;
            orientation = 'N';
          } else {
            mazeblock[currentX][currentY] = '#';
            currentY--;
            orientation = 'W';
          }
        }
      }
    
      mazeblock[currentX][currentY] = '# ';
      printf("\n");
    
      // output loop
      for (r = 0; r < rows; r++) {
        for (c = 0; c < columns; c++) {
          printf("%1c", mazeblock[r][c]);
        }
      }
    
      return 0;
    }
    The first problem is you don't even read in the maze properly.

    > fscanf(fPointer, "%c", &mazeblock[r][c]);
    This will fill your maze with \n characters from the input file.

    > mazeblock[currentX][currentY] = '#';
    Why are you filling in where you've been with the wall character?
    If you reach a dead end, how are you going to get back to a place where you had a choice?

    Add some constants to make the code more readable.
    Code:
    #define WALL '#'
    #define FLOOR ' '
    #define CRUMB '~' // mark where you've been
    #define CHOICE '+' // a point in the maze where there was a choice of next move
    So you can say things like
    Code:
    if ( maze[x][y] == FLOOR )
        maze[x][y] = CRUMB;
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  6. #6
    TEIAM - problem solved
    Join Date
    Apr 2012
    Location
    Melbourne Australia
    Posts
    1,907
    On a side note, you seem to have forgotton to free the dynamically allocated memory.

    You have also forgotton to handle if any of the mallocs fail (you prompt the user, but never handle it).

    If you are not compiling this for C++, it is also a good idea not to cast the return from a malloc (for more on this, see FAQ > Casting malloc - Cprogramming.com)
    Code:
    T *banana;
    
    banana = malloc(items * sizeof(*banana) );
    Fact - Beethoven wrote his first symphony in C

  7. #7
    Registered User
    Join Date
    Mar 2019
    Posts
    15
    Thank you for the advice. we had not learned about constants yet so I was not sure if my professor would expect me to use it. I replace it(the wall) with a different sign(marker) or use a constant. And I will try to figure out back tracking when I hit a wall. And about reading in the maze. When I ran it IT looked fine to me so I didn't know that there was a problem with that. Thank you again for the advice.

  8. #8
    Registered User
    Join Date
    Mar 2019
    Posts
    15
    Is my reading in a syntax error? I looked at the fscanf in the loop but can't seem to figure out what I did wrong ? I made some changes to my code but I did not use constant. Added comments for what a wall and a space is. I'm not done making all the changes you said and I'm sorry.

    Code:
    
    
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <stdbool.h>
    
    
    
    
    void print_maze(char** mazeblock, int r, int c, int columns, int rows );
    
    
     // void freeMem(char** mazeblock, int rows, int r,int c);
    int main()
    {
    
    
    
    
         // all variables declared
         int rows  , columns , r , c,i,j, rowStart, columnStart, rowEnd, columnEnd, currentX, currentY;
    
    
         char** mazeblock;
         char orientation;
    
    
         FILE *fPointer;// file pointer
    
    
         //read file into array
    
    
    
    
         fPointer = fopen("maze03.txt", "r");
         if(fPointer==NULL)
         {
            printf("Error in opening file\n");
            exit(1); // help check opening error
         }
    
    
    
    
        fscanf( fPointer, " %d %d %d %d %d %d\n ", &rows, &columns, &rowStart, &columnStart, &rowEnd, &columnEnd );// read the first line
    
    
    
    
    
    
    // Dynamically allocate memory
    
    
        mazeblock = (char**)malloc(sizeof(char*) * rows);
    
    
    // failure to allocate memory
        if(!mazeblock)
        {
         printf("memmory allocation failed");
        }
    
    
    
    
        for ( i= 0; i < rows; i++)
        {
            mazeblock[i] = (char*)malloc(sizeof(char) * columns);
        }
    
    
        // to read in the maze
        for ( r = 0; r < rows; r++)
        {
            for ( c = 0; c < columns; c++)
            {
                fscanf(fPointer,"%c",&mazeblock[r][c]);
    
    
            }
        }
    
    
    
    
        fclose(fPointer);
    
    
    
    
    
    
    
    
    
    
    
    
           // Defining direction
        if (rowStart  == 0)
        {
            orientation = 'S';
        }
        else if (rowStart == (rows - 1)){
            orientation = 'N';
        }
        else if (columnStart == 0){
            orientation = 'E';
        }
        else
        {
            orientation = 'W';
        }
    
    
    
    
    // to hold direction
        currentX = rowStart;
        currentY = columnStart;
    
    
    
    
    //
    
    
    
    
    // for going south rules
    //  mazeblock[currentX][currentY ]  == ' ' (IS A FLOOR)
     // mazeblock[currentX][currentY ]  == '+' (IS A MARKER)
        while ( !(currentX == rowEnd) && (currentY == columnEnd)){
            if ( orientation == 'S'){
                if ( (currentY > 0) && (mazeblock[currentX][currentY - 1]  == ' ' || mazeblock[currentX][currentY - 1]  == '+')){
                    mazeblock[currentX][currentY] = '+';
                    --currentY;
                    orientation = 'W';
                }
                else if ( (currentX < (rows - 1)) && (mazeblock[currentX + 1][currentY] == ' ' || mazeblock[currentX + 1][currentY] == '+')){
                    mazeblock[currentX][currentY] = '+';
                    ++currentX;
                    orientation = 'S';
                }
                else if ( (currentY < (columns - 1)) && (mazeblock[currentX][currentY + 1] == ' ' || mazeblock[currentX][currentY + 1] == '+')){
                    mazeblock[currentX][currentY] = '+';
                    ++currentY;
                    orientation = 'E';
                }
                else {
                    mazeblock[currentX][currentY] = '+';
                    --currentX;
                    orientation = 'N';
                }
            }
    
    
    //for going North
    
    
            else if ( orientation == 'N'){
                if ( (currentY < (columns - 1)) && (mazeblock[currentX][currentY + 1]  == ' ' || mazeblock[currentX][currentY + 1]  == '+')){
                    mazeblock[currentX][currentY] = '+';
                    ++currentY;
                    orientation = 'E';
                }
                else if ( (currentX > 0) && (mazeblock[currentX - 1][currentY] == ' '|| mazeblock[currentX - 1][currentY] == '+')){
                    mazeblock[currentX][currentY] = '+';
                    --currentX;
                    orientation = 'N';
                }
                else if ( (currentY > 0) && (mazeblock[currentX][currentY - 1] == ' ' || mazeblock[currentX][currentY - 1] == '+')){
                    mazeblock[currentX][currentY] = '+';
                    --currentY;
                    orientation = 'W';
                }
                else {
                    mazeblock[currentX][currentY] = '+';
                    currentX++;
                    orientation = 'S';
                }
            }
    
    
    
    
    //for going West
            else if ( orientation == 'W'){
                if ( (currentX > 0) && (mazeblock[currentX - 1][currentY]  == ' ' || mazeblock[currentX - 1][currentY]  == '+')){
                    mazeblock[currentX][currentY] = '+';
                    --currentX;
                    orientation = 'N';
                }
                else if ( (currentY > 0) && (mazeblock[currentX][currentY - 1] == ' ' || mazeblock[currentX][currentY - 1] =='+')){
                    mazeblock[currentX][currentY] = '+';
                    --currentY;
                    orientation = 'W';
                }
                else if ( (currentX < (rows - 1)) && (mazeblock[currentX + 1][currentY] == ' ' || mazeblock[currentX + 1][currentY] =='+')){
                    mazeblock[currentX][currentY] = '+';
                    ++currentX;
                    orientation = 'S';
                }
                else {
                    mazeblock[currentX][currentY] = '#';
                    currentY++;
                    orientation = 'E';
                }
            }
    
    
    
    
    //For going east
            else {
                if ( (currentX < (rows - 1)) && (mazeblock[currentX + 1][currentY]  == ' ' || mazeblock[currentX + 1][currentY]  =='+')){
                    mazeblock[currentX][currentY] = '+';
                    ++currentX;
                    orientation = 'S';
                }
                else if ( (currentY < (columns - 1)) && (mazeblock[currentX][currentY + 1] == ' ' || mazeblock[currentX][currentY + 1] =='+')){
                    mazeblock[currentX][currentY] = '+';
                    ++currentY;
                    orientation = 'E';
                }
                else if ( (currentX > 0) && (mazeblock[currentX - 1][currentY] == ' ' || mazeblock[currentX - 1][currentY] =='+')){
                    mazeblock[currentX][currentY] = '+';
                    --currentX;
                    orientation = 'N';
                }
                else {
                    mazeblock[currentX][currentY] = '+';
                    currentY--;
                    orientation = 'W';
                }
            }
        }
                mazeblock[currentX][currentY] = '+';
    
    
                printf("\n");
    
    
                printf(" The Coordiantes are row = %d , column = %d , Starting Row = %d, Starting Column = %d ,Ending Row = %d,  Ending Column = %d\n\n", rows, columns, rowStart, columnStart, rowEnd, columnEnd );
    
    
    
    
    
    
                print_maze(mazeblock, r, c,  columns, rows );
    
    
      //  freeMem(mazeblock, rows, r, c);
    
    
       // printf("test");
                printf("\n");
    
    
                if((currentX == rowEnd) && (currentY == columnEnd))
                {
                    printf("The maze has been solved");
                }
    
    
    
    
                return 0;
    
    
    
    
        }
    
    
        void print_maze(char** mazeblock, int r, int c, int columns, int rows )
    {
         for (r = 0; r < rows; r++)
            {
            for ( c = 0; c < columns; c++)
            {
    
    
                printf("%c", mazeblock[r][c]);
    
    
            }
    
    
            }
    }
    
    
      //  void freeMem(char** mazeblock, int rows, int r,int c)
    //{
    
    
        //for (r = 0; r < rows; r++){
    //        free ( mazeblock[r][c]);
        //}
    
    
        //free( mazeblock[r][c]);
    //}

  9. #9
    TEIAM - problem solved
    Join Date
    Apr 2012
    Location
    Melbourne Australia
    Posts
    1,907
    Looks fine to me

    Code:
    &banana[i][j]
    ...Is the address of that element at i/j which is what you want.

    That being said: Because you are reading one char at a time, why not just use fgetc?
    FAQ > Work with files (C) - Cprogramming.com
    Fact - Beethoven wrote his first symphony in C

  10. #10
    Registered User
    Join Date
    Mar 2019
    Posts
    15
    my professor actually gave me this code for printing

  11. #11
    TEIAM - problem solved
    Join Date
    Apr 2012
    Location
    Melbourne Australia
    Posts
    1,907
    Quote Originally Posted by Bossuche9 View Post
    my professor actually gave me this code for printing
    If you have any questions about code that your professor has done, go and ask them - In general, all teachers love it when a student is thinking about their material.

    There are a lot of people who waste teachers/professors time which can be quite draining on them - But if you ask some of them who have been there for a while you'll get the same answer, "I find a student that is really into the material and invest my energy there"

    I'd say that because you are seeking out forums for extra help, you are the type of student that make teaching rewarding
    Fact - Beethoven wrote his first symphony in C

  12. #12
    Registered User
    Join Date
    Mar 2019
    Posts
    15
    I have a class during my professor's office hours. He said virtual office hours which I tried but did not like.

  13. #13
    Registered User
    Join Date
    Mar 2019
    Posts
    15
    I actually got it to solve the maze . I'm just stuck on actually changing the color of the walls and making the marker just a line

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 11
    Last Post: 01-08-2011, 01:10 PM
  2. Tree traversal
    By recluse in forum C Programming
    Replies: 4
    Last Post: 12-05-2004, 04:00 PM
  3. Preorder Traversal
    By AmazingRando in forum C Programming
    Replies: 17
    Last Post: 10-29-2003, 03:22 AM
  4. graph traversal
    By Unregistered in forum C Programming
    Replies: 2
    Last Post: 04-10-2002, 11:47 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

Tags for this Thread