Maze generator in C

Question

Iterative dfs Maze generation program in C.

Details about the algorithm:

Example run of the program:

In my implementation:

• Each cell has:
  4 neighbors [left, right, top, bottom]
  2 walls [right, top]
  and a visited field obviously

Here is the code:

cell.h

#ifndef CELL
#define CELL

#define LEFT 0
#define RIGHT 1
#define TOP 2 
#define BOT 3

typedef struct cellstruct *cellptr;

typedef struct cellstruct {
    cellptr neighbors[4];
    int walls[2];              // [0] = top wall, [1] = right wall

    int visited;
} cell;

#endif

main.c

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "stack.c"
#include "cell.h"


#define NEWLINE 10
#define SPACE 32
#define true 1
#define false 0

#define TOP_ROW 0
#define BOT_ROW (rowMAX - 1)
#define FAR_LEFT 0
#define FAR_RIGHT (colMAX - 1)

#define BOT_WALL 0
#define RIGHT_WALL 1

static int rowMAX;
static int colMAX;

void initcells(cellptr maze);
void printmaze(cellptr maze);
void generatemaze(cellptr maze);
int getrand();

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

    if (argc == 1) {    
        colMAX = rowMAX = 7; // default 
    } else colMAX = rowMAX = (atoi(argv[1]));


    cell maze[rowMAX][colMAX];

    initcells(*maze);
    generatemaze(*maze);
    printmaze(*maze);

    putchar(NEWLINE);

    
    return 0;
}


void generatemaze(cellptr maze) {
    cellptr start = maze;   
    push(start);

    int allVisited(cellptr cell);
    int getrand(int min, int max);

    // while stack is not empty
    while (sp > 0) {
        cellptr current = pop();

        // check that there are unvisited neighbors
        if (!allVisited(current)) {
            push(current);

            cellptr neighbor;
            int dir = 0;

            // get random neighbor that isnt NULL and isnt visited already
            while ((neighbor = current->neighbors[dir = getrand(0, 3)]) == NULL || neighbor->visited == true)
                    ;
            

            // each cell only has a right wall and a bottom wall
            // so to modify for example the left wall of the current cell
            // you would modify the right wall of the cell left to the current cell


            if (dir == LEFT) {
                neighbor->walls[RIGHT_WALL] = false;            // false = remove wall
            }
            if (dir == RIGHT) {
                current->walls[RIGHT_WALL] = false;
            }
            if (dir == BOT) {
                current->walls[BOT_WALL] = false;
            }
            if (dir == TOP) {
                neighbor->walls[BOT_WALL] = false;
            }
        
            neighbor->visited = true;
            push(neighbor);         
        }       
    }
}

void printmaze(cellptr maze) {
    cellptr cptr = maze;

    // print the top part for whole maze:
    for (int i = 0; i < (colMAX * 2); ++i) putchar('_');
    putchar(NEWLINE);

    for (int i = 0; i < (colMAX * rowMAX); ++i) {

        // print left wall for whole maze
        if (cptr->neighbors[LEFT] == NULL) putchar('|');

        // bottom wall
        if (cptr->walls[BOT_WALL] != false) {
            putchar('_');
        } else putchar(SPACE);

        // right wall
        if (cptr->walls[RIGHT_WALL] != false) {
            putchar('|');
        } else putchar(SPACE);
        

        // new row
        if (cptr->neighbors[RIGHT] == NULL) {
            putchar(NEWLINE);
        }
        cptr++; 
    }
}


void initcells(cellptr maze) {
    cellptr rowptr, colptr;
    int row, col;

    for (row = 0; row < rowMAX; ++row) {
        rowptr = &maze[rowMAX * row];
        colptr = rowptr;

        for (col = 0; col < rowMAX; ++col) {  
            if (row == TOP_ROW) {

                // top row has no cells above them
                colptr->neighbors[TOP] = NULL;                          
            } else colptr->neighbors[TOP] = &(rowptr - rowMAX)[col];

            if (row == BOT_ROW) {

                // bottom row has no cells below them
                colptr->neighbors[BOT] = NULL;
            } else colptr->neighbors[BOT] = &(rowptr + rowMAX)[col];

            if (col == FAR_LEFT) {

                // left column has no cells left to them
                colptr->neighbors[LEFT] = NULL;
            } else colptr->neighbors[LEFT] = (colptr - 1);

            if (col == FAR_RIGHT) {

                // right column has no cells right to the,
                colptr->neighbors[RIGHT] = NULL;
            } else colptr->neighbors[RIGHT] = (colptr + 1);
            
            // set all walls to true at the start
            colptr->walls[BOT_WALL] = true;                 
            colptr->walls[RIGHT_WALL] = true;

            colptr++->visited = false;   
        }  
    } 
}


