# To unbundle, run this file
echo maze.c
sed 's/^X//' >maze.c <<'!'
X/*
X * maze - generates and solves mazes, with graphical display
X *	ported to Plan 9 by andrey@lanl.gov, August 2002.
X *	see maze.novel for too much information.
X */

X#include <u.h>
X#include <libc.h>
X#include <pool.h>
X#include <draw.h>
X#include <event.h>

X#define random rand
X#define	get_random(x)	(rand() % (x))

enum {
X	Debug = 0,

X	/* these must fit in a ushort */
X	Wallleft	= 1<<0,
X	Wallbottom	= 1<<1,
X	Wallright	= 1<<2,
X	Walltop		= 1<<3,
X	Wallany = Walltop | Wallright | Wallbottom | Wallleft,

X	Dooroutleft	= 1<<4,
X	Dooroutbottom	= 1<<5,
X	Dooroutright	= 1<<6,
X	Doorouttop	= 1<<7,

X	Doorinleft	= 1<<8,
X	Doorinbottom	= 1<<9,
X	Doorinright	= 1<<10,
X	Doorintop	= 1<<11,
X	Doorinany = Doorintop | Doorinright | Doorinbottom | Doorinleft,

X	Endsq		= 1<<12,
X	Startsq		= 1<<13,
X	Solvervisit	= 1<<14,
X	Notdead		= 1<<15,

X	Border_x        = 0,
X	Border_y        = 0,
X	Slop		= 10,		/* excess grids for random groping */

X	Logowidth = 48,
X	Logoheight = Logowidth,
X};
enum { Nozero, Zero };

typedef struct {
X	/* on modern displays, we can have > 256 grid squares on an axis */
X	ushort	x;
X	ushort	y;
X	uchar	dir;
X	uchar	ways;
X} Move;

static Image *colors[256];
static Image *liveColor, *deadColor, *skipColor, *surroundColor;
static Image *glenda;

static char *buttons[] = {
X	"exit",
X	0
X};
static Menu menu = {
X	buttons
X};

static ushort **maze, **mazealloc;	/* realloced for each new maze */
static Move *move_list, *path;		/* realloced for each new maze */
static int maze_size_x, maze_size_y;	/* in grid squares, not pixels */
static int grid_width, grid_height, gridsize;

static int solve_delay, pre_solve_delay, post_solve_delay;
static int logo_x, logo_y;
static int sqnum, cur_sq_x, cur_sq_y;
static int start_x, start_y, start_dir, end_x, end_y, end_dir;
static int bw;
static int restart = 0, stop = 0, state = 1, max_length;
static int sync_p, bridge_p, ignorant_p;

X/* For set_create_maze. */
static int *sets = 0;		/* The sets that our squares are in. */
static int *hedges = 0;		/* The `list' of hedges. */

static int	backup(void);
static void	build_wall(int, int, int);
static int	choose_door(void);
static void	draw_solid_square(int, int, int, Image*);
static void	draw_wall(int, int, int);
static void	join_sets(int, int);

static void *
emallocz(ulong size, int clr)
X{
X	void *p = mallocz(size, clr);

X	if (p == nil)
X		sysfatal("out of memory");
X	return p;
X}

static void
set_maze_sizes(int width, int height)		/* in pixels */
X{
X	int i;
X	long grids;
X	static int first = 1;

X	if (!first)
X		for (i = 0; i < maze_size_x + Slop; i++)
X			if (mazealloc[i])
X				free(mazealloc[i] - Slop/2);
X	first = 0;
X	free(mazealloc);
X	free(move_list);
X	free(path);

X	maze_size_x = width / grid_width;
X	maze_size_y = height / grid_height;
X	grids = (maze_size_x + Slop) * (maze_size_y + Slop);

X	mazealloc = emallocz((maze_size_x + Slop) * sizeof maze[0], Nozero);
X	for (i = 0; i < maze_size_x + Slop; i++) {
X		mazealloc[i] = emallocz((maze_size_y + Slop) *
X			sizeof maze[0][0], Zero);
X		mazealloc[i] += Slop/2;
X	}
X	maze = mazealloc + Slop/2;

X	move_list = emallocz(grids * sizeof *move_list, Zero);
X	path = emallocz(grids * sizeof *path, Zero);
X}

static void
initialize_maze(void)	/* draw the surrounding wall and start/end squares */
X{
X	int i, j, wall;
X	int logow = 1 + Logowidth / grid_width;
X	int logoh = 1 + Logoheight / grid_height;

X	for (i = 0; i < maze_size_x; i++) {
X		maze[i][0] |= Walltop;
X		maze[i][maze_size_y-1] |= Wallbottom;
X	}
X	for (j = 0; j < maze_size_y; j++) {
X		maze[maze_size_x-1][j] |= Wallright;
X		maze[0][j] |= Wallleft;
X	}

X	/* set start square */
X	wall = get_random(4);
X	switch (wall) {
X	case 0:
X		i = get_random(maze_size_x);
X		j = 0;
X		break;
X	case 1:
X		i = maze_size_x - 1;
X		j = get_random(maze_size_y);
X		break;
X	case 2:
X		i = get_random(maze_size_x);
X		j = maze_size_y - 1;
X		break;
X	case 3:
X		i = 0;
X		j = get_random(maze_size_y);
X		break;
X	}
X	maze[i][j] |= Startsq | (Doorintop >> wall);
X	maze[i][j] &= ~(Walltop >> wall);
X	cur_sq_x = start_x = i;
X	cur_sq_y = start_y = j;
X	start_dir = wall;
X	sqnum = 0;

X	/* set end square */
X	wall = (wall + 2) % 4;
X	switch (wall) {
X	case 0:
X		i = get_random(maze_size_x);
X		j = 0;
X		break;
X	case 1:
X		i = maze_size_x - 1;
X		j = get_random(maze_size_y);
X		break;
X	case 2:
X		i = get_random(maze_size_x);
X		j = maze_size_y - 1;
X		break;
X	case 3:
X		i = 0;
X		j = get_random(maze_size_y);
X		break;
X	}
X	maze[i][j] |= Endsq | (Doorouttop >> wall);
X	maze[i][j] &= ~(Walltop >> wall);
X	end_x = i;
X	end_y = j;
X	end_dir = wall;

X	/* set logo */
X	if (maze_size_x - logow >= 6 && maze_size_y - logoh >= 6) {
X		/* not closer than 3 grid units from a wall */
X		logo_x = get_random(maze_size_x - logow - 5) + 3;
X		logo_y = get_random(maze_size_y - logoh - 5) + 3;
X		for (i = 0; i < logow; i++)
X			for (j = 0; j < logoh; j++)
X				maze[logo_x + i][logo_y + j] |= Doorintop;
X	} else
X		logo_y = logo_x = -1;
X}

