+ st->logo_y = st->logo_x = -1;
+
+ /* mask out the fps area */
+ if (st->fps_width > 0)
+ {
+ int fpsw = 1 + st->fps_width / st->grid_width;
+ int fpsh = 1 + st->fps_height / st->grid_width;
+
+ /* if the chosen logo position overlapped the fps area, try again! */
+ if (st->logo_x < fpsw+3 && st->logo_y+logoh > st->maze_size_y-fpsh-4)
+ goto AGAIN;
+
+ /* if the start or end point is inside the fps area, try again! */
+ if ((st->start_x <= fpsw && st->start_y >= st->maze_size_y-fpsh-1) ||
+ (st->end_x <= fpsw && st->end_y >= st->maze_size_y-fpsh-1))
+ goto AGAIN;
+
+ for (i=0; i<fpsw; i++)
+ for (j=0; j<fpsh; j++) {
+ /* mark as having doors to prevent these cells being used in maze.
+ mark as visit to prevent it being colored "unreachable". */
+ st->maze[i][st->maze_size_y - j - 1] |= DOOR_IN_ANY|SOLVER_VISIT;
+ /* take off left/bottom wall or the FPS text overlaps it */
+ st->maze[i][st->maze_size_y - j - 1] &= ~(WALL_BOTTOM|WALL_LEFT);
+ }
+ }
+}
+
+
+/****************************************************************************
+ Generator 2: Set-based maze generator.
+
+ 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.
+
+ This is essentially the "Kruskal" algorithm.
+
+ ****************************************************************************/
+
+static void mask_out_set_rect(struct state *st, int x, int y, int w, int h);
+
+/* Initialise the sets. */
+static void
+init_sets(struct state *st)
+{
+ int i, t, r;
+
+ if(st->sets)
+ free(st->sets);
+ st->sets = (int *)malloc(st->maze_size_x*st->maze_size_y*sizeof(int));
+ if(!st->sets)
+ abort();
+ for(i = 0; i < st->maze_size_x*st->maze_size_y; i++)
+ {
+ st->sets[i] = i;
+ }
+
+ if(st->hedges)
+ free(st->hedges);
+ st->hedges = (int *)malloc(st->maze_size_x*st->maze_size_y*2*sizeof(int));
+ if(!st->hedges)
+ abort();
+ for(i = 0; i < st->maze_size_x*st->maze_size_y*2; i++)
+ {
+ st->hedges[i] = i;
+ }
+ /* Mask out outside walls. */
+ for(i = 0; i < st->maze_size_y; i++)
+ {
+ st->hedges[2*((st->maze_size_x)*i+st->maze_size_x-1)+1] = -1;
+ }
+ for(i = 0; i < st->maze_size_x; i++)
+ {
+ st->hedges[2*((st->maze_size_y-1)*st->maze_size_x+i)] = -1;
+ }
+
+ /* Mask out the logo area. */
+ if(st->logo_x!=-1)
+ {
+ int logow = 1 + st->logo_width / st->grid_width;
+ int logoh = 1 + st->logo_height / st->grid_height;
+ mask_out_set_rect(st, st->logo_x, st->logo_y, logow, logoh);
+ }
+
+ /* Mask out the FPS area. */
+ if(st->fps_width > 0)
+ {
+ int fpsw = 1 + st->fps_width / st->grid_width;
+ int fpsh = 1 + st->fps_height / st->grid_height;
+ mask_out_set_rect(st, 0, st->maze_size_y-fpsh, fpsw, fpsh);
+ }
+
+ for(i = 0; i < st->maze_size_x*st->maze_size_y*2; i++)
+ {
+ t = st->hedges[i];
+ r = random()%(st->maze_size_x*st->maze_size_y*2);
+ st->hedges[i] = st->hedges[r];
+ st->hedges[r] = t;
+ }
+}
+
+/* Get the representative of a set. */
+static int
+get_set(struct state *st, int num)
+{
+ int s;
+
+ if(st->sets[num]==num)
+ return num;
+ else
+ {
+ s = get_set(st, st->sets[num]);
+ st->sets[num] = s;
+ return s;
+ }
+}
+
+/* Join two sets together. */
+static void
+join_sets(struct state *st, int num1, int num2)
+{
+ int s1, s2;
+
+ s1 = get_set(st, num1);
+ s2 = get_set(st, num2);
+
+ if(s1<s2)
+ st->sets[s2] = s1;
+ else
+ st->sets[s1] = s2;
+}
+
+/* Exitialise the sets. */
+static void
+exit_sets(struct state *st)
+{
+ if(st->hedges)
+ free(st->hedges);
+ st->hedges = 0;
+ if(st->sets)
+ free(st->sets);
+ st->sets = 0;
+}
+
+
+static void
+set_create_maze(struct state *st)
+{
+ int i, h, xx, yy, dir, v, w;
+
+ /* Do almost all the setup. */
+ init_sets(st);
+
+ /* Start running through the hedges. */
+ for(i = 0; i < 2*st->maze_size_x*st->maze_size_y; i++)
+ {
+ h = st->hedges[i];
+
+ /* This one is in the logo or outside border. */
+ if(h==-1)
+ continue;
+
+ dir = h%2?1:2;
+ xx = (h>>1)%st->maze_size_x;
+ yy = (h>>1)/st->maze_size_x;
+
+ v = xx;
+ w = yy;
+ switch(dir)
+ {
+ case 1:
+ v++;
+ break;
+ case 2:
+ w++;
+ break;
+ }
+
+ if(get_set(st, xx+yy*st->maze_size_x)!=get_set(st, v+w*st->maze_size_x))
+ {
+ join_sets(st, xx+yy*st->maze_size_x, v+w*st->maze_size_x);
+ /* Don't draw the wall. */
+ }
+ else
+ {
+ /* Don't join the sets. */
+ build_wall(st, xx, yy, dir);
+ }
+ }
+
+ /* Free some memory. */
+ exit_sets(st);
+}
+
+/* mark a rectangle as being unavailable for usage in the maze */
+static void
+mask_out_set_rect(struct state *st, int x, int y, int w, int h)
+{
+ int xx, yy;
+ for(xx = x; xx < x+w; xx++)
+ for(yy = y; yy < y+h; yy++)
+ {
+ st->hedges[2*(xx+st->maze_size_x*yy)+1] = -1;
+ st->hedges[2*(xx+st->maze_size_x*yy)] = -1;
+ }
+ for(xx = x; xx < x+w; xx++)
+ {
+ build_wall(st, xx, y, 0);
+ build_wall(st, xx, y+h, 0);
+ st->hedges[2*(xx+st->maze_size_x*(y-1))] = -1;
+ }
+ for(yy = y; yy < y+h; yy++)
+ {
+ build_wall(st, x, yy, 3);
+ build_wall(st, x+w, yy, 3);
+ st->hedges[2*(x-1+st->maze_size_x*yy)+1] = -1;
+ }
+}
+
+
+/****************************************************************************
+ Generator 1: Wall-building maze generator.
+
+ 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.
+
+ This is essentially the "Prim" algorithm.
+ ****************************************************************************/
+
+static void alt_mask_out_rect(struct state *st, char *corners,
+ int x, int y, int w, int h);
+
+static void
+alt_create_maze(struct state *st)
+{
+ char *corners;
+ int *c_idx;
+ int i, j, height, width, open_corners, k, dir, xx, yy;
+
+ height = st->maze_size_y+1;
+ width = st->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;
+ }
+
+ /* mask out the logo area */
+ if(st->logo_x!=-1)
+ {
+ int logow = 1 + st->logo_width / st->grid_width;
+ int logoh = 1 + st->logo_height / st->grid_height;
+ alt_mask_out_rect (st, corners, st->logo_x, st->logo_y, logow, logoh);
+ }
+
+ /* mask out the FPS area */
+ if(st->fps_width>0)
+ {
+ int fpsw = 1 + st->fps_width / st->grid_width;
+ int fpsh = 1 + st->fps_height / st->grid_height;
+ alt_mask_out_rect (st, corners, 0, st->maze_size_y-fpsh, fpsw, fpsh);
+ }
+
+ /* 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]])
+ {
+ xx = c_idx[i]%width;
+ yy = c_idx[i]/width;
+ /* Choose a random direction. */
+ dir = random()%4;
+
+ k = 0;
+ /* Measure the length of the wall we'd draw. */
+ while(!corners[xx+width*yy])
+ {
+ k++;
+ switch(dir)
+ {
+ case 0:
+ yy--;
+ break;
+ case 1:
+ xx++;
+ break;
+ case 2:
+ yy++;
+ break;
+ case 3:
+ xx--;
+ break;
+ }
+ }
+
+ if(k<=st->max_length)
+ {
+ xx = c_idx[i]%width;
+ yy = c_idx[i]/width;
+
+ /* Draw a wall until we hit something. */
+ while(!corners[xx+width*yy])
+ {
+ open_corners--;
+ corners[xx+width*yy] = 1;
+ switch(dir)
+ {
+ case 0:
+ build_wall(st, xx-1, yy-1, 1);
+ yy--;
+ break;
+ case 1:
+ build_wall(st, xx, yy, 0);
+ xx++;
+ break;
+ case 2:
+ build_wall(st, xx, yy, 3);
+ yy++;
+ break;
+ case 3:
+ build_wall(st, xx-1, yy-1, 2);
+ xx--;
+ break;
+ }
+ }
+ }
+ }
+ }
+ }
+
+ /* Free some memory we used. */
+ free(corners);
+ free(c_idx);
+}
+
+
+/* mark a rectangle as being unavailable for usage in the maze */
+static void
+alt_mask_out_rect(struct state *st, char *corners, int x, int y, int w, int h)
+{
+ int i, j, xx, yy;
+ int mazew = st->maze_size_x+1;
+
+ for(i = x; i <= x+w; i++)
+ for(j = y; j <= y+h; j++)
+ corners[i+mazew*j] = 1;
+
+ for(xx = x; xx < x+w; xx++)
+ {
+ build_wall(st, xx, y, 0);
+ if (y+h < st->maze_size_y)
+ build_wall(st, xx, y+h, 0);
+ }
+ for(yy = y; yy < y+h; yy++)
+ {
+ if (x > 0)
+ build_wall(st, x, yy, 3);
+ build_wall(st, x+w, yy, 3);
+ }