Arrow maze generator (/r/dailyprogrammer)

Makefile

CC = cc -std=c89 -ansi
CFLAGS = -Wall -Wextra -O3 -march=native

maze: maze.c

clean:
	rm -f maze

maze.c

/* https://redd.it/6rqwxk */
#include <time.h>
#include <stdio.h>
#include <stdlib.h>
#include <getopt.h>

static unsigned long
rand32(unsigned long *state)
{
    unsigned long x = *state;
    x ^= x << 13;
    x ^= (x & 0xffffffffUL) >> 17;
    x ^= x << 5;
    return (*state = x) & 0xffffffffUL;
}

/* Maze representation */
enum {N, NE, E, SE, S, SW, W, NW, H};
static const signed char moves[] = {
    +0, -1, +1, -1, +1, +0, +1, +1, +0, +1, -1, +1, -1, +0, -1, -1,
};
static const char names[][3] = {
    [N] = "n", [NE] = "ne", [E] = "e", [SE] = "se",
    [S] = "s", [SW] = "sw", [W] = "w", [NW] = "nw",
    [H] = "h"
};

struct maze {
    unsigned long seed;
    int *solution;
    int w;
    int h;
    int s;
    int e;
    char g[];
};

static struct maze *
maze_create(unsigned long *rng, int w, int h)
{
    struct maze *m = malloc(sizeof(*m) + w * h);
    if (m) {
        int i;
        m->seed = *rng & 0xffffffffUL;
        m->solution = 0;
        m->w = w;
        m->h = h;
        m->e = h / 2 * w + w / 2;
        do
            m->s = rand32(rng) % (w * h);
        while (m->s == m->e);
        for (i = 0; i < w * h; i++)
            m->g[i] = rand32(rng) % 8;
        m->g[m->e] = H;
    }
    return m;
}

static void
maze_destroy(struct maze *m)
{
    free(m->solution);
    free(m);
}

static int
maze_length(struct maze *m)
{
    if (m) {
        int i;
        int len = 0;
        for (i = 0; m->solution[i] != -1; i++)
            len++;
        return len;
    } else {
        return -1;
    }
}

static void
maze_print(struct maze *m)
{
    int x, y;
    printf("# length=%d, seed=%08lx\n", maze_length(m), m->seed);
    printf("(%d,%d)\n", m->s % m->w, m->s / m->w);
    for (y = 0; y < m->h; y++) {
        for (x = 0; x < m->w; x++)
            printf("%3s", names[(int)m->g[y * m->w + x]]);
        putchar('\n');
    }
}

static void
maze_svg(struct maze *m, int s, int print_solution)
{
    int x, y;
    int re = s * 3 / 8;

    printf("<svg version='1.1' xmlns='http://www.w3.org/2000/svg' "
            "width='%d' height='%d'>\n", m->w * s, m->h * s);
    puts("<!--");
    maze_print(m);
    puts("-->");
    for (y = 0; y < m->h; y++) {
        for (x = 0; x < m->w; x++) {
            int i = y * m->w + x;
            int c = m->g[i];
            int cx = x * s + s / 2;
            int cy = y * s + s / 2;
            char *bg = i == m->s ? "black" : "white";
            char *fg = i == m->s ? "white" : "black";
            printf("<rect x='%d' y='%d' width='%d' height='%d' ",
                    x * s, y * s, s, s);
            printf("style='stroke: black; stroke-width: 2px; fill: %s;'/>\n",
                    bg);
            if (c == H) {
                printf("<circle cx='%d' cy='%d' r='%d'/>\n", cx, cy, re);
            } else {
                /* Shaft */
                printf("<line x1='%d' y1='%d' x2='%d' y2='%d' ", 
                        x * s + s / 2, y * s + s * 1 / 8,
                        x * s + s / 2, y * s + s * 7 / 8);
                printf("style='stroke: %s; "
                        "stroke-linecap: round; "
                        "stroke-width: %dpx;' ", fg, s / 10);
                printf("transform='rotate(%d %d %d)'/>\n", c * 45, cx, cy);
                /* Left */
                printf("<line x1='%d' y1='%d' x2='%d' y2='%d' ", 
                        x * s + s / 2, y * s + s * 1 / 8,
                        x * s + s * 1 / 6, y * s + s * 29 / 64);
                printf("style='stroke: %s; "
                        "stroke-linecap: round; "
                        "stroke-width: %dpx;' ", fg, s / 10);
                printf("transform='rotate(%d %d %d)'/>\n", c * 45, cx, cy);
                /* Right */
                printf("<line x1='%d' y1='%d' x2='%d' y2='%d' ", 
                        x * s + s / 2, y * s + s * 1 / 8,
                        x * s + s * 5 / 6, y * s + s * 29 / 64);
                printf("style='stroke: %s; "
                        "stroke-linecap: round; "
                        "stroke-width: %dpx;' ", fg, s / 10);
                printf("transform='rotate(%d %d %d)'/>\n", c * 45, cx, cy);
            }
        }
    }
    if (print_solution && m->solution) {
        int i;
        for (i = 0; m->solution[i] != -1; i++) {
            int x2 = m->solution[i] % m->w;
            int y2 = m->solution[i] / m->w;
            if (i > 0) {
                int x1 = m->solution[i - 1] % m->w;
                int y1 = m->solution[i - 1] / m->w;
                printf("<line x1='%d' y1='%d' x2='%d' y2='%d' ",
                        x1 * s + s / 2, y1 * s + s / 2,
                        x2 * s + s / 2, y2 * s + s / 2);
                printf("style='"
                        "stroke: red; "
                        "stroke-width: %dpx; "
                        "stroke-linecap: round'/>\n",
                        s / 20);
            }
            printf("<circle cx='%d' cy='%d' r='%d' "
                    "style='fill: red;'/>\n",
                    x2 * s + s / 2, y2 * s + s / 2, s / 8);
        }
    }
    printf("</svg>\n");
}

