2 * signpost.c: implementation of the janko game 'arrow path'
14 #define PREFERRED_TILE_SIZE 48
15 #define TILE_SIZE (ds->tilesize)
16 #define BLITTER_SIZE TILE_SIZE
17 #define BORDER (TILE_SIZE / 2)
19 #define COORD(x) ( (x) * TILE_SIZE + BORDER )
20 #define FROMCOORD(x) ( ((x) - BORDER + TILE_SIZE) / TILE_SIZE - 1 )
22 #define INGRID(s,x,y) ((x) >= 0 && (x) < (s)->w && (y) >= 0 && (y) < (s)->h)
24 #define FLASH_SPIN 0.7F
26 #define NBACKGROUNDS 16
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
42 int force_corner_start
;
45 enum { DIR_N
= 0, DIR_NE
, DIR_E
, DIR_SE
, DIR_S
, DIR_SW
, DIR_W
, DIR_NW
, DIR_MAX
};
46 static const char *dirstrings
[8] = { "N ", "NE", "E ", "SE", "S ", "SW", "W ", "NW" };
48 static const int dxs
[DIR_MAX
] = { 0, 1, 1, 1, 0, -1, -1, -1 };
49 static const int dys
[DIR_MAX
] = { -1, -1, 0, 1, 1, 1, 0, -1 };
51 #define DIR_OPPOSITE(d) ((d+4)%8)
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) */
64 #define FLAG_IMMUTABLE 1
67 /* --- Generally useful functions --- */
69 #define ISREALNUM(state, num) ((num) > 0 && (num) <= (state)->n)
71 static int whichdir(int fromx
, int fromy
, int tox
, int toy
)
78 if (dx
&& dy
&& abs(dx
) != abs(dy
)) return -1;
80 if (dx
) dx
= dx
/ abs(dx
); /* limit to (-1, 0, 1) */
81 if (dy
) dy
= dy
/ abs(dy
); /* ditto */
83 for (i
= 0; i
< DIR_MAX
; i
++) {
84 if (dx
== dxs
[i
] && dy
== dys
[i
]) return i
;
89 static int whichdiri(game_state
*state
, int fromi
, int toi
)
92 return whichdir(fromi
%w
, fromi
/w
, toi
%w
, toi
/w
);
95 static int ispointing(const game_state
*state
, int fromx
, int fromy
,
98 int w
= state
->w
, dir
= state
->dirs
[fromy
*w
+fromx
];
100 /* (by convention) squares do not point to themselves. */
101 if (fromx
== tox
&& fromy
== toy
) return 0;
103 /* the final number points to nothing. */
104 if (state
->nums
[fromy
*w
+ fromx
] == state
->n
) return 0;
107 if (!INGRID(state
, fromx
, fromy
)) return 0;
108 if (fromx
== tox
&& fromy
== toy
) return 1;
109 fromx
+= dxs
[dir
]; fromy
+= dys
[dir
];
111 return 0; /* not reached */
114 static int ispointingi(game_state
*state
, int fromi
, int toi
)
117 return ispointing(state
, fromi
%w
, fromi
/w
, toi
%w
, toi
/w
);
120 /* Taking the number 'num', work out the gap between it and the next
121 * available number up or down (depending on d). Return 1 if the region
122 * at (x,y) will fit in that gap, or 0 otherwise. */
123 static int move_couldfit(const game_state
*state
, int num
, int d
, int x
, int y
)
125 int n
, gap
, i
= y
*state
->w
+x
, sz
;
128 /* The 'gap' is the number of missing numbers in the grid between
129 * our number and the next one in the sequence (up or down), or
130 * the end of the sequence (if we happen not to have 1/n present) */
131 for (n
= num
+ d
, gap
= 0;
132 ISREALNUM(state
, n
) && state
->numsi
[n
] == -1;
133 n
+= d
, gap
++) ; /* empty loop */
136 /* no gap, so the only allowable move is that that directly
137 * links the two numbers. */
139 return (n
== num
+d
) ? 0 : 1;
141 if (state
->prev
[i
] == -1 && state
->next
[i
] == -1)
142 return 1; /* single unconnected square, always OK */
144 sz
= dsf_size(state
->dsf
, i
);
145 return (sz
> gap
) ? 0 : 1;
148 static int isvalidmove(const game_state
*state
, int clever
,
149 int fromx
, int fromy
, int tox
, int toy
)
151 int w
= state
->w
, from
= fromy
*w
+fromx
, to
= toy
*w
+tox
;
154 if (!INGRID(state
, fromx
, fromy
) || !INGRID(state
, tox
, toy
))
157 /* can only move where we point */
158 if (!ispointing(state
, fromx
, fromy
, tox
, toy
))
161 nfrom
= state
->nums
[from
]; nto
= state
->nums
[to
];
163 /* can't move _from_ the preset final number, or _to_ the preset 1. */
164 if (((nfrom
== state
->n
) && (state
->flags
[from
] & FLAG_IMMUTABLE
)) ||
165 ((nto
== 1) && (state
->flags
[to
] & FLAG_IMMUTABLE
)))
168 /* can't create a new connection between cells in the same region
169 * as that would create a loop. */
170 if (dsf_canonify(state
->dsf
, from
) == dsf_canonify(state
->dsf
, to
))
173 /* if both cells are actual numbers, can't drag if we're not
174 * one digit apart. */
175 if (ISREALNUM(state
, nfrom
) && ISREALNUM(state
, nto
)) {
178 } else if (clever
&& ISREALNUM(state
, nfrom
)) {
179 if (!move_couldfit(state
, nfrom
, +1, tox
, toy
))
181 } else if (clever
&& ISREALNUM(state
, nto
)) {
182 if (!move_couldfit(state
, nto
, -1, fromx
, fromy
))
189 static void makelink(game_state
*state
, int from
, int to
)
191 if (state
->next
[from
] != -1)
192 state
->prev
[state
->next
[from
]] = -1;
193 state
->next
[from
] = to
;
195 if (state
->prev
[to
] != -1)
196 state
->next
[state
->prev
[to
]] = -1;
197 state
->prev
[to
] = from
;
200 static int game_can_format_as_text_now(const game_params
*params
)
202 if (params
->w
* params
->h
>= 100) return 0;
206 static char *game_text_format(const game_state
*state
)
208 int len
= state
->h
* 2 * (4*state
->w
+ 1) + state
->h
+ 2;
209 int x
, y
, i
, num
, n
, set
;
212 p
= ret
= snewn(len
, char);
214 for (y
= 0; y
< state
->h
; y
++) {
215 for (x
= 0; x
< state
->h
; x
++) {
217 *p
++ = dirstrings
[state
->dirs
[i
]][0];
218 *p
++ = dirstrings
[state
->dirs
[i
]][1];
219 *p
++ = (state
->flags
[i
] & FLAG_IMMUTABLE
) ? 'I' : ' ';
223 for (x
= 0; x
< state
->h
; x
++) {
225 num
= state
->nums
[i
];
231 n
= num
% (state
->n
+1);
232 set
= num
/ (state
->n
+1);
234 assert(n
<= 99); /* two digits only! */
239 *p
++ = (n
>= 10) ? ('0' + (n
/10)) : ' ';
255 static void debug_state(const char *desc
, game_state
*state
)
259 if (state
->n
>= 100) {
260 debug(("[ no game_text_format for this size ]"));
263 dbg
= game_text_format(state
);
264 debug(("%s\n%s", desc
, dbg
));
270 static void strip_nums(game_state
*state
) {
272 for (i
= 0; i
< state
->n
; i
++) {
273 if (!(state
->flags
[i
] & FLAG_IMMUTABLE
))
276 memset(state
->next
, -1, state
->n
*sizeof(int));
277 memset(state
->prev
, -1, state
->n
*sizeof(int));
278 memset(state
->numsi
, -1, (state
->n
+1)*sizeof(int));
279 dsf_init(state
->dsf
, state
->n
);
282 static int check_nums(game_state
*orig
, game_state
*copy
, int only_immutable
)
285 assert(copy
->n
== orig
->n
);
286 for (i
= 0; i
< copy
->n
; i
++) {
287 if (only_immutable
&& !(copy
->flags
[i
] & FLAG_IMMUTABLE
)) continue;
288 assert(copy
->nums
[i
] >= 0);
289 assert(copy
->nums
[i
] <= copy
->n
);
290 if (copy
->nums
[i
] != orig
->nums
[i
]) {
291 debug(("check_nums: (%d,%d) copy=%d, orig=%d.",
292 i
%orig
->w
, i
/orig
->w
, copy
->nums
[i
], orig
->nums
[i
]));
299 /* --- Game parameter/presets functions --- */
301 static game_params
*default_params(void)
303 game_params
*ret
= snew(game_params
);
305 ret
->force_corner_start
= 1;
310 static const struct game_params signpost_presets
[] = {
319 static int game_fetch_preset(int i
, char **name
, game_params
**params
)
324 if (i
< 0 || i
>= lenof(signpost_presets
))
327 ret
= default_params();
328 *ret
= signpost_presets
[i
];
331 sprintf(buf
, "%dx%d%s", ret
->w
, ret
->h
,
332 ret
->force_corner_start
? "" : ", free ends");
338 static void free_params(game_params
*params
)
343 static game_params
*dup_params(const game_params
*params
)
345 game_params
*ret
= snew(game_params
);
346 *ret
= *params
; /* structure copy */
350 static void decode_params(game_params
*ret
, char const *string
)
352 ret
->w
= ret
->h
= atoi(string
);
353 while (*string
&& isdigit((unsigned char)*string
)) string
++;
354 if (*string
== 'x') {
356 ret
->h
= atoi(string
);
357 while (*string
&& isdigit((unsigned char)*string
)) string
++;
359 ret
->force_corner_start
= 0;
360 if (*string
== 'c') {
362 ret
->force_corner_start
= 1;
367 static char *encode_params(const game_params
*params
, int full
)
372 sprintf(data
, "%dx%d%s", params
->w
, params
->h
,
373 params
->force_corner_start
? "c" : "");
375 sprintf(data
, "%dx%d", params
->w
, params
->h
);
380 static config_item
*game_configure(const game_params
*params
)
385 ret
= snewn(4, config_item
);
387 ret
[0].name
= "Width";
388 ret
[0].type
= C_STRING
;
389 sprintf(buf
, "%d", params
->w
);
390 ret
[0].sval
= dupstr(buf
);
393 ret
[1].name
= "Height";
394 ret
[1].type
= C_STRING
;
395 sprintf(buf
, "%d", params
->h
);
396 ret
[1].sval
= dupstr(buf
);
399 ret
[2].name
= "Start and end in corners";
400 ret
[2].type
= C_BOOLEAN
;
402 ret
[2].ival
= params
->force_corner_start
;
412 static game_params
*custom_params(const config_item
*cfg
)
414 game_params
*ret
= snew(game_params
);
416 ret
->w
= atoi(cfg
[0].sval
);
417 ret
->h
= atoi(cfg
[1].sval
);
418 ret
->force_corner_start
= cfg
[2].ival
;
423 static char *validate_params(const game_params
*params
, int full
)
425 if (params
->w
< 1) return "Width must be at least one";
426 if (params
->h
< 1) return "Height must be at least one";
427 if (full
&& params
->w
== 1 && params
->h
== 1)
428 /* The UI doesn't let us move these from unsolved to solved,
429 * so we disallow generating (but not playing) them. */
430 return "Width and height cannot both be one";
434 /* --- Game description string generation and unpicking --- */
436 static void blank_game_into(game_state
*state
)
438 memset(state
->dirs
, 0, state
->n
*sizeof(int));
439 memset(state
->nums
, 0, state
->n
*sizeof(int));
440 memset(state
->flags
, 0, state
->n
*sizeof(unsigned int));
441 memset(state
->next
, -1, state
->n
*sizeof(int));
442 memset(state
->prev
, -1, state
->n
*sizeof(int));
443 memset(state
->numsi
, -1, (state
->n
+1)*sizeof(int));
446 static game_state
*blank_game(int w
, int h
)
448 game_state
*state
= snew(game_state
);
450 memset(state
, 0, sizeof(game_state
));
455 state
->dirs
= snewn(state
->n
, int);
456 state
->nums
= snewn(state
->n
, int);
457 state
->flags
= snewn(state
->n
, unsigned int);
458 state
->next
= snewn(state
->n
, int);
459 state
->prev
= snewn(state
->n
, int);
460 state
->dsf
= snew_dsf(state
->n
);
461 state
->numsi
= snewn(state
->n
+1, int);
463 blank_game_into(state
);
468 static void dup_game_to(game_state
*to
, const game_state
*from
)
470 to
->completed
= from
->completed
;
471 to
->used_solve
= from
->used_solve
;
472 to
->impossible
= from
->impossible
;
474 memcpy(to
->dirs
, from
->dirs
, to
->n
*sizeof(int));
475 memcpy(to
->flags
, from
->flags
, to
->n
*sizeof(unsigned int));
476 memcpy(to
->nums
, from
->nums
, to
->n
*sizeof(int));
478 memcpy(to
->next
, from
->next
, to
->n
*sizeof(int));
479 memcpy(to
->prev
, from
->prev
, to
->n
*sizeof(int));
481 memcpy(to
->dsf
, from
->dsf
, to
->n
*sizeof(int));
482 memcpy(to
->numsi
, from
->numsi
, (to
->n
+1)*sizeof(int));
485 static game_state
*dup_game(const game_state
*state
)
487 game_state
*ret
= blank_game(state
->w
, state
->h
);
488 dup_game_to(ret
, state
);
492 static void free_game(game_state
*state
)
504 static void unpick_desc(const game_params
*params
, const char *desc
,
505 game_state
**sout
, char **mout
)
507 game_state
*state
= blank_game(params
->w
, params
->h
);
513 msg
= "Game description longer than expected";
518 if (isdigit((unsigned char)c
)) {
519 num
= (num
*10) + (int)(c
-'0');
520 if (num
> state
->n
) {
521 msg
= "Number too large";
524 } else if ((c
-'a') >= 0 && (c
-'a') < DIR_MAX
) {
525 state
->nums
[i
] = num
;
526 state
->flags
[i
] = num
? FLAG_IMMUTABLE
: 0;
529 state
->dirs
[i
] = c
- 'a';
532 msg
= "Game description shorter than expected";
535 msg
= "Game description contains unexpected characters";
541 msg
= "Game description shorter than expected";
546 if (msg
) { /* sth went wrong. */
547 if (mout
) *mout
= msg
;
550 if (mout
) *mout
= NULL
;
551 if (sout
) *sout
= state
;
552 else free_game(state
);
556 static char *generate_desc(game_state
*state
, int issolve
)
561 ret
= NULL
; retlen
= 0;
563 ret
= sresize(ret
, 2, char);
564 ret
[0] = 'S'; ret
[1] = '\0';
567 for (i
= 0; i
< state
->n
; i
++) {
569 k
= sprintf(buf
, "%d%c", state
->nums
[i
], (int)(state
->dirs
[i
]+'a'));
571 k
= sprintf(buf
, "%c", (int)(state
->dirs
[i
]+'a'));
572 ret
= sresize(ret
, retlen
+ k
+ 1, char);
573 strcpy(ret
+ retlen
, buf
);
579 /* --- Game generation --- */
581 /* Fills in preallocated arrays ai (indices) and ad (directions)
582 * showing all non-numbered cells adjacent to index i, returns length */
583 /* This function has been somewhat optimised... */
584 static int cell_adj(game_state
*state
, int i
, int *ai
, int *ad
)
586 int n
= 0, a
, x
, y
, sx
, sy
, dx
, dy
, newi
;
587 int w
= state
->w
, h
= state
->h
;
589 sx
= i
% w
; sy
= i
/ w
;
591 for (a
= 0; a
< DIR_MAX
; a
++) {
593 dx
= dxs
[a
]; dy
= dys
[a
];
596 if (x
< 0 || y
< 0 || x
>= w
|| y
>= h
) break;
599 if (state
->nums
[newi
] == 0) {
609 static int new_game_fill(game_state
*state
, random_state
*rs
,
610 int headi
, int taili
)
612 int nfilled
, an
, ret
= 0, j
;
615 aidx
= snewn(state
->n
, int);
616 adir
= snewn(state
->n
, int);
618 debug(("new_game_fill: headi=%d, taili=%d.", headi
, taili
));
620 memset(state
->nums
, 0, state
->n
*sizeof(int));
622 state
->nums
[headi
] = 1;
623 state
->nums
[taili
] = state
->n
;
625 state
->dirs
[taili
] = 0;
627 assert(state
->n
> 1);
629 while (nfilled
< state
->n
) {
630 /* Try and expand _from_ headi; keep going if there's only one
632 an
= cell_adj(state
, headi
, aidx
, adir
);
634 if (an
== 0) goto done
;
635 j
= random_upto(rs
, an
);
636 state
->dirs
[headi
] = adir
[j
];
637 state
->nums
[aidx
[j
]] = state
->nums
[headi
] + 1;
640 an
= cell_adj(state
, headi
, aidx
, adir
);
643 if (nfilled
== state
->n
) break;
645 /* Try and expand _to_ taili; keep going if there's only one
647 an
= cell_adj(state
, taili
, aidx
, adir
);
649 if (an
== 0) goto done
;
650 j
= random_upto(rs
, an
);
651 state
->dirs
[aidx
[j
]] = DIR_OPPOSITE(adir
[j
]);
652 state
->nums
[aidx
[j
]] = state
->nums
[taili
] - 1;
655 an
= cell_adj(state
, taili
, aidx
, adir
);
658 /* If we get here we have headi and taili set but unconnected
659 * by direction: we need to set headi's direction so as to point
661 state
->dirs
[headi
] = whichdiri(state
, headi
, taili
);
663 /* it could happen that our last two weren't in line; if that's the
664 * case, we have to start again. */
665 if (state
->dirs
[headi
] != -1) ret
= 1;
673 /* Better generator: with the 'generate, sprinkle numbers, solve,
674 * repeat' algorithm we're _never_ generating anything greater than
675 * 6x6, and spending all of our time in new_game_fill (and very little
678 * So, new generator steps:
679 * generate the grid, at random (same as now). Numbers 1 and N get
680 immutable flag immediately.
681 * squirrel that away for the solved state.
683 * (solve:) Try and solve it.
684 * If we solved it, we're done:
685 * generate the description from current immutable numbers,
686 * free stuff that needs freeing,
687 * return description + solved state.
688 * If we didn't solve it:
689 * count #tiles in state we've made deductions about.
691 * randomise a scratch array.
692 * for each index in scratch (in turn):
693 * if the cell isn't empty, continue (through scratch array)
694 * set number + immutable in state.
695 * try and solve state.
696 * if we've solved it, we're done.
697 * otherwise, count #tiles. If it's more than we had before:
698 * good, break from this loop and re-randomise.
699 * otherwise (number didn't help):
700 * remove number and try next in scratch array.
701 * if we've got to the end of the scratch array, no luck:
702 free everything we need to, and go back to regenerate the grid.
705 static int solve_state(game_state
*state
);
707 static void debug_desc(const char *what
, game_state
*state
)
711 char *desc
= generate_desc(state
, 0);
712 debug(("%s game state: %dx%d:%s", what
, state
->w
, state
->h
, desc
));
718 /* Expects a fully-numbered game_state on input, and makes sure
719 * FLAG_IMMUTABLE is only set on those numbers we need to solve
720 * (as for a real new-game); returns 1 if it managed
721 * this (such that it could solve it), or 0 if not. */
722 static int new_game_strip(game_state
*state
, random_state
*rs
)
724 int *scratch
, i
, j
, ret
= 1;
725 game_state
*copy
= dup_game(state
);
727 debug(("new_game_strip."));
730 debug_desc("Stripped", copy
);
732 if (solve_state(copy
) > 0) {
733 debug(("new_game_strip: soluble immediately after strip."));
738 scratch
= snewn(state
->n
, int);
739 for (i
= 0; i
< state
->n
; i
++) scratch
[i
] = i
;
740 shuffle(scratch
, state
->n
, sizeof(int), rs
);
742 /* This is scungy. It might just be quick enough.
743 * It goes through, adding set numbers in empty squares
744 * until either we run out of empty squares (in the one
745 * we're half-solving) or else we solve it properly.
746 * NB that we run the entire solver each time, which
747 * strips the grid beforehand; we will save time if we
749 for (i
= 0; i
< state
->n
; i
++) {
751 if (copy
->nums
[j
] > 0 && copy
->nums
[j
] <= state
->n
)
752 continue; /* already solved to a real number here. */
753 assert(state
->nums
[j
] <= state
->n
);
754 debug(("new_game_strip: testing add IMMUTABLE number %d at square (%d,%d).",
755 state
->nums
[j
], j
%state
->w
, j
/state
->w
));
756 copy
->nums
[j
] = state
->nums
[j
];
757 copy
->flags
[j
] |= FLAG_IMMUTABLE
;
758 state
->flags
[j
] |= FLAG_IMMUTABLE
;
759 debug_state("Copy of state: ", copy
);
761 if (solve_state(copy
) > 0) goto solved
;
762 assert(check_nums(state
, copy
, 1));
768 debug(("new_game_strip: now solved."));
769 /* Since we added basically at random, try now to remove numbers
770 * and see if we can still solve it; if we can (still), really
771 * remove the number. Make sure we don't remove the anchor numbers
773 for (i
= 0; i
< state
->n
; i
++) {
775 if ((state
->flags
[j
] & FLAG_IMMUTABLE
) &&
776 (state
->nums
[j
] != 1 && state
->nums
[j
] != state
->n
)) {
777 debug(("new_game_strip: testing remove IMMUTABLE number %d at square (%d,%d).",
778 state
->nums
[j
], j
%state
->w
, j
/state
->w
));
779 state
->flags
[j
] &= ~FLAG_IMMUTABLE
;
780 dup_game_to(copy
, state
);
782 if (solve_state(copy
) > 0) {
783 assert(check_nums(state
, copy
, 0));
784 debug(("new_game_strip: OK, removing number"));
786 assert(state
->nums
[j
] <= state
->n
);
787 debug(("new_game_strip: cannot solve, putting IMMUTABLE back."));
788 copy
->nums
[j
] = state
->nums
[j
];
789 state
->flags
[j
] |= FLAG_IMMUTABLE
;
795 debug(("new_game_strip: %ssuccessful.", ret
? "" : "not "));
801 static char *new_game_desc(const game_params
*params
, random_state
*rs
,
802 char **aux
, int interactive
)
804 game_state
*state
= blank_game(params
->w
, params
->h
);
808 /* this shouldn't happen (validate_params), but let's play it safe */
809 if (params
->w
== 1 && params
->h
== 1) return dupstr("1a");
812 blank_game_into(state
);
814 /* keep trying until we fill successfully. */
816 if (params
->force_corner_start
) {
821 headi
= random_upto(rs
, state
->n
);
822 taili
= random_upto(rs
, state
->n
);
823 } while (headi
== taili
);
825 } while (!new_game_fill(state
, rs
, headi
, taili
));
827 debug_state("Filled game:", state
);
829 assert(state
->nums
[headi
] <= state
->n
);
830 assert(state
->nums
[taili
] <= state
->n
);
832 state
->flags
[headi
] |= FLAG_IMMUTABLE
;
833 state
->flags
[taili
] |= FLAG_IMMUTABLE
;
835 /* This will have filled in directions and _all_ numbers.
836 * Store the game definition for this, as the solved-state. */
837 if (!new_game_strip(state
, rs
)) {
842 game_state
*tosolve
= dup_game(state
);
843 assert(solve_state(tosolve
) > 0);
846 ret
= generate_desc(state
, 0);
851 static char *validate_desc(const game_params
*params
, const char *desc
)
855 unpick_desc(params
, desc
, NULL
, &ret
);
859 /* --- Linked-list and numbers array --- */
861 /* Assuming numbers are always up-to-date, there are only four possibilities
862 * for regions changing after a single valid move:
864 * 1) two differently-coloured regions being combined (the resulting colouring
865 * should be based on the larger of the two regions)
866 * 2) a numbered region having a single number added to the start (the
867 * region's colour will remain, and the numbers will shift by 1)
868 * 3) a numbered region having a single number added to the end (the
869 * region's colour and numbering remains as-is)
870 * 4) two unnumbered squares being joined (will pick the smallest unused set
871 * of colours to use for the new region).
873 * There should never be any complications with regions containing 3 colours
874 * being combined, since two of those colours should have been merged on a
877 * Most of the complications are in ensuring we don't accidentally set two
878 * regions with the same colour (e.g. if a region was split). If this happens
879 * we always try and give the largest original portion the original colour.
882 #define COLOUR(a) ((a) / (state->n+1))
883 #define START(c) ((c) * (state->n+1))
886 int i
; /* position */
887 int sz
; /* size of region */
888 int start
; /* region start number preferred, or 0 if !preference */
889 int preference
; /* 0 if we have no preference (and should just pick one) */
893 static void head_number(game_state
*state
, int i
, struct head_meta
*head
)
895 int off
= 0, ss
, j
= i
, c
, n
, sz
;
897 /* Insist we really were passed the head of a chain. */
898 assert(state
->prev
[i
] == -1 && state
->next
[i
] != -1);
901 head
->sz
= dsf_size(state
->dsf
, i
);
904 /* Search through this chain looking for real numbers, checking that
905 * they match up (if there are more than one). */
906 head
->preference
= 0;
908 if (state
->flags
[j
] & FLAG_IMMUTABLE
) {
909 ss
= state
->nums
[j
] - off
;
910 if (!head
->preference
) {
912 head
->preference
= 1;
913 head
->why
= "contains cell with immutable number";
914 } else if (head
->start
!= ss
) {
915 debug(("head_number: chain with non-sequential numbers!"));
916 state
->impossible
= 1;
921 assert(j
!= i
); /* we have created a loop, obviously wrong */
923 if (head
->preference
) goto done
;
925 if (state
->nums
[i
] == 0 && state
->nums
[state
->next
[i
]] > state
->n
) {
926 /* (probably) empty cell onto the head of a coloured region:
927 * make sure we start at a 0 offset. */
928 head
->start
= START(COLOUR(state
->nums
[state
->next
[i
]]));
929 head
->preference
= 1;
930 head
->why
= "adding blank cell to head of numbered region";
931 } else if (state
->nums
[i
] <= state
->n
) {
932 /* if we're 0 we're probably just blank -- but even if we're a
933 * (real) numbered region, we don't have an immutable number
934 * in it (any more) otherwise it'd have been caught above, so
935 * reassign the colour. */
937 head
->preference
= 0;
938 head
->why
= "lowest available colour group";
940 c
= COLOUR(state
->nums
[i
]);
942 sz
= dsf_size(state
->dsf
, i
);
944 while (state
->next
[j
] != -1) {
946 if (state
->nums
[j
] == 0 && state
->next
[j
] == -1) {
947 head
->start
= START(c
);
948 head
->preference
= 1;
949 head
->why
= "adding blank cell to end of numbered region";
952 if (COLOUR(state
->nums
[j
]) == c
)
955 int start_alternate
= START(COLOUR(state
->nums
[j
]));
957 head
->start
= start_alternate
;
958 head
->preference
= 1;
959 head
->why
= "joining two coloured regions, swapping to larger colour";
961 head
->start
= START(c
);
962 head
->preference
= 1;
963 head
->why
= "joining two coloured regions, taking largest";
968 /* If we got here then we may have split a region into
969 * two; make sure we don't assign a colour we've already used. */
971 /* not convinced this shouldn't be an assertion failure here. */
973 head
->preference
= 0;
975 head
->start
= START(c
);
976 head
->preference
= 1;
978 head
->why
= "got to end of coloured region";
982 assert(head
->why
!= NULL
);
983 if (head
->preference
)
984 debug(("Chain at (%d,%d) numbered for preference at %d (colour %d): %s.",
985 head
->i
%state
->w
, head
->i
/state
->w
,
986 head
->start
, COLOUR(head
->start
), head
->why
));
988 debug(("Chain at (%d,%d) using next available colour: %s.",
989 head
->i
%state
->w
, head
->i
/state
->w
,
994 static void debug_numbers(game_state
*state
)
998 for (i
= 0; i
< state
->n
; i
++) {
999 debug(("(%d,%d) --> (%d,%d) --> (%d,%d)",
1000 state
->prev
[i
]==-1 ? -1 : state
->prev
[i
]%w
,
1001 state
->prev
[i
]==-1 ? -1 : state
->prev
[i
]/w
,
1003 state
->next
[i
]==-1 ? -1 : state
->next
[i
]%w
,
1004 state
->next
[i
]==-1 ? -1 : state
->next
[i
]/w
));
1010 static void connect_numbers(game_state
*state
)
1014 dsf_init(state
->dsf
, state
->n
);
1015 for (i
= 0; i
< state
->n
; i
++) {
1016 if (state
->next
[i
] != -1) {
1017 assert(state
->prev
[state
->next
[i
]] == i
);
1018 di
= dsf_canonify(state
->dsf
, i
);
1019 dni
= dsf_canonify(state
->dsf
, state
->next
[i
]);
1021 debug(("connect_numbers: chain forms a loop."));
1022 state
->impossible
= 1;
1024 dsf_merge(state
->dsf
, di
, dni
);
1029 static int compare_heads(const void *a
, const void *b
)
1031 struct head_meta
*ha
= (struct head_meta
*)a
;
1032 struct head_meta
*hb
= (struct head_meta
*)b
;
1034 /* Heads with preferred colours first... */
1035 if (ha
->preference
&& !hb
->preference
) return -1;
1036 if (hb
->preference
&& !ha
->preference
) return 1;
1038 /* ...then heads with low colours first... */
1039 if (ha
->start
< hb
->start
) return -1;
1040 if (ha
->start
> hb
->start
) return 1;
1042 /* ... then large regions first... */
1043 if (ha
->sz
> hb
->sz
) return -1;
1044 if (ha
->sz
< hb
->sz
) return 1;
1046 /* ... then position. */
1047 if (ha
->i
> hb
->i
) return -1;
1048 if (ha
->i
< hb
->i
) return 1;
1053 static int lowest_start(game_state
*state
, struct head_meta
*heads
, int nheads
)
1057 /* NB start at 1: colour 0 is real numbers */
1058 for (c
= 1; c
< state
->n
; c
++) {
1059 for (n
= 0; n
< nheads
; n
++) {
1060 if (COLOUR(heads
[n
].start
) == c
)
1067 assert(!"No available colours!");
1071 static void update_numbers(game_state
*state
)
1073 int i
, j
, n
, nnum
, nheads
;
1074 struct head_meta
*heads
= snewn(state
->n
, struct head_meta
);
1076 for (n
= 0; n
< state
->n
; n
++)
1077 state
->numsi
[n
] = -1;
1079 for (i
= 0; i
< state
->n
; i
++) {
1080 if (state
->flags
[i
] & FLAG_IMMUTABLE
) {
1081 assert(state
->nums
[i
] > 0);
1082 assert(state
->nums
[i
] <= state
->n
);
1083 state
->numsi
[state
->nums
[i
]] = i
;
1085 else if (state
->prev
[i
] == -1 && state
->next
[i
] == -1)
1088 connect_numbers(state
);
1090 /* Construct an array of the heads of all current regions, together
1091 * with their preferred colours. */
1093 for (i
= 0; i
< state
->n
; i
++) {
1094 /* Look for a cell that is the start of a chain
1095 * (has a next but no prev). */
1096 if (state
->prev
[i
] != -1 || state
->next
[i
] == -1) continue;
1098 head_number(state
, i
, &heads
[nheads
++]);
1102 * - heads with preferred colours first, then
1103 * - heads with low colours first, then
1104 * - large regions first
1106 qsort(heads
, nheads
, sizeof(struct head_meta
), compare_heads
);
1108 /* Remove duplicate-coloured regions. */
1109 for (n
= nheads
-1; n
>= 0; n
--) { /* order is important! */
1110 if ((n
!= 0) && (heads
[n
].start
== heads
[n
-1].start
)) {
1111 /* We have a duplicate-coloured region: since we're
1112 * sorted in size order and this is not the first
1113 * of its colour it's not the largest: recolour it. */
1114 heads
[n
].start
= START(lowest_start(state
, heads
, nheads
));
1115 heads
[n
].preference
= -1; /* '-1' means 'was duplicate' */
1117 else if (!heads
[n
].preference
) {
1118 assert(heads
[n
].start
== 0);
1119 heads
[n
].start
= START(lowest_start(state
, heads
, nheads
));
1123 debug(("Region colouring after duplicate removal:"));
1125 for (n
= 0; n
< nheads
; n
++) {
1126 debug((" Chain at (%d,%d) sz %d numbered at %d (colour %d): %s%s",
1127 heads
[n
].i
% state
->w
, heads
[n
].i
/ state
->w
, heads
[n
].sz
,
1128 heads
[n
].start
, COLOUR(heads
[n
].start
), heads
[n
].why
,
1129 heads
[n
].preference
== 0 ? " (next available)" :
1130 heads
[n
].preference
< 0 ? " (duplicate, next available)" : ""));
1132 nnum
= heads
[n
].start
;
1135 if (!(state
->flags
[j
] & FLAG_IMMUTABLE
)) {
1136 if (nnum
> 0 && nnum
<= state
->n
)
1137 state
->numsi
[nnum
] = j
;
1138 state
->nums
[j
] = nnum
;
1142 assert(j
!= heads
[n
].i
); /* loop?! */
1145 /*debug_numbers(state);*/
1149 static int check_completion(game_state
*state
, int mark_errors
)
1151 int n
, j
, k
, error
= 0, complete
;
1153 /* NB This only marks errors that are possible to perpetrate with
1154 * the current UI in interpret_move. Things like forming loops in
1155 * linked sections and having numbers not add up should be forbidden
1156 * by the code elsewhere, so we don't bother marking those (because
1157 * it would add lots of tricky drawing code for very little gain). */
1159 for (j
= 0; j
< state
->n
; j
++)
1160 state
->flags
[j
] &= ~FLAG_ERROR
;
1163 /* Search for repeated numbers. */
1164 for (j
= 0; j
< state
->n
; j
++) {
1165 if (state
->nums
[j
] > 0 && state
->nums
[j
] <= state
->n
) {
1166 for (k
= j
+1; k
< state
->n
; k
++) {
1167 if (state
->nums
[k
] == state
->nums
[j
]) {
1169 state
->flags
[j
] |= FLAG_ERROR
;
1170 state
->flags
[k
] |= FLAG_ERROR
;
1178 /* Search and mark numbers n not pointing to n+1; if any numbers
1179 * are missing we know we've not completed. */
1181 for (n
= 1; n
< state
->n
; n
++) {
1182 if (state
->numsi
[n
] == -1 || state
->numsi
[n
+1] == -1)
1184 else if (!ispointingi(state
, state
->numsi
[n
], state
->numsi
[n
+1])) {
1186 state
->flags
[state
->numsi
[n
]] |= FLAG_ERROR
;
1187 state
->flags
[state
->numsi
[n
+1]] |= FLAG_ERROR
;
1191 /* make sure the link is explicitly made here; for instance, this
1192 * is nice if the user drags from 2 out (making 3) and a 4 is also
1193 * visible; this ensures that the link from 3 to 4 is also made. */
1195 makelink(state
, state
->numsi
[n
], state
->numsi
[n
+1]);
1199 /* Search and mark numbers less than 0, or 0 with links. */
1200 for (n
= 1; n
< state
->n
; n
++) {
1201 if ((state
->nums
[n
] < 0) ||
1202 (state
->nums
[n
] == 0 &&
1203 (state
->next
[n
] != -1 || state
->prev
[n
] != -1))) {
1206 state
->flags
[n
] |= FLAG_ERROR
;
1210 if (error
) return 0;
1213 static game_state
*new_game(midend
*me
, const game_params
*params
,
1216 game_state
*state
= NULL
;
1218 unpick_desc(params
, desc
, &state
, NULL
);
1219 if (!state
) assert(!"new_game failed to unpick");
1221 update_numbers(state
);
1222 check_completion(state
, 1); /* update any auto-links */
1227 /* --- Solver --- */
1229 /* If a tile has a single tile it can link _to_, or there's only a single
1230 * location that can link to a given tile, fill that link in. */
1231 static int solve_single(game_state
*state
, game_state
*copy
, int *from
)
1233 int i
, j
, sx
, sy
, x
, y
, d
, poss
, w
=state
->w
, nlinks
= 0;
1235 /* The from array is a list of 'which square can link _to_ us';
1236 * we start off with from as '-1' (meaning 'not found'); if we find
1237 * something that can link to us it is set to that index, and then if
1238 * we find another we set it to -2. */
1240 memset(from
, -1, state
->n
*sizeof(int));
1242 /* poss is 'can I link to anything' with the same meanings. */
1244 for (i
= 0; i
< state
->n
; i
++) {
1245 if (state
->next
[i
] != -1) continue;
1246 if (state
->nums
[i
] == state
->n
) continue; /* no next from last no. */
1250 sx
= x
= i
%w
; sy
= y
= i
/w
;
1252 x
+= dxs
[d
]; y
+= dys
[d
];
1253 if (!INGRID(state
, x
, y
)) break;
1254 if (!isvalidmove(state
, 1, sx
, sy
, x
, y
)) continue;
1256 /* can't link to somewhere with a back-link we would have to
1257 * break (the solver just doesn't work like this). */
1259 if (state
->prev
[j
] != -1) continue;
1261 if (state
->nums
[i
] > 0 && state
->nums
[j
] > 0 &&
1262 state
->nums
[i
] <= state
->n
&& state
->nums
[j
] <= state
->n
&&
1263 state
->nums
[j
] == state
->nums
[i
]+1) {
1264 debug(("Solver: forcing link through existing consecutive numbers."));
1270 /* if there's been a valid move already, we have to move on;
1271 * we can't make any deductions here. */
1272 poss
= (poss
== -1) ? j
: -2;
1274 /* Modify the from array as described above (which is enumerating
1275 * what points to 'j' in a similar way). */
1276 from
[j
] = (from
[j
] == -1) ? i
: -2;
1279 /*debug(("Solver: (%d,%d) has multiple possible next squares.", sx, sy));*/
1281 } else if (poss
== -1) {
1282 debug(("Solver: nowhere possible for (%d,%d) to link to.", sx
, sy
));
1283 copy
->impossible
= 1;
1286 debug(("Solver: linking (%d,%d) to only possible next (%d,%d).",
1287 sx
, sy
, poss
%w
, poss
/w
));
1288 makelink(copy
, i
, poss
);
1293 for (i
= 0; i
< state
->n
; i
++) {
1294 if (state
->prev
[i
] != -1) continue;
1295 if (state
->nums
[i
] == 1) continue; /* no prev from 1st no. */
1298 if (from
[i
] == -1) {
1299 debug(("Solver: nowhere possible to link to (%d,%d)", x
, y
));
1300 copy
->impossible
= 1;
1302 } else if (from
[i
] == -2) {
1303 /*debug(("Solver: (%d,%d) has multiple possible prev squares.", x, y));*/
1306 debug(("Solver: linking only possible prev (%d,%d) to (%d,%d).",
1307 from
[i
]%w
, from
[i
]/w
, x
, y
));
1308 makelink(copy
, from
[i
], i
);
1316 /* Returns 1 if we managed to solve it, 0 otherwise. */
1317 static int solve_state(game_state
*state
)
1319 game_state
*copy
= dup_game(state
);
1320 int *scratch
= snewn(state
->n
, int), ret
;
1322 debug_state("Before solver: ", state
);
1325 update_numbers(state
);
1327 if (solve_single(state
, copy
, scratch
)) {
1328 dup_game_to(state
, copy
);
1329 if (state
->impossible
) break; else continue;
1336 update_numbers(state
);
1337 ret
= state
->impossible
? -1 : check_completion(state
, 0);
1338 debug(("Solver finished: %s",
1339 ret
< 0 ? "impossible" : ret
> 0 ? "solved" : "not solved"));
1340 debug_state("After solver: ", state
);
1344 static char *solve_game(const game_state
*state
, const game_state
*currstate
,
1345 const char *aux
, char **error
)
1347 game_state
*tosolve
;
1351 tosolve
= dup_game(currstate
);
1352 result
= solve_state(tosolve
);
1354 ret
= generate_desc(tosolve
, 1);
1356 if (ret
) return ret
;
1358 tosolve
= dup_game(state
);
1359 result
= solve_state(tosolve
);
1361 *error
= "Puzzle is impossible.";
1362 else if (result
== 0)
1363 *error
= "Unable to solve puzzle.";
1365 ret
= generate_desc(tosolve
, 1);
1372 /* --- UI and move routines. --- */
1378 int dragging
, drag_is_from
;
1379 int sx
, sy
; /* grid coords of start cell */
1380 int dx
, dy
; /* pixel coords of drag posn */
1383 static game_ui
*new_ui(const game_state
*state
)
1385 game_ui
*ui
= snew(game_ui
);
1387 /* NB: if this is ever changed to as to require more than a structure
1388 * copy to clone, there's code that needs fixing in game_redraw too. */
1390 ui
->cx
= ui
->cy
= ui
->cshow
= 0;
1393 ui
->sx
= ui
->sy
= ui
->dx
= ui
->dy
= 0;
1398 static void free_ui(game_ui
*ui
)
1403 static char *encode_ui(const game_ui
*ui
)
1408 static void decode_ui(game_ui
*ui
, const char *encoding
)
1412 static void game_changed_state(game_ui
*ui
, const game_state
*oldstate
,
1413 const game_state
*newstate
)
1415 if (!oldstate
->completed
&& newstate
->completed
)
1416 ui
->cshow
= ui
->dragging
= 0;
1419 struct game_drawstate
{
1420 int tilesize
, started
, solved
;
1424 double angle_offset
;
1426 int dragging
, dx
, dy
;
1430 static char *interpret_move(const game_state
*state
, game_ui
*ui
,
1431 const game_drawstate
*ds
,
1432 int mx
, int my
, int button
)
1434 int x
= FROMCOORD(mx
), y
= FROMCOORD(my
), w
= state
->w
;
1437 if (IS_CURSOR_MOVE(button
)) {
1438 move_cursor(button
, &ui
->cx
, &ui
->cy
, state
->w
, state
->h
, 0);
1441 ui
->dx
= COORD(ui
->cx
) + TILE_SIZE
/2;
1442 ui
->dy
= COORD(ui
->cy
) + TILE_SIZE
/2;
1445 } else if (IS_CURSOR_SELECT(button
)) {
1448 else if (ui
->dragging
) {
1449 ui
->dragging
= FALSE
;
1450 if (ui
->sx
== ui
->cx
&& ui
->sy
== ui
->cy
) return "";
1451 if (ui
->drag_is_from
) {
1452 if (!isvalidmove(state
, 0, ui
->sx
, ui
->sy
, ui
->cx
, ui
->cy
)) return "";
1453 sprintf(buf
, "L%d,%d-%d,%d", ui
->sx
, ui
->sy
, ui
->cx
, ui
->cy
);
1455 if (!isvalidmove(state
, 0, ui
->cx
, ui
->cy
, ui
->sx
, ui
->sy
)) return "";
1456 sprintf(buf
, "L%d,%d-%d,%d", ui
->cx
, ui
->cy
, ui
->sx
, ui
->sy
);
1460 ui
->dragging
= TRUE
;
1463 ui
->dx
= COORD(ui
->cx
) + TILE_SIZE
/2;
1464 ui
->dy
= COORD(ui
->cy
) + TILE_SIZE
/2;
1465 ui
->drag_is_from
= (button
== CURSOR_SELECT
) ? 1 : 0;
1469 if (IS_MOUSE_DOWN(button
)) {
1471 ui
->cshow
= ui
->dragging
= 0;
1473 assert(!ui
->dragging
);
1474 if (!INGRID(state
, x
, y
)) return NULL
;
1476 if (button
== LEFT_BUTTON
) {
1477 /* disallow dragging from the final number. */
1478 if ((state
->nums
[y
*w
+x
] == state
->n
) &&
1479 (state
->flags
[y
*w
+x
] & FLAG_IMMUTABLE
))
1481 } else if (button
== RIGHT_BUTTON
) {
1482 /* disallow dragging to the first number. */
1483 if ((state
->nums
[y
*w
+x
] == 1) &&
1484 (state
->flags
[y
*w
+x
] & FLAG_IMMUTABLE
))
1488 ui
->dragging
= TRUE
;
1489 ui
->drag_is_from
= (button
== LEFT_BUTTON
) ? 1 : 0;
1496 } else if (IS_MOUSE_DRAG(button
) && ui
->dragging
) {
1500 } else if (IS_MOUSE_RELEASE(button
) && ui
->dragging
) {
1501 ui
->dragging
= FALSE
;
1502 if (ui
->sx
== x
&& ui
->sy
== y
) return ""; /* single click */
1504 if (!INGRID(state
, x
, y
)) {
1505 int si
= ui
->sy
*w
+ui
->sx
;
1506 if (state
->prev
[si
] == -1 && state
->next
[si
] == -1)
1508 sprintf(buf
, "%c%d,%d",
1509 (int)(ui
->drag_is_from
? 'C' : 'X'), ui
->sx
, ui
->sy
);
1513 if (ui
->drag_is_from
) {
1514 if (!isvalidmove(state
, 0, ui
->sx
, ui
->sy
, x
, y
)) return "";
1515 sprintf(buf
, "L%d,%d-%d,%d", ui
->sx
, ui
->sy
, x
, y
);
1517 if (!isvalidmove(state
, 0, x
, y
, ui
->sx
, ui
->sy
)) return "";
1518 sprintf(buf
, "L%d,%d-%d,%d", x
, y
, ui
->sx
, ui
->sy
);
1521 } /* else if (button == 'H' || button == 'h')
1522 return dupstr("H"); */
1523 else if ((button
== 'x' || button
== 'X') && ui
->cshow
) {
1524 int si
= ui
->cy
*w
+ ui
->cx
;
1525 if (state
->prev
[si
] == -1 && state
->next
[si
] == -1)
1527 sprintf(buf
, "%c%d,%d",
1528 (int)((button
== 'x') ? 'C' : 'X'), ui
->cx
, ui
->cy
);
1535 static void unlink_cell(game_state
*state
, int si
)
1537 debug(("Unlinking (%d,%d).", si
%state
->w
, si
/state
->w
));
1538 if (state
->prev
[si
] != -1) {
1539 debug((" ... removing prev link from (%d,%d).",
1540 state
->prev
[si
]%state
->w
, state
->prev
[si
]/state
->w
));
1541 state
->next
[state
->prev
[si
]] = -1;
1542 state
->prev
[si
] = -1;
1544 if (state
->next
[si
] != -1) {
1545 debug((" ... removing next link to (%d,%d).",
1546 state
->next
[si
]%state
->w
, state
->next
[si
]/state
->w
));
1547 state
->prev
[state
->next
[si
]] = -1;
1548 state
->next
[si
] = -1;
1552 static game_state
*execute_move(const game_state
*state
, const char *move
)
1554 game_state
*ret
= NULL
;
1555 int sx
, sy
, ex
, ey
, si
, ei
, w
= state
->w
;
1558 debug(("move: %s", move
));
1560 if (move
[0] == 'S') {
1566 p
.w
= state
->w
; p
.h
= state
->h
;
1567 valid
= validate_desc(&p
, move
+1);
1569 debug(("execute_move: move not valid: %s", valid
));
1572 ret
= dup_game(state
);
1573 tmp
= new_game(NULL
, &p
, move
+1);
1574 for (i
= 0; i
< state
->n
; i
++) {
1575 ret
->prev
[i
] = tmp
->prev
[i
];
1576 ret
->next
[i
] = tmp
->next
[i
];
1579 ret
->used_solve
= 1;
1580 } else if (sscanf(move
, "L%d,%d-%d,%d", &sx
, &sy
, &ex
, &ey
) == 4) {
1581 if (!isvalidmove(state
, 0, sx
, sy
, ex
, ey
)) return NULL
;
1583 ret
= dup_game(state
);
1585 si
= sy
*w
+sx
; ei
= ey
*w
+ex
;
1586 makelink(ret
, si
, ei
);
1587 } else if (sscanf(move
, "%c%d,%d", &c
, &sx
, &sy
) == 3) {
1590 if (c
!= 'C' && c
!= 'X') return NULL
;
1591 if (!INGRID(state
, sx
, sy
)) return NULL
;
1593 if (state
->prev
[si
] == -1 && state
->next
[si
] == -1)
1596 ret
= dup_game(state
);
1598 sset
= state
->nums
[si
] / (state
->n
+1);
1599 if (c
== 'C' || (c
== 'X' && sset
== 0)) {
1600 /* Unlink the single cell we dragged from the board. */
1601 unlink_cell(ret
, si
);
1604 for (i
= 0; i
< state
->n
; i
++) {
1605 /* Unlink all cells in the same set as the one we dragged
1606 * from the board. */
1608 if (state
->nums
[i
] == 0) continue;
1609 set
= state
->nums
[i
] / (state
->n
+1);
1610 if (set
!= sset
) continue;
1612 unlink_cell(ret
, i
);
1615 } else if (strcmp(move
, "H") == 0) {
1616 ret
= dup_game(state
);
1620 update_numbers(ret
);
1621 if (check_completion(ret
, 1)) ret
->completed
= 1;
1627 /* ----------------------------------------------------------------------
1631 static void game_compute_size(const game_params
*params
, int tilesize
,
1634 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
1635 struct { int tilesize
, order
; } ads
, *ds
= &ads
;
1636 ads
.tilesize
= tilesize
;
1638 *x
= TILE_SIZE
* params
->w
+ 2 * BORDER
;
1639 *y
= TILE_SIZE
* params
->h
+ 2 * BORDER
;
1642 static void game_set_size(drawing
*dr
, game_drawstate
*ds
,
1643 const game_params
*params
, int tilesize
)
1645 ds
->tilesize
= tilesize
;
1646 assert(TILE_SIZE
> 0);
1649 ds
->dragb
= blitter_new(dr
, BLITTER_SIZE
, BLITTER_SIZE
);
1652 /* Colours chosen from the webby palette to work as a background to black text,
1653 * W then some plausible approximation to pastelly ROYGBIV; we then interpolate
1654 * between consecutive pairs to give another 8 (and then the drawing routine
1655 * will reuse backgrounds). */
1656 static const unsigned long bgcols
[8] = {
1657 0xffffff, /* white */
1658 0xffa07a, /* lightsalmon */
1659 0x98fb98, /* green */
1660 0x7fffd4, /* aquamarine */
1661 0x9370db, /* medium purple */
1662 0xffa500, /* orange */
1663 0x87cefa, /* lightskyblue */
1664 0xffff00, /* yellow */
1667 static float *game_colours(frontend
*fe
, int *ncolours
)
1669 float *ret
= snewn(3 * NCOLOURS
, float);
1672 game_mkhighlight(fe
, ret
, COL_BACKGROUND
, COL_HIGHLIGHT
, COL_LOWLIGHT
);
1674 for (i
= 0; i
< 3; i
++) {
1675 ret
[COL_NUMBER
* 3 + i
] = 0.0F
;
1676 ret
[COL_ARROW
* 3 + i
] = 0.0F
;
1677 ret
[COL_CURSOR
* 3 + i
] = ret
[COL_BACKGROUND
* 3 + i
] / 2.0F
;
1678 ret
[COL_GRID
* 3 + i
] = ret
[COL_BACKGROUND
* 3 + i
] / 1.3F
;
1680 ret
[COL_NUMBER_SET
* 3 + 0] = 0.0F
;
1681 ret
[COL_NUMBER_SET
* 3 + 1] = 0.0F
;
1682 ret
[COL_NUMBER_SET
* 3 + 2] = 0.9F
;
1684 ret
[COL_ERROR
* 3 + 0] = 1.0F
;
1685 ret
[COL_ERROR
* 3 + 1] = 0.0F
;
1686 ret
[COL_ERROR
* 3 + 2] = 0.0F
;
1688 ret
[COL_DRAG_ORIGIN
* 3 + 0] = 0.2F
;
1689 ret
[COL_DRAG_ORIGIN
* 3 + 1] = 1.0F
;
1690 ret
[COL_DRAG_ORIGIN
* 3 + 2] = 0.2F
;
1692 for (c
= 0; c
< 8; c
++) {
1693 ret
[(COL_B0
+ c
) * 3 + 0] = (float)((bgcols
[c
] & 0xff0000) >> 16) / 256.0F
;
1694 ret
[(COL_B0
+ c
) * 3 + 1] = (float)((bgcols
[c
] & 0xff00) >> 8) / 256.0F
;
1695 ret
[(COL_B0
+ c
) * 3 + 2] = (float)((bgcols
[c
] & 0xff)) / 256.0F
;
1697 for (c
= 0; c
< 8; c
++) {
1698 for (i
= 0; i
< 3; i
++) {
1699 ret
[(COL_B0
+ 8 + c
) * 3 + i
] =
1700 (ret
[(COL_B0
+ c
) * 3 + i
] + ret
[(COL_B0
+ c
+ 1) * 3 + i
]) / 2.0F
;
1704 #define average(r,a,b,w) do { \
1705 for (i = 0; i < 3; i++) \
1706 ret[(r)*3+i] = ret[(a)*3+i] + w * (ret[(b)*3+i] - ret[(a)*3+i]); \
1708 average(COL_ARROW_BG_DIM
, COL_BACKGROUND
, COL_ARROW
, 0.1F
);
1709 average(COL_NUMBER_SET_MID
, COL_B0
, COL_NUMBER_SET
, 0.3F
);
1710 for (c
= 0; c
< NBACKGROUNDS
; c
++) {
1711 /* I assume here that COL_ARROW and COL_NUMBER are the same.
1712 * Otherwise I'd need two sets of COL_M*. */
1713 average(COL_M0
+ c
, COL_B0
+ c
, COL_NUMBER
, 0.3F
);
1714 average(COL_D0
+ c
, COL_B0
+ c
, COL_NUMBER
, 0.1F
);
1715 average(COL_X0
+ c
, COL_BACKGROUND
, COL_B0
+ c
, 0.5F
);
1718 *ncolours
= NCOLOURS
;
1722 static game_drawstate
*game_new_drawstate(drawing
*dr
, const game_state
*state
)
1724 struct game_drawstate
*ds
= snew(struct game_drawstate
);
1727 ds
->tilesize
= ds
->started
= ds
->solved
= 0;
1732 ds
->nums
= snewn(state
->n
, int);
1733 ds
->dirp
= snewn(state
->n
, int);
1734 ds
->f
= snewn(state
->n
, unsigned int);
1735 for (i
= 0; i
< state
->n
; i
++) {
1741 ds
->angle_offset
= 0.0F
;
1743 ds
->dragging
= ds
->dx
= ds
->dy
= 0;
1749 static void game_free_drawstate(drawing
*dr
, game_drawstate
*ds
)
1754 if (ds
->dragb
) blitter_free(dr
, ds
->dragb
);
1759 /* cx, cy are top-left corner. sz is the 'radius' of the arrow.
1760 * ang is in radians, clockwise from 0 == straight up. */
1761 static void draw_arrow(drawing
*dr
, int cx
, int cy
, int sz
, double ang
,
1762 int cfill
, int cout
)
1765 int xdx
, ydx
, xdy
, ydy
, xdx3
, xdy3
;
1766 double s
= sin(ang
), c
= cos(ang
);
1768 xdx3
= (int)(sz
* (c
/3 + 1) + 0.5) - sz
;
1769 xdy3
= (int)(sz
* (s
/3 + 1) + 0.5) - sz
;
1770 xdx
= (int)(sz
* (c
+ 1) + 0.5) - sz
;
1771 xdy
= (int)(sz
* (s
+ 1) + 0.5) - sz
;
1776 coords
[2*0 + 0] = cx
- ydx
;
1777 coords
[2*0 + 1] = cy
- ydy
;
1778 coords
[2*1 + 0] = cx
+ xdx
;
1779 coords
[2*1 + 1] = cy
+ xdy
;
1780 coords
[2*2 + 0] = cx
+ xdx3
;
1781 coords
[2*2 + 1] = cy
+ xdy3
;
1782 coords
[2*3 + 0] = cx
+ xdx3
+ ydx
;
1783 coords
[2*3 + 1] = cy
+ xdy3
+ ydy
;
1784 coords
[2*4 + 0] = cx
- xdx3
+ ydx
;
1785 coords
[2*4 + 1] = cy
- xdy3
+ ydy
;
1786 coords
[2*5 + 0] = cx
- xdx3
;
1787 coords
[2*5 + 1] = cy
- xdy3
;
1788 coords
[2*6 + 0] = cx
- xdx
;
1789 coords
[2*6 + 1] = cy
- xdy
;
1791 draw_polygon(dr
, coords
, 7, cfill
, cout
);
1794 static void draw_arrow_dir(drawing
*dr
, int cx
, int cy
, int sz
, int dir
,
1795 int cfill
, int cout
, double angle_offset
)
1797 double ang
= 2.0 * PI
* (double)dir
/ 8.0 + angle_offset
;
1798 draw_arrow(dr
, cx
, cy
, sz
, ang
, cfill
, cout
);
1801 /* cx, cy are centre coordinates.. */
1802 static void draw_star(drawing
*dr
, int cx
, int cy
, int rad
, int npoints
,
1803 int cfill
, int cout
, double angle_offset
)
1808 assert(npoints
> 0);
1810 coords
= snewn(npoints
* 2 * 2, int);
1812 for (n
= 0; n
< npoints
* 2; n
++) {
1813 a
= 2.0 * PI
* ((double)n
/ ((double)npoints
* 2.0)) + angle_offset
;
1814 r
= (n
% 2) ? (double)rad
/2.0 : (double)rad
;
1816 /* We're rotating the point at (0, -r) by a degrees */
1817 coords
[2*n
+0] = cx
+ (int)( r
* sin(a
));
1818 coords
[2*n
+1] = cy
+ (int)(-r
* cos(a
));
1820 draw_polygon(dr
, coords
, npoints
*2, cfill
, cout
);
1824 static int num2col(game_drawstate
*ds
, int num
)
1826 int set
= num
/ (ds
->n
+1);
1828 if (num
<= 0 || set
== 0) return COL_B0
;
1829 return COL_B0
+ 1 + ((set
-1) % 15);
1832 #define ARROW_HALFSZ (7 * TILE_SIZE / 32)
1834 #define F_CUR 0x001 /* Cursor on this tile. */
1835 #define F_DRAG_SRC 0x002 /* Tile is source of a drag. */
1836 #define F_ERROR 0x004 /* Tile marked in error. */
1837 #define F_IMMUTABLE 0x008 /* Tile (number) is immutable. */
1838 #define F_ARROW_POINT 0x010 /* Tile points to other tile */
1839 #define F_ARROW_INPOINT 0x020 /* Other tile points in here. */
1840 #define F_DIM 0x040 /* Tile is dim */
1842 static void tile_redraw(drawing
*dr
, game_drawstate
*ds
, int tx
, int ty
,
1843 int dir
, int dirp
, int num
, unsigned int f
,
1844 double angle_offset
, int print_ink
)
1846 int cb
= TILE_SIZE
/ 16, textsz
;
1848 int arrowcol
, sarrowcol
, setcol
, textcol
;
1849 int acx
, acy
, asz
, empty
= 0;
1851 if (num
== 0 && !(f
& F_ARROW_POINT
) && !(f
& F_ARROW_INPOINT
)) {
1854 * We don't display text in empty cells: typically these are
1855 * signified by num=0. However, in some cases a cell could
1856 * have had the number 0 assigned to it if the user made an
1857 * error (e.g. tried to connect a chain of length 5 to the
1858 * immutable number 4) so we _do_ display the 0 if the cell
1859 * has a link in or a link out.
1863 /* Calculate colours. */
1865 if (print_ink
>= 0) {
1867 * We're printing, so just do everything in black.
1869 arrowcol
= textcol
= print_ink
;
1870 setcol
= sarrowcol
= -1; /* placate optimiser */
1873 setcol
= empty
? COL_BACKGROUND
: num2col(ds
, num
);
1875 #define dim(fg,bg) ( \
1876 (bg)==COL_BACKGROUND ? COL_ARROW_BG_DIM : \
1877 (bg) + COL_D0 - COL_B0 \
1880 #define mid(fg,bg) ( \
1881 (fg)==COL_NUMBER_SET ? COL_NUMBER_SET_MID : \
1882 (bg) + COL_M0 - COL_B0 \
1885 #define dimbg(bg) ( \
1886 (bg)==COL_BACKGROUND ? COL_BACKGROUND : \
1887 (bg) + COL_X0 - COL_B0 \
1890 if (f
& F_DRAG_SRC
) arrowcol
= COL_DRAG_ORIGIN
;
1891 else if (f
& F_DIM
) arrowcol
= dim(COL_ARROW
, setcol
);
1892 else if (f
& F_ARROW_POINT
) arrowcol
= mid(COL_ARROW
, setcol
);
1893 else arrowcol
= COL_ARROW
;
1895 if ((f
& F_ERROR
) && !(f
& F_IMMUTABLE
)) textcol
= COL_ERROR
;
1897 if (f
& F_IMMUTABLE
) textcol
= COL_NUMBER_SET
;
1898 else textcol
= COL_NUMBER
;
1900 if (f
& F_DIM
) textcol
= dim(textcol
, setcol
);
1901 else if (((f
& F_ARROW_POINT
) || num
==ds
->n
) &&
1902 ((f
& F_ARROW_INPOINT
) || num
==1))
1903 textcol
= mid(textcol
, setcol
);
1906 if (f
& F_DIM
) sarrowcol
= dim(COL_ARROW
, setcol
);
1907 else sarrowcol
= COL_ARROW
;
1910 /* Clear tile background */
1912 if (print_ink
< 0) {
1913 draw_rect(dr
, tx
, ty
, TILE_SIZE
, TILE_SIZE
,
1914 (f
& F_DIM
) ? dimbg(setcol
) : setcol
);
1917 /* Draw large (outwards-pointing) arrow. */
1919 asz
= ARROW_HALFSZ
; /* 'radius' of arrow/star. */
1920 acx
= tx
+TILE_SIZE
/2+asz
; /* centre x */
1921 acy
= ty
+TILE_SIZE
/2+asz
; /* centre y */
1923 if (num
== ds
->n
&& (f
& F_IMMUTABLE
))
1924 draw_star(dr
, acx
, acy
, asz
, 5, arrowcol
, arrowcol
, angle_offset
);
1926 draw_arrow_dir(dr
, acx
, acy
, asz
, dir
, arrowcol
, arrowcol
, angle_offset
);
1927 if (print_ink
< 0 && (f
& F_CUR
))
1928 draw_rect_corners(dr
, acx
, acy
, asz
+1, COL_CURSOR
);
1930 /* Draw dot iff this tile requires a predecessor and doesn't have one. */
1932 if (print_ink
< 0) {
1933 acx
= tx
+TILE_SIZE
/2-asz
;
1934 acy
= ty
+TILE_SIZE
/2+asz
;
1936 if (!(f
& F_ARROW_INPOINT
) && num
!= 1) {
1937 draw_circle(dr
, acx
, acy
, asz
/ 4, sarrowcol
, sarrowcol
);
1941 /* Draw text (number or set). */
1944 int set
= (num
<= 0) ? 0 : num
/ (ds
->n
+1);
1947 if (set
== 0 || num
<= 0) {
1948 sprintf(buf
, "%d", num
);
1950 int n
= num
% (ds
->n
+1);
1951 p
+= sizeof(buf
) - 1;
1954 sprintf(buf
, "+%d", n
); /* Just to get the length... */
1956 sprintf(p
, "+%d", n
);
1963 *p
= (char)((set
% 26)+'a');
1967 textsz
= min(2*asz
, (TILE_SIZE
- 2 * cb
) / (int)strlen(p
));
1968 draw_text(dr
, tx
+ cb
, ty
+ TILE_SIZE
/4, FONT_VARIABLE
, textsz
,
1969 ALIGN_VCENTRE
| ALIGN_HLEFT
, textcol
, p
);
1972 if (print_ink
< 0) {
1973 draw_rect_outline(dr
, tx
, ty
, TILE_SIZE
, TILE_SIZE
, COL_GRID
);
1974 draw_update(dr
, tx
, ty
, TILE_SIZE
, TILE_SIZE
);
1978 static void draw_drag_indicator(drawing
*dr
, game_drawstate
*ds
,
1979 const game_state
*state
, const game_ui
*ui
,
1982 int dir
, w
= ds
->w
, acol
= COL_ARROW
;
1983 int fx
= FROMCOORD(ui
->dx
), fy
= FROMCOORD(ui
->dy
);
1987 /* If we could move here, lock the arrow to the appropriate direction. */
1988 dir
= ui
->drag_is_from
? state
->dirs
[ui
->sy
*w
+ui
->sx
] : state
->dirs
[fy
*w
+fx
];
1990 ang
= (2.0 * PI
* dir
) / 8.0; /* similar to calculation in draw_arrow_dir. */
1992 /* Draw an arrow pointing away from/towards the origin cell. */
1993 int ox
= COORD(ui
->sx
) + TILE_SIZE
/2, oy
= COORD(ui
->sy
) + TILE_SIZE
/2;
1994 double tana
, offset
;
1995 double xdiff
= abs(ox
- ui
->dx
), ydiff
= abs(oy
- ui
->dy
);
1998 ang
= (oy
> ui
->dy
) ? 0.0F
: PI
;
1999 } else if (ydiff
== 0) {
2000 ang
= (ox
> ui
->dx
) ? 3.0F
*PI
/2.0F
: PI
/2.0F
;
2002 if (ui
->dx
> ox
&& ui
->dy
< oy
) {
2003 tana
= xdiff
/ ydiff
;
2005 } else if (ui
->dx
> ox
&& ui
->dy
> oy
) {
2006 tana
= ydiff
/ xdiff
;
2008 } else if (ui
->dx
< ox
&& ui
->dy
> oy
) {
2009 tana
= xdiff
/ ydiff
;
2012 tana
= ydiff
/ xdiff
;
2013 offset
= 3.0F
* PI
/ 2.0F
;
2015 ang
= atan(tana
) + offset
;
2018 if (!ui
->drag_is_from
) ang
+= PI
; /* point to origin, not away from. */
2021 draw_arrow(dr
, ui
->dx
, ui
->dy
, ARROW_HALFSZ
, ang
, acol
, acol
);
2024 static void game_redraw(drawing
*dr
, game_drawstate
*ds
,
2025 const game_state
*oldstate
, const game_state
*state
,
2026 int dir
, const game_ui
*ui
,
2027 float animtime
, float flashtime
)
2029 int x
, y
, i
, w
= ds
->w
, dirp
, force
= 0;
2031 double angle_offset
= 0.0;
2032 game_state
*postdrop
= NULL
;
2034 if (flashtime
> 0.0F
)
2035 angle_offset
= 2.0 * PI
* (flashtime
/ FLASH_SPIN
);
2036 if (angle_offset
!= ds
->angle_offset
) {
2037 ds
->angle_offset
= angle_offset
;
2043 blitter_load(dr
, ds
->dragb
, ds
->dx
, ds
->dy
);
2044 draw_update(dr
, ds
->dx
, ds
->dy
, BLITTER_SIZE
, BLITTER_SIZE
);
2045 ds
->dragging
= FALSE
;
2048 /* If an in-progress drag would make a valid move if finished, we
2049 * reflect that move in the board display. We let interpret_move do
2050 * most of the heavy lifting for us: we have to copy the game_ui so
2051 * as not to stomp on the real UI's drag state. */
2053 game_ui uicopy
= *ui
;
2054 char *movestr
= interpret_move(state
, &uicopy
, ds
, ui
->dx
, ui
->dy
, LEFT_RELEASE
);
2056 if (movestr
!= NULL
&& strcmp(movestr
, "") != 0) {
2057 postdrop
= execute_move(state
, movestr
);
2065 int aw
= TILE_SIZE
* state
->w
;
2066 int ah
= TILE_SIZE
* state
->h
;
2067 draw_rect(dr
, 0, 0, aw
+ 2 * BORDER
, ah
+ 2 * BORDER
, COL_BACKGROUND
);
2068 draw_rect_outline(dr
, BORDER
- 1, BORDER
- 1, aw
+ 2, ah
+ 2, COL_GRID
);
2069 draw_update(dr
, 0, 0, aw
+ 2 * BORDER
, ah
+ 2 * BORDER
);
2071 for (x
= 0; x
< state
->w
; x
++) {
2072 for (y
= 0; y
< state
->h
; y
++) {
2077 if (ui
->cshow
&& x
== ui
->cx
&& y
== ui
->cy
)
2081 if (x
== ui
->sx
&& y
== ui
->sy
)
2083 else if (ui
->drag_is_from
) {
2084 if (!ispointing(state
, ui
->sx
, ui
->sy
, x
, y
))
2087 if (!ispointing(state
, x
, y
, ui
->sx
, ui
->sy
))
2092 if (state
->impossible
||
2093 state
->nums
[i
] < 0 || state
->flags
[i
] & FLAG_ERROR
)
2095 if (state
->flags
[i
] & FLAG_IMMUTABLE
)
2098 if (state
->next
[i
] != -1)
2101 if (state
->prev
[i
] != -1) {
2102 /* Currently the direction here is from our square _back_
2103 * to its previous. We could change this to give the opposite
2104 * sense to the direction. */
2105 f
|= F_ARROW_INPOINT
;
2106 dirp
= whichdir(x
, y
, state
->prev
[i
]%w
, state
->prev
[i
]/w
);
2109 if (state
->nums
[i
] != ds
->nums
[i
] ||
2110 f
!= ds
->f
[i
] || dirp
!= ds
->dirp
[i
] ||
2111 force
|| !ds
->started
) {
2115 * Trivial and foolish configurable option done on
2116 * purest whim. With this option enabled, the
2117 * victory flash is done by rotating each square
2118 * in the opposite direction from its immediate
2119 * neighbours, so that they behave like a field of
2120 * interlocking gears. With it disabled, they all
2121 * rotate in the same direction. Choose for
2122 * yourself which is more brain-twisting :-)
2124 static int gear_mode
= -1;
2125 if (gear_mode
< 0) {
2126 char *env
= getenv("SIGNPOST_GEARS");
2127 gear_mode
= (env
&& (env
[0] == 'y' || env
[0] == 'Y'));
2130 sign
= 1 - 2 * ((x
^ y
) & 1);
2135 BORDER
+ x
* TILE_SIZE
,
2136 BORDER
+ y
* TILE_SIZE
,
2137 state
->dirs
[i
], dirp
, state
->nums
[i
], f
,
2138 sign
* angle_offset
, -1);
2139 ds
->nums
[i
] = state
->nums
[i
];
2146 ds
->dragging
= TRUE
;
2147 ds
->dx
= ui
->dx
- BLITTER_SIZE
/2;
2148 ds
->dy
= ui
->dy
- BLITTER_SIZE
/2;
2149 blitter_save(dr
, ds
->dragb
, ds
->dx
, ds
->dy
);
2151 draw_drag_indicator(dr
, ds
, state
, ui
, postdrop
? 1 : 0);
2153 if (postdrop
) free_game(postdrop
);
2154 if (!ds
->started
) ds
->started
= TRUE
;
2157 static float game_anim_length(const game_state
*oldstate
,
2158 const game_state
*newstate
, int dir
, game_ui
*ui
)
2163 static float game_flash_length(const game_state
*oldstate
,
2164 const game_state
*newstate
, int dir
, game_ui
*ui
)
2166 if (!oldstate
->completed
&&
2167 newstate
->completed
&& !newstate
->used_solve
)
2173 static int game_status(const game_state
*state
)
2175 return state
->completed
? +1 : 0;
2178 static int game_timing_state(const game_state
*state
, game_ui
*ui
)
2183 static void game_print_size(const game_params
*params
, float *x
, float *y
)
2187 game_compute_size(params
, 1300, &pw
, &ph
);
2192 static void game_print(drawing
*dr
, const game_state
*state
, int tilesize
)
2194 int ink
= print_mono_colour(dr
, 0);
2197 /* Fake up just enough of a drawstate */
2198 game_drawstate ads
, *ds
= &ads
;
2199 ds
->tilesize
= tilesize
;
2205 print_line_width(dr
, TILE_SIZE
/ 40);
2206 for (x
= 1; x
< state
->w
; x
++)
2207 draw_line(dr
, COORD(x
), COORD(0), COORD(x
), COORD(state
->h
), ink
);
2208 for (y
= 1; y
< state
->h
; y
++)
2209 draw_line(dr
, COORD(0), COORD(y
), COORD(state
->w
), COORD(y
), ink
);
2210 print_line_width(dr
, 2*TILE_SIZE
/ 40);
2211 draw_rect_outline(dr
, COORD(0), COORD(0), TILE_SIZE
*state
->w
,
2212 TILE_SIZE
*state
->h
, ink
);
2215 * Arrows and numbers.
2217 print_line_width(dr
, 0);
2218 for (y
= 0; y
< state
->h
; y
++)
2219 for (x
= 0; x
< state
->w
; x
++)
2220 tile_redraw(dr
, ds
, COORD(x
), COORD(y
), state
->dirs
[y
*state
->w
+x
],
2221 0, state
->nums
[y
*state
->w
+x
], 0, 0.0, ink
);
2225 #define thegame signpost
2228 const struct game thegame
= {
2229 "Signpost", "games.signpost", "signpost",
2231 game_fetch_preset
, NULL
,
2236 TRUE
, game_configure
, custom_params
,
2244 TRUE
, game_can_format_as_text_now
, game_text_format
,
2252 PREFERRED_TILE_SIZE
, game_compute_size
, game_set_size
,
2255 game_free_drawstate
,
2260 TRUE
, FALSE
, game_print_size
, game_print
,
2261 FALSE
, /* wants_statusbar */
2262 FALSE
, game_timing_state
,
2263 REQUIRE_RBUTTON
, /* flags */
2266 #ifdef STANDALONE_SOLVER
2271 const char *quis
= NULL
;
2274 void usage(FILE *out
) {
2275 fprintf(out
, "usage: %s [--stdin] [--soak] [--seed SEED] <params>|<game id>\n", quis
);
2278 static void cycle_seed(char **seedstr
, random_state
*rs
)
2284 newseed
[0] = '1' + (char)random_upto(rs
, 9);
2285 for (j
= 1; j
< 15; j
++)
2286 newseed
[j
] = '0' + (char)random_upto(rs
, 10);
2288 *seedstr
= dupstr(newseed
);
2291 static void start_soak(game_params
*p
, char *seedstr
)
2293 time_t tt_start
, tt_now
, tt_last
;
2296 long n
= 0, nnums
= 0, i
;
2299 tt_start
= tt_now
= time(NULL
);
2300 printf("Soak-generating a %dx%d grid.\n", p
->w
, p
->h
);
2303 rs
= random_new(seedstr
, strlen(seedstr
));
2304 desc
= thegame
.new_desc(p
, rs
, &aux
, 0);
2306 state
= thegame
.new_game(NULL
, p
, desc
);
2307 for (i
= 0; i
< state
->n
; i
++) {
2308 if (state
->flags
[i
] & FLAG_IMMUTABLE
)
2311 thegame
.free_game(state
);
2314 cycle_seed(&seedstr
, rs
);
2318 tt_last
= time(NULL
);
2319 if (tt_last
> tt_now
) {
2321 printf("%ld total, %3.1f/s, %3.1f nums/grid (%3.1f%%).\n",
2323 (double)n
/ ((double)tt_now
- tt_start
),
2324 (double)nnums
/ (double)n
,
2325 ((double)nnums
* 100.0) / ((double)n
* (double)p
->w
* (double)p
->h
) );
2330 static void process_desc(char *id
)
2332 char *desc
, *err
, *solvestr
;
2336 printf("%s\n ", id
);
2338 desc
= strchr(id
, ':');
2340 fprintf(stderr
, "%s: expecting game description.", quis
);
2346 p
= thegame
.default_params();
2347 thegame
.decode_params(p
, id
);
2348 err
= thegame
.validate_params(p
, 1);
2350 fprintf(stderr
, "%s: %s", quis
, err
);
2351 thegame
.free_params(p
);
2355 err
= thegame
.validate_desc(p
, desc
);
2357 fprintf(stderr
, "%s: %s\nDescription: %s\n", quis
, err
, desc
);
2358 thegame
.free_params(p
);
2362 s
= thegame
.new_game(NULL
, p
, desc
);
2364 solvestr
= thegame
.solve(s
, s
, NULL
, &err
);
2366 fprintf(stderr
, "%s\n", err
);
2368 printf("Puzzle is soluble.\n");
2370 thegame
.free_game(s
);
2371 thegame
.free_params(p
);
2374 int main(int argc
, const char *argv
[])
2376 char *id
= NULL
, *desc
, *err
, *aux
= NULL
;
2377 int soak
= 0, verbose
= 0, stdin_desc
= 0, n
= 1, i
;
2378 char *seedstr
= NULL
, newseed
[16];
2380 setvbuf(stdout
, NULL
, _IONBF
, 0);
2383 while (--argc
> 0) {
2384 char *p
= (char*)(*++argv
);
2385 if (!strcmp(p
, "-v") || !strcmp(p
, "--verbose"))
2387 else if (!strcmp(p
, "--stdin"))
2389 else if (!strcmp(p
, "-e") || !strcmp(p
, "--seed")) {
2390 seedstr
= dupstr(*++argv
);
2392 } else if (!strcmp(p
, "-n") || !strcmp(p
, "--number")) {
2395 } else if (!strcmp(p
, "-s") || !strcmp(p
, "--soak")) {
2397 } else if (*p
== '-') {
2398 fprintf(stderr
, "%s: unrecognised option `%s'\n", argv
[0], p
);
2406 sprintf(newseed
, "%lu", (unsigned long) time(NULL
));
2407 seedstr
= dupstr(newseed
);
2409 if (id
|| !stdin_desc
) {
2410 if (id
&& strchr(id
, ':')) {
2411 /* Parameters and description passed on cmd-line:
2412 * try and solve it. */
2415 /* No description passed on cmd-line: decode parameters
2416 * (with optional seed too) */
2418 game_params
*p
= thegame
.default_params();
2421 char *cmdseed
= strchr(id
, '#');
2425 seedstr
= dupstr(cmdseed
);
2428 thegame
.decode_params(p
, id
);
2431 err
= thegame
.validate_params(p
, 1);
2433 fprintf(stderr
, "%s: %s", quis
, err
);
2434 thegame
.free_params(p
);
2438 /* We have a set of valid parameters; either soak with it
2439 * or generate a single game description and print to stdout. */
2441 start_soak(p
, seedstr
);
2443 char *pstring
= thegame
.encode_params(p
, 0);
2445 for (i
= 0; i
< n
; i
++) {
2446 random_state
*rs
= random_new(seedstr
, strlen(seedstr
));
2448 if (verbose
) printf("%s#%s\n", pstring
, seedstr
);
2449 desc
= thegame
.new_desc(p
, rs
, &aux
, 0);
2450 printf("%s:%s\n", pstring
, desc
);
2453 cycle_seed(&seedstr
, rs
);
2460 thegame
.free_params(p
);
2467 while (fgets(buf
, sizeof(buf
), stdin
)) {
2468 buf
[strcspn(buf
, "\r\n")] = '\0';
2480 /* vim: set shiftwidth=4 tabstop=8: */