# 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 <draw.h>
X#include <event.h>

enum {
X	Debug = 0,

X	MAX_MAZE_SIZE_X	= 500,
X	MAX_MAZE_SIZE_Y	= 500,

X	MOVE_LIST_SIZE  = (MAX_MAZE_SIZE_X * MAX_MAZE_SIZE_Y),

X	/* these must fit in a ushort */
X	WALL_LEFT	= 1<<0,
X	WALL_BOTTOM	= 1<<1,
X	WALL_RIGHT	= 1<<2,
X	WALL_TOP	= 1<<3,
X	WALL_ANY = (WALL_TOP|WALL_RIGHT|WALL_BOTTOM|WALL_LEFT),

X	DOOR_OUT_LEFT	= 1<<4,
X	DOOR_OUT_BOTTOM	= 1<<5,
X	DOOR_OUT_RIGHT	= 1<<6,
X	DOOR_OUT_TOP	= 1<<7,

X	DOOR_IN_LEFT	= 1<<8,
X	DOOR_IN_BOTTOM	= 1<<9,
X	DOOR_IN_RIGHT	= 1<<10,
X	DOOR_IN_TOP	= 1<<11,
X	DOOR_IN_ANY = (DOOR_IN_TOP|DOOR_IN_RIGHT|DOOR_IN_BOTTOM|DOOR_IN_LEFT),

X	END_SQUARE	= 1<<12,
X	START_SQUARE	= 1<<13,
X	SOLVER_VISIT    = 1<<14,
X	NOT_DEAD	= 1<<15,

X	Border_x        = 0,
X	Border_y        = 0,

X	MAXRAND = (1UL<<31)-1,
X	RAND_MAX = MAXRAND,

X	Logowidth = 48,
X	Logoheight = Logowidth,
X};


X#define random rand
X#define	get_random(x)	(rand() % (x))
X#define Pnt(x, y)	(Point){(x), (y)}

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

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

X/* TODO: UGH! can't we dynamically allocate these at the right size? */
static ushort maze[MAX_MAZE_SIZE_X][MAX_MAZE_SIZE_Y];
typedef struct {
X	uchar	x;
X	uchar	y;
X	uchar	dir;
X	uchar	ways;
X} Move;
static Move move_list[MOVE_LIST_SIZE], save_path[MOVE_LIST_SIZE],
X	path[MOVE_LIST_SIZE];

static int solve_delay, pre_solve_delay, post_solve_delay;
static int logo_x, logo_y;
static int maze_size_x, maze_size_y;
static int sqnum, cur_sq_x, cur_sq_y, path_length;
static int start_x, start_y, start_dir, end_x, end_y, end_dir;
static int grid_width, grid_height;
static int bw;
static int x = 0, y = 0, restart = 0, stop = 0, state = 1, max_length;
static int sync_p, bridge_p, ignorant_p;
static int nodrawmaze = 0;

static void
set_maze_sizes (int width, int height)
X{
X	maze_size_x = width / grid_width;
X	maze_size_y = height / grid_height;
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	memset(maze, 0, sizeof maze);
X	for ( i = 0; i < maze_size_x; i++) {
X		maze[i][0] |= WALL_TOP;
X		maze[i][maze_size_y-1] |= WALL_BOTTOM;
X	}
X	for ( j = 0; j < maze_size_y; j++) {
X		maze[maze_size_x-1][j] |= WALL_RIGHT;
X		maze[0][j] |= WALL_LEFT;
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] |= START_SQUARE | ( DOOR_IN_TOP >> wall );
X	maze[i][j] &= ~( WALL_TOP >> wall );
X	cur_sq_x = i;
X	cur_sq_y = j;
X	start_x = i;
X	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] |= END_SQUARE | ( DOOR_OUT_TOP >> wall );
X	maze[i][j] &= ~( WALL_TOP >> 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] |= DOOR_IN_TOP;
X	} else
X		logo_y = logo_x = -1;
X}

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

