Prepare to release sgt-puzzles (20170606.272beef-1).
[sgt-puzzles.git] / loopgen.c
blob0b6990455ffc36249cc682a5efdbc04280dbac85
1 /*
2 * loopgen.c: loop generation functions for grid.[ch].
3 */
5 #include <stdio.h>
6 #include <stdlib.h>
7 #include <stddef.h>
8 #include <string.h>
9 #include <assert.h>
10 #include <ctype.h>
11 #include <math.h>
13 #include "puzzles.h"
14 #include "tree234.h"
15 #include "grid.h"
16 #include "loopgen.h"
19 /* We're going to store lists of current candidate faces for colouring black
20 * or white.
21 * Each face gets a 'score', which tells us how adding that face right
22 * now would affect the curliness of the solution loop. We're trying to
23 * maximise that quantity so will bias our random selection of faces to
24 * colour those with high scores */
25 struct face_score {
26 int white_score;
27 int black_score;
28 unsigned long random;
29 /* No need to store a grid_face* here. The 'face_scores' array will
30 * be a list of 'face_score' objects, one for each face of the grid, so
31 * the position (index) within the 'face_scores' array will determine
32 * which face corresponds to a particular face_score.
33 * Having a single 'face_scores' array for all faces simplifies memory
34 * management, and probably improves performance, because we don't have to
35 * malloc/free each individual face_score, and we don't have to maintain
36 * a mapping from grid_face* pointers to face_score* pointers.
40 static int generic_sort_cmpfn(void *v1, void *v2, size_t offset)
42 struct face_score *f1 = v1;
43 struct face_score *f2 = v2;
44 int r;
46 r = *(int *)((char *)f2 + offset) - *(int *)((char *)f1 + offset);
47 if (r) {
48 return r;
51 if (f1->random < f2->random)
52 return -1;
53 else if (f1->random > f2->random)
54 return 1;
57 * It's _just_ possible that two faces might have been given
58 * the same random value. In that situation, fall back to
59 * comparing based on the positions within the face_scores list.
60 * This introduces a tiny directional bias, but not a significant one.
62 return f1 - f2;
65 static int white_sort_cmpfn(void *v1, void *v2)
67 return generic_sort_cmpfn(v1, v2, offsetof(struct face_score,white_score));
70 static int black_sort_cmpfn(void *v1, void *v2)
72 return generic_sort_cmpfn(v1, v2, offsetof(struct face_score,black_score));
75 /* 'board' is an array of enum face_colour, indicating which faces are
76 * currently black/white/grey. 'colour' is FACE_WHITE or FACE_BLACK.
77 * Returns whether it's legal to colour the given face with this colour. */
78 static int can_colour_face(grid *g, char* board, int face_index,
79 enum face_colour colour)
81 int i, j;
82 grid_face *test_face = g->faces + face_index;
83 grid_face *starting_face, *current_face;
84 grid_dot *starting_dot;
85 int transitions;
86 int current_state, s; /* booleans: equal or not-equal to 'colour' */
87 int found_same_coloured_neighbour = FALSE;
88 assert(board[face_index] != colour);
90 /* Can only consider a face for colouring if it's adjacent to a face
91 * with the same colour. */
92 for (i = 0; i < test_face->order; i++) {
93 grid_edge *e = test_face->edges[i];
94 grid_face *f = (e->face1 == test_face) ? e->face2 : e->face1;
95 if (FACE_COLOUR(f) == colour) {
96 found_same_coloured_neighbour = TRUE;
97 break;
100 if (!found_same_coloured_neighbour)
101 return FALSE;
103 /* Need to avoid creating a loop of faces of this colour around some
104 * differently-coloured faces.
105 * Also need to avoid meeting a same-coloured face at a corner, with
106 * other-coloured faces in between. Here's a simple test that (I believe)
107 * takes care of both these conditions:
109 * Take the circular path formed by this face's edges, and inflate it
110 * slightly outwards. Imagine walking around this path and consider
111 * the faces that you visit in sequence. This will include all faces
112 * touching the given face, either along an edge or just at a corner.
113 * Count the number of 'colour'/not-'colour' transitions you encounter, as
114 * you walk along the complete loop. This will obviously turn out to be
115 * an even number.
116 * If 0, we're either in the middle of an "island" of this colour (should
117 * be impossible as we're not supposed to create black or white loops),
118 * or we're about to start a new island - also not allowed.
119 * If 4 or greater, there are too many separate coloured regions touching
120 * this face, and colouring it would create a loop or a corner-violation.
121 * The only allowed case is when the count is exactly 2. */
123 /* i points to a dot around the test face.
124 * j points to a face around the i^th dot.
125 * The current face will always be:
126 * test_face->dots[i]->faces[j]
127 * We assume dots go clockwise around the test face,
128 * and faces go clockwise around dots. */
131 * The end condition is slightly fiddly. In sufficiently strange
132 * degenerate grids, our test face may be adjacent to the same
133 * other face multiple times (typically if it's the exterior
134 * face). Consider this, in particular:
136 * +--+
137 * | |
138 * +--+--+
139 * | | |
140 * +--+--+
142 * The bottom left face there is adjacent to the exterior face
143 * twice, so we can't just terminate our iteration when we reach
144 * the same _face_ we started at. Furthermore, we can't
145 * condition on having the same (i,j) pair either, because
146 * several (i,j) pairs identify the bottom left contiguity with
147 * the exterior face! We canonicalise the (i,j) pair by taking
148 * one step around before we set the termination tracking.
151 i = j = 0;
152 current_face = test_face->dots[0]->faces[0];
153 if (current_face == test_face) {
154 j = 1;
155 current_face = test_face->dots[0]->faces[1];
157 transitions = 0;
158 current_state = (FACE_COLOUR(current_face) == colour);
159 starting_dot = NULL;
160 starting_face = NULL;
161 while (TRUE) {
162 /* Advance to next face.
163 * Need to loop here because it might take several goes to
164 * find it. */
165 while (TRUE) {
166 j++;
167 if (j == test_face->dots[i]->order)
168 j = 0;
170 if (test_face->dots[i]->faces[j] == test_face) {
171 /* Advance to next dot round test_face, then
172 * find current_face around new dot
173 * and advance to the next face clockwise */
174 i++;
175 if (i == test_face->order)
176 i = 0;
177 for (j = 0; j < test_face->dots[i]->order; j++) {
178 if (test_face->dots[i]->faces[j] == current_face)
179 break;
181 /* Must actually find current_face around new dot,
182 * or else something's wrong with the grid. */
183 assert(j != test_face->dots[i]->order);
184 /* Found, so advance to next face and try again */
185 } else {
186 break;
189 /* (i,j) are now advanced to next face */
190 current_face = test_face->dots[i]->faces[j];
191 s = (FACE_COLOUR(current_face) == colour);
192 if (!starting_dot) {
193 starting_dot = test_face->dots[i];
194 starting_face = current_face;
195 current_state = s;
196 } else {
197 if (s != current_state) {
198 ++transitions;
199 current_state = s;
200 if (transitions > 2)
201 break;
203 if (test_face->dots[i] == starting_dot &&
204 current_face == starting_face)
205 break;
209 return (transitions == 2) ? TRUE : FALSE;
212 /* Count the number of neighbours of 'face', having colour 'colour' */
213 static int face_num_neighbours(grid *g, char *board, grid_face *face,
214 enum face_colour colour)
216 int colour_count = 0;
217 int i;
218 grid_face *f;
219 grid_edge *e;
220 for (i = 0; i < face->order; i++) {
221 e = face->edges[i];
222 f = (e->face1 == face) ? e->face2 : e->face1;
223 if (FACE_COLOUR(f) == colour)
224 ++colour_count;
226 return colour_count;
229 /* The 'score' of a face reflects its current desirability for selection
230 * as the next face to colour white or black. We want to encourage moving
231 * into grey areas and increasing loopiness, so we give scores according to
232 * how many of the face's neighbours are currently coloured the same as the
233 * proposed colour. */
234 static int face_score(grid *g, char *board, grid_face *face,
235 enum face_colour colour)
237 /* Simple formula: score = 0 - num. same-coloured neighbours,
238 * so a higher score means fewer same-coloured neighbours. */
239 return -face_num_neighbours(g, board, face, colour);
243 * Generate a new complete random closed loop for the given grid.
245 * The method is to generate a WHITE/BLACK colouring of all the faces,
246 * such that the WHITE faces will define the inside of the path, and the
247 * BLACK faces define the outside.
248 * To do this, we initially colour all faces GREY. The infinite space outside
249 * the grid is coloured BLACK, and we choose a random face to colour WHITE.
250 * Then we gradually grow the BLACK and the WHITE regions, eliminating GREY
251 * faces, until the grid is filled with BLACK/WHITE. As we grow the regions,
252 * we avoid creating loops of a single colour, to preserve the topological
253 * shape of the WHITE and BLACK regions.
254 * We also try to make the boundary as loopy and twisty as possible, to avoid
255 * generating paths that are uninteresting.
256 * The algorithm works by choosing a BLACK/WHITE colour, then choosing a GREY
257 * face that can be coloured with that colour (without violating the
258 * topological shape of that region). It's not obvious, but I think this
259 * algorithm is guaranteed to terminate without leaving any GREY faces behind.
260 * Indeed, if there are any GREY faces at all, both the WHITE and BLACK
261 * regions can be grown.
262 * This is checked using assert()ions, and I haven't seen any failures yet.
264 * Hand-wavy proof: imagine what can go wrong...
266 * Could the white faces get completely cut off by the black faces, and still
267 * leave some grey faces remaining?
268 * No, because then the black faces would form a loop around both the white
269 * faces and the grey faces, which is disallowed because we continually
270 * maintain the correct topological shape of the black region.
271 * Similarly, the black faces can never get cut off by the white faces. That
272 * means both the WHITE and BLACK regions always have some room to grow into
273 * the GREY regions.
274 * Could it be that we can't colour some GREY face, because there are too many
275 * WHITE/BLACK transitions as we walk round the face? (see the
276 * can_colour_face() function for details)
277 * No. Imagine otherwise, and we see WHITE/BLACK/WHITE/BLACK as we walk
278 * around the face. The two WHITE faces would be connected by a WHITE path,
279 * and the BLACK faces would be connected by a BLACK path. These paths would
280 * have to cross, which is impossible.
281 * Another thing that could go wrong: perhaps we can't find any GREY face to
282 * colour WHITE, because it would create a loop-violation or a corner-violation
283 * with the other WHITE faces?
284 * This is a little bit tricky to prove impossible. Imagine you have such a
285 * GREY face (that is, if you coloured it WHITE, you would create a WHITE loop
286 * or corner violation).
287 * That would cut all the non-white area into two blobs. One of those blobs
288 * must be free of BLACK faces (because the BLACK stuff is a connected blob).
289 * So we have a connected GREY area, completely surrounded by WHITE
290 * (including the GREY face we've tentatively coloured WHITE).
291 * A well-known result in graph theory says that you can always find a GREY
292 * face whose removal leaves the remaining GREY area connected. And it says
293 * there are at least two such faces, so we can always choose the one that
294 * isn't the "tentative" GREY face. Colouring that face WHITE leaves
295 * everything nice and connected, including that "tentative" GREY face which
296 * acts as a gateway to the rest of the non-WHITE grid.
298 void generate_loop(grid *g, char *board, random_state *rs,
299 loopgen_bias_fn_t bias, void *biasctx)
301 int i, j;
302 int num_faces = g->num_faces;
303 struct face_score *face_scores; /* Array of face_score objects */
304 struct face_score *fs; /* Points somewhere in the above list */
305 struct grid_face *cur_face;
306 tree234 *lightable_faces_sorted;
307 tree234 *darkable_faces_sorted;
308 int *face_list;
309 int do_random_pass;
311 /* Make a board */
312 memset(board, FACE_GREY, num_faces);
314 /* Create and initialise the list of face_scores */
315 face_scores = snewn(num_faces, struct face_score);
316 for (i = 0; i < num_faces; i++) {
317 face_scores[i].random = random_bits(rs, 31);
318 face_scores[i].black_score = face_scores[i].white_score = 0;
321 /* Colour a random, finite face white. The infinite face is implicitly
322 * coloured black. Together, they will seed the random growth process
323 * for the black and white areas. */
324 i = random_upto(rs, num_faces);
325 board[i] = FACE_WHITE;
327 /* We need a way of favouring faces that will increase our loopiness.
328 * We do this by maintaining a list of all candidate faces sorted by
329 * their score and choose randomly from that with appropriate skew.
330 * In order to avoid consistently biasing towards particular faces, we
331 * need the sort order _within_ each group of scores to be completely
332 * random. But it would be abusing the hospitality of the tree234 data
333 * structure if our comparison function were nondeterministic :-). So with
334 * each face we associate a random number that does not change during a
335 * particular run of the generator, and use that as a secondary sort key.
336 * Yes, this means we will be biased towards particular random faces in
337 * any one run but that doesn't actually matter. */
339 lightable_faces_sorted = newtree234(white_sort_cmpfn);
340 darkable_faces_sorted = newtree234(black_sort_cmpfn);
342 /* Initialise the lists of lightable and darkable faces. This is
343 * slightly different from the code inside the while-loop, because we need
344 * to check every face of the board (the grid structure does not keep a
345 * list of the infinite face's neighbours). */
346 for (i = 0; i < num_faces; i++) {
347 grid_face *f = g->faces + i;
348 struct face_score *fs = face_scores + i;
349 if (board[i] != FACE_GREY) continue;
350 /* We need the full colourability check here, it's not enough simply
351 * to check neighbourhood. On some grids, a neighbour of the infinite
352 * face is not necessarily darkable. */
353 if (can_colour_face(g, board, i, FACE_BLACK)) {
354 fs->black_score = face_score(g, board, f, FACE_BLACK);
355 add234(darkable_faces_sorted, fs);
357 if (can_colour_face(g, board, i, FACE_WHITE)) {
358 fs->white_score = face_score(g, board, f, FACE_WHITE);
359 add234(lightable_faces_sorted, fs);
363 /* Colour faces one at a time until no more faces are colourable. */
364 while (TRUE)
366 enum face_colour colour;
367 tree234 *faces_to_pick;
368 int c_lightable = count234(lightable_faces_sorted);
369 int c_darkable = count234(darkable_faces_sorted);
370 if (c_lightable == 0 && c_darkable == 0) {
371 /* No more faces we can use at all. */
372 break;
374 assert(c_lightable != 0 && c_darkable != 0);
376 /* Choose a colour, and colour the best available face
377 * with that colour. */
378 colour = random_upto(rs, 2) ? FACE_WHITE : FACE_BLACK;
380 if (colour == FACE_WHITE)
381 faces_to_pick = lightable_faces_sorted;
382 else
383 faces_to_pick = darkable_faces_sorted;
384 if (bias) {
386 * Go through all the candidate faces and pick the one the
387 * bias function likes best, breaking ties using the
388 * ordering in our tree234 (which is why we replace only
389 * if score > bestscore, not >=).
391 int j, k;
392 struct face_score *best = NULL;
393 int score, bestscore = 0;
395 for (j = 0;
396 (fs = (struct face_score *)index234(faces_to_pick, j))!=NULL;
397 j++) {
399 assert(fs);
400 k = fs - face_scores;
401 assert(board[k] == FACE_GREY);
402 board[k] = colour;
403 score = bias(biasctx, board, k);
404 board[k] = FACE_GREY;
405 bias(biasctx, board, k); /* let bias know we put it back */
407 if (!best || score > bestscore) {
408 bestscore = score;
409 best = fs;
412 fs = best;
413 } else {
414 fs = (struct face_score *)index234(faces_to_pick, 0);
416 assert(fs);
417 i = fs - face_scores;
418 assert(board[i] == FACE_GREY);
419 board[i] = colour;
420 if (bias)
421 bias(biasctx, board, i); /* notify bias function of the change */
423 /* Remove this newly-coloured face from the lists. These lists should
424 * only contain grey faces. */
425 del234(lightable_faces_sorted, fs);
426 del234(darkable_faces_sorted, fs);
428 /* Remember which face we've just coloured */
429 cur_face = g->faces + i;
431 /* The face we've just coloured potentially affects the colourability
432 * and the scores of any neighbouring faces (touching at a corner or
433 * edge). So the search needs to be conducted around all faces
434 * touching the one we've just lit. Iterate over its corners, then
435 * over each corner's faces. For each such face, we remove it from
436 * the lists, recalculate any scores, then add it back to the lists
437 * (depending on whether it is lightable, darkable or both). */
438 for (i = 0; i < cur_face->order; i++) {
439 grid_dot *d = cur_face->dots[i];
440 for (j = 0; j < d->order; j++) {
441 grid_face *f = d->faces[j];
442 int fi; /* face index of f */
444 if (f == NULL)
445 continue;
446 if (f == cur_face)
447 continue;
449 /* If the face is already coloured, it won't be on our
450 * lightable/darkable lists anyway, so we can skip it without
451 * bothering with the removal step. */
452 if (FACE_COLOUR(f) != FACE_GREY) continue;
454 /* Find the face index and face_score* corresponding to f */
455 fi = f - g->faces;
456 fs = face_scores + fi;
458 /* Remove from lightable list if it's in there. We do this,
459 * even if it is still lightable, because the score might
460 * be different, and we need to remove-then-add to maintain
461 * correct sort order. */
462 del234(lightable_faces_sorted, fs);
463 if (can_colour_face(g, board, fi, FACE_WHITE)) {
464 fs->white_score = face_score(g, board, f, FACE_WHITE);
465 add234(lightable_faces_sorted, fs);
467 /* Do the same for darkable list. */
468 del234(darkable_faces_sorted, fs);
469 if (can_colour_face(g, board, fi, FACE_BLACK)) {
470 fs->black_score = face_score(g, board, f, FACE_BLACK);
471 add234(darkable_faces_sorted, fs);
477 /* Clean up */
478 freetree234(lightable_faces_sorted);
479 freetree234(darkable_faces_sorted);
480 sfree(face_scores);
482 /* The next step requires a shuffled list of all faces */
483 face_list = snewn(num_faces, int);
484 for (i = 0; i < num_faces; ++i) {
485 face_list[i] = i;
487 shuffle(face_list, num_faces, sizeof(int), rs);
489 /* The above loop-generation algorithm can often leave large clumps
490 * of faces of one colour. In extreme cases, the resulting path can be
491 * degenerate and not very satisfying to solve.
492 * This next step alleviates this problem:
493 * Go through the shuffled list, and flip the colour of any face we can
494 * legally flip, and which is adjacent to only one face of the opposite
495 * colour - this tends to grow 'tendrils' into any clumps.
496 * Repeat until we can find no more faces to flip. This will
497 * eventually terminate, because each flip increases the loop's
498 * perimeter, which cannot increase for ever.
499 * The resulting path will have maximal loopiness (in the sense that it
500 * cannot be improved "locally". Unfortunately, this allows a player to
501 * make some illicit deductions. To combat this (and make the path more
502 * interesting), we do one final pass making random flips. */
504 /* Set to TRUE for final pass */
505 do_random_pass = FALSE;
507 while (TRUE) {
508 /* Remember whether a flip occurred during this pass */
509 int flipped = FALSE;
511 for (i = 0; i < num_faces; ++i) {
512 int j = face_list[i];
513 enum face_colour opp =
514 (board[j] == FACE_WHITE) ? FACE_BLACK : FACE_WHITE;
515 if (can_colour_face(g, board, j, opp)) {
516 grid_face *face = g->faces +j;
517 if (do_random_pass) {
518 /* final random pass */
519 if (!random_upto(rs, 10))
520 board[j] = opp;
521 } else {
522 /* normal pass - flip when neighbour count is 1 */
523 if (face_num_neighbours(g, board, face, opp) == 1) {
524 board[j] = opp;
525 flipped = TRUE;
531 if (do_random_pass) break;
532 if (!flipped) do_random_pass = TRUE;
535 sfree(face_list);