summaryrefslogtreecommitdiff
path: root/apps/plugins/puzzles/src/tracks.c
diff options
context:
space:
mode:
Diffstat (limited to 'apps/plugins/puzzles/src/tracks.c')
-rw-r--r--apps/plugins/puzzles/src/tracks.c2660
1 files changed, 2660 insertions, 0 deletions
diff --git a/apps/plugins/puzzles/src/tracks.c b/apps/plugins/puzzles/src/tracks.c
new file mode 100644
index 0000000000..43428a19e9
--- /dev/null
+++ b/apps/plugins/puzzles/src/tracks.c
@@ -0,0 +1,2660 @@
1/*
2 * Implementation of 'Train Tracks', a puzzle from the Times on Saturday.
3 *
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."
8 *
9 * Puzzles:
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
15 */
16
17#include <stdio.h>
18#include <stdlib.h>
19#include <string.h>
20#include <assert.h>
21#include <ctype.h>
22#include <math.h>
23
24#include "puzzles.h"
25
26/* --- Game parameters --- */
27
28/*
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.
31 */
32#define DIFFLIST(A) \
33 A(EASY,Easy,e) \
34 A(TRICKY,Tricky,t)
35
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
40enum { DIFFLIST(ENUM) DIFFCOUNT };
41static char const *const tracks_diffnames[] = { DIFFLIST(TITLE) };
42static char const tracks_diffchars[] = DIFFLIST(ENCODE);
43#define DIFFCONFIG DIFFLIST(CONFIG)
44
45struct game_params {
46 int w, h, diff, single_ones;
47};
48
49static game_params *default_params(void)
50{
51 game_params *ret = snew(game_params);
52
53 ret->w = ret->h = 8;
54 ret->diff = DIFF_TRICKY;
55 ret->single_ones = TRUE;
56
57 return ret;
58}
59
60static const struct game_params tracks_presets[] = {
61 {8, 8, DIFF_EASY, 1},
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},
71};
72
73static int game_fetch_preset(int i, char **name, game_params **params)
74{
75 game_params *ret;
76 char str[80];
77
78 if (i < 0 || i >= lenof(tracks_presets))
79 return FALSE;
80
81 ret = snew(game_params);
82 *ret = tracks_presets[i];
83
84 sprintf(str, "%dx%d %s", ret->w, ret->h, tracks_diffnames[ret->diff]);
85
86 *name = dupstr(str);
87 *params = ret;
88 return TRUE;
89}
90
91static void free_params(game_params *params)
92{
93 sfree(params);
94}
95
96static game_params *dup_params(const game_params *params)
97{
98 game_params *ret = snew(game_params);
99 *ret = *params; /* structure copy */
100 return ret;
101}
102
103static void decode_params(game_params *params, char const *string)
104{
105 params->w = params->h = atoi(string);
106 while (*string && isdigit((unsigned char)*string)) string++;
107 if (*string == 'x') {
108 string++;
109 params->h = atoi(string);
110 while (*string && isdigit((unsigned char)*string)) string++;
111 }
112 if (*string == 'd') {
113 int i;
114 string++;
115 params->diff = DIFF_TRICKY;
116 for (i = 0; i < DIFFCOUNT; i++)
117 if (*string == tracks_diffchars[i])
118 params->diff = i;
119 if (*string) string++;
120 }
121 params->single_ones = TRUE;
122 if (*string == 'o') {
123 params->single_ones = FALSE;
124 string++;
125 }
126
127}
128
129static char *encode_params(const game_params *params, int full)
130{
131 char buf[120];
132
133 sprintf(buf, "%dx%d", params->w, params->h);
134 if (full)
135 sprintf(buf + strlen(buf), "d%c%s",
136 tracks_diffchars[params->diff],
137 params->single_ones ? "" : "o");
138 return dupstr(buf);
139}
140
141static config_item *game_configure(const game_params *params)
142{
143 config_item *ret;
144 char buf[80];
145
146 ret = snewn(5, config_item);
147
148 ret[0].name = "Width";
149 ret[0].type = C_STRING;
150 sprintf(buf, "%d", params->w);
151 ret[0].sval = dupstr(buf);
152 ret[0].ival = 0;
153
154 ret[1].name = "Height";
155 ret[1].type = C_STRING;
156 sprintf(buf, "%d", params->h);
157 ret[1].sval = dupstr(buf);
158 ret[1].ival = 0;
159
160 ret[2].name = "Difficulty";
161 ret[2].type = C_CHOICES;
162 ret[2].sval = DIFFCONFIG;
163 ret[2].ival = params->diff;
164
165 ret[3].name = "Disallow consecutive 1 clues";
166 ret[3].type = C_BOOLEAN;
167 ret[3].ival = params->single_ones;
168
169 ret[4].name = NULL;
170 ret[4].type = C_END;
171 ret[4].sval = NULL;
172 ret[4].ival = 0;
173
174 return ret;
175}
176
177static game_params *custom_params(const config_item *cfg)
178{
179 game_params *ret = snew(game_params);
180
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;
185
186 return ret;
187}
188
189static char *validate_params(const game_params *params, int full)
190{
191 /*
192 * Generating anything under 4x4 runs into trouble of one kind
193 * or another.
194 */
195 if (params->w < 4 || params->h < 4)
196 return "Width and height must both be at least four";
197 return NULL;
198}
199
200/* --- Game state --- */
201
202/* flag usage copied from pearl */
203
204#define R 1
205#define U 2
206#define L 4
207#define D 8
208
209#define MOVECHAR(m) ((m==R)?'R':(m==U)?'U':(m==L)?'L':(m==D)?'D':'?')
210
211#define DX(d) ( ((d)==R) - ((d)==L) )
212#define DY(d) ( ((d)==D) - ((d)==U) )
213
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)
217
218#define LR (L | R)
219#define RL (R | L)
220#define UD (U | D)
221#define DU (D | U)
222#define LU (L | U)
223#define UL (U | L)
224#define LD (L | D)
225#define DL (D | L)
226#define RU (R | U)
227#define UR (U | R)
228#define RD (R | D)
229#define DR (D | R)
230#define ALLDIR 15
231#define BLANK 0
232#define UNKNOWN 15
233
234int nbits[] = { 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4 };
235
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 */
239#define S_ERROR 4
240#define S_CLUE 8
241#define S_MARK 16
242
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 */
245
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 */
249
250struct numbers {
251 int refcount;
252 int *numbers; /* sz w+h */
253 int row_s, col_s; /* stations: TODO think about multiple lines
254 (for bigger grids)? */
255};
256
257#define INGRID(state, gx, gy) ((gx) >= 0 && (gx) < (state)->p.w && \
258 (gy) >= 0 && (gy) < (state)->p.h)
259
260struct game_state {
261 game_params p;
262 unsigned int *sflags; /* size w*h */
263 struct numbers *numbers;
264 int *num_errors; /* size w+h */
265 int completed, used_solve, impossible;
266};
267
268/* Return the four directions in which a particular edge flag is set, around a square. */
269int 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;
272}
273
274/* Count the number of a particular edge flag around a grid square. */
275int S_E_COUNT(const game_state *state, int sx, int sy, unsigned int eflag) {
276 return nbits[S_E_DIRS(state, sx, sy, eflag)];
277}
278
279/* Return the two flags (E_TRACK and/or E_NOTRACK) set on a specific
280 * edge of a square. */
281unsigned 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);
285}
286
287int 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; }
292
293 return 0;
294}
295
296/* Sets flag (E_TRACK or E_NOTRACK) on a given edge of a square. */
297void 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;
299 int ax, ay;
300
301 state->sflags[sy*state->p.w+sx] |= (d << shift);
302
303 if (S_E_ADJ(state, sx, sy, d, &ax, &ay, &ad)) {
304 state->sflags[ay*state->p.w+ax] |= (ad << shift);
305 }
306}
307
308/* Clears flag (E_TRACK or E_NOTRACK) on a given edge of a square. */
309void 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;
311 int ax, ay;
312
313 state->sflags[sy*state->p.w+sx] &= ~(d << shift);
314
315 if (S_E_ADJ(state, sx, sy, d, &ax, &ay, &ad)) {
316 state->sflags[ay*state->p.w+ax] &= ~(ad << shift);
317 }
318}
319
320static void clear_game(game_state *state)
321{
322 int w = state->p.w, h = state->p.h;
323
324 memset(state->sflags, 0, w*h * sizeof(unsigned int));
325
326 memset(state->numbers->numbers, 0, (w+h) * sizeof(int));
327 state->numbers->col_s = state->numbers->row_s = -1;
328
329 memset(state->num_errors, 0, (w+h) * sizeof(int));
330
331 state->completed = state->used_solve = state->impossible = FALSE;
332}
333
334static game_state *blank_game(const game_params *params)
335{
336 game_state *state = snew(game_state);
337 int w = params->w, h = params->h;
338
339 state->p = *params;
340
341 state->sflags = snewn(w*h, unsigned int);
342
343 state->numbers = snew(struct numbers);
344 state->numbers->refcount = 1;
345 state->numbers->numbers = snewn(w+h, int);
346
347 state->num_errors = snewn(w+h, int);
348
349 clear_game(state);
350
351 return state;
352}
353
354static void copy_game_flags(const game_state *src, game_state *dest)
355{
356 int w = src->p.w, h = src->p.h;
357
358 memcpy(dest->sflags, src->sflags, w*h*sizeof(unsigned int));
359}
360
361static game_state *dup_game(const game_state *state)
362{
363 int w = state->p.w, h = state->p.h;
364 game_state *ret = snew(game_state);
365
366 ret->p = state->p; /* structure copy */
367
368 ret->sflags = snewn(w*h, unsigned int);
369 copy_game_flags(state, ret);
370
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));
375
376 ret->completed = state->completed;
377 ret->used_solve = state->used_solve;
378 ret->impossible = state->impossible;
379
380 return ret;
381}
382
383static void free_game(game_state *state)
384{
385 if (--state->numbers->refcount <= 0) {
386 sfree(state->numbers->numbers);
387 sfree(state->numbers);
388 }
389 sfree(state->num_errors);
390 sfree(state->sflags);
391 sfree(state);
392}
393
394#define NDIRS 4
395const unsigned int dirs_const[] = { U, D, L, R };
396
397static unsigned int find_direction(game_state *state, random_state *rs,
398 int x, int y)
399{
400 int i, nx, ny, w=state->p.w, h=state->p.h;
401 unsigned int dirs[NDIRS];
402
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. */
410 return dirs[i];
411 } else if (!INGRID(state, nx, ny)) {
412 /* off the board: can't move here */
413 continue;
414 } else if (S_E_COUNT(state, nx, ny, E_TRACK) > 0) {
415 /* already tracks here: can't move */
416 continue;
417 }
418 return dirs[i];
419 }
420 return 0; /* no possible directions left. */
421}
422
423static int check_completion(game_state *state, int mark);
424
425static void lay_path(game_state *state, random_state *rs)
426{
427 int px, py, w=state->p.w, h=state->p.h;
428 unsigned int d;
429
430start:
431 clear_game(state);
432
433 /* pick a random entry point, lay its left edge */
434 state->numbers->row_s = py = random_upto(rs, h);
435 px = 0;
436 S_E_SET(state, px, py, L, E_TRACK);
437
438 while (INGRID(state, px, py)) {
439 d = find_direction(state, rs, px, py);
440 if (d == 0)
441 goto start; /* nowhere else to go, restart */
442
443 S_E_SET(state, px, py, d, E_TRACK);
444 px += DX(d);
445 py += DY(d);
446 }
447 /* double-check we got to the right place */
448 assert(px >= 0 && px < w && py == h);
449
450 state->numbers->col_s = px;
451}
452
453static int tracks_solve(game_state *state, int diff);
454static void debug_state(game_state *state, const char *what);
455
456/* Clue-setting algorithm:
457
458 - first lay clues randomly until it's soluble
459 - then remove clues randomly if removing them doesn't affect solubility
460
461 - We start with two clues, one at each path entrance.
462
463 More details:
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
468 the clue-laying step
469 - count the number of flags the solver managed to place, remember this.
470
471 - to lay clues:
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
481 - go to strip-clues.
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
485 clue position
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.
488
489 - to strip clues:
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
499 clues)
500
501 - that should be it.
502*/
503
504static game_state *copy_and_strip(const game_state *state, game_state *ret, int flipcluei)
505{
506 int i, j, w = state->p.w, h = state->p.h;
507
508 copy_game_flags(state, ret);
509
510 /* Add/remove a clue before stripping, if required */
511
512 if (flipcluei != -1)
513 ret->sflags[flipcluei] ^= S_CLUE;
514
515 /* All squares that are not clue squares have square track info erased, and some edge flags.. */
516
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++) {
521 unsigned f = 1<<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);
527 }
528 }
529 }
530 }
531 return ret;
532}
533
534static int solve_progress(const game_state *state) {
535 int i, w = state->p.w, h = state->p.h, progress = 0;
536
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-
540 solved board. */
541
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);
547 }
548 return progress;
549}
550
551static int check_phantom_moves(const game_state *state) {
552 int x, y, i;
553
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. */
557
558 for (x = 0; x < state->p.w; x++) {
559 for (y = 0; y < state->p.h; y++) {
560 i = y*state->p.w+x;
561 if (state->sflags[i] & S_CLUE)
562 continue;
563 if (S_E_COUNT(state, x, y, E_TRACK) > 1)
564 return 1; /* found one! */
565 }
566 }
567 return 0;
568}
569
570static int add_clues(game_state *state, random_state *rs, int diff)
571{
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);
576
577 debug_state(state, "gen: Initial board");
578
579 debug(("gen: Adding clues..."));
580
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;
586 }
587 nedges_previous_solve[i] = 0;
588 }
589
590 /* First, check whether the puzzle is already either too easy, or just right */
591 scratch = copy_and_strip(state, scratch, -1);
592 if (diff > 0) {
593 sr = tracks_solve(scratch, diff-1);
594 if (sr < 0)
595 assert(!"Generator should not have created impossible puzzle");
596 if (sr > 0) {
597 ret = -1; /* already too easy, even without adding clues. */
598 debug(("gen: ...already too easy, need new board."));
599 goto done;
600 }
601 }
602 sr = tracks_solve(scratch, diff);
603 if (sr < 0)
604 assert(!"Generator should not have created impossible puzzle");
605 if (sr > 0) {
606 ret = 1; /* already soluble without any extra clues. */
607 debug(("gen: ...soluble without clues, nothing to do."));
608 goto done;
609 }
610 debug_state(scratch, "gen: Initial part-solved state: ");
611 progress = solve_progress(scratch);
612 debug(("gen: Initial solve progress is %d", progress));
613
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 */
623
624 /* set a clue in that position (on a copy of the board) and test solubility */
625 scratch = copy_and_strip(state, scratch, i);
626
627 if (check_phantom_moves(scratch))
628 continue; /* adding a clue here would add phantom track */
629
630 if (diff > 0) {
631 if (tracks_solve(scratch, diff-1) > 0) {
632 continue; /* adding a clue here makes it too easy */
633 }
634 }
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;
640 goto strip_clues;
641 }
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;
647
648 for (j = 0; j < w*h; j++)
649 nedges_previous_solve[j] = S_E_COUNT(scratch, j%w, j/w, E_TRACK);
650 }
651 }
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. */
654
655 debug(("gen: Unable to make soluble with clues, need new board."));
656 ret = -1;
657 goto done;
658
659strip_clues:
660 debug(("gen: Stripping clues."));
661
662 /* Now, strip redundant clues (i.e. those without which the puzzle is still
663 soluble) */
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 */
672
673 scratch = copy_and_strip(state, scratch, i);
674 if (check_phantom_moves(scratch))
675 continue; /* removing a clue here would add phantom track */
676
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. */
680 }
681 }
682 debug(("gen: Finished stripping clues."));
683 ret = 1;
684
685done:
686 sfree(positions);
687 free_game(scratch);
688 return ret;
689}
690
691static char *new_game_desc(const game_params *params, random_state *rs,
692 char **aux, int interactive)
693{
694 int i, j, w = params->w, h = params->h, x, y, ret;
695 game_state *state;
696 char *desc, *p;
697 game_params adjusted_params;
698
699 /*
700 * 4x4 Tricky cannot be generated, so fall back to Easy.
701 */
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;
706 }
707
708 state = blank_game(params);
709
710 /* --- lay the random path */
711
712newpath:
713 lay_path(state, rs);
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;
718 }
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;
722 }
723 }
724 }
725
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]++;
732 }
733 }
734 }
735 for (i = 0; i < w+h; i++) {
736 if (state->numbers->numbers[i] == 0)
737 goto newpath; /* too boring */
738 }
739
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;
747 }
748 if (state->numbers->numbers[w+h-1] == 1)
749 goto newpath; /* (disallow 1 clue at exit point) */
750 }
751
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 */
755
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')
761 desc[j-1]++;
762 else if (!(state->sflags[i] & S_CLUE))
763 desc[j++] = 'a';
764 else {
765 unsigned int f = S_E_DIRS(state, i%w, i/w, E_TRACK);
766 desc[j++] = (f < 10) ? ('0' + f) : ('A' + (f-10));
767 }
768 }
769
770 p = desc + j;
771 for (x = 0; x < w; x++) {
772 p += sprintf(p, ",%s%d", x == state->numbers->col_s ? "S" : "",
773 state->numbers->numbers[x]);
774 }
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]);
778 }
779 *p++ = '\0';
780
781 ret = tracks_solve(state, DIFFCOUNT);
782 assert(ret >= 0);
783 free_game(state);
784
785 debug(("new_game_desc: %s", desc));
786 return desc;
787}
788
789static char *validate_desc(const game_params *params, const char *desc)
790{
791 int i = 0, w = params->w, h = params->h, in = 0, out = 0;
792
793 while (*desc) {
794 unsigned int f = 0;
795 if (*desc >= '0' && *desc <= '9')
796 f = (*desc - '0');
797 else if (*desc >= 'A' && *desc <= 'F')
798 f = (*desc - 'A' + 10);
799 else if (*desc >= 'a' && *desc <= 'z')
800 i += *desc - 'a';
801 else
802 return "Game description contained unexpected characters";
803
804 if (f != 0) {
805 if (nbits[f] != 2)
806 return "Clue did not provide 2 direction flags";
807 }
808 i++;
809 desc++;
810 if (i == w*h) break;
811 }
812 for (i = 0; i < w+h; i++) {
813 if (!*desc)
814 return "Not enough numbers given after grid specification";
815 else if (*desc != ',')
816 return "Invalid character in number list";
817 desc++;
818 if (*desc == 'S') {
819 if (i < w)
820 out++;
821 else
822 in++;
823 desc++;
824 }
825 while (*desc && isdigit((unsigned char)*desc)) desc++;
826 }
827 if (in != 1 || out != 1)
828 return "Puzzle must have one entrance and one exit";
829 if (*desc)
830 return "Unexpected additional character at end of game description";
831 return NULL;
832}
833
834static game_state *new_game(midend *me, const game_params *params, const char *desc)
835{
836 game_state *state = blank_game(params);
837 int w = params->w, h = params->h, i = 0;
838
839 while (*desc) {
840 unsigned int f = 0;
841 if (*desc >= '0' && *desc <= '9')
842 f = (*desc - '0');
843 else if (*desc >= 'A' && *desc <= 'F')
844 f = (*desc - 'A' + 10);
845 else if (*desc >= 'a' && *desc <= 'z')
846 i += *desc - 'a';
847
848 if (f != 0) {
849 int x = i % w, y = i / w;
850 assert(f < 16);
851 assert(nbits[f] == 2);
852
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);
858 }
859 i++;
860 desc++;
861 if (i == w*h) break;
862 }
863 for (i = 0; i < w+h; i++) {
864 assert(*desc == ',');
865 desc++;
866
867 if (*desc == 'S') {
868 if (i < w)
869 state->numbers->col_s = i;
870 else
871 state->numbers->row_s = i-w;
872 desc++;
873 }
874 state->numbers->numbers[i] = atoi(desc);
875 while (*desc && isdigit((unsigned char)*desc)) desc++;
876 }
877
878 assert(!*desc);
879
880 return state;
881}
882
883static int solve_set_sflag(game_state *state, int x, int y,
884 unsigned int f, const char *why)
885{
886 int w = state->p.w, i = y*w + x;
887
888 if (state->sflags[i] & f)
889 return 0;
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;
895 }
896 state->sflags[i] |= f;
897 return 1;
898}
899
900static int solve_set_eflag(game_state *state, int x, int y, int d,
901 unsigned int f, const char *why)
902{
903 int sf = S_E_FLAGS(state, x, y, d);
904
905 if (sf & f)
906 return 0;
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;
913 }
914 S_E_SET(state, x, y, d, f);
915 return 1;
916}
917
918static int solve_update_flags(game_state *state)
919{
920 int x, y, i, w = state->p.w, h = state->p.h, did = 0;
921
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");
929 }
930 }
931
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");
935 }
936
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");
940 }
941
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");
952 }
953 }
954 }
955
956 /* If a square is TRACK and 2 edges are TRACK, the other two
957 must be NOTRACK. */
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");
966 }
967 }
968 }
969 }
970 }
971 return did;
972}
973
974static int solve_count_col(game_state *state, int col, unsigned int f)
975{
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++;
979 }
980 return c;
981}
982
983static int solve_count_row(game_state *state, int row, unsigned int f)
984{
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++;
988 }
989 return c;
990}
991
992static int solve_count_clues_sub(game_state *state, int si, int id, int n,
993 int target, const char *what)
994{
995 int ctrack = 0, cnotrack = 0, did = 0, j, i, w = state->p.w;
996
997 for (j = 0, i = si; j < n; j++, i += id) {
998 if (state->sflags[i] & S_TRACK)
999 ctrack++;
1000 if (state->sflags[i] & S_NOTRACK)
1001 cnotrack++;
1002 }
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);
1008 }
1009 }
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);
1015 }
1016 }
1017 return did;
1018}
1019
1020static int solve_count_clues(game_state *state)
1021{
1022 int w = state->p.w, h = state->p.h, x, y, target, did = 0;
1023
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");
1027 }
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");
1031 }
1032 return did;
1033}
1034
1035static int solve_check_single_sub(game_state *state, int si, int id, int n,
1036 int target, unsigned int perpf,
1037 const char *what)
1038{
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;
1042
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. */
1049
1050 for (j = 0, i = si; j < n; j++, i += id) {
1051 if (state->sflags[i] & S_TRACK)
1052 ctrack++;
1053 impossible = S_E_DIRS(state, i%w, i/w, E_NOTRACK);
1054 if ((perpf & impossible) == 0)
1055 nperp++;
1056 if (S_E_COUNT(state, i%w, i/w, E_TRACK) <= 1) {
1057 n1edge++;
1058 i1edge = i;
1059 }
1060 }
1061 if (ctrack != (target-1)) return 0;
1062 if (nperp > 0 || n1edge != 1) return 0;
1063
1064 debug(("check_single from (%d,%d): 1 match from (%d,%d)",
1065 si%w, si/w, i1edge%w, i1edge/w));
1066
1067 /* We have a match: anything that's more than 1 away from this square
1068 cannot now contain a track. */
1069 ox = i1edge%w;
1070 oy = i1edge/w;
1071 for (j = 0, i = si; j < n; j++, i += id) {
1072 x = i%w;
1073 y = i/w;
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);
1077 }
1078 }
1079
1080 return did;
1081}
1082
1083static int solve_check_single(game_state *state)
1084{
1085 int w = state->p.w, h = state->p.h, x, y, target, did = 0;
1086
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");
1090 }
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");
1094 }
1095 return did;
1096}
1097
1098static int solve_check_loose_sub(game_state *state, int si, int id, int n,
1099 int target, unsigned int perpf,
1100 const char *what)
1101{
1102 int nperp = 0, nloose = 0, e2count = 0, did = 0, i, j, k;
1103 int w = state->p.w;
1104 unsigned int parf = ALLDIR & (~perpf);
1105
1106 for (j = 0, i = si; j < n; j++, i += id) {
1107 int fcount = S_E_COUNT(state, i%w, i/w, E_TRACK);
1108 if (fcount == 2)
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 */
1115 }
1116 if (fcount != 2 && !(perpf & S_E_DIRS(state, i%w, i/w, E_NOTRACK)))
1117 nperp++; /* we could lay perpendicular across this cell */
1118 }
1119
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;
1124 }
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 */
1135
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
1140 not already set. */
1141 did += solve_set_eflag(state, i%w, i/w, 1<<k, E_NOTRACK, what);
1142 }
1143 }
1144 }
1145 }
1146 if (nloose == 1 && (target - e2count) == 2 && nperp == 0) {
1147 debug(("check %s from (%d,%d): 1 loose end, 2 empty squares, forcing parallel",
1148 what, si%w, si/w));
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++) {
1153 if (parf & (1<<k))
1154 did += solve_set_eflag(state, i%w, i/w, 1<<k, E_TRACK, what);
1155 }
1156 }
1157 }
1158
1159 return did;
1160}
1161
1162static int solve_check_loose_ends(game_state *state)
1163{
1164 int w = state->p.w, h = state->p.h, x, y, target, did = 0;
1165
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");
1169 }
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");
1173 }
1174 return did;
1175}
1176
1177static int solve_check_loop_sub(game_state *state, int x, int y, int dir,
1178 int *dsf, int startc, int endc)
1179{
1180 int w = state->p.w, h = state->p.h, i = y*w+x, j, k, satisfied = 1;
1181
1182 j = (y+DY(dir))*w + (x+DX(dir));
1183
1184 assert(i < w*h && j < w*h);
1185
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);
1191 if (ic == jc) {
1192 return solve_set_eflag(state, x, y, dir, E_NOTRACK, "would close loop");
1193 }
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
1199 */
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");
1205 }
1206 }
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;
1211 }
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;
1216 }
1217 if (!satisfied) {
1218 return solve_set_eflag(state, x, y, dir, E_NOTRACK,
1219 "joins start to end with incomplete clues");
1220 }
1221 }
1222 }
1223 return 0;
1224}
1225
1226static int solve_check_loop(game_state *state)
1227{
1228 int w = state->p.w, h = state->p.h, x, y, i, j, did = 0;
1229 int *dsf, startc, endc;
1230
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);
1235 dsf_init(dsf, w*h);
1236
1237 /* Work out the connectedness of the current loop set. */
1238 for (x = 0; x < w; x++) {
1239 for (y = 0; y < h; y++) {
1240 i = y*w + x;
1241 if (x < (w-1) && S_E_DIRS(state, x, y, E_TRACK) & R) {
1242 /* connection to the right... */
1243 j = y*w + (x+1);
1244 assert(i < w*h && j < w*h);
1245 dsf_merge(dsf, i, j);
1246 }
1247 if (y < (h-1) && S_E_DIRS(state, x, y, E_TRACK) & D) {
1248 /* connection down... */
1249 j = (y+1)*w + x;
1250 assert(i < w*h && j < w*h);
1251 dsf_merge(dsf, i, j);
1252 }
1253 /* NB no need to check up and left because they'll have been checked
1254 by the other side. */
1255 }
1256 }
1257
1258 startc = dsf_canonify(dsf, state->numbers->row_s*w);
1259 endc = dsf_canonify(dsf, (h-1)*w+state->numbers->col_s);
1260
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++) {
1266 if (x < (w-1))
1267 did += solve_check_loop_sub(state, x, y, R, dsf, startc, endc);
1268 if (y < (h-1))
1269 did += solve_check_loop_sub(state, x, y, D, dsf, startc, endc);
1270 }
1271 }
1272
1273 sfree(dsf);
1274
1275 return did;
1276}
1277
1278static void solve_discount_edge(game_state *state, int x, int y, int d)
1279{
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. */
1283 }
1284 solve_set_eflag(state, x, y, d, E_NOTRACK, "outer edge");
1285}
1286
1287static int tracks_solve(game_state *state, int diff)
1288{
1289 int didsth, x, y, w = state->p.w, h = state->p.h;
1290
1291 debug(("solve..."));
1292 state->impossible = FALSE;
1293
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);
1298 }
1299 for (y = 0; y < h; y++) {
1300 solve_discount_edge(state, 0, y, L);
1301 solve_discount_edge(state, w-1, y, R);
1302 }
1303
1304 while (1) {
1305 didsth = 0;
1306
1307 didsth += solve_update_flags(state);
1308 didsth += solve_count_clues(state);
1309 didsth += solve_check_loop(state);
1310
1311 if (diff >= DIFF_TRICKY) {
1312 didsth += solve_check_single(state);
1313 didsth += solve_check_loose_ends(state);
1314 }
1315
1316 if (!didsth || state->impossible) break;
1317 }
1318
1319 return state->impossible ? -1 : check_completion(state, FALSE) ? 1 : 0;
1320}
1321
1322static char *move_string_diff(const game_state *before, const game_state *after, int issolve)
1323{
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;
1328
1329 if (issolve) {
1330 *p++ = 'S';
1331 sep = ";";
1332 }
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);
1338
1339 for (j = 0; j < 4; j++) {
1340 unsigned df = 1<<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);
1344 sep = ";";
1345 }
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);
1349 sep = ";";
1350 }
1351 }
1352
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);
1356 sep = ";";
1357 }
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);
1361 sep = ";";
1362 }
1363 }
1364 *p++ = '\0';
1365 move = sresize(move, p - move, char);
1366
1367 return move;
1368}
1369
1370static char *solve_game(const game_state *state, const game_state *currstate,
1371 const char *aux, char **error)
1372{
1373 game_state *solved;
1374 int ret;
1375 char *move;
1376
1377 solved = dup_game(currstate);
1378 ret = tracks_solve(solved, DIFFCOUNT);
1379 if (ret < 1) {
1380 free_game(solved);
1381 solved = dup_game(state);
1382 ret = tracks_solve(solved, DIFFCOUNT);
1383 }
1384
1385 if (ret < 1) {
1386 *error = "Unable to find solution";
1387 move = NULL;
1388 } else {
1389 move = move_string_diff(currstate, solved, TRUE);
1390 }
1391
1392 free_game(solved);
1393 return move;
1394}
1395
1396static int game_can_format_as_text_now(const game_params *params)
1397{
1398 return TRUE;
1399}
1400
1401static char *game_text_format(const game_state *state)
1402{
1403 char *ret, *p;
1404 int x, y, len, w = state->p.w, h = state->p.h;
1405
1406 len = ((w*2) + 4) * ((h*2)+4) + 2;
1407 ret = snewn(len+1, char);
1408 p = ret;
1409
1410 /* top line: column clues */
1411 *p++ = ' ';
1412 *p++ = ' ';
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);
1417 *p++ = ' ';
1418 }
1419 *p++ = '\n';
1420
1421 /* second line: top edge */
1422 *p++ = ' ';
1423 *p++ = '+';
1424 for (x = 0; x < w*2-1; x++)
1425 *p++ = '-';
1426 *p++ = '+';
1427 *p++ = '\n';
1428
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) ? '-' : '|';
1434
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';
1443 else *p++ = ' ';
1444
1445 if (x < w-1) {
1446 *p++ = (f & R) ? '-' : ' ';
1447 } else
1448 *p++ = '|';
1449 }
1450 *p++ = (state->numbers->numbers[w+y] < 10 ?
1451 '0' + state->numbers->numbers[w+y] :
1452 'A' + state->numbers->numbers[w+y] - 10);
1453 *p++ = '\n';
1454
1455 if (y == h-1) continue;
1456
1457 /* edges line */
1458 *p++ = ' ';
1459 *p++ = '|';
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) ? ' ' : '|';
1464 }
1465 *p++ = '\n';
1466 }
1467
1468 /* next line: bottom edge */
1469 *p++ = ' ';
1470 *p++ = '+';
1471 for (x = 0; x < w*2-1; x++)
1472 *p++ = (x == state->numbers->col_s*2) ? '|' : '-';
1473 *p++ = '+';
1474 *p++ = '\n';
1475
1476 /* final line: bottom clue */
1477 *p++ = ' ';
1478 *p++ = ' ';
1479 for (x = 0; x < w*2-1; x++)
1480 *p++ = (x == state->numbers->col_s*2) ? 'B' : ' ';
1481 *p++ = '\n';
1482
1483 *p = '\0';
1484 return ret;
1485}
1486
1487static void debug_state(game_state *state, const char *what) {
1488 char *sstring = game_text_format(state);
1489 debug(("%s: %s", what, sstring));
1490 sfree(sstring);
1491}
1492
1493static void dsf_update_completion(game_state *state, int ax, int ay,
1494 char dir, int *dsf)
1495{
1496 int w = state->p.w, ai = ay*w+ax, bx, by, bi;
1497
1498 if (!(S_E_DIRS(state, ax, ay, E_TRACK) & dir)) return;
1499 bx = ax + DX(dir);
1500 by = ay + DY(dir);
1501
1502 if (!INGRID(state, bx, by)) return;
1503 bi = by*w+bx;
1504
1505 dsf_merge(dsf, ai, bi);
1506}
1507
1508struct tracks_neighbour_ctx {
1509 game_state *state;
1510 int i, n, neighbours[4];
1511};
1512static int tracks_neighbour(int vertex, void *vctx)
1513{
1514 struct tracks_neighbour_ctx *ctx = (struct tracks_neighbour_ctx *)vctx;
1515 if (vertex >= 0) {
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);
1519 int j;
1520
1521 ctx->i = ctx->n = 0;
1522
1523 for (j = 0; j < 4; j++) {
1524 int dir = 1<<j;
1525 if (dirs & dir) {
1526 int nx = x + DX(dir), ny = y + DY(dir);
1527 if (INGRID(state, nx, ny))
1528 ctx->neighbours[ctx->n++] = ny * w + nx;
1529 }
1530 }
1531 }
1532
1533 if (ctx->i < ctx->n)
1534 return ctx->neighbours[ctx->i++];
1535 else
1536 return -1;
1537}
1538
1539static int check_completion(game_state *state, int mark)
1540{
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;
1546
1547 if (mark) {
1548 for (i = 0; i < w+h; i++) {
1549 state->num_errors[i] = 0;
1550 }
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) {
1555 ret = FALSE;
1556 state->sflags[i] |= S_ERROR;
1557 }
1558 }
1559 }
1560 }
1561
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)
1573 ntrack++;
1574 if (S_E_COUNT(state, x, y, E_TRACK) == 2)
1575 ntrackcomplete++;
1576 if (state->sflags[y*w+x] & S_NOTRACK)
1577 nnotrack++;
1578 }
1579 if (mark) {
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;
1584 ret = FALSE;
1585 }
1586 }
1587 if (ntrackcomplete != target)
1588 ret = FALSE;
1589 }
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)
1596 ntrack++;
1597 if (S_E_COUNT(state, x, y, E_TRACK) == 2)
1598 ntrackcomplete++;
1599 if (state->sflags[y*w+x] & S_NOTRACK)
1600 nnotrack++;
1601 }
1602 if (mark) {
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;
1607 ret = FALSE;
1608 }
1609 }
1610 if (ntrackcomplete != target)
1611 ret = FALSE;
1612 }
1613
1614 dsf = snewn(w*h, int);
1615 dsf_init(dsf, w*h);
1616
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);
1621 }
1622 }
1623
1624 fls = findloop_new_state(w*h);
1625 ctx.state = state;
1626 if (findloop_run(fls, w*h, tracks_neighbour, &ctx)) {
1627 debug(("loop detected, not complete"));
1628 ret = FALSE; /* no loop allowed */
1629 if (mark) {
1630 for (x = 0; x < w; x++) {
1631 for (y = 0; y < h; y++) {
1632 int u, v;
1633
1634 u = y*w + x;
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;
1639 }
1640 }
1641 }
1642 }
1643 findloop_free_state(fls);
1644
1645 if (mark) {
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))) {
1654 ret = FALSE;
1655 state->sflags[i] |= S_ERROR;
1656 }
1657 }
1658 } else {
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
1662 * return true. */
1663 ret = FALSE;
1664 }
1665 }
1666
1667 if (mark)
1668 state->completed = ret;
1669 sfree(dsf);
1670 return ret;
1671}
1672
1673/* Code borrowed from Pearl. */
1674
1675struct game_ui {
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 */
1679
1680 int curx, cury; /* grid position of keyboard cursor; uses half-size grid */
1681 int cursor_active; /* TRUE iff cursor is shown */
1682};
1683
1684static game_ui *new_ui(const game_state *state)
1685{
1686 game_ui *ui = snew(game_ui);
1687
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;
1692
1693 return ui;
1694}
1695
1696static void free_ui(game_ui *ui)
1697{
1698 sfree(ui);
1699}
1700
1701static char *encode_ui(const game_ui *ui)
1702{
1703 return NULL;
1704}
1705
1706static void decode_ui(game_ui *ui, const char *encoding)
1707{
1708}
1709
1710static void game_changed_state(game_ui *ui, const game_state *oldstate,
1711 const game_state *newstate)
1712{
1713}
1714
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)
1719
1720#define BORDER (TILE_SIZE/8)
1721#define BORDER_WIDTH (max(TILE_SIZE / 32, 1))
1722
1723#define COORD(x) ( (x+1) * TILE_SIZE + BORDER )
1724#define CENTERED_COORD(x) ( COORD(x) + TILE_SIZE/2 )
1725#define FROMCOORD(x) ( ((x) < BORDER) ? -1 : ( ((x) - BORDER) / TILE_SIZE) - 1 )
1726
1727#define DS_DSHIFT 4 /* R/U/L/D shift, for drag-in-progress flags */
1728
1729#define DS_ERROR (1 << 8)
1730#define DS_CLUE (1 << 9)
1731#define DS_NOTRACK (1 << 10)
1732#define DS_FLASH (1 << 11)
1733#define DS_CURSOR (1 << 12) /* cursor in square (centre, or on edge) */
1734#define DS_TRACK (1 << 13)
1735#define DS_CLEARING (1 << 14)
1736
1737#define DS_NSHIFT 16 /* R/U/L/D shift, for no-track edge flags */
1738#define DS_CSHIFT 20 /* R/U/L/D shift, for cursor-on-edge */
1739
1740struct game_drawstate {
1741 int sz6;
1742 int started;
1743
1744 int w, h, sz;
1745 unsigned int *flags, *flags_drag;
1746 int *num_errors;
1747};
1748
1749static void update_ui_drag(const game_state *state, game_ui *ui, int gx, int gy)
1750{
1751 int w = state->p.w, h = state->p.h;
1752 int dx = abs(ui->drag_sx - gx), dy = abs(ui->drag_sy - gy);
1753
1754 if (dy == 0) {
1755 ui->drag_ex = gx < 0 ? 0 : gx >= w ? w-1 : gx;
1756 ui->drag_ey = ui->drag_sy;
1757 ui->dragging = TRUE;
1758 } else if (dx == 0) {
1759 ui->drag_ex = ui->drag_sx;
1760 ui->drag_ey = gy < 0 ? 0 : gy >= h ? h-1 : gy;
1761 ui->dragging = TRUE;
1762 } else {
1763 ui->drag_ex = ui->drag_sx;
1764 ui->drag_ey = ui->drag_sy;
1765 ui->dragging = FALSE;
1766 }
1767}
1768
1769static int ui_can_flip_edge(const game_state *state, int x, int y, int dir,
1770 int notrack)
1771{
1772 int w = state->p.w /*, h = state->shared->h, sz = state->shared->sz */;
1773 int x2 = x + DX(dir);
1774 int y2 = y + DY(dir);
1775 unsigned int sf1, sf2, ef;
1776
1777 if (!INGRID(state, x, y) || !INGRID(state, x2, y2))
1778 return FALSE;
1779
1780 sf1 = state->sflags[y*w + x];
1781 sf2 = state->sflags[y2*w + x2];
1782 if ( !notrack && ((sf1 & S_CLUE) || (sf2 & S_CLUE)) )
1783 return FALSE;
1784
1785 ef = S_E_FLAGS(state, x, y, dir);
1786 if (notrack) {
1787 /* if we're going to _set_ NOTRACK (i.e. the flag is currently unset),
1788 make sure the edge is not already set to TRACK. The adjacent squares
1789 could be set to TRACK, because we don't know which edges the general
1790 square setting refers to. */
1791 if (!(ef & E_NOTRACK) && (ef & E_TRACK))
1792 return FALSE;
1793 } else {
1794 if (!(ef & E_TRACK)) {
1795 /* if we're going to _set_ TRACK, make sure neither adjacent square nor
1796 the edge itself is already set to NOTRACK. */
1797 if ((sf1 & S_NOTRACK) || (sf2 & S_NOTRACK) || (ef & E_NOTRACK))
1798 return FALSE;
1799 /* if we're going to _set_ TRACK, make sure neither adjacent square has
1800 2 track flags already. */
1801 if ((S_E_COUNT(state, x, y, E_TRACK) >= 2) ||
1802 (S_E_COUNT(state, x2, y2, E_TRACK) >= 2))
1803 return FALSE;
1804 }
1805 }
1806 return TRUE;
1807}
1808
1809static int ui_can_flip_square(const game_state *state, int x, int y, int notrack)
1810{
1811 int w = state->p.w, trackc;
1812 unsigned sf;
1813
1814 if (!INGRID(state, x, y)) return FALSE;
1815 sf = state->sflags[y*w+x];
1816 trackc = S_E_COUNT(state, x, y, E_TRACK);
1817
1818 if (sf & S_CLUE) return FALSE;
1819
1820 if (notrack) {
1821 /* If we're setting S_NOTRACK, we cannot have either S_TRACK or any E_TRACK. */
1822 if (!(sf & S_NOTRACK) && ((sf & S_TRACK) || (trackc > 0)))
1823 return FALSE;
1824 } else {
1825 /* If we're setting S_TRACK, we cannot have any S_NOTRACK (we could have
1826 E_NOTRACK, though, because one or two wouldn't rule out a track) */
1827 if (!(sf & S_TRACK) && (sf & S_NOTRACK))
1828 return FALSE;
1829 }
1830 return TRUE;
1831}
1832
1833static char *edge_flip_str(const game_state *state, int x, int y, int dir, int notrack, char *buf) {
1834 unsigned ef = S_E_FLAGS(state, x, y, dir);
1835 char c;
1836
1837 if (notrack)
1838 c = (ef & E_NOTRACK) ? 'n' : 'N';
1839 else
1840 c = (ef & E_TRACK) ? 't' : 'T';
1841
1842 sprintf(buf, "%c%c%d,%d", c, MOVECHAR(dir), x, y);
1843 return dupstr(buf);
1844}
1845
1846static char *square_flip_str(const game_state *state, int x, int y, int notrack, char *buf) {
1847 unsigned f = state->sflags[y*state->p.w+x];
1848 char c;
1849
1850 if (notrack)
1851 c = (f & E_NOTRACK) ? 'n' : 'N';
1852 else
1853 c = (f & E_TRACK) ? 't' : 'T';
1854
1855 sprintf(buf, "%cS%d,%d", c, x, y);
1856 return dupstr(buf);
1857}
1858
1859#define SIGN(x) ((x<0) ? -1 : (x>0))
1860
1861static game_state *copy_and_apply_drag(const game_state *state, const game_ui *ui)
1862{
1863 game_state *after = dup_game(state);
1864 int x1, y1, x2, y2, x, y, w = state->p.w;
1865 unsigned f = ui->notrack ? S_NOTRACK : S_TRACK, ff;
1866
1867 x1 = min(ui->drag_sx, ui->drag_ex); x2 = max(ui->drag_sx, ui->drag_ex);
1868 y1 = min(ui->drag_sy, ui->drag_ey); y2 = max(ui->drag_sy, ui->drag_ey);
1869
1870 /* actually either x1 == x2, or y1 == y2, but it's easier just to code
1871 the nested loop. */
1872 for (x = x1; x <= x2; x++) {
1873 for (y = y1; y <= y2; y++) {
1874 ff = state->sflags[y*w+x];
1875 if (ui->clearing && !(ff & f))
1876 continue; /* nothing to do, clearing and already clear */
1877 else if (!ui->clearing && (ff & f))
1878 continue; /* nothing to do, setting and already set */
1879 else if (ui_can_flip_square(state, x, y, ui->notrack))
1880 after->sflags[y*w+x] ^= f;
1881 }
1882 }
1883 return after;
1884}
1885
1886#define KEY_DIRECTION(btn) (\
1887 (btn) == CURSOR_DOWN ? D : (btn) == CURSOR_UP ? U :\
1888 (btn) == CURSOR_LEFT ? L : R)
1889
1890static char *interpret_move(const game_state *state, game_ui *ui,
1891 const game_drawstate *ds,
1892 int x, int y, int button)
1893{
1894 int w = state->p.w, h = state->p.h, direction;
1895 int gx = FROMCOORD(x), gy = FROMCOORD(y);
1896 char tmpbuf[80];
1897
1898 /* --- mouse operations --- */
1899
1900 if (IS_MOUSE_DOWN(button)) {
1901 ui->cursor_active = FALSE;
1902 ui->dragging = FALSE;
1903
1904 if (!INGRID(state, gx, gy)) {
1905 /* can't drag from off grid */
1906 return NULL;
1907 }
1908
1909 if (button == RIGHT_BUTTON) {
1910 ui->notrack = TRUE;
1911 ui->clearing = state->sflags[gy*w+gx] & S_NOTRACK;
1912 } else {
1913 ui->notrack = FALSE;
1914 ui->clearing = state->sflags[gy*w+gx] & S_TRACK;
1915 }
1916
1917 ui->clickx = x;
1918 ui->clicky = y;
1919 ui->drag_sx = ui->drag_ex = gx;
1920 ui->drag_sy = ui->drag_ey = gy;
1921
1922 return "";
1923 }
1924
1925 if (IS_MOUSE_DRAG(button)) {
1926 ui->cursor_active = FALSE;
1927 update_ui_drag(state, ui, gx, gy);
1928 return "";
1929 }
1930
1931 if (IS_MOUSE_RELEASE(button)) {
1932 ui->cursor_active = FALSE;
1933 if (ui->dragging &&
1934 (ui->drag_sx != ui->drag_ex || ui->drag_sy != ui->drag_ey)) {
1935 game_state *dragged = copy_and_apply_drag(state, ui);
1936 char *ret = move_string_diff(state, dragged, FALSE);
1937
1938 ui->dragging = 0;
1939 free_game(dragged);
1940
1941 return ret;
1942 } else {
1943 int cx, cy;
1944
1945 /* We might still have been dragging (and just done a one-
1946 * square drag): cancel drag, so undo doesn't make it like
1947 * a drag-in-progress. */
1948 ui->dragging = 0;
1949
1950 /* Click (or tiny drag). Work out which edge we were
1951 * closest to. */
1952
1953 /*
1954 * We process clicks based on the mouse-down location,
1955 * because that's more natural for a user to carefully
1956 * control than the mouse-up.
1957 */
1958 x = ui->clickx;
1959 y = ui->clicky;
1960
1961 cx = CENTERED_COORD(gx);
1962 cy = CENTERED_COORD(gy);
1963
1964 if (!INGRID(state, gx, gy) || FROMCOORD(x) != gx || FROMCOORD(y) != gy)
1965 return "";
1966
1967 if (max(abs(x-cx),abs(y-cy)) < TILE_SIZE/4) {
1968 if (ui_can_flip_square(state, gx, gy, button == RIGHT_RELEASE))
1969 return square_flip_str(state, gx, gy, button == RIGHT_RELEASE, tmpbuf);
1970 return "";
1971 } else {
1972 if (abs(x-cx) < abs(y-cy)) {
1973 /* Closest to top/bottom edge. */
1974 direction = (y < cy) ? U : D;
1975 } else {
1976 /* Closest to left/right edge. */
1977 direction = (x < cx) ? L : R;
1978 }
1979 if (ui_can_flip_edge(state, gx, gy, direction,
1980 button == RIGHT_RELEASE))
1981 return edge_flip_str(state, gx, gy, direction,
1982 button == RIGHT_RELEASE, tmpbuf);
1983 else
1984 return "";
1985 }
1986 }
1987 }
1988
1989 /* --- cursor/keyboard operations --- */
1990
1991 if (IS_CURSOR_MOVE(button)) {
1992 int dx = (button == CURSOR_LEFT) ? -1 : ((button == CURSOR_RIGHT) ? +1 : 0);
1993 int dy = (button == CURSOR_DOWN) ? +1 : ((button == CURSOR_UP) ? -1 : 0);
1994
1995 if (!ui->cursor_active) {
1996 ui->cursor_active = TRUE;
1997 return "";
1998 }
1999
2000 ui->curx = ui->curx + dx;
2001 ui->cury = ui->cury + dy;
2002 if ((ui->curx % 2 == 0) && (ui->cury % 2 == 0)) {
2003 /* disallow cursor on square corners: centres and edges only */
2004 ui->curx += dx; ui->cury += dy;
2005 }
2006 ui->curx = min(max(ui->curx, 1), 2*w-1);
2007 ui->cury = min(max(ui->cury, 1), 2*h-1);
2008 return "";
2009 }
2010
2011 if (IS_CURSOR_SELECT(button)) {
2012 if (!ui->cursor_active) {
2013 ui->cursor_active = TRUE;
2014 return "";
2015 }
2016 /* click on square corner does nothing (shouldn't get here) */
2017 if ((ui->curx % 2) == 0 && (ui->cury % 2 == 0))
2018 return "";
2019
2020 gx = ui->curx / 2;
2021 gy = ui->cury / 2;
2022 direction = ((ui->curx % 2) == 0) ? L : ((ui->cury % 2) == 0) ? U : 0;
2023
2024 if (direction &&
2025 ui_can_flip_edge(state, gx, gy, direction, button == CURSOR_SELECT2))
2026 return edge_flip_str(state, gx, gy, direction, button == CURSOR_SELECT2, tmpbuf);
2027 else if (!direction &&
2028 ui_can_flip_square(state, gx, gy, button == CURSOR_SELECT2))
2029 return square_flip_str(state, gx, gy, button == CURSOR_SELECT2, tmpbuf);
2030 return "";
2031 }
2032
2033#if 0
2034 /* helps to debug the solver */
2035 if (button == 'H' || button == 'h')
2036 return dupstr("H");
2037#endif
2038
2039 return NULL;
2040}
2041
2042static game_state *execute_move(const game_state *state, const char *move)
2043{
2044 int w = state->p.w, x, y, n, i;
2045 char c, d;
2046 unsigned f;
2047 game_state *ret = dup_game(state);
2048
2049 /* this is breaking the bank on GTK, which vsprintf's into a fixed-size buffer
2050 * which is 4096 bytes long. vsnprintf needs a feature-test macro to use, faff. */
2051 /*debug(("move: %s\n", move));*/
2052
2053 while (*move) {
2054 c = *move;
2055 if (c == 'S') {
2056 ret->used_solve = TRUE;
2057 move++;
2058 } else if (c == 'T' || c == 't' || c == 'N' || c == 'n') {
2059 /* set track, clear track; set notrack, clear notrack */
2060 move++;
2061 if (sscanf(move, "%c%d,%d%n", &d, &x, &y, &n) != 3)
2062 goto badmove;
2063 if (!INGRID(state, x, y)) goto badmove;
2064
2065 f = (c == 'T' || c == 't') ? S_TRACK : S_NOTRACK;
2066
2067 if (d == 'S') {
2068 if (c == 'T' || c == 'N')
2069 ret->sflags[y*w+x] |= f;
2070 else
2071 ret->sflags[y*w+x] &= ~f;
2072 } else if (d == 'U' || d == 'D' || d == 'L' || d == 'R') {
2073 for (i = 0; i < 4; i++) {
2074 unsigned df = 1<<i;
2075
2076 if (MOVECHAR(df) == d) {
2077 if (c == 'T' || c == 'N')
2078 S_E_SET(ret, x, y, df, f);
2079 else
2080 S_E_CLEAR(ret, x, y, df, f);
2081 }
2082 }
2083 } else
2084 goto badmove;
2085 move += n;
2086 } else if (c == 'H') {
2087 tracks_solve(ret, DIFFCOUNT);
2088 move++;
2089 } else {
2090 goto badmove;
2091 }
2092 if (*move == ';')
2093 move++;
2094 else if (*move)
2095 goto badmove;
2096 }
2097
2098 check_completion(ret, TRUE);
2099
2100 return ret;
2101
2102 badmove:
2103 free_game(ret);
2104 return NULL;
2105}
2106
2107/* ----------------------------------------------------------------------
2108 * Drawing routines.
2109 */
2110
2111#define FLASH_TIME 0.5F
2112
2113static void game_compute_size(const game_params *params, int tilesize,
2114 int *x, int *y)
2115{
2116 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
2117 struct {
2118 int sz6;
2119 } ads, *ds = &ads;
2120 ads.sz6 = tilesize/6;
2121
2122 *x = (params->w+2) * TILE_SIZE + 2 * BORDER;
2123 *y = (params->h+2) * TILE_SIZE + 2 * BORDER;
2124}
2125
2126static void game_set_size(drawing *dr, game_drawstate *ds,
2127 const game_params *params, int tilesize)
2128{
2129 ds->sz6 = tilesize/6;
2130}
2131
2132enum {
2133 COL_BACKGROUND, COL_LOWLIGHT, COL_HIGHLIGHT,
2134 COL_TRACK_BACKGROUND = COL_LOWLIGHT,
2135 COL_GRID, COL_CLUE, COL_CURSOR,
2136 COL_TRACK, COL_TRACK_CLUE, COL_SLEEPER,
2137 COL_DRAGON, COL_DRAGOFF,
2138 COL_ERROR, COL_FLASH,
2139 NCOLOURS
2140};
2141
2142static float *game_colours(frontend *fe, int *ncolours)
2143{
2144 float *ret = snewn(3 * NCOLOURS, float);
2145 int i;
2146
2147 game_mkhighlight(fe, ret, COL_BACKGROUND, COL_HIGHLIGHT, COL_LOWLIGHT);
2148
2149 for (i = 0; i < 3; i++) {
2150 ret[COL_TRACK_CLUE * 3 + i] = 0.0F;
2151 ret[COL_TRACK * 3 + i] = 0.5F;
2152 ret[COL_CLUE * 3 + i] = 0.0F;
2153 ret[COL_GRID * 3 + i] = 0.75F;
2154 ret[COL_CURSOR * 3 + i] = 0.6F;
2155 }
2156
2157 ret[COL_SLEEPER * 3 + 0] = 0.5F;
2158 ret[COL_SLEEPER * 3 + 1] = 0.4F;
2159 ret[COL_SLEEPER * 3 + 2] = 0.1F;
2160
2161 ret[COL_ERROR * 3 + 0] = 1.0F;
2162 ret[COL_ERROR * 3 + 1] = 0.0F;
2163 ret[COL_ERROR * 3 + 2] = 0.0F;
2164
2165 ret[COL_DRAGON * 3 + 0] = 0.0F;
2166 ret[COL_DRAGON * 3 + 1] = 0.0F;
2167 ret[COL_DRAGON * 3 + 2] = 1.0F;
2168
2169 ret[COL_DRAGOFF * 3 + 0] = 0.8F;
2170 ret[COL_DRAGOFF * 3 + 1] = 0.8F;
2171 ret[COL_DRAGOFF * 3 + 2] = 1.0F;
2172
2173 ret[COL_FLASH * 3 + 0] = 1.0F;
2174 ret[COL_FLASH * 3 + 1] = 1.0F;
2175 ret[COL_FLASH * 3 + 2] = 1.0F;
2176
2177 *ncolours = NCOLOURS;
2178 return ret;
2179}
2180
2181static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state)
2182{
2183 struct game_drawstate *ds = snew(struct game_drawstate);
2184 int i;
2185
2186 ds->sz6 = 0;
2187 ds->started = FALSE;
2188
2189 ds->w = state->p.w;
2190 ds->h = state->p.h;
2191 ds->sz = ds->w*ds->h;
2192 ds->flags = snewn(ds->sz, unsigned int);
2193 ds->flags_drag = snewn(ds->sz, unsigned int);
2194 for (i = 0; i < ds->sz; i++)
2195 ds->flags[i] = ds->flags_drag[i] = 0;
2196
2197 ds->num_errors = snewn(ds->w+ds->h, int);
2198 for (i = 0; i < ds->w+ds->h; i++)
2199 ds->num_errors[i] = 0;
2200
2201 return ds;
2202}
2203
2204static void game_free_drawstate(drawing *dr, game_drawstate *ds)
2205{
2206 sfree(ds->flags);
2207 sfree(ds->flags_drag);
2208 sfree(ds->num_errors);
2209 sfree(ds);
2210}
2211
2212static void draw_circle_sleepers(drawing *dr, game_drawstate *ds,
2213 float cx, float cy, float r2, float thickness, int c)
2214{
2215 float qr6 = (float)PI/12, qr3 = (float)PI/6, th, x1, y1, x2, y2;
2216 float t6 = THIRDSZ/2.0F, r1 = t6;
2217 int i;
2218
2219 for (i = 0; i < 12; i++) {
2220 th = qr6 + (i*qr3);
2221 x1 = r1*(float)cos(th);
2222 x2 = r2*(float)cos(th);
2223 y1 = r1*(float)sin(th);
2224 y2 = r2*(float)sin(th);
2225 draw_thick_line(dr, thickness, cx+x1, cy+y1, cx+x2, cy+y2, c);
2226 }
2227}
2228
2229static void draw_thick_circle_outline(drawing *dr, float thickness,
2230 float cx, float cy, float r,
2231 int colour)
2232{
2233 float circ4 = 0.5F * (float)PI * r, ang, x1, y1, x2, y2;
2234 int i, nseg;
2235
2236 nseg = (int)(circ4 / 4.0F)*4; /* ensure a quarter-circle has a whole #segs */
2237 ang = 2.0F*(float)PI / nseg;
2238
2239 for (i = 0; i < nseg; i++) {
2240 float th = ang * i, th2 = ang * (i+1);
2241 x1 = cx + r*(float)cos(th);
2242 x2 = cx + r*(float)cos(th2);
2243 y1 = cy + r*(float)sin(th);
2244 y2 = cy + r*(float)sin(th2);
2245 debug(("circ outline: x=%.2f -> %.2f, thick=%.2f", x1, x2, thickness));
2246 draw_thick_line(dr, thickness, x1, y1, x2, y2, colour);
2247 }
2248}
2249
2250static void draw_tracks_specific(drawing *dr, game_drawstate *ds,
2251 int x, int y, unsigned int flags,
2252 int ctrack, int csleeper)
2253{
2254 float ox = (float)COORD(x), oy = (float)COORD(y), cx, cy;
2255 float t1 = (float)TILE_SIZE, t3 = TILE_SIZE/3.0F, t6 = TILE_SIZE/6.0F;
2256 int d, i;
2257 float thick_track = TILE_SIZE/8.0F, thick_sleeper = TILE_SIZE/12.0F;
2258
2259 if (flags == LR) {
2260 for (i = 1; i <= 7; i+=2) {
2261 cx = ox + TILE_SIZE/8.0F*i;
2262 draw_thick_line(dr, thick_sleeper,
2263 cx, oy+t6, cx, oy+t6+2*t3, csleeper);
2264 }
2265 draw_thick_line(dr, thick_track, ox, oy + t3, ox + TILE_SIZE, oy + t3, ctrack);
2266 draw_thick_line(dr, thick_track, ox, oy + 2*t3, ox + TILE_SIZE, oy + 2*t3, ctrack);
2267 return;
2268 }
2269 if (flags == UD) {
2270 for (i = 1; i <= 7; i+=2) {
2271 cy = oy + TILE_SIZE/8.0F*i;
2272 draw_thick_line(dr, thick_sleeper,
2273 ox+t6, cy, ox+t6+2*t3, cy, csleeper);
2274 }
2275 debug(("vert line: x=%.2f, thick=%.2f", ox + t3, thick_track));
2276 draw_thick_line(dr, thick_track, ox + t3, oy, ox + t3, oy + TILE_SIZE, ctrack);
2277 draw_thick_line(dr, thick_track, ox + 2*t3, oy, ox + 2*t3, oy + TILE_SIZE, ctrack);
2278 return;
2279 }
2280 if (flags == UL || flags == DL || flags == UR || flags == DR) {
2281 cx = (flags & L) ? ox : ox + TILE_SIZE;
2282 cy = (flags & U) ? oy : oy + TILE_SIZE;
2283
2284 draw_circle_sleepers(dr, ds, cx, cy, (float)(5*t6), thick_sleeper, csleeper);
2285
2286 draw_thick_circle_outline(dr, thick_track, (float)cx, (float)cy,
2287 2*t3, ctrack);
2288 draw_thick_circle_outline(dr, thick_track, (float)cx, (float)cy,
2289 t3, ctrack);
2290
2291 return;
2292 }
2293
2294 for (d = 1; d < 16; d *= 2) {
2295 float ox1 = 0, ox2 = 0, oy1 = 0, oy2 = 0;
2296
2297 if (!(flags & d)) continue;
2298
2299 for (i = 1; i <= 2; i++) {
2300 if (d == L) {
2301 ox1 = 0;
2302 ox2 = thick_track;
2303 oy1 = oy2 = i*t3;
2304 } else if (d == R) {
2305 ox1 = t1;
2306 ox2 = t1 - thick_track;
2307 oy1 = oy2 = i*t3;
2308 } else if (d == U) {
2309 ox1 = ox2 = i*t3;
2310 oy1 = 0;
2311 oy2 = thick_track;
2312 } else if (d == D) {
2313 ox1 = ox2 = i*t3;
2314 oy1 = t1;
2315 oy2 = t1 - thick_track;
2316 }
2317 draw_thick_line(dr, thick_track, ox+ox1, oy+oy1, ox+ox2, oy+oy2, ctrack);
2318 }
2319 }
2320}
2321
2322static unsigned int best_bits(unsigned int flags, unsigned int flags_drag, int *col)
2323{
2324 int nb_orig = nbits[flags & ALLDIR], nb_drag = nbits[flags_drag & ALLDIR];
2325
2326 if (nb_orig > nb_drag) {
2327 *col = COL_DRAGOFF;
2328 return flags & ALLDIR;
2329 } else if (nb_orig < nb_drag) {
2330 *col = COL_DRAGON;
2331 return flags_drag & ALLDIR;
2332 }
2333 return flags & ALLDIR; /* same number of bits: no special colour. */
2334}
2335
2336static void draw_square(drawing *dr, game_drawstate *ds,
2337 int x, int y, unsigned int flags, unsigned int flags_drag)
2338{
2339 int t2 = HALFSZ, t16 = HALFSZ/4, off;
2340 int ox = COORD(x), oy = COORD(y), cx = ox + t2, cy = oy + t2, d, c;
2341 int bg = (flags & DS_TRACK) ? COL_TRACK_BACKGROUND : COL_BACKGROUND;
2342 unsigned int flags_best;
2343
2344 assert(dr);
2345
2346 /* Clip to the grid square. */
2347 clip(dr, ox, oy, TILE_SIZE, TILE_SIZE);
2348
2349 /* Clear the square. */
2350 best_bits((flags & DS_TRACK) == DS_TRACK,
2351 (flags_drag & DS_TRACK) == DS_TRACK, &bg);
2352 draw_rect(dr, ox, oy, TILE_SIZE, TILE_SIZE, bg);
2353
2354 /* Draw outline of grid square */
2355 draw_line(dr, ox, oy, COORD(x+1), oy, COL_GRID);
2356 draw_line(dr, ox, oy, ox, COORD(y+1), COL_GRID);
2357
2358 /* More outlines for clue squares. */
2359 if (flags & DS_CURSOR) {
2360 int curx, cury, curw, curh;
2361
2362 off = t16;
2363 curx = ox + off; cury = oy + off;
2364 curw = curh = TILE_SIZE - (2*off) + 1;
2365
2366 if (flags & (U << DS_CSHIFT)) {
2367 cury = oy - off; curh = 2*off + 1;
2368 } else if (flags & (D << DS_CSHIFT)) {
2369 cury = oy + TILE_SIZE - off; curh = 2*off + 1;
2370 } else if (flags & (L << DS_CSHIFT)) {
2371 curx = ox - off; curw = 2*off + 1;
2372 } else if (flags & (R << DS_CSHIFT)) {
2373 curx = ox + TILE_SIZE - off; curw = 2*off + 1;
2374 }
2375
2376 draw_rect_outline(dr, curx, cury, curw, curh, COL_GRID);
2377 }
2378
2379 /* Draw tracks themselves */
2380 c = (flags & DS_ERROR) ? COL_ERROR :
2381 (flags & DS_FLASH) ? COL_FLASH :
2382 (flags & DS_CLUE) ? COL_TRACK_CLUE : COL_TRACK;
2383 flags_best = best_bits(flags, flags_drag, &c);
2384 draw_tracks_specific(dr, ds, x, y, flags_best, c, COL_SLEEPER);
2385
2386 /* Draw no-track marks, if present, in square and on edges. */
2387 c = COL_TRACK;
2388 flags_best = best_bits((flags & DS_NOTRACK) == DS_NOTRACK,
2389 (flags_drag & DS_NOTRACK) == DS_NOTRACK, &c);
2390 if (flags_best) {
2391 off = HALFSZ/2;
2392 draw_line(dr, cx - off, cy - off, cx + off, cy + off, c);
2393 draw_line(dr, cx - off, cy + off, cx + off, cy - off, c);
2394 }
2395
2396 c = COL_TRACK;
2397 flags_best = best_bits(flags >> DS_NSHIFT, flags_drag >> DS_NSHIFT, &c);
2398 for (d = 1; d < 16; d *= 2) {
2399 off = t16;
2400 cx = ox + t2;
2401 cy = oy + t2;
2402
2403 if (flags_best & d) {
2404 cx += (d == R) ? t2 : (d == L) ? -t2 : 0;
2405 cy += (d == D) ? t2 : (d == U) ? -t2 : 0;
2406
2407 draw_line(dr, cx - off, cy - off, cx + off, cy + off, c);
2408 draw_line(dr, cx - off, cy + off, cx + off, cy - off, c);
2409 }
2410 }
2411
2412 unclip(dr);
2413 draw_update(dr, ox, oy, TILE_SIZE, TILE_SIZE);
2414}
2415
2416static void draw_clue(drawing *dr, game_drawstate *ds, int w, int clue, int i, int col)
2417{
2418 int cx, cy, tsz = TILE_SIZE/2;
2419 char buf[20];
2420
2421 if (i < w) {
2422 cx = CENTERED_COORD(i);
2423 cy = CENTERED_COORD(-1);
2424 } else {
2425 cx = CENTERED_COORD(w);
2426 cy = CENTERED_COORD(i-w);
2427 }
2428
2429 draw_rect(dr, cx - tsz + BORDER, cy - tsz + BORDER,
2430 TILE_SIZE - BORDER, TILE_SIZE - BORDER, COL_BACKGROUND);
2431 sprintf(buf, "%d", clue);
2432 draw_text(dr, cx, cy, FONT_VARIABLE, tsz, ALIGN_VCENTRE|ALIGN_HCENTRE,
2433 col, buf);
2434 draw_update(dr, cx - tsz, cy - tsz, TILE_SIZE, TILE_SIZE);
2435}
2436
2437static void draw_loop_ends(drawing *dr, game_drawstate *ds,
2438 const game_state *state, int c)
2439{
2440 int tsz = TILE_SIZE/2;
2441
2442 draw_text(dr, CENTERED_COORD(-1), CENTERED_COORD(state->numbers->row_s),
2443 FONT_VARIABLE, tsz, ALIGN_VCENTRE|ALIGN_HCENTRE,
2444 c, "A");
2445
2446 draw_text(dr, CENTERED_COORD(state->numbers->col_s), CENTERED_COORD(state->p.h),
2447 FONT_VARIABLE, tsz, ALIGN_VCENTRE|ALIGN_HCENTRE,
2448 c, "B");
2449}
2450
2451static unsigned int s2d_flags(const game_state *state, int x, int y, const game_ui *ui)
2452{
2453 unsigned int f;
2454 int w = state->p.w;
2455
2456 f = S_E_DIRS(state, x, y, E_TRACK);
2457 f |= (S_E_DIRS(state, x, y, E_NOTRACK) << DS_NSHIFT);
2458
2459 if (state->sflags[y*w+x] & S_ERROR)
2460 f |= DS_ERROR;
2461 if (state->sflags[y*w+x] & S_CLUE)
2462 f |= DS_CLUE;
2463 if (state->sflags[y*w+x] & S_NOTRACK)
2464 f |= DS_NOTRACK;
2465 if ((state->sflags[y*w+x] & S_TRACK) || (S_E_COUNT(state, x, y, E_TRACK) > 0))
2466 f |= DS_TRACK;
2467
2468 if (ui->cursor_active) {
2469 if (ui->curx >= x*2 && ui->curx <= (x+1)*2 &&
2470 ui->cury >= y*2 && ui->cury <= (y+1)*2) {
2471 f |= DS_CURSOR;
2472 if (ui->curx == x*2) f |= (L << DS_CSHIFT);
2473 if (ui->curx == (x+1)*2) f |= (R << DS_CSHIFT);
2474 if (ui->cury == y*2) f |= (U << DS_CSHIFT);
2475 if (ui->cury == (y+1)*2) f |= (D << DS_CSHIFT);
2476 }
2477 }
2478
2479 return f;
2480}
2481
2482static void game_redraw(drawing *dr, game_drawstate *ds, const game_state *oldstate,
2483 const game_state *state, int dir, const game_ui *ui,
2484 float animtime, float flashtime)
2485{
2486 int i, x, y, force = 0, flashing = 0, w = ds->w, h = ds->h;
2487 game_state *drag_state = NULL;
2488
2489 if (!ds->started) {
2490 /*
2491 * The initial contents of the window are not guaranteed and
2492 * can vary with front ends. To be on the safe side, all games
2493 * should start by drawing a big background-colour rectangle
2494 * covering the whole window.
2495 */
2496 draw_rect(dr, 0, 0, (w+2)*TILE_SIZE + 2*BORDER, (h+2)*TILE_SIZE + 2*BORDER,
2497 COL_BACKGROUND);
2498
2499 draw_loop_ends(dr, ds, state, COL_CLUE);
2500
2501 draw_line(dr, COORD(ds->w), COORD(0), COORD(ds->w), COORD(ds->h), COL_GRID);
2502 draw_line(dr, COORD(0), COORD(ds->h), COORD(ds->w), COORD(ds->h), COL_GRID);
2503
2504 draw_update(dr, 0, 0, (w+2)*TILE_SIZE + 2*BORDER, (h+2)*TILE_SIZE + 2*BORDER);
2505
2506 ds->started = TRUE;
2507 force = 1;
2508 }
2509
2510 for (i = 0; i < w+h; i++) {
2511 if (force || (state->num_errors[i] != ds->num_errors[i])) {
2512 ds->num_errors[i] = state->num_errors[i];
2513 draw_clue(dr, ds, w, state->numbers->numbers[i], i,
2514 ds->num_errors[i] ? COL_ERROR : COL_CLUE);
2515 }
2516 }
2517
2518 if (flashtime > 0 &&
2519 (flashtime <= FLASH_TIME/3 ||
2520 flashtime >= FLASH_TIME*2/3))
2521 flashing = DS_FLASH;
2522
2523 if (ui->dragging)
2524 drag_state = copy_and_apply_drag(state, ui);
2525
2526 for (x = 0; x < w; x++) {
2527 for (y = 0; y < h; y++) {
2528 unsigned int f, f_d;
2529
2530 f = s2d_flags(state, x, y, ui) | flashing;
2531 f_d = drag_state ? s2d_flags(drag_state, x, y, ui) : f;
2532
2533 if (f != ds->flags[y*w+x] || f_d != ds->flags_drag[y*w+x] || force) {
2534 ds->flags[y*w+x] = f;
2535 ds->flags_drag[y*w+x] = f_d;
2536 draw_square(dr, ds, x, y, f, f_d);
2537 }
2538 }
2539 }
2540
2541 if (drag_state) free_game(drag_state);
2542}
2543
2544static float game_anim_length(const game_state *oldstate, const game_state *newstate,
2545 int dir, game_ui *ui)
2546{
2547 return 0.0F;
2548}
2549
2550static float game_flash_length(const game_state *oldstate, const game_state *newstate,
2551 int dir, game_ui *ui)
2552{
2553 if (!oldstate->completed &&
2554 newstate->completed && !newstate->used_solve)
2555 return FLASH_TIME;
2556 else
2557 return 0.0F;
2558}
2559
2560static int game_status(const game_state *state)
2561{
2562 return state->completed ? +1 : 0;
2563}
2564
2565static int game_timing_state(const game_state *state, game_ui *ui)
2566{
2567 return TRUE;
2568}
2569
2570static void game_print_size(const game_params *params, float *x, float *y)
2571{
2572 int pw, ph;
2573
2574 /* The Times uses 7mm squares */
2575 game_compute_size(params, 700, &pw, &ph);
2576 *x = pw / 100.0F;
2577 *y = ph / 100.0F;
2578}
2579
2580static void game_print(drawing *dr, const game_state *state, int tilesize)
2581{
2582 int w = state->p.w, h = state->p.h;
2583 int black = print_mono_colour(dr, 0), grey = print_grey_colour(dr, 0.5F);
2584 int x, y, i;
2585
2586 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
2587 game_drawstate ads, *ds = &ads;
2588 game_set_size(dr, ds, NULL, tilesize);
2589
2590 /* Grid, then border (second so it is on top) */
2591 print_line_width(dr, TILE_SIZE / 24);
2592 for (x = 1; x < w; x++)
2593 draw_line(dr, COORD(x), COORD(0), COORD(x), COORD(h), grey);
2594 for (y = 1; y < h; y++)
2595 draw_line(dr, COORD(0), COORD(y), COORD(w), COORD(y), grey);
2596
2597 print_line_width(dr, TILE_SIZE / 16);
2598 draw_rect_outline(dr, COORD(0), COORD(0), w*TILE_SIZE, h*TILE_SIZE, black);
2599
2600 print_line_width(dr, TILE_SIZE / 24);
2601
2602 /* clue numbers, and loop ends */
2603 for (i = 0; i < w+h; i++)
2604 draw_clue(dr, ds, w, state->numbers->numbers[i], i, black);
2605 draw_loop_ends(dr, ds, state, black);
2606
2607 /* clue tracks / solution */
2608 for (x = 0; x < w; x++) {
2609 for (y = 0; y < h; y++) {
2610 clip(dr, COORD(x), COORD(y), TILE_SIZE, TILE_SIZE);
2611 draw_tracks_specific(dr, ds, x, y, S_E_DIRS(state, x, y, E_TRACK),
2612 black, grey);
2613 unclip(dr);
2614 }
2615 }
2616}
2617
2618#ifdef COMBINED
2619#define thegame tracks
2620#endif
2621
2622const struct game thegame = {
2623 "Train Tracks", "games.tracks", "tracks",
2624 default_params,
2625 game_fetch_preset, NULL,
2626 decode_params,
2627 encode_params,
2628 free_params,
2629 dup_params,
2630 TRUE, game_configure, custom_params,
2631 validate_params,
2632 new_game_desc,
2633 validate_desc,
2634 new_game,
2635 dup_game,
2636 free_game,
2637 TRUE, solve_game,
2638 TRUE, game_can_format_as_text_now, game_text_format,
2639 new_ui,
2640 free_ui,
2641 encode_ui,
2642 decode_ui,
2643 game_changed_state,
2644 interpret_move,
2645 execute_move,
2646 PREFERRED_TILE_SIZE, game_compute_size, game_set_size,
2647 game_colours,
2648 game_new_drawstate,
2649 game_free_drawstate,
2650 game_redraw,
2651 game_anim_length,
2652 game_flash_length,
2653 game_status,
2654 TRUE, FALSE, game_print_size, game_print,
2655 FALSE, /* wants_statusbar */
2656 FALSE, game_timing_state,
2657 0, /* flags */
2658};
2659
2660/* vim: set shiftwidth=4 tabstop=8: */
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-05 14:59:58 +0000