mazegen.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <locale.h>

wchar_t glyph[] = L""
                  " "
                  "│││─┘┐┤─└┌├─┴┬┼"
                  " "
                  "┆";

typedef unsigned char byte;

enum
{
    N = 1,
    S = 2,
    W = 4,
    E = 8,
    V = 16
};

byte **cell;
int w, h, avail;
#define each(i, x, y) for (i = x; i <= y; i++)

int irand(int n)
{
    int r, rmax = n * (RAND_MAX / n);
    while ((r = rand()) >= rmax)
        ;
    return r / (RAND_MAX / n);
}

void show()
{
    int i, j;
    each(i, 0, 2 * h)
    {
        each(j, 0, 2 * w)
        {
            printf("%lc", glyph[cell[i][j]]);
        }
        printf("\n");
    }
}

static int dirs[4][2] = {{-2, 0}, {0, 2}, {2, 0}, {0, -2}};

void walk(int x, int y)
{
    int i, t, x1, y1, d[4] = {0, 1, 2, 3};

    cell[y][x] |= V;
    avail--;

    for (x1 = 3; x1; x1--)
        if (x1 != (y1 = irand(x1 + 1)))
            i = d[x1], d[x1] = d[y1], d[y1] = i;

    for (i = 0; avail && i < 4; i++)
    {
        x1 = x + dirs[d[i]][0], y1 = y + dirs[d[i]][1];

        if (cell[y1][x1] & V)
            continue;

        /* break walls */
        if (x1 == x)
        {
            t = (y + y1) / 2;
            cell[t][x + 1] &= ~W, cell[t][x] &= ~(E | W), cell[t][x - 1] &= ~E;
        }
        else if (y1 == y)
        {
            t = (x + x1) / 2;
            cell[y - 1][t] &= ~S, cell[y][t] &= ~(N | S), cell[y + 1][t] &= ~N;
        }
        walk(x1, y1);
    }
}

void make_maze()
{
    int i, j;
    int h2 = 2 * h + 2, w2 = 2 * w + 2;
    byte **p;

    p = calloc(sizeof(byte *) * (h2 + 2) + w2 * h2 + 1, 1);

    p[1] = (byte *)(p + h2 + 2) + 1;

    each(i, 2, h2) p[i] = p[i - 1] + w2;
    p[0] = p[h2];
    cell = &p[1];

    each(i, -1, 2 * h + 1) cell[i][-1] = cell[i][w2 - 1] = V;
    each(j, 0, 2 * w) cell[-1][j] = cell[h2 - 1][j] = V;
    each(i, 0, h) each(j, 0, 2 * w) cell[2 * i][j] |= E | W;
    each(i, 0, 2 * h) each(j, 0, w) cell[i][2 * j] |= N | S;
    each(j, 0, 2 * w) cell[0][j] &= ~N, cell[2 * h][j] &= ~S;
    each(i, 0, 2 * h) cell[i][0] &= ~W, cell[i][2 * w] &= ~E;

    avail = w * h;
    walk(1, 1);

    show();
}

int main()
{
    setlocale(LC_ALL, "");

    printf("Enter height : ");
    scanf("%d", &h);
    printf("\nEnter height : ");
    scanf("%d", &w);

    make_maze();

    return 0;
}