Maze SOLVER in C

Question

a maze solver in C.

I have not included the maze generation code because i'm not looking for a review on that in this post, but the maze solver operates on a 1D array of cells, for more info: Maze generation algorithm review

Sample run:

Bottom left is the starting point (0, 6) Top right is the ending point (6, 0)

solve.c

#include "../struct.h"
#include "../maze.c"
#include "../cell.c"
#include <stdio.h>
#include <stdlib.h>


bool topwall(Maze *maze, point *p);
bool botwall(Maze *maze, point *p);
bool leftwall(Maze *maze, point *p);
bool rightwall(Maze *maze, point *p);

bool equal(point p, point p2);

void solve(Maze *maze, point p, point e) {
    static bool found = false;
    if (found) return;

    if (equal(p, e)) {
        found = true;  
    }

    (*cell_at(maze, p.x, p.y)).visited = true;
    point temp;
    if (p.x < (colMAX - 1) && !rightwall(maze, &p) && !is_visited(maze, p.x + 1, p.y)) {
        temp = p;
        temp.x++;
        solve(maze, temp, e);
    } 
    if (p.x > 0 && !leftwall(maze, &p) && !is_visited(maze, p.x - 1, p.y)) {
        temp = p;
        temp.x--;
        solve(maze, temp, e);
    }
    if (p.y > 0 && !topwall(maze, &p) && !is_visited(maze, p.x, p.y - 1)) {
        temp = p;
        temp.y--;
        solve(maze, temp, e);
    }
    if (p.y < (rowMAX - 1) && !botwall(maze, &p) && !is_visited(maze, p.x, p.y + 1)) {
        temp = p;
        temp.y++;
        solve(maze, temp, e);
    }

    if (found) {
        (*cell_at(maze, p.x, p.y)).path = true;
    }
    return;
}

bool equal(point p, point p2) {
    return (p.x == p2.x && p.y == p2.y);
}

bool rightwall(Maze *maze, point *p) {
    return (*cell_at(maze, p->x, p->y)).right_wall;
}

bool leftwall(Maze *maze, point *p) {
    return (*cell_at(maze, p->x - 1, p->y)).right_wall;
}

bool botwall(Maze *maze, point *p) {
    return (*cell_at(maze, p->x, p->y)).bottom_wall;
}

bool topwall(Maze *maze, point *p) {
    return (*cell_at(maze, p->x, p->y - 1)).bottom_wall;
}

cell.c

#ifndef C
#define C
#include "struct.h"
#include <stdbool.h>

cell *cell_at(Maze *maze, size_t x, size_t y) {
    return &maze->cells[x + y * maze->width];
}

bool is_visited(Maze *maze, size_t x, size_t y) {
    return (*cell_at(maze, x, y)).visited;
}

#endif

main.c

#include <stdio.h>
#include "generate/generate.c"
#include "solve/solve.c"
#include "maze.c"

int main(int argc, char *argv[]) {
    srand(time(0));

    if (argc == 1) {    
        colMAX = rowMAX = 7; // default 
    } else colMAX = rowMAX = (atoi(argv[2]));
    stack = malloc((rowMAX * colMAX) * sizeof(point));
    Maze maze = {colMAX, rowMAX, malloc(rowMAX * colMAX)};

    initcells(&maze);
    point p = {0, 0};
    push(p);
    while (sp > 0) {
        generatemaze(&maze);
    }
    printmaze(&maze);
    putchar('\n');
    
    cell* cellptr = maze.cells;
    for (int i = 0; i < (rowMAX * colMAX); ++i) {
        cellptr->path = false;                          // reset
        cellptr++->visited = false;    
    }

    point s = {0, 1};               // custom starting / end point not yet implemented
    point e = {6, 0};
    solve(&maze, s, e);

    printmaze(&maze);
    return 0;
}

struct.h

#ifndef H
#define H
#include <stddef.h>

typedef struct cellstruct {
    bool bottom_wall: 1;
    bool right_wall: 1;
    bool visited: 1;
    bool path: 1;
} cell;

typedef struct mazestruct {
    size_t width;
    size_t height;
    cell *cells;
} Maze;

typedef struct {
    size_t x;
    size_t y;
} point;

typedef enum {
    LEFT,
    RIGHT,
    TOP,
    BOTTOM
} direction;
    
#endif

Answer 1

