2 * Implementation of 'Train Tracks', a puzzle from the Times on Saturday.
4 * "Lay tracks to enable the train to travel from village A to village B.
5 * The numbers indicate how many sections of rail go in each row and
6 * column. There are only straight rails and curved rails. The track
7 * cannot cross itself."
10 * #9 8x8:d9s5c6zgAa,1,4,1,4,4,3,S3,5,2,2,4,S5,3,3,5,1
11 * #112 8x8:w6x5mAa,1,3,1,4,6,4,S4,3,3,4,5,2,4,2,S5,1
12 * #113 8x8:gCx5xAf,1,S4,2,5,4,6,2,3,4,2,5,2,S4,4,5,1
13 * #114 8x8:p5fAzkAb,1,6,3,3,3,S6,2,3,5,4,S3,3,5,1,5,1
14 * #115 8x8:zi9d5tAb,1,3,4,5,3,S4,2,4,2,6,2,3,6,S3,3,1
26 /* --- Game parameters --- */
29 * Difficulty levels. I do some macro ickery here to ensure that my
30 * enum and the various forms of my name list always match up.
36 #define ENUM(upper,title,lower) DIFF_ ## upper,
37 #define TITLE(upper,title,lower) #title,
38 #define ENCODE(upper,title,lower) #lower
39 #define CONFIG(upper,title,lower) ":" #title
40 enum { DIFFLIST(ENUM) DIFFCOUNT };
41 static char const *const tracks_diffnames[] = { DIFFLIST(TITLE) };
42 static char const tracks_diffchars[] = DIFFLIST(ENCODE);
43 #define DIFFCONFIG DIFFLIST(CONFIG)
46 int w, h, diff, single_ones;
49 static game_params *default_params(void)
51 game_params *ret = snew(game_params);
54 ret->diff = DIFF_TRICKY;
55 ret->single_ones = TRUE;
60 static const struct game_params tracks_presets[] = {
62 {8, 8, DIFF_TRICKY, 1},
63 {10, 8, DIFF_EASY, 1},
64 {10, 8, DIFF_TRICKY, 1 },
65 {10, 10, DIFF_EASY, 1},
66 {10, 10, DIFF_TRICKY, 1},
67 {15, 10, DIFF_EASY, 1},
68 {15, 10, DIFF_TRICKY, 1},
69 {15, 15, DIFF_EASY, 1},
70 {15, 15, DIFF_TRICKY, 1},
73 static int game_fetch_preset(int i, char **name, game_params **params)
78 if (i < 0 || i >= lenof(tracks_presets))
81 ret = snew(game_params);
82 *ret = tracks_presets[i];
84 sprintf(str, "%dx%d %s", ret->w, ret->h, tracks_diffnames[ret->diff]);
91 static void free_params(game_params *params)
96 static game_params *dup_params(const game_params *params)
98 game_params *ret = snew(game_params);
99 *ret = *params; /* structure copy */
103 static void decode_params(game_params *params, char const *string)
105 params->w = params->h = atoi(string);
106 while (*string && isdigit((unsigned char)*string)) string++;
107 if (*string == 'x') {
109 params->h = atoi(string);
110 while (*string && isdigit((unsigned char)*string)) string++;
112 if (*string == 'd') {
115 params->diff = DIFF_TRICKY;
116 for (i = 0; i < DIFFCOUNT; i++)
117 if (*string == tracks_diffchars[i])
119 if (*string) string++;
121 params->single_ones = TRUE;
122 if (*string == 'o') {
123 params->single_ones = FALSE;
129 static char *encode_params(const game_params *params, int full)
133 sprintf(buf, "%dx%d", params->w, params->h);
135 sprintf(buf + strlen(buf), "d%c%s",
136 tracks_diffchars[params->diff],
137 params->single_ones ? "" : "o");
141 static config_item *game_configure(const game_params *params)
146 ret = snewn(5, config_item);
148 ret[0].name = "Width";
149 ret[0].type = C_STRING;
150 sprintf(buf, "%d", params->w);
151 ret[0].sval = dupstr(buf);
154 ret[1].name = "Height";
155 ret[1].type = C_STRING;
156 sprintf(buf, "%d", params->h);
157 ret[1].sval = dupstr(buf);
160 ret[2].name = "Difficulty";
161 ret[2].type = C_CHOICES;
162 ret[2].sval = DIFFCONFIG;
163 ret[2].ival = params->diff;
165 ret[3].name = "Disallow consecutive 1 clues";
166 ret[3].type = C_BOOLEAN;
167 ret[3].ival = params->single_ones;
177 static game_params *custom_params(const config_item *cfg)
179 game_params *ret = snew(game_params);
181 ret->w = atoi(cfg[0].sval);
182 ret->h = atoi(cfg[1].sval);
183 ret->diff = cfg[2].ival;
184 ret->single_ones = cfg[3].ival;
189 static char *validate_params(const game_params *params, int full)
192 * Generating anything under 4x4 runs into trouble of one kind
195 if (params->w < 4 || params->h < 4)
196 return "Width and height must both be at least four";
200 /* --- Game state --- */
202 /* flag usage copied from pearl */
209 #define MOVECHAR(m) ((m==R)?'R':(m==U)?'U':(m==L)?'L':(m==D)?'D':'?')
211 #define DX(d) ( ((d)==R) - ((d)==L) )
212 #define DY(d) ( ((d)==D) - ((d)==U) )
214 #define F(d) (((d << 2) | (d >> 2)) & 0xF)
215 #define C(d) (((d << 3) | (d >> 1)) & 0xF)
216 #define A(d) (((d << 1) | (d >> 3)) & 0xF)
234 int nbits[] = { 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4 };
236 /* square grid flags */
237 #define S_TRACK 1 /* a track passes through this square (--> 2 edges) */
238 #define S_NOTRACK 2 /* no track passes through this square */
243 #define S_TRACK_SHIFT 16 /* U/D/L/R flags for edge track indicators */
244 #define S_NOTRACK_SHIFT 20 /* U/D/L/R flags for edge no-track indicators */
246 /* edge grid flags */
247 #define E_TRACK 1 /* a track passes through this edge */
248 #define E_NOTRACK 2 /* no track passes through this edge */
252 int *numbers; /* sz w+h */
253 int row_s, col_s; /* stations: TODO think about multiple lines
254 (for bigger grids)? */
257 #define INGRID(state, gx, gy) ((gx) >= 0 && (gx) < (state)->p.w && \
258 (gy) >= 0 && (gy) < (state)->p.h)
262 unsigned int *sflags; /* size w*h */
263 struct numbers *numbers;
264 int *num_errors; /* size w+h */
265 int completed, used_solve, impossible;
268 /* Return the four directions in which a particular edge flag is set, around a square. */
269 int S_E_DIRS(const game_state *state, int sx, int sy, unsigned int eflag) {
270 return (state->sflags[sy*state->p.w+sx] >>
271 ((eflag == E_TRACK) ? S_TRACK_SHIFT : S_NOTRACK_SHIFT)) & ALLDIR;
274 /* Count the number of a particular edge flag around a grid square. */
275 int S_E_COUNT(const game_state *state, int sx, int sy, unsigned int eflag) {
276 return nbits[S_E_DIRS(state, sx, sy, eflag)];
279 /* Return the two flags (E_TRACK and/or E_NOTRACK) set on a specific
280 * edge of a square. */
281 unsigned S_E_FLAGS(const game_state *state, int sx, int sy, int d) {
282 unsigned f = state->sflags[sy*state->p.w+sx];
283 int t = (f & (d << S_TRACK_SHIFT)), nt = (f & (d << S_NOTRACK_SHIFT));
284 return (t ? E_TRACK : 0) | (nt ? E_NOTRACK : 0);
287 int S_E_ADJ(const game_state *state, int sx, int sy, int d, int *ax, int *ay, unsigned int *ad) {
288 if (d == L && sx > 0) { *ax = sx-1; *ay = sy; *ad = R; return 1; }
289 if (d == R && sx < state->p.w-1) { *ax = sx+1; *ay = sy; *ad = L; return 1; }
290 if (d == U && sy > 0) { *ax = sx; *ay = sy-1; *ad = D; return 1; }
291 if (d == D && sy < state->p.h-1) { *ax = sx; *ay = sy+1; *ad = U; return 1; }
296 /* Sets flag (E_TRACK or E_NOTRACK) on a given edge of a square. */
297 void S_E_SET(game_state *state, int sx, int sy, int d, unsigned int eflag) {
298 unsigned shift = (eflag == E_TRACK) ? S_TRACK_SHIFT : S_NOTRACK_SHIFT, ad;
301 state->sflags[sy*state->p.w+sx] |= (d << shift);
303 if (S_E_ADJ(state, sx, sy, d, &ax, &ay, &ad)) {
304 state->sflags[ay*state->p.w+ax] |= (ad << shift);
308 /* Clears flag (E_TRACK or E_NOTRACK) on a given edge of a square. */
309 void S_E_CLEAR(game_state *state, int sx, int sy, int d, unsigned int eflag) {
310 unsigned shift = (eflag == E_TRACK) ? S_TRACK_SHIFT : S_NOTRACK_SHIFT, ad;
313 state->sflags[sy*state->p.w+sx] &= ~(d << shift);
315 if (S_E_ADJ(state, sx, sy, d, &ax, &ay, &ad)) {
316 state->sflags[ay*state->p.w+ax] &= ~(ad << shift);
320 static void clear_game(game_state *state)
322 int w = state->p.w, h = state->p.h;
324 memset(state->sflags, 0, w*h * sizeof(unsigned int));
326 memset(state->numbers->numbers, 0, (w+h) * sizeof(int));
327 state->numbers->col_s = state->numbers->row_s = -1;
329 memset(state->num_errors, 0, (w+h) * sizeof(int));
331 state->completed = state->used_solve = state->impossible = FALSE;
334 static game_state *blank_game(const game_params *params)
336 game_state *state = snew(game_state);
337 int w = params->w, h = params->h;
341 state->sflags = snewn(w*h, unsigned int);
343 state->numbers = snew(struct numbers);
344 state->numbers->refcount = 1;
345 state->numbers->numbers = snewn(w+h, int);
347 state->num_errors = snewn(w+h, int);
354 static void copy_game_flags(const game_state *src, game_state *dest)
356 int w = src->p.w, h = src->p.h;
358 memcpy(dest->sflags, src->sflags, w*h*sizeof(unsigned int));
361 static game_state *dup_game(const game_state *state)
363 int w = state->p.w, h = state->p.h;
364 game_state *ret = snew(game_state);
366 ret->p = state->p; /* structure copy */
368 ret->sflags = snewn(w*h, unsigned int);
369 copy_game_flags(state, ret);
371 ret->numbers = state->numbers;
372 state->numbers->refcount++;
373 ret->num_errors = snewn(w+h, int);
374 memcpy(ret->num_errors, state->num_errors, (w+h)*sizeof(int));
376 ret->completed = state->completed;
377 ret->used_solve = state->used_solve;
378 ret->impossible = state->impossible;
383 static void free_game(game_state *state)
385 if (--state->numbers->refcount <= 0) {
386 sfree(state->numbers->numbers);
387 sfree(state->numbers);
389 sfree(state->num_errors);
390 sfree(state->sflags);
395 const unsigned int dirs_const[] = { U, D, L, R };
397 static unsigned int find_direction(game_state *state, random_state *rs,
400 int i, nx, ny, w=state->p.w, h=state->p.h;
401 unsigned int dirs[NDIRS];
403 memcpy(dirs, dirs_const, sizeof(dirs));
404 shuffle(dirs, NDIRS, sizeof(*dirs), rs);
405 for (i = 0; i < NDIRS; i++) {
406 nx = x + DX(dirs[i]);
407 ny = y + DY(dirs[i]);
408 if (nx >= 0 && nx < w && ny == h) {
409 /* off the bottom of the board: we've finished the path. */
411 } else if (!INGRID(state, nx, ny)) {
412 /* off the board: can't move here */
414 } else if (S_E_COUNT(state, nx, ny, E_TRACK) > 0) {
415 /* already tracks here: can't move */
420 return 0; /* no possible directions left. */
423 static int check_completion(game_state *state, int mark);
425 static void lay_path(game_state *state, random_state *rs)
427 int px, py, w=state->p.w, h=state->p.h;
433 /* pick a random entry point, lay its left edge */
434 state->numbers->row_s = py = random_upto(rs, h);
436 S_E_SET(state, px, py, L, E_TRACK);
438 while (INGRID(state, px, py)) {
439 d = find_direction(state, rs, px, py);
441 goto start; /* nowhere else to go, restart */
443 S_E_SET(state, px, py, d, E_TRACK);
447 /* double-check we got to the right place */
448 assert(px >= 0 && px < w && py == h);
450 state->numbers->col_s = px;
453 static int tracks_solve(game_state *state, int diff);
454 static void debug_state(game_state *state, const char *what);
456 /* Clue-setting algorithm:
458 - first lay clues randomly until it's soluble
459 - then remove clues randomly if removing them doesn't affect solubility
461 - We start with two clues, one at each path entrance.
464 - start with an array of all square i positions
465 - if the grid is already soluble by a level easier than we've requested,
466 go back and make a new grid
467 - if the grid is already soluble by our requested difficulty level, skip
469 - count the number of flags the solver managed to place, remember this.
472 - shuffle the i positions
473 - for each possible clue position:
474 - copy the solved board, strip it
475 - take the next position, add a clue there on the copy
476 - try and solve the copy
477 - if it's soluble by a level easier than we've requested, continue (on
478 to next clue position: putting a clue here makes it too easy)
479 - if it's soluble by our difficulty level, we're done:
480 - put the clue flag into the solved board
482 - if the solver didn't manage to place any more flags, continue (on to next
483 clue position: putting a clue here didn't help he solver)
484 - otherwise put the clue flag in the original board, and go on to the next
486 - if we get here and we've not solved it yet, we never will (did we really
487 fill _all_ the clues in?!). Go back and make a new grid.
490 - shuffle the i positions
491 - for each possible clue position:
492 - if the solved grid doesn't have a clue here, skip
493 - copy the solved board, remove this clue, strip it
494 - try and solve the copy
495 - assert that it is not soluble by a level easier than we've requested
496 - (because this should never happen)
497 - if this is (still) soluble by our difficulty level:
498 - remove this clue from the solved board, it's redundant (with the other
504 static game_state *copy_and_strip(const game_state *state, game_state *ret, int flipcluei)
506 int i, j, w = state->p.w, h = state->p.h;
508 copy_game_flags(state, ret);
510 /* Add/remove a clue before stripping, if required */
513 ret->sflags[flipcluei] ^= S_CLUE;
515 /* All squares that are not clue squares have square track info erased, and some edge flags.. */
517 for (i = 0; i < w*h; i++) {
518 if (!(ret->sflags[i] & S_CLUE)) {
519 ret->sflags[i] &= ~(S_TRACK|S_NOTRACK|S_ERROR|S_MARK);
520 for (j = 0; j < 4; j++) {
522 int xx = i%w + DX(f), yy = i/w + DY(f);
523 if (!INGRID(state, xx, yy) || !(ret->sflags[yy*w+xx] & S_CLUE)) {
524 /* only erase an edge flag if neither side of the edge is S_CLUE. */
525 S_E_CLEAR(ret, i%w, i/w, f, E_TRACK);
526 S_E_CLEAR(ret, i%w, i/w, f, E_NOTRACK);
534 static int solve_progress(const game_state *state) {
535 int i, w = state->p.w, h = state->p.h, progress = 0;
537 /* Work out how many flags the solver managed to set (either TRACK
538 or NOTRACK) and return this as a progress measure, to check whether
539 a partially-solved board gets any further than a previous partially-
542 for (i = 0; i < w*h; i++) {
543 if (state->sflags[i] & S_TRACK) progress++;
544 if (state->sflags[i] & S_NOTRACK) progress++;
545 progress += S_E_COUNT(state, i%w, i/w, E_TRACK);
546 progress += S_E_COUNT(state, i%w, i/w, E_NOTRACK);
551 static int check_phantom_moves(const game_state *state) {
554 /* Check that this state won't show 'phantom moves' at the start of the
555 * game: squares which have multiple edge flags set but no clue flag
556 * cause a piece of track to appear that isn't on a clue square. */
558 for (x = 0; x < state->p.w; x++) {
559 for (y = 0; y < state->p.h; y++) {
561 if (state->sflags[i] & S_CLUE)
563 if (S_E_COUNT(state, x, y, E_TRACK) > 1)
564 return 1; /* found one! */
570 static int add_clues(game_state *state, random_state *rs, int diff)
572 int i, j, pi, w = state->p.w, h = state->p.h, progress, ret = 0, sr;
573 int *positions = snewn(w*h, int), npositions = 0;
574 int *nedges_previous_solve = snewn(w*h, int);
575 game_state *scratch = dup_game(state);
577 debug_state(state, "gen: Initial board");
579 debug(("gen: Adding clues..."));
581 /* set up the shuffly-position grid for later, used for adding clues:
582 * we only bother adding clues where any edges are set. */
583 for (i = 0; i < w*h; i++) {
584 if (S_E_DIRS(state, i%w, i/w, E_TRACK) != 0) {
585 positions[npositions++] = i;
587 nedges_previous_solve[i] = 0;
590 /* First, check whether the puzzle is already either too easy, or just right */
591 scratch = copy_and_strip(state, scratch, -1);
593 sr = tracks_solve(scratch, diff-1);
595 assert(!"Generator should not have created impossible puzzle");
597 ret = -1; /* already too easy, even without adding clues. */
598 debug(("gen: ...already too easy, need new board."));
602 sr = tracks_solve(scratch, diff);
604 assert(!"Generator should not have created impossible puzzle");
606 ret = 1; /* already soluble without any extra clues. */
607 debug(("gen: ...soluble without clues, nothing to do."));
610 debug_state(scratch, "gen: Initial part-solved state: ");
611 progress = solve_progress(scratch);
612 debug(("gen: Initial solve progress is %d", progress));
614 /* First, lay clues until we're soluble. */
615 shuffle(positions, npositions, sizeof(int), rs);
616 for (pi = 0; pi < npositions; pi++) {
617 i = positions[pi]; /* pick a random position */
618 if (state->sflags[i] & S_CLUE)
619 continue; /* already a clue here (entrance location?) */
620 if (nedges_previous_solve[i] == 2)
621 continue; /* no point putting a clue here, we could solve both edges
622 with the previous set of clues */
624 /* set a clue in that position (on a copy of the board) and test solubility */
625 scratch = copy_and_strip(state, scratch, i);
627 if (check_phantom_moves(scratch))
628 continue; /* adding a clue here would add phantom track */
631 if (tracks_solve(scratch, diff-1) > 0) {
632 continue; /* adding a clue here makes it too easy */
635 if (tracks_solve(scratch, diff) > 0) {
636 /* we're now soluble (and we weren't before): add this clue, and then
637 start stripping clues */
638 debug(("gen: ...adding clue at (%d,%d), now soluble", i%w, i/w));
639 state->sflags[i] |= S_CLUE;
642 if (solve_progress(scratch) > progress) {
643 /* We've made more progress solving: add this clue, then. */
644 progress = solve_progress(scratch);
645 debug(("gen: ... adding clue at (%d,%d), new progress %d", i%w, i/w, progress));
646 state->sflags[i] |= S_CLUE;
648 for (j = 0; j < w*h; j++)
649 nedges_previous_solve[j] = S_E_COUNT(scratch, j%w, j/w, E_TRACK);
652 /* If we got here we didn't ever manage to make the puzzle soluble
653 (without making it too easily soluble, that is): give up. */
655 debug(("gen: Unable to make soluble with clues, need new board."));
660 debug(("gen: Stripping clues."));
662 /* Now, strip redundant clues (i.e. those without which the puzzle is still
664 shuffle(positions, npositions, sizeof(int), rs);
665 for (pi = 0; pi < npositions; pi++) {
666 i = positions[pi]; /* pick a random position */
667 if (!(state->sflags[i] & S_CLUE))
668 continue; /* no clue here to strip */
669 if ((i%w == 0 && i/w == state->numbers->row_s) ||
670 (i/w == (h-1) && i%w == state->numbers->col_s))
671 continue; /* don't strip clues at entrance/exit */
673 scratch = copy_and_strip(state, scratch, i);
674 if (check_phantom_moves(scratch))
675 continue; /* removing a clue here would add phantom track */
677 if (tracks_solve(scratch, diff) > 0) {
678 debug(("gen: ... removing clue at (%d,%d), still soluble without it", i%w, i/w));
679 state->sflags[i] &= ~S_CLUE; /* still soluble without this clue. */
682 debug(("gen: Finished stripping clues."));
691 static char *new_game_desc(const game_params *params, random_state *rs,
692 char **aux, int interactive)
694 int i, j, w = params->w, h = params->h, x, y, ret;
697 game_params adjusted_params;
700 * 4x4 Tricky cannot be generated, so fall back to Easy.
702 if (w == 4 && h == 4 && params->diff > DIFF_EASY) {
703 adjusted_params = *params; /* structure copy */
704 adjusted_params.diff = DIFF_EASY;
705 params = &adjusted_params;
708 state = blank_game(params);
710 /* --- lay the random path */
714 for (x = 0; x < w; x++) {
715 for (y = 0; y < h; y++) {
716 if (S_E_COUNT(state, x, y, E_TRACK) > 0) {
717 state->sflags[y*w + x] |= S_TRACK;
719 if ((x == 0 && y == state->numbers->row_s) ||
720 (y == (h-1) && x == state->numbers->col_s)) {
721 state->sflags[y*w + x] |= S_CLUE;
726 /* --- Update the clue numbers based on the tracks we have generated. */
727 for (x = 0; x < w; x++) {
728 for (y = 0; y < h; y++) {
729 if (state->sflags[y*w + x] & S_TRACK) {
730 state->numbers->numbers[x]++;
731 state->numbers->numbers[y+w]++;
735 for (i = 0; i < w+h; i++) {
736 if (state->numbers->numbers[i] == 0)
737 goto newpath; /* too boring */
740 if (params->single_ones) {
741 int last_was_one = 1, is_one; /* (disallow 1 clue at entry point) */
742 for (i = 0; i < w+h; i++) {
743 is_one = (state->numbers->numbers[i] == 1);
744 if (is_one && last_was_one)
745 goto newpath; /* disallow consecutive 1 clues. */
746 last_was_one = is_one;
748 if (state->numbers->numbers[w+h-1] == 1)
749 goto newpath; /* (disallow 1 clue at exit point) */
752 /* --- Add clues to make a soluble puzzle */
753 ret = add_clues(state, rs, params->diff);
754 if (ret != 1) goto newpath; /* couldn't make it soluble, or too easy */
756 /* --- Generate the game desc based on the generated grid. */
757 desc = snewn(w*h*3 + (w+h)*5, char);
758 for (i = j = 0; i < w*h; i++) {
759 if (!(state->sflags[i] & S_CLUE) && j > 0 &&
760 desc[j-1] >= 'a' && desc[j-1] < 'z')
762 else if (!(state->sflags[i] & S_CLUE))
765 unsigned int f = S_E_DIRS(state, i%w, i/w, E_TRACK);
766 desc[j++] = (f < 10) ? ('0' + f) : ('A' + (f-10));
771 for (x = 0; x < w; x++) {
772 p += sprintf(p, ",%s%d", x == state->numbers->col_s ? "S" : "",
773 state->numbers->numbers[x]);
775 for (y = 0; y < h; y++) {
776 p += sprintf(p, ",%s%d", y == state->numbers->row_s ? "S" : "",
777 state->numbers->numbers[y+w]);
781 ret = tracks_solve(state, DIFFCOUNT);
785 debug(("new_game_desc: %s", desc));
789 static char *validate_desc(const game_params *params, const char *desc)
791 int i = 0, w = params->w, h = params->h, in = 0, out = 0;
795 if (*desc >= '0' && *desc <= '9')
797 else if (*desc >= 'A' && *desc <= 'F')
798 f = (*desc - 'A' + 10);
799 else if (*desc >= 'a' && *desc <= 'z')
802 return "Game description contained unexpected characters";
806 return "Clue did not provide 2 direction flags";
812 for (i = 0; i < w+h; i++) {
814 return "Not enough numbers given after grid specification";
815 else if (*desc != ',')
816 return "Invalid character in number list";
825 while (*desc && isdigit((unsigned char)*desc)) desc++;
827 if (in != 1 || out != 1)
828 return "Puzzle must have one entrance and one exit";
830 return "Unexpected additional character at end of game description";
834 static game_state *new_game(midend *me, const game_params *params, const char *desc)
836 game_state *state = blank_game(params);
837 int w = params->w, h = params->h, i = 0;
841 if (*desc >= '0' && *desc <= '9')
843 else if (*desc >= 'A' && *desc <= 'F')
844 f = (*desc - 'A' + 10);
845 else if (*desc >= 'a' && *desc <= 'z')
849 int x = i % w, y = i / w;
851 assert(nbits[f] == 2);
853 state->sflags[i] |= (S_TRACK | S_CLUE);
854 if (f & U) S_E_SET(state, x, y, U, E_TRACK);
855 if (f & D) S_E_SET(state, x, y, D, E_TRACK);
856 if (f & L) S_E_SET(state, x, y, L, E_TRACK);
857 if (f & R) S_E_SET(state, x, y, R, E_TRACK);
863 for (i = 0; i < w+h; i++) {
864 assert(*desc == ',');
869 state->numbers->col_s = i;
871 state->numbers->row_s = i-w;
874 state->numbers->numbers[i] = atoi(desc);
875 while (*desc && isdigit((unsigned char)*desc)) desc++;
883 static int solve_set_sflag(game_state *state, int x, int y,
884 unsigned int f, const char *why)
886 int w = state->p.w, i = y*w + x;
888 if (state->sflags[i] & f)
890 debug(("solve: square (%d,%d) -> %s: %s",
891 x, y, (f == S_TRACK ? "TRACK" : "NOTRACK"), why));
892 if (state->sflags[i] & (f == S_TRACK ? S_NOTRACK : S_TRACK)) {
893 debug(("solve: opposite flag already set there, marking IMPOSSIBLE"));
894 state->impossible = TRUE;
896 state->sflags[i] |= f;
900 static int solve_set_eflag(game_state *state, int x, int y, int d,
901 unsigned int f, const char *why)
903 int sf = S_E_FLAGS(state, x, y, d);
907 debug(("solve: edge (%d,%d)/%c -> %s: %s", x, y,
908 (d == U) ? 'U' : (d == D) ? 'D' : (d == L) ? 'L' : 'R',
909 (f == S_TRACK ? "TRACK" : "NOTRACK"), why));
910 if (sf & (f == E_TRACK ? E_NOTRACK : E_TRACK)) {
911 debug(("solve: opposite flag already set there, marking IMPOSSIBLE"));
912 state->impossible = TRUE;
914 S_E_SET(state, x, y, d, f);
918 static int solve_update_flags(game_state *state)
920 int x, y, i, w = state->p.w, h = state->p.h, did = 0;
922 for (x = 0; x < w; x++) {
923 for (y = 0; y < h; y++) {
924 /* If a square is NOTRACK, all four edges must be. */
925 if (state->sflags[y*w + x] & S_NOTRACK) {
926 for (i = 0; i < 4; i++) {
927 unsigned int d = 1<<i;
928 did += solve_set_eflag(state, x, y, d, E_NOTRACK, "edges around NOTRACK");
932 /* If 3 or more edges around a square are NOTRACK, the square is. */
933 if (S_E_COUNT(state, x, y, E_NOTRACK) >= 3) {
934 did += solve_set_sflag(state, x, y, S_NOTRACK, "square has >2 NOTRACK edges");
937 /* If any edge around a square is TRACK, the square is. */
938 if (S_E_COUNT(state, x, y, E_TRACK) > 0) {
939 did += solve_set_sflag(state, x, y, S_TRACK, "square has TRACK edge");
942 /* If a square is TRACK and 2 edges are NOTRACK,
943 the other two edges must be TRACK. */
944 if ((state->sflags[y*w + x] & S_TRACK) &&
945 (S_E_COUNT(state, x, y, E_NOTRACK) == 2) &&
946 (S_E_COUNT(state, x, y, E_TRACK) < 2)) {
947 for (i = 0; i < 4; i++) {
948 unsigned int d = 1<<i;
949 if (!(S_E_FLAGS(state, x, y, d) & (E_TRACK|E_NOTRACK))) {
950 did += solve_set_eflag(state, x, y, d, E_TRACK,
951 "TRACK square/2 NOTRACK edges");
956 /* If a square is TRACK and 2 edges are TRACK, the other two
958 if ((state->sflags[y*w + x] & S_TRACK) &&
959 (S_E_COUNT(state, x, y, E_TRACK) == 2) &&
960 (S_E_COUNT(state, x, y, E_NOTRACK) < 2)) {
961 for (i = 0; i < 4; i++) {
962 unsigned int d = 1<<i;
963 if (!(S_E_FLAGS(state, x, y, d) & (E_TRACK|E_NOTRACK))) {
964 did += solve_set_eflag(state, x, y, d, E_NOTRACK,
965 "TRACK square/2 TRACK edges");
974 static int solve_count_col(game_state *state, int col, unsigned int f)
976 int i, n, c = 0, h = state->p.h, w = state->p.w;
977 for (n = 0, i = col; n < h; n++, i += w) {
978 if (state->sflags[i] & f) c++;
983 static int solve_count_row(game_state *state, int row, unsigned int f)
985 int i, n, c = 0, w = state->p.w;
986 for (n = 0, i = w*row; n < state->p.w; n++, i++) {
987 if (state->sflags[i] & f) c++;
992 static int solve_count_clues_sub(game_state *state, int si, int id, int n,
993 int target, const char *what)
995 int ctrack = 0, cnotrack = 0, did = 0, j, i, w = state->p.w;
997 for (j = 0, i = si; j < n; j++, i += id) {
998 if (state->sflags[i] & S_TRACK)
1000 if (state->sflags[i] & S_NOTRACK)
1003 if (ctrack == target) {
1004 /* everything that's not S_TRACK must be S_NOTRACK. */
1005 for (j = 0, i = si; j < n; j++, i += id) {
1006 if (!(state->sflags[i] & S_TRACK))
1007 did += solve_set_sflag(state, i%w, i/w, S_NOTRACK, what);
1010 if (cnotrack == (n-target)) {
1011 /* everything that's not S_NOTRACK must be S_TRACK. */
1012 for (j = 0, i = si; j < n; j++, i += id) {
1013 if (!(state->sflags[i] & S_NOTRACK))
1014 did += solve_set_sflag(state, i%w, i/w, S_TRACK, what);
1020 static int solve_count_clues(game_state *state)
1022 int w = state->p.w, h = state->p.h, x, y, target, did = 0;
1024 for (x = 0; x < w; x++) {
1025 target = state->numbers->numbers[x];
1026 did += solve_count_clues_sub(state, x, w, h, target, "col count");
1028 for (y = 0; y < h; y++) {
1029 target = state->numbers->numbers[w+y];
1030 did += solve_count_clues_sub(state, y*w, 1, w, target, "row count");
1035 static int solve_check_single_sub(game_state *state, int si, int id, int n,
1036 int target, unsigned int perpf,
1039 int ctrack = 0, nperp = 0, did = 0, j, i, w = state->p.w;
1040 int n1edge = 0, i1edge = 0, ox, oy, x, y;
1041 unsigned int impossible = 0;
1043 /* For rows or columns which only have one more square to put a track in, we
1044 know the only way a new track section could be there would be to run
1045 perpendicular to the track (otherwise we'd need at least two free squares).
1046 So, if there is nowhere we can run perpendicular to the track (e.g. because
1047 we're on an edge) we know the extra track section much be on one end of an
1048 existing section. */
1050 for (j = 0, i = si; j < n; j++, i += id) {
1051 if (state->sflags[i] & S_TRACK)
1053 impossible = S_E_DIRS(state, i%w, i/w, E_NOTRACK);
1054 if ((perpf & impossible) == 0)
1056 if (S_E_COUNT(state, i%w, i/w, E_TRACK) <= 1) {
1061 if (ctrack != (target-1)) return 0;
1062 if (nperp > 0 || n1edge != 1) return 0;
1064 debug(("check_single from (%d,%d): 1 match from (%d,%d)",
1065 si%w, si/w, i1edge%w, i1edge/w));
1067 /* We have a match: anything that's more than 1 away from this square
1068 cannot now contain a track. */
1071 for (j = 0, i = si; j < n; j++, i += id) {
1074 if (abs(ox-x) > 1 || abs(oy-y) > 1) {
1075 if (!(state->sflags[i] & S_TRACK))
1076 did += solve_set_sflag(state, x, y, S_NOTRACK, what);
1083 static int solve_check_single(game_state *state)
1085 int w = state->p.w, h = state->p.h, x, y, target, did = 0;
1087 for (x = 0; x < w; x++) {
1088 target = state->numbers->numbers[x];
1089 did += solve_check_single_sub(state, x, w, h, target, R|L, "single on col");
1091 for (y = 0; y < h; y++) {
1092 target = state->numbers->numbers[w+y];
1093 did += solve_check_single_sub(state, y*w, 1, w, target, U|D, "single on row");
1098 static int solve_check_loose_sub(game_state *state, int si, int id, int n,
1099 int target, unsigned int perpf,
1102 int nperp = 0, nloose = 0, e2count = 0, did = 0, i, j, k;
1104 unsigned int parf = ALLDIR & (~perpf);
1106 for (j = 0, i = si; j < n; j++, i += id) {
1107 int fcount = S_E_COUNT(state, i%w, i/w, E_TRACK);
1109 e2count++; /* this cell has 2 definite edges */
1110 state->sflags[i] &= ~S_MARK;
1111 if (fcount == 1 && (parf & S_E_DIRS(state, i%w, i/w, E_TRACK))) {
1112 nloose++; /* this cell has a loose end (single flag set parallel
1113 to the direction of this row/column) */
1114 state->sflags[i] |= S_MARK; /* mark loose ends */
1116 if (fcount != 2 && !(perpf & S_E_DIRS(state, i%w, i/w, E_NOTRACK)))
1117 nperp++; /* we could lay perpendicular across this cell */
1120 if (nloose > (target - e2count)) {
1121 debug(("check %s from (%d,%d): more loose (%d) than empty (%d), IMPOSSIBLE",
1122 what, si%w, si/w, nloose, target-e2count));
1123 state->impossible = TRUE;
1125 if (nloose > 0 && nloose == (target - e2count)) {
1126 debug(("check %s from (%d,%d): nloose = empty (%d), forcing loners out.",
1127 what, si%w, si/w, nloose));
1128 for (j = 0, i = si; j < n; j++, i += id) {
1129 if (!(state->sflags[i] & S_MARK))
1130 continue; /* skip non-loose ends */
1131 if (j > 0 && state->sflags[i-id] & S_MARK)
1132 continue; /* next to other loose end, could join up */
1133 if (j < (n-1) && state->sflags[i+id] & S_MARK)
1134 continue; /* ditto */
1136 for (k = 0; k < 4; k++) {
1137 if ((parf & (1<<k)) &&
1138 !(S_E_DIRS(state, i%w, i/w, E_TRACK) & (1<<k))) {
1139 /* set as NOTRACK the edge parallel to the row/column that's
1141 did += solve_set_eflag(state, i%w, i/w, 1<<k, E_NOTRACK, what);
1146 if (nloose == 1 && (target - e2count) == 2 && nperp == 0) {
1147 debug(("check %s from (%d,%d): 1 loose end, 2 empty squares, forcing parallel",
1149 for (j = 0, i = si; j < n; j++, i += id) {
1150 if (!(state->sflags[i] & S_MARK))
1151 continue; /* skip non-loose ends */
1152 for (k = 0; k < 4; k++) {
1154 did += solve_set_eflag(state, i%w, i/w, 1<<k, E_TRACK, what);
1162 static int solve_check_loose_ends(game_state *state)
1164 int w = state->p.w, h = state->p.h, x, y, target, did = 0;
1166 for (x = 0; x < w; x++) {
1167 target = state->numbers->numbers[x];
1168 did += solve_check_loose_sub(state, x, w, h, target, R|L, "loose on col");
1170 for (y = 0; y < h; y++) {
1171 target = state->numbers->numbers[w+y];
1172 did += solve_check_loose_sub(state, y*w, 1, w, target, U|D, "loose on row");
1177 static int solve_check_loop_sub(game_state *state, int x, int y, int dir,
1178 int *dsf, int startc, int endc)
1180 int w = state->p.w, h = state->p.h, i = y*w+x, j, k, satisfied = 1;
1182 j = (y+DY(dir))*w + (x+DX(dir));
1184 assert(i < w*h && j < w*h);
1186 if ((state->sflags[i] & S_TRACK) &&
1187 (state->sflags[j] & S_TRACK) &&
1188 !(S_E_DIRS(state, x, y, E_TRACK) & dir) &&
1189 !(S_E_DIRS(state, x, y, E_NOTRACK) & dir)) {
1190 int ic = dsf_canonify(dsf, i), jc = dsf_canonify(dsf, j);
1192 return solve_set_eflag(state, x, y, dir, E_NOTRACK, "would close loop");
1194 if ((ic == startc && jc == endc) || (ic == endc && jc == startc)) {
1195 debug(("Adding link at (%d,%d) would join start to end", x, y));
1196 /* We mustn't join the start to the end if:
1197 - there are other bits of track that aren't attached to either end
1198 - the clues are not fully satisfied yet
1200 for (k = 0; k < w*h; k++) {
1201 if (state->sflags[k] & S_TRACK &&
1202 dsf_canonify(dsf, k) != startc && dsf_canonify(dsf, k) != endc) {
1203 return solve_set_eflag(state, x, y, dir, E_NOTRACK,
1204 "joins start to end but misses tracks");
1207 for (k = 0; k < w; k++) {
1208 int target = state->numbers->numbers[k];
1209 int ntracks = solve_count_col(state, k, S_TRACK);
1210 if (ntracks < target) satisfied = 0;
1212 for (k = 0; k < h; k++) {
1213 int target = state->numbers->numbers[w+k];
1214 int ntracks = solve_count_row(state, k, S_TRACK);
1215 if (ntracks < target) satisfied = 0;
1218 return solve_set_eflag(state, x, y, dir, E_NOTRACK,
1219 "joins start to end with incomplete clues");
1226 static int solve_check_loop(game_state *state)
1228 int w = state->p.w, h = state->p.h, x, y, i, j, did = 0;
1229 int *dsf, startc, endc;
1231 /* TODO eventually we should pull this out into a solver struct and keep it
1232 updated as we connect squares. For now we recreate it every time we try
1233 this particular solver step. */
1234 dsf = snewn(w*h, int);
1237 /* Work out the connectedness of the current loop set. */
1238 for (x = 0; x < w; x++) {
1239 for (y = 0; y < h; y++) {
1241 if (x < (w-1) && S_E_DIRS(state, x, y, E_TRACK) & R) {
1242 /* connection to the right... */
1244 assert(i < w*h && j < w*h);
1245 dsf_merge(dsf, i, j);
1247 if (y < (h-1) && S_E_DIRS(state, x, y, E_TRACK) & D) {
1248 /* connection down... */
1250 assert(i < w*h && j < w*h);
1251 dsf_merge(dsf, i, j);
1253 /* NB no need to check up and left because they'll have been checked
1254 by the other side. */
1258 startc = dsf_canonify(dsf, state->numbers->row_s*w);
1259 endc = dsf_canonify(dsf, (h-1)*w+state->numbers->col_s);
1261 /* Now look at all adjacent squares that are both S_TRACK: if connecting
1262 any of them would complete a loop (i.e. they're both the same dsf class
1263 already) then that edge must be NOTRACK. */
1264 for (x = 0; x < w; x++) {
1265 for (y = 0; y < h; y++) {
1267 did += solve_check_loop_sub(state, x, y, R, dsf, startc, endc);
1269 did += solve_check_loop_sub(state, x, y, D, dsf, startc, endc);
1278 static void solve_discount_edge(game_state *state, int x, int y, int d)
1280 if (S_E_DIRS(state, x, y, E_TRACK) & d) {
1281 assert(state->sflags[y*state->p.w + x] & S_CLUE);
1282 return; /* (only) clue squares can have outer edges set. */
1284 solve_set_eflag(state, x, y, d, E_NOTRACK, "outer edge");
1287 static int tracks_solve(game_state *state, int diff)
1289 int didsth, x, y, w = state->p.w, h = state->p.h;
1291 debug(("solve..."));
1292 state->impossible = FALSE;
1294 /* Set all the outer border edges as no-track. */
1295 for (x = 0; x < w; x++) {
1296 solve_discount_edge(state, x, 0, U);
1297 solve_discount_edge(state, x, h-1, D);
1299 for (y = 0; y < h; y++) {
1300 solve_discount_edge(state, 0, y, L);
1301 solve_discount_edge(state, w-1, y, R);
1307 didsth += solve_update_flags(state);
1308 didsth += solve_count_clues(state);
1309 didsth += solve_check_loop(state);
1311 if (diff >= DIFF_TRICKY) {
1312 didsth += solve_check_single(state);
1313 didsth += solve_check_loose_ends(state);
1316 if (!didsth || state->impossible) break;
1319 return state->impossible ? -1 : check_completion(state, FALSE) ? 1 : 0;
1322 static char *move_string_diff(const game_state *before, const game_state *after, int issolve)
1324 int w = after->p.w, h = after->p.h, i, j;
1325 char *move = snewn(w*h*40, char), *p = move;
1326 const char *sep = "";
1327 unsigned int otf, ntf, onf, nnf;
1333 for (i = 0; i < w*h; i++) {
1334 otf = S_E_DIRS(before, i%w, i/w, E_TRACK);
1335 ntf = S_E_DIRS(after, i%w, i/w, E_TRACK);
1336 onf = S_E_DIRS(before, i%w, i/w, E_NOTRACK);
1337 nnf = S_E_DIRS(after, i%w, i/w, E_NOTRACK);
1339 for (j = 0; j < 4; j++) {
1341 if ((otf & df) != (ntf & df)) {
1342 p += sprintf(p, "%s%c%c%d,%d", sep,
1343 (ntf & df) ? 'T' : 't', MOVECHAR(df), i%w, i/w);
1346 if ((onf & df) != (nnf & df)) {
1347 p += sprintf(p, "%s%c%c%d,%d", sep,
1348 (nnf & df) ? 'N' : 'n', MOVECHAR(df), i%w, i/w);
1353 if ((before->sflags[i] & S_NOTRACK) != (after->sflags[i] & S_NOTRACK)) {
1354 p += sprintf(p, "%s%cS%d,%d", sep,
1355 (after->sflags[i] & S_NOTRACK) ? 'N' : 'n', i%w, i/w);
1358 if ((before->sflags[i] & S_TRACK) != (after->sflags[i] & S_TRACK)) {
1359 p += sprintf(p, "%s%cS%d,%d", sep,
1360 (after->sflags[i] & S_TRACK) ? 'T' : 't', i%w, i/w);
1365 move = sresize(move, p - move, char);
1370 static char *solve_game(const game_state *state, const game_state *currstate,
1371 const char *aux, char **error)
1377 solved = dup_game(currstate);
1378 ret = tracks_solve(solved, DIFFCOUNT);
1381 solved = dup_game(state);
1382 ret = tracks_solve(solved, DIFFCOUNT);
1386 *error = "Unable to find solution";
1389 move = move_string_diff(currstate, solved, TRUE);
1396 static int game_can_format_as_text_now(const game_params *params)
1401 static char *game_text_format(const game_state *state)
1404 int x, y, len, w = state->p.w, h = state->p.h;
1406 len = ((w*2) + 4) * ((h*2)+4) + 2;
1407 ret = snewn(len+1, char);
1410 /* top line: column clues */
1413 for (x = 0; x < w; x++) {
1414 *p++ = (state->numbers->numbers[x] < 10 ?
1415 '0' + state->numbers->numbers[x] :
1416 'A' + state->numbers->numbers[x] - 10);
1421 /* second line: top edge */
1424 for (x = 0; x < w*2-1; x++)
1429 /* grid rows: one line of squares, one line of edges. */
1430 for (y = 0; y < h; y++) {
1431 /* grid square line */
1432 *p++ = (y == state->numbers->row_s) ? 'A' : ' ';
1433 *p++ = (y == state->numbers->row_s) ? '-' : '|';
1435 for (x = 0; x < w; x++) {
1436 unsigned int f = S_E_DIRS(state, x, y, E_TRACK);
1437 if (state->sflags[y*w+x] & S_CLUE) *p++ = 'C';
1438 else if (f == LU || f == RD) *p++ = '/';
1439 else if (f == LD || f == RU) *p++ = '\\';
1440 else if (f == UD) *p++ = '|';
1441 else if (f == RL) *p++ = '-';
1442 else if (state->sflags[y*w+x] & S_NOTRACK) *p++ = 'x';
1446 *p++ = (f & R) ? '-' : ' ';
1450 *p++ = (state->numbers->numbers[w+y] < 10 ?
1451 '0' + state->numbers->numbers[w+y] :
1452 'A' + state->numbers->numbers[w+y] - 10);
1455 if (y == h-1) continue;
1460 for (x = 0; x < w; x++) {
1461 unsigned int f = S_E_DIRS(state, x, y, E_TRACK);
1462 *p++ = (f & D) ? '|' : ' ';
1463 *p++ = (x < w-1) ? ' ' : '|';
1468 /* next line: bottom edge */
1471 for (x = 0; x < w*2-1; x++)
1472 *p++ = (x == state->numbers->col_s*2) ? '|' : '-';
1476 /* final line: bottom clue */
1479 for (x = 0; x < w*2-1; x++)
1480 *p++ = (x == state->numbers->col_s*2) ? 'B' : ' ';
1487 static void debug_state(game_state *state, const char *what) {
1488 char *sstring = game_text_format(state);
1489 debug(("%s: %s", what, sstring));
1493 static void dsf_update_completion(game_state *state, int ax, int ay,
1496 int w = state->p.w, ai = ay*w+ax, bx, by, bi;
1498 if (!(S_E_DIRS(state, ax, ay, E_TRACK) & dir)) return;
1502 if (!INGRID(state, bx, by)) return;
1505 dsf_merge(dsf, ai, bi);
1508 struct tracks_neighbour_ctx {
1510 int i, n, neighbours[4];
1512 static int tracks_neighbour(int vertex, void *vctx)
1514 struct tracks_neighbour_ctx *ctx = (struct tracks_neighbour_ctx *)vctx;
1516 game_state *state = ctx->state;
1517 int w = state->p.w, x = vertex % w, y = vertex / w;
1518 int dirs = S_E_DIRS(state, x, y, E_TRACK);
1521 ctx->i = ctx->n = 0;
1523 for (j = 0; j < 4; j++) {
1526 int nx = x + DX(dir), ny = y + DY(dir);
1527 if (INGRID(state, nx, ny))
1528 ctx->neighbours[ctx->n++] = ny * w + nx;
1533 if (ctx->i < ctx->n)
1534 return ctx->neighbours[ctx->i++];
1539 static int check_completion(game_state *state, int mark)
1541 int w = state->p.w, h = state->p.h, x, y, i, target, ret = TRUE;
1542 int ntrack, nnotrack, ntrackcomplete;
1543 int *dsf, pathclass;
1544 struct findloopstate *fls;
1545 struct tracks_neighbour_ctx ctx;
1548 for (i = 0; i < w+h; i++) {
1549 state->num_errors[i] = 0;
1551 for (i = 0; i < w*h; i++) {
1552 state->sflags[i] &= ~S_ERROR;
1553 if (S_E_COUNT(state, i%w, i/w, E_TRACK) > 0) {
1554 if (S_E_COUNT(state, i%w, i/w, E_TRACK) > 2) {
1556 state->sflags[i] |= S_ERROR;
1562 /* A cell is 'complete', for the purposes of marking the game as
1563 * finished, if it has two edges marked as TRACK. But it only has
1564 * to have one edge marked as TRACK, or be filled in as trackful
1565 * without any specific edges known, to count towards checking
1566 * row/column clue errors. */
1567 for (x = 0; x < w; x++) {
1568 target = state->numbers->numbers[x];
1569 ntrack = nnotrack = ntrackcomplete = 0;
1570 for (y = 0; y < h; y++) {
1571 if (S_E_COUNT(state, x, y, E_TRACK) > 0 ||
1572 state->sflags[y*w+x] & S_TRACK)
1574 if (S_E_COUNT(state, x, y, E_TRACK) == 2)
1576 if (state->sflags[y*w+x] & S_NOTRACK)
1580 if (ntrack > target || nnotrack > (h-target)) {
1581 debug(("col %d error: target %d, track %d, notrack %d",
1582 x, target, ntrack, nnotrack));
1583 state->num_errors[x] = 1;
1587 if (ntrackcomplete != target)
1590 for (y = 0; y < h; y++) {
1591 target = state->numbers->numbers[w+y];
1592 ntrack = nnotrack = ntrackcomplete = 0;
1593 for (x = 0; x < w; x++) {
1594 if (S_E_COUNT(state, x, y, E_TRACK) > 0 ||
1595 state->sflags[y*w+x] & S_TRACK)
1597 if (S_E_COUNT(state, x, y, E_TRACK) == 2)
1599 if (state->sflags[y*w+x] & S_NOTRACK)
1603 if (ntrack > target || nnotrack > (w-target)) {
1604 debug(("row %d error: target %d, track %d, notrack %d",
1605 y, target, ntrack, nnotrack));
1606 state->num_errors[w+y] = 1;
1610 if (ntrackcomplete != target)
1614 dsf = snewn(w*h, int);
1617 for (x = 0; x < w; x++) {
1618 for (y = 0; y < h; y++) {
1619 dsf_update_completion(state, x, y, R, dsf);
1620 dsf_update_completion(state, x, y, D, dsf);
1624 fls = findloop_new_state(w*h);
1626 if (findloop_run(fls, w*h, tracks_neighbour, &ctx)) {
1627 debug(("loop detected, not complete"));
1628 ret = FALSE; /* no loop allowed */
1630 for (x = 0; x < w; x++) {
1631 for (y = 0; y < h; y++) {
1635 for (v = tracks_neighbour(u, &ctx); v >= 0;
1636 v = tracks_neighbour(-1, &ctx))
1637 if (findloop_is_loop_edge(fls, u, v))
1638 state->sflags[y*w+x] |= S_ERROR;
1643 findloop_free_state(fls);
1646 pathclass = dsf_canonify(dsf, state->numbers->row_s*w);
1647 if (pathclass == dsf_canonify(dsf, (h-1)*w + state->numbers->col_s)) {
1648 /* We have a continuous path between the entrance and the exit: any
1649 other path must be in error. */
1650 for (i = 0; i < w*h; i++) {
1651 if ((dsf_canonify(dsf, i) != pathclass) &&
1652 ((state->sflags[i] & S_TRACK) ||
1653 (S_E_COUNT(state, i%w, i/w, E_TRACK) > 0))) {
1655 state->sflags[i] |= S_ERROR;
1659 /* If we _don't_ have such a path, then certainly the game
1660 * can't be in a winning state. So even if we're not
1661 * highlighting any _errors_, we certainly shouldn't
1668 state->completed = ret;
1673 /* Code borrowed from Pearl. */
1676 int dragging, clearing, notrack;
1677 int drag_sx, drag_sy, drag_ex, drag_ey; /* drag start and end grid coords */
1678 int clickx, clicky; /* pixel position of initial click */
1680 int curx, cury; /* grid position of keyboard cursor; uses half-size grid */
1681 int cursor_active; /* TRUE iff cursor is shown */
1684 static game_ui *new_ui(const game_state *state)
1686 game_ui *ui = snew(game_ui);
1688 ui->clearing = ui->notrack = ui->dragging = 0;
1689 ui->drag_sx = ui->drag_sy = ui->drag_ex = ui->drag_ey = -1;
1690 ui->cursor_active = FALSE;
1691 ui->curx = ui->cury = 1;
1696 static void free_ui(game_ui *ui)
1701 static char *encode_ui(const game_ui *ui)
1706 static void decode_ui(game_ui *ui, const char *encoding)
1710 static void game_changed_state(game_ui *ui, const game_state *oldstate,
1711 const game_state *newstate)
1715 #define PREFERRED_TILE_SIZE 30
1716 #define HALFSZ (ds->sz6*3)
1717 #define THIRDSZ (ds->sz6*2)
1718 #define TILE_SIZE (ds->sz6*6)
1720 #define BORDER (TILE_SIZE/8)
1721 #define LINE_THICK (TILE_SIZE/16)
1722 #define GRID_LINE_TL (ds->grid_line_tl)
1723 #define GRID_LINE_BR (ds->grid_line_br)
1724 #define GRID_LINE_ALL (ds->grid_line_all)
1726 #define COORD(x) ( (x+1) * TILE_SIZE + BORDER )
1727 #define CENTERED_COORD(x) ( COORD(x) + TILE_SIZE/2 )
1728 #define FROMCOORD(x) ( ((x) < BORDER) ? -1 : ( ((x) - BORDER) / TILE_SIZE) - 1 )
1730 #define DS_DSHIFT 4 /* R/U/L/D shift, for drag-in-progress flags */
1732 #define DS_ERROR (1 << 8)
1733 #define DS_CLUE (1 << 9)
1734 #define DS_NOTRACK (1 << 10)
1735 #define DS_FLASH (1 << 11)
1736 #define DS_CURSOR (1 << 12) /* cursor in square (centre, or on edge) */
1737 #define DS_TRACK (1 << 13)
1738 #define DS_CLEARING (1 << 14)
1740 #define DS_NSHIFT 16 /* R/U/L/D shift, for no-track edge flags */
1741 #define DS_CSHIFT 20 /* R/U/L/D shift, for cursor-on-edge */
1743 struct game_drawstate {
1744 int sz6, grid_line_all, grid_line_tl, grid_line_br;
1748 unsigned int *flags, *flags_drag;
1752 static void update_ui_drag(const game_state *state, game_ui *ui, int gx, int gy)
1754 int w = state->p.w, h = state->p.h;
1755 int dx = abs(ui->drag_sx - gx), dy = abs(ui->drag_sy - gy);
1758 ui->drag_ex = gx < 0 ? 0 : gx >= w ? w-1 : gx;
1759 ui->drag_ey = ui->drag_sy;
1760 ui->dragging = TRUE;
1761 } else if (dx == 0) {
1762 ui->drag_ex = ui->drag_sx;
1763 ui->drag_ey = gy < 0 ? 0 : gy >= h ? h-1 : gy;
1764 ui->dragging = TRUE;
1766 ui->drag_ex = ui->drag_sx;
1767 ui->drag_ey = ui->drag_sy;
1768 ui->dragging = FALSE;
1772 static int ui_can_flip_edge(const game_state *state, int x, int y, int dir,
1775 int w = state->p.w /*, h = state->shared->h, sz = state->shared->sz */;
1776 int x2 = x + DX(dir);
1777 int y2 = y + DY(dir);
1778 unsigned int sf1, sf2, ef;
1780 if (!INGRID(state, x, y) || !INGRID(state, x2, y2))
1783 sf1 = state->sflags[y*w + x];
1784 sf2 = state->sflags[y2*w + x2];
1785 if ( !notrack && ((sf1 & S_CLUE) || (sf2 & S_CLUE)) )
1788 ef = S_E_FLAGS(state, x, y, dir);
1790 /* if we're going to _set_ NOTRACK (i.e. the flag is currently unset),
1791 make sure the edge is not already set to TRACK. The adjacent squares
1792 could be set to TRACK, because we don't know which edges the general
1793 square setting refers to. */
1794 if (!(ef & E_NOTRACK) && (ef & E_TRACK))
1797 if (!(ef & E_TRACK)) {
1798 /* if we're going to _set_ TRACK, make sure neither adjacent square nor
1799 the edge itself is already set to NOTRACK. */
1800 if ((sf1 & S_NOTRACK) || (sf2 & S_NOTRACK) || (ef & E_NOTRACK))
1802 /* if we're going to _set_ TRACK, make sure neither adjacent square has
1803 2 track flags already. */
1804 if ((S_E_COUNT(state, x, y, E_TRACK) >= 2) ||
1805 (S_E_COUNT(state, x2, y2, E_TRACK) >= 2))
1812 static int ui_can_flip_square(const game_state *state, int x, int y, int notrack)
1814 int w = state->p.w, trackc;
1817 if (!INGRID(state, x, y)) return FALSE;
1818 sf = state->sflags[y*w+x];
1819 trackc = S_E_COUNT(state, x, y, E_TRACK);
1821 if (sf & S_CLUE) return FALSE;
1824 /* If we're setting S_NOTRACK, we cannot have either S_TRACK or any E_TRACK. */
1825 if (!(sf & S_NOTRACK) && ((sf & S_TRACK) || (trackc > 0)))
1828 /* If we're setting S_TRACK, we cannot have any S_NOTRACK (we could have
1829 E_NOTRACK, though, because one or two wouldn't rule out a track) */
1830 if (!(sf & S_TRACK) && (sf & S_NOTRACK))
1836 static char *edge_flip_str(const game_state *state, int x, int y, int dir, int notrack, char *buf) {
1837 unsigned ef = S_E_FLAGS(state, x, y, dir);
1841 c = (ef & E_NOTRACK) ? 'n' : 'N';
1843 c = (ef & E_TRACK) ? 't' : 'T';
1845 sprintf(buf, "%c%c%d,%d", c, MOVECHAR(dir), x, y);
1849 static char *square_flip_str(const game_state *state, int x, int y, int notrack, char *buf) {
1850 unsigned f = state->sflags[y*state->p.w+x];
1854 c = (f & E_NOTRACK) ? 'n' : 'N';
1856 c = (f & E_TRACK) ? 't' : 'T';
1858 sprintf(buf, "%cS%d,%d", c, x, y);
1862 #define SIGN(x) ((x<0) ? -1 : (x>0))
1864 static game_state *copy_and_apply_drag(const game_state *state, const game_ui *ui)
1866 game_state *after = dup_game(state);
1867 int x1, y1, x2, y2, x, y, w = state->p.w;
1868 unsigned f = ui->notrack ? S_NOTRACK : S_TRACK, ff;
1870 x1 = min(ui->drag_sx, ui->drag_ex); x2 = max(ui->drag_sx, ui->drag_ex);
1871 y1 = min(ui->drag_sy, ui->drag_ey); y2 = max(ui->drag_sy, ui->drag_ey);
1873 /* actually either x1 == x2, or y1 == y2, but it's easier just to code
1875 for (x = x1; x <= x2; x++) {
1876 for (y = y1; y <= y2; y++) {
1877 ff = state->sflags[y*w+x];
1878 if (ui->clearing && !(ff & f))
1879 continue; /* nothing to do, clearing and already clear */
1880 else if (!ui->clearing && (ff & f))
1881 continue; /* nothing to do, setting and already set */
1882 else if (ui_can_flip_square(state, x, y, ui->notrack))
1883 after->sflags[y*w+x] ^= f;
1889 #define KEY_DIRECTION(btn) (\
1890 (btn) == CURSOR_DOWN ? D : (btn) == CURSOR_UP ? U :\
1891 (btn) == CURSOR_LEFT ? L : R)
1893 static char *interpret_move(const game_state *state, game_ui *ui,
1894 const game_drawstate *ds,
1895 int x, int y, int button)
1897 int w = state->p.w, h = state->p.h, direction;
1898 int gx = FROMCOORD(x), gy = FROMCOORD(y);
1901 /* --- mouse operations --- */
1903 if (IS_MOUSE_DOWN(button)) {
1904 ui->cursor_active = FALSE;
1905 ui->dragging = FALSE;
1907 if (!INGRID(state, gx, gy)) {
1908 /* can't drag from off grid */
1912 if (button == RIGHT_BUTTON) {
1914 ui->clearing = state->sflags[gy*w+gx] & S_NOTRACK;
1916 ui->notrack = FALSE;
1917 ui->clearing = state->sflags[gy*w+gx] & S_TRACK;
1922 ui->drag_sx = ui->drag_ex = gx;
1923 ui->drag_sy = ui->drag_ey = gy;
1928 if (IS_MOUSE_DRAG(button)) {
1929 ui->cursor_active = FALSE;
1930 update_ui_drag(state, ui, gx, gy);
1934 if (IS_MOUSE_RELEASE(button)) {
1935 ui->cursor_active = FALSE;
1937 (ui->drag_sx != ui->drag_ex || ui->drag_sy != ui->drag_ey)) {
1938 game_state *dragged = copy_and_apply_drag(state, ui);
1939 char *ret = move_string_diff(state, dragged, FALSE);
1948 /* We might still have been dragging (and just done a one-
1949 * square drag): cancel drag, so undo doesn't make it like
1950 * a drag-in-progress. */
1953 /* Click (or tiny drag). Work out which edge we were
1957 * We process clicks based on the mouse-down location,
1958 * because that's more natural for a user to carefully
1959 * control than the mouse-up.
1964 cx = CENTERED_COORD(gx);
1965 cy = CENTERED_COORD(gy);
1967 if (!INGRID(state, gx, gy) || FROMCOORD(x) != gx || FROMCOORD(y) != gy)
1970 if (max(abs(x-cx),abs(y-cy)) < TILE_SIZE/4) {
1971 if (ui_can_flip_square(state, gx, gy, button == RIGHT_RELEASE))
1972 return square_flip_str(state, gx, gy, button == RIGHT_RELEASE, tmpbuf);
1975 if (abs(x-cx) < abs(y-cy)) {
1976 /* Closest to top/bottom edge. */
1977 direction = (y < cy) ? U : D;
1979 /* Closest to left/right edge. */
1980 direction = (x < cx) ? L : R;
1982 if (ui_can_flip_edge(state, gx, gy, direction,
1983 button == RIGHT_RELEASE))
1984 return edge_flip_str(state, gx, gy, direction,
1985 button == RIGHT_RELEASE, tmpbuf);
1992 /* --- cursor/keyboard operations --- */
1994 if (IS_CURSOR_MOVE(button)) {
1995 int dx = (button == CURSOR_LEFT) ? -1 : ((button == CURSOR_RIGHT) ? +1 : 0);
1996 int dy = (button == CURSOR_DOWN) ? +1 : ((button == CURSOR_UP) ? -1 : 0);
1998 if (!ui->cursor_active) {
1999 ui->cursor_active = TRUE;
2003 ui->curx = ui->curx + dx;
2004 ui->cury = ui->cury + dy;
2005 if ((ui->curx % 2 == 0) && (ui->cury % 2 == 0)) {
2006 /* disallow cursor on square corners: centres and edges only */
2007 ui->curx += dx; ui->cury += dy;
2009 ui->curx = min(max(ui->curx, 1), 2*w-1);
2010 ui->cury = min(max(ui->cury, 1), 2*h-1);
2014 if (IS_CURSOR_SELECT(button)) {
2015 if (!ui->cursor_active) {
2016 ui->cursor_active = TRUE;
2019 /* click on square corner does nothing (shouldn't get here) */
2020 if ((ui->curx % 2) == 0 && (ui->cury % 2 == 0))
2025 direction = ((ui->curx % 2) == 0) ? L : ((ui->cury % 2) == 0) ? U : 0;
2028 ui_can_flip_edge(state, gx, gy, direction, button == CURSOR_SELECT2))
2029 return edge_flip_str(state, gx, gy, direction, button == CURSOR_SELECT2, tmpbuf);
2030 else if (!direction &&
2031 ui_can_flip_square(state, gx, gy, button == CURSOR_SELECT2))
2032 return square_flip_str(state, gx, gy, button == CURSOR_SELECT2, tmpbuf);
2037 /* helps to debug the solver */
2038 if (button == 'H' || button == 'h')
2045 static game_state *execute_move(const game_state *state, const char *move)
2047 int w = state->p.w, x, y, n, i;
2050 game_state *ret = dup_game(state);
2052 /* this is breaking the bank on GTK, which vsprintf's into a fixed-size buffer
2053 * which is 4096 bytes long. vsnprintf needs a feature-test macro to use, faff. */
2054 /*debug(("move: %s\n", move));*/
2059 ret->used_solve = TRUE;
2061 } else if (c == 'T' || c == 't' || c == 'N' || c == 'n') {
2062 /* set track, clear track; set notrack, clear notrack */
2064 if (sscanf(move, "%c%d,%d%n", &d, &x, &y, &n) != 3)
2066 if (!INGRID(state, x, y)) goto badmove;
2068 f = (c == 'T' || c == 't') ? S_TRACK : S_NOTRACK;
2071 if (c == 'T' || c == 'N')
2072 ret->sflags[y*w+x] |= f;
2074 ret->sflags[y*w+x] &= ~f;
2075 } else if (d == 'U' || d == 'D' || d == 'L' || d == 'R') {
2076 for (i = 0; i < 4; i++) {
2079 if (MOVECHAR(df) == d) {
2080 if (c == 'T' || c == 'N')
2081 S_E_SET(ret, x, y, df, f);
2083 S_E_CLEAR(ret, x, y, df, f);
2089 } else if (c == 'H') {
2090 tracks_solve(ret, DIFFCOUNT);
2101 check_completion(ret, TRUE);
2110 /* ----------------------------------------------------------------------
2114 #define FLASH_TIME 0.5F
2116 static void game_compute_size(const game_params *params, int tilesize,
2119 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
2123 ads.sz6 = tilesize/6;
2124 *x = (params->w+2) * TILE_SIZE + 2 * BORDER;
2125 *y = (params->h+2) * TILE_SIZE + 2 * BORDER;
2128 static void game_set_size(drawing *dr, game_drawstate *ds,
2129 const game_params *params, int tilesize)
2131 ds->sz6 = tilesize/6;
2132 ds->grid_line_all = max(LINE_THICK, 1);
2133 ds->grid_line_br = ds->grid_line_all / 2;
2134 ds->grid_line_tl = ds->grid_line_all - ds->grid_line_br;
2138 COL_BACKGROUND, COL_LOWLIGHT, COL_HIGHLIGHT,
2139 COL_TRACK_BACKGROUND = COL_LOWLIGHT,
2140 COL_GRID, COL_CLUE, COL_CURSOR,
2141 COL_TRACK, COL_TRACK_CLUE, COL_SLEEPER,
2142 COL_DRAGON, COL_DRAGOFF,
2143 COL_ERROR, COL_FLASH, COL_ERROR_BACKGROUND,
2147 static float *game_colours(frontend *fe, int *ncolours)
2149 float *ret = snewn(3 * NCOLOURS, float);
2152 game_mkhighlight(fe, ret, COL_BACKGROUND, COL_HIGHLIGHT, COL_LOWLIGHT);
2154 for (i = 0; i < 3; i++) {
2155 ret[COL_TRACK_CLUE * 3 + i] = 0.0F;
2156 ret[COL_TRACK * 3 + i] = 0.5F;
2157 ret[COL_CLUE * 3 + i] = 0.0F;
2158 ret[COL_GRID * 3 + i] = 0.75F;
2159 ret[COL_CURSOR * 3 + i] = 0.6F;
2160 ret[COL_ERROR_BACKGROUND * 3 + i] = 1.0F;
2163 ret[COL_SLEEPER * 3 + 0] = 0.5F;
2164 ret[COL_SLEEPER * 3 + 1] = 0.4F;
2165 ret[COL_SLEEPER * 3 + 2] = 0.1F;
2167 ret[COL_ERROR * 3 + 0] = 1.0F;
2168 ret[COL_ERROR * 3 + 1] = 0.0F;
2169 ret[COL_ERROR * 3 + 2] = 0.0F;
2171 ret[COL_DRAGON * 3 + 0] = 0.0F;
2172 ret[COL_DRAGON * 3 + 1] = 0.0F;
2173 ret[COL_DRAGON * 3 + 2] = 1.0F;
2175 ret[COL_DRAGOFF * 3 + 0] = 0.8F;
2176 ret[COL_DRAGOFF * 3 + 1] = 0.8F;
2177 ret[COL_DRAGOFF * 3 + 2] = 1.0F;
2179 ret[COL_FLASH * 3 + 0] = 1.0F;
2180 ret[COL_FLASH * 3 + 1] = 1.0F;
2181 ret[COL_FLASH * 3 + 2] = 1.0F;
2183 *ncolours = NCOLOURS;
2187 static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state)
2189 struct game_drawstate *ds = snew(struct game_drawstate);
2193 ds->started = FALSE;
2197 ds->sz = ds->w*ds->h;
2198 ds->flags = snewn(ds->sz, unsigned int);
2199 ds->flags_drag = snewn(ds->sz, unsigned int);
2200 for (i = 0; i < ds->sz; i++)
2201 ds->flags[i] = ds->flags_drag[i] = 0;
2203 ds->num_errors = snewn(ds->w+ds->h, int);
2204 for (i = 0; i < ds->w+ds->h; i++)
2205 ds->num_errors[i] = 0;
2210 static void game_free_drawstate(drawing *dr, game_drawstate *ds)
2213 sfree(ds->flags_drag);
2214 sfree(ds->num_errors);
2218 static void draw_circle_sleepers(drawing *dr, game_drawstate *ds,
2219 float cx, float cy, float r2, float thickness, int c)
2221 float qr6 = (float)PI/12, qr3 = (float)PI/6, th, x1, y1, x2, y2;
2222 float t6 = THIRDSZ/2.0F, r1 = t6;
2225 for (i = 0; i < 12; i++) {
2227 x1 = r1*(float)cos(th);
2228 x2 = r2*(float)cos(th);
2229 y1 = r1*(float)sin(th);
2230 y2 = r2*(float)sin(th);
2231 draw_thick_line(dr, thickness, cx+x1, cy+y1, cx+x2, cy+y2, c);
2235 static void draw_thick_circle_outline(drawing *dr, float thickness,
2236 float cx, float cy, float r,
2239 float circ4 = 0.5F * (float)PI * r, ang, x1, y1, x2, y2;
2242 nseg = (int)(circ4 / 4.0F)*4; /* ensure a quarter-circle has a whole #segs */
2243 ang = 2.0F*(float)PI / nseg;
2245 for (i = 0; i < nseg; i++) {
2246 float th = ang * i, th2 = ang * (i+1);
2247 x1 = cx + r*(float)cos(th);
2248 x2 = cx + r*(float)cos(th2);
2249 y1 = cy + r*(float)sin(th);
2250 y2 = cy + r*(float)sin(th2);
2251 debug(("circ outline: x=%.2f -> %.2f, thick=%.2f", x1, x2, thickness));
2252 draw_thick_line(dr, thickness, x1, y1, x2, y2, colour);
2256 static void draw_tracks_specific(drawing *dr, game_drawstate *ds,
2257 int x, int y, unsigned int flags,
2258 int ctrack, int csleeper)
2260 float ox = (float)COORD(x), oy = (float)COORD(y), cx, cy;
2261 float t1 = (float)TILE_SIZE, t3 = TILE_SIZE/3.0F, t6 = TILE_SIZE/6.0F;
2263 float thick_track = TILE_SIZE/8.0F, thick_sleeper = TILE_SIZE/12.0F;
2266 for (i = 1; i <= 7; i+=2) {
2267 cx = ox + TILE_SIZE/8.0F*i;
2268 draw_thick_line(dr, thick_sleeper,
2269 cx, oy+t6, cx, oy+t6+2*t3, csleeper);
2271 draw_thick_line(dr, thick_track, ox, oy + t3, ox + TILE_SIZE, oy + t3, ctrack);
2272 draw_thick_line(dr, thick_track, ox, oy + 2*t3, ox + TILE_SIZE, oy + 2*t3, ctrack);
2276 for (i = 1; i <= 7; i+=2) {
2277 cy = oy + TILE_SIZE/8.0F*i;
2278 draw_thick_line(dr, thick_sleeper,
2279 ox+t6, cy, ox+t6+2*t3, cy, csleeper);
2281 debug(("vert line: x=%.2f, thick=%.2f", ox + t3, thick_track));
2282 draw_thick_line(dr, thick_track, ox + t3, oy, ox + t3, oy + TILE_SIZE, ctrack);
2283 draw_thick_line(dr, thick_track, ox + 2*t3, oy, ox + 2*t3, oy + TILE_SIZE, ctrack);
2286 if (flags == UL || flags == DL || flags == UR || flags == DR) {
2287 cx = (flags & L) ? ox : ox + TILE_SIZE;
2288 cy = (flags & U) ? oy : oy + TILE_SIZE;
2290 draw_circle_sleepers(dr, ds, cx, cy, (float)(5*t6), thick_sleeper, csleeper);
2292 draw_thick_circle_outline(dr, thick_track, (float)cx, (float)cy,
2294 draw_thick_circle_outline(dr, thick_track, (float)cx, (float)cy,
2300 for (d = 1; d < 16; d *= 2) {
2301 float ox1 = 0, ox2 = 0, oy1 = 0, oy2 = 0;
2303 if (!(flags & d)) continue;
2305 for (i = 1; i <= 2; i++) {
2310 } else if (d == R) {
2312 ox2 = t1 - thick_track;
2314 } else if (d == U) {
2318 } else if (d == D) {
2321 oy2 = t1 - thick_track;
2323 draw_thick_line(dr, thick_track, ox+ox1, oy+oy1, ox+ox2, oy+oy2, ctrack);
2328 static unsigned int best_bits(unsigned int flags, unsigned int flags_drag, int *col)
2330 int nb_orig = nbits[flags & ALLDIR], nb_drag = nbits[flags_drag & ALLDIR];
2332 if (nb_orig > nb_drag) {
2334 return flags & ALLDIR;
2335 } else if (nb_orig < nb_drag) {
2337 return flags_drag & ALLDIR;
2339 return flags & ALLDIR; /* same number of bits: no special colour. */
2342 static void draw_square(drawing *dr, game_drawstate *ds,
2343 int x, int y, unsigned int flags, unsigned int flags_drag)
2345 int t2 = HALFSZ, t16 = HALFSZ/4, off;
2346 int ox = COORD(x), oy = COORD(y), cx = ox + t2, cy = oy + t2, d, c;
2347 int bg = (flags & DS_TRACK) ? COL_TRACK_BACKGROUND : COL_BACKGROUND;
2348 unsigned int flags_best;
2352 /* Clip to the grid square. */
2353 clip(dr, ox, oy, TILE_SIZE, TILE_SIZE);
2355 /* Clear the square so that it's got an appropriately-sized border
2356 * in COL_GRID and a central area in the right background colour. */
2357 best_bits((flags & DS_TRACK) == DS_TRACK,
2358 (flags_drag & DS_TRACK) == DS_TRACK, &bg);
2359 draw_rect(dr, ox, oy, TILE_SIZE, TILE_SIZE, COL_GRID);
2360 draw_rect(dr, ox + GRID_LINE_TL, oy + GRID_LINE_TL,
2361 TILE_SIZE - GRID_LINE_ALL, TILE_SIZE - GRID_LINE_ALL, bg);
2363 /* More outlines for clue squares. */
2364 if (flags & DS_CURSOR) {
2365 int curx, cury, curw, curh;
2368 curx = ox + off; cury = oy + off;
2369 curw = curh = TILE_SIZE - (2*off) + 1;
2371 if (flags & (U << DS_CSHIFT)) {
2372 cury = oy - off; curh = 2*off + 1;
2373 } else if (flags & (D << DS_CSHIFT)) {
2374 cury = oy + TILE_SIZE - off; curh = 2*off + 1;
2375 } else if (flags & (L << DS_CSHIFT)) {
2376 curx = ox - off; curw = 2*off + 1;
2377 } else if (flags & (R << DS_CSHIFT)) {
2378 curx = ox + TILE_SIZE - off; curw = 2*off + 1;
2381 draw_rect_outline(dr, curx, cury, curw, curh, COL_GRID);
2384 /* Draw tracks themselves */
2385 c = (flags & DS_ERROR) ? COL_ERROR :
2386 (flags & DS_FLASH) ? COL_FLASH :
2387 (flags & DS_CLUE) ? COL_TRACK_CLUE : COL_TRACK;
2388 flags_best = best_bits(flags, flags_drag, &c);
2389 draw_tracks_specific(dr, ds, x, y, flags_best, c, COL_SLEEPER);
2391 /* Draw no-track marks, if present, in square and on edges. */
2393 flags_best = best_bits((flags & DS_NOTRACK) == DS_NOTRACK,
2394 (flags_drag & DS_NOTRACK) == DS_NOTRACK, &c);
2397 draw_thick_line(dr, LINE_THICK, cx - off, cy - off, cx + off, cy + off, c);
2398 draw_thick_line(dr, LINE_THICK, cx - off, cy + off, cx + off, cy - off, c);
2402 flags_best = best_bits(flags >> DS_NSHIFT, flags_drag >> DS_NSHIFT, &c);
2403 for (d = 1; d < 16; d *= 2) {
2408 if (flags_best & d) {
2409 cx += (d == R) ? t2 : (d == L) ? -t2 : 0;
2410 cy += (d == D) ? t2 : (d == U) ? -t2 : 0;
2412 draw_thick_line(dr, LINE_THICK, cx - off, cy - off, cx + off, cy + off, c);
2413 draw_thick_line(dr, LINE_THICK, cx - off, cy + off, cx + off, cy - off, c);
2418 draw_update(dr, ox, oy, TILE_SIZE, TILE_SIZE);
2421 static void draw_clue(drawing *dr, game_drawstate *ds, int w, int clue, int i, int col, int bg)
2423 int cx, cy, tsz = TILE_SIZE/2;
2427 cx = CENTERED_COORD(i);
2428 cy = CENTERED_COORD(-1);
2430 cx = CENTERED_COORD(w);
2431 cy = CENTERED_COORD(i-w);
2434 draw_rect(dr, cx - tsz + GRID_LINE_TL, cy - tsz + GRID_LINE_TL,
2435 TILE_SIZE - GRID_LINE_ALL, TILE_SIZE - GRID_LINE_ALL,
2437 sprintf(buf, "%d", clue);
2438 draw_text(dr, cx, cy, FONT_VARIABLE, tsz, ALIGN_VCENTRE|ALIGN_HCENTRE,
2440 draw_update(dr, cx - tsz + GRID_LINE_TL, cy - tsz + GRID_LINE_TL,
2441 TILE_SIZE - GRID_LINE_ALL, TILE_SIZE - GRID_LINE_ALL);
2444 static void draw_loop_ends(drawing *dr, game_drawstate *ds,
2445 const game_state *state, int c)
2447 int tsz = TILE_SIZE/2;
2449 draw_text(dr, CENTERED_COORD(-1), CENTERED_COORD(state->numbers->row_s),
2450 FONT_VARIABLE, tsz, ALIGN_VCENTRE|ALIGN_HCENTRE,
2453 draw_text(dr, CENTERED_COORD(state->numbers->col_s), CENTERED_COORD(state->p.h),
2454 FONT_VARIABLE, tsz, ALIGN_VCENTRE|ALIGN_HCENTRE,
2458 static unsigned int s2d_flags(const game_state *state, int x, int y, const game_ui *ui)
2463 f = S_E_DIRS(state, x, y, E_TRACK);
2464 f |= (S_E_DIRS(state, x, y, E_NOTRACK) << DS_NSHIFT);
2466 if (state->sflags[y*w+x] & S_ERROR)
2468 if (state->sflags[y*w+x] & S_CLUE)
2470 if (state->sflags[y*w+x] & S_NOTRACK)
2472 if ((state->sflags[y*w+x] & S_TRACK) || (S_E_COUNT(state, x, y, E_TRACK) > 0))
2475 if (ui->cursor_active) {
2476 if (ui->curx >= x*2 && ui->curx <= (x+1)*2 &&
2477 ui->cury >= y*2 && ui->cury <= (y+1)*2) {
2479 if (ui->curx == x*2) f |= (L << DS_CSHIFT);
2480 if (ui->curx == (x+1)*2) f |= (R << DS_CSHIFT);
2481 if (ui->cury == y*2) f |= (U << DS_CSHIFT);
2482 if (ui->cury == (y+1)*2) f |= (D << DS_CSHIFT);
2489 static void game_redraw(drawing *dr, game_drawstate *ds, const game_state *oldstate,
2490 const game_state *state, int dir, const game_ui *ui,
2491 float animtime, float flashtime)
2493 int i, x, y, force = 0, flashing = 0, w = ds->w, h = ds->h;
2494 game_state *drag_state = NULL;
2498 * The initial contents of the window are not guaranteed and
2499 * can vary with front ends. To be on the safe side, all games
2500 * should start by drawing a big background-colour rectangle
2501 * covering the whole window.
2503 draw_rect(dr, 0, 0, (w+2)*TILE_SIZE + 2*BORDER, (h+2)*TILE_SIZE + 2*BORDER,
2506 draw_loop_ends(dr, ds, state, COL_CLUE);
2508 draw_rect(dr, COORD(0) - GRID_LINE_BR, COORD(0) - GRID_LINE_BR,
2509 ds->w * TILE_SIZE + GRID_LINE_ALL,
2510 ds->h * TILE_SIZE + GRID_LINE_ALL, COL_GRID);
2512 draw_update(dr, 0, 0, (w+2)*TILE_SIZE + 2*BORDER, (h+2)*TILE_SIZE + 2*BORDER);
2518 for (i = 0; i < w+h; i++) {
2519 if (force || (state->num_errors[i] != ds->num_errors[i])) {
2520 ds->num_errors[i] = state->num_errors[i];
2521 draw_clue(dr, ds, w, state->numbers->numbers[i], i,
2522 ds->num_errors[i] ? COL_ERROR : COL_CLUE,
2523 ds->num_errors[i] ? COL_ERROR_BACKGROUND : COL_BACKGROUND);
2527 if (flashtime > 0 &&
2528 (flashtime <= FLASH_TIME/3 ||
2529 flashtime >= FLASH_TIME*2/3))
2530 flashing = DS_FLASH;
2533 drag_state = copy_and_apply_drag(state, ui);
2535 for (x = 0; x < w; x++) {
2536 for (y = 0; y < h; y++) {
2537 unsigned int f, f_d;
2539 f = s2d_flags(state, x, y, ui) | flashing;
2540 f_d = drag_state ? s2d_flags(drag_state, x, y, ui) : f;
2542 if (f != ds->flags[y*w+x] || f_d != ds->flags_drag[y*w+x] || force) {
2543 ds->flags[y*w+x] = f;
2544 ds->flags_drag[y*w+x] = f_d;
2545 draw_square(dr, ds, x, y, f, f_d);
2550 if (drag_state) free_game(drag_state);
2553 static float game_anim_length(const game_state *oldstate, const game_state *newstate,
2554 int dir, game_ui *ui)
2559 static float game_flash_length(const game_state *oldstate, const game_state *newstate,
2560 int dir, game_ui *ui)
2562 if (!oldstate->completed &&
2563 newstate->completed && !newstate->used_solve)
2569 static int game_status(const game_state *state)
2571 return state->completed ? +1 : 0;
2574 static int game_timing_state(const game_state *state, game_ui *ui)
2579 static void game_print_size(const game_params *params, float *x, float *y)
2583 /* The Times uses 7mm squares */
2584 game_compute_size(params, 700, &pw, &ph);
2589 static void game_print(drawing *dr, const game_state *state, int tilesize)
2591 int w = state->p.w, h = state->p.h;
2592 int black = print_mono_colour(dr, 0), grey = print_grey_colour(dr, 0.5F);
2595 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
2596 game_drawstate ads, *ds = &ads;
2597 game_set_size(dr, ds, NULL, tilesize);
2599 /* Grid, then border (second so it is on top) */
2600 print_line_width(dr, TILE_SIZE / 24);
2601 for (x = 1; x < w; x++)
2602 draw_line(dr, COORD(x), COORD(0), COORD(x), COORD(h), grey);
2603 for (y = 1; y < h; y++)
2604 draw_line(dr, COORD(0), COORD(y), COORD(w), COORD(y), grey);
2606 print_line_width(dr, TILE_SIZE / 16);
2607 draw_rect_outline(dr, COORD(0), COORD(0), w*TILE_SIZE, h*TILE_SIZE, black);
2609 print_line_width(dr, TILE_SIZE / 24);
2611 /* clue numbers, and loop ends */
2612 for (i = 0; i < w+h; i++)
2613 draw_clue(dr, ds, w, state->numbers->numbers[i], i,
2614 black, COL_BACKGROUND);
2615 draw_loop_ends(dr, ds, state, black);
2617 /* clue tracks / solution */
2618 for (x = 0; x < w; x++) {
2619 for (y = 0; y < h; y++) {
2620 clip(dr, COORD(x), COORD(y), TILE_SIZE, TILE_SIZE);
2621 draw_tracks_specific(dr, ds, x, y, S_E_DIRS(state, x, y, E_TRACK),
2629 #define thegame tracks
2632 const struct game thegame = {
2633 "Train Tracks", "games.tracks", "tracks",
2635 game_fetch_preset, NULL,
2640 TRUE, game_configure, custom_params,
2648 TRUE, game_can_format_as_text_now, game_text_format,
2656 PREFERRED_TILE_SIZE, game_compute_size, game_set_size,
2659 game_free_drawstate,
2664 TRUE, FALSE, game_print_size, game_print,
2665 FALSE, /* wants_statusbar */
2666 FALSE, game_timing_state,
2670 /* vim: set shiftwidth=4 tabstop=8: */