+ if(s1<s2)
+ sets[s2] = s1;
+ else
+ sets[s1] = s2;
+}
+
+/* Exitialise the sets. */
+static void
+exit_sets(void)
+{
+ if(hedges)
+ free(hedges);
+ hedges = 0;
+ if(sets)
+ free(sets);
+ sets = 0;
+}
+
+#if DEBUG_SETS
+/* Temporary hack. */
+static void
+show_set(int num, GC gc)
+{
+ int x, y, set;
+
+ set = get_set(num);
+
+ for(x = 0; x < maze_size_x; x++)
+ for(y = 0; y < maze_size_y; y++)
+ {
+ if(get_set(x+y*maze_size_x)==set)
+ {
+ XFillRectangle(dpy, win, gc, border_x + bw + grid_width * x,
+ border_y + bw + grid_height * y,
+ grid_width-2*bw , grid_height-2*bw);
+ }
+ }
+}
+#endif
+
+/* 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;
+#if DEBUG_SETS
+ int cont = 0;
+ char c;
+#endif
+
+ /* Do almost all the setup. */
+ init_sets();
+
+ /* Start running through the hedges. */
+ for(i = 0; i < 2*maze_size_x*maze_size_y; 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)%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;
+ }
+ }
+ }
+