+ j = TRUE;
+ for (i = 0; i < w*h; i++) {
+ if (tilestate[i * 4 + 1] == 255) {
+ assert(tilestate[i * 4 + 0] != 255);
+ tiles[i] = tilestate[i * 4] | LOCKED;
+ } else {
+ tiles[i] &= ~LOCKED;
+ j = FALSE;
+ }
+ }
+
+ /*
+ * Free up working space.
+ */
+ todo_free(todo);
+ sfree(tilestate);
+ sfree(edgestate);
+ sfree(deadends);
+ sfree(equivalence);
+
+ return j;
+}
+
+/* ----------------------------------------------------------------------
+ * Randomly select a new game description.
+ */
+
+/*
+ * Function to randomly perturb an ambiguous section in a grid, to
+ * attempt to ensure unique solvability.
+ */
+static void perturb(int w, int h, unsigned char *tiles, int wrapping,
+ random_state *rs, int startx, int starty, int startd)
+{
+ struct xyd *perimeter, *perim2, *loop[2], looppos[2];
+ int nperim, perimsize, nloop[2], loopsize[2];
+ int x, y, d, i;
+
+ /*
+ * We know that the tile at (startx,starty) is part of an
+ * ambiguous section, and we also know that its neighbour in
+ * direction startd is fully specified. We begin by tracing all
+ * the way round the ambiguous area.
+ */
+ nperim = perimsize = 0;
+ perimeter = NULL;
+ x = startx;
+ y = starty;
+ d = startd;
+#ifdef PERTURB_DIAGNOSTICS
+ printf("perturb %d,%d:%d\n", x, y, d);
+#endif
+ do {
+ int x2, y2, d2;
+
+ if (nperim >= perimsize) {
+ perimsize = perimsize * 3 / 2 + 32;
+ perimeter = sresize(perimeter, perimsize, struct xyd);
+ }
+ perimeter[nperim].x = x;
+ perimeter[nperim].y = y;
+ perimeter[nperim].direction = d;
+ nperim++;
+#ifdef PERTURB_DIAGNOSTICS
+ printf("perimeter: %d,%d:%d\n", x, y, d);
+#endif
+
+ /*
+ * First, see if we can simply turn left from where we are
+ * and find another locked square.
+ */
+ d2 = A(d);
+ OFFSETWH(x2, y2, x, y, d2, w, h);
+ if ((!wrapping && (abs(x2-x) > 1 || abs(y2-y) > 1)) ||
+ (tiles[y2*w+x2] & LOCKED)) {
+ d = d2;
+ } else {
+ /*
+ * Failing that, step left into the new square and look
+ * in front of us.
+ */
+ x = x2;
+ y = y2;
+ OFFSETWH(x2, y2, x, y, d, w, h);
+ if ((wrapping || (abs(x2-x) <= 1 && abs(y2-y) <= 1)) &&
+ !(tiles[y2*w+x2] & LOCKED)) {
+ /*
+ * And failing _that_, we're going to have to step
+ * forward into _that_ square and look right at the
+ * same locked square as we started with.
+ */
+ x = x2;
+ y = y2;
+ d = C(d);
+ }
+ }
+
+ } while (x != startx || y != starty || d != startd);
+
+ /*
+ * Our technique for perturbing this ambiguous area is to
+ * search round its edge for a join we can make: that is, an
+ * edge on the perimeter which is (a) not currently connected,
+ * and (b) connecting it would not yield a full cross on either
+ * side. Then we make that join, search round the network to
+ * find the loop thus constructed, and sever the loop at a
+ * randomly selected other point.
+ */
+ perim2 = snewn(nperim, struct xyd);
+ memcpy(perim2, perimeter, nperim * sizeof(struct xyd));
+ /* Shuffle the perimeter, so as to search it without directional bias. */
+ for (i = nperim; --i ;) {
+ int j = random_upto(rs, i+1);
+ struct xyd t;
+
+ t = perim2[j];
+ perim2[j] = perim2[i];
+ perim2[i] = t;
+ }
+ for (i = 0; i < nperim; i++) {
+ int x2, y2;
+
+ x = perim2[i].x;
+ y = perim2[i].y;
+ d = perim2[i].direction;
+
+ OFFSETWH(x2, y2, x, y, d, w, h);
+ if (!wrapping && (abs(x2-x) > 1 || abs(y2-y) > 1))
+ continue; /* can't link across non-wrapping border */
+ if (tiles[y*w+x] & d)
+ continue; /* already linked in this direction! */
+ if (((tiles[y*w+x] | d) & 15) == 15)
+ continue; /* can't turn this tile into a cross */
+ if (((tiles[y2*w+x2] | F(d)) & 15) == 15)
+ continue; /* can't turn other tile into a cross */
+
+ /*
+ * We've found the point at which we're going to make a new
+ * link.
+ */
+#ifdef PERTURB_DIAGNOSTICS
+ printf("linking %d,%d:%d\n", x, y, d);
+#endif
+ tiles[y*w+x] |= d;
+ tiles[y2*w+x2] |= F(d);
+
+ break;
+ }
+ sfree(perim2);
+
+ if (i == nperim)
+ return; /* nothing we can do! */
+
+ /*
+ * Now we've constructed a new link, we need to find the entire
+ * loop of which it is a part.
+ *
+ * In principle, this involves doing a complete search round
+ * the network. However, I anticipate that in the vast majority
+ * of cases the loop will be quite small, so what I'm going to
+ * do is make _two_ searches round the network in parallel, one
+ * keeping its metaphorical hand on the left-hand wall while
+ * the other keeps its hand on the right. As soon as one of
+ * them gets back to its starting point, I abandon the other.
+ */
+ for (i = 0; i < 2; i++) {
+ loopsize[i] = nloop[i] = 0;
+ loop[i] = NULL;
+ looppos[i].x = x;
+ looppos[i].y = y;
+ looppos[i].direction = d;
+ }
+ while (1) {
+ for (i = 0; i < 2; i++) {
+ int x2, y2, j;
+
+ x = looppos[i].x;
+ y = looppos[i].y;
+ d = looppos[i].direction;
+
+ OFFSETWH(x2, y2, x, y, d, w, h);
+
+ /*
+ * Add this path segment to the loop, unless it exactly
+ * reverses the previous one on the loop in which case
+ * we take it away again.
+ */
+#ifdef PERTURB_DIAGNOSTICS
+ printf("looppos[%d] = %d,%d:%d\n", i, x, y, d);
+#endif
+ if (nloop[i] > 0 &&
+ loop[i][nloop[i]-1].x == x2 &&
+ loop[i][nloop[i]-1].y == y2 &&
+ loop[i][nloop[i]-1].direction == F(d)) {
+#ifdef PERTURB_DIAGNOSTICS
+ printf("removing path segment %d,%d:%d from loop[%d]\n",
+ x2, y2, F(d), i);
+#endif
+ nloop[i]--;
+ } else {
+ if (nloop[i] >= loopsize[i]) {
+ loopsize[i] = loopsize[i] * 3 / 2 + 32;
+ loop[i] = sresize(loop[i], loopsize[i], struct xyd);
+ }
+#ifdef PERTURB_DIAGNOSTICS
+ printf("adding path segment %d,%d:%d to loop[%d]\n",
+ x, y, d, i);
+#endif
+ loop[i][nloop[i]++] = looppos[i];
+ }
+
+#ifdef PERTURB_DIAGNOSTICS
+ printf("tile at new location is %x\n", tiles[y2*w+x2] & 0xF);
+#endif
+ d = F(d);
+ for (j = 0; j < 4; j++) {
+ if (i == 0)
+ d = A(d);
+ else
+ d = C(d);
+#ifdef PERTURB_DIAGNOSTICS
+ printf("trying dir %d\n", d);
+#endif
+ if (tiles[y2*w+x2] & d) {
+ looppos[i].x = x2;
+ looppos[i].y = y2;
+ looppos[i].direction = d;
+ break;
+ }
+ }
+
+ assert(j < 4);
+ assert(nloop[i] > 0);
+
+ if (looppos[i].x == loop[i][0].x &&
+ looppos[i].y == loop[i][0].y &&
+ looppos[i].direction == loop[i][0].direction) {
+#ifdef PERTURB_DIAGNOSTICS
+ printf("loop %d finished tracking\n", i);
+#endif
+
+ /*
+ * Having found our loop, we now sever it at a
+ * randomly chosen point - absolutely any will do -
+ * which is not the one we joined it at to begin
+ * with. Conveniently, the one we joined it at is
+ * loop[i][0], so we just avoid that one.
+ */
+ j = random_upto(rs, nloop[i]-1) + 1;
+ x = loop[i][j].x;
+ y = loop[i][j].y;
+ d = loop[i][j].direction;
+ OFFSETWH(x2, y2, x, y, d, w, h);
+ tiles[y*w+x] &= ~d;
+ tiles[y2*w+x2] &= ~F(d);
+
+ break;
+ }
+ }
+ if (i < 2)
+ break;
+ }
+ sfree(loop[0]);
+ sfree(loop[1]);
+
+ /*
+ * Finally, we must mark the entire disputed section as locked,
+ * to prevent the perturb function being called on it multiple
+ * times.
+ *
+ * To do this, we _sort_ the perimeter of the area. The
+ * existing xyd_cmp function will arrange things into columns
+ * for us, in such a way that each column has the edges in
+ * vertical order. Then we can work down each column and fill
+ * in all the squares between an up edge and a down edge.
+ */
+ qsort(perimeter, nperim, sizeof(struct xyd), xyd_cmp);
+ x = y = -1;
+ for (i = 0; i <= nperim; i++) {
+ if (i == nperim || perimeter[i].x > x) {
+ /*
+ * Fill in everything from the last Up edge to the
+ * bottom of the grid, if necessary.
+ */
+ if (x != -1) {
+ while (y < h) {
+#ifdef PERTURB_DIAGNOSTICS
+ printf("resolved: locking tile %d,%d\n", x, y);
+#endif
+ tiles[y * w + x] |= LOCKED;
+ y++;
+ }
+ x = y = -1;
+ }
+
+ if (i == nperim)
+ break;
+
+ x = perimeter[i].x;
+ y = 0;
+ }
+
+ if (perimeter[i].direction == U) {
+ x = perimeter[i].x;
+ y = perimeter[i].y;
+ } else if (perimeter[i].direction == D) {
+ /*
+ * Fill in everything from the last Up edge to here.
+ */
+ assert(x == perimeter[i].x && y <= perimeter[i].y);
+ while (y <= perimeter[i].y) {
+#ifdef PERTURB_DIAGNOSTICS
+ printf("resolved: locking tile %d,%d\n", x, y);
+#endif
+ tiles[y * w + x] |= LOCKED;
+ y++;
+ }
+ x = y = -1;
+ }
+ }
+
+ sfree(perimeter);
+}
+
+static char *new_game_desc(game_params *params, random_state *rs,
+ char **aux, int interactive)
+{
+ tree234 *possibilities, *barriertree;
+ int w, h, x, y, cx, cy, nbarriers;
+ unsigned char *tiles, *barriers;
+ char *desc, *p;
+
+ w = params->width;
+ h = params->height;
+
+ cx = w / 2;
+ cy = h / 2;
+
+ tiles = snewn(w * h, unsigned char);
+ barriers = snewn(w * h, unsigned char);
+
+ begin_generation:
+
+ memset(tiles, 0, w * h);
+ memset(barriers, 0, w * h);