static void join_sets(int, int);

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

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

X	if (sets)
X		free(sets);
X	sets = (int *)malloc(maze_size_x * maze_size_y * sizeof(int));
X	if (!sets)
X		abort();
X	for (i = 0; i < maze_size_x * maze_size_y; i++)
X		sets[i] = i;

X	if (hedges)
X		free(hedges);
X	hedges = (int *)malloc(maze_size_x * maze_size_y * 2 * sizeof(int));
X	if (!hedges)
X		abort();
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				/* I should check for the bridge here, except that I join the
X            			 * 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, 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 + 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(num1, num2)
int num1, 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	if (hedges)
X		free(hedges);
X	hedges = 0;
X	if (sets)
X		free(sets);
X	sets = 0;
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			/* Don't join the sets. */
X			build_wall(x, y, dir);
X	}
X	exit_sets();			/* Free some memory. */
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 = (char *)calloc(size, 1);
X	if (!corners)
X		return;

X	/* Set up the indexing array. */
X	c_idx = (int *)malloc(sizeof(int) * size);
X	if (!c_idx) {
X		free(corners);
X		return;
X	}
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/* 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] &= ~DOOR_IN_TOP;
X		else
X			for (i = logo_y; i < logo_y + logoh; i++)
X				maze[bridge_c][i] &= ~DOOR_IN_TOP;
X	}

X	for (; ; ) {
X		move_list[sqnum].x = cur_sq_x;
X		move_list[sqnum].y = cur_sq_y;
X		move_list[sqnum].dir = newdoor;
X		while ((newdoor = choose_door()) == -1)	/* pick a door */
X			if (backup() == -1)	/* no more doors ... backup */
X				return;	

X		/* mark the out door */
X		maze[cur_sq_x][cur_sq_y] |= DOOR_OUT_TOP >> 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		sqnum++;

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

X		/* if end square set path length and save path */
X		if (maze[cur_sq_x][cur_sq_y] & END_SQUARE) {
X			path_length = sqnum;
X			for (i = 0; i < path_length; i++) {
X				save_path[i].x = move_list[i].x;
X				save_path[i].y = move_list[i].y;
X				save_path[i].dir = move_list[i].dir;
X			}
X		}
X	}
X}

static int
choose_door(void)				/* pick a new path */
X{
X	int candidate = 0, num_candidates = 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 & (DOOR_IN_TOP|DOOR_OUT_TOP|WALL_TOP)))
X		if (maze[cursqx][cursqy - 1] & DOOR_IN_ANY) {
X			*sqp |= WALL_TOP;
X			maze[cursqx][cursqy - 1] |= WALL_BOTTOM;
X			draw_wall(cursqx, cursqy, candidate);
X		} else
X			candidates[num_candidates++] = candidate;
X	candidate++;

X	/* right wall */
X	if (!(*sqp & (DOOR_IN_RIGHT|DOOR_OUT_RIGHT|WALL_RIGHT)))
X		if (maze[cursqx + 1][cursqy] & DOOR_IN_ANY) {
X			*sqp |= WALL_RIGHT;
X			maze[cursqx + 1][cursqy] |= WALL_LEFT;
X			draw_wall(cursqx, cursqy, candidate);
X		} else
X			candidates[num_candidates++] = candidate;
X	candidate++;

X	/* bottom wall */
X	if (!(*sqp & (DOOR_IN_BOTTOM|DOOR_OUT_BOTTOM|WALL_BOTTOM)))
X		if (maze[cursqx][cursqy + 1] & DOOR_IN_ANY) {
X			*sqp |= WALL_BOTTOM;
X			maze[cursqx][cursqy + 1] |= WALL_TOP;
X			draw_wall(cursqx, cursqy, candidate);
X		} else
X			candidates[num_candidates++] = candidate;
X	candidate++;