static void
setmove(Move *mv, int x, int y, int dir)
X{
X	mv->x = x;
X	mv->y = y;
X	mv->dir = dir;

X	/* check for overflow */
X	assert(mv->x == x);
X	assert(mv->y == y);
X	assert(mv->dir == dir);
X}

X/* Initialise the sets. */
static void
init_sets(void)
X{
X	int i, t, r, x, y;

X	free(sets);
X	sets = emallocz(maze_size_x * maze_size_y * sizeof(int), Nozero);
X	for (i = 0; i < maze_size_x * maze_size_y; i++)
X		sets[i] = i;

X	free(hedges);
X	hedges = emallocz(maze_size_x * maze_size_y * 2 * sizeof(int), Nozero);
X	for (i = 0; i < maze_size_x * maze_size_y * 2; i++)
X		hedges[i] = i;

X	/* Mask out outside walls. */
X	for (i = 0; i < maze_size_y; i++)
X		hedges[2*(maze_size_x*i + maze_size_x - 1) + 1] = -1;
X	for (i = 0; i < maze_size_x; i++)
X		hedges[2*((maze_size_y - 1)*maze_size_x + i)] = -1;

X	/* Mask out a possible logo. */
X	if (logo_x != -1) {
X		int logow = 1 + Logowidth / grid_width;
X		int logoh = 1 + Logoheight / grid_height;
X		int bridge_dir, bridge_c;

X		if (bridge_p && logoh >= 3 && logow >= 3) {
X			bridge_dir = 1 + random() % 2;
X			if (bridge_dir == 1)
X				bridge_c = logo_y + random() % (logoh - 2) + 1;
X			else
X				bridge_c = logo_x + random() % (logow - 2) + 1;
X		} else {
X			bridge_dir = 0;
X			bridge_c = -1;
X		}

X		for (x = logo_x; x < logo_x + logow; x++)
X			for (y = logo_y; y < logo_y + logoh; y++) {
X				/*
X				 * I should check for the bridge here,
X				 * except that I join the bridge together below.
X            			 */
X				hedges[2*(x + maze_size_x*y) + 1] = -1;
X				hedges[2*(x + maze_size_x*y)] = -1;
X			}
X		for (x = logo_x; x < logo_x + logow; x++) {
X			if (!(bridge_dir == 2 && x == bridge_c)) {
X				build_wall(x, logo_y, 0);
X				build_wall(x, logo_y + logoh, 0);
X			}
X			hedges[2*(x+maze_size_x*(logo_y-1))] = -1;
X			if (bridge_dir == 1) {
X				build_wall(x, bridge_c, 0);
X				build_wall(x, bridge_c, 2);
X			}
X		}
X		for (y = logo_y; y < logo_y + logoh; y++) {
X			if (!(bridge_dir == 1 && y == bridge_c)) {
X				build_wall(logo_x, y, 3);
X				build_wall(logo_x + logow, y, 3);
X			}
X			hedges[2*(logo_x-1+maze_size_x*y)+1] = -1;
X			if (bridge_dir == 2) {
X				build_wall(bridge_c, y, 1);
X				build_wall(bridge_c, y, 3);
X			}
X		}
X		/* Join the whole bridge together. */
X		if (bridge_p)
X			if (bridge_dir == 1) {
X				x = logo_x - 1;
X				y = bridge_c;
X				for (i = logo_x; i < logo_x + logow + 1; i++)
X					join_sets(x + y * maze_size_x,
X						  i + y * maze_size_x);
X			} else {
X				y = logo_y - 1;
X				x = bridge_c;
X				for (i = logo_y; i < logo_y + logoh + 1; i++)
X					join_sets(x + y * maze_size_x,
X						  x + i * maze_size_x);
X			}
X	}

X	for (i = 0; i < maze_size_x * maze_size_y * 2; i++) {
X		r = random() % (maze_size_x * maze_size_y * 2);
X		t = hedges[i];
X		hedges[i] = hedges[r];
X		hedges[r] = t;
X	}
X}

X/* Get the representative of a set. */
static int
get_set(int num)
X{
X	int *snp = &sets[num];
X	int setsnum = *snp;

X	if (setsnum == num)
X		return num;
X	else
X		return (*snp = get_set(setsnum));
X}

X/* Join two sets together. */
static void
join_sets(int num1, int num2)
X{
X	int s1, s2;

X	s1 = get_set(num1);
X	s2 = get_set(num2);
X	if (s1 < s2)
X		sets[s2] = s1;
X	else
X		sets[s1] = s2;
X}

X/* Exitialise the sets. */
static void
exit_sets(void)
X{
X	free(hedges);
X	hedges = nil;
X	free(sets);
X	sets = nil;
X}

X/*
X * Second alternative maze creator: Put each square in the maze in a
X * separate set. Also, make a list of all the hedges. Randomize that list.
X * Walk through the list. If, for a certain hedge, the two squares on both
X * sides of it are in different sets, union the sets and remove the hedge.
X * Continue until all hedges have been processed or only one set remains.
X */
static void
set_create_maze(void)
X{
X	int i, h, x, y, dir, v, w;
X	int xsz = maze_size_x, ysz = maze_size_y;	/* local copies */
X	int done = 2 * xsz * ysz;

X	init_sets();			/* Do almost all the setup. */
X	/* Start running through the hedges. */
X	for (i = 0; i < done; i++) {
X		h = hedges[i];

X		/* This one is in the logo or outside border. */
X		if (h == -1)
X			continue;

X		dir = h % 2? 1: 2;
X		x = (h >> 1) % xsz;
X		y = (h >> 1) / xsz;

X		v = x;
X		w = y;
X		switch (dir) {
X		case 1:
X			v++;
X			break;
X		case 2:
X			w++;
X			break;
X		}

X		if (get_set(x + y * xsz) != get_set(v + w * xsz))
X			join_sets(x + y * xsz, v + w * xsz);
X						/* Don't draw the wall. */
X		else
X			build_wall(x, y, dir);	/* Don't join the sets. */
X	}
X	exit_sets();				/* Free some memory. */
X}

