X-Git-Url: http://git.hungrycats.org/cgi-bin/gitweb.cgi?a=blobdiff_plain;f=hacks%2Fmaze.c;h=dbb77535155b64474d892a50d4c8a032fc9ba6cb;hb=0bd2eabab3e404c6769fe8f59b639275e960c415;hp=22af1d6a848450fb7cf0bad3d21c8b0ea71a4908;hpb=f3e0240915ed9f9b3a61781f5c7002d587563fe0;p=xscreensaver diff --git a/hacks/maze.c b/hacks/maze.c index 22af1d6a..dbb77535 100644 --- a/hacks/maze.c +++ b/hacks/maze.c @@ -1,6 +1,9 @@ /****************************************************************************** * [ maze ] ... * + * 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 @@ -46,6 +49,7 @@ *****************************************************************************/ #include "screenhack.h" +#include "erase.h" #define XROGER @@ -81,6 +85,7 @@ static int solve_delay, pre_solve_delay, post_solve_delay; #define DOOR_OUT_BOTTOM 0x20 #define DOOR_OUT_LEFT 0x10 +#define SOLVER_VISIT 0x4 #define START_SQUARE 0x2 #define END_SQUARE 0x1 @@ -113,13 +118,15 @@ 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, 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 (void) /* X event handler [ rhess ] */ @@ -180,6 +187,8 @@ static void 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 -create_maze (void) /* create a maze layout given the intiialized maze */ +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 (void) /* create a maze layout given the initialized maze */ { 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; @@ -353,7 +971,7 @@ choose_door (void) /* 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; @@ -369,7 +987,7 @@ choose_door (void) /* 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; @@ -385,7 +1003,7 @@ choose_door (void) /* 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; @@ -401,7 +1019,7 @@ choose_door (void) /* 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; @@ -482,7 +1100,7 @@ draw_maze_border (void) /* draw the maze outline */ static void -draw_wall(int i, int j, int dir) /* draw a single wall */ +draw_wall(int i, int j, int dir, GC gc) /* draw a single wall */ { switch (dir) { case 0: @@ -514,9 +1132,78 @@ draw_wall(int i, int j, int dir) /* draw a single wall */ border_y + grid_height * (j+1)); break; } + if(sync_p) + XSync(dpy, False); } -static 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(int i, int j, /* draw a solid square in a square */ @@ -552,8 +1239,9 @@ static void solve_maze (void) /* solve it with graphical feedback */ { int i; - - + int step_x[4] = { 0, 1, 0, -1 }; + int step_y[4] = { -1, 0, 1, 0 }; + /* plug up the surrounding wall */ maze[start_x][start_y] |= (WALL_TOP >> start_dir); maze[end_x][end_y] |= (WALL_TOP >> end_dir); @@ -563,6 +1251,7 @@ solve_maze (void) /* solve it with graphical feedback */ path[i].x = end_x; path[i].y = end_y; path[i].dir = -1; + maze[end_x][end_y] |= SOLVER_VISIT; /* do it */ while (1) { @@ -572,15 +1261,23 @@ solve_maze (void) /* solve it with graphical feedback */ border_y + bw + grid_height * (int)(path[i].y), grid_width - (bw+bw), grid_height - (bw+bw)); i--; + if(i<0) /* Can't solve this maze. */ + { + printf("Unsolvable maze.\n"); + return; + } 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); + else if ( (! (maze[path[i].x][path[i].y] & (WALL_TOP >> path[i].dir))) && + (!( maze[path[i].x+step_x[path[i].dir]] + [path[i].y+step_y[path[i].dir]]&SOLVER_VISIT)) ) { + path[i+1].x = path[i].x+step_x[path[i].dir]; + path[i+1].y = path[i].y+step_y[path[i].dir]; + path[i+1].dir = -1; + draw_solid_square(path[i].x, path[i].y, path[i].dir, tgc); i++; + maze[path[i].x][path[i].y] |= SOLVER_VISIT; if ( maze[path[i].x][path[i].y] & START_SQUARE ) { return; } @@ -592,6 +1289,7 @@ solve_maze (void) /* solve it with graphical feedback */ } +#if 0 static void enter_square (int n) /* move into a neighboring square */ { @@ -614,6 +1312,7 @@ enter_square (int n) /* move into a neighboring square */ break; } } +#endif /* 0 */ /* @@ -625,14 +1324,18 @@ enter_square (int 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", + "*generator: -1", + "*maxLength: 5", + "*syncDraw: False", + "*bridge: False", #ifdef XROGER "*logoColor: red3", #endif @@ -646,6 +1349,10 @@ XrmOptionDescRec options[] = { { "-post-delay", ".postDelay", XrmoptionSepArg, 0 }, { "-live-color", ".liveColor", XrmoptionSepArg, 0 }, { "-dead-color", ".deadColor", XrmoptionSepArg, 0 }, + { "-generator", ".generator", XrmoptionSepArg, 0 }, + { "-max-length", ".maxLength", XrmoptionSepArg, 0 }, + { "-bridge", ".bridge", XrmoptionNoArg, "True" }, + { "-no-bridge", ".bridge", XrmoptionNoArg, "False" }, { 0, 0, 0, 0 } }; @@ -657,7 +1364,7 @@ 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; @@ -666,6 +1373,9 @@ screenhack(Display *display, Window window) 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; @@ -687,6 +1397,7 @@ screenhack(Display *display, Window window) cgc = XCreateGC(dpy, win, 0, 0); tgc = 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); @@ -710,6 +1421,8 @@ screenhack(Display *display, Window window) XSetBackground (dpy, tgc, 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); @@ -741,10 +1454,11 @@ screenhack(Display *display, Window 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; @@ -757,7 +1471,22 @@ screenhack(Display *display, Window 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); @@ -770,6 +1499,7 @@ screenhack(Display *display, Window window) XSync (dpy, False); usleep (post_solve_delay); state = 0 ; + erase_full_window(display, window); break; default: abort (); @@ -786,6 +1516,7 @@ screenhack(Display *display, Window window) set_maze_sizes (wattr.width, wattr.height); XClearWindow (dpy, win); XSync (dpy, False); + sync_p = !(random() % 10); } } }