{
int n = params->n, w = n+2, h = n+1, wh = w*h;
int *grid, *grid2, *list;
- int i, j, k, m, todo, done, len;
+ int i, j, k, len;
char *ret;
/*
*/
do {
- /*
- * To begin with, set grid[i] = i for all i to indicate
- * that all squares are currently singletons. Later we'll
- * set grid[i] to be the index of the other end of the
- * domino on i.
- */
- for (i = 0; i < wh; i++)
- grid[i] = i;
-
- /*
- * Now prepare a list of the possible domino locations. There
- * are w*(h-1) possible vertical locations, and (w-1)*h
- * horizontal ones, for a total of 2*wh - h - w.
- *
- * I'm going to denote the vertical domino placement with
- * its top in square i as 2*i, and the horizontal one with
- * its left half in square i as 2*i+1.
- */
- k = 0;
- for (j = 0; j < h-1; j++)
- for (i = 0; i < w; i++)
- list[k++] = 2 * (j*w+i); /* vertical positions */
- for (j = 0; j < h; j++)
- for (i = 0; i < w-1; i++)
- list[k++] = 2 * (j*w+i) + 1; /* horizontal positions */
- assert(k == 2*wh - h - w);
-
- /*
- * Shuffle the list.
- */
- shuffle(list, k, sizeof(*list), rs);
-
- /*
- * Work down the shuffled list, placing a domino everywhere
- * we can.
- */
- for (i = 0; i < k; i++) {
- int horiz, xy, xy2;
-
- horiz = list[i] % 2;
- xy = list[i] / 2;
- xy2 = xy + (horiz ? 1 : w);
-
- if (grid[xy] == xy && grid[xy2] == xy2) {
- /*
- * We can place this domino. Do so.
- */
- grid[xy] = xy2;
- grid[xy2] = xy;
- }
- }
-
-#ifdef GENERATION_DIAGNOSTICS
- printf("generated initial layout\n");
-#endif
-
- /*
- * Now we've placed as many dominoes as we can immediately
- * manage. There will be squares remaining, but they'll be
- * singletons. So loop round and deal with the singletons
- * two by two.
- */
- while (1) {
-#ifdef GENERATION_DIAGNOSTICS
- for (j = 0; j < h; j++) {
- for (i = 0; i < w; i++) {
- int xy = j*w+i;
- int v = grid[xy];
- int c = (v == xy+1 ? '[' : v == xy-1 ? ']' :
- v == xy+w ? 'n' : v == xy-w ? 'U' : '.');
- putchar(c);
- }
- putchar('\n');
- }
- putchar('\n');
-#endif
-
- /*
- * Our strategy is:
- *
- * First find a singleton square.
- *
- * Then breadth-first search out from the starting
- * square. From that square (and any others we reach on
- * the way), examine all four neighbours of the square.
- * If one is an end of a domino, we move to the _other_
- * end of that domino before looking at neighbours
- * again. When we encounter another singleton on this
- * search, stop.
- *
- * This will give us a path of adjacent squares such
- * that all but the two ends are covered in dominoes.
- * So we can now shuffle every domino on the path up by
- * one.
- *
- * (Chessboard colours are mathematically important
- * here: we always end up pairing each singleton with a
- * singleton of the other colour. However, we never
- * have to track this manually, since it's
- * automatically taken care of by the fact that we
- * always make an even number of orthogonal moves.)
- */
- for (i = 0; i < wh; i++)
- if (grid[i] == i)
- break;
- if (i == wh)
- break; /* no more singletons; we're done. */
-
-#ifdef GENERATION_DIAGNOSTICS
- printf("starting b.f.s. at singleton %d\n", i);
-#endif
- /*
- * Set grid2 to -1 everywhere. It will hold our
- * distance-from-start values, and also our
- * backtracking data, during the b.f.s.
- */
- for (j = 0; j < wh; j++)
- grid2[j] = -1;
- grid2[i] = 0; /* starting square has distance zero */
-
- /*
- * Start our to-do list of squares. It'll live in
- * `list'; since the b.f.s can cover every square at
- * most once there is no need for it to be circular.
- * We'll just have two counters tracking the end of the
- * list and the squares we've already dealt with.
- */
- done = 0;
- todo = 1;
- list[0] = i;
-
- /*
- * Now begin the b.f.s. loop.
- */
- while (done < todo) {
- int d[4], nd, x, y;
-
- i = list[done++];
-
-#ifdef GENERATION_DIAGNOSTICS
- printf("b.f.s. iteration from %d\n", i);
-#endif
- x = i % w;
- y = i / w;
- nd = 0;
- if (x > 0)
- d[nd++] = i - 1;
- if (x+1 < w)
- d[nd++] = i + 1;
- if (y > 0)
- d[nd++] = i - w;
- if (y+1 < h)
- d[nd++] = i + w;
- /*
- * To avoid directional bias, process the
- * neighbours of this square in a random order.
- */
- shuffle(d, nd, sizeof(*d), rs);
-
- for (j = 0; j < nd; j++) {
- k = d[j];
- if (grid[k] == k) {
-#ifdef GENERATION_DIAGNOSTICS
- printf("found neighbouring singleton %d\n", k);
-#endif
- grid2[k] = i;
- break; /* found a target singleton! */
- }
-
- /*
- * We're moving through a domino here, so we
- * have two entries in grid2 to fill with
- * useful data. In grid[k] - the square
- * adjacent to where we came from - I'm going
- * to put the address _of_ the square we came
- * from. In the other end of the domino - the
- * square from which we will continue the
- * search - I'm going to put the distance.
- */
- m = grid[k];
-
- if (grid2[m] < 0 || grid2[m] > grid2[i]+1) {
-#ifdef GENERATION_DIAGNOSTICS
- printf("found neighbouring domino %d/%d\n", k, m);
-#endif
- grid2[m] = grid2[i]+1;
- grid2[k] = i;
- /*
- * And since we've now visited a new
- * domino, add m to the to-do list.
- */
- assert(todo < wh);
- list[todo++] = m;
- }
- }
-
- if (j < nd) {
- i = k;
-#ifdef GENERATION_DIAGNOSTICS
- printf("terminating b.f.s. loop, i = %d\n", i);
-#endif
- break;
- }
-
- i = -1; /* just in case the loop terminates */
- }
-
- /*
- * We expect this b.f.s. to have found us a target
- * square.
- */
- assert(i >= 0);
-
- /*
- * Now we can follow the trail back to our starting
- * singleton, re-laying dominoes as we go.
- */
- while (1) {
- j = grid2[i];
- assert(j >= 0 && j < wh);
- k = grid[j];
-
- grid[i] = j;
- grid[j] = i;
-#ifdef GENERATION_DIAGNOSTICS
- printf("filling in domino %d/%d (next %d)\n", i, j, k);
-#endif
- if (j == k)
- break; /* we've reached the other singleton */
- i = k;
- }
-#ifdef GENERATION_DIAGNOSTICS
- printf("fixup path completed\n");
-#endif
- }
+ domino_layout_prealloc(w, h, rs, grid, grid2, list);
/*
* Now we have a complete layout covering the whole
* I'll use 6mm squares by default.
*/
game_compute_size(params, 600, &pw, &ph);
- *x = pw / 100.0;
- *y = ph / 100.0;
+ *x = pw / 100.0F;
+ *y = ph / 100.0F;
}
static void game_print(drawing *dr, game_state *state, int tilesize)
FALSE, game_timing_state,
0, /* flags */
};
+
+/* vim: set shiftwidth=4 :set textwidth=80: */
+