# To unbundle, run this file
echo maze.c
sed 's/.//' >maze.c <<'//GO.SYSIN DD maze.c'
-/*
- * maze - generates and solves mazes, with graphical display
- *	ported to Plan 9 by andrey@lanl.gov, August 2002.
- *	see maze.novel for too much information.
- */
-
-#include <u.h>
-#include <libc.h>
-#include <pool.h>
-#include <draw.h>
-#include <event.h>
-
-#define random rand
-#define	get_random(x)	(rand() % (x))
-
-enum {
-	Debug = 0,
-
-	/* these must fit in a ushort */
-	Wallleft	= 1<<0,
-	Wallbottom	= 1<<1,
-	Wallright	= 1<<2,
-	Walltop		= 1<<3,
-	Wallany = Walltop | Wallright | Wallbottom | Wallleft,
-
-	Dooroutleft	= 1<<4,
-	Dooroutbottom	= 1<<5,
-	Dooroutright	= 1<<6,
-	Doorouttop	= 1<<7,
-
-	Doorinleft	= 1<<8,
-	Doorinbottom	= 1<<9,
-	Doorinright	= 1<<10,
-	Doorintop	= 1<<11,
-	Doorinany = Doorintop | Doorinright | Doorinbottom | Doorinleft,
-
-	Endsq		= 1<<12,
-	Startsq		= 1<<13,
-	Solvervisit	= 1<<14,
-	Notdead		= 1<<15,
-
-	Border_x        = 0,
-	Border_y        = 0,
-	Slop		= 10,		/* excess grids for random groping */
-
-	Logowidth = 48,
-	Logoheight = Logowidth,
-};
-enum { Nozero, Zero };
-
-typedef struct {
-	/* on modern displays, we can have > 256 grid squares on an axis */
-	ushort	x;
-	ushort	y;
-	uchar	dir;
-	uchar	ways;
-} Move;
-
-static Image *colors[256];
-static Image *liveColor, *deadColor, *skipColor, *surroundColor;
-static Image *glenda;
-
-static char *buttons[] = {
-	"exit",
-	0
-};
-static Menu menu = {
-	buttons
-};
-
-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;
-
-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;
-static int nodrawmaze = 0;
-
-/* 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)
-{
-	void *p = mallocz(size, clr);
-
-	if (p == nil)
-		sysfatal("out of memory");
-	return p;
-}
-
-static void
-set_maze_sizes(int width, int height)		/* in pixels */
-{
-	int i;
-	long grids;
-	static int first = 1;
-
-	if (!first)
-		for (i = 0; i < maze_size_x + Slop; i++)
-			if (mazealloc[i])
-				free(mazealloc[i] - Slop/2);
-	first = 0;
-	free(mazealloc);
-	free(move_list);
-	free(path);
-
-	maze_size_x = width / grid_width;
-	maze_size_y = height / grid_height;
-	grids = (maze_size_x + Slop) * (maze_size_y + Slop);
-
-	mazealloc = emallocz((maze_size_x + Slop) * sizeof maze[0], Nozero);
-	for (i = 0; i < maze_size_x + Slop; i++) {
-		mazealloc[i] = emallocz((maze_size_y + Slop) *
-			sizeof maze[0][0], Zero);
-		mazealloc[i] += Slop/2;
-	}
-	maze = mazealloc + Slop/2;
-
-	move_list = emallocz(grids * sizeof *move_list, Zero);
-	path = emallocz(grids * sizeof *path, Zero);
-}
-
-static void
-initialize_maze(void)	/* draw the surrounding wall and start/end squares */
-{
-	int i, j, wall;
-	int logow = 1 + Logowidth / grid_width;
-	int logoh = 1 + Logoheight / grid_height;
-
-	for (i = 0; i < maze_size_x; i++) {
-		maze[i][0] |= Walltop;
-		maze[i][maze_size_y-1] |= Wallbottom;
-	}
-	for (j = 0; j < maze_size_y; j++) {
-		maze[maze_size_x-1][j] |= Wallright;
-		maze[0][j] |= Wallleft;
-	}
-
-	/* set start square */
-	wall = get_random(4);
-	switch (wall) {
-	case 0:
-		i = get_random(maze_size_x);
-		j = 0;
-		break;
-	case 1:
-		i = maze_size_x - 1;
-		j = get_random(maze_size_y);
-		break;
-	case 2:
-		i = get_random(maze_size_x);
-		j = maze_size_y - 1;
-		break;
-	case 3:
-		i = 0;
-		j = get_random(maze_size_y);
-		break;
-	}
-	maze[i][j] |= Startsq | (Doorintop >> wall);
-	maze[i][j] &= ~(Walltop >> wall);
-	cur_sq_x = start_x = i;
-	cur_sq_y = start_y = j;
-	start_dir = wall;
-	sqnum = 0;
-
-	/* set end square */
-	wall = (wall + 2) % 4;
-	switch (wall) {
-	case 0:
-		i = get_random(maze_size_x);
-		j = 0;
-		break;
-	case 1:
-		i = maze_size_x - 1;
-		j = get_random(maze_size_y);
-		break;
-	case 2:
-		i = get_random(maze_size_x);
-		j = maze_size_y - 1;
-		break;
-	case 3:
-		i = 0;
-		j = get_random(maze_size_y);
-		break;
-	}
-	maze[i][j] |= Endsq | (Doorouttop >> wall);
-	maze[i][j] &= ~(Walltop >> wall);
-	end_x = i;
-	end_y = j;
-	end_dir = wall;
-
-	/* set logo */
-	if (maze_size_x - logow >= 6 && maze_size_y - logoh >= 6) {
-		/* not closer than 3 grid units from a wall */
-		logo_x = get_random(maze_size_x - logow - 5) + 3;
-		logo_y = get_random(maze_size_y - logoh - 5) + 3;
-		for (i = 0; i < logow; i++)
-			for (j = 0; j < logoh; j++)
-				maze[logo_x + i][logo_y + j] |= Doorintop;
-	} else
-		logo_y = logo_x = -1;
-}
-
-static void
-setmove(Move *mv, int x, int y, int dir)
-{
-	mv->x = x;
-	mv->y = y;
-	mv->dir = dir;
-
-	/* check for overflow */
-	assert(mv->x == x);
-	assert(mv->y == y);
-	assert(mv->dir == dir);
-}
-
-/* Initialise the sets. */
-static void
-init_sets(void)
-{
-	int i, t, r, x, y;
-
-	free(sets);
-	sets = emallocz(maze_size_x * maze_size_y * sizeof(int), Nozero);
-	for (i = 0; i < maze_size_x * maze_size_y; i++)
-		sets[i] = i;
-
-	free(hedges);
-	hedges = emallocz(maze_size_x * maze_size_y * 2 * sizeof(int), Nozero);
-	for (i = 0; i < maze_size_x * maze_size_y * 2; i++)
-		hedges[i] = i;
-
-	/* Mask out outside walls. */
-	for (i = 0; i < maze_size_y; i++)
-		hedges[2*(maze_size_x*i + maze_size_x - 1) + 1] = -1;
-	for (i = 0; i < maze_size_x; i++)
-		hedges[2*((maze_size_y - 1)*maze_size_x + i)] = -1;
-
-	/* Mask out a possible logo. */
-	if (logo_x != -1) {
-		int logow = 1 + Logowidth / grid_width;
-		int logoh = 1 + Logoheight / grid_height;
-		int bridge_dir, bridge_c;
-
-		if (bridge_p && logoh >= 3 && logow >= 3) {
-			bridge_dir = 1 + random() % 2;
-			if (bridge_dir == 1)
-				bridge_c = logo_y + random() % (logoh - 2) + 1;
-			else
-				bridge_c = logo_x + random() % (logow - 2) + 1;
-		} else {
-			bridge_dir = 0;
-			bridge_c = -1;
-		}
-
-		for (x = logo_x; x < logo_x + logow; x++)
-			for (y = logo_y; y < logo_y + logoh; y++) {
-				/*
-				 * I should check for the bridge here,
-				 * except that I join the bridge together below.
-            			 */
-				hedges[2*(x + maze_size_x*y) + 1] = -1;
-				hedges[2*(x + maze_size_x*y)] = -1;
-			}
-		for (x = logo_x; x < logo_x + logow; x++) {
-			if (!(bridge_dir == 2 && x == bridge_c)) {
-				build_wall(x, logo_y, 0);
-				build_wall(x, logo_y + logoh, 0);
-			}
-			hedges[2*(x+maze_size_x*(logo_y-1))] = -1;
-			if (bridge_dir == 1) {
-				build_wall(x, bridge_c, 0);
-				build_wall(x, bridge_c, 2);
-			}
-		}
-		for (y = logo_y; y < logo_y + logoh; y++) {
-			if (!(bridge_dir == 1 && y == bridge_c)) {
-				build_wall(logo_x, y, 3);
-				build_wall(logo_x + logow, y, 3);
-			}
-			hedges[2*(logo_x-1+maze_size_x*y)+1] = -1;
-			if (bridge_dir == 2) {
-				build_wall(bridge_c, y, 1);
-				build_wall(bridge_c, y, 3);
-			}
-		}
-		/* Join the whole bridge together. */
-		if (bridge_p)
-			if (bridge_dir == 1) {
-				x = logo_x - 1;
-				y = bridge_c;
-				for (i = logo_x; i < logo_x + logow + 1; i++)
-					join_sets(x + y * maze_size_x,
-						  i + y * maze_size_x);
-			} else {
-				y = logo_y - 1;
-				x = bridge_c;
-				for (i = logo_y; i < logo_y + logoh + 1; i++)
-					join_sets(x + y * maze_size_x,
-						  x + i * maze_size_x);
-			}
-	}
-
-	for (i = 0; i < maze_size_x * maze_size_y * 2; i++) {
-		r = random() % (maze_size_x * maze_size_y * 2);
-		t = hedges[i];
-		hedges[i] = hedges[r];
-		hedges[r] = t;
-	}
-}
-
-/* Get the representative of a set. */
-static int
-get_set(int num)
-{
-	int *snp = &sets[num];
-	int setsnum = *snp;
-
-	if (setsnum == num)
-		return num;
-	else
-		return (*snp = get_set(setsnum));
-}
-
-/* Join two sets together. */
-static void
-join_sets(int num1, int num2)
-{
-	int s1, s2;
-
-	s1 = get_set(num1);
-	s2 = get_set(num2);
-	if (s1 < s2)
-		sets[s2] = s1;
-	else
-		sets[s1] = s2;
-}
-
-/* Exitialise the sets. */
-static void
-exit_sets(void)
-{
-	free(hedges);
-	hedges = nil;
-	free(sets);
-	sets = nil;
-}
-
-/*
- * Second alternative maze creator: Put each square in the maze in a
- * separate set. Also, make a list of all the hedges. Randomize that list.
- * Walk through the list. If, for a certain hedge, the two squares on both
- * sides of it are in different sets, union the sets and remove the hedge.
- * Continue until all hedges have been processed or only one set remains.
- */
-static void
-set_create_maze(void)
-{
-	int i, h, x, y, dir, v, w;
-	int xsz = maze_size_x, ysz = maze_size_y;	/* local copies */
-	int done = 2 * xsz * ysz;
-
-	init_sets();			/* Do almost all the setup. */
-	/* Start running through the hedges. */
-	for (i = 0; i < done; i++) {
-		h = hedges[i];
-
-		/* This one is in the logo or outside border. */
-		if (h == -1)
-			continue;
-
-		dir = h % 2? 1: 2;
-		x = (h >> 1) % xsz;
-		y = (h >> 1) / xsz;
-
-		v = x;
-		w = y;
-		switch (dir) {
-		case 1:
-			v++;
-			break;
-		case 2:
-			w++;
-			break;
-		}
-
-		if (get_set(x + y * xsz) != get_set(v + w * xsz))
-			join_sets(x + y * xsz, v + w * xsz);
-						/* Don't draw the wall. */
-		else
-			build_wall(x, y, dir);	/* Don't join the sets. */
-	}
-	exit_sets();				/* Free some memory. */
-}
-
-/*
- * First alternative maze creator: Pick a random, empty corner in the maze.
- * Pick a random direction.  Draw a wall in that direction, from that corner
- * until we hit a wall.  Option: Only draw the wall if it's going to be
- * shorter than a certain length.  Otherwise we get lots of long walls.
- */
-static void
-alt_create_maze(void)
-{
-	char *corners;
-	int *c_idx;
-	int i, j, height, width, open_corners, k, dir, x, y, size;
-
-	height = maze_size_y + 1;
-	width = maze_size_x + 1;
-	size = height * width;
-
-	/* Allocate and clear some mem. */
-	corners = emallocz(size, Zero);
-
-	/* Set up the indexing array. */
-	c_idx = emallocz(sizeof(int) * size, Nozero);
-	for (i = 0; i < size; i++)
-		c_idx[i] = i;
-	for (i = 0; i < size; i++) {
-		k = random() % size;
-		j = c_idx[i];
-		c_idx[i] = c_idx[k];
-		c_idx[k] = j;
-	}
-
-	/* Set up some initial walls. */
-	/* Outside walls. */
-	for (i = 0; i < width; i++) {
-		corners[i] = 1;
-		corners[i+width*(height-1)] = 1;
-	}
-	for (i = 0; i < height; i++) {
-		corners[i*width] = 1;
-		corners[i*width+width-1] = 1;
-	}
-	/* Walls around logo.  In fact, inside the logo, too. */
-	/* Also draw the walls. */
-	if (logo_x != -1) {
-		int logow = 1 + Logowidth/grid_width;
-		int logoh = 1 + Logoheight/grid_height;
-		int bridge_dir, bridge_c;
-
-		if (bridge_p && logoh >= 3 && logow >= 3) {
-			bridge_dir = 1 + random() % 2;
-			if (bridge_dir == 1)
-				bridge_c = logo_y + random()%(logoh - 2) + 1;
-			else
-				bridge_c = logo_x + random()%(logow - 2) + 1;
-		} else {
-			bridge_dir = 0;
-			bridge_c = -1;
-		}
-		for (i = logo_x; i <= logo_x + logow; i++)
-			for (j = logo_y; j <= logo_y + logoh; j++)
-				corners[i+width*j] = 1;
-		for (x = logo_x; x < logo_x + logow; x++) {
-			if (!(bridge_dir == 2 && x == bridge_c)) {
-				build_wall(x, logo_y, 0);
-				build_wall(x, logo_y + logoh, 0);
-			}
-			if (bridge_dir == 1) {
-				build_wall(x, bridge_c, 0);
-				build_wall(x, bridge_c, 2);
-			}
-		}
-		for (y = logo_y; y < logo_y + logoh; y++) {
-			if (!(bridge_dir == 1 && y == bridge_c)) {
-				build_wall(logo_x, y, 3);
-				build_wall(logo_x + logow, y, 3);
-			}
-			if (bridge_dir == 2) {
-				build_wall(bridge_c, y, 1);
-				build_wall(bridge_c, y, 3);
-			}
-		}
-		/* Connect one wall of the logo with an outside wall. */
-		if (bridge_p)
-			dir = (bridge_dir + 1) % 4;
-		else
-			dir = random() % 4;
-		switch (dir) {
-		case 0:
-			x = logo_x + (random() % (logow + 1));
-			y = logo_y;
-			break;
-		case 1:
-			x = logo_x + logow;
-			y = logo_y + (random() % (logoh + 1));
-			break;
-		case 2:
-			x = logo_x + (random() % (logow + 1));
-			y = logo_y + logoh;
-			break;
-		case 3:
-			x = logo_x;
-			y = logo_y + (random() % (logoh + 1));
-			break;
-		}
-		do {
-			corners[x+width*y] = 1;
-			switch (dir) {
-			case 0:
-				build_wall(x - 1, y - 1, 1);
-				y--;
-				break;
-			case 1:
-				build_wall(x, y, 0);
-				x++;
-				break;
-			case 2:
-				build_wall(x, y, 3);
-				y++;
-				break;
-			case 3:
-				build_wall(x - 1, y - 1, 2);
-				x--;
-				break;
-			}
-		} while (!corners[x+width*y]);
-		if (bridge_p) {
-			dir = (dir + 2) % 4;
-			switch (dir) {
-			case 0:
-				x = logo_x + (random() % (logow + 1));
-				y = logo_y;
-				break;
-			case 1:
-				x = logo_x + logow;
-				y = logo_y + (random() % (logoh + 1));
-				break;
-			case 2:
-				x = logo_x + (random() % (logow + 1));
-				y = logo_y + logoh;
-				break;
-			case 3:
-				x = logo_x;
-				y = logo_y + (random() % (logoh + 1));
-				break;
-			}
-			do {
-				corners[x+width*y] = 1;
-				switch (dir) {
-				case 0:
-					build_wall(x - 1, y - 1, 1);
-					y--;
-					break;
-				case 1:
-					build_wall(x, y, 0);
-					x++;
-					break;
-				case 2:
-					build_wall(x, y, 3);
-					y++;
-					break;
-				case 3:
-					build_wall(x - 1, y - 1, 2);
-					x--;
-					break;
-				}
-			} while (!corners[x+width*y]);
-		}
-	}
-
-	/* Count open gridpoints. */
-	open_corners = 0;
-	for (i = 0; i < width; i++)
-		for (j = 0; j < height; j++)
-			if (!corners[i+width*j])
-				open_corners++;
-
-	/* Now do actual maze generation. */
-	while (open_corners > 0)
-		for (i = 0; i < size; i++)
-			if (!corners[c_idx[i]]) {
-				x = c_idx[i] % width;
-				y = c_idx[i] / width;
-				/* Choose a random direction. */
-				dir = random() % 4;
-
-				k = 0;
-				/* Measure the length of the wall we'd draw. */
-				while (!corners[x+width*y]) {
-					k++;
-					switch (dir) {
-					case 0:
-						y--;
-						break;
-					case 1:
-						x++;
-						break;
-					case 2:
-						y++;
-						break;
-					case 3:
-						x--;
-						break;
-					}
-				}
-
-				if (k <= max_length) {
-					x = c_idx[i] % width;
-					y = c_idx[i] / width;
-
-					/* Draw a wall until we hit something */
-					while (!corners[x+width*y]) {
-						open_corners--;
-						corners[x+width*y] = 1;
-						switch (dir) {
-						case 0:
-							build_wall(x-1, y-1, 1);
-							y--;
-							break;
-						case 1:
-							build_wall(x, y, 0);
-							x++;
-							break;
-						case 2:
-							build_wall(x, y, 3);
-							y++;
-							break;
-						case 3:
-							build_wall(x-1, y-1, 2);
-							x--;
-							break;
-						}
-					}
-				}
-			}
-
-	/* Free some memory we used. */
-	free(corners);
-	free(c_idx);
-}
-
-/*
- * The original maze creator.  Start somewhere.  Take a step in a random
- * direction.  Keep doing this until we hit a wall.  Then, backtrack until
- * we find a point where we can go in another direction.
- */
-static void
-create_maze(void)	/* create a maze layout given the initialized maze */
-{
-	int i, newdoor = 0;
-	int logow = 1 + Logowidth / grid_width;
-	int logoh = 1 + Logoheight / grid_height;
-
-	/* Maybe we should make a bridge? */
-	if (bridge_p && logo_x >= 0 && logow >= 3 && logoh >= 3) {
-		int bridge_dir, bridge_c;
-
-		bridge_dir = 1 + random() % 2;
-		if (bridge_dir == 1)
-			if (logoh >= 3)
-				bridge_c = logo_y + random() % (logoh - 2) + 1;
-			else
-				bridge_c = logo_y + random() % logoh;
-		else
-			if (logow >= 3)
-				bridge_c = logo_x + random() % (logow - 2) + 1;
-			else
-				bridge_c = logo_x + random() % logow;
-
-		if (bridge_dir == 1)
-			for (i = logo_x; i < logo_x + logow; i++)
-				maze[i][bridge_c] &= ~Doorintop;
-		else
-			for (i = logo_y; i < logo_y + logoh; i++)
-				maze[bridge_c][i] &= ~Doorintop;
-	}
-
-	for (; ;) {
-		setmove(move_list + sqnum, cur_sq_x, cur_sq_y, newdoor);
-		while ((newdoor = choose_door()) == -1)	/* pick a door */
-			if (backup() == -1)	/* no more doors ... backup */
-				return;	
-		sqnum++;
-
-		/* mark the out door */
-		maze[cur_sq_x][cur_sq_y] |= Doorouttop >> newdoor;
-
-		switch (newdoor) {
-		case 0:
-			cur_sq_y--;
-			break;
-		case 1:
-			cur_sq_x++;
-			break;
-		case 2:
-			cur_sq_y++;
-			break;
-		case 3:
-			cur_sq_x--;
-			break;
-		}
-
-		/* mark the in door */
-		maze[cur_sq_x][cur_sq_y] |= Doorintop >> ((newdoor + 2) % 4);
-
-		/* if end square set path length and save path */
-		if (maze[cur_sq_x][cur_sq_y] & Endsq) {
-			/* we're done; we've got a soluble maze. */
-		}
-	}
-}
-
-static int
-choose_door(void)				/* pick a new path */
-{
-	int candidate = 0, ncand = 0;
-	int cursqx = cur_sq_x, cursqy = cur_sq_y;	/* local copies */
-	int candidates[3];
-	ushort *sqp = &maze[cursqx][cursqy];
-
-	/* top wall */
-	if (!(*sqp & (Doorintop|Doorouttop|Walltop)))
-		if (maze[cursqx][cursqy - 1] & Doorinany) {
-			*sqp |= Walltop;
-			maze[cursqx][cursqy - 1] |= Wallbottom;
-			draw_wall(cursqx, cursqy, candidate);
-		} else
-			candidates[ncand++] = candidate;
-	candidate++;
-
-	/* right wall */
-	if (!(*sqp & (Doorinright|Dooroutright|Wallright)))
-		if (maze[cursqx + 1][cursqy] & Doorinany) {
-			*sqp |= Wallright;
-			maze[cursqx + 1][cursqy] |= Wallleft;
-			draw_wall(cursqx, cursqy, candidate);
-		} else
-			candidates[ncand++] = candidate;
-	candidate++;
-
-	/* bottom wall */
-	if (!(*sqp & (Doorinbottom|Dooroutbottom|Wallbottom)))
-		if (maze[cursqx][cursqy + 1] & Doorinany) {
-			*sqp |= Wallbottom;
-			maze[cursqx][cursqy + 1] |= Walltop;
-			draw_wall(cursqx, cursqy, candidate);
-		} else
-			candidates[ncand++] = candidate;
-	candidate++;
-
-	/* left wall */
-	if (!(*sqp & (Doorinleft|Dooroutleft|Wallleft)))
-		if (maze[cursqx - 1][cursqy] & Doorinany) {
-			*sqp |= Wallleft;
-			maze[cursqx - 1][cursqy] |= Wallright;
-			draw_wall(cursqx, cursqy, candidate);
-		} else
-			candidates[ncand++] = candidate;
-	candidate++;
-	USED(candidate);
-
-	if (ncand == 0)
-		return -1;
-	if (ncand == 1)
-		return candidates[0];
-	return candidates[get_random(ncand)];
-
-}
-
-static int
-backup(void)					/* back up a move */
-{
-	sqnum--;
-	if (sqnum >= 0) {
-		cur_sq_x = move_list[sqnum].x;
-		cur_sq_y = move_list[sqnum].y;
-	} else
-		cur_sq_x = cur_sq_y = 0;
-	return sqnum;
-}
-
-static void
-draw_maze_border(void)				/* draw the maze outline */
-{
-	int i, j;
-
-	for (i = 0; i < maze_size_x; i++) {
-		if (maze[i][0] & Walltop)
-			line(screen, addpt(screen->r.min,
-				Pt(Border_x + grid_width * i, Border_y)),
-			    addpt(screen->r.min,
-				Pt(Border_x + grid_width*(i+1) - 1, Border_y)),
-			    Endsquare, Endsquare, 0, display->white, ZP);
-		if ((maze[i][maze_size_y - 1] & Wallbottom))
-			line(screen, addpt(screen->r.min,
-			    Pt(Border_x + grid_width * i,
-				Border_y + grid_height * (maze_size_y) - 1)),
-			    addpt(screen->r.min,
-			    Pt(Border_x + grid_width * (i + 1) - 1,
-				Border_y + grid_height * (maze_size_y) - 1)),
-			    Endsquare, Endsquare, 0, display->white, ZP);
-	}
-	for (j = 0; j < maze_size_y; j++) {
-		if (maze[maze_size_x - 1][j] & Wallright)
-			line(screen, addpt(screen->r.min,
-			    Pt(Border_x + grid_width * maze_size_x - 1,
-				Border_y + grid_height * j)),
-			    addpt(screen->r.min,
-			    Pt(Border_x + grid_width * maze_size_x - 1,
-				Border_y + grid_height * (j + 1) - 1)),
-			    Endsquare, Endsquare, 0, display->white, ZP);
-		if (maze[0][j] & Wallleft)
-			line(screen, addpt(screen->r.min,
-			    Pt(Border_x, Border_y + grid_height * j)),
-			    addpt(screen->r.min,
-			    Pt(Border_x, Border_y + grid_height * (j + 1) - 1)),
-			    Endsquare, Endsquare, 0, display->white, ZP);
-	}
-
-	if (logo_x != -1) {
-		unsigned w = 48, h = 48;
-		Point p;
-		/* round up to grid size */
-		int ww = ((Logowidth  / grid_width) + 1)  *grid_width;
-		int hh = ((Logoheight / grid_height) + 1) *grid_height;
-
-		p = addpt(screen->r.min,
-			Pt(Border_x + 1 + grid_width *logo_x + ((ww - w)/2),
-			   Border_y + 1 + grid_height*logo_y + ((hh - h)/2)));
-
-		draw(screen, Rpt(p, addpt(p, Pt(48, 48))), glenda, nil, ZP);
-		/* draw(screen, screen->r, glenda, nil, ZP); */
-	}
-	draw_solid_square(start_x, start_y, Walltop >> start_dir, liveColor);
-	draw_solid_square(end_x, end_y, Walltop >> end_dir, liveColor);
-}
-
-/* was a profiling hot-spot; called a lot */
-static void
-draw_wall(int i, int j, int dir)                /* draw a single wall */
-{
-	int gridhigh = grid_height, gridwide = grid_width;
-	Point scrmin = screen->r.min, p1, p2;
-
-	switch (dir) {
-	case 0:
-		p1 = Pt(Border_x + gridwide*i, Border_y + gridhigh*j);
-		p2 = Pt(Border_x + gridwide*(i+1), Border_y + gridhigh*j);
-		break;
-	case 1:
-		p1 = Pt(Border_x + gridwide*(i+1), Border_y + gridhigh*j);
-		p2 = Pt(Border_x + gridwide*(i+1), Border_y + gridhigh*(j+1));
-		break;
-	case 2:
-		p1 = Pt(Border_x + gridwide*i, Border_y + gridhigh*(j+1));
-		p2 = Pt(Border_x + gridwide*(i+1), Border_y + gridhigh*(j+1));
-		break;
-	case 3:
-		p1 = Pt(Border_x + gridwide*i, Border_y + gridhigh*j);
-		p2 = Pt(Border_x + gridwide*i, Border_y + gridhigh*(j+1));
-		break;
-	default:
-		if (sync_p && !nodrawmaze)
-			flushimage(display, 1);
-		return;
-	}
-	line(screen, addpt(scrmin, p1), addpt(scrmin, p2),
-		Endsquare, Endsquare, 0, display->white, ZP);
-	if (sync_p && !nodrawmaze)
-		flushimage(display, 1);
-}
-
-/* Actually build a wall. */
-static void
-build_wall(int i, int j, int dir)
-{
-	draw_wall(i, j, dir);		/* Draw it on the screen. */
-	/* Put it in the maze. */
-	switch (dir) {
-	case 0:
-		maze[i][j] |= Walltop;
-		if (j > 0)
-			maze[i][j-1] |= Wallbottom;
-		break;
-	case 1:
-		maze[i][j] |= Wallright;
-		if (i < maze_size_x - 1)
-			maze[i+1][j] |= Wallleft;
-		break;
-	case 2:
-		maze[i][j] |= Wallbottom;
-		if (j < maze_size_y - 1)
-			maze[i][j+1] |= Walltop;
-		break;
-	case 3:
-		maze[i][j] |= Wallleft;
-		if (i > 0)
-			maze[i-1][j] |= Wallright;
-		break;
-	}
-}
-
-/* draw a solid square in a square */
-static void
-draw_solid_square(int i, int j, int dir, Image *c)
-{
-	int gridhigh = grid_height, gridwide = grid_width;
-	int lbw = bw;			/* local copy */
-	int twobw = lbw << 1;
-	int bxgrwi = Border_x + gridwide*i, bygrhj = Border_y + gridhigh*j;
-	Rectangle r;
-	Point p, scrmin = screen->r.min;
-
-	switch (dir) {
-	case Walltop:
-		p = addpt(scrmin, Pt(bxgrwi + lbw, bygrhj - lbw));
-		r = Rpt(p, addpt(p, Pt(gridwide - twobw, gridhigh)));
-		break;
-	case Wallright:
-		p = addpt(scrmin, Pt(bxgrwi + lbw,  bygrhj + lbw));
-		r = Rpt(p, addpt(p, Pt(gridwide, gridhigh - twobw)));
-		break;
-	case Wallbottom:
-		p = addpt(scrmin, Pt(bxgrwi + lbw, bygrhj + lbw));
-		r = Rpt(p, addpt(p, Pt(gridwide - twobw, gridhigh)));
-		break;
-	case Wallleft:
-		p = addpt(scrmin, Pt(bxgrwi - lbw, bygrhj + lbw));
-		r = Rpt(p, addpt(p, Pt(gridwide, gridhigh - twobw)));
-		break;
-	default:
-		if (!nodrawmaze)
-			flushimage(display, 1);
-		return;
-	}
-	draw(screen, r, c, nil, ZP);
-	if (!nodrawmaze)
-		flushimage(display, 1);
-}
-
-int
-longdeadend_p(int x1, int y1, int x2, int y2, int endwall)
-{
-	int dx = x2 - x1, dy = y2 - y1;
-	int sidewalls;
-
-	assert(dx != 0 || dy != 0);
-	sidewalls = endwall | endwall >> 2 | endwall << 2;
-	sidewalls = ~sidewalls & Wallany;
-	while ((maze[x2][y2] & Wallany) == sidewalls) {
-		x2 += dx;
-		y2 += dy;
-	}
-
-	if ((maze[x2][y2] & Wallany) == (sidewalls | endwall)) {
-		endwall = (endwall >> 2 | endwall << 2) & Wallany;
-		while (x1 != x2 || y1 != y2) {
-			x1 += dx;
-			y1 += dy;
-			draw_solid_square(x1, y1, endwall, skipColor);
-			maze[x1][y1] |= Solvervisit;
-		}
-		return 1;
-	} else
-		return 0;
-}
-
-static void
-drawnowall(int x, int y)
-{
-	int lbw = bw, gridhigh = grid_height, gridwide = grid_width;
-								/* local copy */
-	int twobw = lbw << 1;
-	Point p;
-	Rectangle r;
-
-	/* fill the rectangle */
-	p = addpt(screen->r.min,
-		Pt(Border_x + lbw + gridwide*x, Border_y + lbw + gridhigh*y));
-	r = Rpt(p, addpt(p, Pt(gridwide - twobw, gridhigh - twobw)));
-	draw(screen, r, surroundColor, nil, ZP);
-}
-
-/*
- * Find all not Solvervisit squares bordering Notdead squares
- * and mark them Notdead also.  Repeat until no more such squares.
- * a major profiling hotspot.
- */
-static void
-marknotdead(void)
-{
-	int x, y, flipped;
-	int xsz = maze_size_x, ysz = maze_size_y; 	/* local copies */
-	ushort *sqp;
-
-	maze[start_x][start_y] |= Notdead;
-	do {
-		flipped = 0;
-		for (x = 0; x < xsz; x++) {
-			sqp = maze[x];
-			for (y = 0; y < ysz; y++, sqp++)
-				if (!(*sqp & (Solvervisit|Notdead)) &&
-				     (y > 0 && (sqp[-1] & Notdead) ||
-				      x > 0 && (maze[x-1][y] & Notdead))) {
-					flipped = 1;
-					*sqp |= Notdead;
-				}
-		}
-		for (x = xsz - 1; x >= 0; x--) {
-			sqp = &maze[x][ysz];
-			for (y = ysz - 1; sqp--, y >= 0; y--) {
-				if (!(*sqp & (Solvervisit|Notdead)) &&
-				     (y < ysz-1 && (sqp[1]&Notdead) ||
-				      x < xsz-1 && (maze[x+1][y]&Notdead))) {
-					flipped = 1;
-					*sqp |= Notdead;
-				}
-			}
-		}
-	} while (flipped);
-}
-
-#define ifnowalldraw(x, y, sq, wallbit) \
-	if (!((sq) & (wallbit))) \
-		draw_solid_square(x, y, wallbit, surroundColor);
-#define drawsq(x, y, sq) { \
-	if (!((sq) & Wallany)) \
-		drawnowall(x, y); \
-	else { \
-		ifnowalldraw(x, y, sq, Wallleft); \
-		ifnowalldraw(x, y, sq, Wallright); \
-		ifnowalldraw(x, y, sq, Walltop); \
-		ifnowalldraw(x, y, sq, Wallbottom); \
-	} \
-}
-
-/* a profiling hotspot. */
-static void
-markdeadredraw(void)
-{
-	int x, y;
-	int xsz = maze_size_x, ysz = maze_size_y; 	/* local copies */
-	int gridhigh = grid_height, gridwide = grid_width;	/* " */
-	int logox = logo_x, logoy = logo_y;			/* " */
-	int logoxbound = logox + Logowidth/gridwide;
-	int logoybound = logoy + Logoheight/gridhigh;
-	ushort sq;
-	ushort *sqp;
-
-	for (x = 0; x < xsz; x++) {
-		sqp = maze[x];
-		for (y = 0; y < ysz; y++, sqp++) {
-			sq = *sqp;
-			if (sq & Notdead)
-				*sqp &= ~Notdead;
-			else if (!(sq & Solvervisit)) {
-				sq |= Solvervisit;
-				*sqp = sq;
-				if (x < logox || x > logoxbound ||
-				    y < logoy || y > logoybound)
-					drawsq(x, y, sq);
-			}
-		}
-	}
-}
-
-/*
- * Find all dead regions -- areas from which the goal cannot be reached --
- * and mark them visited.
- */
-static void
-find_dead_regions(void)
-{
-	marknotdead();
-	markdeadredraw();
-	flushimage(display, 1);
-}
-
-static void
-chkmouse(void)
-{
-	if (ecanmouse()) {
-		Mouse m = emouse();
-
-		if ((m.buttons & 4) && emenuhit(3, &m, &menu) == 0)
-			exits(0);
-	}
-}
-
-/* backtracking state */
-typedef struct {
-	int	depth;		/* of `recursion' */
-	Move	*mv;
-	int	backing;	/* flag: backtracking in progress */
-	int	from;
-} Backtrack;
-
-static Move *
-backtrack(Backtrack *btp)
-{
-	int from;
-	Move *mv = btp->mv;
-
-	if (btp->depth <= 0) {		/* backtracked to the start? */
-		print("Insoluble maze.\n");
-		return nil;
-	}
-
-	if (!btp->backing && !ignorant_p)
-		find_dead_regions();
-	btp->backing = 1;
-	assert(mv != path);
-	from = (mv-1)->dir;
-	btp->from = ((from << 2) & Wallany) | ((from >> 2) & Wallany);
-
-	draw_solid_square(mv->x, mv->y, btp->from, deadColor);
-	btp->mv = path + --btp->depth;
-	return btp->mv;
-}
-
-/* doing the backtracking via recursion would be cleaner. */
-/* a profiling hotspot */
-static void
-solve_maze(void)			/* solve it with graphical feedback */
-{
-	int x, y, ways;
-	unsigned dir;
-	Backtrack btstate;
-	Backtrack *btp = &btstate;
-	Move *mv;			/* cached copy of btp->mv */
-
-	/* plug up the surrounding wall */
-	maze[end_x][end_y] |= Walltop >> end_dir;
-
-	/* initialize search path */
-	btp->depth = btp->backing = btp->from = 0;
-	btp->mv = mv = path;
-	setmove(mv, end_x, end_y, 0);
-	mv->ways = 0;
-	maze[end_x][end_y] |= Solvervisit;
-	while (!(maze[mv->x][mv->y] & Startsq) && !restart) {
-		if (solve_delay)
-			sleep(solve_delay);
-		chkmouse();
-		if (mv->dir)
-			ways = mv->ways;
-		else {
-			ways = 0;
-			/*
-			 * First visit this square.
-			 * Which adjacent squares are open?
-			 */
-			for (dir = Walltop; dir & Wallany; dir >>= 1) {
-				if (maze[mv->x][mv->y] & dir)
-					continue;
-
-				x = mv->x - !!(dir&Wallleft) + !!(dir&Wallright);
-				y = mv->y - !!(dir&Walltop) + !!(dir&Wallbottom);
-				if (maze[x][y] & Solvervisit)
-					continue;
-
-				btp->from = ((dir << 2) & Wallany) |
-					    ((dir >> 2) & Wallany);
-				/* don't enter obvious dead ends */
-				chkmouse();
-				if (((maze[x][y] & Wallany) | btp->from) !=
-				    Wallany) {
-					if (!longdeadend_p(mv->x, mv->y, x, y,
-					    dir))
-						ways |= dir;
-				} else {
-					draw_solid_square(x, y, btp->from,
-						skipColor);
-					maze[x][y] |= Solvervisit;
-				}
-			}
-		}
-		/* ways now has a bitmask of open paths. */
-
-		if (!ways) {
-			mv = backtrack(btp);
-			if (mv == nil)
-				return;
-			continue;
-		}
-
-		if (!ignorant_p) {
-			x = mv->x - start_x;
-			y = mv->y - start_y;
-
-			/* choice one */
-			if (abs(y) <= abs(x))
-				dir = (x > 0)? Wallleft: Wallright;
-			else
-				dir = (y > 0)? Walltop: Wallbottom;
-
-			if (!(dir & ways))
-				/* choice two */
-				switch (dir) {
-				case Walltop:
-				case Wallbottom:
-					dir = (x > 0)? Wallleft: Wallright;
-					break;
-				case Wallleft:
-				case Wallright:
-					dir = (y > 0)? Walltop: Wallbottom;
-					break;
-				}
-			if (!(dir & ways))
-				dir = ((dir << 2) & Wallany) |
-				      ((dir >> 2) & Wallany);/* choice three */
-			if (!(dir & ways))
-				dir = ways;		/* choice four */
-		} else {
-			if (ways & Walltop)
-				dir = Walltop;
-			else if (ways & Wallleft)
-				dir = Wallleft;
-			else if (ways & Wallbottom)
-				dir = Wallbottom;
-			else if (ways & Wallright)
-				dir = Wallright;
-			else
-				dir = 0;
-		}
-
-		if (!dir) {
-			mv = backtrack(btp);
-			if (mv == nil)
-				return;
-			continue;
-		}
-
-		btp->backing = 0;
-		ways &= ~dir;		/* tried this one */
-
-		x = mv->x - !!(dir & Wallleft) + !!(dir & Wallright);
-		y = mv->y - !!(dir & Walltop) + !!(dir & Wallbottom);
-
-		/* advance in direction dir */
-		mv->dir = dir;
-		assert(mv->dir == dir);
-		mv->ways = ways;
-		assert(mv->ways == ways);
-		draw_solid_square(mv->x, mv->y, dir, liveColor);
-
-		btp->mv = mv = path + ++btp->depth;
-		setmove(mv, x, y, 0);
-		mv->ways = 0;
-		maze[x][y] |= Solvervisit;
-	}
-}
-
-static void
-newmaze(void)
-{
-	exit_sets();
-	restart = 0;
-	sqnum = 0;
-	cur_sq_x = cur_sq_y = 0;
-	start_x = start_y = start_dir = end_x = end_y = end_dir = 0;
-	nodrawmaze = 0;
-	set_maze_sizes(Dx(screen->r), Dy(screen->r));
-
-	draw(screen, screen->r, display->black, nil, ZP);
-	flushimage(display, 1);
-	sync_p = (random() % 10) == 0;
-}
-
-/*
- *  jmr additions for Jamie Zawinski's <jwz@jwz.org> screensaver stuff,
- *  note that the code above this has probably been hacked about in some
- *  arbitrary way.
- */
-void
-outerloop(void)
-{
-	int size = 5 + random()%20, generator = -1, this_gen;
-	ushort **stmaze = nil;
-
-	if (!Debug) {
-		solve_delay = 5;
-		pre_solve_delay = 2000;
-		post_solve_delay = 4000;
-	}
-	max_length = 5;
-	bridge_p = ignorant_p = 0;
-
-	grid_width = grid_height = size;
-	bw = (size > 6? 3: (size-1)/2);
-
-	restart = 0;
-	sync_p = (random() % 10) == 0;
-
-	for (; ;) {			/* primary execution loop [rhess] */
-		chkmouse();
-		if (restart) {
-			restart = stop = 0;
-			state = 1;
-		} else if (stop)
-			continue;
-
-		if (state > 1)
-			assert(stmaze == maze);
-		switch (state++) {
-		case 1:
-			newmaze();
-			stmaze = maze;
-			initialize_maze();
-			break;
-		case 2:
-			nodrawmaze = 1;		/* draw it in core */
-			draw(screen, screen->r, display->black, nil, ZP);
-			draw_maze_border();
-			if (!nodrawmaze)
-				flushimage(display, 1);
-			break;
-		case 3:
-			this_gen = generator;
-			if (this_gen < 0 || this_gen > 2)
-				this_gen = random() % 3;
-			switch (this_gen) {
-			case 0:
-				create_maze();
-				break;
-			case 1:
-				alt_create_maze();
-				break;
-			case 2:
-				set_create_maze();
-				break;
-			}
-			nodrawmaze = 0;		/* now push it out */
-			flushimage(display, 1);
-			break;
-		case 4:
-			sleep(pre_solve_delay);
-			break;
-		case 5:
-			solve_maze();
-			break;
-		case 6:
-			sleep(post_solve_delay);
-			state = 1;
-			draw(screen, screen->r, display->black, nil, ZP);
-			break;
-		default:
-			abort();
-			break;
-		}
-		assert(maze == stmaze);
-	}
-}
-
-void
-eresized(int new)
-{
-	if (new && getwindow(display, Refnone) < 0)
-		sysfatal("can't reattach to window");
-	restart = 1;
-}
-
-void
-main(int argc, char **argv)
-{
-	int fd;
-	Rectangle unit = Rect(0, 0, 1, 1);
-
-	mainmem->flags |= POOL_ANTAGONISM;
-
-	ARGBEGIN{
-	}ARGEND;
-	srand(time(0));
-
-	if (initdraw(nil, nil, "maze") < 0)
-		sysfatal("initdraw failed: %r");
-
-	liveColor = allocimage(display, unit, screen->chan, 1, DGreen);
-	deadColor = allocimage(display, unit, screen->chan, 1, DRed);
-	skipColor = allocimage(display, unit, screen->chan, 1, DMagenta);
-	surroundColor = allocimage(display, unit, screen->chan, 1, DPaleblue);
-	if (liveColor == nil || deadColor == nil || skipColor == nil ||
-	    surroundColor == nil)
-		sysfatal("out of memory");
-
-	fd = open("/lib/face/48x48x4/g/glenda.1", OREAD);
-	if (fd < 0)
-		sysfatal("cannot open /lib/face/48x48x4/g/glenda.1: %r");
-
-	glenda = readimage(display, fd, 0);
-	if (glenda == nil)
-		sysfatal("cannot load glenda's image: %r");
-
-	draw(screen, screen->r, display->black, nil, ZP);
-	flushimage(display, 1);
-
-	einit(Emouse);
-	eresized(0);
-	outerloop();
-}
//GO.SYSIN DD maze.c
echo maze.novel
sed 's/.//' >maze.novel <<'//GO.SYSIN DD maze.novel'
-/* the theory, the first, by Anne Elk (Miss), ahem. */
-
-/*
- * [ maze ] ...
- *
- * modified:  [ 1-04-00 ]  Johannes Keukelaar <johannes@nada.kth.se>
- *              Added -ignorant option (not the default) to remove knowlege
- *              of the direction in which the exit lies.
- *
- * modified:  [ 6-28-98 ]  Zack Weinberg <zack@rabi.phys.columbia.edu>
- *
- *              Made the maze-solver somewhat more intelligent.  There are
- *              three optimizations:
- *
- *              - Straight-line lookahead: the solver does not enter dead-end
- *                corridors.  This is a win with all maze generators.
- *
- *              - First order direction choice: the solver knows where the
- *                exit is in relation to itself, and will try paths leading in
- *                that direction first. This is a major win on maze generator 1
- *                which tends to offer direct routes to the exit.
- *
- *              - Dead region elimination: the solver already has a map of
- *                all squares visited.  Whenever it starts to backtrack, it
- *                consults this map and marks off all squares that cannot be
- *                reached from the exit without crossing a square already
- *                visited.  Those squares can never contribute to the path to
- *                the exit, so it doesn't bother checking them.  This helps a
- *                lot with maze generator 2 and somewhat less with generator 1.
- *
- *              Further improvements would require knowledge of the wall map
- *              as well as the position of the exit and the squares visited.
- *              I would consider that to be cheating.  Generator 0 makes
- *              mazes which are remarkably difficult to solve mechanically --
- *              even with these optimizations the solver generally must visit
- *              at least two-thirds of the squares.  This is partially
- *              because generator 0's mazes have longer paths to the exit.
- *
- * modified:  [ 4-10-97 ]  Johannes Keukelaar <johannes@nada.kth.se>
- *              Added multiple maze creators. Robustified solver.
- *              Added bridge option.
- * modified:  [ 8-11-95 ] Ed James <james@mml.mmc.com>
- *              added fill of dead-end box to solve_maze while loop.
- * modified:  [ 3-7-93 ]  Jamie Zawinski <jwz@jwz.org>
- *		added the XRoger logo, cleaned up resources, made
- *		grid size a parameter.
- * modified:  [ 3-3-93 ]  Jim Randell <jmr@mddjmr.fc.hp.com>
- *		Added the colour stuff and integrated it with jwz's
- *		screenhack stuff.  There's still some work that could
- *		be done on this, particularly allowing a resource to
- *		specify how big the squares are.
- * modified:  [ 10-4-88 ]  Richard Hess    ...!uunet!cimshop!rhess
- *              [ Revised primary execution loop within main()...
- *              [ Extended X event handler, check_events()...
- * modified:  [ 1-29-88 ]  Dave Lemke      lemke@sun.com
- *              [ Hacked for X11...
- *              [  Note the word "hacked" -- this is extremely ugly, but at
- *              [   least it does the job.  NOT a good programming example
- *              [   for X.
- * original:  [ 6/21/85 ]  Martin Weiss    Sun Microsystems  [ SunView ]
- *
- Copyright 1988 by Sun Microsystems, Inc. Mountain View, CA.
-
- All Rights Reserved
-
- Permission to use, copy, modify, and distribute this software and its
- documentation for any purpose and without fee is hereby granted,
- provided that the above copyright notice appear in all copies and that
- both that copyright notice and this permission notice appear in
- supporting documentation, and that the names of Sun or MIT not be
- used in advertising or publicity pertaining to distribution of the
- software without specific prior written permission. Sun and M.I.T.
- make no representations about the suitability of this software for
- any purpose. It is provided "as is" without any express or implied warranty.
-
- SUN DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
- ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
- PURPOSE. IN NO EVENT SHALL SUN BE LIABLE FOR ANY SPECIAL, INDIRECT
- OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS
- OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
- OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE
- OR PERFORMANCE OF THIS SOFTWARE.
- */
//GO.SYSIN DD maze.novel