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