# 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 [email protected], 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 <[email protected]> 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 <[email protected]>
- * Added -ignorant option (not the default) to remove knowlege
- * of the direction in which the exit lies.
- *
- * modified: [ 6-28-98 ] Zack Weinberg <[email protected]>
- *
- * 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 <[email protected]>
- * Added multiple maze creators. Robustified solver.
- * Added bridge option.
- * modified: [ 8-11-95 ] Ed James <[email protected]>
- * added fill of dead-end box to solve_maze while loop.
- * modified: [ 3-7-93 ] Jamie Zawinski <[email protected]>
- * added the XRoger logo, cleaned up resources, made
- * grid size a parameter.
- * modified: [ 3-3-93 ] Jim Randell <[email protected]>
- * 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 [email protected]
- * [ 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
|