X/*
X * First alternative maze creator: Pick a random, empty corner in the maze.
X * Pick a random direction.  Draw a wall in that direction, from that corner
X * until we hit a wall.  Option: Only draw the wall if it's going to be
X * shorter than a certain length.  Otherwise we get lots of long walls.
X */
static void
alt_create_maze(void)
X{
X	char *corners;
X	int *c_idx;
X	int i, j, height, width, open_corners, k, dir, x, y, size;

X	height = maze_size_y + 1;
X	width = maze_size_x + 1;
X	size = height * width;

X	/* Allocate and clear some mem. */
X	corners = emallocz(size, Zero);

X	/* Set up the indexing array. */
X	c_idx = emallocz(sizeof(int) * size, Nozero);
X	for (i = 0; i < size; i++)
X		c_idx[i] = i;
X	for (i = 0; i < size; i++) {
X		k = random() % size;
X		j = c_idx[i];
X		c_idx[i] = c_idx[k];
X		c_idx[k] = j;
X	}

X	/* Set up some initial walls. */
X	/* Outside walls. */
X	for (i = 0; i < width; i++) {
X		corners[i] = 1;
X		corners[i+width*(height-1)] = 1;
X	}
X	for (i = 0; i < height; i++) {
X		corners[i*width] = 1;
X		corners[i*width+width-1] = 1;
X	}
X	/* Walls around logo.  In fact, inside the logo, too. */
X	/* Also draw the walls. */
X	if (logo_x != -1) {
X		int logow = 1 + Logowidth/grid_width;
X		int logoh = 1 + Logoheight/grid_height;
X		int bridge_dir, bridge_c;

X		if (bridge_p && logoh >= 3 && logow >= 3) {
X			bridge_dir = 1 + random() % 2;
X			if (bridge_dir == 1)
X				bridge_c = logo_y + random()%(logoh - 2) + 1;
X			else
X				bridge_c = logo_x + random()%(logow - 2) + 1;
X		} else {
X			bridge_dir = 0;
X			bridge_c = -1;
X		}
X		for (i = logo_x; i <= logo_x + logow; i++)
X			for (j = logo_y; j <= logo_y + logoh; j++)
X				corners[i+width*j] = 1;
X		for (x = logo_x; x < logo_x + logow; x++) {
X			if (!(bridge_dir == 2 && x == bridge_c)) {
X				build_wall(x, logo_y, 0);
X				build_wall(x, logo_y + logoh, 0);
X			}
X			if (bridge_dir == 1) {
X				build_wall(x, bridge_c, 0);
X				build_wall(x, bridge_c, 2);
X			}
X		}
X		for (y = logo_y; y < logo_y + logoh; y++) {
X			if (!(bridge_dir == 1 && y == bridge_c)) {
X				build_wall(logo_x, y, 3);
X				build_wall(logo_x + logow, y, 3);
X			}
X			if (bridge_dir == 2) {
X				build_wall(bridge_c, y, 1);
X				build_wall(bridge_c, y, 3);
X			}
X		}
X		/* Connect one wall of the logo with an outside wall. */
X		if (bridge_p)
X			dir = (bridge_dir + 1) % 4;
X		else
X			dir = random() % 4;
X		switch (dir) {
X		case 0:
X			x = logo_x + (random() % (logow + 1));
X			y = logo_y;
X			break;
X		case 1:
X			x = logo_x + logow;
X			y = logo_y + (random() % (logoh + 1));
X			break;
X		case 2:
X			x = logo_x + (random() % (logow + 1));
X			y = logo_y + logoh;
X			break;
X		case 3:
X			x = logo_x;
X			y = logo_y + (random() % (logoh + 1));
X			break;
X		}
X		do {
X			corners[x+width*y] = 1;
X			switch (dir) {
X			case 0:
X				build_wall(x - 1, y - 1, 1);
X				y--;
X				break;
X			case 1:
X				build_wall(x, y, 0);
X				x++;
X				break;
X			case 2:
X				build_wall(x, y, 3);
X				y++;
X				break;
X			case 3:
X				build_wall(x - 1, y - 1, 2);
X				x--;
X				break;
X			}
X		} while (!corners[x+width*y]);
X		if (bridge_p) {
X			dir = (dir + 2) % 4;
X			switch (dir) {
X			case 0:
X				x = logo_x + (random() % (logow + 1));
X				y = logo_y;
X				break;
X			case 1:
X				x = logo_x + logow;
X				y = logo_y + (random() % (logoh + 1));
X				break;
X			case 2:
X				x = logo_x + (random() % (logow + 1));
X				y = logo_y + logoh;
X				break;
X			case 3:
X				x = logo_x;
X				y = logo_y + (random() % (logoh + 1));
X				break;
X			}
X			do {
X				corners[x+width*y] = 1;
X				switch (dir) {
X				case 0:
X					build_wall(x - 1, y - 1, 1);
X					y--;
X					break;
X				case 1:
X					build_wall(x, y, 0);
X					x++;
X					break;
X				case 2:
X					build_wall(x, y, 3);
X					y++;
X					break;
X				case 3:
X					build_wall(x - 1, y - 1, 2);
X					x--;
X					break;
X				}
X			} while (!corners[x+width*y]);
X		}
X	}

X	/* Count open gridpoints. */
X	open_corners = 0;
X	for (i = 0; i < width; i++)
X		for (j = 0; j < height; j++)
X			if (!corners[i+width*j])
X				open_corners++;

X	/* Now do actual maze generation. */
X	while (open_corners > 0)
X		for (i = 0; i < size; i++)
X			if (!corners[c_idx[i]]) {
X				x = c_idx[i] % width;
X				y = c_idx[i] / width;
X				/* Choose a random direction. */
X				dir = random() % 4;

X				k = 0;
X				/* Measure the length of the wall we'd draw. */
X				while (!corners[x+width*y]) {
X					k++;
X					switch (dir) {
X					case 0:
X						y--;
X						break;
X					case 1:
X						x++;
X						break;
X					case 2:
X						y++;
X						break;
X					case 3:
X						x--;
X						break;
X					}
X				}

X				if (k <= max_length) {
X					x = c_idx[i] % width;
X					y = c_idx[i] / width;

X					/* Draw a wall until we hit something */
X					while (!corners[x+width*y]) {
X						open_corners--;
X						corners[x+width*y] = 1;
X						switch (dir) {
X						case 0:
X							build_wall(x-1, y-1, 1);
X							y--;
X							break;
X						case 1:
X							build_wall(x, y, 0);
X							x++;
X							break;
X						case 2:
X							build_wall(x, y, 3);
X							y++;
X							break;
X						case 3:
X							build_wall(x-1, y-1, 2);
X							x--;
X							break;
X						}
X					}
X				}
X			}

X	/* Free some memory we used. */
X	free(corners);
X	free(c_idx);
X}

