maze-thing/main.c

/*
 * Copyright (c) Camden Dixie O'Brien
 * SPDX-License-Identifier: AGPL-3.0-only
 */

#define _POSIX_C_SOURCE 199309L

#include <X11/Xlib.h>
#include <assert.h>
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
#include <sys/time.h>
#include <time.h>
#include <unistd.h>

#define MAZE_WIDTH 958
#define MAZE_HEIGHT 538
#define PX(x) (x)

#define GRID_WIDTH (2 * MAZE_WIDTH - 1)
#define GRID_HEIGHT (2 * MAZE_HEIGHT - 1)
#define WINDOW_WIDTH (GRID_WIDTH + 2)
#define WINDOW_HEIGHT (GRID_HEIGHT + 2)

#define ENTRANCE_X (-1)
#define ENTRANCE_Y 0
#define EXIT_X GRID_WIDTH
#define EXIT_Y (GRID_HEIGHT - 1)

#define MAX_PATH_LENGTH (MAZE_WIDTH * MAZE_HEIGHT)
#define STACK_SIZE MAX_PATH_LENGTH

typedef enum { LEFT, RIGHT, UP, DOWN } dir_t;

typedef struct {
	int x, y;
} vec2_t;

typedef bool (*coord_pred_t)(vec2_t c, vec2_t im);
typedef bool (*visit_fn_t)(vec2_t c, vec2_t im);

typedef struct {
	bool is_path : 1;
	bool visited : 1;
} cell_t;

static const struct timespec path_draw_pause = { .tv_nsec = 100000 };

static const vec2_t steps[] = {
	[LEFT] = { .x = -2, .y = 0 },
	[RIGHT] = { .x = 2, .y = 0 },
	[UP] = { .x = 0, .y = -2 },
	[DOWN] = { .x = 0, .y = 2 },
};

static const vec2_t start = { 0, 0 };
static const vec2_t end = { GRID_WIDTH - 1, GRID_HEIGHT - 1 };

static cell_t maze[GRID_WIDTH][GRID_HEIGHT];
static Display *dpy;
static Window window;
static GC ctx;

static void draw_cell(int x, int y)
{
	XFillRectangle(
	    dpy, window, ctx, 1 + PX(x + 1), 1 + PX(y + 1), PX(1), PX(1));
}

static void clear_cell(int x, int y)
{
	XClearArea(
	    dpy, window, 1 + PX(x + 1), 1 + PX(y + 1), PX(1), PX(1), false);
}

static bool in_bounds(int x, int y)
{
	const bool valid_x = x >= 0 && x < GRID_WIDTH;
	const bool valid_y = y >= 0 && y < GRID_HEIGHT;
	return valid_x && valid_y;
}

static bool finished_gen(int x, int y)
{
	int nx, ny;
	for (int i = 0; i < 4; ++i) {
		nx = x + steps[i].x;
		ny = y + steps[i].y;
		if (in_bounds(nx, ny) && !maze[nx][ny].is_path)
			return false;
	}
	return true;
}

static void generate(vec2_t p)
{
	vec2_t stack[STACK_SIZE], *sp = stack;
	maze[p.x][p.y].is_path = true;

	do {
		if (finished_gen(p.x, p.y)) {
			p = *(--sp);
			continue;
		}

		int nx, ny;
		do {
			dir_t d = rand() % 4;
			nx = p.x + steps[d].x;
			ny = p.y + steps[d].y;
		} while (!in_bounds(nx, ny) || maze[nx][ny].is_path);

		const int imx = (p.x + nx) / 2;
		const int imy = (p.y + ny) / 2;
		maze[imx][imy].is_path = maze[nx][ny].is_path = true;

		*sp++ = p;
		p.x = nx;
		p.y = ny;
	} while (sp != stack);
}