1. Use the same tag-name and typedef-name. Thus there is less to remember, and without inventing your own / choosing one of many patterns to derive one from the other.

2. Pass small types (like direction, point, and cell) by value unless it is an optional argument (in which case pointer to constant is needed) or an output-argument (which is the only reason to require a pointer to non-constant).

3. Dereferencing in parenthesis and then using member-access-operator is strictly less readable than simply using the designated operator (->).

4. If a function is only used in one TU, make it static. Doing so simplifies the optimizer's work, and ensures it isn't gratuitously exported, avoiding name-clashes and bloat.

5. Properly ordering your functions allows you to avoid most forward-declarations.

6. Only header-files, which might contain a few inline functions (preferably static) but should be mostly declarations, should be included. For such a small project, a single header might suffice, but it should be properly named.
   Yes, there are projects which can be built as a single TU, but with the proliferation of LTO the advantages have greatly diminished if not disappeared, and with the increased number of cores the disadvantages have likewise compounded.

7. What can go wrong, will go wrong, at the most inopportune time, in the most disastrous way possible.
   Check for error-returns, especially from malloc(). Or at least write and use your own wrapper which will print an error and abort() if it fails.

Answer 2

File Organization

While there is no rule about including C files, a general best practice for modularity in C programming is to create a pair of files, one header file and one c source file. The header file contains structs, constants and function prototypes that are used throughout the code. A possible example in this case is cell.h and cell.c. This organization allows faster builds of libraries and executable code because interfaces such as structs and function prototypes change less than the C source code functions. In the current file structure a change to any of the C source files forces the entire program to recompile, if the code was altered to header files and source files, a change to cell.c would only force cell.c to recompile.

Each struct in struct.h should be separated into a header file:

• point.h
• cell.h
• maze.h

As I mentioned about the header files should also contain the function prototypes to manipulate the struct.

Suggested files:

cell.h

#ifndef CELL_H
#define CELL_H

typedef struct cellstruct {
    bool bottom_wall : 1;
    bool right_wall : 1;
    bool visited : 1;
    bool path : 1;
} cell;

#endif  // CELL_H

It isn't clear why you are limiting the size of the bools in the cell struct to one bit.

maze.h

#ifndef MAZE_H
#define MAZE_H

#include "cell.h"
typedef struct mazestruct {
    size_t width;
    size_t height;
    cell* cells;
} Maze;

typedef enum {
    LEFT,
    RIGHT,
    TOP,
    BOTTOM
} direction;

extern cell* cell_at(Maze* maze, size_t x, size_t y);

extern bool is_visited(Maze* maze, size_t x, size_t y);


#endif  // MAZE_H

Test for Possible Memory Allocation Errors

In modern high-level languages such as C++, memory allocation errors throw an exception that the programmer can catch. This is not the case in the C programming language. While it is rare in modern computers because there is so much memory, memory allocation can fail, especially if the code is working in a limited memory application such as embedded control systems. In the C programming language when memory allocation fails, the functions malloc(), calloc() and realloc() return NULL. Referencing any memory address through a NULL pointer results in undefined behavior (UB).

Possible unknown behavior in this case can be a memory page error (in Unix this would be call segmentation fault), corrupted data in the program and in very old computers it could even cause the computer to reboot (corruption of the stack pointer).

To prevent this undefined behavior a best practice is to always follow the memory allocation statement with a test that the pointer that was returned is not NULL.

Current Code:

    stack = malloc((rowMAX * colMAX) * sizeof(point));
    Maze maze = { colMAX, rowMAX, malloc(rowMAX * colMAX) };

Suggested Code:

    stack = malloc((rowMAX * colMAX) * sizeof(*stack));
    if (!stack)
    {
        fprintf(stderr, "Creation of stack: malloc failed\n");
        return EXIT_FAILURE;
    }
    Maze maze = { colMAX, rowMAX, NULL };
    maze.cells = malloc(colMAX * rowMAX * sizeof(*maze.cells));
    if (!maze.cells)
    {
        fprintf(stderr, "Creation of maze of cells: malloc failed\n");
        return EXIT_FAILURE;
    }

Convention When Using Memory Allocation in C

When using malloc(), calloc() or realloc() in C a common convention is to sizeof(*PTR) rather sizeof(PTR_TYPE); this makes the code easier to maintain and less error prone, since less editing is required if the type of the pointer changes. (Shown in the above example).