X/*
X * The original maze creator.  Start somewhere.  Take a step in a random
X * direction.  Keep doing this until we hit a wall.  Then, backtrack until
X * we find a point where we can go in another direction.
X */
static void
create_maze(void)	/* create a maze layout given the initialized maze */
X{
X	int i, newdoor = 0;
X	int logow = 1 + Logowidth / grid_width;
X	int logoh = 1 + Logoheight / grid_height;

X	/* Maybe we should make a bridge? */
X	if (bridge_p && logo_x >= 0 && logow >= 3 && logoh >= 3) {
X		int bridge_dir, bridge_c;

X		bridge_dir = 1 + random() % 2;
X		if (bridge_dir == 1)
X			if (logoh >= 3)
X				bridge_c = logo_y + random() % (logoh - 2) + 1;
X			else
X				bridge_c = logo_y + random() % logoh;
X		else
X			if (logow >= 3)
X				bridge_c = logo_x + random() % (logow - 2) + 1;
X			else
X				bridge_c = logo_x + random() % logow;

X		if (bridge_dir == 1)
X			for (i = logo_x; i < logo_x + logow; i++)
X				maze[i][bridge_c] &= ~Doorintop;
X		else
X			for (i = logo_y; i < logo_y + logoh; i++)
X				maze[bridge_c][i] &= ~Doorintop;
X	}

X	for (; ;) {
X		setmove(move_list + sqnum, cur_sq_x, cur_sq_y, newdoor);
X		while ((newdoor = choose_door()) == -1)	/* pick a door */
X			if (backup() == -1)	/* no more doors ... backup */
X				return;	
X		sqnum++;

X		/* mark the out door */
X		maze[cur_sq_x][cur_sq_y] |= Doorouttop >> newdoor;

X		switch (newdoor) {
X		case 0:
X			cur_sq_y--;
X			break;
X		case 1:
X			cur_sq_x++;
X			break;
X		case 2:
X			cur_sq_y++;
X			break;
X		case 3:
X			cur_sq_x--;
X			break;
X		}

X		/* mark the in door */
X		maze[cur_sq_x][cur_sq_y] |= Doorintop >> ((newdoor + 2) % 4);

X		if (maze[cur_sq_x][cur_sq_y] & Endsq) {
X			/* we're done; we've got a soluble maze. */
X		}
X	}
X}

static int
choose_door(void)				/* pick a new path */
X{
X	int candidate = 0, ncand = 0;
X	int cursqx = cur_sq_x, cursqy = cur_sq_y;	/* local copies */
X	int candidates[3];
X	ushort *sqp = &maze[cursqx][cursqy];

X	/* top wall */
X	if (!(*sqp & (Doorintop|Doorouttop|Walltop)))
X		if (maze[cursqx][cursqy - 1] & Doorinany) {
X			*sqp |= Walltop;
X			maze[cursqx][cursqy - 1] |= Wallbottom;
X			draw_wall(cursqx, cursqy, candidate);
X		} else
X			candidates[ncand++] = candidate;
X	candidate++;

X	/* right wall */
X	if (!(*sqp & (Doorinright|Dooroutright|Wallright)))
X		if (maze[cursqx + 1][cursqy] & Doorinany) {
X			*sqp |= Wallright;
X			maze[cursqx + 1][cursqy] |= Wallleft;
X			draw_wall(cursqx, cursqy, candidate);
X		} else
X			candidates[ncand++] = candidate;
X	candidate++;

X	/* bottom wall */
X	if (!(*sqp & (Doorinbottom|Dooroutbottom|Wallbottom)))
X		if (maze[cursqx][cursqy + 1] & Doorinany) {
X			*sqp |= Wallbottom;
X			maze[cursqx][cursqy + 1] |= Walltop;
X			draw_wall(cursqx, cursqy, candidate);
X		} else
X			candidates[ncand++] = candidate;
X	candidate++;

X	/* left wall */
X	if (!(*sqp & (Doorinleft|Dooroutleft|Wallleft)))
X		if (maze[cursqx - 1][cursqy] & Doorinany) {
X			*sqp |= Wallleft;
X			maze[cursqx - 1][cursqy] |= Wallright;
X			draw_wall(cursqx, cursqy, candidate);
X		} else
X			candidates[ncand++] = candidate;
X	candidate++;
X	USED(candidate);

X	if (ncand == 0)
X		return -1;
X	if (ncand == 1)
X		return candidates[0];
X	return candidates[get_random(ncand)];

X}

static int
backup(void)					/* back up a move */
X{
X	sqnum--;
X	if (sqnum >= 0) {
X		cur_sq_x = move_list[sqnum].x;
X		cur_sq_y = move_list[sqnum].y;
X	} else
X		cur_sq_x = cur_sq_y = 0;
X	return sqnum;
X}