X	/* left wall */
X	if (!(*sqp & (DOOR_IN_LEFT|DOOR_OUT_LEFT|WALL_LEFT)))
X		if (maze[cursqx - 1][cursqy] & DOOR_IN_ANY) {
X			*sqp |= WALL_LEFT;
X			maze[cursqx - 1][cursqy] |= WALL_RIGHT;
X			draw_wall(cursqx, cursqy, candidate);
X		} else
X			candidates[num_candidates++] = candidate;
X	candidate++;
X	USED(candidate);

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

X}

static int
backup(void)                                          /* back up a move */
X{
X	sqnum--;
X	cur_sq_x = move_list[sqnum].x;
X	cur_sq_y = move_list[sqnum].y;
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] & WALL_TOP)
X			line(screen, addpt(screen->r.min,
X				Pnt(Border_x + grid_width * i, Border_y)),
X			    addpt(screen->r.min,
X				Pnt(Border_x + grid_width*(i+1) - 1, Border_y)),
X			    Endsquare, Endsquare, 0, display->white, ZP);
X		if ((maze[i][maze_size_y - 1] & WALL_BOTTOM))
X			line(screen, addpt(screen->r.min,
X			    Pnt(Border_x + grid_width * i,
X				Border_y + grid_height * (maze_size_y) - 1)),
X			    addpt(screen->r.min,
X			    Pnt(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] & WALL_RIGHT)
X			line(screen, addpt(screen->r.min,
X			    Pnt(Border_x + grid_width * maze_size_x - 1,
X				Border_y + grid_height * j)),
X			    addpt(screen->r.min,
X			    Pnt(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] & WALL_LEFT)
X			line(screen, addpt(screen->r.min,
X			    Pnt(Border_x, Border_y + grid_height * j)),
X			    addpt(screen->r.min,
X			    Pnt(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			Pnt(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, Pnt(48, 48))), glenda, nil, ZP);
X		/* draw(screen, screen->r, glenda, nil, ZP); */
X	}
X	draw_solid_square (start_x, start_y, WALL_TOP >> start_dir, liveColor);
X	draw_solid_square (end_x, end_y, WALL_TOP >> 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 gridhigh = grid_height, gridwide = grid_width;
X	Point scrmin = screen->r.min, p1, p2;

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

X/* Actually build a wall. */
static void
build_wall(i, j, dir)
int i, j, 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] |= WALL_TOP;
X		if (j > 0)
X			maze[i][j-1] |= WALL_BOTTOM;
X		break;
X	case 1:
X		maze[i][j] |= WALL_RIGHT;
X		if (i < maze_size_x - 1)
X			maze[i+1][j] |= WALL_LEFT;
X		break;
X	case 2:
X		maze[i][j] |= WALL_BOTTOM;
X		if (j < maze_size_y - 1)
X			maze[i][j+1] |= WALL_TOP;
X		break;
X	case 3:
X		maze[i][j] |= WALL_LEFT;
X		if (i > 0)
X			maze[i-1][j] |= WALL_RIGHT;
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 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 WALL_TOP:
X		p = addpt(scrmin, Pnt(bxgrwi + lbw, bygrhj - lbw));
X		r = Rpt(p, addpt(p, Pnt(gridwide - twobw, gridhigh)));
X		break;
X	case WALL_RIGHT:
X		p = addpt(scrmin, Pnt(bxgrwi + lbw,  bygrhj + lbw));
X		r = Rpt(p, addpt(p, Pnt(gridwide, gridhigh - twobw)));
X		break;
X	case WALL_BOTTOM:
X		p = addpt(scrmin, Pnt(bxgrwi + lbw, bygrhj + lbw));
X		r = Rpt(p, addpt(p, Pnt(gridwide - twobw, gridhigh)));
X		break;
X	case WALL_LEFT:
X		p = addpt(scrmin, Pnt(bxgrwi - lbw, bygrhj + lbw));
X		r = Rpt(p, addpt(p, Pnt(gridwide, gridhigh - twobw)));
X		break;
X	default:
X		if (!nodrawmaze)
X			flushimage(display, 1);
X		return;
X	}
X	draw(screen, r, c, nil, ZP);
X	if (!nodrawmaze)
X		flushimage(display, 1);
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	sidewalls = endwall | (endwall >> 2 | endwall << 2);
X	sidewalls = ~sidewalls & WALL_ANY;
X	while ((maze[x2][y2] & WALL_ANY) == sidewalls) {
X		x2 += dx;
X		y2 += dy;
X	}

X	if ((maze[x2][y2] & WALL_ANY) == (sidewalls | endwall)) {
X		endwall = (endwall >> 2 | endwall << 2) & WALL_ANY;
X		while (x1 != x2 || y1 != y2) {
X			x1 += dx;
X			y1 += dy;
X			draw_solid_square(x1, y1, endwall, skipColor);
X			maze[x1][y1] |= SOLVER_VISIT;
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		Pnt(Border_x + lbw + gridwide*x, Border_y + lbw + gridhigh*y));
X	r = Rpt(p, addpt(p, Pnt(gridwide - twobw, gridhigh - twobw)));
X	draw(screen, r, surroundColor, nil, ZP);
X}

X/*
X * Find all not SOLVER_VISIT squares bordering NOT_DEAD squares
X * and mark them NOT_DEAD 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] |= NOT_DEAD;
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 & (SOLVER_VISIT|NOT_DEAD)) &&
X				     (y > 0 && (sqp[-1] & NOT_DEAD) ||
X				      x > 0 && (maze[x-1][y] & NOT_DEAD))) {
X					flipped = 1;
X					*sqp |= NOT_DEAD;
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 & (SOLVER_VISIT|NOT_DEAD)) &&
X				     (y < ysz-1 && (sqp[1]&NOT_DEAD) ||
X				      x < xsz-1 && (maze[x+1][y]&NOT_DEAD))) {
X					flipped = 1;
X					*sqp |= NOT_DEAD;
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) & WALL_ANY)) \
X		drawnowall(x, y); \
X	else { \
X		ifnowalldraw(x, y, sq, WALL_LEFT); \
X		ifnowalldraw(x, y, sq, WALL_RIGHT); \
X		ifnowalldraw(x, y, sq, WALL_TOP); \
X		ifnowalldraw(x, y, sq, WALL_BOTTOM); \
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 & NOT_DEAD)
X				*sqp &= ~NOT_DEAD;
X			else if (!(sq & SOLVER_VISIT)) {
X				sq |= SOLVER_VISIT;
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);
X}

static void
chkmouse(void)
X{
X	if (ecanmouse()) {
X		Mouse m = emouse();

X		if ((m.buttons & 4) && emenuhit(3, &m, &menu) == 0)
X			exits(0);
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	from = (mv-1)->dir;
X	btp->from = ((from << 2) & WALL_ANY) | ((from >> 2) & WALL_ANY);

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] |= (WALL_TOP >> end_dir);

X	/* initialize search path */
X	btp->depth = btp->backing = 0;
X	btp->mv = mv = path;
X	mv->x = end_x;
X	mv->y = end_y;
X	mv->dir = 0;
X	maze[end_x][end_y] |= SOLVER_VISIT;
X	while (!(maze[mv->x][mv->y] & START_SQUARE) && !restart) {
X		if (solve_delay)
X			sleep(solve_delay);
X		chkmouse();
X		if (!mv->dir) {
X			ways = 0;
X			/*
X			 * First visit this square.
X			 * Which adjacent squares are open?
X			 */
X			for (dir = WALL_TOP; dir & WALL_ANY; dir >>= 1) {
X				if (maze[mv->x][mv->y] & dir)
X					continue;

X				y = mv->y - !!(dir&WALL_TOP) + !!(dir&WALL_BOTTOM);
X				x = mv->x + !!(dir&WALL_RIGHT) - !!(dir&WALL_LEFT);
X				if (maze[x][y] & SOLVER_VISIT)
X					continue;

X				btp->from = ((dir << 2) & WALL_ANY) |
X					    ((dir >> 2) & WALL_ANY);
X				/* don't enter obvious dead ends */
X				chkmouse();
X				if (((maze[x][y]&WALL_ANY)|btp->from) !=
X				    WALL_ANY) {
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] |= SOLVER_VISIT;
X				}
X			}
X		} else
X			ways = mv->ways;
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)? WALL_LEFT: WALL_RIGHT;
X			else
X				dir = (y > 0)? WALL_TOP: WALL_BOTTOM;