static void solve(vec2_t p, vec2_t *sp, vec2_t **top)
{
	maze[0][0].visited = true;
	*sp++ = p;

	while (1) {
		if (end.x == p.x && end.y == p.y) {
			*sp++ = p;
			*top = sp;
			return;
		}

		int nx, ny, imx, imy;
		bool done = true;
		for (int i = 0; i < 4; ++i) {
			nx = p.x + steps[i].x;
			ny = p.y + steps[i].y;
			if (!in_bounds(nx, ny))
				continue;

			imx = (p.x + nx) / 2;
			imy = (p.y + ny) / 2;
			if (maze[imx][imy].is_path && !maze[nx][ny].visited) {
				done = false;
				break;
			}
		}

		if (done) {
			p = *(--sp);
			continue;
		}

		maze[imx][imy].visited = maze[nx][ny].visited = true;

		*sp++ = p;
		p.x = nx;
		p.y = ny;
	}
}

int main(void)
{
	// Seed random number generation from time
	struct timeval tv;
	gettimeofday(&tv, NULL);
	srand(tv.tv_usec);

	XEvent evt;
	dpy = XOpenDisplay(NULL);
	assert(dpy);

	// Create window and configure graphics context
	const int black = BlackPixel(dpy, DefaultScreen(dpy));
	const int white = WhitePixel(dpy, DefaultScreen(dpy));
	window = XCreateSimpleWindow(
	    dpy, DefaultRootWindow(dpy), 0, 0, PX(WINDOW_WIDTH),
	    PX(WINDOW_HEIGHT), 0, black, black);
	Atom del = XInternAtom(dpy, "WM_DELETE_WINDOW", false);
	XSetWMProtocols(dpy, window, &del, 1);
	ctx = DefaultGC(dpy, DefaultScreen(dpy));

	// Create colormap and allocate colour for visited cells
	Colormap cm = XCreateColormap(
	    dpy, window, DefaultVisual(dpy, DefaultScreen(dpy)), AllocNone);
	XColor xcol = { .red = 55555, .green = 10000, .blue = 10000 };
	XAllocColor(dpy, cm, &xcol);
	const int red = xcol.pixel;

	// Map window
	XSelectInput(dpy, window, StructureNotifyMask);
	XMapWindow(dpy, window);
	do
		XNextEvent(dpy, &evt);
	while (MapNotify != evt.type);

	// Draw entrance and exit
	XSetForeground(dpy, ctx, white);
	draw_cell(ENTRANCE_X, ENTRANCE_Y);
	draw_cell(EXIT_X, EXIT_Y);
	XFlush(dpy);

	while (1) {
		// Generate
		memset(&maze, 0, sizeof(maze));
		generate(end);

		// Draw maze
		XSetForeground(dpy, ctx, white);
		draw_cell(ENTRANCE_X, ENTRANCE_Y);
		for (int y = 0; y < GRID_HEIGHT; ++y) {
			for (int x = 0; x < GRID_WIDTH; ++x) {
				if (maze[x][y].is_path)
					draw_cell(x, y);
				else
					clear_cell(x, y);
			}
		}
		draw_cell(EXIT_X, EXIT_Y);
		XFlush(dpy);

		sleep(1);

		// Solve
		vec2_t path[MAX_PATH_LENGTH], *path_end;
		solve(start, path, &path_end);

		// Draw solution path
		XSetForeground(dpy, ctx, red);
		draw_cell(ENTRANCE_X, ENTRANCE_Y);
		const vec2_t *prev = &start;
		for (const vec2_t *p = path; p < path_end; ++p) {
			const int imx = (prev->x + p->x) / 2;
			const int imy = (prev->y + p->y) / 2;

			draw_cell(imx, imy);
			draw_cell(p->x, p->y);
			XFlush(dpy);

			nanosleep(&path_draw_pause, NULL);
			prev = p;
		}
		draw_cell(EXIT_X, EXIT_Y);
		XFlush(dpy);

		sleep(1);
	}

	// Wait for window exit
	bool is_del = false;
	do {
		XNextEvent(dpy, &evt);
		if (ClientMessage == evt.type)
			is_del = (unsigned long)evt.xclient.data.l[0] == del;
	} while (!is_del);

	XCloseDisplay(dpy);
	return EXIT_SUCCESS;
}