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].u.string.sval = dupstr(buf);
153 ret[1].name = "Height";
154 ret[1].type = C_STRING;
155 sprintf(buf, "%d", params->h);
156 ret[1].u.string.sval = dupstr(buf);
158 ret[2].name = "Difficulty";
159 ret[2].type = C_CHOICES;
160 ret[2].u.choices.choicenames = DIFFCONFIG;
161 ret[2].u.choices.selected = params->diff;
163 ret[3].name = "Disallow consecutive 1 clues";
164 ret[3].type = C_BOOLEAN;
165 ret[3].u.boolean.bval = params->single_ones;
173 static game_params *custom_params(const config_item *cfg)
175 game_params *ret = snew(game_params);
177 ret->w = atoi(cfg[0].u.string.sval);
178 ret->h = atoi(cfg[1].u.string.sval);
179 ret->diff = cfg[2].u.choices.selected;
180 ret->single_ones = cfg[3].u.boolean.bval;
185 static const char *validate_params(const game_params *params, int full)
188 * Generating anything under 4x4 runs into trouble of one kind
191 if (params->w < 4 || params->h < 4)
192 return "Width and height must both be at least four";
196 /* --- Game state --- */
198 /* flag usage copied from pearl */
205 #define MOVECHAR(m) ((m==R)?'R':(m==U)?'U':(m==L)?'L':(m==D)?'D':'?')
207 #define DX(d) ( ((d)==R) - ((d)==L) )
208 #define DY(d) ( ((d)==D) - ((d)==U) )
210 #define F(d) (((d << 2) | (d >> 2)) & 0xF)
211 #define C(d) (((d << 3) | (d >> 1)) & 0xF)
212 #define A(d) (((d << 1) | (d >> 3)) & 0xF)
230 int nbits[] = { 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4 };
232 /* square grid flags */
233 #define S_TRACK 1 /* a track passes through this square (--> 2 edges) */
234 #define S_NOTRACK 2 /* no track passes through this square */
239 #define S_TRACK_SHIFT 16 /* U/D/L/R flags for edge track indicators */
240 #define S_NOTRACK_SHIFT 20 /* U/D/L/R flags for edge no-track indicators */
242 /* edge grid flags */
243 #define E_TRACK 1 /* a track passes through this edge */
244 #define E_NOTRACK 2 /* no track passes through this edge */
248 int *numbers; /* sz w+h */
249 int row_s, col_s; /* stations: TODO think about multiple lines
250 (for bigger grids)? */
253 #define INGRID(state, gx, gy) ((gx) >= 0 && (gx) < (state)->p.w && \
254 (gy) >= 0 && (gy) < (state)->p.h)
258 unsigned int *sflags; /* size w*h */
259 struct numbers *numbers;
260 int *num_errors; /* size w+h */
261 int completed, used_solve, impossible;
264 /* Return the four directions in which a particular edge flag is set, around a square. */
265 int S_E_DIRS(const game_state *state, int sx, int sy, unsigned int eflag) {
266 return (state->sflags[sy*state->p.w+sx] >>
267 ((eflag == E_TRACK) ? S_TRACK_SHIFT : S_NOTRACK_SHIFT)) & ALLDIR;
270 /* Count the number of a particular edge flag around a grid square. */
271 int S_E_COUNT(const game_state *state, int sx, int sy, unsigned int eflag) {
272 return nbits[S_E_DIRS(state, sx, sy, eflag)];
275 /* Return the two flags (E_TRACK and/or E_NOTRACK) set on a specific
276 * edge of a square. */
277 unsigned S_E_FLAGS(const game_state *state, int sx, int sy, int d) {
278 unsigned f = state->sflags[sy*state->p.w+sx];
279 int t = (f & (d << S_TRACK_SHIFT)), nt = (f & (d << S_NOTRACK_SHIFT));
280 return (t ? E_TRACK : 0) | (nt ? E_NOTRACK : 0);
283 int S_E_ADJ(const game_state *state, int sx, int sy, int d, int *ax, int *ay, unsigned int *ad) {
284 if (d == L && sx > 0) { *ax = sx-1; *ay = sy; *ad = R; return 1; }
285 if (d == R && sx < state->p.w-1) { *ax = sx+1; *ay = sy; *ad = L; return 1; }
286 if (d == U && sy > 0) { *ax = sx; *ay = sy-1; *ad = D; return 1; }
287 if (d == D && sy < state->p.h-1) { *ax = sx; *ay = sy+1; *ad = U; return 1; }
292 /* Sets flag (E_TRACK or E_NOTRACK) on a given edge of a square. */
293 void S_E_SET(game_state *state, int sx, int sy, int d, unsigned int eflag) {
294 unsigned shift = (eflag == E_TRACK) ? S_TRACK_SHIFT : S_NOTRACK_SHIFT, ad;
297 state->sflags[sy*state->p.w+sx] |= (d << shift);
299 if (S_E_ADJ(state, sx, sy, d, &ax, &ay, &ad)) {
300 state->sflags[ay*state->p.w+ax] |= (ad << shift);
304 /* Clears flag (E_TRACK or E_NOTRACK) on a given edge of a square. */
305 void S_E_CLEAR(game_state *state, int sx, int sy, int d, unsigned int eflag) {
306 unsigned shift = (eflag == E_TRACK) ? S_TRACK_SHIFT : S_NOTRACK_SHIFT, ad;
309 state->sflags[sy*state->p.w+sx] &= ~(d << shift);
311 if (S_E_ADJ(state, sx, sy, d, &ax, &ay, &ad)) {
312 state->sflags[ay*state->p.w+ax] &= ~(ad << shift);
316 static void clear_game(game_state *state)
318 int w = state->p.w, h = state->p.h;
320 memset(state->sflags, 0, w*h * sizeof(unsigned int));
322 memset(state->numbers->numbers, 0, (w+h) * sizeof(int));
323 state->numbers->col_s = state->numbers->row_s = -1;
325 memset(state->num_errors, 0, (w+h) * sizeof(int));
327 state->completed = state->used_solve = state->impossible = FALSE;
330 static game_state *blank_game(const game_params *params)
332 game_state *state = snew(game_state);
333 int w = params->w, h = params->h;
337 state->sflags = snewn(w*h, unsigned int);
339 state->numbers = snew(struct numbers);
340 state->numbers->refcount = 1;
341 state->numbers->numbers = snewn(w+h, int);
343 state->num_errors = snewn(w+h, int);
350 static void copy_game_flags(const game_state *src, game_state *dest)
352 int w = src->p.w, h = src->p.h;
354 memcpy(dest->sflags, src->sflags, w*h*sizeof(unsigned int));
357 static game_state *dup_game(const game_state *state)
359 int w = state->p.w, h = state->p.h;
360 game_state *ret = snew(game_state);
362 ret->p = state->p; /* structure copy */
364 ret->sflags = snewn(w*h, unsigned int);
365 copy_game_flags(state, ret);
367 ret->numbers = state->numbers;
368 state->numbers->refcount++;
369 ret->num_errors = snewn(w+h, int);
370 memcpy(ret->num_errors, state->num_errors, (w+h)*sizeof(int));
372 ret->completed = state->completed;
373 ret->used_solve = state->used_solve;
374 ret->impossible = state->impossible;
379 static void free_game(game_state *state)
381 if (--state->numbers->refcount <= 0) {
382 sfree(state->numbers->numbers);
383 sfree(state->numbers);
385 sfree(state->num_errors);
386 sfree(state->sflags);
391 const unsigned int dirs_const[] = { U, D, L, R };
393 static unsigned int find_direction(game_state *state, random_state *rs,
396 int i, nx, ny, w=state->p.w, h=state->p.h;
397 unsigned int dirs[NDIRS];
399 memcpy(dirs, dirs_const, sizeof(dirs));
400 shuffle(dirs, NDIRS, sizeof(*dirs), rs);
401 for (i = 0; i < NDIRS; i++) {
402 nx = x + DX(dirs[i]);
403 ny = y + DY(dirs[i]);
404 if (nx >= 0 && nx < w && ny == h) {
405 /* off the bottom of the board: we've finished the path. */
407 } else if (!INGRID(state, nx, ny)) {
408 /* off the board: can't move here */
410 } else if (S_E_COUNT(state, nx, ny, E_TRACK) > 0) {
411 /* already tracks here: can't move */
416 return 0; /* no possible directions left. */
419 static int check_completion(game_state *state, int mark);
421 static void lay_path(game_state *state, random_state *rs)
423 int px, py, w=state->p.w, h=state->p.h;
429 /* pick a random entry point, lay its left edge */
430 state->numbers->row_s = py = random_upto(rs, h);
432 S_E_SET(state, px, py, L, E_TRACK);
434 while (INGRID(state, px, py)) {
435 d = find_direction(state, rs, px, py);
437 goto start; /* nowhere else to go, restart */
439 S_E_SET(state, px, py, d, E_TRACK);
443 /* double-check we got to the right place */
444 assert(px >= 0 && px < w && py == h);
446 state->numbers->col_s = px;
449 static int tracks_solve(game_state *state, int diff);
450 static void debug_state(game_state *state, const char *what);
452 /* Clue-setting algorithm:
454 - first lay clues randomly until it's soluble
455 - then remove clues randomly if removing them doesn't affect solubility
457 - We start with two clues, one at each path entrance.
460 - start with an array of all square i positions
461 - if the grid is already soluble by a level easier than we've requested,
462 go back and make a new grid
463 - if the grid is already soluble by our requested difficulty level, skip
465 - count the number of flags the solver managed to place, remember this.
468 - shuffle the i positions
469 - for each possible clue position:
470 - copy the solved board, strip it
471 - take the next position, add a clue there on the copy
472 - try and solve the copy
473 - if it's soluble by a level easier than we've requested, continue (on
474 to next clue position: putting a clue here makes it too easy)
475 - if it's soluble by our difficulty level, we're done:
476 - put the clue flag into the solved board
478 - if the solver didn't manage to place any more flags, continue (on to next
479 clue position: putting a clue here didn't help he solver)
480 - otherwise put the clue flag in the original board, and go on to the next
482 - if we get here and we've not solved it yet, we never will (did we really
483 fill _all_ the clues in?!). Go back and make a new grid.
486 - shuffle the i positions
487 - for each possible clue position:
488 - if the solved grid doesn't have a clue here, skip
489 - copy the solved board, remove this clue, strip it
490 - try and solve the copy
491 - assert that it is not soluble by a level easier than we've requested
492 - (because this should never happen)
493 - if this is (still) soluble by our difficulty level:
494 - remove this clue from the solved board, it's redundant (with the other
500 static game_state *copy_and_strip(const game_state *state, game_state *ret, int flipcluei)
502 int i, j, w = state->p.w, h = state->p.h;
504 copy_game_flags(state, ret);
506 /* Add/remove a clue before stripping, if required */
509 ret->sflags[flipcluei] ^= S_CLUE;
511 /* All squares that are not clue squares have square track info erased, and some edge flags.. */
513 for (i = 0; i < w*h; i++) {
514 if (!(ret->sflags[i] & S_CLUE)) {
515 ret->sflags[i] &= ~(S_TRACK|S_NOTRACK|S_ERROR|S_MARK);
516 for (j = 0; j < 4; j++) {
518 int xx = i%w + DX(f), yy = i/w + DY(f);
519 if (!INGRID(state, xx, yy) || !(ret->sflags[yy*w+xx] & S_CLUE)) {
520 /* only erase an edge flag if neither side of the edge is S_CLUE. */
521 S_E_CLEAR(ret, i%w, i/w, f, E_TRACK);
522 S_E_CLEAR(ret, i%w, i/w, f, E_NOTRACK);
530 static int solve_progress(const game_state *state) {
531 int i, w = state->p.w, h = state->p.h, progress = 0;
533 /* Work out how many flags the solver managed to set (either TRACK
534 or NOTRACK) and return this as a progress measure, to check whether
535 a partially-solved board gets any further than a previous partially-
538 for (i = 0; i < w*h; i++) {
539 if (state->sflags[i] & S_TRACK) progress++;
540 if (state->sflags[i] & S_NOTRACK) progress++;
541 progress += S_E_COUNT(state, i%w, i/w, E_TRACK);
542 progress += S_E_COUNT(state, i%w, i/w, E_NOTRACK);
547 static int check_phantom_moves(const game_state *state) {
550 /* Check that this state won't show 'phantom moves' at the start of the
551 * game: squares which have multiple edge flags set but no clue flag
552 * cause a piece of track to appear that isn't on a clue square. */
554 for (x = 0; x < state->p.w; x++) {
555 for (y = 0; y < state->p.h; y++) {
557 if (state->sflags[i] & S_CLUE)
559 if (S_E_COUNT(state, x, y, E_TRACK) > 1)
560 return 1; /* found one! */
566 static int add_clues(game_state *state, random_state *rs, int diff)
568 int i, j, pi, w = state->p.w, h = state->p.h, progress, ret = 0, sr;
569 int *positions = snewn(w*h, int), npositions = 0;
570 int *nedges_previous_solve = snewn(w*h, int);
571 game_state *scratch = dup_game(state);
573 debug_state(state, "gen: Initial board");
575 debug(("gen: Adding clues..."));
577 /* set up the shuffly-position grid for later, used for adding clues:
578 * we only bother adding clues where any edges are set. */
579 for (i = 0; i < w*h; i++) {
580 if (S_E_DIRS(state, i%w, i/w, E_TRACK) != 0) {
581 positions[npositions++] = i;
583 nedges_previous_solve[i] = 0;
586 /* First, check whether the puzzle is already either too easy, or just right */
587 scratch = copy_and_strip(state, scratch, -1);
589 sr = tracks_solve(scratch, diff-1);
591 assert(!"Generator should not have created impossible puzzle");
593 ret = -1; /* already too easy, even without adding clues. */
594 debug(("gen: ...already too easy, need new board."));
598 sr = tracks_solve(scratch, diff);
600 assert(!"Generator should not have created impossible puzzle");
602 ret = 1; /* already soluble without any extra clues. */
603 debug(("gen: ...soluble without clues, nothing to do."));
606 debug_state(scratch, "gen: Initial part-solved state: ");
607 progress = solve_progress(scratch);
608 debug(("gen: Initial solve progress is %d", progress));
610 /* First, lay clues until we're soluble. */
611 shuffle(positions, npositions, sizeof(int), rs);
612 for (pi = 0; pi < npositions; pi++) {
613 i = positions[pi]; /* pick a random position */
614 if (state->sflags[i] & S_CLUE)
615 continue; /* already a clue here (entrance location?) */
616 if (nedges_previous_solve[i] == 2)
617 continue; /* no point putting a clue here, we could solve both edges
618 with the previous set of clues */
620 /* set a clue in that position (on a copy of the board) and test solubility */
621 scratch = copy_and_strip(state, scratch, i);
623 if (check_phantom_moves(scratch))
624 continue; /* adding a clue here would add phantom track */
627 if (tracks_solve(scratch, diff-1) > 0) {
628 continue; /* adding a clue here makes it too easy */
631 if (tracks_solve(scratch, diff) > 0) {
632 /* we're now soluble (and we weren't before): add this clue, and then
633 start stripping clues */
634 debug(("gen: ...adding clue at (%d,%d), now soluble", i%w, i/w));
635 state->sflags[i] |= S_CLUE;
638 if (solve_progress(scratch) > progress) {
639 /* We've made more progress solving: add this clue, then. */
640 progress = solve_progress(scratch);
641 debug(("gen: ... adding clue at (%d,%d), new progress %d", i%w, i/w, progress));
642 state->sflags[i] |= S_CLUE;
644 for (j = 0; j < w*h; j++)
645 nedges_previous_solve[j] = S_E_COUNT(scratch, j%w, j/w, E_TRACK);
648 /* If we got here we didn't ever manage to make the puzzle soluble
649 (without making it too easily soluble, that is): give up. */
651 debug(("gen: Unable to make soluble with clues, need new board."));
656 debug(("gen: Stripping clues."));
658 /* Now, strip redundant clues (i.e. those without which the puzzle is still
660 shuffle(positions, npositions, sizeof(int), rs);
661 for (pi = 0; pi < npositions; pi++) {
662 i = positions[pi]; /* pick a random position */
663 if (!(state->sflags[i] & S_CLUE))
664 continue; /* no clue here to strip */
665 if ((i%w == 0 && i/w == state->numbers->row_s) ||
666 (i/w == (h-1) && i%w == state->numbers->col_s))
667 continue; /* don't strip clues at entrance/exit */
669 scratch = copy_and_strip(state, scratch, i);
670 if (check_phantom_moves(scratch))
671 continue; /* removing a clue here would add phantom track */
673 if (tracks_solve(scratch, diff) > 0) {
674 debug(("gen: ... removing clue at (%d,%d), still soluble without it", i%w, i/w));
675 state->sflags[i] &= ~S_CLUE; /* still soluble without this clue. */
678 debug(("gen: Finished stripping clues."));
687 static char *new_game_desc(const game_params *params, random_state *rs,
688 char **aux, int interactive)
690 int i, j, w = params->w, h = params->h, x, y, ret;
693 game_params adjusted_params;
696 * 4x4 Tricky cannot be generated, so fall back to Easy.
698 if (w == 4 && h == 4 && params->diff > DIFF_EASY) {
699 adjusted_params = *params; /* structure copy */
700 adjusted_params.diff = DIFF_EASY;
701 params = &adjusted_params;
704 state = blank_game(params);
706 /* --- lay the random path */
710 for (x = 0; x < w; x++) {
711 for (y = 0; y < h; y++) {
712 if (S_E_COUNT(state, x, y, E_TRACK) > 0) {
713 state->sflags[y*w + x] |= S_TRACK;
715 if ((x == 0 && y == state->numbers->row_s) ||
716 (y == (h-1) && x == state->numbers->col_s)) {
717 state->sflags[y*w + x] |= S_CLUE;
722 /* --- Update the clue numbers based on the tracks we have generated. */
723 for (x = 0; x < w; x++) {
724 for (y = 0; y < h; y++) {
725 if (state->sflags[y*w + x] & S_TRACK) {
726 state->numbers->numbers[x]++;
727 state->numbers->numbers[y+w]++;
731 for (i = 0; i < w+h; i++) {
732 if (state->numbers->numbers[i] == 0)
733 goto newpath; /* too boring */
736 if (params->single_ones) {
737 int last_was_one = 1, is_one; /* (disallow 1 clue at entry point) */
738 for (i = 0; i < w+h; i++) {
739 is_one = (state->numbers->numbers[i] == 1);
740 if (is_one && last_was_one)
741 goto newpath; /* disallow consecutive 1 clues. */
742 last_was_one = is_one;
744 if (state->numbers->numbers[w+h-1] == 1)
745 goto newpath; /* (disallow 1 clue at exit point) */
748 /* --- Add clues to make a soluble puzzle */
749 ret = add_clues(state, rs, params->diff);
750 if (ret != 1) goto newpath; /* couldn't make it soluble, or too easy */
752 /* --- Generate the game desc based on the generated grid. */
753 desc = snewn(w*h*3 + (w+h)*5, char);
754 for (i = j = 0; i < w*h; i++) {
755 if (!(state->sflags[i] & S_CLUE) && j > 0 &&
756 desc[j-1] >= 'a' && desc[j-1] < 'z')
758 else if (!(state->sflags[i] & S_CLUE))
761 unsigned int f = S_E_DIRS(state, i%w, i/w, E_TRACK);
762 desc[j++] = (f < 10) ? ('0' + f) : ('A' + (f-10));
767 for (x = 0; x < w; x++) {
768 p += sprintf(p, ",%s%d", x == state->numbers->col_s ? "S" : "",
769 state->numbers->numbers[x]);
771 for (y = 0; y < h; y++) {
772 p += sprintf(p, ",%s%d", y == state->numbers->row_s ? "S" : "",
773 state->numbers->numbers[y+w]);
777 ret = tracks_solve(state, DIFFCOUNT);
781 debug(("new_game_desc: %s", desc));
785 static const char *validate_desc(const game_params *params, const char *desc)
787 int i = 0, w = params->w, h = params->h, in = 0, out = 0;
791 if (*desc >= '0' && *desc <= '9')
793 else if (*desc >= 'A' && *desc <= 'F')
794 f = (*desc - 'A' + 10);
795 else if (*desc >= 'a' && *desc <= 'z')
798 return "Game description contained unexpected characters";
802 return "Clue did not provide 2 direction flags";
808 for (i = 0; i < w+h; i++) {
810 return "Not enough numbers given after grid specification";
811 else if (*desc != ',')
812 return "Invalid character in number list";
821 while (*desc && isdigit((unsigned char)*desc)) desc++;
823 if (in != 1 || out != 1)
824 return "Puzzle must have one entrance and one exit";
826 return "Unexpected additional character at end of game description";
830 static game_state *new_game(midend *me, const game_params *params, const char *desc)
832 game_state *state = blank_game(params);
833 int w = params->w, h = params->h, i = 0;
837 if (*desc >= '0' && *desc <= '9')
839 else if (*desc >= 'A' && *desc <= 'F')
840 f = (*desc - 'A' + 10);
841 else if (*desc >= 'a' && *desc <= 'z')
845 int x = i % w, y = i / w;
847 assert(nbits[f] == 2);
849 state->sflags[i] |= (S_TRACK | S_CLUE);
850 if (f & U) S_E_SET(state, x, y, U, E_TRACK);
851 if (f & D) S_E_SET(state, x, y, D, E_TRACK);
852 if (f & L) S_E_SET(state, x, y, L, E_TRACK);
853 if (f & R) S_E_SET(state, x, y, R, E_TRACK);
859 for (i = 0; i < w+h; i++) {
860 assert(*desc == ',');
865 state->numbers->col_s = i;
867 state->numbers->row_s = i-w;
870 state->numbers->numbers[i] = atoi(desc);
871 while (*desc && isdigit((unsigned char)*desc)) desc++;
879 static int solve_set_sflag(game_state *state, int x, int y,
880 unsigned int f, const char *why)
882 int w = state->p.w, i = y*w + x;
884 if (state->sflags[i] & f)
886 debug(("solve: square (%d,%d) -> %s: %s",
887 x, y, (f == S_TRACK ? "TRACK" : "NOTRACK"), why));
888 if (state->sflags[i] & (f == S_TRACK ? S_NOTRACK : S_TRACK)) {
889 debug(("solve: opposite flag already set there, marking IMPOSSIBLE"));
890 state->impossible = TRUE;
892 state->sflags[i] |= f;
896 static int solve_set_eflag(game_state *state, int x, int y, int d,
897 unsigned int f, const char *why)
899 int sf = S_E_FLAGS(state, x, y, d);
903 debug(("solve: edge (%d,%d)/%c -> %s: %s", x, y,
904 (d == U) ? 'U' : (d == D) ? 'D' : (d == L) ? 'L' : 'R',
905 (f == S_TRACK ? "TRACK" : "NOTRACK"), why));
906 if (sf & (f == E_TRACK ? E_NOTRACK : E_TRACK)) {
907 debug(("solve: opposite flag already set there, marking IMPOSSIBLE"));
908 state->impossible = TRUE;
910 S_E_SET(state, x, y, d, f);
914 static int solve_update_flags(game_state *state)
916 int x, y, i, w = state->p.w, h = state->p.h, did = 0;
918 for (x = 0; x < w; x++) {
919 for (y = 0; y < h; y++) {
920 /* If a square is NOTRACK, all four edges must be. */
921 if (state->sflags[y*w + x] & S_NOTRACK) {
922 for (i = 0; i < 4; i++) {
923 unsigned int d = 1<<i;
924 did += solve_set_eflag(state, x, y, d, E_NOTRACK, "edges around NOTRACK");
928 /* If 3 or more edges around a square are NOTRACK, the square is. */
929 if (S_E_COUNT(state, x, y, E_NOTRACK) >= 3) {
930 did += solve_set_sflag(state, x, y, S_NOTRACK, "square has >2 NOTRACK edges");
933 /* If any edge around a square is TRACK, the square is. */
934 if (S_E_COUNT(state, x, y, E_TRACK) > 0) {
935 did += solve_set_sflag(state, x, y, S_TRACK, "square has TRACK edge");
938 /* If a square is TRACK and 2 edges are NOTRACK,
939 the other two edges must be TRACK. */
940 if ((state->sflags[y*w + x] & S_TRACK) &&
941 (S_E_COUNT(state, x, y, E_NOTRACK) == 2) &&
942 (S_E_COUNT(state, x, y, E_TRACK) < 2)) {
943 for (i = 0; i < 4; i++) {
944 unsigned int d = 1<<i;
945 if (!(S_E_FLAGS(state, x, y, d) & (E_TRACK|E_NOTRACK))) {
946 did += solve_set_eflag(state, x, y, d, E_TRACK,
947 "TRACK square/2 NOTRACK edges");
952 /* If a square is TRACK and 2 edges are TRACK, the other two
954 if ((state->sflags[y*w + x] & S_TRACK) &&
955 (S_E_COUNT(state, x, y, E_TRACK) == 2) &&
956 (S_E_COUNT(state, x, y, E_NOTRACK) < 2)) {
957 for (i = 0; i < 4; i++) {
958 unsigned int d = 1<<i;
959 if (!(S_E_FLAGS(state, x, y, d) & (E_TRACK|E_NOTRACK))) {
960 did += solve_set_eflag(state, x, y, d, E_NOTRACK,
961 "TRACK square/2 TRACK edges");
970 static int solve_count_col(game_state *state, int col, unsigned int f)
972 int i, n, c = 0, h = state->p.h, w = state->p.w;
973 for (n = 0, i = col; n < h; n++, i += w) {
974 if (state->sflags[i] & f) c++;
979 static int solve_count_row(game_state *state, int row, unsigned int f)
981 int i, n, c = 0, w = state->p.w;
982 for (n = 0, i = w*row; n < state->p.w; n++, i++) {
983 if (state->sflags[i] & f) c++;
988 static int solve_count_clues_sub(game_state *state, int si, int id, int n,
989 int target, const char *what)
991 int ctrack = 0, cnotrack = 0, did = 0, j, i, w = state->p.w;
993 for (j = 0, i = si; j < n; j++, i += id) {
994 if (state->sflags[i] & S_TRACK)
996 if (state->sflags[i] & S_NOTRACK)
999 if (ctrack == target) {
1000 /* everything that's not S_TRACK must be S_NOTRACK. */
1001 for (j = 0, i = si; j < n; j++, i += id) {
1002 if (!(state->sflags[i] & S_TRACK))
1003 did += solve_set_sflag(state, i%w, i/w, S_NOTRACK, what);
1006 if (cnotrack == (n-target)) {
1007 /* everything that's not S_NOTRACK must be S_TRACK. */
1008 for (j = 0, i = si; j < n; j++, i += id) {
1009 if (!(state->sflags[i] & S_NOTRACK))
1010 did += solve_set_sflag(state, i%w, i/w, S_TRACK, what);
1016 static int solve_count_clues(game_state *state)
1018 int w = state->p.w, h = state->p.h, x, y, target, did = 0;
1020 for (x = 0; x < w; x++) {
1021 target = state->numbers->numbers[x];
1022 did += solve_count_clues_sub(state, x, w, h, target, "col count");
1024 for (y = 0; y < h; y++) {
1025 target = state->numbers->numbers[w+y];
1026 did += solve_count_clues_sub(state, y*w, 1, w, target, "row count");
1031 static int solve_check_single_sub(game_state *state, int si, int id, int n,
1032 int target, unsigned int perpf,
1035 int ctrack = 0, nperp = 0, did = 0, j, i, w = state->p.w;
1036 int n1edge = 0, i1edge = 0, ox, oy, x, y;
1037 unsigned int impossible = 0;
1039 /* For rows or columns which only have one more square to put a track in, we
1040 know the only way a new track section could be there would be to run
1041 perpendicular to the track (otherwise we'd need at least two free squares).
1042 So, if there is nowhere we can run perpendicular to the track (e.g. because
1043 we're on an edge) we know the extra track section much be on one end of an
1044 existing section. */
1046 for (j = 0, i = si; j < n; j++, i += id) {
1047 if (state->sflags[i] & S_TRACK)
1049 impossible = S_E_DIRS(state, i%w, i/w, E_NOTRACK);
1050 if ((perpf & impossible) == 0)
1052 if (S_E_COUNT(state, i%w, i/w, E_TRACK) <= 1) {
1057 if (ctrack != (target-1)) return 0;
1058 if (nperp > 0 || n1edge != 1) return 0;
1060 debug(("check_single from (%d,%d): 1 match from (%d,%d)",
1061 si%w, si/w, i1edge%w, i1edge/w));
1063 /* We have a match: anything that's more than 1 away from this square
1064 cannot now contain a track. */
1067 for (j = 0, i = si; j < n; j++, i += id) {
1070 if (abs(ox-x) > 1 || abs(oy-y) > 1) {
1071 if (!(state->sflags[i] & S_TRACK))
1072 did += solve_set_sflag(state, x, y, S_NOTRACK, what);
1079 static int solve_check_single(game_state *state)
1081 int w = state->p.w, h = state->p.h, x, y, target, did = 0;
1083 for (x = 0; x < w; x++) {
1084 target = state->numbers->numbers[x];
1085 did += solve_check_single_sub(state, x, w, h, target, R|L, "single on col");
1087 for (y = 0; y < h; y++) {
1088 target = state->numbers->numbers[w+y];
1089 did += solve_check_single_sub(state, y*w, 1, w, target, U|D, "single on row");
1094 static int solve_check_loose_sub(game_state *state, int si, int id, int n,
1095 int target, unsigned int perpf,
1098 int nperp = 0, nloose = 0, e2count = 0, did = 0, i, j, k;
1100 unsigned int parf = ALLDIR & (~perpf);
1102 for (j = 0, i = si; j < n; j++, i += id) {
1103 int fcount = S_E_COUNT(state, i%w, i/w, E_TRACK);
1105 e2count++; /* this cell has 2 definite edges */
1106 state->sflags[i] &= ~S_MARK;
1107 if (fcount == 1 && (parf & S_E_DIRS(state, i%w, i/w, E_TRACK))) {
1108 nloose++; /* this cell has a loose end (single flag set parallel
1109 to the direction of this row/column) */
1110 state->sflags[i] |= S_MARK; /* mark loose ends */
1112 if (fcount != 2 && !(perpf & S_E_DIRS(state, i%w, i/w, E_NOTRACK)))
1113 nperp++; /* we could lay perpendicular across this cell */
1116 if (nloose > (target - e2count)) {
1117 debug(("check %s from (%d,%d): more loose (%d) than empty (%d), IMPOSSIBLE",
1118 what, si%w, si/w, nloose, target-e2count));
1119 state->impossible = TRUE;
1121 if (nloose > 0 && nloose == (target - e2count)) {
1122 debug(("check %s from (%d,%d): nloose = empty (%d), forcing loners out.",
1123 what, si%w, si/w, nloose));
1124 for (j = 0, i = si; j < n; j++, i += id) {
1125 if (!(state->sflags[i] & S_MARK))
1126 continue; /* skip non-loose ends */
1127 if (j > 0 && state->sflags[i-id] & S_MARK)
1128 continue; /* next to other loose end, could join up */
1129 if (j < (n-1) && state->sflags[i+id] & S_MARK)
1130 continue; /* ditto */
1132 for (k = 0; k < 4; k++) {
1133 if ((parf & (1<<k)) &&
1134 !(S_E_DIRS(state, i%w, i/w, E_TRACK) & (1<<k))) {
1135 /* set as NOTRACK the edge parallel to the row/column that's
1137 did += solve_set_eflag(state, i%w, i/w, 1<<k, E_NOTRACK, what);
1142 if (nloose == 1 && (target - e2count) == 2 && nperp == 0) {
1143 debug(("check %s from (%d,%d): 1 loose end, 2 empty squares, forcing parallel",
1145 for (j = 0, i = si; j < n; j++, i += id) {
1146 if (!(state->sflags[i] & S_MARK))
1147 continue; /* skip non-loose ends */
1148 for (k = 0; k < 4; k++) {
1150 did += solve_set_eflag(state, i%w, i/w, 1<<k, E_TRACK, what);
1158 static int solve_check_loose_ends(game_state *state)
1160 int w = state->p.w, h = state->p.h, x, y, target, did = 0;
1162 for (x = 0; x < w; x++) {
1163 target = state->numbers->numbers[x];
1164 did += solve_check_loose_sub(state, x, w, h, target, R|L, "loose on col");
1166 for (y = 0; y < h; y++) {
1167 target = state->numbers->numbers[w+y];
1168 did += solve_check_loose_sub(state, y*w, 1, w, target, U|D, "loose on row");
1173 static int solve_check_loop_sub(game_state *state, int x, int y, int dir,
1174 int *dsf, int startc, int endc)
1176 int w = state->p.w, h = state->p.h, i = y*w+x, j, k, satisfied = 1;
1178 j = (y+DY(dir))*w + (x+DX(dir));
1180 assert(i < w*h && j < w*h);
1182 if ((state->sflags[i] & S_TRACK) &&
1183 (state->sflags[j] & S_TRACK) &&
1184 !(S_E_DIRS(state, x, y, E_TRACK) & dir) &&
1185 !(S_E_DIRS(state, x, y, E_NOTRACK) & dir)) {
1186 int ic = dsf_canonify(dsf, i), jc = dsf_canonify(dsf, j);
1188 return solve_set_eflag(state, x, y, dir, E_NOTRACK, "would close loop");
1190 if ((ic == startc && jc == endc) || (ic == endc && jc == startc)) {
1191 debug(("Adding link at (%d,%d) would join start to end", x, y));
1192 /* We mustn't join the start to the end if:
1193 - there are other bits of track that aren't attached to either end
1194 - the clues are not fully satisfied yet
1196 for (k = 0; k < w*h; k++) {
1197 if (state->sflags[k] & S_TRACK &&
1198 dsf_canonify(dsf, k) != startc && dsf_canonify(dsf, k) != endc) {
1199 return solve_set_eflag(state, x, y, dir, E_NOTRACK,
1200 "joins start to end but misses tracks");
1203 for (k = 0; k < w; k++) {
1204 int target = state->numbers->numbers[k];
1205 int ntracks = solve_count_col(state, k, S_TRACK);
1206 if (ntracks < target) satisfied = 0;
1208 for (k = 0; k < h; k++) {
1209 int target = state->numbers->numbers[w+k];
1210 int ntracks = solve_count_row(state, k, S_TRACK);
1211 if (ntracks < target) satisfied = 0;
1214 return solve_set_eflag(state, x, y, dir, E_NOTRACK,
1215 "joins start to end with incomplete clues");
1222 static int solve_check_loop(game_state *state)
1224 int w = state->p.w, h = state->p.h, x, y, i, j, did = 0;
1225 int *dsf, startc, endc;
1227 /* TODO eventually we should pull this out into a solver struct and keep it
1228 updated as we connect squares. For now we recreate it every time we try
1229 this particular solver step. */
1230 dsf = snewn(w*h, int);
1233 /* Work out the connectedness of the current loop set. */
1234 for (x = 0; x < w; x++) {
1235 for (y = 0; y < h; y++) {
1237 if (x < (w-1) && S_E_DIRS(state, x, y, E_TRACK) & R) {
1238 /* connection to the right... */
1240 assert(i < w*h && j < w*h);
1241 dsf_merge(dsf, i, j);
1243 if (y < (h-1) && S_E_DIRS(state, x, y, E_TRACK) & D) {
1244 /* connection down... */
1246 assert(i < w*h && j < w*h);
1247 dsf_merge(dsf, i, j);
1249 /* NB no need to check up and left because they'll have been checked
1250 by the other side. */
1254 startc = dsf_canonify(dsf, state->numbers->row_s*w);
1255 endc = dsf_canonify(dsf, (h-1)*w+state->numbers->col_s);
1257 /* Now look at all adjacent squares that are both S_TRACK: if connecting
1258 any of them would complete a loop (i.e. they're both the same dsf class
1259 already) then that edge must be NOTRACK. */
1260 for (x = 0; x < w; x++) {
1261 for (y = 0; y < h; y++) {
1263 did += solve_check_loop_sub(state, x, y, R, dsf, startc, endc);
1265 did += solve_check_loop_sub(state, x, y, D, dsf, startc, endc);
1274 static void solve_discount_edge(game_state *state, int x, int y, int d)
1276 if (S_E_DIRS(state, x, y, E_TRACK) & d) {
1277 assert(state->sflags[y*state->p.w + x] & S_CLUE);
1278 return; /* (only) clue squares can have outer edges set. */
1280 solve_set_eflag(state, x, y, d, E_NOTRACK, "outer edge");
1283 static int tracks_solve(game_state *state, int diff)
1285 int didsth, x, y, w = state->p.w, h = state->p.h;
1287 debug(("solve..."));
1288 state->impossible = FALSE;
1290 /* Set all the outer border edges as no-track. */
1291 for (x = 0; x < w; x++) {
1292 solve_discount_edge(state, x, 0, U);
1293 solve_discount_edge(state, x, h-1, D);
1295 for (y = 0; y < h; y++) {
1296 solve_discount_edge(state, 0, y, L);
1297 solve_discount_edge(state, w-1, y, R);
1303 didsth += solve_update_flags(state);
1304 didsth += solve_count_clues(state);
1305 didsth += solve_check_loop(state);
1307 if (diff >= DIFF_TRICKY) {
1308 didsth += solve_check_single(state);
1309 didsth += solve_check_loose_ends(state);
1312 if (!didsth || state->impossible) break;
1315 return state->impossible ? -1 : check_completion(state, FALSE) ? 1 : 0;
1318 static char *move_string_diff(const game_state *before, const game_state *after, int issolve)
1320 int w = after->p.w, h = after->p.h, i, j;
1321 char *move = snewn(w*h*40, char), *p = move;
1322 const char *sep = "";
1323 unsigned int otf, ntf, onf, nnf;
1329 for (i = 0; i < w*h; i++) {
1330 otf = S_E_DIRS(before, i%w, i/w, E_TRACK);
1331 ntf = S_E_DIRS(after, i%w, i/w, E_TRACK);
1332 onf = S_E_DIRS(before, i%w, i/w, E_NOTRACK);
1333 nnf = S_E_DIRS(after, i%w, i/w, E_NOTRACK);
1335 for (j = 0; j < 4; j++) {
1337 if ((otf & df) != (ntf & df)) {
1338 p += sprintf(p, "%s%c%c%d,%d", sep,
1339 (ntf & df) ? 'T' : 't', MOVECHAR(df), i%w, i/w);
1342 if ((onf & df) != (nnf & df)) {
1343 p += sprintf(p, "%s%c%c%d,%d", sep,
1344 (nnf & df) ? 'N' : 'n', MOVECHAR(df), i%w, i/w);
1349 if ((before->sflags[i] & S_NOTRACK) != (after->sflags[i] & S_NOTRACK)) {
1350 p += sprintf(p, "%s%cS%d,%d", sep,
1351 (after->sflags[i] & S_NOTRACK) ? 'N' : 'n', i%w, i/w);
1354 if ((before->sflags[i] & S_TRACK) != (after->sflags[i] & S_TRACK)) {
1355 p += sprintf(p, "%s%cS%d,%d", sep,
1356 (after->sflags[i] & S_TRACK) ? 'T' : 't', i%w, i/w);
1361 move = sresize(move, p - move, char);
1366 static char *solve_game(const game_state *state, const game_state *currstate,
1367 const char *aux, const char **error)
1373 solved = dup_game(currstate);
1374 ret = tracks_solve(solved, DIFFCOUNT);
1377 solved = dup_game(state);
1378 ret = tracks_solve(solved, DIFFCOUNT);
1382 *error = "Unable to find solution";
1385 move = move_string_diff(currstate, solved, TRUE);
1392 static int game_can_format_as_text_now(const game_params *params)
1397 static char *game_text_format(const game_state *state)
1400 int x, y, len, w = state->p.w, h = state->p.h;
1402 len = ((w*2) + 4) * ((h*2)+4) + 2;
1403 ret = snewn(len+1, char);
1406 /* top line: column clues */
1409 for (x = 0; x < w; x++) {
1410 *p++ = (state->numbers->numbers[x] < 10 ?
1411 '0' + state->numbers->numbers[x] :
1412 'A' + state->numbers->numbers[x] - 10);
1417 /* second line: top edge */
1420 for (x = 0; x < w*2-1; x++)
1425 /* grid rows: one line of squares, one line of edges. */
1426 for (y = 0; y < h; y++) {
1427 /* grid square line */
1428 *p++ = (y == state->numbers->row_s) ? 'A' : ' ';
1429 *p++ = (y == state->numbers->row_s) ? '-' : '|';
1431 for (x = 0; x < w; x++) {
1432 unsigned int f = S_E_DIRS(state, x, y, E_TRACK);
1433 if (state->sflags[y*w+x] & S_CLUE) *p++ = 'C';
1434 else if (f == LU || f == RD) *p++ = '/';
1435 else if (f == LD || f == RU) *p++ = '\\';
1436 else if (f == UD) *p++ = '|';
1437 else if (f == RL) *p++ = '-';
1438 else if (state->sflags[y*w+x] & S_NOTRACK) *p++ = 'x';
1442 *p++ = (f & R) ? '-' : ' ';
1446 *p++ = (state->numbers->numbers[w+y] < 10 ?
1447 '0' + state->numbers->numbers[w+y] :
1448 'A' + state->numbers->numbers[w+y] - 10);
1451 if (y == h-1) continue;
1456 for (x = 0; x < w; x++) {
1457 unsigned int f = S_E_DIRS(state, x, y, E_TRACK);
1458 *p++ = (f & D) ? '|' : ' ';
1459 *p++ = (x < w-1) ? ' ' : '|';
1464 /* next line: bottom edge */
1467 for (x = 0; x < w*2-1; x++)
1468 *p++ = (x == state->numbers->col_s*2) ? '|' : '-';
1472 /* final line: bottom clue */
1475 for (x = 0; x < w*2-1; x++)
1476 *p++ = (x == state->numbers->col_s*2) ? 'B' : ' ';
1483 static void debug_state(game_state *state, const char *what) {
1484 char *sstring = game_text_format(state);
1485 debug(("%s: %s", what, sstring));
1489 static void dsf_update_completion(game_state *state, int ax, int ay,
1492 int w = state->p.w, ai = ay*w+ax, bx, by, bi;
1494 if (!(S_E_DIRS(state, ax, ay, E_TRACK) & dir)) return;
1498 if (!INGRID(state, bx, by)) return;
1501 dsf_merge(dsf, ai, bi);
1504 struct tracks_neighbour_ctx {
1506 int i, n, neighbours[4];
1508 static int tracks_neighbour(int vertex, void *vctx)
1510 struct tracks_neighbour_ctx *ctx = (struct tracks_neighbour_ctx *)vctx;
1512 game_state *state = ctx->state;
1513 int w = state->p.w, x = vertex % w, y = vertex / w;
1514 int dirs = S_E_DIRS(state, x, y, E_TRACK);
1517 ctx->i = ctx->n = 0;
1519 for (j = 0; j < 4; j++) {
1522 int nx = x + DX(dir), ny = y + DY(dir);
1523 if (INGRID(state, nx, ny))
1524 ctx->neighbours[ctx->n++] = ny * w + nx;
1529 if (ctx->i < ctx->n)
1530 return ctx->neighbours[ctx->i++];
1535 static int check_completion(game_state *state, int mark)
1537 int w = state->p.w, h = state->p.h, x, y, i, target, ret = TRUE;
1538 int ntrack, nnotrack, ntrackcomplete;
1539 int *dsf, pathclass;
1540 struct findloopstate *fls;
1541 struct tracks_neighbour_ctx ctx;
1544 for (i = 0; i < w+h; i++) {
1545 state->num_errors[i] = 0;
1547 for (i = 0; i < w*h; i++) {
1548 state->sflags[i] &= ~S_ERROR;
1549 if (S_E_COUNT(state, i%w, i/w, E_TRACK) > 0) {
1550 if (S_E_COUNT(state, i%w, i/w, E_TRACK) > 2) {
1552 state->sflags[i] |= S_ERROR;
1558 /* A cell is 'complete', for the purposes of marking the game as
1559 * finished, if it has two edges marked as TRACK. But it only has
1560 * to have one edge marked as TRACK, or be filled in as trackful
1561 * without any specific edges known, to count towards checking
1562 * row/column clue errors. */
1563 for (x = 0; x < w; x++) {
1564 target = state->numbers->numbers[x];
1565 ntrack = nnotrack = ntrackcomplete = 0;
1566 for (y = 0; y < h; y++) {
1567 if (S_E_COUNT(state, x, y, E_TRACK) > 0 ||
1568 state->sflags[y*w+x] & S_TRACK)
1570 if (S_E_COUNT(state, x, y, E_TRACK) == 2)
1572 if (state->sflags[y*w+x] & S_NOTRACK)
1576 if (ntrack > target || nnotrack > (h-target)) {
1577 debug(("col %d error: target %d, track %d, notrack %d",
1578 x, target, ntrack, nnotrack));
1579 state->num_errors[x] = 1;
1583 if (ntrackcomplete != target)
1586 for (y = 0; y < h; y++) {
1587 target = state->numbers->numbers[w+y];
1588 ntrack = nnotrack = ntrackcomplete = 0;
1589 for (x = 0; x < w; x++) {
1590 if (S_E_COUNT(state, x, y, E_TRACK) > 0 ||
1591 state->sflags[y*w+x] & S_TRACK)
1593 if (S_E_COUNT(state, x, y, E_TRACK) == 2)
1595 if (state->sflags[y*w+x] & S_NOTRACK)
1599 if (ntrack > target || nnotrack > (w-target)) {
1600 debug(("row %d error: target %d, track %d, notrack %d",
1601 y, target, ntrack, nnotrack));
1602 state->num_errors[w+y] = 1;
1606 if (ntrackcomplete != target)
1610 dsf = snewn(w*h, int);
1613 for (x = 0; x < w; x++) {
1614 for (y = 0; y < h; y++) {
1615 dsf_update_completion(state, x, y, R, dsf);
1616 dsf_update_completion(state, x, y, D, dsf);
1620 fls = findloop_new_state(w*h);
1622 if (findloop_run(fls, w*h, tracks_neighbour, &ctx)) {
1623 debug(("loop detected, not complete"));
1624 ret = FALSE; /* no loop allowed */
1626 for (x = 0; x < w; x++) {
1627 for (y = 0; y < h; y++) {
1631 for (v = tracks_neighbour(u, &ctx); v >= 0;
1632 v = tracks_neighbour(-1, &ctx))
1633 if (findloop_is_loop_edge(fls, u, v))
1634 state->sflags[y*w+x] |= S_ERROR;
1639 findloop_free_state(fls);
1642 pathclass = dsf_canonify(dsf, state->numbers->row_s*w);
1643 if (pathclass == dsf_canonify(dsf, (h-1)*w + state->numbers->col_s)) {
1644 /* We have a continuous path between the entrance and the exit: any
1645 other path must be in error. */
1646 for (i = 0; i < w*h; i++) {
1647 if ((dsf_canonify(dsf, i) != pathclass) &&
1648 ((state->sflags[i] & S_TRACK) ||
1649 (S_E_COUNT(state, i%w, i/w, E_TRACK) > 0))) {
1651 state->sflags[i] |= S_ERROR;
1655 /* If we _don't_ have such a path, then certainly the game
1656 * can't be in a winning state. So even if we're not
1657 * highlighting any _errors_, we certainly shouldn't
1664 state->completed = ret;
1669 /* Code borrowed from Pearl. */
1672 int dragging, clearing, notrack;
1673 int drag_sx, drag_sy, drag_ex, drag_ey; /* drag start and end grid coords */
1674 int clickx, clicky; /* pixel position of initial click */
1676 int curx, cury; /* grid position of keyboard cursor; uses half-size grid */
1677 int cursor_active; /* TRUE iff cursor is shown */
1680 static game_ui *new_ui(const game_state *state)
1682 game_ui *ui = snew(game_ui);
1684 ui->clearing = ui->notrack = ui->dragging = 0;
1685 ui->drag_sx = ui->drag_sy = ui->drag_ex = ui->drag_ey = -1;
1686 ui->cursor_active = FALSE;
1687 ui->curx = ui->cury = 1;
1692 static void free_ui(game_ui *ui)
1697 static char *encode_ui(const game_ui *ui)
1702 static void decode_ui(game_ui *ui, const char *encoding)
1706 static void game_changed_state(game_ui *ui, const game_state *oldstate,
1707 const game_state *newstate)
1711 #define PREFERRED_TILE_SIZE 30
1712 #define HALFSZ (ds->sz6*3)
1713 #define THIRDSZ (ds->sz6*2)
1714 #define TILE_SIZE (ds->sz6*6)
1716 #define BORDER (TILE_SIZE/8)
1717 #define LINE_THICK (TILE_SIZE/16)
1718 #define GRID_LINE_TL (ds->grid_line_tl)
1719 #define GRID_LINE_BR (ds->grid_line_br)
1720 #define GRID_LINE_ALL (ds->grid_line_all)
1722 #define COORD(x) ( (x+1) * TILE_SIZE + BORDER )
1723 #define CENTERED_COORD(x) ( COORD(x) + TILE_SIZE/2 )
1724 #define FROMCOORD(x) ( ((x) < BORDER) ? -1 : ( ((x) - BORDER) / TILE_SIZE) - 1 )
1726 #define DS_DSHIFT 4 /* R/U/L/D shift, for drag-in-progress flags */
1728 #define DS_ERROR (1 << 8)
1729 #define DS_CLUE (1 << 9)
1730 #define DS_NOTRACK (1 << 10)
1731 #define DS_FLASH (1 << 11)
1732 #define DS_CURSOR (1 << 12) /* cursor in square (centre, or on edge) */
1733 #define DS_TRACK (1 << 13)
1734 #define DS_CLEARING (1 << 14)
1736 #define DS_NSHIFT 16 /* R/U/L/D shift, for no-track edge flags */
1737 #define DS_CSHIFT 20 /* R/U/L/D shift, for cursor-on-edge */
1739 struct game_drawstate {
1740 int sz6, grid_line_all, grid_line_tl, grid_line_br;
1744 unsigned int *flags, *flags_drag;
1748 static void update_ui_drag(const game_state *state, game_ui *ui, int gx, int gy)
1750 int w = state->p.w, h = state->p.h;
1751 int dx = abs(ui->drag_sx - gx), dy = abs(ui->drag_sy - gy);
1754 ui->drag_ex = gx < 0 ? 0 : gx >= w ? w-1 : gx;
1755 ui->drag_ey = ui->drag_sy;
1756 ui->dragging = TRUE;
1757 } else if (dx == 0) {
1758 ui->drag_ex = ui->drag_sx;
1759 ui->drag_ey = gy < 0 ? 0 : gy >= h ? h-1 : gy;
1760 ui->dragging = TRUE;
1762 ui->drag_ex = ui->drag_sx;
1763 ui->drag_ey = ui->drag_sy;
1764 ui->dragging = FALSE;
1768 static int ui_can_flip_edge(const game_state *state, int x, int y, int dir,
1771 int w = state->p.w /*, h = state->shared->h, sz = state->shared->sz */;
1772 int x2 = x + DX(dir);
1773 int y2 = y + DY(dir);
1774 unsigned int sf1, sf2, ef;
1776 if (!INGRID(state, x, y) || !INGRID(state, x2, y2))
1779 sf1 = state->sflags[y*w + x];
1780 sf2 = state->sflags[y2*w + x2];
1781 if ( !notrack && ((sf1 & S_CLUE) || (sf2 & S_CLUE)) )
1784 ef = S_E_FLAGS(state, x, y, dir);
1786 /* if we're going to _set_ NOTRACK (i.e. the flag is currently unset),
1787 make sure the edge is not already set to TRACK. The adjacent squares
1788 could be set to TRACK, because we don't know which edges the general
1789 square setting refers to. */
1790 if (!(ef & E_NOTRACK) && (ef & E_TRACK))
1793 if (!(ef & E_TRACK)) {
1794 /* if we're going to _set_ TRACK, make sure neither adjacent square nor
1795 the edge itself is already set to NOTRACK. */
1796 if ((sf1 & S_NOTRACK) || (sf2 & S_NOTRACK) || (ef & E_NOTRACK))
1798 /* if we're going to _set_ TRACK, make sure neither adjacent square has
1799 2 track flags already. */
1800 if ((S_E_COUNT(state, x, y, E_TRACK) >= 2) ||
1801 (S_E_COUNT(state, x2, y2, E_TRACK) >= 2))
1808 static int ui_can_flip_square(const game_state *state, int x, int y, int notrack)
1810 int w = state->p.w, trackc;
1813 if (!INGRID(state, x, y)) return FALSE;
1814 sf = state->sflags[y*w+x];
1815 trackc = S_E_COUNT(state, x, y, E_TRACK);
1817 if (sf & S_CLUE) return FALSE;
1820 /* If we're setting S_NOTRACK, we cannot have either S_TRACK or any E_TRACK. */
1821 if (!(sf & S_NOTRACK) && ((sf & S_TRACK) || (trackc > 0)))
1824 /* If we're setting S_TRACK, we cannot have any S_NOTRACK (we could have
1825 E_NOTRACK, though, because one or two wouldn't rule out a track) */
1826 if (!(sf & S_TRACK) && (sf & S_NOTRACK))
1832 static char *edge_flip_str(const game_state *state, int x, int y, int dir, int notrack, char *buf) {
1833 unsigned ef = S_E_FLAGS(state, x, y, dir);
1837 c = (ef & E_NOTRACK) ? 'n' : 'N';
1839 c = (ef & E_TRACK) ? 't' : 'T';
1841 sprintf(buf, "%c%c%d,%d", c, MOVECHAR(dir), x, y);
1845 static char *square_flip_str(const game_state *state, int x, int y, int notrack, char *buf) {
1846 unsigned f = state->sflags[y*state->p.w+x];
1850 c = (f & E_NOTRACK) ? 'n' : 'N';
1852 c = (f & E_TRACK) ? 't' : 'T';
1854 sprintf(buf, "%cS%d,%d", c, x, y);
1858 #define SIGN(x) ((x<0) ? -1 : (x>0))
1860 static game_state *copy_and_apply_drag(const game_state *state, const game_ui *ui)
1862 game_state *after = dup_game(state);
1863 int x1, y1, x2, y2, x, y, w = state->p.w;
1864 unsigned f = ui->notrack ? S_NOTRACK : S_TRACK, ff;
1866 x1 = min(ui->drag_sx, ui->drag_ex); x2 = max(ui->drag_sx, ui->drag_ex);
1867 y1 = min(ui->drag_sy, ui->drag_ey); y2 = max(ui->drag_sy, ui->drag_ey);
1869 /* actually either x1 == x2, or y1 == y2, but it's easier just to code
1871 for (x = x1; x <= x2; x++) {
1872 for (y = y1; y <= y2; y++) {
1873 ff = state->sflags[y*w+x];
1874 if (ui->clearing && !(ff & f))
1875 continue; /* nothing to do, clearing and already clear */
1876 else if (!ui->clearing && (ff & f))
1877 continue; /* nothing to do, setting and already set */
1878 else if (ui_can_flip_square(state, x, y, ui->notrack))
1879 after->sflags[y*w+x] ^= f;
1885 #define KEY_DIRECTION(btn) (\
1886 (btn) == CURSOR_DOWN ? D : (btn) == CURSOR_UP ? U :\
1887 (btn) == CURSOR_LEFT ? L : R)
1889 static char *interpret_move(const game_state *state, game_ui *ui,
1890 const game_drawstate *ds,
1891 int x, int y, int button)
1893 int w = state->p.w, h = state->p.h, direction;
1894 int gx = FROMCOORD(x), gy = FROMCOORD(y);
1897 /* --- mouse operations --- */
1899 if (IS_MOUSE_DOWN(button)) {
1900 ui->cursor_active = FALSE;
1901 ui->dragging = FALSE;
1903 if (!INGRID(state, gx, gy)) {
1904 /* can't drag from off grid */
1908 if (button == RIGHT_BUTTON) {
1910 ui->clearing = state->sflags[gy*w+gx] & S_NOTRACK;
1912 ui->notrack = FALSE;
1913 ui->clearing = state->sflags[gy*w+gx] & S_TRACK;
1918 ui->drag_sx = ui->drag_ex = gx;
1919 ui->drag_sy = ui->drag_ey = gy;
1924 if (IS_MOUSE_DRAG(button)) {
1925 ui->cursor_active = FALSE;
1926 update_ui_drag(state, ui, gx, gy);
1930 if (IS_MOUSE_RELEASE(button)) {
1931 ui->cursor_active = FALSE;
1933 (ui->drag_sx != ui->drag_ex || ui->drag_sy != ui->drag_ey)) {
1934 game_state *dragged = copy_and_apply_drag(state, ui);
1935 char *ret = move_string_diff(state, dragged, FALSE);
1944 /* We might still have been dragging (and just done a one-
1945 * square drag): cancel drag, so undo doesn't make it like
1946 * a drag-in-progress. */
1949 /* Click (or tiny drag). Work out which edge we were
1953 * We process clicks based on the mouse-down location,
1954 * because that's more natural for a user to carefully
1955 * control than the mouse-up.
1960 cx = CENTERED_COORD(gx);
1961 cy = CENTERED_COORD(gy);
1963 if (!INGRID(state, gx, gy) || FROMCOORD(x) != gx || FROMCOORD(y) != gy)
1966 if (max(abs(x-cx),abs(y-cy)) < TILE_SIZE/4) {
1967 if (ui_can_flip_square(state, gx, gy, button == RIGHT_RELEASE))
1968 return square_flip_str(state, gx, gy, button == RIGHT_RELEASE, tmpbuf);
1971 if (abs(x-cx) < abs(y-cy)) {
1972 /* Closest to top/bottom edge. */
1973 direction = (y < cy) ? U : D;
1975 /* Closest to left/right edge. */
1976 direction = (x < cx) ? L : R;
1978 if (ui_can_flip_edge(state, gx, gy, direction,
1979 button == RIGHT_RELEASE))
1980 return edge_flip_str(state, gx, gy, direction,
1981 button == RIGHT_RELEASE, tmpbuf);
1988 /* --- cursor/keyboard operations --- */
1990 if (IS_CURSOR_MOVE(button)) {
1991 int dx = (button == CURSOR_LEFT) ? -1 : ((button == CURSOR_RIGHT) ? +1 : 0);
1992 int dy = (button == CURSOR_DOWN) ? +1 : ((button == CURSOR_UP) ? -1 : 0);
1994 if (!ui->cursor_active) {
1995 ui->cursor_active = TRUE;
1999 ui->curx = ui->curx + dx;
2000 ui->cury = ui->cury + dy;
2001 if ((ui->curx % 2 == 0) && (ui->cury % 2 == 0)) {
2002 /* disallow cursor on square corners: centres and edges only */
2003 ui->curx += dx; ui->cury += dy;
2005 ui->curx = min(max(ui->curx, 1), 2*w-1);
2006 ui->cury = min(max(ui->cury, 1), 2*h-1);
2010 if (IS_CURSOR_SELECT(button)) {
2011 if (!ui->cursor_active) {
2012 ui->cursor_active = TRUE;
2015 /* click on square corner does nothing (shouldn't get here) */
2016 if ((ui->curx % 2) == 0 && (ui->cury % 2 == 0))
2021 direction = ((ui->curx % 2) == 0) ? L : ((ui->cury % 2) == 0) ? U : 0;
2024 ui_can_flip_edge(state, gx, gy, direction, button == CURSOR_SELECT2))
2025 return edge_flip_str(state, gx, gy, direction, button == CURSOR_SELECT2, tmpbuf);
2026 else if (!direction &&
2027 ui_can_flip_square(state, gx, gy, button == CURSOR_SELECT2))
2028 return square_flip_str(state, gx, gy, button == CURSOR_SELECT2, tmpbuf);
2033 /* helps to debug the solver */
2034 if (button == 'H' || button == 'h')
2041 static game_state *execute_move(const game_state *state, const char *move)
2043 int w = state->p.w, x, y, n, i;
2046 game_state *ret = dup_game(state);
2048 /* this is breaking the bank on GTK, which vsprintf's into a fixed-size buffer
2049 * which is 4096 bytes long. vsnprintf needs a feature-test macro to use, faff. */
2050 /*debug(("move: %s\n", move));*/
2055 ret->used_solve = TRUE;
2057 } else if (c == 'T' || c == 't' || c == 'N' || c == 'n') {
2058 /* set track, clear track; set notrack, clear notrack */
2060 if (sscanf(move, "%c%d,%d%n", &d, &x, &y, &n) != 3)
2062 if (!INGRID(state, x, y)) goto badmove;
2064 f = (c == 'T' || c == 't') ? S_TRACK : S_NOTRACK;
2067 if (c == 'T' || c == 'N')
2068 ret->sflags[y*w+x] |= f;
2070 ret->sflags[y*w+x] &= ~f;
2071 } else if (d == 'U' || d == 'D' || d == 'L' || d == 'R') {
2072 for (i = 0; i < 4; i++) {
2075 if (MOVECHAR(df) == d) {
2076 if (c == 'T' || c == 'N')
2077 S_E_SET(ret, x, y, df, f);
2079 S_E_CLEAR(ret, x, y, df, f);
2085 } else if (c == 'H') {
2086 tracks_solve(ret, DIFFCOUNT);
2097 check_completion(ret, TRUE);
2106 /* ----------------------------------------------------------------------
2110 #define FLASH_TIME 0.5F
2112 static void game_compute_size(const game_params *params, int tilesize,
2115 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
2119 ads.sz6 = tilesize/6;
2120 *x = (params->w+2) * TILE_SIZE + 2 * BORDER;
2121 *y = (params->h+2) * TILE_SIZE + 2 * BORDER;
2124 static void game_set_size(drawing *dr, game_drawstate *ds,
2125 const game_params *params, int tilesize)
2127 ds->sz6 = tilesize/6;
2128 ds->grid_line_all = max(LINE_THICK, 1);
2129 ds->grid_line_br = ds->grid_line_all / 2;
2130 ds->grid_line_tl = ds->grid_line_all - ds->grid_line_br;
2134 COL_BACKGROUND, COL_LOWLIGHT, COL_HIGHLIGHT,
2135 COL_TRACK_BACKGROUND = COL_LOWLIGHT,
2136 COL_GRID, COL_CLUE, COL_CURSOR,
2137 COL_TRACK, COL_TRACK_CLUE, COL_SLEEPER,
2138 COL_DRAGON, COL_DRAGOFF,
2139 COL_ERROR, COL_FLASH, COL_ERROR_BACKGROUND,
2143 static float *game_colours(frontend *fe, int *ncolours)
2145 float *ret = snewn(3 * NCOLOURS, float);
2148 game_mkhighlight(fe, ret, COL_BACKGROUND, COL_HIGHLIGHT, COL_LOWLIGHT);
2150 for (i = 0; i < 3; i++) {
2151 ret[COL_TRACK_CLUE * 3 + i] = 0.0F;
2152 ret[COL_TRACK * 3 + i] = 0.5F;
2153 ret[COL_CLUE * 3 + i] = 0.0F;
2154 ret[COL_GRID * 3 + i] = 0.75F;
2155 ret[COL_CURSOR * 3 + i] = 0.6F;
2156 ret[COL_ERROR_BACKGROUND * 3 + i] = 1.0F;
2159 ret[COL_SLEEPER * 3 + 0] = 0.5F;
2160 ret[COL_SLEEPER * 3 + 1] = 0.4F;
2161 ret[COL_SLEEPER * 3 + 2] = 0.1F;
2163 ret[COL_ERROR * 3 + 0] = 1.0F;
2164 ret[COL_ERROR * 3 + 1] = 0.0F;
2165 ret[COL_ERROR * 3 + 2] = 0.0F;
2167 ret[COL_DRAGON * 3 + 0] = 0.0F;
2168 ret[COL_DRAGON * 3 + 1] = 0.0F;
2169 ret[COL_DRAGON * 3 + 2] = 1.0F;
2171 ret[COL_DRAGOFF * 3 + 0] = 0.8F;
2172 ret[COL_DRAGOFF * 3 + 1] = 0.8F;
2173 ret[COL_DRAGOFF * 3 + 2] = 1.0F;
2175 ret[COL_FLASH * 3 + 0] = 1.0F;
2176 ret[COL_FLASH * 3 + 1] = 1.0F;
2177 ret[COL_FLASH * 3 + 2] = 1.0F;
2179 *ncolours = NCOLOURS;
2183 static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state)
2185 struct game_drawstate *ds = snew(struct game_drawstate);
2189 ds->started = FALSE;
2193 ds->sz = ds->w*ds->h;
2194 ds->flags = snewn(ds->sz, unsigned int);
2195 ds->flags_drag = snewn(ds->sz, unsigned int);
2196 for (i = 0; i < ds->sz; i++)
2197 ds->flags[i] = ds->flags_drag[i] = 0;
2199 ds->num_errors = snewn(ds->w+ds->h, int);
2200 for (i = 0; i < ds->w+ds->h; i++)
2201 ds->num_errors[i] = 0;
2206 static void game_free_drawstate(drawing *dr, game_drawstate *ds)
2209 sfree(ds->flags_drag);
2210 sfree(ds->num_errors);
2214 static void draw_circle_sleepers(drawing *dr, game_drawstate *ds,
2215 float cx, float cy, float r2, float thickness, int c)
2217 float qr6 = (float)PI/12, qr3 = (float)PI/6, th, x1, y1, x2, y2;
2218 float t6 = THIRDSZ/2.0F, r1 = t6;
2221 for (i = 0; i < 12; i++) {
2223 x1 = r1*(float)cos(th);
2224 x2 = r2*(float)cos(th);
2225 y1 = r1*(float)sin(th);
2226 y2 = r2*(float)sin(th);
2227 draw_thick_line(dr, thickness, cx+x1, cy+y1, cx+x2, cy+y2, c);
2231 static void draw_thick_circle_outline(drawing *dr, float thickness,
2232 float cx, float cy, float r,
2235 float circ4 = 0.5F * (float)PI * r, ang, x1, y1, x2, y2;
2238 nseg = (int)(circ4 / 4.0F)*4; /* ensure a quarter-circle has a whole #segs */
2239 ang = 2.0F*(float)PI / nseg;
2241 for (i = 0; i < nseg; i++) {
2242 float th = ang * i, th2 = ang * (i+1);
2243 x1 = cx + r*(float)cos(th);
2244 x2 = cx + r*(float)cos(th2);
2245 y1 = cy + r*(float)sin(th);
2246 y2 = cy + r*(float)sin(th2);
2247 debug(("circ outline: x=%.2f -> %.2f, thick=%.2f", x1, x2, thickness));
2248 draw_thick_line(dr, thickness, x1, y1, x2, y2, colour);
2252 static void draw_tracks_specific(drawing *dr, game_drawstate *ds,
2253 int x, int y, unsigned int flags,
2254 int ctrack, int csleeper)
2256 float ox = (float)COORD(x), oy = (float)COORD(y), cx, cy;
2257 float t1 = (float)TILE_SIZE, t3 = TILE_SIZE/3.0F, t6 = TILE_SIZE/6.0F;
2259 float thick_track = TILE_SIZE/8.0F, thick_sleeper = TILE_SIZE/12.0F;
2262 for (i = 1; i <= 7; i+=2) {
2263 cx = ox + TILE_SIZE/8.0F*i;
2264 draw_thick_line(dr, thick_sleeper,
2265 cx, oy+t6, cx, oy+t6+2*t3, csleeper);
2267 draw_thick_line(dr, thick_track, ox, oy + t3, ox + TILE_SIZE, oy + t3, ctrack);
2268 draw_thick_line(dr, thick_track, ox, oy + 2*t3, ox + TILE_SIZE, oy + 2*t3, ctrack);
2272 for (i = 1; i <= 7; i+=2) {
2273 cy = oy + TILE_SIZE/8.0F*i;
2274 draw_thick_line(dr, thick_sleeper,
2275 ox+t6, cy, ox+t6+2*t3, cy, csleeper);
2277 debug(("vert line: x=%.2f, thick=%.2f", ox + t3, thick_track));
2278 draw_thick_line(dr, thick_track, ox + t3, oy, ox + t3, oy + TILE_SIZE, ctrack);
2279 draw_thick_line(dr, thick_track, ox + 2*t3, oy, ox + 2*t3, oy + TILE_SIZE, ctrack);
2282 if (flags == UL || flags == DL || flags == UR || flags == DR) {
2283 cx = (flags & L) ? ox : ox + TILE_SIZE;
2284 cy = (flags & U) ? oy : oy + TILE_SIZE;
2286 draw_circle_sleepers(dr, ds, cx, cy, (float)(5*t6), thick_sleeper, csleeper);
2288 draw_thick_circle_outline(dr, thick_track, (float)cx, (float)cy,
2290 draw_thick_circle_outline(dr, thick_track, (float)cx, (float)cy,
2296 for (d = 1; d < 16; d *= 2) {
2297 float ox1 = 0, ox2 = 0, oy1 = 0, oy2 = 0;
2299 if (!(flags & d)) continue;
2301 for (i = 1; i <= 2; i++) {
2306 } else if (d == R) {
2308 ox2 = t1 - thick_track;
2310 } else if (d == U) {
2314 } else if (d == D) {
2317 oy2 = t1 - thick_track;
2319 draw_thick_line(dr, thick_track, ox+ox1, oy+oy1, ox+ox2, oy+oy2, ctrack);
2324 static unsigned int best_bits(unsigned int flags, unsigned int flags_drag, int *col)
2326 int nb_orig = nbits[flags & ALLDIR], nb_drag = nbits[flags_drag & ALLDIR];
2328 if (nb_orig > nb_drag) {
2330 return flags & ALLDIR;
2331 } else if (nb_orig < nb_drag) {
2333 return flags_drag & ALLDIR;
2335 return flags & ALLDIR; /* same number of bits: no special colour. */
2338 static void draw_square(drawing *dr, game_drawstate *ds,
2339 int x, int y, unsigned int flags, unsigned int flags_drag)
2341 int t2 = HALFSZ, t16 = HALFSZ/4, off;
2342 int ox = COORD(x), oy = COORD(y), cx = ox + t2, cy = oy + t2, d, c;
2343 int bg = (flags & DS_TRACK) ? COL_TRACK_BACKGROUND : COL_BACKGROUND;
2344 unsigned int flags_best;
2348 /* Clip to the grid square. */
2349 clip(dr, ox, oy, TILE_SIZE, TILE_SIZE);
2351 /* Clear the square so that it's got an appropriately-sized border
2352 * in COL_GRID and a central area in the right background colour. */
2353 best_bits((flags & DS_TRACK) == DS_TRACK,
2354 (flags_drag & DS_TRACK) == DS_TRACK, &bg);
2355 draw_rect(dr, ox, oy, TILE_SIZE, TILE_SIZE, COL_GRID);
2356 draw_rect(dr, ox + GRID_LINE_TL, oy + GRID_LINE_TL,
2357 TILE_SIZE - GRID_LINE_ALL, TILE_SIZE - GRID_LINE_ALL, bg);
2359 /* More outlines for clue squares. */
2360 if (flags & DS_CURSOR) {
2361 int curx, cury, curw, curh;
2364 curx = ox + off; cury = oy + off;
2365 curw = curh = TILE_SIZE - (2*off) + 1;
2367 if (flags & (U << DS_CSHIFT)) {
2368 cury = oy - off; curh = 2*off + 1;
2369 } else if (flags & (D << DS_CSHIFT)) {
2370 cury = oy + TILE_SIZE - off; curh = 2*off + 1;
2371 } else if (flags & (L << DS_CSHIFT)) {
2372 curx = ox - off; curw = 2*off + 1;
2373 } else if (flags & (R << DS_CSHIFT)) {
2374 curx = ox + TILE_SIZE - off; curw = 2*off + 1;
2377 draw_rect_outline(dr, curx, cury, curw, curh, COL_GRID);
2380 /* Draw tracks themselves */
2381 c = (flags & DS_ERROR) ? COL_ERROR :
2382 (flags & DS_FLASH) ? COL_FLASH :
2383 (flags & DS_CLUE) ? COL_TRACK_CLUE : COL_TRACK;
2384 flags_best = best_bits(flags, flags_drag, &c);
2385 draw_tracks_specific(dr, ds, x, y, flags_best, c, COL_SLEEPER);
2387 /* Draw no-track marks, if present, in square and on edges. */
2389 flags_best = best_bits((flags & DS_NOTRACK) == DS_NOTRACK,
2390 (flags_drag & DS_NOTRACK) == DS_NOTRACK, &c);
2393 draw_thick_line(dr, LINE_THICK, cx - off, cy - off, cx + off, cy + off, c);
2394 draw_thick_line(dr, LINE_THICK, cx - off, cy + off, cx + off, cy - off, c);
2398 flags_best = best_bits(flags >> DS_NSHIFT, flags_drag >> DS_NSHIFT, &c);
2399 for (d = 1; d < 16; d *= 2) {
2404 if (flags_best & d) {
2405 cx += (d == R) ? t2 : (d == L) ? -t2 : 0;
2406 cy += (d == D) ? t2 : (d == U) ? -t2 : 0;
2408 draw_thick_line(dr, LINE_THICK, cx - off, cy - off, cx + off, cy + off, c);
2409 draw_thick_line(dr, LINE_THICK, cx - off, cy + off, cx + off, cy - off, c);
2414 draw_update(dr, ox, oy, TILE_SIZE, TILE_SIZE);
2417 static void draw_clue(drawing *dr, game_drawstate *ds, int w, int clue, int i, int col, int bg)
2419 int cx, cy, tsz = TILE_SIZE/2;
2423 cx = CENTERED_COORD(i);
2424 cy = CENTERED_COORD(-1);
2426 cx = CENTERED_COORD(w);
2427 cy = CENTERED_COORD(i-w);
2430 draw_rect(dr, cx - tsz + GRID_LINE_TL, cy - tsz + GRID_LINE_TL,
2431 TILE_SIZE - GRID_LINE_ALL, TILE_SIZE - GRID_LINE_ALL,
2433 sprintf(buf, "%d", clue);
2434 draw_text(dr, cx, cy, FONT_VARIABLE, tsz, ALIGN_VCENTRE|ALIGN_HCENTRE,
2436 draw_update(dr, cx - tsz + GRID_LINE_TL, cy - tsz + GRID_LINE_TL,
2437 TILE_SIZE - GRID_LINE_ALL, TILE_SIZE - GRID_LINE_ALL);
2440 static void draw_loop_ends(drawing *dr, game_drawstate *ds,
2441 const game_state *state, int c)
2443 int tsz = TILE_SIZE/2;
2445 draw_text(dr, CENTERED_COORD(-1), CENTERED_COORD(state->numbers->row_s),
2446 FONT_VARIABLE, tsz, ALIGN_VCENTRE|ALIGN_HCENTRE,
2449 draw_text(dr, CENTERED_COORD(state->numbers->col_s), CENTERED_COORD(state->p.h),
2450 FONT_VARIABLE, tsz, ALIGN_VCENTRE|ALIGN_HCENTRE,
2454 static unsigned int s2d_flags(const game_state *state, int x, int y, const game_ui *ui)
2459 f = S_E_DIRS(state, x, y, E_TRACK);
2460 f |= (S_E_DIRS(state, x, y, E_NOTRACK) << DS_NSHIFT);
2462 if (state->sflags[y*w+x] & S_ERROR)
2464 if (state->sflags[y*w+x] & S_CLUE)
2466 if (state->sflags[y*w+x] & S_NOTRACK)
2468 if ((state->sflags[y*w+x] & S_TRACK) || (S_E_COUNT(state, x, y, E_TRACK) > 0))
2471 if (ui->cursor_active) {
2472 if (ui->curx >= x*2 && ui->curx <= (x+1)*2 &&
2473 ui->cury >= y*2 && ui->cury <= (y+1)*2) {
2475 if (ui->curx == x*2) f |= (L << DS_CSHIFT);
2476 if (ui->curx == (x+1)*2) f |= (R << DS_CSHIFT);
2477 if (ui->cury == y*2) f |= (U << DS_CSHIFT);
2478 if (ui->cury == (y+1)*2) f |= (D << DS_CSHIFT);
2485 static void game_redraw(drawing *dr, game_drawstate *ds, const game_state *oldstate,
2486 const game_state *state, int dir, const game_ui *ui,
2487 float animtime, float flashtime)
2489 int i, x, y, force = 0, flashing = 0, w = ds->w, h = ds->h;
2490 game_state *drag_state = NULL;
2494 * The initial contents of the window are not guaranteed and
2495 * can vary with front ends. To be on the safe side, all games
2496 * should start by drawing a big background-colour rectangle
2497 * covering the whole window.
2499 draw_rect(dr, 0, 0, (w+2)*TILE_SIZE + 2*BORDER, (h+2)*TILE_SIZE + 2*BORDER,
2502 draw_loop_ends(dr, ds, state, COL_CLUE);
2504 draw_rect(dr, COORD(0) - GRID_LINE_BR, COORD(0) - GRID_LINE_BR,
2505 ds->w * TILE_SIZE + GRID_LINE_ALL,
2506 ds->h * TILE_SIZE + GRID_LINE_ALL, COL_GRID);
2508 draw_update(dr, 0, 0, (w+2)*TILE_SIZE + 2*BORDER, (h+2)*TILE_SIZE + 2*BORDER);
2514 for (i = 0; i < w+h; i++) {
2515 if (force || (state->num_errors[i] != ds->num_errors[i])) {
2516 ds->num_errors[i] = state->num_errors[i];
2517 draw_clue(dr, ds, w, state->numbers->numbers[i], i,
2518 ds->num_errors[i] ? COL_ERROR : COL_CLUE,
2519 ds->num_errors[i] ? COL_ERROR_BACKGROUND : COL_BACKGROUND);
2523 if (flashtime > 0 &&
2524 (flashtime <= FLASH_TIME/3 ||
2525 flashtime >= FLASH_TIME*2/3))
2526 flashing = DS_FLASH;
2529 drag_state = copy_and_apply_drag(state, ui);
2531 for (x = 0; x < w; x++) {
2532 for (y = 0; y < h; y++) {
2533 unsigned int f, f_d;
2535 f = s2d_flags(state, x, y, ui) | flashing;
2536 f_d = drag_state ? s2d_flags(drag_state, x, y, ui) : f;
2538 if (f != ds->flags[y*w+x] || f_d != ds->flags_drag[y*w+x] || force) {
2539 ds->flags[y*w+x] = f;
2540 ds->flags_drag[y*w+x] = f_d;
2541 draw_square(dr, ds, x, y, f, f_d);
2546 if (drag_state) free_game(drag_state);
2549 static float game_anim_length(const game_state *oldstate, const game_state *newstate,
2550 int dir, game_ui *ui)
2555 static float game_flash_length(const game_state *oldstate, const game_state *newstate,
2556 int dir, game_ui *ui)
2558 if (!oldstate->completed &&
2559 newstate->completed && !newstate->used_solve)
2565 static int game_status(const game_state *state)
2567 return state->completed ? +1 : 0;
2570 static int game_timing_state(const game_state *state, game_ui *ui)
2575 static void game_print_size(const game_params *params, float *x, float *y)
2579 /* The Times uses 7mm squares */
2580 game_compute_size(params, 700, &pw, &ph);
2585 static void game_print(drawing *dr, const game_state *state, int tilesize)
2587 int w = state->p.w, h = state->p.h;
2588 int black = print_mono_colour(dr, 0), grey = print_grey_colour(dr, 0.5F);
2591 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
2592 game_drawstate ads, *ds = &ads;
2593 game_set_size(dr, ds, NULL, tilesize);
2595 /* Grid, then border (second so it is on top) */
2596 print_line_width(dr, TILE_SIZE / 24);
2597 for (x = 1; x < w; x++)
2598 draw_line(dr, COORD(x), COORD(0), COORD(x), COORD(h), grey);
2599 for (y = 1; y < h; y++)
2600 draw_line(dr, COORD(0), COORD(y), COORD(w), COORD(y), grey);
2602 print_line_width(dr, TILE_SIZE / 16);
2603 draw_rect_outline(dr, COORD(0), COORD(0), w*TILE_SIZE, h*TILE_SIZE, black);
2605 print_line_width(dr, TILE_SIZE / 24);
2607 /* clue numbers, and loop ends */
2608 for (i = 0; i < w+h; i++)
2609 draw_clue(dr, ds, w, state->numbers->numbers[i], i,
2610 black, COL_BACKGROUND);
2611 draw_loop_ends(dr, ds, state, black);
2613 /* clue tracks / solution */
2614 for (x = 0; x < w; x++) {
2615 for (y = 0; y < h; y++) {
2616 clip(dr, COORD(x), COORD(y), TILE_SIZE, TILE_SIZE);
2617 draw_tracks_specific(dr, ds, x, y, S_E_DIRS(state, x, y, E_TRACK),
2625 #define thegame tracks
2628 const struct game thegame = {
2629 "Train Tracks", "games.tracks", "tracks",
2631 game_fetch_preset, NULL,
2636 TRUE, game_configure, custom_params,
2644 TRUE, game_can_format_as_text_now, game_text_format,
2652 PREFERRED_TILE_SIZE, game_compute_size, game_set_size,
2655 game_free_drawstate,
2660 TRUE, FALSE, game_print_size, game_print,
2661 FALSE, /* wants_statusbar */
2662 FALSE, game_timing_state,
2666 /* vim: set shiftwidth=4 tabstop=8: */