static void
draw_maze_border(void)				/* draw the maze outline */
X{
X	int i, j;

X	for (i = 0; i < maze_size_x; i++) {
X		if (maze[i][0] & Walltop)
X			line(screen, addpt(screen->r.min,
X				Pt(Border_x + grid_width * i, Border_y)),
X			    addpt(screen->r.min,
X				Pt(Border_x + grid_width*(i+1) - 1, Border_y)),
X			    Endsquare, Endsquare, 0, display->white, ZP);
X		if ((maze[i][maze_size_y - 1] & Wallbottom))
X			line(screen, addpt(screen->r.min,
X			    Pt(Border_x + grid_width * i,
X				Border_y + grid_height * (maze_size_y) - 1)),
X			    addpt(screen->r.min,
X			    Pt(Border_x + grid_width * (i + 1) - 1,
X				Border_y + grid_height * (maze_size_y) - 1)),
X			    Endsquare, Endsquare, 0, display->white, ZP);
X	}
X	for (j = 0; j < maze_size_y; j++) {
X		if (maze[maze_size_x - 1][j] & Wallright)
X			line(screen, addpt(screen->r.min,
X			    Pt(Border_x + grid_width * maze_size_x - 1,
X				Border_y + grid_height * j)),
X			    addpt(screen->r.min,
X			    Pt(Border_x + grid_width * maze_size_x - 1,
X				Border_y + grid_height * (j + 1) - 1)),
X			    Endsquare, Endsquare, 0, display->white, ZP);
X		if (maze[0][j] & Wallleft)
X			line(screen, addpt(screen->r.min,
X			    Pt(Border_x, Border_y + grid_height * j)),
X			    addpt(screen->r.min,
X			    Pt(Border_x, Border_y + grid_height * (j + 1) - 1)),
X			    Endsquare, Endsquare, 0, display->white, ZP);
X	}

X	if (logo_x != -1) {
X		unsigned w = 48, h = 48;
X		Point p;
X		/* round up to grid size */
X		int ww = ((Logowidth  / grid_width) + 1)  *grid_width;
X		int hh = ((Logoheight / grid_height) + 1) *grid_height;

X		p = addpt(screen->r.min,
X			Pt(Border_x + 1 + grid_width *logo_x + ((ww - w)/2),
X			   Border_y + 1 + grid_height*logo_y + ((hh - h)/2)));

X		draw(screen, Rpt(p, addpt(p, Pt(48, 48))), glenda, nil, ZP);
X		/* draw(screen, screen->r, glenda, nil, ZP); */
X	}
X	draw_solid_square(start_x, start_y, Walltop >> start_dir, liveColor);
X	draw_solid_square(end_x, end_y, Walltop >> end_dir, liveColor);
X}

X/* was a profiling hot-spot; called a lot */
static void
draw_wall(int i, int j, int dir)                /* draw a single wall */
X{
X	int drawline = 1, gridhigh = grid_height, gridwide = grid_width;
X	Point scrmin = screen->r.min, p1, p2;

X	switch (dir) {
X	case 0:
X		p1 = Pt(Border_x + gridwide*i, Border_y + gridhigh*j);
X		p2 = Pt(Border_x + gridwide*(i+1), Border_y + gridhigh*j);
X		break;
X	case 1:
X		p1 = Pt(Border_x + gridwide*(i+1), Border_y + gridhigh*j);
X		p2 = Pt(Border_x + gridwide*(i+1), Border_y + gridhigh*(j+1));
X		break;
X	case 2:
X		p1 = Pt(Border_x + gridwide*i, Border_y + gridhigh*(j+1));
X		p2 = Pt(Border_x + gridwide*(i+1), Border_y + gridhigh*(j+1));
X		break;
X	case 3:
X		p1 = Pt(Border_x + gridwide*i, Border_y + gridhigh*j);
X		p2 = Pt(Border_x + gridwide*i, Border_y + gridhigh*(j+1));
X		break;
X	default:
X		drawline = 0;
X		break;
X	}
X	if (drawline)
X		line(screen, addpt(scrmin, p1), addpt(scrmin, p2),
X			Endsquare, Endsquare, 0, display->white, ZP);
X}

X/* Actually build a wall. */
static void
build_wall(int i, int j, int dir)
X{
X	draw_wall(i, j, dir);		/* Draw it on the screen. */
X	/* Put it in the maze. */
X	switch (dir) {
X	case 0:
X		maze[i][j] |= Walltop;
X		if (j > 0)
X			maze[i][j-1] |= Wallbottom;
X		break;
X	case 1:
X		maze[i][j] |= Wallright;
X		if (i < maze_size_x - 1)
X			maze[i+1][j] |= Wallleft;
X		break;
X	case 2:
X		maze[i][j] |= Wallbottom;
X		if (j < maze_size_y - 1)
X			maze[i][j+1] |= Walltop;
X		break;
X	case 3:
X		maze[i][j] |= Wallleft;
X		if (i > 0)
X			maze[i-1][j] |= Wallright;
X		break;
X	}
X}

X/* draw a solid square in a square */
static void
draw_solid_square(int i, int j, int dir, Image *c)
X{
X	int dodraw = 1, gridhigh = grid_height, gridwide = grid_width;
X	int lbw = bw;			/* local copy */
X	int twobw = lbw << 1;
X	int bxgrwi = Border_x + gridwide*i, bygrhj = Border_y + gridhigh*j;
X	Rectangle r;
X	Point p, scrmin = screen->r.min;

X	switch (dir) {
X	case Walltop:
X		p = addpt(scrmin, Pt(bxgrwi + lbw, bygrhj - lbw));
X		r = Rpt(p, addpt(p, Pt(gridwide - twobw, gridhigh)));
X		break;
X	case Wallright:
X		p = addpt(scrmin, Pt(bxgrwi + lbw,  bygrhj + lbw));
X		r = Rpt(p, addpt(p, Pt(gridwide, gridhigh - twobw)));
X		break;
X	case Wallbottom:
X		p = addpt(scrmin, Pt(bxgrwi + lbw, bygrhj + lbw));
X		r = Rpt(p, addpt(p, Pt(gridwide - twobw, gridhigh)));
X		break;
X	case Wallleft:
X		p = addpt(scrmin, Pt(bxgrwi - lbw, bygrhj + lbw));
X		r = Rpt(p, addpt(p, Pt(gridwide, gridhigh - twobw)));
X		break;
X	default:
X		dodraw = 0;
X		break;
X	}
X	if (dodraw)
X		draw(screen, r, c, nil, ZP);
X}