int isNull(cellptr cell) {
    return cell == NULL;  
}

int allVisited(cellptr cell) {
    int l, r, t, b;
    l = r = t = b = 1;
    if (!isNull(cell->neighbors[LEFT])) {
        l = cell->neighbors[LEFT]->visited;
    }
    if (!isNull(cell->neighbors[RIGHT])) {
        r = cell->neighbors[RIGHT]->visited;
    }
    if (!isNull(cell->neighbors[TOP])) {
        t = cell->neighbors[TOP]->visited;
    }
    if (!isNull(cell->neighbors[BOT])) {
        b = cell->neighbors[BOT]->visited;
    }
    //printf("%d %d %d %d\n", l, r, t, b);
    return (l && r && t && b);
}

int getrand(int min, int max) {
    return (rand() % (max - min + 1) + min);
}

stack.c

#include "cell.h"

static cellptr cellstack[10000];
static int sp;

void push(cellptr cell) {
    cellstack[sp++] = cell;   
}

cellptr pop() {
    return (sp > 0) ? cellstack[--sp] : NULL;
}

Answer 1

There is quite a bit that can be improved here. I see you are trying to do things in a correct way, but you miss the mark here and there. I'll explain below.

Avoid macros

Giving name to constants is a good thing to do. However, macros created with #define have some issues: if they become a bit more complex than a single number, you have to put thing in parentheses (as you did), but they also lack a type. Sometimes they look like constants but they aren't (like BOT_ROW: it depend on the current value of rowMAX). There are a few cases where you really need macros in C, but in many cases they can be avoided.

In some cases, an enum is preferred, like for LEFT, RIGHT and so on. This combines well with switch statements, where the compiler can warn if you forgot to cover one of the enum values. So:

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

There are also a few cases where you defined things that should not be named at all:

• true and false: these are actually standard types since C99; #include <stdbool.h> instead.
• NEWLINE and SPACE: you used the ASCII codes here, but that is actually less portable than just writing the character literals '\n' and ' ' wherever you need to have a space or newline. It's also not consistent, since you did write '_' and '|' directly instead of defining constants for those.
• TOP_ROW, BOT_ROW etc.: it is a common enough pattern that 0 is the top/left-most index, and rowMAX - 1 and colMAX - 1 spelled out literally are the bottom and right-most indices of a 2D array. The meaning should be clear from those expressions, since arrays are 0-indexed in C.

The only constants I would maybe keep can be converted to static const variables:

static const int BOTTOM_WALL = 0;
static const int RIGHT_WALL = 1;

Although even that is not necessary, as I'll explain below.

A cell is too big

A cell should only need to track three bits of information: whether it has a top and/or a right wall, and whether it has been visited. It should not have to track which neighbors it has, instead you can tell that from its position in the array maze[][].

For one bit of information, you can use the type bool, but even that actually takes a whole byte of memory. But C also allows you to define bitfields, allowing you to pack three bits in one byte:

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

Your cell actually uses 48 bytes on a 64-bit computer. You might not think it is important, but it does reduce memory usage and improves performance a lot for large mazes.

Create a struct to represent a maze

You have several functions that get a cellptr as an argument, but to get the size of the maze they actually use the global variables rowMAX and colMAX. That's not great. It's better to create a struct that contains all the information regarding a maze, for example:

typedef struct {
    size_t width;
    size_t height;
    cell *cells;
} maze;

Here cells points to a 1-dimensional array as far as C is concerned, it's support for multi-dimensional arrays is unfortunately a bit limited. To make working with the cells in the maze more easy, write some helper functions:

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;
}

void set_visited(maze *maze, size_t x, size_t y) {
    (*cell_at(maze, x, y)).visited = true;
}

Don't hide pointers behind typedefs

It has been found that hiding pointers behind typedefs does more harm than good. So I would avoid creating a cellptr, instead jut write cell *. It should be clear to any programmer that the latter is a pointer, and it's even less typing.

Allocate arrays using malloc()

In your code, maze[][] is an array which is allocated on the stack of main(). However, the stack has a limited size, depending on the operating system and other constraints. Running out of stack space will cause your program to crash. So it is fine for small arrays, but since you don't know in advance how large a maze a user might want to generate, it's best to allocate it dynamically instead using malloc(). This will allocate it from the heap, which should allow it to be much bigger. Of course if you ask for something that really doesn't fit into your computer's memory, then malloc() will fail and return NULL, which you should gracefully handle.

Another issue is with the statically allocated cellstack[]. For small mazes, it is too large, wasting memory. For very large mazes, it might be too small, causing a buffer overflow which at best causes your program to crash, but at worst causes silent data corruption. Again, allocate it dynamically. Also note that you can grow memory allocated using malloc() by using realloc().