maze.c

/**
An implementation of the recursive backtracker maze
generation algorithm in C. Implemented recursively.

Author: nokko
Date: March 2nd
Look on my works, ye mighty, and cringe at my horrible code.

Credit to Jamis Buck for teaching me this wonderful algorithm.
(https://weblog.jamisbuck.org/2010/12/27/maze-generation-recursive-backtracking)
**/

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <locale.h>
#include <wchar.h>

// Openings in each maze cell are represented as a bitfield:
// 0b1000 = 8, north
#define N 8
// 0b0100 = 4, east
#define E 4
// 0b0010 = 2, south
#define S 2
// 0b0001 = 1, west
#define W 1

// 0b1111 = 15, every way is open
#define ALL 15
// 0b0000 = 0,  every way is walled-off
#define NONE 0

// Characters to use when drawing
#define FILLCHAR ((wint_t)9619)
#define NONECHAR ((wint_t)9617)

// A maze is represented as pointer to the beginning of a `data` array,
// and that array's width and height.
struct maze {
    int *data;
    int width;
    int height;
};

// Maybe should be called “FillUnless…”
// Sets the char at `location` to NONECHAR if `condition` is met.
void fillIf(wint_t *location, bool condition) {
    if (condition) {
        *location = NONECHAR;
    } else {
        *location = FILLCHAR;
    }
};

void display_row(const int *data, const struct maze *m) {
    const int width = m->width;
    // Init strings
    wint_t *top    = (wint_t *) calloc(width * 3 + 1, sizeof(wint_t));
    wint_t *middle = (wint_t *) calloc(width * 3 + 1, sizeof(wint_t));
    wint_t *bottom = (wint_t *) calloc(width * 3 + 1, sizeof(wint_t));

    if (top == NULL || middle == NULL || bottom == NULL) {
        printf("failed to allocate memory! exiting.\n");
        exit(1);
    }

    // Fill strings with data: Top pass
    for (int i = 0; i < width; i++) {
        int base = i * 3; // char array is 3x the size of the data

        // Corners don't change.
        top[base] = FILLCHAR;
        top[base + 2] = FILLCHAR;
        // Check only the North bit
        fillIf(&top[base + 1], data[i] & N);

        // Middle pass: check two bits
        // Centre doesn't change
        middle[base + 1] = NONECHAR;
        fillIf(&middle[base], data[i] & W);
        fillIf(&middle[base + 2], data[i] & E);

        // Bottom pass
        bottom[base] = FILLCHAR;
        bottom[base + 2] = FILLCHAR;
        fillIf(&bottom[base + 1], data[i] & S);
    }

    // Use the strings!
    printf("%ls\n", top);
    printf("%ls\n", middle);
    printf("%ls\n", bottom);

    // Always free dynamically allocated memory.
    free(top);
    free(middle);
    free(bottom);
}

void display_maze(struct maze m) {
    int size = m.width * m.height;
    for (int row = 0; row < m.height; row++) {
        display_row(&m.data[row * m.width], &m);
    }
}


// Fill a maze with walls, i.e. NONE values
void fill_maze(struct maze *m) {
    for (int row = 0; row < m->height; row++) {
        for (int col = 0; col < m->width; col++) {
            m->data[row * m->width + col] = NONE;
        }
    }
}

struct neighbour {
    char ox;
    char oy;
    int direction;
    int *data;
};

// get a random neighbour!
struct neighbour get_neighbour(int ox, int oy, struct maze *m) {
    // check out-of-bounds
    bool can_N, can_E, can_S, can_W;
    can_N = (oy - 1) >= 0;
    can_E = (ox + 1) < m->width;
    can_S = (oy + 1) < m->height;
    can_W = (ox - 1) >= 0;

    struct neighbour neighbours[4];
    int count = 0;
    // North: (0, -1)
    if (can_N) {
        int *data = &m->data[(m->width * (oy - 1)) + (ox)];
        if (*data == NONE) {
            neighbours[count] = (struct neighbour) {0, -1, N, data};
            count++;
        }
    }
    // East: (+1, 0)
    if (can_E) {
        int *data = &m->data[(m->width * (oy)) + (ox + 1)];
        if (*data == NONE) {
            neighbours[count] = (struct neighbour) {1, 0, E, data};
            count++;
        }
    }
    // South: (0, +1)
    if (can_S) {
        int *data = &m->data[(m->width * (oy + 1)) + (ox)];
        if (*data == NONE) {
            neighbours[count] = (struct neighbour) {0, 1, S, data};
            count++;
        }
    }
    // West: (-1, 0)
    if (can_W) {
        int *data = &m->data[(m->width * (oy)) + (ox - 1)];
        if (*data == NONE) {
            neighbours[count] = (struct neighbour) {-1, 0, W, data};
            count++;
        }
    }
    struct neighbour out = {.ox=0, .oy=0};
    // No valid neighbours.
    if (count == 0) {
        // Can't keep going, return!
        //printf("can't get neighbour!\n");
        return out;
    }
    // Very wasteful, we throw away a lot of computation here.
    // Honestly, I've stopped caring.
    // PRO TIP: MAKE SURE YOU DON'T INDEX BY NEGATIVE VALUES.
    // THIS BUG TOOK AWAY VALUABLE HOURS OF MY LIFE.
    out = neighbours[(unsigned int) arc4random() % count];
    return out;
}

// LUT for opposite directions

int opposite[N+1];

// int opposite(int direction) {
//     switch (direction) {
//         case N:
//             return S;
//         case S:
//             return N;
//         case W:
//             return E;
//         case E:
//             return W;
//         default:
//             return -1;
//     }
// }

void carve(int ox, int oy, struct maze *m) {
    int *current = &m->data[(m->width * oy) + ox];
    while (true) {
        // Pick a random neighbour.
        struct neighbour nb = get_neighbour(ox, oy, m);
        // No neighbours? Done!
        if (nb.ox == 0 && nb.oy == 0) {
            return;
        }

        // Check if there's any path to the neighbour
        // If not:
        if (!(*current & nb.direction) && *nb.data == NONE) {
            *nb.data |= opposite[nb.direction]; // carved!
            // carve self!
            *current |= nb.direction;
            // recur!
            carve(ox + nb.ox, oy + nb.oy, m);
        }

    }
}

void carve_maze(struct maze *m) {
    // Fill the maze, we'll be carving paths out.
    fill_maze(m);
    carve(0, 0, m);
}

void init_opposite(void) {
    opposite[N] = S;
    opposite[S] = N;
    opposite[E] = W;
    opposite[W] = E;
}

int main(int argc, char **argv) {
    init_opposite();
    setlocale(LC_ALL, "");

    int side_length = 10;
    if (argc > 1) {
        // Try to parse length argument
        int user_length;
        int converted = sscanf(argv[1], "%d", &user_length);
        if (converted >= 1) {
//            a->b
            side_length = user_length;
        } 
    } else {
        printf("Defaulting to a side length of 10.\n"
                "Call with side length argument to generate a maze of custom size.\n"
                "\t ./c_maze [side_length]\n");
    }

    int *box_data = (int *) calloc(side_length*side_length, sizeof(int));
    struct maze box_maze = {box_data, side_length, side_length};

    carve_maze(&box_maze);
    display_maze(box_maze);

    free(box_data);
    return 0;
}