int
longdeadend_p(int x1, int y1, int x2, int y2, int endwall)
X{
X	int dx = x2 - x1, dy = y2 - y1;
X	int sidewalls;

X	assert(dx != 0 || dy != 0);
X	sidewalls = endwall | endwall >> 2 | endwall << 2;
X	sidewalls = ~sidewalls & Wallany;
X	while ((maze[x2][y2] & Wallany) == sidewalls) {
X		x2 += dx;
X		y2 += dy;
X	}

X	if ((maze[x2][y2] & Wallany) == (sidewalls | endwall)) {
X		endwall = (endwall >> 2 | endwall << 2) & Wallany;
X		while (x1 != x2 || y1 != y2) {
X			x1 += dx;
X			y1 += dy;
X			draw_solid_square(x1, y1, endwall, skipColor);
X			maze[x1][y1] |= Solvervisit;
X		}
X		return 1;
X	} else
X		return 0;
X}

static void
drawnowall(int x, int y)
X{
X	int lbw = bw, gridhigh = grid_height, gridwide = grid_width;
X								/* local copy */
X	int twobw = lbw << 1;
X	Point p;
X	Rectangle r;

X	/* fill the rectangle */
X	p = addpt(screen->r.min,
X		Pt(Border_x + lbw + gridwide*x, Border_y + lbw + gridhigh*y));
X	r = Rpt(p, addpt(p, Pt(gridwide - twobw, gridhigh - twobw)));
X	draw(screen, r, surroundColor, nil, ZP);
X}

X/*
X * Find all not Solvervisit squares bordering Notdead squares
X * and mark them Notdead also.  Repeat until no more such squares.
X * a major profiling hotspot.
X */
static void
marknotdead(void)
X{
X	int x, y, flipped;
X	int xsz = maze_size_x, ysz = maze_size_y; 	/* local copies */
X	ushort *sqp;

X	maze[start_x][start_y] |= Notdead;
X	do {
X		flipped = 0;
X		for (x = 0; x < xsz; x++) {
X			sqp = maze[x];
X			for (y = 0; y < ysz; y++, sqp++)
X				if (!(*sqp & (Solvervisit|Notdead)) &&
X				     (y > 0 && (sqp[-1] & Notdead) ||
X				      x > 0 && (maze[x-1][y] & Notdead))) {
X					flipped = 1;
X					*sqp |= Notdead;
X				}
X		}
X		for (x = xsz - 1; x >= 0; x--) {
X			sqp = &maze[x][ysz];
X			for (y = ysz - 1; sqp--, y >= 0; y--) {
X				if (!(*sqp & (Solvervisit|Notdead)) &&
X				     (y < ysz-1 && (sqp[1]&Notdead) ||
X				      x < xsz-1 && (maze[x+1][y]&Notdead))) {
X					flipped = 1;
X					*sqp |= Notdead;
X				}
X			}
X		}
X	} while (flipped);
X}

X#define ifnowalldraw(x, y, sq, wallbit) \
X	if (!((sq) & (wallbit))) \
X		draw_solid_square(x, y, wallbit, surroundColor);
X#define drawsq(x, y, sq) { \
X	if (!((sq) & Wallany)) \
X		drawnowall(x, y); \
X	else { \
X		ifnowalldraw(x, y, sq, Wallleft); \
X		ifnowalldraw(x, y, sq, Wallright); \
X		ifnowalldraw(x, y, sq, Walltop); \
X		ifnowalldraw(x, y, sq, Wallbottom); \
X	} \
X}

X/* a profiling hotspot. */
static void
markdeadredraw(void)
X{
X	int x, y;
X	int xsz = maze_size_x, ysz = maze_size_y; 	/* local copies */
X	int gridhigh = grid_height, gridwide = grid_width;	/* " */
X	int logox = logo_x, logoy = logo_y;			/* " */
X	int logoxbound = logox + Logowidth/gridwide;
X	int logoybound = logoy + Logoheight/gridhigh;
X	ushort sq;
X	ushort *sqp;

X	for (x = 0; x < xsz; x++) {
X		sqp = maze[x];
X		for (y = 0; y < ysz; y++, sqp++) {
X			sq = *sqp;
X			if (sq & Notdead)
X				*sqp &= ~Notdead;
X			else if (!(sq & Solvervisit)) {
X				sq |= Solvervisit;
X				*sqp = sq;
X				if (x < logox || x > logoxbound ||
X				    y < logoy || y > logoybound)
X					drawsq(x, y, sq);
X			}
X		}
X	}
X}

X/*
X * Find all dead regions -- areas from which the goal cannot be reached --
X * and mark them visited.
X */
static void
find_dead_regions(void)
X{
X	marknotdead();
X	markdeadredraw();
X	flushimage(display, 1);		/* show new dead regions */
X}

static void
chkmouse(void)
X{
X	int cnt = 20;

X	while (cnt-- > 0 && ecanmouse()) {
X		Mouse m = emouse();

X		if ((m.buttons & 4) && emenuhit(3, &m, &menu) == 0)
X			exits(0);
X	}
X}

enum { Mspollms = 100, };	/* ms. between mouse polls */

static void
pollmouse(void)
X{
X	uvlong nowns;
X	static uvlong nextpoll;

X	nowns = nsec();
X	if (nowns >= nextpoll) {
X		flushimage(display, 1);		/* show recent changes */
X		chkmouse();
X		nextpoll = nowns + Mspollms * 1000000;
X	}
X}

X/* backtracking state */
typedef struct {
X	int	depth;		/* of `recursion' */
X	Move	*mv;
X	int	backing;	/* flag: backtracking in progress */
X	int	from;
X} Backtrack;

static Move *
backtrack(Backtrack *btp)
X{
X	int from;
X	Move *mv = btp->mv;

X	if (btp->depth <= 0) {		/* backtracked to the start? */
X		print("Insoluble maze.\n");
X		return nil;
X	}

X	if (!btp->backing && !ignorant_p)
X		find_dead_regions();
X	btp->backing = 1;
X	assert(mv != path);
X	from = (mv-1)->dir;
X	btp->from = ((from << 2) & Wallany) | ((from >> 2) & Wallany);

X	draw_solid_square(mv->x, mv->y, btp->from, deadColor);
X	btp->mv = path + --btp->depth;
X	return btp->mv;
X}

