X-Git-Url: http://git.hungrycats.org/cgi-bin/gitweb.cgi?a=blobdiff_plain;f=hacks%2Fmaze.c;h=40edf41b58bf9e8dfdc310585680c9b963d037a2;hb=278c59e14c53fd412b734e699bd4f314f766f804;hp=5a77195cf41fa80aa8b0818ed1a5f87de73b3e74;hpb=6edc84f12f15860a71430c45e8392a5e4ef8203c;p=xscreensaver diff --git a/hacks/maze.c b/hacks/maze.c index 5a77195c..40edf41b 100644 --- a/hacks/maze.c +++ b/hacks/maze.c @@ -1,7 +1,41 @@ /****************************************************************************** * [ maze ] ... * - * modified: [ 3-7-93 ] Jamie Zawinski + * modified: [ 6-28-98 ] Zack Weinberg + * + * 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 + * Added multiple maze creators. Robustified solver. + * Added bridge option. + * modified: [ 8-11-95 ] Ed James + * added fill of dead-end box to solve_maze while loop. + * modified: [ 3-7-93 ] Jamie Zawinski * added the XRoger logo, cleaned up resources, made * grid size a parameter. * modified: [ 3-3-93 ] Jim Randell @@ -44,6 +78,7 @@ *****************************************************************************/ #include "screenhack.h" +#include "erase.h" #define XROGER @@ -52,17 +87,27 @@ static int solve_delay, pre_solve_delay, post_solve_delay; #include #include #include -#include +#ifndef VMS +# include +#else /* VMS */ +# include "sys$common:[decw$include.bitmaps]gray1.xbm" +#endif /* VMS */ #define MAX_MAZE_SIZE_X 500 #define MAX_MAZE_SIZE_Y 500 #define MOVE_LIST_SIZE (MAX_MAZE_SIZE_X * MAX_MAZE_SIZE_Y) -#define WALL_TOP 0x8000 -#define WALL_RIGHT 0x4000 -#define WALL_BOTTOM 0x2000 -#define WALL_LEFT 0x1000 +#define NOT_DEAD 0x8000 +#define SOLVER_VISIT 0x4000 +#define START_SQUARE 0x2000 +#define END_SQUARE 0x1000 + +#define WALL_TOP 0x8 +#define WALL_RIGHT 0x4 +#define WALL_BOTTOM 0x2 +#define WALL_LEFT 0x1 +#define WALL_ANY 0xF #define DOOR_IN_TOP 0x800 #define DOOR_IN_RIGHT 0x400 @@ -75,14 +120,13 @@ static int solve_delay, pre_solve_delay, post_solve_delay; #define DOOR_OUT_BOTTOM 0x20 #define DOOR_OUT_LEFT 0x10 -#define START_SQUARE 0x2 -#define END_SQUARE 0x1 #define border_x (0) #define border_y (0) #define get_random(x) (random() % (x)) - + + static int logo_x, logo_y; #ifdef XROGER @@ -100,23 +144,25 @@ static unsigned short maze[MAX_MAZE_SIZE_X][MAX_MAZE_SIZE_Y]; static struct { unsigned char x; unsigned char y; - unsigned char dir; + unsigned char dir, ways; } move_list[MOVE_LIST_SIZE], save_path[MOVE_LIST_SIZE], path[MOVE_LIST_SIZE]; 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 Display *dpy; static Window win; -static GC gc, cgc, tgc, logo_gc; +static GC gc, cgc, tgc, sgc, ugc, logo_gc, erase_gc; static Pixmap logo_map; -static int x = 0, y = 0, restart = 0, stop = 1, state = 1; +static int x = 0, y = 0, restart = 0, stop = 1, state = 1, max_length; +static int sync_p, bridge_p; static int -check_events() /* X event handler [ rhess ] */ +check_events (void) /* X event handler [ rhess ] */ { XEvent e; @@ -155,6 +201,9 @@ check_events() /* X event handler [ rhess ] */ case Expose: restart = 1; break; + default: + screenhack_handle_event(dpy, &e); + break; } return(1); } @@ -163,8 +212,7 @@ check_events() /* X event handler [ rhess ] */ static void -set_maze_sizes (width, height) - int width, height; +set_maze_sizes (int width, int height) { maze_size_x = width / grid_width; maze_size_y = height / grid_height; @@ -172,9 +220,11 @@ set_maze_sizes (width, height) static void -initialize_maze() /* draw the surrounding wall and start/end squares */ +initialize_maze (void) /* draw the surrounding wall and start/end squares */ { register int i, j, wall; + int logow = 1 + logo_width / grid_width; + int logoh = 1 + logo_height / grid_height; /* initialize all squares */ for ( i=0; i 15) && (maze_size_y > 15)) + if ((maze_size_x-logow >= 6) && (maze_size_y-logoh >= 6)) { - int logow = 1 + logo_width / grid_width; - int logoh = 1 + logo_height / grid_height; /* not closer than 3 grid units from a wall */ - logo_x = get_random (maze_size_x - logow - 6) + 3; - logo_y = get_random (maze_size_y - logoh - 6) + 3; + logo_x = get_random (maze_size_x - logow - 5) + 3; + logo_y = get_random (maze_size_y - logoh - 5) + 3; for (i=0; i=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++) + { + t = hedges[i]; + r = random()%(maze_size_x*maze_size_y*2); + hedges[i] = hedges[r]; + hedges[r] = t; + } +} + +/* Get the representative of a set. */ +static int +get_set(int num) +{ + int s; + + if(sets[num]==num) + return num; + else + { + s = get_set(sets[num]); + sets[num] = s; + return s; + } +} + +/* Join two sets together. */ +static void +join_sets(num1, num2) + int num1, num2; +{ + int s1, s2; + + s1 = get_set(num1); + s2 = get_set(num2); + + if(s1>1)%maze_size_x; + y = (h>>1)/maze_size_x; + + v = x; + w = y; + switch(dir) + { + case 1: + v++; + break; + case 2: + w++; + break; + } + +#if DEBUG_SETS + show_set(x+y*maze_size_x, logo_gc); + show_set(v+w*maze_size_x, tgc); +#endif + if(get_set(x+y*maze_size_x)!=get_set(v+w*maze_size_x)) + { +#if DEBUG_SETS + printf("Join!"); +#endif + join_sets(x+y*maze_size_x, v+w*maze_size_x); + /* Don't draw the wall. */ + } + else + { +#if DEBUG_SETS + printf("Build."); +#endif + /* Don't join the sets. */ + build_wall(x, y, dir); + } +#if DEBUG_SETS + if(!cont) + { + XSync(dpy, False); + c = getchar(); + if(c=='c') + cont = 1; + } + show_set(x+y*maze_size_x, erase_gc); + show_set(v+w*maze_size_x, erase_gc); +#endif + } + + /* Free some memory. */ + exit_sets(); +} + +/* 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; + + height = maze_size_y+1; + width = maze_size_x+1; + + /* Allocate and clear some mem. */ + corners = (char *)calloc(height*width, 1); + if(!corners) + return; + + /* Set up the indexing array. */ + c_idx = (int *)malloc(sizeof(int)*height*width); + if(!c_idx) + { + free(corners); + return; + } + for(i = 0; i < height*width; i++) + c_idx[i] = i; + for(i = 0; i < height*width; i++) + { + j = c_idx[i]; + k = random()%(height*width); + 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 + logo_width / grid_width; + int logoh = 1 + logo_height / 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 < width*height; 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() /* create a maze layout given the intiialized maze */ +create_maze (void) /* create a maze layout given the initialized maze */ { - register int i, newdoor; + register int i, newdoor = 0; + int logow = 1 + logo_width / grid_width; + int logoh = 1 + logo_height / 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] &= ~DOOR_IN_TOP; + } + } + else + { + for(i = logo_y; i < logo_y+logoh; i++) + { + maze[bridge_c][i] &= ~DOOR_IN_TOP; + } + } + } + do { move_list[sqnum].x = cur_sq_x; move_list[sqnum].y = cur_sq_y; @@ -331,7 +990,7 @@ create_maze() /* create a maze layout given the intiialized maze */ static int -choose_door() /* pick a new path */ +choose_door (void) /* pick a new path */ { int candidates[3]; register int num_candidates; @@ -348,7 +1007,7 @@ choose_door() /* pick a new path */ if ( maze[cur_sq_x][cur_sq_y - 1] & DOOR_IN_ANY ) { maze[cur_sq_x][cur_sq_y] |= WALL_TOP; maze[cur_sq_x][cur_sq_y - 1] |= WALL_BOTTOM; - draw_wall(cur_sq_x, cur_sq_y, 0); + draw_wall(cur_sq_x, cur_sq_y, 0, gc); goto rightwall; } candidates[num_candidates++] = 0; @@ -364,7 +1023,7 @@ choose_door() /* pick a new path */ if ( maze[cur_sq_x + 1][cur_sq_y] & DOOR_IN_ANY ) { maze[cur_sq_x][cur_sq_y] |= WALL_RIGHT; maze[cur_sq_x + 1][cur_sq_y] |= WALL_LEFT; - draw_wall(cur_sq_x, cur_sq_y, 1); + draw_wall(cur_sq_x, cur_sq_y, 1, gc); goto bottomwall; } candidates[num_candidates++] = 1; @@ -380,7 +1039,7 @@ choose_door() /* pick a new path */ if ( maze[cur_sq_x][cur_sq_y + 1] & DOOR_IN_ANY ) { maze[cur_sq_x][cur_sq_y] |= WALL_BOTTOM; maze[cur_sq_x][cur_sq_y + 1] |= WALL_TOP; - draw_wall(cur_sq_x, cur_sq_y, 2); + draw_wall(cur_sq_x, cur_sq_y, 2, gc); goto leftwall; } candidates[num_candidates++] = 2; @@ -396,7 +1055,7 @@ choose_door() /* pick a new path */ if ( maze[cur_sq_x - 1][cur_sq_y] & DOOR_IN_ANY ) { maze[cur_sq_x][cur_sq_y] |= WALL_LEFT; maze[cur_sq_x - 1][cur_sq_y] |= WALL_RIGHT; - draw_wall(cur_sq_x, cur_sq_y, 3); + draw_wall(cur_sq_x, cur_sq_y, 3, gc); goto donewall; } candidates[num_candidates++] = 3; @@ -412,7 +1071,7 @@ choose_door() /* pick a new path */ static int -backup() /* back up a move */ +backup (void) /* back up a move */ { sqnum--; cur_sq_x = move_list[sqnum].x; @@ -422,7 +1081,7 @@ backup() /* back up a move */ static void -draw_maze_border() /* draw the maze outline */ +draw_maze_border (void) /* draw the maze outline */ { register int i, j; @@ -471,14 +1130,13 @@ draw_maze_border() /* draw the maze outline */ border_x + 3 + grid_width * logo_x, border_y + 3 + grid_height * logo_y, 1); } - draw_solid_square (start_x, start_y, start_dir, tgc); - draw_solid_square (end_x, end_y, end_dir, tgc); + draw_solid_square (start_x, start_y, WALL_TOP >> start_dir, tgc); + draw_solid_square (end_x, end_y, WALL_TOP >> end_dir, tgc); } static void -draw_wall(i, j, dir) /* draw a single wall */ - int i, j, dir; +draw_wall(int i, int j, int dir, GC gc) /* draw a single wall */ { switch (dir) { case 0: @@ -510,84 +1168,350 @@ draw_wall(i, j, dir) /* draw a single wall */ border_y + grid_height * (j+1)); break; } + if(sync_p) + XSync(dpy, False); } -int bw; +/* Actually build a wall. */ +static void +build_wall(i, j, dir) + int i, j, dir; +{ + /* Draw it on the screen. */ + draw_wall(i, j, dir, gc); + /* Put it in the maze. */ + switch(dir) + { + case 0: + maze[i][j] |= WALL_TOP; + if(j>0) + maze[i][j-1] |= WALL_BOTTOM; + break; + case 1: + maze[i][j] |= WALL_RIGHT; + if(i0) + maze[i-1][j] |= WALL_RIGHT; + break; + } +} + +/* Break out a wall. */ +#if 0 +static void +break_wall(i, j, dir) + int i, j, dir; +{ + /* Draw it on the screen. */ + draw_wall(i, j, dir, erase_gc); + /* Put it in the maze. */ + switch(dir) + { + case 0: + maze[i][j] &= ~WALL_TOP; + if(j>0) + maze[i][j-1] &= ~WALL_BOTTOM; + break; + case 1: + maze[i][j] &= ~WALL_RIGHT; + if(i0) + maze[i-1][j] &= ~WALL_RIGHT; + break; + } +} +#endif /* 0 */ + static void -draw_solid_square(i, j, dir, gc) /* draw a solid square in a square */ - register int i, j, dir; - GC gc; +draw_solid_square(int i, int j, /* draw a solid square in a square */ + int dir, GC gc) { switch (dir) { - case 0: XFillRectangle(dpy, win, gc, - border_x + bw + grid_width * i, - border_y - bw + grid_height * j, - grid_width - (bw+bw), grid_height); - break; - case 1: XFillRectangle(dpy, win, gc, - border_x + bw + grid_width * i, - border_y + bw + grid_height * j, - grid_width, grid_height - (bw+bw)); - break; - case 2: XFillRectangle(dpy, win, gc, - border_x + bw + grid_width * i, - border_y + bw + grid_height * j, - grid_width - (bw+bw), grid_height); - break; - case 3: XFillRectangle(dpy, win, gc, - border_x - bw + grid_width * i, - border_y + bw + grid_height * j, - grid_width, grid_height - (bw+bw)); - break; + case WALL_TOP: + XFillRectangle(dpy, win, gc, + border_x + bw + grid_width * i, + border_y - bw + grid_height * j, + grid_width - (bw+bw), grid_height); + break; + case WALL_RIGHT: + XFillRectangle(dpy, win, gc, + border_x + bw + grid_width * i, + border_y + bw + grid_height * j, + grid_width, grid_height - (bw+bw)); + break; + case WALL_BOTTOM: + XFillRectangle(dpy, win, gc, + border_x + bw + grid_width * i, + border_y + bw + grid_height * j, + grid_width - (bw+bw), grid_height); + break; + case WALL_LEFT: + XFillRectangle(dpy, win, gc, + border_x - bw + grid_width * i, + border_y + bw + grid_height * j, + grid_width, grid_height - (bw+bw)); + break; } XSync (dpy, False); } +int +longdeadend_p(int x1, int y1, int x2, int y2, int endwall) +{ + int dx = x2 - x1, dy = y2 - y1; + int sidewalls; -static void -solve_maze() /* solve it with graphical feedback */ + sidewalls = endwall | (endwall >> 2 | endwall << 2); + sidewalls = ~sidewalls & WALL_ANY; + + while((maze[x2][y2] & WALL_ANY) == sidewalls) + { + x2 += dx; + y2 += dy; + } + + if((maze[x2][y2] & WALL_ANY) == (sidewalls | endwall)) + { + endwall = (endwall >> 2 | endwall << 2) & WALL_ANY; + while(x1 != x2 || y1 != y2) + { + x1 += dx; + y1 += dy; + draw_solid_square(x1, y1, endwall, sgc); + maze[x1][y1] |= SOLVER_VISIT; + } + return 1; + } + else + return 0; +} + +/* Find all dead regions -- areas from which the goal cannot be reached -- + and mark them visited. */ +void +find_dead_regions(void) { - int i; - - - /* plug up the surrounding wall */ - maze[start_x][start_y] |= (WALL_TOP >> start_dir); - maze[end_x][end_y] |= (WALL_TOP >> end_dir); - - /* initialize search path */ - i = 0; - path[i].x = end_x; - path[i].y = end_y; - path[i].dir = -1; - - /* do it */ - while (1) { - if ( ++path[i].dir >= 4 ) { - i--; - draw_solid_square( (int)(path[i].x), (int)(path[i].y), - (int)(path[i].dir), cgc); - } - else if ( ! (maze[path[i].x][path[i].y] & - (WALL_TOP >> path[i].dir)) && - ( (i == 0) || ( (path[i].dir != - (int)(path[i-1].dir+2)%4) ) ) ) { - enter_square(i); - i++; - if ( maze[path[i].x][path[i].y] & START_SQUARE ) { - return; + int x, y, flipped; + + /* Find all not SOLVER_VISIT squares bordering NOT_DEAD squares + and mark them NOT_DEAD also. Repeat until no more such squares. */ + maze[start_x][start_y] |= NOT_DEAD; + + do + { + flipped = 0; + for(x = 0; x < maze_size_x; x++) + for(y = 0; y < maze_size_y; y++) + if(!(maze[x][y] & (SOLVER_VISIT | NOT_DEAD)) + && ( (x && (maze[x-1][y] & NOT_DEAD)) + || (y && (maze[x][y-1] & NOT_DEAD)))) + { + flipped = 1; + maze[x][y] |= NOT_DEAD; + } + for(x = maze_size_x-1; x >= 0; x--) + for(y = maze_size_y-1; y >= 0; y--) + if(!(maze[x][y] & (SOLVER_VISIT | NOT_DEAD)) + && ( (x != maze_size_x-1 && (maze[x+1][y] & NOT_DEAD)) + || (y != maze_size_y-1 && (maze[x][y+1] & NOT_DEAD)))) + { + flipped = 1; + maze[x][y] |= NOT_DEAD; + } + } + while(flipped); + + for (y = 0; y < maze_size_y; y++) + for (x = 0; x < maze_size_x; x++) + { + if (maze[x][y] & NOT_DEAD) + maze[x][y] &= ~NOT_DEAD; + else if (!(maze[x][y] & SOLVER_VISIT)) + { + maze[x][y] |= SOLVER_VISIT; + if((x < logo_x || x > logo_x + logo_width / grid_width) || + (y < logo_y || y > logo_y + logo_height / grid_height)) + { + if (!maze[x][y] & WALL_ANY) + XFillRectangle(dpy, win, ugc, + border_x + bw + grid_width * x, + border_y + bw + grid_height * y, + grid_width - (bw+bw), grid_height - (bw+bw)); + else + { + if (! (maze[x][y] & WALL_LEFT)) + draw_solid_square(x, y, WALL_LEFT, ugc); + if (! (maze[x][y] & WALL_RIGHT)) + draw_solid_square(x, y, WALL_RIGHT, ugc); + if (! (maze[x][y] & WALL_TOP)) + draw_solid_square(x, y, WALL_TOP, ugc); + if (! (maze[x][y] & WALL_BOTTOM)) + draw_solid_square(x, y, WALL_BOTTOM, ugc); + } + } + } } - } - if (check_events()) return; - /* Abort solve on expose - cheapo repaint strategy */ - if (solve_delay) usleep (solve_delay); - } -} + XSync(dpy, False); +} + +static void +solve_maze (void) /* solve it with graphical feedback */ +{ + int i, dir, from, x, y, ways, bt = 0; + + /* plug up the surrounding wall */ + maze[end_x][end_y] |= (WALL_TOP >> end_dir); + + /* initialize search path */ + i = 0; + path[i].x = end_x; + path[i].y = end_y; + path[i].dir = 0; + maze[end_x][end_y] |= SOLVER_VISIT; + + /* do it */ + while (1) + { + if ( maze[path[i].x][path[i].y] & START_SQUARE ) + return; + + /* Abort solve on expose - cheapo repaint strategy */ + if (check_events()) return; + + if (solve_delay) usleep (solve_delay); + + if(!path[i].dir) + { + ways = 0; + /* First visit this square. Which adjacent squares are open? */ + for(dir = WALL_TOP; dir & WALL_ANY; dir >>= 1) + { + if(maze[path[i].x][path[i].y] & dir) + continue; + + y = path[i].y - !!(dir & WALL_TOP) + !!(dir & WALL_BOTTOM); + x = path[i].x + !!(dir & WALL_RIGHT) - !!(dir & WALL_LEFT); + + if(maze[x][y] & SOLVER_VISIT) + continue; + + from = (dir << 2 & WALL_ANY) | (dir >> 2 & WALL_ANY); + /* don't enter obvious dead ends */ + if(((maze[x][y] & WALL_ANY) | from) != WALL_ANY) + { + if(!longdeadend_p(path[i].x, path[i].y, x, y, dir)) + ways |= dir; + } + else + { + draw_solid_square(x, y, from, sgc); + maze[x][y] |= SOLVER_VISIT; + } + } + } + else + ways = path[i].ways; + /* ways now has a bitmask of open paths. */ + + if(!ways) + goto backtrack; + + x = path[i].x - start_x; + y = path[i].y - start_y; + /* choice one */ + if(abs(y) <= abs(x)) + dir = (x > 0) ? WALL_LEFT : WALL_RIGHT; + else + dir = (y > 0) ? WALL_TOP : WALL_BOTTOM; + + if(dir & ways) + goto found; + + /* choice two */ + switch(dir) + { + case WALL_LEFT: + case WALL_RIGHT: + dir = (y > 0) ? WALL_TOP : WALL_BOTTOM; break; + case WALL_TOP: + case WALL_BOTTOM: + dir = (x > 0) ? WALL_LEFT : WALL_RIGHT; + } + + if(dir & ways) + goto found; + + /* choice three */ + + dir = (dir << 2 & WALL_ANY) | (dir >> 2 & WALL_ANY); + if(dir & ways) + goto found; + + /* choice four */ + dir = ways; + if(!dir) + goto backtrack; + + found: + bt = 0; + ways &= ~dir; /* tried this one */ + + y = path[i].y - !!(dir & WALL_TOP) + !!(dir & WALL_BOTTOM); + x = path[i].x + !!(dir & WALL_RIGHT) - !!(dir & WALL_LEFT); + + /* advance in direction dir */ + path[i].dir = dir; + path[i].ways = ways; + draw_solid_square(path[i].x, path[i].y, dir, tgc); + + i++; + path[i].dir = 0; + path[i].ways = 0; + path[i].x = x; + path[i].y = y; + maze[x][y] |= SOLVER_VISIT; + continue; + backtrack: + if(i == 0) + { + printf("Unsolvable maze.\n"); + return; + } + if(!bt) + find_dead_regions(); + bt = 1; + from = path[i-1].dir; + from = (from << 2 & WALL_ANY) | (from >> 2 & WALL_ANY); + + draw_solid_square(path[i].x, path[i].y, from, cgc); + i--; + } +} + +#if 0 static void -enter_square(n) /* move into a neighboring square */ - int n; +enter_square (int n) /* move into a neighboring square */ { draw_solid_square( (int)path[n].x, (int)path[n].y, (int)path[n].dir, tgc); @@ -608,12 +1532,11 @@ enter_square(n) /* move into a neighboring square */ break; } } - -/* ---- */ +#endif /* 0 */ /* - * jmr additions for Jamie Zawinski's screensaver stuff, + * jmr additions for Jamie Zawinski's screensaver stuff, * note that the code above this has probably been hacked about in some * arbitrary way. */ @@ -621,14 +1544,20 @@ enter_square(n) /* move into a neighboring square */ char *progclass = "Maze"; char *defaults[] = { - "Maze.background: black", /* to placate SGI */ - "Maze.foreground: white", /* to placate SGI */ + ".background: black", + ".foreground: white", "*gridSize: 0", "*solveDelay: 5000", "*preDelay: 2000000", "*postDelay: 4000000", "*liveColor: green", "*deadColor: red", + "*skipColor: orange", + "*surroundColor: slateblue", + "*generator: -1", + "*maxLength: 5", + "*syncDraw: False", + "*bridge: False", #ifdef XROGER "*logoColor: red3", #endif @@ -641,25 +1570,36 @@ XrmOptionDescRec options[] = { { "-pre-delay", ".preDelay", XrmoptionSepArg, 0 }, { "-post-delay", ".postDelay", XrmoptionSepArg, 0 }, { "-live-color", ".liveColor", XrmoptionSepArg, 0 }, - { "-dead-color", ".deadColor", XrmoptionSepArg, 0 } + { "-dead-color", ".deadColor", XrmoptionSepArg, 0 }, + { "-skip-color", ".skipColor", XrmoptionSepArg, 0 }, + { "-surround-color", ".surroundColor",XrmoptionSepArg, 0 }, + { "-generator", ".generator", XrmoptionSepArg, 0 }, + { "-max-length", ".maxLength", XrmoptionSepArg, 0 }, + { "-bridge", ".bridge", XrmoptionNoArg, "True" }, + { "-no-bridge", ".bridge", XrmoptionNoArg, "False" }, + { 0, 0, 0, 0 } }; -int options_size = (sizeof(options)/sizeof(options[0])); +#ifdef XROGER +extern void skull (Display *, Window, GC, GC, int, int, int, int); +#endif -void screenhack(display,window) - Display *display; - Window window; +void +screenhack(Display *display, Window window) { Pixmap gray; - int size, root; + int size, root, generator, this_gen; XWindowAttributes xgwa; - unsigned long bg, fg, pfg, pbg, lfg; + unsigned long bg, fg, pfg, pbg, lfg, sfg, ufg; size = get_integer_resource ("gridSize", "Dimension"); root = get_boolean_resource("root", "Boolean"); solve_delay = get_integer_resource ("solveDelay", "Integer"); pre_solve_delay = get_integer_resource ("preDelay", "Integer"); post_solve_delay = get_integer_resource ("postDelay", "Integer"); + generator = get_integer_resource("generator", "Integer"); + max_length = get_integer_resource("maxLength", "Integer"); + bridge_p = get_boolean_resource("bridge", "Boolean"); if (size < 2) size = 7 + (random () % 30); grid_width = grid_height = size; @@ -675,12 +1615,21 @@ void screenhack(display,window) set_maze_sizes (xgwa.width, xgwa.height); if (! root) - XSelectInput (dpy, win, ExposureMask|ButtonPressMask|StructureNotifyMask); + { + XWindowAttributes xgwa; + XGetWindowAttributes (dpy, window, &xgwa); + XSelectInput (dpy, win, + xgwa.your_event_mask | ExposureMask | + ButtonPressMask |StructureNotifyMask); + } - gc = XCreateGC(dpy, win, 0, 0); + gc = XCreateGC(dpy, win, 0, 0); cgc = XCreateGC(dpy, win, 0, 0); - tgc = XCreateGC(dpy,win,0,0); + tgc = XCreateGC(dpy, win, 0, 0); + sgc = XCreateGC(dpy, win, 0, 0); + ugc = XCreateGC(dpy, win, 0, 0); logo_gc = XCreateGC(dpy, win, 0, 0); + erase_gc = XCreateGC(dpy, win, 0, 0); gray = XCreateBitmapFromData (dpy,win,gray1_bits,gray1_width,gray1_height); @@ -689,6 +1638,8 @@ void screenhack(display,window) lfg = get_pixel_resource ("logoColor", "Foreground", dpy, xgwa.colormap); pfg = get_pixel_resource ("liveColor", "Foreground", dpy, xgwa.colormap); pbg = get_pixel_resource ("deadColor", "Foreground", dpy, xgwa.colormap); + sfg = get_pixel_resource ("skipColor", "Foreground", dpy, xgwa.colormap); + ufg = get_pixel_resource ("surroundColor", "Foreground", dpy, xgwa.colormap); if (mono_p) lfg = pfg = fg; if (lfg == bg) @@ -702,18 +1653,27 @@ void screenhack(display,window) XSetBackground (dpy, cgc, bg); XSetForeground (dpy, tgc, pfg); XSetBackground (dpy, tgc, bg); + XSetForeground (dpy, sgc, sfg); + XSetBackground (dpy, sgc, bg); + XSetForeground (dpy, ugc, ufg); + XSetBackground (dpy, ugc, bg); XSetForeground (dpy, logo_gc, lfg); XSetBackground (dpy, logo_gc, bg); + XSetForeground (dpy, erase_gc, bg); + XSetBackground (dpy, erase_gc, bg); XSetStipple (dpy, cgc, gray); XSetFillStyle (dpy, cgc, FillOpaqueStippled); + XSetStipple (dpy, sgc, gray); + XSetFillStyle (dpy, sgc, FillOpaqueStippled); + XSetStipple (dpy, ugc, gray); + XSetFillStyle (dpy, ugc, FillOpaqueStippled); #ifdef XROGER { int w, h; XGCValues gcv; GC draw_gc, erase_gc; - extern void skull (); /* round up to grid size */ w = ((logo_width / grid_width) + 1) * grid_width; h = ((logo_height / grid_height) + 1) * grid_height; @@ -736,10 +1696,11 @@ void screenhack(display,window) } #endif XMapRaised(dpy, win); - srandom(getpid()); restart = root; + sync_p = !(random() % 10); + while (1) { /* primary execution loop [ rhess ] */ if (check_events()) continue ; if (restart || stop) goto pop; @@ -752,7 +1713,22 @@ void screenhack(display,window) draw_maze_border(); break; case 3: - create_maze(); + 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; + } break; case 4: XSync (dpy, False); @@ -765,6 +1741,7 @@ void screenhack(display,window) XSync (dpy, False); usleep (post_solve_delay); state = 0 ; + erase_full_window(display, window); break; default: abort (); @@ -781,6 +1758,7 @@ void screenhack(display,window) set_maze_sizes (wattr.width, wattr.height); XClearWindow (dpy, win); XSync (dpy, False); + sync_p = !(random() % 10); } } }