X			if (!(dir & ways))
X				/* choice two */
X				switch (dir) {
X				case WALL_TOP:
X				case WALL_BOTTOM:
X					dir = (x > 0)? WALL_LEFT: WALL_RIGHT;
X					break;
X				case WALL_LEFT:
X				case WALL_RIGHT:
X					dir = (y > 0)? WALL_TOP: WALL_BOTTOM;
X					break;
X				}
X			if (!(dir & ways))
X				dir = ((dir << 2) & WALL_ANY) |
X				      ((dir >> 2) & WALL_ANY);/* choice three */
X			if (!(dir & ways))
X				dir = ways;		/* choice four */
X		} else {
X			if (ways & WALL_TOP)
X				dir = WALL_TOP;
X			else if (ways & WALL_LEFT)
X				dir = WALL_LEFT;
X			else if (ways & WALL_BOTTOM)
X				dir = WALL_BOTTOM;
X			else if (ways & WALL_RIGHT)
X				dir = WALL_RIGHT;
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		y = mv->y - !!(dir & WALL_TOP) + !!(dir & WALL_BOTTOM);
X		x = mv->x + !!(dir & WALL_RIGHT) - !!(dir & WALL_LEFT);

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

X		btp->mv = mv = path + ++btp->depth;
X		mv->dir = mv->ways = 0;
X		mv->x = x;
X		mv->y = y;
X		maze[x][y] |= SOLVER_VISIT;
X	}
X}

