Reading in an array for maze file in C with an uneven size of cube and extra characters

Question

I'm trying to figure out how to properly read in and store a maze from a .txt document in C. The max size of this maze will be 40x40 "cubes". After reading it in, I will be needing to solve it, by placing the path from the left hand corner to bottom right with a *. I'm used to using 2D Arrays, but this problem keeps tripping me up as I don't understand how to keep track of the rows and cols if they are not exactly even, or how I would even accurately print a * in the middle of each "cube" after I have solved it. I've read other examples of mazes that are composed of 1s and 0s, or all even # for the walls, which makes it easy to read in and keep track of, but not input like this. There will be other mazes on the same text file that I will need to read in after solving the first maze that will be separated by a double space. Below is an example of one of the mazes :

+---+---+---+---+---+  
|       |           |  
+---+   +   +   +   +  
|   |   |   |   |   |  
+   +   +   +   +---+  
|   |   |   |       |  
+   +   +   +---+   +  
|       |   |       |  
+   +---+---+   +   +  
|               |   |  
+---+---+---+---+---+

Here is some of my code I am making so far to error check and read in characters. In it, I am attempting to initialize an array of 120x120, read in the current char, and convert these characters to either a -1 or 0 to correspond to a wall or empty space. :

/* Read in a grid as parameter of max 120x120 to account for '+' and'-' */
int readLine(int grid2D[120][120])
{
    int row = 0;
    int col = 0;

    int isNewLine = TRUE;

    /* Loop through while getchar does not equal EOF */
    while ((c = getchar()) != EOF)
    {

        /* Check for foreign characters, return FALSE if found */
        if ((c != '+') || (c != '-') || (c != '|') || (c != ' '))
        {
            /* If c = 
 , avoid tripping error, and do nothing */
            if(c == '
'){}
            else
              errorFree = FALSE;
        }

        /* If character is a '+' '-' or '|', it is a wall, set to -1 to 
        use int's for wall tracking */
        else if (row%2 == 0)
        {
           if(c == '|')
           {
              grid2D[row][col] = -1;
              col++;
           }
        }
        else if((c == '+') || (c == '-'))
        {
           grid2D[row][col] = -1;
           col++;
        }
        else
        {
            if(c == '
')
            {
               col = 0;
               row++;
            }
        }

    isNewLine = TRUE;

    return isNewLine;
}

Any guidance would be greatly appreciated, I am not sure if the approach I am doing is correct. I believe I am currently error checking correctly, however I am struggling to understand how I should be keep track of the each "cube" since the chars for each "cube" are not even, they are more so dimensioned as 5x1 cubes (a +---+ for one side and a | for the other)

David C. Rankin · Accepted Answer

In response to your question and question in the comment, determining the row and column size is pretty straight forward. When you read a line of the array from the file with fgets, you can use strlen() to determine the number of characters (but note, it also contains the ' ' character - so you will need to subtract one - which you can do in combination with trimming the ' ' from the end)

Once you have read the first line and accounted for the ' ', set a variable that holds the number of characters (columns) in your array. Since you know your array is a cube, you can then compare the first-line length with the length of every other line read to validate all rows have the same number of columns.

As you are looping and handling the input of each line, you simply keep a row counter which when you are done with your read will hold the number of rows in your array.

There are two ways you can handle storage for your array. You can either declare an array large enough to hold your largest anticipated maze (while keeping it small enough to fit on the stack 256x512 is safe on both Linux and Windoze) or you can dynamically allocate storage for your columns and rows, using realloc() to allocate additional storage as required. (There you can handle maze sizes up to the memory limit of your computer - but it does add complexity)

Your "confusion" over my array needing to be, e.g. 11x21 is understandable. It all stems from the fact that characters on a terminal are roughly two-times taller than they are wide. So to print a "cube" of characters, you need roughly twice as many columns as you do rows. That isn't a problem at all. If you code your read of columns and rows properly and have variables tracking the number of columns and rows -- then the difference becomes nothing more than numbers that your code keeps track of in a couple of variables.

The following is a short example to address your stumbling blocks on the read of an unknown number or rows and columns up to a fixed maximum. (rather than dynamically allocating and reallocating -- which we can leave for later). To do so, we #define a constant for the maximum number of columns, and then knowing we need 1/2 that number of rows, #define a constant for that number of rows, e.g.

#include 
#include 

#define MAXC 512    /* declare consts for max NxN you can handle */
#define MAXR (MAXC + 1) / 2

Then it is a simple matter of declaring your variables to track the current row and col and the total number of rows and columns (nrow, ncol) along with declaring an array a[MAXR][MAXC] = {""}; to hold the maze. You can then either open your file if a filename is given as the 1st argument (or read from stdin by default if no argument is given). In either case, you can validate you have a stream open for reading, e.g.

    size_t row = 0, col = 0, nrow = 0, ncol = 0;
    char a[MAXR][MAXC+1] = {""}; /* delcare and initialize array */
    /* use filename provided as 1st argument (stdin by default) */
    FILE *fp = argc > 1 ? fopen (argv[1], "r") : stdin;

    if (!fp) {  /* validate file open for reading */
        perror ("file open failed");
        return 1;
    }

With your file stream open for reading, now it is just a matter of reading all rows of data in the file. Since you expect all lines to have an even number of characters so that your maze is actually a cube, you can save the number of characters in the first line (after trimming the ' ') and use that to compare against the number of characters in every other line to validate you have a cube. As you read lines, you also need to protect your array bounds so you don't attempt to store more lines in your array than you have rows to hold, so a simple check of row < MAXR combined with your fgets (a[row], MAXC, fp) will impose that limit, e.g.

    while (row < MAXR && fgets (a[row], MAXC, fp)) {
        size_t len = strlen (a[row]);       /* get length of row */
        if (len && a[row][len-1] == '
')   /* validate it fits in array */
            a[row][--len] = 0;  /* remove trailing '
' char from end */
        else if (len == MAXC) {
            fprintf (stderr, "error: row exceeds %d chars.
", MAXC);
            return 1;
        }
        if (!row)       /* if 1st row - set expected ncol for each row */
            ncol = len;
        if (ncol != len) {  /* validate all other rows against 1st */
            fprintf (stderr, "error: unequal columns (%lu) on row (%lu)
",
                    len, row);
            return 1;
        }
        /* your code goes here - example just outputs array */
        for (col = 0; col < ncol; col++)
            putchar (a[row][col]);
        putchar ('
');

        row++;  /* advance row counter when done processing row */
    }
    if (fp != stdin) fclose (fp);   /* close file if not stdin */
    nrow = row;                     /* save the total number of rows */

You now have all the rows and columns of stored and you have your nrow and ncol values set giving you your nrow x ncol array. The path logic I will leave to you, but I did want to provide an example of how to replace the ' ' with '*' in your path. The following does just that for every possible path character imposing the constrain that each '*' have an adjacent space (you can adjust as needed). Here we just loop 0 -> nrow-1 and nest a loop from 0 -> ncol-1 to loop over each character in the array.

The only wrinkle you have to pay attention to when checking adjacent cells in a row is that you must insure you are not on the left-edge of the maze when you check the column to the left and not on the right-edge of the maze when checking the column to the right (accessing elements beyond the bounds of your array will invoke Undefined Behavior)

You handle the edges checks as simply additions to the conditionals insider your if (...) statement, e.g.

    /* you can make multiple passes over the array to determine your path.
     * below is just an example of replacing the spaces in the path with
     * asterisks.
     */
    puts ("
replacing path spaces with asterisks
");
    for (row = 0; row < nrow; row++) {
        for (col = 0; col < ncol; col++) {
            /* if adjacents and current ' ', replace with '*' */
            if (col && col < ncol - 1 &&    /* col > 0 && col < ncol-1 */
                    /* next checks adjacent and current all ' ' */
                    a[row][col-1] == ' ' && a[row][col] == ' ' && 
                    a[row][col+1] == ' ')
                a[row][col] = '*';  /* if conditions met, set element '*' */
            putchar (a[row][col]);
        }
        putchar ('
');
    }

Putting all the pieces together in a short example to read any maze up to 512 characters wide, you could do something like the following:

#include 
#include 

#define MAXC 512    /* declare consts for max NxN you can handle */
#define MAXR (MAXC + 1) / 2

int main (int argc, char **argv) {

    size_t row = 0, col = 0, nrow = 0, ncol = 0;
    char a[MAXR][MAXC+1] = {""}; /* delcare and initialize array */
    /* use filename provided as 1st argument (stdin by default) */
    FILE *fp = argc > 1 ? fopen (argv[1], "r") : stdin;

    if (!fp) {  /* validate file open for reading */
        perror ("file open failed");
        return 1;
    }

    while (row < MAXR && fgets (a[row], MAXC, fp)) {
        size_t len = strlen (a[row]);       /* get length of row */
        if (len && a[row][len-1] == '
')   /* validate it fits in array */
            a[row][--len] = 0;  /* remove trailing '
' char from end */
        else if (len == MAXC) {
            fprintf (stderr, "error: row exceeds %d chars.
", MAXC);
            return 1;
        }
        if (!row)       /* if 1st row - set expected ncol for each row */
            ncol = len;
        if (ncol != len) {  /* validate all other rows against 1st */
            fprintf (stderr, "error: unequal columns (%lu) on row (%lu)
",
                    len, row);
            return 1;
        }
        /* your code goes here - example just outputs array */
        for (col = 0; col < ncol; col++)
            putchar (a[row][col]);
        putchar ('
');

        row++;  /* advance row counter when done processing row */
    }
    if (fp != stdin) fclose (fp);   /* close file if not stdin */
    nrow = row;                     /* save the total number of rows */

    /* you can make multiple passes over the array to determine your path.
     * below is just an example of replacing the spaces in the path with
     * asterisks.
     */
    puts ("
replacing path spaces with asterisks
");
    for (row = 0; row < nrow; row++) {
        for (col = 0; col < ncol; col++) {
            /* if adjacents and current ' ', replace with '*' */
            if (col && col < ncol - 1 &&    /* col > 0 && col < ncol-1 */
                    /* next checks adjacent and current all ' ' */
                    a[row][col-1] == ' ' && a[row][col] == ' ' && 
                    a[row][col+1] == ' ')
                a[row][col] = '*';  /* if conditions met, set element '*' */
            putchar (a[row][col]);
        }
        putchar ('
');
    }

    return 0;
}

Example Use/Output

As indicated, the code simply reads and outputs the original maze and then makes a second pass over the maze outputting it with the path filled with '*'

$ ./bin/array2dread



Look things over and let me know if you have further questions.

Reading in an array for maze file in C with an uneven size of cube and extra characters

Answers (1)

Related Questions