X/* doing the backtracking via recursion would be cleaner. */
X/* a profiling hotspot */
static void
solve_maze(void)			/* solve it with graphical feedback */
X{
X	int x, y, ways;
X	unsigned dir;
X	Backtrack btstate;
X	Backtrack *btp = &btstate;
X	Move *mv;			/* cached copy of btp->mv */

X	/* plug up the surrounding wall */
X	maze[end_x][end_y] |= Walltop >> end_dir;

X	/* initialize search path */
X	btp->depth = btp->backing = btp->from = 0;
X	btp->mv = mv = path;
X	setmove(mv, end_x, end_y, 0);
X	mv->ways = 0;
X	maze[end_x][end_y] |= Solvervisit;
X	while (!(maze[mv->x][mv->y] & Startsq) && !restart) {
X		if (solve_delay) {
X			flushimage(display, 1);	/* show latest square */
X			sleep(solve_delay);
X		}
X		pollmouse();

X		if (mv->dir)
X			ways = mv->ways;
X		else {
X			ways = 0;
X			/*
X			 * First visit this square.
X			 * Which adjacent squares are open?
X			 */
X			for (dir = Walltop; dir & Wallany; dir >>= 1) {
X				if (maze[mv->x][mv->y] & dir)
X					continue;

X				x = mv->x - !!(dir&Wallleft) + !!(dir&Wallright);
X				y = mv->y - !!(dir&Walltop) + !!(dir&Wallbottom);
X				if (maze[x][y] & Solvervisit)
X					continue;

X				btp->from = ((dir << 2) & Wallany) |
X					    ((dir >> 2) & Wallany);
X				/* don't enter obvious dead ends */
X				pollmouse();
X				if (((maze[x][y] & Wallany) | btp->from) !=
X				    Wallany) {
X					if (!longdeadend_p(mv->x, mv->y, x, y,
X					    dir))
X						ways |= dir;
X				} else {
X					draw_solid_square(x, y, btp->from,
X						skipColor);
X					maze[x][y] |= Solvervisit;
X				}
X			}
X		}
X		/* ways now has a bitmask of open paths. */

X		if (!ways) {
X			mv = backtrack(btp);
X			if (mv == nil)
X				return;
X			continue;
X		}

X		if (!ignorant_p) {
X			x = mv->x - start_x;
X			y = mv->y - start_y;

X			/* choice one */
X			if (abs(y) <= abs(x))
X				dir = (x > 0)? Wallleft: Wallright;
X			else
X				dir = (y > 0)? Walltop: Wallbottom;

X			if (!(dir & ways))
X				/* choice two */
X				switch (dir) {
X				case Walltop:
X				case Wallbottom:
X					dir = (x > 0)? Wallleft: Wallright;
X					break;
X				case Wallleft:
X				case Wallright:
X					dir = (y > 0)? Walltop: Wallbottom;
X					break;
X				}
X			if (!(dir & ways))
X				dir = ((dir << 2) & Wallany) |
X				      ((dir >> 2) & Wallany);/* choice three */
X			if (!(dir & ways))
X				dir = ways;		/* choice four */
X		} else {
X			if (ways & Walltop)
X				dir = Walltop;
X			else if (ways & Wallleft)
X				dir = Wallleft;
X			else if (ways & Wallbottom)
X				dir = Wallbottom;
X			else if (ways & Wallright)
X				dir = Wallright;
X			else
X				dir = 0;
X		}

X		if (!dir) {
X			mv = backtrack(btp);
X			if (mv == nil)
X				return;
X			continue;
X		}

X		btp->backing = 0;
X		ways &= ~dir;		/* tried this one */

X		x = mv->x - !!(dir & Wallleft) + !!(dir & Wallright);
X		y = mv->y - !!(dir & Walltop) + !!(dir & Wallbottom);

X		/* advance in direction dir */
X		mv->dir = dir;
X		assert(mv->dir == dir);
X		mv->ways = ways;
X		assert(mv->ways == ways);
X		draw_solid_square(mv->x, mv->y, dir, liveColor);

X		btp->mv = mv = path + ++btp->depth;
X		setmove(mv, x, y, 0);
X		mv->ways = 0;
X		maze[x][y] |= Solvervisit;
X	}
X}

static void
newmaze(void)
X{
X	exit_sets();
X	restart = 0;
X	sqnum = 0;
X	cur_sq_x = cur_sq_y = 0;
X	start_x = start_y = start_dir = end_x = end_y = end_dir = 0;
X	set_maze_sizes(Dx(screen->r), Dy(screen->r));

X	draw(screen, screen->r, display->black, nil, ZP);
X	sync_p = (random() % 10) == 0;
X}

X/*
X *  jmr additions for Jamie Zawinski's <jwz@jwz.org> screensaver stuff,
X *  note that the code above this has probably been hacked about in some
X *  arbitrary way.
X */
void
outerloop(void)
X{
X	int size, generator = -1, this_gen;
X	ushort **stmaze = nil;

X	max_length = 5;
X	bridge_p = ignorant_p = 0;
X	if (gridsize)
X		size = gridsize;
X	else
X		size = 5 + random()%20;

X	grid_width = grid_height = size;
X	bw = (size > 6? 3: (size-1)/2);

X	restart = 0;
X	sync_p = (random() % 10) == 0;

X	for (; ;) {			/* primary execution loop [rhess] */
X		pollmouse();
X		if (restart) {
X			restart = stop = 0;
X			state = 1;
X		} else if (stop)
X			continue;

X		if (state > 1)
X			assert(stmaze == maze);
X		switch (state++) {
X		case 1:
X			newmaze();
X			stmaze = maze;
X			initialize_maze();
X			break;
X		case 2:
X			draw(screen, screen->r, display->black, nil, ZP);
X			draw_maze_border();
X			break;
X		case 3:
X			this_gen = generator;
X			if (this_gen < 0 || this_gen > 2)
X				this_gen = random() % 3;
X			switch (this_gen) {
X			case 0:
X				create_maze();
X				break;
X			case 1:
X				alt_create_maze();
X				break;
X			case 2:
X				set_create_maze();
X				break;
X			}
X			flushimage(display, 1);		/* draw initial maze */
X			break;
X		case 4:
X			sleep(pre_solve_delay);
X			break;
X		case 5:
X			solve_maze();
X			break;
X		case 6:
X			flushimage(display, 1);		/* show final maze */
X			sleep(post_solve_delay);

X			state = 1;
X			break;
X		default:
X			abort();
X			break;
X		}
X		assert(maze == stmaze);
X	}
X}

