/*
* A classic maze-generator in C, by Chris Pressey, sometime late in 2011.
*
* SPDX-FileCopyrightText: Chris Pressey, the original author of this work, has dedicated it to the public domain.
* For more information, please refer to <https://unlicense.org/>
* SPDX-License-Identifier: Unlicense
*
* The implementation does not use recursion, or indeed a stack; back-
* tracking information is stored right in the array in which we generate
* the maze. I encountered this idea in a BASIC maze-generator program
* which I dimly remember from the magazine "Enter" in the 80's, but I
* don't think I appreciated it until writing a recursive maze-generator
* in Pascal sometime in the early 90's. I did not try this in-place
* method until writing the program that now stands before you.
*
* The coding style is particularly inelegant (observe the heavy use of
* global variables!) because this source was meant to be an intermediate
* step towards implementing the algorithm in assembly.
*/
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <assert.h>
#define SIZE_X 40
#define SIZE_Y 21
/*
* top four bits is reverse
* bottom four bits is tried
*/
unsigned char *maze;
#define UNSEEN 0x00
#define START 0x0f
#define NORTH 0x01
#define SOUTH 0x02
#define EAST 0x04
#define WEST 0x08
#define NONE 0x00
#define ALL 0x0f
unsigned char d, opp, x, y;
signed char dx, dy;
int pos;
void set_reverse(unsigned char reverse)
{
maze[pos] = (maze[pos] & 0x0f) | (reverse << 4);
}
unsigned char get_reverse(void)
{
return (maze[pos] & 0xf0) >> 4;
}
void mark_tried(unsigned char d)
{
maze[pos] |= d;
}
void set_tried(unsigned char d)
{
maze[pos] = (maze[pos] & 0xf0) | (d & 0x0f);
}
unsigned char get_tried(void)
{
return maze[pos] & 0x0f;
}
void calc_pos(void)
{
pos = y * SIZE_X + x;
}
void clear(void)
{
for (x = 0; x < SIZE_X; x++)
for (y = 0; y < SIZE_Y; y++) {
calc_pos();
maze[pos] = 0;
}
}
void draw(void)
{
for (y = 0; y < SIZE_Y; y++) {
for (x = 0; x < SIZE_X; x++) {
calc_pos();
if (x % 2 == 1 && y % 2 == 1)
assert(get_tried() == ALL);
if (get_tried() == ALL) {
printf(" ");
} else {
printf("#");
}
}
printf("#\n");
}
}
void get_delta(int d)
{
switch (d) {
case NORTH:
opp = SOUTH;
dx = 0;
dy = -1;
break;
case SOUTH:
opp = NORTH;
dx = 0;
dy = 1;
break;
case EAST:
opp = WEST;
dx = 1;
dy = 0;
break;
case WEST:
opp = EAST;
dx = -1;
dy = 0;
break;
}
}
int in_bounds(int nx, int ny)
{
return nx >= 0 && ny >= 0 && nx < SIZE_X && ny < SIZE_Y;
}
void make(void)
{
again:
calc_pos();
if (get_tried() == ALL) {
if (get_reverse() == START) {
assert(x == 1 && y == 1);
return;
}
get_delta(get_reverse());
x += (dx + dx);
y += (dy + dy);
goto again;
}
d = 1 << (random() & 0x03);
mark_tried(d);
get_delta(d);
if (!in_bounds(x + dx + dx, y + dy + dy))
goto again;
x += (dx + dx);
y += (dy + dy);
calc_pos();
if (get_tried() != NONE) {
x -= (dx + dx);
y -= (dy + dy);
goto again;
}
set_reverse(opp);
x -= dx;
y -= dy;
calc_pos();
set_tried(ALL);
x += dx;
y += dy;
goto again;
}
int main(int argc, char **argv)
{
srandom(time(NULL));
maze = malloc(SIZE_X * SIZE_Y * sizeof(unsigned char));
clear();
x = 1; y = 1;
calc_pos();
set_reverse(START);
make();
draw();
exit(0);
}