tsiry-sandratraina.com
A modern Music Player Daemon based on Rockbox open source high quality audio player
libadwaita
audio
rust
zig
deno
mpris
rockbox
mpd
1/*
2 * signpost.c: implementation of the janko game 'arrow path'
3 */
4
5#include <stdio.h>
6#include <stdlib.h>
7#include <string.h>
8#include <assert.h>
9#include <ctype.h>
10#include <limits.h>
11#ifdef NO_TGMATH_H
12# include <math.h>
13#else
14# include <tgmath.h>
15#endif
16
17#include "puzzles.h"
18
19#define PREFERRED_TILE_SIZE 48
20#define TILE_SIZE (ds->tilesize)
21#define BLITTER_SIZE TILE_SIZE
22#define BORDER (TILE_SIZE / 2)
23
24#define COORD(x) ( (x) * TILE_SIZE + BORDER )
25#define FROMCOORD(x) ( ((x) - BORDER + TILE_SIZE) / TILE_SIZE - 1 )
26
27#define INGRID(s,x,y) ((x) >= 0 && (x) < (s)->w && (y) >= 0 && (y) < (s)->h)
28
29#define FLASH_SPIN 0.7F
30
31#define NBACKGROUNDS 16
32
33enum {
34 COL_BACKGROUND, COL_HIGHLIGHT, COL_LOWLIGHT,
35 COL_GRID, COL_CURSOR, COL_ERROR, COL_DRAG_ORIGIN,
36 COL_ARROW, COL_ARROW_BG_DIM,
37 COL_NUMBER, COL_NUMBER_SET, COL_NUMBER_SET_MID,
38 COL_B0, /* background colours */
39 COL_M0 = COL_B0 + 1*NBACKGROUNDS, /* mid arrow colours */
40 COL_D0 = COL_B0 + 2*NBACKGROUNDS, /* dim arrow colours */
41 COL_X0 = COL_B0 + 3*NBACKGROUNDS, /* dim arrow colours */
42 NCOLOURS = COL_B0 + 4*NBACKGROUNDS
43};
44
45enum {
46 PREF_FLASH_TYPE,
47 N_PREF_ITEMS
48};
49
50struct game_params {
51 int w, h;
52 bool force_corner_start;
53};
54
55enum { DIR_N = 0, DIR_NE, DIR_E, DIR_SE, DIR_S, DIR_SW, DIR_W, DIR_NW, DIR_MAX };
56static const char *dirstrings[8] = { "N ", "NE", "E ", "SE", "S ", "SW", "W ", "NW" };
57
58static const int dxs[DIR_MAX] = { 0, 1, 1, 1, 0, -1, -1, -1 };
59static const int dys[DIR_MAX] = { -1, -1, 0, 1, 1, 1, 0, -1 };
60
61#define DIR_OPPOSITE(d) ((d+4)%8)
62
63struct game_state {
64 int w, h, n;
65 bool completed, used_solve, impossible;
66 int *dirs; /* direction enums, size n */
67 int *nums; /* numbers, size n */
68 unsigned int *flags; /* flags, size n */
69 int *next, *prev; /* links to other cell indexes, size n (-1 absent) */
70 DSF *dsf; /* connects regions with a dsf. */
71 int *numsi; /* for each number, which index is it in? (-1 absent) */
72};
73
74#define FLAG_IMMUTABLE 1
75#define FLAG_ERROR 2
76
77/* --- Generally useful functions --- */
78
79#define ISREALNUM(state, num) ((num) > 0 && (num) <= (state)->n)
80
81static int whichdir(int fromx, int fromy, int tox, int toy)
82{
83 int i, dx, dy;
84
85 dx = tox - fromx;
86 dy = toy - fromy;
87
88 if (dx && dy && abs(dx) != abs(dy)) return -1;
89
90 if (dx) dx = dx / abs(dx); /* limit to (-1, 0, 1) */
91 if (dy) dy = dy / abs(dy); /* ditto */
92
93 for (i = 0; i < DIR_MAX; i++) {
94 if (dx == dxs[i] && dy == dys[i]) return i;
95 }
96 return -1;
97}
98
99static int whichdiri(game_state *state, int fromi, int toi)
100{
101 int w = state->w;
102 return whichdir(fromi%w, fromi/w, toi%w, toi/w);
103}
104
105static bool ispointing(const game_state *state, int fromx, int fromy,
106 int tox, int toy)
107{
108 int w = state->w, dir = state->dirs[fromy*w+fromx];
109
110 /* (by convention) squares do not point to themselves. */
111 if (fromx == tox && fromy == toy) return false;
112
113 /* the final number points to nothing. */
114 if (state->nums[fromy*w + fromx] == state->n) return false;
115
116 while (1) {
117 if (!INGRID(state, fromx, fromy)) return false;
118 if (fromx == tox && fromy == toy) return true;
119 fromx += dxs[dir]; fromy += dys[dir];
120 }
121 return false; /* not reached */
122}
123
124static bool ispointingi(game_state *state, int fromi, int toi)
125{
126 int w = state->w;
127 return ispointing(state, fromi%w, fromi/w, toi%w, toi/w);
128}
129
130/* Taking the number 'num', work out the gap between it and the next
131 * available number up or down (depending on d). Return true if the
132 * region at (x,y) will fit in that gap. */
133static bool move_couldfit(
134 const game_state *state, int num, int d, int x, int y)
135{
136 int n, gap, i = y*state->w+x, sz;
137
138 assert(d != 0);
139 /* The 'gap' is the number of missing numbers in the grid between
140 * our number and the next one in the sequence (up or down), or
141 * the end of the sequence (if we happen not to have 1/n present) */
142 for (n = num + d, gap = 0;
143 ISREALNUM(state, n) && state->numsi[n] == -1;
144 n += d, gap++) ; /* empty loop */
145
146 if (gap == 0) {
147 /* no gap, so the only allowable move is that that directly
148 * links the two numbers. */
149 n = state->nums[i];
150 return n != num+d;
151 }
152 if (state->prev[i] == -1 && state->next[i] == -1)
153 return true; /* single unconnected square, always OK */
154
155 sz = dsf_size(state->dsf, i);
156 return sz <= gap;
157}
158
159static bool isvalidmove(const game_state *state, bool clever,
160 int fromx, int fromy, int tox, int toy)
161{
162 int w = state->w, from = fromy*w+fromx, to = toy*w+tox;
163 int nfrom, nto;
164
165 if (!INGRID(state, fromx, fromy) || !INGRID(state, tox, toy))
166 return false;
167
168 /* can only move where we point */
169 if (!ispointing(state, fromx, fromy, tox, toy))
170 return false;
171
172 nfrom = state->nums[from]; nto = state->nums[to];
173
174 /* can't move _from_ the preset final number, or _to_ the preset 1. */
175 if (((nfrom == state->n) && (state->flags[from] & FLAG_IMMUTABLE)) ||
176 ((nto == 1) && (state->flags[to] & FLAG_IMMUTABLE)))
177 return false;
178
179 /* can't create a new connection between cells in the same region
180 * as that would create a loop. */
181 if (dsf_equivalent(state->dsf, from, to))
182 return false;
183
184 /* if both cells are actual numbers, can't drag if we're not
185 * one digit apart. */
186 if (ISREALNUM(state, nfrom) && ISREALNUM(state, nto)) {
187 if (nfrom != nto-1)
188 return false;
189 } else if (clever && ISREALNUM(state, nfrom)) {
190 if (!move_couldfit(state, nfrom, +1, tox, toy))
191 return false;
192 } else if (clever && ISREALNUM(state, nto)) {
193 if (!move_couldfit(state, nto, -1, fromx, fromy))
194 return false;
195 }
196
197 return true;
198}
199
200static void makelink(game_state *state, int from, int to)
201{
202 if (state->next[from] != -1)
203 state->prev[state->next[from]] = -1;
204 state->next[from] = to;
205
206 if (state->prev[to] != -1)
207 state->next[state->prev[to]] = -1;
208 state->prev[to] = from;
209}
210
211static bool game_can_format_as_text_now(const game_params *params)
212{
213 if (params->w * params->h >= 100) return false;
214 return true;
215}
216
217static char *game_text_format(const game_state *state)
218{
219 int len = state->h * 2 * (4*state->w + 1) + state->h + 2;
220 int x, y, i, num, n, set;
221 char *ret, *p;
222
223 p = ret = snewn(len, char);
224
225 for (y = 0; y < state->h; y++) {
226 for (x = 0; x < state->h; x++) {
227 i = y*state->w+x;
228 *p++ = dirstrings[state->dirs[i]][0];
229 *p++ = dirstrings[state->dirs[i]][1];
230 *p++ = (state->flags[i] & FLAG_IMMUTABLE) ? 'I' : ' ';
231 *p++ = ' ';
232 }
233 *p++ = '\n';
234 for (x = 0; x < state->h; x++) {
235 i = y*state->w+x;
236 num = state->nums[i];
237 if (num == 0) {
238 *p++ = ' ';
239 *p++ = ' ';
240 *p++ = ' ';
241 } else {
242 n = num % (state->n+1);
243 set = num / (state->n+1);
244
245 assert(n <= 99); /* two digits only! */
246
247 if (set != 0)
248 *p++ = set+'a'-1;
249
250 *p++ = (n >= 10) ? ('0' + (n/10)) : ' ';
251 *p++ = '0' + (n%10);
252
253 if (set == 0)
254 *p++ = ' ';
255 }
256 *p++ = ' ';
257 }
258 *p++ = '\n';
259 *p++ = '\n';
260 }
261 *p++ = '\0';
262
263 return ret;
264}
265
266static void debug_state(const char *desc, game_state *state)
267{
268#ifdef DEBUGGING
269 char *dbg;
270 if (state->n >= 100) {
271 debug(("[ no game_text_format for this size ]"));
272 return;
273 }
274 dbg = game_text_format(state);
275 debug(("%s\n%s", desc, dbg));
276 sfree(dbg);
277#endif
278}
279
280
281static void strip_nums(game_state *state) {
282 int i;
283 for (i = 0; i < state->n; i++) {
284 if (!(state->flags[i] & FLAG_IMMUTABLE))
285 state->nums[i] = 0;
286 }
287 memset(state->next, -1, state->n*sizeof(int));
288 memset(state->prev, -1, state->n*sizeof(int));
289 memset(state->numsi, -1, (state->n+1)*sizeof(int));
290 dsf_reinit(state->dsf);
291}
292
293static bool check_nums(game_state *orig, game_state *copy, bool only_immutable)
294{
295 int i;
296 bool ret = true;
297 assert(copy->n == orig->n);
298 for (i = 0; i < copy->n; i++) {
299 if (only_immutable && !(copy->flags[i] & FLAG_IMMUTABLE)) continue;
300 assert(copy->nums[i] >= 0);
301 assert(copy->nums[i] <= copy->n);
302 if (copy->nums[i] != orig->nums[i]) {
303 debug(("check_nums: (%d,%d) copy=%d, orig=%d.",
304 i%orig->w, i/orig->w, copy->nums[i], orig->nums[i]));
305 ret = false;
306 }
307 }
308 return ret;
309}
310
311/* --- Game parameter/presets functions --- */
312
313static game_params *default_params(void)
314{
315 game_params *ret = snew(game_params);
316 ret->w = ret->h = 4;
317 ret->force_corner_start = true;
318
319 return ret;
320}
321
322static const struct game_params signpost_presets[] = {
323 { 4, 4, 1 },
324 { 4, 4, 0 },
325 { 5, 5, 1 },
326 { 5, 5, 0 },
327 { 6, 6, 1 },
328 { 7, 7, 1 }
329};
330
331static bool game_fetch_preset(int i, char **name, game_params **params)
332{
333 game_params *ret;
334 char buf[80];
335
336 if (i < 0 || i >= lenof(signpost_presets))
337 return false;
338
339 ret = default_params();
340 *ret = signpost_presets[i];
341 *params = ret;
342
343 sprintf(buf, "%dx%d%s", ret->w, ret->h,
344 ret->force_corner_start ? "" : ", free ends");
345 *name = dupstr(buf);
346
347 return true;
348}
349
350static void free_params(game_params *params)
351{
352 sfree(params);
353}
354
355static game_params *dup_params(const game_params *params)
356{
357 game_params *ret = snew(game_params);
358 *ret = *params; /* structure copy */
359 return ret;
360}
361
362static void decode_params(game_params *ret, char const *string)
363{
364 ret->w = ret->h = atoi(string);
365 while (*string && isdigit((unsigned char)*string)) string++;
366 if (*string == 'x') {
367 string++;
368 ret->h = atoi(string);
369 while (*string && isdigit((unsigned char)*string)) string++;
370 }
371 ret->force_corner_start = false;
372 if (*string == 'c') {
373 string++;
374 ret->force_corner_start = true;
375 }
376
377}
378
379static char *encode_params(const game_params *params, bool full)
380{
381 char data[256];
382
383 if (full)
384 sprintf(data, "%dx%d%s", params->w, params->h,
385 params->force_corner_start ? "c" : "");
386 else
387 sprintf(data, "%dx%d", params->w, params->h);
388
389 return dupstr(data);
390}
391
392static config_item *game_configure(const game_params *params)
393{
394 config_item *ret;
395 char buf[80];
396
397 ret = snewn(4, config_item);
398
399 ret[0].name = "Width";
400 ret[0].type = C_STRING;
401 sprintf(buf, "%d", params->w);
402 ret[0].u.string.sval = dupstr(buf);
403
404 ret[1].name = "Height";
405 ret[1].type = C_STRING;
406 sprintf(buf, "%d", params->h);
407 ret[1].u.string.sval = dupstr(buf);
408
409 ret[2].name = "Start and end in corners";
410 ret[2].type = C_BOOLEAN;
411 ret[2].u.boolean.bval = params->force_corner_start;
412
413 ret[3].name = NULL;
414 ret[3].type = C_END;
415
416 return ret;
417}
418
419static game_params *custom_params(const config_item *cfg)
420{
421 game_params *ret = snew(game_params);
422
423 ret->w = atoi(cfg[0].u.string.sval);
424 ret->h = atoi(cfg[1].u.string.sval);
425 ret->force_corner_start = cfg[2].u.boolean.bval;
426
427 return ret;
428}
429
430static const char *validate_params(const game_params *params, bool full)
431{
432 if (params->w < 1) return "Width must be at least one";
433 if (params->h < 1) return "Height must be at least one";
434 if (params->w > INT_MAX / params->h)
435 return "Width times height must not be unreasonably large";
436 if (full && params->w == 1 && params->h == 1)
437 /* The UI doesn't let us move these from unsolved to solved,
438 * so we disallow generating (but not playing) them. */
439 return "Width and height cannot both be one";
440 return NULL;
441}
442
443/* --- Game description string generation and unpicking --- */
444
445static void blank_game_into(game_state *state)
446{
447 memset(state->dirs, 0, state->n*sizeof(int));
448 memset(state->nums, 0, state->n*sizeof(int));
449 memset(state->flags, 0, state->n*sizeof(unsigned int));
450 memset(state->next, -1, state->n*sizeof(int));
451 memset(state->prev, -1, state->n*sizeof(int));
452 memset(state->numsi, -1, (state->n+1)*sizeof(int));
453}
454
455static game_state *blank_game(int w, int h)
456{
457 game_state *state = snew(game_state);
458
459 memset(state, 0, sizeof(game_state));
460 state->w = w;
461 state->h = h;
462 state->n = w*h;
463
464 state->dirs = snewn(state->n, int);
465 state->nums = snewn(state->n, int);
466 state->flags = snewn(state->n, unsigned int);
467 state->next = snewn(state->n, int);
468 state->prev = snewn(state->n, int);
469 state->dsf = dsf_new(state->n);
470 state->numsi = snewn(state->n+1, int);
471
472 blank_game_into(state);
473
474 return state;
475}
476
477static void dup_game_to(game_state *to, const game_state *from)
478{
479 to->completed = from->completed;
480 to->used_solve = from->used_solve;
481 to->impossible = from->impossible;
482
483 memcpy(to->dirs, from->dirs, to->n*sizeof(int));
484 memcpy(to->flags, from->flags, to->n*sizeof(unsigned int));
485 memcpy(to->nums, from->nums, to->n*sizeof(int));
486
487 memcpy(to->next, from->next, to->n*sizeof(int));
488 memcpy(to->prev, from->prev, to->n*sizeof(int));
489
490 dsf_copy(to->dsf, from->dsf);
491 memcpy(to->numsi, from->numsi, (to->n+1)*sizeof(int));
492}
493
494static game_state *dup_game(const game_state *state)
495{
496 game_state *ret = blank_game(state->w, state->h);
497 dup_game_to(ret, state);
498 return ret;
499}
500
501static void free_game(game_state *state)
502{
503 sfree(state->dirs);
504 sfree(state->nums);
505 sfree(state->flags);
506 sfree(state->next);
507 sfree(state->prev);
508 dsf_free(state->dsf);
509 sfree(state->numsi);
510 sfree(state);
511}
512
513static void unpick_desc(const game_params *params, const char *desc,
514 game_state **sout, const char **mout)
515{
516 game_state *state = blank_game(params->w, params->h);
517 const char *msg = NULL;
518 char c;
519 int num = 0, i = 0;
520
521 while (*desc) {
522 if (i >= state->n) {
523 msg = "Game description longer than expected";
524 goto done;
525 }
526
527 c = *desc;
528 if (isdigit((unsigned char)c)) {
529 num = (num*10) + (int)(c-'0');
530 if (num > state->n) {
531 msg = "Number too large";
532 goto done;
533 }
534 } else if ((c-'a') >= 0 && (c-'a') < DIR_MAX) {
535 state->nums[i] = num;
536 state->flags[i] = num ? FLAG_IMMUTABLE : 0;
537 num = 0;
538
539 state->dirs[i] = c - 'a';
540 i++;
541 } else if (!*desc) {
542 msg = "Game description shorter than expected";
543 goto done;
544 } else {
545 msg = "Game description contains unexpected characters";
546 goto done;
547 }
548 desc++;
549 }
550 if (i < state->n) {
551 msg = "Game description shorter than expected";
552 goto done;
553 }
554
555done:
556 if (msg) { /* sth went wrong. */
557 if (mout) *mout = msg;
558 free_game(state);
559 } else {
560 if (mout) *mout = NULL;
561 if (sout) *sout = state;
562 else free_game(state);
563 }
564}
565
566static char *generate_desc(game_state *state, bool issolve)
567{
568 char *ret, buf[80];
569 int retlen, i, k;
570
571 ret = NULL; retlen = 0;
572 if (issolve) {
573 ret = sresize(ret, 2, char);
574 ret[0] = 'S'; ret[1] = '\0';
575 retlen += 1;
576 }
577 for (i = 0; i < state->n; i++) {
578 if (state->nums[i])
579 k = sprintf(buf, "%d%c", state->nums[i], (int)(state->dirs[i]+'a'));
580 else
581 k = sprintf(buf, "%c", (int)(state->dirs[i]+'a'));
582 ret = sresize(ret, retlen + k + 1, char);
583 strcpy(ret + retlen, buf);
584 retlen += k;
585 }
586 return ret;
587}
588
589/* --- Game generation --- */
590
591/* Fills in preallocated arrays ai (indices) and ad (directions)
592 * showing all non-numbered cells adjacent to index i, returns length */
593/* This function has been somewhat optimised... */
594static int cell_adj(game_state *state, int i, int *ai, int *ad)
595{
596 int n = 0, a, x, y, sx, sy, dx, dy, newi;
597 int w = state->w, h = state->h;
598
599 sx = i % w; sy = i / w;
600
601 for (a = 0; a < DIR_MAX; a++) {
602 x = sx; y = sy;
603 dx = dxs[a]; dy = dys[a];
604 while (1) {
605 x += dx; y += dy;
606 if (x < 0 || y < 0 || x >= w || y >= h) break;
607
608 newi = y*w + x;
609 if (state->nums[newi] == 0) {
610 ai[n] = newi;
611 ad[n] = a;
612 n++;
613 }
614 }
615 }
616 return n;
617}
618
619static bool new_game_fill(game_state *state, random_state *rs,
620 int headi, int taili)
621{
622 int nfilled, an, j;
623 bool ret = false;
624 int *aidx, *adir;
625
626 aidx = snewn(state->n, int);
627 adir = snewn(state->n, int);
628
629 debug(("new_game_fill: headi=%d, taili=%d.", headi, taili));
630
631 memset(state->nums, 0, state->n*sizeof(int));
632
633 state->nums[headi] = 1;
634 state->nums[taili] = state->n;
635
636 state->dirs[taili] = 0;
637 nfilled = 2;
638 assert(state->n > 1);
639
640 while (nfilled < state->n) {
641 /* Try and expand _from_ headi; keep going if there's only one
642 * place to go to. */
643 an = cell_adj(state, headi, aidx, adir);
644 do {
645 if (an == 0) goto done;
646 j = random_upto(rs, an);
647 state->dirs[headi] = adir[j];
648 state->nums[aidx[j]] = state->nums[headi] + 1;
649 nfilled++;
650 headi = aidx[j];
651 an = cell_adj(state, headi, aidx, adir);
652 } while (an == 1);
653
654 if (nfilled == state->n) break;
655
656 /* Try and expand _to_ taili; keep going if there's only one
657 * place to go to. */
658 an = cell_adj(state, taili, aidx, adir);
659 do {
660 if (an == 0) goto done;
661 j = random_upto(rs, an);
662 state->dirs[aidx[j]] = DIR_OPPOSITE(adir[j]);
663 state->nums[aidx[j]] = state->nums[taili] - 1;
664 nfilled++;
665 taili = aidx[j];
666 an = cell_adj(state, taili, aidx, adir);
667 } while (an == 1);
668 }
669 /* If we get here we have headi and taili set but unconnected
670 * by direction: we need to set headi's direction so as to point
671 * at taili. */
672 state->dirs[headi] = whichdiri(state, headi, taili);
673
674 /* it could happen that our last two weren't in line; if that's the
675 * case, we have to start again. */
676 if (state->dirs[headi] != -1) ret = true;
677
678done:
679 sfree(aidx);
680 sfree(adir);
681 return ret;
682}
683
684/* Better generator: with the 'generate, sprinkle numbers, solve,
685 * repeat' algorithm we're _never_ generating anything greater than
686 * 6x6, and spending all of our time in new_game_fill (and very little
687 * in solve_state).
688 *
689 * So, new generator steps:
690 * generate the grid, at random (same as now). Numbers 1 and N get
691 immutable flag immediately.
692 * squirrel that away for the solved state.
693 *
694 * (solve:) Try and solve it.
695 * If we solved it, we're done:
696 * generate the description from current immutable numbers,
697 * free stuff that needs freeing,
698 * return description + solved state.
699 * If we didn't solve it:
700 * count #tiles in state we've made deductions about.
701 * while (1):
702 * randomise a scratch array.
703 * for each index in scratch (in turn):
704 * if the cell isn't empty, continue (through scratch array)
705 * set number + immutable in state.
706 * try and solve state.
707 * if we've solved it, we're done.
708 * otherwise, count #tiles. If it's more than we had before:
709 * good, break from this loop and re-randomise.
710 * otherwise (number didn't help):
711 * remove number and try next in scratch array.
712 * if we've got to the end of the scratch array, no luck:
713 free everything we need to, and go back to regenerate the grid.
714 */
715
716static int solve_state(game_state *state);
717
718static void debug_desc(const char *what, game_state *state)
719{
720#if DEBUGGING
721 {
722 char *desc = generate_desc(state, 0);
723 debug(("%s game state: %dx%d:%s", what, state->w, state->h, desc));
724 sfree(desc);
725 }
726#endif
727}
728
729/* Expects a fully-numbered game_state on input, and makes sure
730 * FLAG_IMMUTABLE is only set on those numbers we need to solve
731 * (as for a real new-game); returns true if it managed
732 * this (such that it could solve it), or false if not. */
733static bool new_game_strip(game_state *state, random_state *rs)
734{
735 int *scratch, i, j;
736 bool ret = true;
737 game_state *copy = dup_game(state);
738
739 debug(("new_game_strip."));
740
741 strip_nums(copy);
742 debug_desc("Stripped", copy);
743
744 if (solve_state(copy) > 0) {
745 debug(("new_game_strip: soluble immediately after strip."));
746 free_game(copy);
747 return true;
748 }
749
750 scratch = snewn(state->n, int);
751 for (i = 0; i < state->n; i++) scratch[i] = i;
752 shuffle(scratch, state->n, sizeof(int), rs);
753
754 /* This is scungy. It might just be quick enough.
755 * It goes through, adding set numbers in empty squares
756 * until either we run out of empty squares (in the one
757 * we're half-solving) or else we solve it properly.
758 * NB that we run the entire solver each time, which
759 * strips the grid beforehand; we will save time if we
760 * avoid that. */
761 for (i = 0; i < state->n; i++) {
762 j = scratch[i];
763 if (copy->nums[j] > 0 && copy->nums[j] <= state->n)
764 continue; /* already solved to a real number here. */
765 assert(state->nums[j] <= state->n);
766 debug(("new_game_strip: testing add IMMUTABLE number %d at square (%d,%d).",
767 state->nums[j], j%state->w, j/state->w));
768 copy->nums[j] = state->nums[j];
769 copy->flags[j] |= FLAG_IMMUTABLE;
770 state->flags[j] |= FLAG_IMMUTABLE;
771 debug_state("Copy of state: ", copy);
772 strip_nums(copy);
773 if (solve_state(copy) > 0) goto solved;
774 assert(check_nums(state, copy, true));
775 }
776 ret = false;
777 goto done;
778
779solved:
780 debug(("new_game_strip: now solved."));
781 /* Since we added basically at random, try now to remove numbers
782 * and see if we can still solve it; if we can (still), really
783 * remove the number. Make sure we don't remove the anchor numbers
784 * 1 and N. */
785 for (i = 0; i < state->n; i++) {
786 j = scratch[i];
787 if ((state->flags[j] & FLAG_IMMUTABLE) &&
788 (state->nums[j] != 1 && state->nums[j] != state->n)) {
789 debug(("new_game_strip: testing remove IMMUTABLE number %d at square (%d,%d).",
790 state->nums[j], j%state->w, j/state->w));
791 state->flags[j] &= ~FLAG_IMMUTABLE;
792 dup_game_to(copy, state);
793 strip_nums(copy);
794 if (solve_state(copy) > 0) {
795 assert(check_nums(state, copy, false));
796 debug(("new_game_strip: OK, removing number"));
797 } else {
798 assert(state->nums[j] <= state->n);
799 debug(("new_game_strip: cannot solve, putting IMMUTABLE back."));
800 copy->nums[j] = state->nums[j];
801 state->flags[j] |= FLAG_IMMUTABLE;
802 }
803 }
804 }
805
806done:
807 debug(("new_game_strip: %ssuccessful.", ret ? "" : "not "));
808 sfree(scratch);
809 free_game(copy);
810 return ret;
811}
812
813static char *new_game_desc(const game_params *params, random_state *rs,
814 char **aux, bool interactive)
815{
816 game_state *state = blank_game(params->w, params->h);
817 char *ret;
818 int headi, taili;
819
820 /* this shouldn't happen (validate_params), but let's play it safe */
821 if (params->w == 1 && params->h == 1) return dupstr("1a");
822
823generate:
824 blank_game_into(state);
825
826 /* keep trying until we fill successfully. */
827 do {
828 if (params->force_corner_start) {
829 headi = 0;
830 taili = state->n-1;
831 } else {
832 do {
833 headi = random_upto(rs, state->n);
834 taili = random_upto(rs, state->n);
835 } while (headi == taili);
836 }
837 } while (!new_game_fill(state, rs, headi, taili));
838
839 debug_state("Filled game:", state);
840
841 assert(state->nums[headi] <= state->n);
842 assert(state->nums[taili] <= state->n);
843
844 state->flags[headi] |= FLAG_IMMUTABLE;
845 state->flags[taili] |= FLAG_IMMUTABLE;
846
847 /* This will have filled in directions and _all_ numbers.
848 * Store the game definition for this, as the solved-state. */
849 if (!new_game_strip(state, rs)) {
850 goto generate;
851 }
852 strip_nums(state);
853 {
854 game_state *tosolve = dup_game(state);
855 assert(solve_state(tosolve) > 0);
856 free_game(tosolve);
857 }
858 ret = generate_desc(state, false);
859 free_game(state);
860 return ret;
861}
862
863static const char *validate_desc(const game_params *params, const char *desc)
864{
865 const char *ret = NULL;
866
867 unpick_desc(params, desc, NULL, &ret);
868 return ret;
869}
870
871/* --- Linked-list and numbers array --- */
872
873/* Assuming numbers are always up-to-date, there are only four possibilities
874 * for regions changing after a single valid move:
875 *
876 * 1) two differently-coloured regions being combined (the resulting colouring
877 * should be based on the larger of the two regions)
878 * 2) a numbered region having a single number added to the start (the
879 * region's colour will remain, and the numbers will shift by 1)
880 * 3) a numbered region having a single number added to the end (the
881 * region's colour and numbering remains as-is)
882 * 4) two unnumbered squares being joined (will pick the smallest unused set
883 * of colours to use for the new region).
884 *
885 * There should never be any complications with regions containing 3 colours
886 * being combined, since two of those colours should have been merged on a
887 * previous move.
888 *
889 * Most of the complications are in ensuring we don't accidentally set two
890 * regions with the same colour (e.g. if a region was split). If this happens
891 * we always try and give the largest original portion the original colour.
892 */
893
894#define COLOUR(a) ((a) / (state->n+1))
895#define START(c) ((c) * (state->n+1))
896
897struct head_meta {
898 int i; /* position */
899 int sz; /* size of region */
900 int start; /* region start number preferred, or 0 if !preference */
901 int preference; /* 0 if we have no preference (and should just pick one) */
902 const char *why;
903};
904
905static void head_number(game_state *state, int i, struct head_meta *head)
906{
907 int off = 0, ss, j = i, c, n, sz;
908
909 /* Insist we really were passed the head of a chain. */
910 assert(state->prev[i] == -1 && state->next[i] != -1);
911
912 head->i = i;
913 head->sz = dsf_size(state->dsf, i);
914 head->why = NULL;
915
916 /* Search through this chain looking for real numbers, checking that
917 * they match up (if there are more than one). */
918 head->preference = 0;
919 while (j != -1) {
920 if (state->flags[j] & FLAG_IMMUTABLE) {
921 ss = state->nums[j] - off;
922 if (!head->preference) {
923 head->start = ss;
924 head->preference = 1;
925 head->why = "contains cell with immutable number";
926 } else if (head->start != ss) {
927 debug(("head_number: chain with non-sequential numbers!"));
928 state->impossible = true;
929 }
930 }
931 off++;
932 j = state->next[j];
933 assert(j != i); /* we have created a loop, obviously wrong */
934 }
935 if (head->preference) goto done;
936
937 if (state->nums[i] == 0 && state->nums[state->next[i]] > state->n) {
938 /* (probably) empty cell onto the head of a coloured region:
939 * make sure we start at a 0 offset. */
940 head->start = START(COLOUR(state->nums[state->next[i]]));
941 head->preference = 1;
942 head->why = "adding blank cell to head of numbered region";
943 } else if (state->nums[i] <= state->n) {
944 /* if we're 0 we're probably just blank -- but even if we're a
945 * (real) numbered region, we don't have an immutable number
946 * in it (any more) otherwise it'd have been caught above, so
947 * reassign the colour. */
948 head->start = 0;
949 head->preference = 0;
950 head->why = "lowest available colour group";
951 } else {
952 c = COLOUR(state->nums[i]);
953 n = 1;
954 sz = dsf_size(state->dsf, i);
955 j = i;
956 while (state->next[j] != -1) {
957 j = state->next[j];
958 if (state->nums[j] == 0 && state->next[j] == -1) {
959 head->start = START(c);
960 head->preference = 1;
961 head->why = "adding blank cell to end of numbered region";
962 goto done;
963 }
964 if (COLOUR(state->nums[j]) == c)
965 n++;
966 else {
967 int start_alternate = START(COLOUR(state->nums[j]));
968 if (n < (sz - n)) {
969 head->start = start_alternate;
970 head->preference = 1;
971 head->why = "joining two coloured regions, swapping to larger colour";
972 } else {
973 head->start = START(c);
974 head->preference = 1;
975 head->why = "joining two coloured regions, taking largest";
976 }
977 goto done;
978 }
979 }
980 /* If we got here then we may have split a region into
981 * two; make sure we don't assign a colour we've already used. */
982 if (c == 0) {
983 /* not convinced this shouldn't be an assertion failure here. */
984 head->start = 0;
985 head->preference = 0;
986 } else {
987 head->start = START(c);
988 head->preference = 1;
989 }
990 head->why = "got to end of coloured region";
991 }
992
993done:
994 assert(head->why != NULL);
995 if (head->preference)
996 debug(("Chain at (%d,%d) numbered for preference at %d (colour %d): %s.",
997 head->i%state->w, head->i/state->w,
998 head->start, COLOUR(head->start), head->why));
999 else
1000 debug(("Chain at (%d,%d) using next available colour: %s.",
1001 head->i%state->w, head->i/state->w,
1002 head->why));
1003}
1004
1005#if 0
1006static void debug_numbers(game_state *state)
1007{
1008 int i, w=state->w;
1009
1010 for (i = 0; i < state->n; i++) {
1011 debug(("(%d,%d) --> (%d,%d) --> (%d,%d)",
1012 state->prev[i]==-1 ? -1 : state->prev[i]%w,
1013 state->prev[i]==-1 ? -1 : state->prev[i]/w,
1014 i%w, i/w,
1015 state->next[i]==-1 ? -1 : state->next[i]%w,
1016 state->next[i]==-1 ? -1 : state->next[i]/w));
1017 }
1018 w = w+1;
1019}
1020#endif
1021
1022static void connect_numbers(game_state *state)
1023{
1024 int i, di, dni;
1025
1026 dsf_reinit(state->dsf);
1027 for (i = 0; i < state->n; i++) {
1028 if (state->next[i] != -1) {
1029 assert(state->prev[state->next[i]] == i);
1030 di = dsf_canonify(state->dsf, i);
1031 dni = dsf_canonify(state->dsf, state->next[i]);
1032 if (di == dni) {
1033 debug(("connect_numbers: chain forms a loop."));
1034 state->impossible = true;
1035 }
1036 dsf_merge(state->dsf, di, dni);
1037 }
1038 }
1039}
1040
1041static int compare_heads(const void *a, const void *b)
1042{
1043 const struct head_meta *ha = (const struct head_meta *)a;
1044 const struct head_meta *hb = (const struct head_meta *)b;
1045
1046 /* Heads with preferred colours first... */
1047 if (ha->preference && !hb->preference) return -1;
1048 if (hb->preference && !ha->preference) return 1;
1049
1050 /* ...then heads with low colours first... */
1051 if (ha->start < hb->start) return -1;
1052 if (ha->start > hb->start) return 1;
1053
1054 /* ... then large regions first... */
1055 if (ha->sz > hb->sz) return -1;
1056 if (ha->sz < hb->sz) return 1;
1057
1058 /* ... then position. */
1059 if (ha->i > hb->i) return -1;
1060 if (ha->i < hb->i) return 1;
1061
1062 return 0;
1063}
1064
1065static int lowest_start(game_state *state, struct head_meta *heads, int nheads)
1066{
1067 int n, c;
1068
1069 /* NB start at 1: colour 0 is real numbers */
1070 for (c = 1; c < state->n; c++) {
1071 for (n = 0; n < nheads; n++) {
1072 if (COLOUR(heads[n].start) == c)
1073 goto used;
1074 }
1075 return c;
1076used:
1077 ;
1078 }
1079 assert(!"No available colours!");
1080 return 0;
1081}
1082
1083static void update_numbers(game_state *state)
1084{
1085 int i, j, n, nnum, nheads;
1086 struct head_meta *heads = snewn(state->n, struct head_meta);
1087
1088 for (n = 0; n < state->n; n++)
1089 state->numsi[n] = -1;
1090
1091 for (i = 0; i < state->n; i++) {
1092 if (state->flags[i] & FLAG_IMMUTABLE) {
1093 assert(state->nums[i] > 0);
1094 assert(state->nums[i] <= state->n);
1095 state->numsi[state->nums[i]] = i;
1096 }
1097 else if (state->prev[i] == -1 && state->next[i] == -1)
1098 state->nums[i] = 0;
1099 }
1100 connect_numbers(state);
1101
1102 /* Construct an array of the heads of all current regions, together
1103 * with their preferred colours. */
1104 nheads = 0;
1105 for (i = 0; i < state->n; i++) {
1106 /* Look for a cell that is the start of a chain
1107 * (has a next but no prev). */
1108 if (state->prev[i] != -1 || state->next[i] == -1) continue;
1109
1110 head_number(state, i, &heads[nheads++]);
1111 }
1112
1113 /* Sort that array:
1114 * - heads with preferred colours first, then
1115 * - heads with low colours first, then
1116 * - large regions first
1117 */
1118 qsort(heads, nheads, sizeof(struct head_meta), compare_heads);
1119
1120 /* Remove duplicate-coloured regions. */
1121 for (n = nheads-1; n >= 0; n--) { /* order is important! */
1122 if ((n != 0) && (heads[n].start == heads[n-1].start)) {
1123 /* We have a duplicate-coloured region: since we're
1124 * sorted in size order and this is not the first
1125 * of its colour it's not the largest: recolour it. */
1126 heads[n].start = START(lowest_start(state, heads, nheads));
1127 heads[n].preference = -1; /* '-1' means 'was duplicate' */
1128 }
1129 else if (!heads[n].preference) {
1130 assert(heads[n].start == 0);
1131 heads[n].start = START(lowest_start(state, heads, nheads));
1132 }
1133 }
1134
1135 debug(("Region colouring after duplicate removal:"));
1136
1137 for (n = 0; n < nheads; n++) {
1138 debug((" Chain at (%d,%d) sz %d numbered at %d (colour %d): %s%s",
1139 heads[n].i % state->w, heads[n].i / state->w, heads[n].sz,
1140 heads[n].start, COLOUR(heads[n].start), heads[n].why,
1141 heads[n].preference == 0 ? " (next available)" :
1142 heads[n].preference < 0 ? " (duplicate, next available)" : ""));
1143
1144 nnum = heads[n].start;
1145 j = heads[n].i;
1146 while (j != -1) {
1147 if (!(state->flags[j] & FLAG_IMMUTABLE)) {
1148 if (nnum > 0 && nnum <= state->n)
1149 state->numsi[nnum] = j;
1150 state->nums[j] = nnum;
1151 }
1152 nnum++;
1153 j = state->next[j];
1154 assert(j != heads[n].i); /* loop?! */
1155 }
1156 }
1157 /*debug_numbers(state);*/
1158 sfree(heads);
1159}
1160
1161static bool check_completion(game_state *state, bool mark_errors)
1162{
1163 int n, j, k;
1164 bool error = false, complete;
1165
1166 /* NB This only marks errors that are possible to perpetrate with
1167 * the current UI in interpret_move. Things like forming loops in
1168 * linked sections and having numbers not add up should be forbidden
1169 * by the code elsewhere, so we don't bother marking those (because
1170 * it would add lots of tricky drawing code for very little gain). */
1171 if (mark_errors) {
1172 for (j = 0; j < state->n; j++)
1173 state->flags[j] &= ~FLAG_ERROR;
1174 }
1175
1176 /* Search for repeated numbers. */
1177 for (j = 0; j < state->n; j++) {
1178 if (state->nums[j] > 0 && state->nums[j] <= state->n) {
1179 for (k = j+1; k < state->n; k++) {
1180 if (state->nums[k] == state->nums[j]) {
1181 if (mark_errors) {
1182 state->flags[j] |= FLAG_ERROR;
1183 state->flags[k] |= FLAG_ERROR;
1184 }
1185 error = true;
1186 }
1187 }
1188 }
1189 }
1190
1191 /* Search and mark numbers n not pointing to n+1; if any numbers
1192 * are missing we know we've not completed. */
1193 complete = true;
1194 for (n = 1; n < state->n; n++) {
1195 if (state->numsi[n] == -1 || state->numsi[n+1] == -1)
1196 complete = false;
1197 else if (!ispointingi(state, state->numsi[n], state->numsi[n+1])) {
1198 if (mark_errors) {
1199 state->flags[state->numsi[n]] |= FLAG_ERROR;
1200 state->flags[state->numsi[n+1]] |= FLAG_ERROR;
1201 }
1202 error = true;
1203 } else {
1204 /* make sure the link is explicitly made here; for instance, this
1205 * is nice if the user drags from 2 out (making 3) and a 4 is also
1206 * visible; this ensures that the link from 3 to 4 is also made. */
1207 if (mark_errors)
1208 makelink(state, state->numsi[n], state->numsi[n+1]);
1209 }
1210 }
1211
1212 /* Search and mark numbers less than 0, or 0 with links. */
1213 for (n = 1; n < state->n; n++) {
1214 if ((state->nums[n] < 0) ||
1215 (state->nums[n] == 0 &&
1216 (state->next[n] != -1 || state->prev[n] != -1))) {
1217 error = true;
1218 if (mark_errors)
1219 state->flags[n] |= FLAG_ERROR;
1220 }
1221 }
1222
1223 if (error) return false;
1224 return complete;
1225}
1226static game_state *new_game(midend *me, const game_params *params,
1227 const char *desc)
1228{
1229 game_state *state = NULL;
1230
1231 unpick_desc(params, desc, &state, NULL);
1232 if (!state) assert(!"new_game failed to unpick");
1233
1234 update_numbers(state);
1235 check_completion(state, true); /* update any auto-links */
1236
1237 return state;
1238}
1239
1240/* --- Solver --- */
1241
1242/* If a tile has a single tile it can link _to_, or there's only a single
1243 * location that can link to a given tile, fill that link in. */
1244static int solve_single(game_state *state, game_state *copy, int *from)
1245{
1246 int i, j, sx, sy, x, y, d, poss, w=state->w, nlinks = 0;
1247
1248 /* The from array is a list of 'which square can link _to_ us';
1249 * we start off with from as '-1' (meaning 'not found'); if we find
1250 * something that can link to us it is set to that index, and then if
1251 * we find another we set it to -2. */
1252
1253 memset(from, -1, state->n*sizeof(int));
1254
1255 /* poss is 'can I link to anything' with the same meanings. */
1256
1257 for (i = 0; i < state->n; i++) {
1258 if (state->next[i] != -1) continue;
1259 if (state->nums[i] == state->n) continue; /* no next from last no. */
1260
1261 d = state->dirs[i];
1262 poss = -1;
1263 sx = x = i%w; sy = y = i/w;
1264 while (1) {
1265 x += dxs[d]; y += dys[d];
1266 if (!INGRID(state, x, y)) break;
1267 if (!isvalidmove(state, true, sx, sy, x, y)) continue;
1268
1269 /* can't link to somewhere with a back-link we would have to
1270 * break (the solver just doesn't work like this). */
1271 j = y*w+x;
1272 if (state->prev[j] != -1) continue;
1273
1274 if (state->nums[i] > 0 && state->nums[j] > 0 &&
1275 state->nums[i] <= state->n && state->nums[j] <= state->n &&
1276 state->nums[j] == state->nums[i]+1) {
1277 debug(("Solver: forcing link through existing consecutive numbers."));
1278 poss = j;
1279 from[j] = i;
1280 break;
1281 }
1282
1283 /* if there's been a valid move already, we have to move on;
1284 * we can't make any deductions here. */
1285 poss = (poss == -1) ? j : -2;
1286
1287 /* Modify the from array as described above (which is enumerating
1288 * what points to 'j' in a similar way). */
1289 from[j] = (from[j] == -1) ? i : -2;
1290 }
1291 if (poss == -2) {
1292 /*debug(("Solver: (%d,%d) has multiple possible next squares.", sx, sy));*/
1293 ;
1294 } else if (poss == -1) {
1295 debug(("Solver: nowhere possible for (%d,%d) to link to.", sx, sy));
1296 copy->impossible = true;
1297 return -1;
1298 } else {
1299 debug(("Solver: linking (%d,%d) to only possible next (%d,%d).",
1300 sx, sy, poss%w, poss/w));
1301 makelink(copy, i, poss);
1302 nlinks++;
1303 }
1304 }
1305
1306 for (i = 0; i < state->n; i++) {
1307 if (state->prev[i] != -1) continue;
1308 if (state->nums[i] == 1) continue; /* no prev from 1st no. */
1309
1310 x = i%w; y = i/w;
1311 if (from[i] == -1) {
1312 debug(("Solver: nowhere possible to link to (%d,%d)", x, y));
1313 copy->impossible = true;
1314 return -1;
1315 } else if (from[i] == -2) {
1316 /*debug(("Solver: (%d,%d) has multiple possible prev squares.", x, y));*/
1317 ;
1318 } else {
1319 debug(("Solver: linking only possible prev (%d,%d) to (%d,%d).",
1320 from[i]%w, from[i]/w, x, y));
1321 makelink(copy, from[i], i);
1322 nlinks++;
1323 }
1324 }
1325
1326 return nlinks;
1327}
1328
1329/* Returns 1 if we managed to solve it, 0 otherwise. */
1330static int solve_state(game_state *state)
1331{
1332 game_state *copy = dup_game(state);
1333 int *scratch = snewn(state->n, int), ret;
1334
1335 debug_state("Before solver: ", state);
1336
1337 while (1) {
1338 update_numbers(state);
1339
1340 if (solve_single(state, copy, scratch)) {
1341 dup_game_to(state, copy);
1342 if (state->impossible) break; else continue;
1343 }
1344 break;
1345 }
1346 free_game(copy);
1347 sfree(scratch);
1348
1349 update_numbers(state);
1350 ret = state->impossible ? -1 : check_completion(state, false);
1351 debug(("Solver finished: %s",
1352 ret < 0 ? "impossible" : ret > 0 ? "solved" : "not solved"));
1353 debug_state("After solver: ", state);
1354 return ret;
1355}
1356
1357static char *solve_game(const game_state *state, const game_state *currstate,
1358 const char *aux, const char **error)
1359{
1360 game_state *tosolve;
1361 char *ret = NULL;
1362 int result;
1363
1364 tosolve = dup_game(currstate);
1365 result = solve_state(tosolve);
1366 if (result > 0)
1367 ret = generate_desc(tosolve, true);
1368 free_game(tosolve);
1369 if (ret) return ret;
1370
1371 tosolve = dup_game(state);
1372 result = solve_state(tosolve);
1373 if (result < 0)
1374 *error = "Puzzle is impossible.";
1375 else if (result == 0)
1376 *error = "Unable to solve puzzle.";
1377 else
1378 ret = generate_desc(tosolve, true);
1379
1380 free_game(tosolve);
1381
1382 return ret;
1383}
1384
1385/* --- UI and move routines. --- */
1386
1387
1388struct game_ui {
1389 int cx, cy;
1390 bool cshow;
1391
1392 bool dragging, drag_is_from;
1393 int sx, sy; /* grid coords of start cell */
1394 int dx, dy; /* pixel coords of drag posn */
1395
1396 /*
1397 * Trivial and foolish configurable option done on purest whim.
1398 * With this option enabled, the victory flash is done by rotating
1399 * each square in the opposite direction from its immediate
1400 * neighbours, so that they behave like a field of interlocking
1401 * gears. With it disabled, they all rotate in the same direction.
1402 * Choose for yourself which is more brain-twisting :-)
1403 */
1404 bool gear_mode;
1405};
1406
1407static void legacy_prefs_override(struct game_ui *ui_out)
1408{
1409 static bool initialised = false;
1410 static int gear_mode = -1;
1411
1412 if (!initialised) {
1413 initialised = true;
1414 gear_mode = getenv_bool("SIGNPOST_GEARS", -1);
1415 }
1416
1417 if (gear_mode != -1)
1418 ui_out->gear_mode = gear_mode;
1419}
1420
1421static game_ui *new_ui(const game_state *state)
1422{
1423 game_ui *ui = snew(game_ui);
1424
1425 /* NB: if this is ever changed to as to require more than a structure
1426 * copy to clone, there's code that needs fixing in game_redraw too. */
1427
1428 ui->cx = ui->cy = 0;
1429 ui->cshow = getenv_bool("PUZZLES_SHOW_CURSOR", false);
1430
1431 ui->dragging = false;
1432 ui->sx = ui->sy = ui->dx = ui->dy = 0;
1433
1434 ui->gear_mode = false;
1435 legacy_prefs_override(ui);
1436
1437 return ui;
1438}
1439
1440static void free_ui(game_ui *ui)
1441{
1442 sfree(ui);
1443}
1444
1445static config_item *get_prefs(game_ui *ui)
1446{
1447 config_item *ret;
1448
1449 ret = snewn(N_PREF_ITEMS+1, config_item);
1450
1451 ret[PREF_FLASH_TYPE].name = "Victory rotation effect";
1452 ret[PREF_FLASH_TYPE].kw = "flash-type";
1453 ret[PREF_FLASH_TYPE].type = C_CHOICES;
1454 ret[PREF_FLASH_TYPE].u.choices.choicenames =
1455 ":Unidirectional:Meshing gears";
1456 ret[PREF_FLASH_TYPE].u.choices.choicekws = ":unidirectional:gears";
1457 ret[PREF_FLASH_TYPE].u.choices.selected = ui->gear_mode;
1458
1459 ret[N_PREF_ITEMS].name = NULL;
1460 ret[N_PREF_ITEMS].type = C_END;
1461
1462 return ret;
1463}
1464
1465static void set_prefs(game_ui *ui, const config_item *cfg)
1466{
1467 ui->gear_mode = cfg[PREF_FLASH_TYPE].u.choices.selected;
1468}
1469
1470static void game_changed_state(game_ui *ui, const game_state *oldstate,
1471 const game_state *newstate)
1472{
1473 if (!oldstate->completed && newstate->completed) {
1474 ui->cshow = false;
1475 ui->dragging = false;
1476 }
1477}
1478
1479static const char *current_key_label(const game_ui *ui,
1480 const game_state *state, int button)
1481{
1482 if (IS_CURSOR_SELECT(button) && ui->cshow) {
1483 if (ui->dragging) {
1484 if (ui->drag_is_from) {
1485 if (isvalidmove(state, false, ui->sx, ui->sy, ui->cx, ui->cy))
1486 return "To here";
1487 } else {
1488 if (isvalidmove(state, false, ui->cx, ui->cy, ui->sx, ui->sy))
1489 return "From here";
1490 }
1491 return "Cancel";
1492 } else {
1493 return button == CURSOR_SELECT ? "From here" : "To here";
1494 }
1495 }
1496 return "";
1497}
1498
1499struct game_drawstate {
1500 int tilesize;
1501 bool started, solved;
1502 int w, h, n;
1503 int *nums, *dirp;
1504 unsigned int *f;
1505 double angle_offset;
1506
1507 bool dragging;
1508 int dx, dy;
1509 blitter *dragb;
1510};
1511
1512static char *interpret_move(const game_state *state, game_ui *ui,
1513 const game_drawstate *ds,
1514 int mx, int my, int button)
1515{
1516 int x = FROMCOORD(mx), y = FROMCOORD(my), w = state->w;
1517 char buf[80];
1518
1519 if (IS_CURSOR_MOVE(button)) {
1520 char *ret;
1521 ret = move_cursor(button, &ui->cx, &ui->cy, state->w, state->h, false,
1522 &ui->cshow);
1523 if (ui->dragging) {
1524 ui->dx = COORD(ui->cx) + TILE_SIZE/2;
1525 ui->dy = COORD(ui->cy) + TILE_SIZE/2;
1526 }
1527 return ret;
1528 } else if (IS_CURSOR_SELECT(button)) {
1529 if (!ui->cshow)
1530 ui->cshow = true;
1531 else if (ui->dragging) {
1532 ui->dragging = false;
1533 if (ui->sx == ui->cx && ui->sy == ui->cy) return MOVE_UI_UPDATE;
1534 if (ui->drag_is_from) {
1535 if (!isvalidmove(state, false, ui->sx, ui->sy, ui->cx, ui->cy))
1536 return MOVE_UI_UPDATE;
1537 sprintf(buf, "L%d,%d-%d,%d", ui->sx, ui->sy, ui->cx, ui->cy);
1538 } else {
1539 if (!isvalidmove(state, false, ui->cx, ui->cy, ui->sx, ui->sy))
1540 return MOVE_UI_UPDATE;
1541 sprintf(buf, "L%d,%d-%d,%d", ui->cx, ui->cy, ui->sx, ui->sy);
1542 }
1543 return dupstr(buf);
1544 } else {
1545 ui->dragging = true;
1546 ui->sx = ui->cx;
1547 ui->sy = ui->cy;
1548 ui->dx = COORD(ui->cx) + TILE_SIZE/2;
1549 ui->dy = COORD(ui->cy) + TILE_SIZE/2;
1550 ui->drag_is_from = (button == CURSOR_SELECT);
1551 }
1552 return MOVE_UI_UPDATE;
1553 }
1554 if (IS_MOUSE_DOWN(button)) {
1555 if (ui->cshow) {
1556 ui->cshow = false;
1557 ui->dragging = false;
1558 }
1559 assert(!ui->dragging);
1560 if (!INGRID(state, x, y)) return NULL;
1561
1562 if (button == LEFT_BUTTON) {
1563 /* disallow dragging from the final number. */
1564 if ((state->nums[y*w+x] == state->n) &&
1565 (state->flags[y*w+x] & FLAG_IMMUTABLE))
1566 return NULL;
1567 } else if (button == RIGHT_BUTTON) {
1568 /* disallow dragging to the first number. */
1569 if ((state->nums[y*w+x] == 1) &&
1570 (state->flags[y*w+x] & FLAG_IMMUTABLE))
1571 return NULL;
1572 }
1573
1574 ui->dragging = true;
1575 ui->drag_is_from = (button == LEFT_BUTTON);
1576 ui->sx = x;
1577 ui->sy = y;
1578 ui->dx = mx;
1579 ui->dy = my;
1580 ui->cshow = false;
1581 return MOVE_UI_UPDATE;
1582 } else if (IS_MOUSE_DRAG(button) && ui->dragging) {
1583 ui->dx = mx;
1584 ui->dy = my;
1585 return MOVE_UI_UPDATE;
1586 } else if (IS_MOUSE_RELEASE(button) && ui->dragging) {
1587 ui->dragging = false;
1588 if (ui->sx == x && ui->sy == y) return MOVE_UI_UPDATE; /* single click */
1589
1590 if (!INGRID(state, x, y)) {
1591 int si = ui->sy*w+ui->sx;
1592 if (state->prev[si] == -1 && state->next[si] == -1)
1593 return MOVE_UI_UPDATE;
1594 sprintf(buf, "%c%d,%d",
1595 (int)(ui->drag_is_from ? 'C' : 'X'), ui->sx, ui->sy);
1596 return dupstr(buf);
1597 }
1598
1599 if (ui->drag_is_from) {
1600 if (!isvalidmove(state, false, ui->sx, ui->sy, x, y))
1601 return MOVE_UI_UPDATE;
1602 sprintf(buf, "L%d,%d-%d,%d", ui->sx, ui->sy, x, y);
1603 } else {
1604 if (!isvalidmove(state, false, x, y, ui->sx, ui->sy))
1605 return MOVE_UI_UPDATE;
1606 sprintf(buf, "L%d,%d-%d,%d", x, y, ui->sx, ui->sy);
1607 }
1608 return dupstr(buf);
1609 } /* else if (button == 'H' || button == 'h')
1610 return dupstr("H"); */
1611 else if ((button == 'x' || button == 'X') && ui->cshow) {
1612 int si = ui->cy*w + ui->cx;
1613 if (state->prev[si] == -1 && state->next[si] == -1)
1614 return MOVE_UI_UPDATE;
1615 sprintf(buf, "%c%d,%d",
1616 (int)((button == 'x') ? 'C' : 'X'), ui->cx, ui->cy);
1617 return dupstr(buf);
1618 }
1619
1620 return NULL;
1621}
1622
1623static void unlink_cell(game_state *state, int si)
1624{
1625 debug(("Unlinking (%d,%d).", si%state->w, si/state->w));
1626 if (state->prev[si] != -1) {
1627 debug((" ... removing prev link from (%d,%d).",
1628 state->prev[si]%state->w, state->prev[si]/state->w));
1629 state->next[state->prev[si]] = -1;
1630 state->prev[si] = -1;
1631 }
1632 if (state->next[si] != -1) {
1633 debug((" ... removing next link to (%d,%d).",
1634 state->next[si]%state->w, state->next[si]/state->w));
1635 state->prev[state->next[si]] = -1;
1636 state->next[si] = -1;
1637 }
1638}
1639
1640static game_state *execute_move(const game_state *state, const char *move)
1641{
1642 game_state *ret = NULL;
1643 int sx, sy, ex, ey, si, ei, w = state->w;
1644 char c;
1645
1646 debug(("move: %s", move));
1647
1648 if (move[0] == 'S') {
1649 game_params p;
1650 game_state *tmp;
1651 const char *valid;
1652 int i;
1653
1654 p.w = state->w; p.h = state->h;
1655 valid = validate_desc(&p, move+1);
1656 if (valid) {
1657 debug(("execute_move: move not valid: %s", valid));
1658 return NULL;
1659 }
1660 ret = dup_game(state);
1661 tmp = new_game(NULL, &p, move+1);
1662 for (i = 0; i < state->n; i++) {
1663 ret->prev[i] = tmp->prev[i];
1664 ret->next[i] = tmp->next[i];
1665 }
1666 free_game(tmp);
1667 ret->used_solve = true;
1668 } else if (sscanf(move, "L%d,%d-%d,%d", &sx, &sy, &ex, &ey) == 4) {
1669 if (!isvalidmove(state, false, sx, sy, ex, ey)) return NULL;
1670
1671 ret = dup_game(state);
1672
1673 si = sy*w+sx; ei = ey*w+ex;
1674 makelink(ret, si, ei);
1675 } else if (sscanf(move, "%c%d,%d", &c, &sx, &sy) == 3) {
1676 int sset;
1677
1678 if (c != 'C' && c != 'X') return NULL;
1679 if (!INGRID(state, sx, sy)) return NULL;
1680 si = sy*w+sx;
1681 if (state->prev[si] == -1 && state->next[si] == -1)
1682 return NULL;
1683
1684 ret = dup_game(state);
1685
1686 sset = state->nums[si] / (state->n+1);
1687 if (c == 'C' || (c == 'X' && sset == 0)) {
1688 /* Unlink the single cell we dragged from the board. */
1689 unlink_cell(ret, si);
1690 } else {
1691 int i, set;
1692 for (i = 0; i < state->n; i++) {
1693 /* Unlink all cells in the same set as the one we dragged
1694 * from the board. */
1695
1696 if (state->nums[i] == 0) continue;
1697 set = state->nums[i] / (state->n+1);
1698 if (set != sset) continue;
1699
1700 unlink_cell(ret, i);
1701 }
1702 }
1703 } else if (strcmp(move, "H") == 0) {
1704 ret = dup_game(state);
1705 solve_state(ret);
1706 }
1707 if (ret) {
1708 update_numbers(ret);
1709 if (check_completion(ret, true)) ret->completed = true;
1710 }
1711
1712 return ret;
1713}
1714
1715/* ----------------------------------------------------------------------
1716 * Drawing routines.
1717 */
1718
1719static void game_compute_size(const game_params *params, int tilesize,
1720 const game_ui *ui, int *x, int *y)
1721{
1722 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
1723 struct { int tilesize, order; } ads, *ds = &ads;
1724 ads.tilesize = tilesize;
1725
1726 *x = TILE_SIZE * params->w + 2 * BORDER;
1727 *y = TILE_SIZE * params->h + 2 * BORDER;
1728}
1729
1730static void game_set_size(drawing *dr, game_drawstate *ds,
1731 const game_params *params, int tilesize)
1732{
1733 ds->tilesize = tilesize;
1734 assert(TILE_SIZE > 0);
1735
1736 assert(!ds->dragb);
1737 ds->dragb = blitter_new(dr, BLITTER_SIZE, BLITTER_SIZE);
1738}
1739
1740/* Colours chosen from the webby palette to work as a background to black text,
1741 * W then some plausible approximation to pastelly ROYGBIV; we then interpolate
1742 * between consecutive pairs to give another 8 (and then the drawing routine
1743 * will reuse backgrounds). */
1744static const unsigned long bgcols[8] = {
1745 0xffffff, /* white */
1746 0xffa07a, /* lightsalmon */
1747 0x98fb98, /* green */
1748 0x7fffd4, /* aquamarine */
1749 0x9370db, /* medium purple */
1750 0xffa500, /* orange */
1751 0x87cefa, /* lightskyblue */
1752 0xffff00, /* yellow */
1753};
1754
1755static float *game_colours(frontend *fe, int *ncolours)
1756{
1757 float *ret = snewn(3 * NCOLOURS, float);
1758 int c, i;
1759
1760 game_mkhighlight(fe, ret, COL_BACKGROUND, COL_HIGHLIGHT, COL_LOWLIGHT);
1761
1762 for (i = 0; i < 3; i++) {
1763 ret[COL_NUMBER * 3 + i] = 0.0F;
1764 ret[COL_ARROW * 3 + i] = 0.0F;
1765 ret[COL_CURSOR * 3 + i] = ret[COL_BACKGROUND * 3 + i] / 2.0F;
1766 ret[COL_GRID * 3 + i] = ret[COL_BACKGROUND * 3 + i] / 1.3F;
1767 }
1768 ret[COL_NUMBER_SET * 3 + 0] = 0.0F;
1769 ret[COL_NUMBER_SET * 3 + 1] = 0.0F;
1770 ret[COL_NUMBER_SET * 3 + 2] = 0.9F;
1771
1772 ret[COL_ERROR * 3 + 0] = 1.0F;
1773 ret[COL_ERROR * 3 + 1] = 0.0F;
1774 ret[COL_ERROR * 3 + 2] = 0.0F;
1775
1776 ret[COL_DRAG_ORIGIN * 3 + 0] = 0.2F;
1777 ret[COL_DRAG_ORIGIN * 3 + 1] = 1.0F;
1778 ret[COL_DRAG_ORIGIN * 3 + 2] = 0.2F;
1779
1780 for (c = 0; c < 8; c++) {
1781 ret[(COL_B0 + c) * 3 + 0] = (float)((bgcols[c] & 0xff0000) >> 16) / 256.0F;
1782 ret[(COL_B0 + c) * 3 + 1] = (float)((bgcols[c] & 0xff00) >> 8) / 256.0F;
1783 ret[(COL_B0 + c) * 3 + 2] = (float)((bgcols[c] & 0xff)) / 256.0F;
1784 }
1785 for (c = 0; c < 8; c++) {
1786 for (i = 0; i < 3; i++) {
1787 ret[(COL_B0 + 8 + c) * 3 + i] =
1788 (ret[(COL_B0 + c) * 3 + i] + ret[(COL_B0 + c + 1) * 3 + i]) / 2.0F;
1789 }
1790 }
1791
1792#define average(r,a,b,w) do { \
1793 for (i = 0; i < 3; i++) \
1794 ret[(r)*3+i] = ret[(a)*3+i] + w * (ret[(b)*3+i] - ret[(a)*3+i]); \
1795} while (0)
1796 average(COL_ARROW_BG_DIM, COL_BACKGROUND, COL_ARROW, 0.1F);
1797 average(COL_NUMBER_SET_MID, COL_B0, COL_NUMBER_SET, 0.3F);
1798 for (c = 0; c < NBACKGROUNDS; c++) {
1799 /* I assume here that COL_ARROW and COL_NUMBER are the same.
1800 * Otherwise I'd need two sets of COL_M*. */
1801 average(COL_M0 + c, COL_B0 + c, COL_NUMBER, 0.3F);
1802 average(COL_D0 + c, COL_B0 + c, COL_NUMBER, 0.1F);
1803 average(COL_X0 + c, COL_BACKGROUND, COL_B0 + c, 0.5F);
1804 }
1805
1806 *ncolours = NCOLOURS;
1807 return ret;
1808}
1809
1810static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state)
1811{
1812 struct game_drawstate *ds = snew(struct game_drawstate);
1813 int i;
1814
1815 ds->tilesize = 0;
1816 ds->started = false;
1817 ds->solved = false;
1818 ds->w = state->w;
1819 ds->h = state->h;
1820 ds->n = state->n;
1821
1822 ds->nums = snewn(state->n, int);
1823 ds->dirp = snewn(state->n, int);
1824 ds->f = snewn(state->n, unsigned int);
1825 for (i = 0; i < state->n; i++) {
1826 ds->nums[i] = 0;
1827 ds->dirp[i] = -1;
1828 ds->f[i] = 0;
1829 }
1830
1831 ds->angle_offset = 0.0F;
1832
1833 ds->dragging = false;
1834 ds->dx = ds->dy = 0;
1835 ds->dragb = NULL;
1836
1837 return ds;
1838}
1839
1840static void game_free_drawstate(drawing *dr, game_drawstate *ds)
1841{
1842 sfree(ds->nums);
1843 sfree(ds->dirp);
1844 sfree(ds->f);
1845 if (ds->dragb) blitter_free(dr, ds->dragb);
1846
1847 sfree(ds);
1848}
1849
1850/* cx, cy are top-left corner. sz is the 'radius' of the arrow.
1851 * ang is in radians, clockwise from 0 == straight up. */
1852static void draw_arrow(drawing *dr, int cx, int cy, int sz, double ang,
1853 int cfill, int cout)
1854{
1855 int coords[14];
1856 int xdx, ydx, xdy, ydy, xdx3, xdy3;
1857 double s = sin(ang), c = cos(ang);
1858
1859 xdx3 = (int)(sz * (c/3 + 1) + 0.5) - sz;
1860 xdy3 = (int)(sz * (s/3 + 1) + 0.5) - sz;
1861 xdx = (int)(sz * (c + 1) + 0.5) - sz;
1862 xdy = (int)(sz * (s + 1) + 0.5) - sz;
1863 ydx = -xdy;
1864 ydy = xdx;
1865
1866
1867 coords[2*0 + 0] = cx - ydx;
1868 coords[2*0 + 1] = cy - ydy;
1869 coords[2*1 + 0] = cx + xdx;
1870 coords[2*1 + 1] = cy + xdy;
1871 coords[2*2 + 0] = cx + xdx3;
1872 coords[2*2 + 1] = cy + xdy3;
1873 coords[2*3 + 0] = cx + xdx3 + ydx;
1874 coords[2*3 + 1] = cy + xdy3 + ydy;
1875 coords[2*4 + 0] = cx - xdx3 + ydx;
1876 coords[2*4 + 1] = cy - xdy3 + ydy;
1877 coords[2*5 + 0] = cx - xdx3;
1878 coords[2*5 + 1] = cy - xdy3;
1879 coords[2*6 + 0] = cx - xdx;
1880 coords[2*6 + 1] = cy - xdy;
1881
1882 draw_polygon(dr, coords, 7, cfill, cout);
1883}
1884
1885static void draw_arrow_dir(drawing *dr, int cx, int cy, int sz, int dir,
1886 int cfill, int cout, double angle_offset)
1887{
1888 double ang = 2.0 * PI * (double)dir / 8.0 + angle_offset;
1889 draw_arrow(dr, cx, cy, sz, ang, cfill, cout);
1890}
1891
1892/* cx, cy are centre coordinates.. */
1893static void draw_star(drawing *dr, int cx, int cy, int rad, int npoints,
1894 int cfill, int cout, double angle_offset)
1895{
1896 int *coords, n;
1897 double a, r;
1898
1899 assert(npoints > 0);
1900
1901 coords = snewn(npoints * 2 * 2, int);
1902
1903 for (n = 0; n < npoints * 2; n++) {
1904 a = 2.0 * PI * ((double)n / ((double)npoints * 2.0)) + angle_offset;
1905 r = (n % 2) ? (double)rad/2.0 : (double)rad;
1906
1907 /* We're rotating the point at (0, -r) by a degrees */
1908 coords[2*n+0] = cx + (int)( r * sin(a));
1909 coords[2*n+1] = cy + (int)(-r * cos(a));
1910 }
1911 draw_polygon(dr, coords, npoints*2, cfill, cout);
1912 sfree(coords);
1913}
1914
1915static int num2col(game_drawstate *ds, int num)
1916{
1917 int set = num / (ds->n+1);
1918
1919 if (num <= 0 || set == 0) return COL_B0;
1920 return COL_B0 + 1 + ((set-1) % 15);
1921}
1922
1923#define ARROW_HALFSZ (7 * TILE_SIZE / 32)
1924
1925#define F_CUR 0x001 /* Cursor on this tile. */
1926#define F_DRAG_SRC 0x002 /* Tile is source of a drag. */
1927#define F_ERROR 0x004 /* Tile marked in error. */
1928#define F_IMMUTABLE 0x008 /* Tile (number) is immutable. */
1929#define F_ARROW_POINT 0x010 /* Tile points to other tile */
1930#define F_ARROW_INPOINT 0x020 /* Other tile points in here. */
1931#define F_DIM 0x040 /* Tile is dim */
1932
1933static void tile_redraw(drawing *dr, game_drawstate *ds, int tx, int ty,
1934 int dir, int dirp, int num, unsigned int f,
1935 double angle_offset, int print_ink)
1936{
1937 int cb = TILE_SIZE / 16, textsz;
1938 char buf[20];
1939 int arrowcol, sarrowcol, setcol, textcol;
1940 int acx, acy, asz;
1941 bool empty = false;
1942
1943 if (num == 0 && !(f & F_ARROW_POINT) && !(f & F_ARROW_INPOINT)) {
1944 empty = true;
1945 /*
1946 * We don't display text in empty cells: typically these are
1947 * signified by num=0. However, in some cases a cell could
1948 * have had the number 0 assigned to it if the user made an
1949 * error (e.g. tried to connect a chain of length 5 to the
1950 * immutable number 4) so we _do_ display the 0 if the cell
1951 * has a link in or a link out.
1952 */
1953 }
1954
1955 /* Calculate colours. */
1956
1957 if (print_ink >= 0) {
1958 /*
1959 * We're printing, so just do everything in black.
1960 */
1961 arrowcol = textcol = print_ink;
1962 setcol = sarrowcol = -1; /* placate optimiser */
1963 } else {
1964
1965 setcol = empty ? COL_BACKGROUND : num2col(ds, num);
1966
1967#define dim(fg,bg) ( \
1968 (bg)==COL_BACKGROUND ? COL_ARROW_BG_DIM : \
1969 (bg) + COL_D0 - COL_B0 \
1970 )
1971
1972#define mid(fg,bg) ( \
1973 (fg)==COL_NUMBER_SET ? COL_NUMBER_SET_MID : \
1974 (bg) + COL_M0 - COL_B0 \
1975 )
1976
1977#define dimbg(bg) ( \
1978 (bg)==COL_BACKGROUND ? COL_BACKGROUND : \
1979 (bg) + COL_X0 - COL_B0 \
1980 )
1981
1982 if (f & F_DRAG_SRC) arrowcol = COL_DRAG_ORIGIN;
1983 else if (f & F_DIM) arrowcol = dim(COL_ARROW, setcol);
1984 else if (f & F_ARROW_POINT) arrowcol = mid(COL_ARROW, setcol);
1985 else arrowcol = COL_ARROW;
1986
1987 if ((f & F_ERROR) && !(f & F_IMMUTABLE)) textcol = COL_ERROR;
1988 else {
1989 if (f & F_IMMUTABLE) textcol = COL_NUMBER_SET;
1990 else textcol = COL_NUMBER;
1991
1992 if (f & F_DIM) textcol = dim(textcol, setcol);
1993 else if (((f & F_ARROW_POINT) || num==ds->n) &&
1994 ((f & F_ARROW_INPOINT) || num==1))
1995 textcol = mid(textcol, setcol);
1996 }
1997
1998 if (f & F_DIM) sarrowcol = dim(COL_ARROW, setcol);
1999 else sarrowcol = COL_ARROW;
2000 }
2001
2002 /* Clear tile background */
2003
2004 if (print_ink < 0) {
2005 draw_rect(dr, tx, ty, TILE_SIZE, TILE_SIZE,
2006 (f & F_DIM) ? dimbg(setcol) : setcol);
2007 }
2008
2009 /* Draw large (outwards-pointing) arrow. */
2010
2011 asz = ARROW_HALFSZ; /* 'radius' of arrow/star. */
2012 acx = tx+TILE_SIZE/2+asz; /* centre x */
2013 acy = ty+TILE_SIZE/2+asz; /* centre y */
2014
2015 if (num == ds->n && (f & F_IMMUTABLE))
2016 draw_star(dr, acx, acy, asz, 5, arrowcol, arrowcol, angle_offset);
2017 else
2018 draw_arrow_dir(dr, acx, acy, asz, dir, arrowcol, arrowcol, angle_offset);
2019 if (print_ink < 0 && (f & F_CUR))
2020 draw_rect_corners(dr, acx, acy, asz+1, COL_CURSOR);
2021
2022 /* Draw dot iff this tile requires a predecessor and doesn't have one. */
2023
2024 if (print_ink < 0) {
2025 acx = tx+TILE_SIZE/2-asz;
2026 acy = ty+TILE_SIZE/2+asz;
2027
2028 if (!(f & F_ARROW_INPOINT) && num != 1) {
2029 draw_circle(dr, acx, acy, asz / 4, sarrowcol, sarrowcol);
2030 }
2031 }
2032
2033 /* Draw text (number or set). */
2034
2035 if (!empty) {
2036 int set = (num <= 0) ? 0 : num / (ds->n+1);
2037
2038 char *p = buf;
2039 if (set == 0 || num <= 0) {
2040 sprintf(buf, "%d", num);
2041 } else {
2042 int n = num % (ds->n+1);
2043 p += sizeof(buf) - 1;
2044
2045 if (n != 0) {
2046 sprintf(buf, "+%d", n); /* Just to get the length... */
2047 p -= strlen(buf);
2048 sprintf(p, "+%d", n);
2049 } else {
2050 *p = '\0';
2051 }
2052 do {
2053 set--;
2054 p--;
2055 *p = (char)((set % 26)+'a');
2056 set /= 26;
2057 } while (set);
2058 }
2059 textsz = min(2*asz, (TILE_SIZE - 2 * cb) / (int)strlen(p));
2060 draw_text(dr, tx + cb, ty + TILE_SIZE/4, FONT_VARIABLE, textsz,
2061 ALIGN_VCENTRE | ALIGN_HLEFT, textcol, p);
2062 }
2063
2064 if (print_ink < 0) {
2065 draw_rect_outline(dr, tx, ty, TILE_SIZE, TILE_SIZE, COL_GRID);
2066 draw_update(dr, tx, ty, TILE_SIZE, TILE_SIZE);
2067 }
2068}
2069
2070static void draw_drag_indicator(drawing *dr, game_drawstate *ds,
2071 const game_state *state, const game_ui *ui,
2072 bool validdrag)
2073{
2074 int dir, w = ds->w, acol = COL_ARROW;
2075 int fx = FROMCOORD(ui->dx), fy = FROMCOORD(ui->dy);
2076 double ang;
2077
2078 if (validdrag && INGRID(state, fx, fy)) {
2079 /* If we could move here, lock the arrow to the appropriate direction. */
2080 dir = ui->drag_is_from ? state->dirs[ui->sy*w+ui->sx] : state->dirs[fy*w+fx];
2081
2082 ang = (2.0 * PI * dir) / 8.0; /* similar to calculation in draw_arrow_dir. */
2083 } else {
2084 /* Draw an arrow pointing away from/towards the origin cell. */
2085 int ox = COORD(ui->sx) + TILE_SIZE/2, oy = COORD(ui->sy) + TILE_SIZE/2;
2086 double tana, offset;
2087 double xdiff = abs(ox - ui->dx), ydiff = abs(oy - ui->dy);
2088
2089 if (xdiff == 0) {
2090 ang = (oy > ui->dy) ? 0.0F : PI;
2091 } else if (ydiff == 0) {
2092 ang = (ox > ui->dx) ? 3.0F*PI/2.0F : PI/2.0F;
2093 } else {
2094 if (ui->dx > ox && ui->dy < oy) {
2095 tana = xdiff / ydiff;
2096 offset = 0.0F;
2097 } else if (ui->dx > ox && ui->dy > oy) {
2098 tana = ydiff / xdiff;
2099 offset = PI/2.0F;
2100 } else if (ui->dx < ox && ui->dy > oy) {
2101 tana = xdiff / ydiff;
2102 offset = PI;
2103 } else {
2104 tana = ydiff / xdiff;
2105 offset = 3.0F * PI / 2.0F;
2106 }
2107 ang = atan(tana) + offset;
2108 }
2109
2110 if (!ui->drag_is_from) ang += PI; /* point to origin, not away from. */
2111
2112 }
2113 draw_arrow(dr, ui->dx, ui->dy, ARROW_HALFSZ, ang, acol, acol);
2114}
2115
2116static void game_redraw(drawing *dr, game_drawstate *ds,
2117 const game_state *oldstate, const game_state *state,
2118 int dir, const game_ui *ui,
2119 float animtime, float flashtime)
2120{
2121 int x, y, i, w = ds->w, dirp;
2122 bool force = false;
2123 unsigned int f;
2124 double angle_offset = 0.0;
2125 game_state *postdrop = NULL;
2126
2127 if (flashtime > 0.0F)
2128 angle_offset = 2.0 * PI * (flashtime / FLASH_SPIN);
2129 if (angle_offset != ds->angle_offset) {
2130 ds->angle_offset = angle_offset;
2131 force = true;
2132 }
2133
2134 if (ds->dragging) {
2135 assert(ds->dragb);
2136 blitter_load(dr, ds->dragb, ds->dx, ds->dy);
2137 draw_update(dr, ds->dx, ds->dy, BLITTER_SIZE, BLITTER_SIZE);
2138 ds->dragging = false;
2139 }
2140
2141 /* If an in-progress drag would make a valid move if finished, we
2142 * reflect that move in the board display. We let interpret_move do
2143 * most of the heavy lifting for us: we have to copy the game_ui so
2144 * as not to stomp on the real UI's drag state. */
2145 if (ui->dragging) {
2146 game_ui uicopy = *ui;
2147 char *movestr = interpret_move(state, &uicopy, ds, ui->dx, ui->dy, LEFT_RELEASE);
2148
2149 if (movestr != NULL && strcmp(movestr, "") != 0) {
2150 postdrop = execute_move(state, movestr);
2151 sfree(movestr);
2152
2153 state = postdrop;
2154 }
2155 }
2156
2157 if (!ds->started) {
2158 int aw = TILE_SIZE * state->w;
2159 int ah = TILE_SIZE * state->h;
2160 draw_rect_outline(dr, BORDER - 1, BORDER - 1, aw + 2, ah + 2, COL_GRID);
2161 draw_update(dr, 0, 0, aw + 2 * BORDER, ah + 2 * BORDER);
2162 }
2163 for (x = 0; x < state->w; x++) {
2164 for (y = 0; y < state->h; y++) {
2165 i = y*w + x;
2166 f = 0;
2167 dirp = -1;
2168
2169 if (ui->cshow && x == ui->cx && y == ui->cy)
2170 f |= F_CUR;
2171
2172 if (ui->dragging) {
2173 if (x == ui->sx && y == ui->sy)
2174 f |= F_DRAG_SRC;
2175 else if (ui->drag_is_from) {
2176 if (!ispointing(state, ui->sx, ui->sy, x, y))
2177 f |= F_DIM;
2178 } else {
2179 if (!ispointing(state, x, y, ui->sx, ui->sy))
2180 f |= F_DIM;
2181 }
2182 }
2183
2184 if (state->impossible ||
2185 state->nums[i] < 0 || state->flags[i] & FLAG_ERROR)
2186 f |= F_ERROR;
2187 if (state->flags[i] & FLAG_IMMUTABLE)
2188 f |= F_IMMUTABLE;
2189
2190 if (state->next[i] != -1)
2191 f |= F_ARROW_POINT;
2192
2193 if (state->prev[i] != -1) {
2194 /* Currently the direction here is from our square _back_
2195 * to its previous. We could change this to give the opposite
2196 * sense to the direction. */
2197 f |= F_ARROW_INPOINT;
2198 dirp = whichdir(x, y, state->prev[i]%w, state->prev[i]/w);
2199 }
2200
2201 if (state->nums[i] != ds->nums[i] ||
2202 f != ds->f[i] || dirp != ds->dirp[i] ||
2203 force || !ds->started) {
2204 int sign = (ui->gear_mode ? 1 - 2 * ((x ^ y) & 1) : 1);
2205 tile_redraw(dr, ds,
2206 BORDER + x * TILE_SIZE,
2207 BORDER + y * TILE_SIZE,
2208 state->dirs[i], dirp, state->nums[i], f,
2209 sign * angle_offset, -1);
2210 ds->nums[i] = state->nums[i];
2211 ds->f[i] = f;
2212 ds->dirp[i] = dirp;
2213 }
2214 }
2215 }
2216 if (ui->dragging) {
2217 ds->dragging = true;
2218 ds->dx = ui->dx - BLITTER_SIZE/2;
2219 ds->dy = ui->dy - BLITTER_SIZE/2;
2220 blitter_save(dr, ds->dragb, ds->dx, ds->dy);
2221
2222 draw_drag_indicator(dr, ds, state, ui, postdrop != NULL);
2223 }
2224 if (postdrop) free_game(postdrop);
2225 if (!ds->started) ds->started = true;
2226}
2227
2228static float game_anim_length(const game_state *oldstate,
2229 const game_state *newstate, int dir, game_ui *ui)
2230{
2231 return 0.0F;
2232}
2233
2234static float game_flash_length(const game_state *oldstate,
2235 const game_state *newstate, int dir, game_ui *ui)
2236{
2237 if (!oldstate->completed &&
2238 newstate->completed && !newstate->used_solve)
2239 return FLASH_SPIN;
2240 else
2241 return 0.0F;
2242}
2243
2244static void game_get_cursor_location(const game_ui *ui,
2245 const game_drawstate *ds,
2246 const game_state *state,
2247 const game_params *params,
2248 int *x, int *y, int *w, int *h)
2249{
2250 if(ui->cshow) {
2251 *x = COORD(ui->cx);
2252 *y = COORD(ui->cy);
2253 *w = *h = TILE_SIZE;
2254 }
2255}
2256
2257static int game_status(const game_state *state)
2258{
2259 return state->completed ? +1 : 0;
2260}
2261
2262static void game_print_size(const game_params *params, const game_ui *ui,
2263 float *x, float *y)
2264{
2265 int pw, ph;
2266
2267 game_compute_size(params, 1300, ui, &pw, &ph);
2268 *x = pw / 100.0F;
2269 *y = ph / 100.0F;
2270}
2271
2272static void game_print(drawing *dr, const game_state *state, const game_ui *ui,
2273 int tilesize)
2274{
2275 int ink = print_mono_colour(dr, 0);
2276 int x, y;
2277
2278 /* Fake up just enough of a drawstate */
2279 game_drawstate ads, *ds = &ads;
2280 ds->tilesize = tilesize;
2281 ds->n = state->n;
2282
2283 /*
2284 * Border and grid.
2285 */
2286 print_line_width(dr, TILE_SIZE / 40);
2287 for (x = 1; x < state->w; x++)
2288 draw_line(dr, COORD(x), COORD(0), COORD(x), COORD(state->h), ink);
2289 for (y = 1; y < state->h; y++)
2290 draw_line(dr, COORD(0), COORD(y), COORD(state->w), COORD(y), ink);
2291 print_line_width(dr, 2*TILE_SIZE / 40);
2292 draw_rect_outline(dr, COORD(0), COORD(0), TILE_SIZE*state->w,
2293 TILE_SIZE*state->h, ink);
2294
2295 /*
2296 * Arrows and numbers.
2297 */
2298 print_line_width(dr, 0);
2299 for (y = 0; y < state->h; y++)
2300 for (x = 0; x < state->w; x++)
2301 tile_redraw(dr, ds, COORD(x), COORD(y), state->dirs[y*state->w+x],
2302 0, state->nums[y*state->w+x], 0, 0.0, ink);
2303}
2304
2305#ifdef COMBINED
2306#define thegame signpost
2307#endif
2308
2309const struct game thegame = {
2310 "Signpost", "games.signpost", "signpost",
2311 default_params,
2312 game_fetch_preset, NULL,
2313 decode_params,
2314 encode_params,
2315 free_params,
2316 dup_params,
2317 true, game_configure, custom_params,
2318 validate_params,
2319 new_game_desc,
2320 validate_desc,
2321 new_game,
2322 dup_game,
2323 free_game,
2324 true, solve_game,
2325 true, game_can_format_as_text_now, game_text_format,
2326 get_prefs, set_prefs,
2327 new_ui,
2328 free_ui,
2329 NULL, /* encode_ui */
2330 NULL, /* decode_ui */
2331 NULL, /* game_request_keys */
2332 game_changed_state,
2333 current_key_label,
2334 interpret_move,
2335 execute_move,
2336 PREFERRED_TILE_SIZE, game_compute_size, game_set_size,
2337 game_colours,
2338 game_new_drawstate,
2339 game_free_drawstate,
2340 game_redraw,
2341 game_anim_length,
2342 game_flash_length,
2343 game_get_cursor_location,
2344 game_status,
2345 true, false, game_print_size, game_print,
2346 false, /* wants_statusbar */
2347 false, NULL, /* timing_state */
2348 REQUIRE_RBUTTON, /* flags */
2349};
2350
2351#ifdef STANDALONE_SOLVER
2352
2353#include <time.h>
2354#include <stdarg.h>
2355
2356static const char *quis = NULL;
2357
2358static void usage(FILE *out) {
2359 fprintf(out, "usage: %s [--stdin] [--soak] [--seed SEED] <params>|<game id>\n", quis);
2360}
2361
2362static void cycle_seed(char **seedstr, random_state *rs)
2363{
2364 char newseed[16];
2365 int j;
2366
2367 newseed[15] = '\0';
2368 newseed[0] = '1' + (char)random_upto(rs, 9);
2369 for (j = 1; j < 15; j++)
2370 newseed[j] = '0' + (char)random_upto(rs, 10);
2371 sfree(*seedstr);
2372 *seedstr = dupstr(newseed);
2373}
2374
2375static void start_soak(game_params *p, char *seedstr)
2376{
2377 time_t tt_start, tt_now, tt_last;
2378 char *desc, *aux;
2379 random_state *rs;
2380 long n = 0, nnums = 0, i;
2381 game_state *state;
2382
2383 tt_start = tt_now = time(NULL);
2384 printf("Soak-generating a %dx%d grid.\n", p->w, p->h);
2385
2386 while (1) {
2387 rs = random_new(seedstr, strlen(seedstr));
2388 desc = thegame.new_desc(p, rs, &aux, 0);
2389
2390 state = thegame.new_game(NULL, p, desc);
2391 for (i = 0; i < state->n; i++) {
2392 if (state->flags[i] & FLAG_IMMUTABLE)
2393 nnums++;
2394 }
2395 thegame.free_game(state);
2396
2397 sfree(desc);
2398 cycle_seed(&seedstr, rs);
2399 random_free(rs);
2400
2401 n++;
2402 tt_last = time(NULL);
2403 if (tt_last > tt_now) {
2404 tt_now = tt_last;
2405 printf("%ld total, %3.1f/s, %3.1f nums/grid (%3.1f%%).\n",
2406 n,
2407 (double)n / ((double)tt_now - tt_start),
2408 (double)nnums / (double)n,
2409 ((double)nnums * 100.0) / ((double)n * (double)p->w * (double)p->h) );
2410 }
2411 }
2412}
2413
2414static void process_desc(char *id)
2415{
2416 char *desc, *solvestr;
2417 const char *err;
2418 game_params *p;
2419 game_state *s;
2420
2421 printf("%s\n ", id);
2422
2423 desc = strchr(id, ':');
2424 if (!desc) {
2425 fprintf(stderr, "%s: expecting game description.", quis);
2426 exit(1);
2427 }
2428
2429 *desc++ = '\0';
2430
2431 p = thegame.default_params();
2432 thegame.decode_params(p, id);
2433 err = thegame.validate_params(p, 1);
2434 if (err) {
2435 fprintf(stderr, "%s: %s", quis, err);
2436 thegame.free_params(p);
2437 return;
2438 }
2439
2440 err = thegame.validate_desc(p, desc);
2441 if (err) {
2442 fprintf(stderr, "%s: %s\nDescription: %s\n", quis, err, desc);
2443 thegame.free_params(p);
2444 return;
2445 }
2446
2447 s = thegame.new_game(NULL, p, desc);
2448
2449 solvestr = thegame.solve(s, s, NULL, &err);
2450 if (!solvestr)
2451 fprintf(stderr, "%s\n", err);
2452 else
2453 printf("Puzzle is soluble.\n");
2454
2455 thegame.free_game(s);
2456 thegame.free_params(p);
2457}
2458
2459int main(int argc, char *argv[])
2460{
2461 char *id = NULL, *desc, *aux = NULL;
2462 const char *err;
2463 bool soak = false, verbose = false, stdin_desc = false;
2464 int n = 1, i;
2465 char *seedstr = NULL, newseed[16];
2466
2467 setvbuf(stdout, NULL, _IONBF, 0);
2468
2469 quis = argv[0];
2470 while (--argc > 0) {
2471 char *p = (char*)(*++argv);
2472 if (!strcmp(p, "-v") || !strcmp(p, "--verbose"))
2473 verbose = true;
2474 else if (!strcmp(p, "--stdin"))
2475 stdin_desc = true;
2476 else if (!strcmp(p, "-e") || !strcmp(p, "--seed")) {
2477 seedstr = dupstr(*++argv);
2478 argc--;
2479 } else if (!strcmp(p, "-n") || !strcmp(p, "--number")) {
2480 n = atoi(*++argv);
2481 argc--;
2482 } else if (!strcmp(p, "-s") || !strcmp(p, "--soak")) {
2483 soak = true;
2484 } else if (*p == '-') {
2485 fprintf(stderr, "%s: unrecognised option `%s'\n", argv[0], p);
2486 usage(stderr);
2487 exit(1);
2488 } else {
2489 id = p;
2490 }
2491 }
2492
2493 sprintf(newseed, "%lu", (unsigned long) time(NULL));
2494 seedstr = dupstr(newseed);
2495
2496 if (id || !stdin_desc) {
2497 if (id && strchr(id, ':')) {
2498 /* Parameters and description passed on cmd-line:
2499 * try and solve it. */
2500 process_desc(id);
2501 } else {
2502 /* No description passed on cmd-line: decode parameters
2503 * (with optional seed too) */
2504
2505 game_params *p = thegame.default_params();
2506
2507 if (id) {
2508 char *cmdseed = strchr(id, '#');
2509 if (cmdseed) {
2510 *cmdseed++ = '\0';
2511 sfree(seedstr);
2512 seedstr = dupstr(cmdseed);
2513 }
2514
2515 thegame.decode_params(p, id);
2516 }
2517
2518 err = thegame.validate_params(p, 1);
2519 if (err) {
2520 fprintf(stderr, "%s: %s", quis, err);
2521 thegame.free_params(p);
2522 exit(1);
2523 }
2524
2525 /* We have a set of valid parameters; either soak with it
2526 * or generate a single game description and print to stdout. */
2527 if (soak)
2528 start_soak(p, seedstr);
2529 else {
2530 char *pstring = thegame.encode_params(p, 0);
2531
2532 for (i = 0; i < n; i++) {
2533 random_state *rs = random_new(seedstr, strlen(seedstr));
2534
2535 if (verbose) printf("%s#%s\n", pstring, seedstr);
2536 desc = thegame.new_desc(p, rs, &aux, 0);
2537 printf("%s:%s\n", pstring, desc);
2538 sfree(desc);
2539
2540 cycle_seed(&seedstr, rs);
2541
2542 random_free(rs);
2543 }
2544
2545 sfree(pstring);
2546 }
2547 thegame.free_params(p);
2548 }
2549 }
2550
2551 if (stdin_desc) {
2552 char buf[4096];
2553
2554 while (fgets(buf, sizeof(buf), stdin)) {
2555 buf[strcspn(buf, "\r\n")] = '\0';
2556 process_desc(buf);
2557 }
2558 }
2559 sfree(seedstr);
2560
2561 return 0;
2562}
2563
2564#endif
2565
2566
2567/* vim: set shiftwidth=4 tabstop=8: */