void
eresized(int new)
X{
X	if (new && getwindow(display, Refnone) < 0)
X		sysfatal("can't reattach to window");
X	restart = 1;
X}

static void
usage(void)
X{
X	fprint(2, "usage: %s [-f] [-g pixels]\n", argv0);
X	exits("usage");
X}

void
main(int argc, char **argv)
X{
X	int fd;
X	Rectangle unit = Rect(0, 0, 1, 1);

X//	mainmem->flags |= POOL_ANTAGONISM;

X	if (!Debug) {
X		solve_delay = 5;
X		pre_solve_delay = 2000;
X		post_solve_delay = 4000;
X	}
X	ARGBEGIN{
X	case 'f':			/* full speed */
X		solve_delay = pre_solve_delay = post_solve_delay = 0;
X		break;
X	case 'g':			/* grid height & width in pixels */
X		gridsize = atoi(EARGF(usage()));
X		break;
X	default:
X		usage();
X	}ARGEND;
X	srand(time(0));

X	if (initdraw(nil, nil, "maze") < 0)
X		sysfatal("initdraw failed: %r");

X	liveColor = allocimage(display, unit, screen->chan, 1, DGreen);
X	deadColor = allocimage(display, unit, screen->chan, 1, DRed);
X	skipColor = allocimage(display, unit, screen->chan, 1, DMagenta);
X	surroundColor = allocimage(display, unit, screen->chan, 1, DPaleblue);
X	if (liveColor == nil || deadColor == nil || skipColor == nil ||
X	    surroundColor == nil)
X		sysfatal("out of memory");

X	fd = open("/lib/face/48x48x4/g/glenda.1", OREAD);
X	if (fd < 0)
X		sysfatal("cannot open /lib/face/48x48x4/g/glenda.1: %r");

X	glenda = readimage(display, fd, 0);
X	if (glenda == nil)
X		sysfatal("cannot load glenda's image: %r");

X	draw(screen, screen->r, display->black, nil, ZP);

X	einit(Emouse);
X	eresized(0);
X	outerloop();
X}
!
echo maze.novel
sed 's/^X//' >maze.novel <<'!'
X/* the theory, the first, by Anne Elk (Miss), ahem. */

X/*
X * [ maze ] ...
X *
X * modified:  [ 1-04-00 ]  Johannes Keukelaar <johannes@nada.kth.se>
X *              Added -ignorant option (not the default) to remove knowlege
X *              of the direction in which the exit lies.
X *
X * modified:  [ 6-28-98 ]  Zack Weinberg <zack@rabi.phys.columbia.edu>
X *
X *              Made the maze-solver somewhat more intelligent.  There are
X *              three optimizations:
X *
X *              - Straight-line lookahead: the solver does not enter dead-end
X *                corridors.  This is a win with all maze generators.
X *
X *              - First order direction choice: the solver knows where the
X *                exit is in relation to itself, and will try paths leading in
X *                that direction first. This is a major win on maze generator 1
X *                which tends to offer direct routes to the exit.
X *
X *              - Dead region elimination: the solver already has a map of
X *                all squares visited.  Whenever it starts to backtrack, it
X *                consults this map and marks off all squares that cannot be
X *                reached from the exit without crossing a square already
X *                visited.  Those squares can never contribute to the path to
X *                the exit, so it doesn't bother checking them.  This helps a
X *                lot with maze generator 2 and somewhat less with generator 1.
X *
X *              Further improvements would require knowledge of the wall map
X *              as well as the position of the exit and the squares visited.
X *              I would consider that to be cheating.  Generator 0 makes
X *              mazes which are remarkably difficult to solve mechanically --
X *              even with these optimizations the solver generally must visit
X *              at least two-thirds of the squares.  This is partially
X *              because generator 0's mazes have longer paths to the exit.
X *
X * modified:  [ 4-10-97 ]  Johannes Keukelaar <johannes@nada.kth.se>
X *              Added multiple maze creators. Robustified solver.
X *              Added bridge option.
X * modified:  [ 8-11-95 ] Ed James <james@mml.mmc.com>
X *              added fill of dead-end box to solve_maze while loop.
X * modified:  [ 3-7-93 ]  Jamie Zawinski <jwz@jwz.org>
X *		added the XRoger logo, cleaned up resources, made
X *		grid size a parameter.
X * modified:  [ 3-3-93 ]  Jim Randell <jmr@mddjmr.fc.hp.com>
X *		Added the colour stuff and integrated it with jwz's
X *		screenhack stuff.  There's still some work that could
X *		be done on this, particularly allowing a resource to
X *		specify how big the squares are.
X * modified:  [ 10-4-88 ]  Richard Hess    ...!uunet!cimshop!rhess
X *              [ Revised primary execution loop within main()...
X *              [ Extended X event handler, check_events()...
X * modified:  [ 1-29-88 ]  Dave Lemke      lemke@sun.com
X *              [ Hacked for X11...
X *              [  Note the word "hacked" -- this is extremely ugly, but at
X *              [   least it does the job.  NOT a good programming example
X *              [   for X.
X * original:  [ 6/21/85 ]  Martin Weiss    Sun Microsystems  [ SunView ]
X *
X Copyright 1988 by Sun Microsystems, Inc. Mountain View, CA.

X All Rights Reserved

X Permission to use, copy, modify, and distribute this software and its
X documentation for any purpose and without fee is hereby granted,
X provided that the above copyright notice appear in all copies and that
X both that copyright notice and this permission notice appear in
X supporting documentation, and that the names of Sun or MIT not be
X used in advertising or publicity pertaining to distribution of the
X software without specific prior written permission. Sun and M.I.T.
X make no representations about the suitability of this software for
X any purpose. It is provided "as is" without any express or implied warranty.

X SUN DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
X ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
X PURPOSE. IN NO EVENT SHALL SUN BE LIABLE FOR ANY SPECIAL, INDIRECT
X OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS
X OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
X OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE
X OR PERFORMANCE OF THIS SOFTWARE.
X */
!