static void
dorestart(void)
X{
X	if (restart) {
X		restart = stop = 0;
X		state = 1;
X		set_maze_sizes (Dx(screen->r), Dy(screen->r));

X		draw(screen, screen->r, display->black, nil, ZP);
X		flushimage(display, 1);
X		sync_p = (random() % 10) == 0;
X	}
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 = 5 + random()%20, root = 0, generator = -1, this_gen;

X	if (!Debug) {
X		solve_delay = 5;
X		pre_solve_delay = 2000;
X		post_solve_delay = 4000;
X	}
X	max_length = 5;
X	bridge_p = ignorant_p = 0;

X	grid_width = grid_height = size;
X	bw = (size > 6? 3: (size-1)/2);
X	x = y = 0;
X	set_maze_sizes(Dx(screen->r), Dy(screen->r));
X	restart = root;
X	sync_p = (random() % 10) == 0;

X	for (; ; ) {			/* primary execution loop [rhess] */
X		chkmouse();
X		if (restart || stop) {
X			dorestart();
X			continue;
X		}
X		switch (state++) {
X		case 1:
X			initialize_maze();
X			break;
X		case 2:
X			nodrawmaze = 1;		/* draw it in core */
X			draw(screen, screen->r, display->black, nil, ZP);
X			draw_maze_border();
X			if (!nodrawmaze)
X				flushimage(display, 1);
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			nodrawmaze = 0;		/* now push it out */
X			flushimage(display, 1);
X			break;
X		case 4:
X			sleep(pre_solve_delay);
X			break;
X		case 5:
X			solve_maze();
X			break;
X		case 6:
X			sleep(post_solve_delay);
X			state = 1;
X			draw(screen, screen->r, display->black, nil, ZP);
X			break;
X		default:
X			abort();
X			break;
X		}
X		dorestart();
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}

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

X	USED(argc, argv);
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	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	flushimage(display, 1);

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 */
!