static int *
maze_solve(struct maze *m)
{
    int head = 0;
    int tail = 1;
    int *queue = malloc(m->w * m->h * sizeof(*queue) * 2);
    char *mark = calloc(m->w, m->h);
    mark[m->e] = 1;
    queue[0] = m->e;
    queue[1] = -1;

    for (; head != tail; head++) {
        int i, d;
        int n = queue[head * 2 + 0];

        if (n == m->s) {
            /* Find the solution length */
            int len = 2;
            int p = head;
            do {
                p = queue[p * 2 + 1];
                len++;
            } while (p);

            /* Store the solution */
            m->solution = malloc(len * sizeof(*m->solution));
            int i = 0;
            p = head;
            m->solution[i++] = n;
            do {
                p = queue[p * 2 + 1];
                m->solution[i++] = queue[p * 2 + 0];
            } while (p);
            m->solution[i] = -1;

            free(mark);
            free(queue);
            return m->solution;
        }

        /* Enqueue all neighbors */
        for (i = 0; i < 8; i++) {
            for (d = 1; ; d++) {
                int x = n % m->w + d * moves[i * 2 + 0];
                int y = n / m->w + d * moves[i * 2 + 1];
                if (x >= 0 && x < m->w && y >= 0 && y < m->h) {
                    int c = y * m->w + x;
                    if (!mark[c] && m->g[c] == (i + 4) % 8) {
                        queue[tail * 2 + 0] = c;
                        queue[tail * 2 + 1] = head;
                        tail++;
                        mark[c] = 1;
                    }
                } else {
                    break;
                }
            }
        }
    }

    /* No solution found. */
    free(mark);
    free(queue);
    return 0;
}

static unsigned long
genseed(void)
{
    unsigned long seed;
    FILE *r = fopen("/dev/urandom", "rb");
    if (!r) {
        seed = time(0);
    } else {
        if (!fread(&seed, sizeof(seed), 1, r))
            seed = time(0);
        fclose(r);
    }
    return seed;
}

static void
print_usage(FILE *o)
{
    fputs("Usage: program [options]\n", o);
    fputs("-a <n>     minimum solution length\n", o);
    fputs("-b <n>     maximum solution length\n", o);
    fputs("-h <n>     maze height\n", o);
    fputs("-p         include solution\n", o);
    fputs("-s <n>     cell size in pixels\n", o);
    fputs("-w <n>     maze width\n", o);
    fputs("-x <hex>   seed\n", o);
}

int
main(int argc, char **argv)
{
    int h = 5;
    int w = 5;
    int s = 100;
    int min = 8;
    int max = 20;
    int print_solution = 0;
    unsigned long seed = 0;

    int option;
    while ((option = getopt(argc, argv, "a:b:h:ps:w:x:")) != -1) {
        switch (option) {
            case 'a':
                min = atoi(optarg);
                break;
            case 'b':
                max = atoi(optarg);
                break;
            case 'h':
                h = atoi(optarg);
                break;
            case 'p':
                print_solution = 1;
                break;
            case 's':
                s = atoi(optarg);
                break;
            case 'w':
                w = atoi(optarg);
                break;
            case 'x':
                seed = strtoul(optarg, 0, 16);
                break;
            default:
                print_usage(stderr);
                exit(EXIT_FAILURE);
        }
    }
    if (argv[optind]) {
        print_usage(stderr);
        exit(EXIT_FAILURE);
    }
    if (!seed)
        seed = genseed();

    for (;;) {
        struct maze *m = maze_create(&seed, w, h);
        int *solution = maze_solve(m);
        if (solution) {
            int len = maze_length(m);
            if (len >= min && len <= max) {
                maze_svg(m, s, print_solution);
                exit(EXIT_SUCCESS);
            }
        }
        maze_destroy(m);
    }
}