tsiry-sandratraina.com
A modern Music Player Daemon based on Rockbox open source high quality audio player
libadwaita
audio
rust
zig
deno
mpris
rockbox
mpd
1/*
2 * bridges.c: Implementation of the Nikoli game 'Bridges'.
3 *
4 * Things still to do:
5 *
6 * - The solver's algorithmic design is not really ideal. It makes
7 * use of the same data representation as gameplay uses, which
8 * often looks like a tempting reuse of code but isn't always a
9 * good idea. In this case, it's unpleasant that each edge of the
10 * graph ends up represented as multiple squares on a grid, with
11 * flags indicating when edges and non-edges cross; that's useful
12 * when the result can be directly translated into positions of
13 * graphics on the display, but in purely internal work it makes
14 * even simple manipulations during solving more painful than they
15 * should be, and complex ones have no choice but to modify the
16 * data structures temporarily, test things, and put them back. I
17 * envisage a complete solver rewrite along the following lines:
18 * + We have a collection of vertices (islands) and edges
19 * (potential bridge locations, i.e. pairs of horizontal or
20 * vertical islands with no other island in between).
21 * + Each edge has an associated list of edges that cross it, and
22 * hence with which it is mutually exclusive.
23 * + For each edge, we track the min and max number of bridges we
24 * currently think possible.
25 * + For each vertex, we track the number of _liberties_ it has,
26 * i.e. its clue number minus the min bridge count for each edge
27 * out of it.
28 * + We also maintain a dsf that identifies sets of vertices which
29 * are connected components of the puzzle so far, and for each
30 * equivalence class we track the total number of liberties for
31 * that component. (The dsf mechanism will also already track
32 * the size of each component, i.e. number of islands.)
33 * + So incrementing the min for an edge requires processing along
34 * the lines of:
35 * - set the max for all edges crossing that one to zero
36 * - decrement the liberty count for the vertex at each end,
37 * and also for each vertex's equivalence class (NB they may
38 * be the same class)
39 * - unify the two equivalence classes if they're not already,
40 * and if so, set the liberty count for the new class to be
41 * the sum of the previous two.
42 * + Decrementing the max is much easier, however.
43 * + With this data structure the really fiddly stuff in stage3()
44 * becomes more or less trivial, because it's now a quick job to
45 * find out whether an island would form an isolated subgraph if
46 * connected to a given subset of its neighbours:
47 * - identify the connected components containing the test
48 * vertex and its putative new neighbours (but be careful not
49 * to count a component more than once if two or more of the
50 * vertices involved are already in the same one)
51 * - find the sum of those components' liberty counts, and also
52 * the total number of islands involved
53 * - if the total liberty count of the connected components is
54 * exactly equal to twice the number of edges we'd be adding
55 * (of course each edge destroys two liberties, one at each
56 * end) then these components would become a subgraph with
57 * zero liberties if connected together.
58 * - therefore, if that subgraph also contains fewer than the
59 * total number of islands, it's disallowed.
60 * - As mentioned in stage3(), once we've identified such a
61 * disallowed pattern, we have two choices for what to do
62 * with it: if the candidate set of neighbours has size 1 we
63 * can reduce the max for the edge to that one neighbour,
64 * whereas if its complement has size 1 we can increase the
65 * min for the edge to the _omitted_ neighbour.
66 *
67 * - write a recursive solver?
68 */
69
70#include <stdio.h>
71#include <stdlib.h>
72#include <string.h>
73#include <assert.h>
74#include <ctype.h>
75#include <limits.h>
76#ifdef NO_TGMATH_H
77# include <math.h>
78#else
79# include <tgmath.h>
80#endif
81
82#include "puzzles.h"
83
84#undef DRAW_GRID
85
86/* --- structures for params, state, etc. --- */
87
88#define MAX_BRIDGES 4
89
90#define PREFERRED_TILE_SIZE 24
91#define TILE_SIZE (ds->tilesize)
92#define BORDER (TILE_SIZE / 2)
93
94#define COORD(x) ( (x) * TILE_SIZE + BORDER )
95#define FROMCOORD(x) ( ((x) - BORDER + TILE_SIZE) / TILE_SIZE - 1 )
96
97#define FLASH_TIME 0.50F
98
99enum {
100 COL_BACKGROUND,
101 COL_FOREGROUND,
102 COL_HIGHLIGHT, COL_LOWLIGHT,
103 COL_SELECTED, COL_MARK,
104 COL_HINT, COL_GRID,
105 COL_WARNING,
106 COL_CURSOR,
107 NCOLOURS
108};
109
110enum {
111 PREF_SHOW_HINTS,
112 N_PREF_ITEMS
113};
114
115struct game_params {
116 int w, h, maxb;
117 int islands, expansion; /* %age of island squares, %age chance of expansion */
118 bool allowloops;
119 int difficulty;
120};
121
122/* general flags used by all structs */
123#define G_ISLAND 0x0001
124#define G_LINEV 0x0002 /* contains a vert. line */
125#define G_LINEH 0x0004 /* contains a horiz. line (mutex with LINEV) */
126#define G_LINE (G_LINEV|G_LINEH)
127#define G_MARKV 0x0008
128#define G_MARKH 0x0010
129#define G_MARK (G_MARKV|G_MARKH)
130#define G_NOLINEV 0x0020
131#define G_NOLINEH 0x0040
132#define G_NOLINE (G_NOLINEV|G_NOLINEH)
133
134/* flags used by the error checker */
135#define G_WARN 0x0080
136
137/* flags used by the solver etc. */
138#define G_SWEEP 0x1000
139
140#define G_FLAGSH (G_LINEH|G_MARKH|G_NOLINEH)
141#define G_FLAGSV (G_LINEV|G_MARKV|G_NOLINEV)
142
143typedef unsigned int grid_type; /* change me later if we invent > 16 bits of flags. */
144
145struct solver_state {
146 DSF *dsf, *tmpdsf;
147 int *comptspaces, *tmpcompspaces;
148 int refcount;
149};
150
151/* state->gridi is an optimisation; it stores the pointer to the island
152 * structs indexed by (x,y). It's not strictly necessary (we could use
153 * find234 instead), but Purify showed that board generation (mostly the solver)
154 * was spending 60% of its time in find234. */
155
156struct surrounds { /* cloned from lightup.c */
157 struct { int x, y, dx, dy, off; } points[4];
158 int npoints, nislands;
159};
160
161struct island {
162 game_state *state;
163 int x, y, count;
164 struct surrounds adj;
165};
166
167struct game_state {
168 int w, h, maxb;
169 bool completed, solved;
170 bool allowloops;
171 grid_type *grid;
172 struct island *islands;
173 int n_islands, n_islands_alloc;
174 game_params params; /* used by the aux solver. */
175#define N_WH_ARRAYS 5
176 char *wha, *possv, *possh, *lines, *maxv, *maxh;
177 struct island **gridi;
178 struct solver_state *solver; /* refcounted */
179};
180
181#define GRIDSZ(s) ((s)->w * (s)->h * sizeof(grid_type))
182
183#define INGRID(s,x,y) ((x) >= 0 && (x) < (s)->w && (y) >= 0 && (y) < (s)->h)
184
185#define DINDEX(x,y) ((y)*state->w + (x))
186
187#define INDEX(s,g,x,y) ((s)->g[(y)*((s)->w) + (x)])
188#define IDX(s,g,i) ((s)->g[(i)])
189#define GRID(s,x,y) INDEX(s,grid,x,y)
190#define POSSIBLES(s,dx,x,y) ((dx) ? (INDEX(s,possh,x,y)) : (INDEX(s,possv,x,y)))
191#define MAXIMUM(s,dx,x,y) ((dx) ? (INDEX(s,maxh,x,y)) : (INDEX(s,maxv,x,y)))
192
193#define GRIDCOUNT(s,x,y,f) ((GRID(s,x,y) & (f)) ? (INDEX(s,lines,x,y)) : 0)
194
195#define WITHIN2(x,min,max) ((x) >= (min) && (x) <= (max))
196#define WITHIN(x,min,max) ((min) > (max) ? \
197 WITHIN2(x,max,min) : WITHIN2(x,min,max))
198
199/* --- island struct and tree support functions --- */
200
201#define ISLAND_ORTH(is,j,f,df) \
202 (is->f + (is->adj.points[(j)].off*is->adj.points[(j)].df))
203
204#define ISLAND_ORTHX(is,j) ISLAND_ORTH(is,j,x,dx)
205#define ISLAND_ORTHY(is,j) ISLAND_ORTH(is,j,y,dy)
206
207static void fixup_islands_for_realloc(game_state *state)
208{
209 int i;
210
211 for (i = 0; i < state->w*state->h; i++) state->gridi[i] = NULL;
212 for (i = 0; i < state->n_islands; i++) {
213 struct island *is = &state->islands[i];
214 is->state = state;
215 INDEX(state, gridi, is->x, is->y) = is;
216 }
217}
218
219static bool game_can_format_as_text_now(const game_params *params)
220{
221 return true;
222}
223
224static char *game_text_format(const game_state *state)
225{
226 int x, y, len, nl;
227 char *ret, *p;
228 struct island *is;
229 grid_type grid;
230
231 len = (state->h) * (state->w+1) + 1;
232 ret = snewn(len, char);
233 p = ret;
234
235 for (y = 0; y < state->h; y++) {
236 for (x = 0; x < state->w; x++) {
237 grid = GRID(state,x,y);
238 nl = INDEX(state,lines,x,y);
239 is = INDEX(state, gridi, x, y);
240 if (is) {
241 *p++ = '0' + is->count;
242 } else if (grid & G_LINEV) {
243 *p++ = (nl > 1) ? '"' : (nl == 1) ? '|' : '!'; /* gaah, want a double-bar. */
244 } else if (grid & G_LINEH) {
245 *p++ = (nl > 1) ? '=' : (nl == 1) ? '-' : '~';
246 } else {
247 *p++ = '.';
248 }
249 }
250 *p++ = '\n';
251 }
252 *p++ = '\0';
253
254 assert(p - ret == len);
255 return ret;
256}
257
258static void debug_state(game_state *state)
259{
260 char *textversion = game_text_format(state);
261 debug(("%s", textversion));
262 sfree(textversion);
263}
264
265/*static void debug_possibles(game_state *state)
266{
267 int x, y;
268 debug(("possh followed by possv\n"));
269 for (y = 0; y < state->h; y++) {
270 for (x = 0; x < state->w; x++) {
271 debug(("%d", POSSIBLES(state, 1, x, y)));
272 }
273 debug((" "));
274 for (x = 0; x < state->w; x++) {
275 debug(("%d", POSSIBLES(state, 0, x, y)));
276 }
277 debug(("\n"));
278 }
279 debug(("\n"));
280 for (y = 0; y < state->h; y++) {
281 for (x = 0; x < state->w; x++) {
282 debug(("%d", MAXIMUM(state, 1, x, y)));
283 }
284 debug((" "));
285 for (x = 0; x < state->w; x++) {
286 debug(("%d", MAXIMUM(state, 0, x, y)));
287 }
288 debug(("\n"));
289 }
290 debug(("\n"));
291}*/
292
293static void island_set_surrounds(struct island *is)
294{
295 assert(INGRID(is->state,is->x,is->y));
296 is->adj.npoints = is->adj.nislands = 0;
297#define ADDPOINT(cond,ddx,ddy) do {\
298 if (cond) { \
299 is->adj.points[is->adj.npoints].x = is->x+(ddx); \
300 is->adj.points[is->adj.npoints].y = is->y+(ddy); \
301 is->adj.points[is->adj.npoints].dx = (ddx); \
302 is->adj.points[is->adj.npoints].dy = (ddy); \
303 is->adj.points[is->adj.npoints].off = 0; \
304 is->adj.npoints++; \
305 } } while(0)
306 ADDPOINT(is->x > 0, -1, 0);
307 ADDPOINT(is->x < (is->state->w-1), +1, 0);
308 ADDPOINT(is->y > 0, 0, -1);
309 ADDPOINT(is->y < (is->state->h-1), 0, +1);
310}
311
312static void island_find_orthogonal(struct island *is)
313{
314 /* fills in the rest of the 'surrounds' structure, assuming
315 * all other islands are now in place. */
316 int i, x, y, dx, dy, off;
317
318 is->adj.nislands = 0;
319 for (i = 0; i < is->adj.npoints; i++) {
320 dx = is->adj.points[i].dx;
321 dy = is->adj.points[i].dy;
322 x = is->x + dx;
323 y = is->y + dy;
324 off = 1;
325 is->adj.points[i].off = 0;
326 while (INGRID(is->state, x, y)) {
327 if (GRID(is->state, x, y) & G_ISLAND) {
328 is->adj.points[i].off = off;
329 is->adj.nislands++;
330 /*debug(("island (%d,%d) has orth is. %d*(%d,%d) away at (%d,%d).\n",
331 is->x, is->y, off, dx, dy,
332 ISLAND_ORTHX(is,i), ISLAND_ORTHY(is,i)));*/
333 goto foundisland;
334 }
335 off++; x += dx; y += dy;
336 }
337foundisland:
338 ;
339 }
340}
341
342static bool island_hasbridge(struct island *is, int direction)
343{
344 int x = is->adj.points[direction].x;
345 int y = is->adj.points[direction].y;
346 grid_type gline = is->adj.points[direction].dx ? G_LINEH : G_LINEV;
347
348 if (GRID(is->state, x, y) & gline) return true;
349 return false;
350}
351
352static struct island *island_find_connection(struct island *is, int adjpt)
353{
354 struct island *is_r;
355
356 assert(adjpt < is->adj.npoints);
357 if (!is->adj.points[adjpt].off) return NULL;
358 if (!island_hasbridge(is, adjpt)) return NULL;
359
360 is_r = INDEX(is->state, gridi,
361 ISLAND_ORTHX(is, adjpt), ISLAND_ORTHY(is, adjpt));
362 assert(is_r);
363
364 return is_r;
365}
366
367static struct island *island_add(game_state *state, int x, int y, int count)
368{
369 struct island *is;
370 bool realloced = false;
371
372 assert(!(GRID(state,x,y) & G_ISLAND));
373 GRID(state,x,y) |= G_ISLAND;
374
375 state->n_islands++;
376 if (state->n_islands > state->n_islands_alloc) {
377 state->n_islands_alloc = state->n_islands * 2;
378 state->islands =
379 sresize(state->islands, state->n_islands_alloc, struct island);
380 realloced = true;
381 }
382 is = &state->islands[state->n_islands-1];
383
384 memset(is, 0, sizeof(struct island));
385 is->state = state;
386 is->x = x;
387 is->y = y;
388 is->count = count;
389 island_set_surrounds(is);
390
391 if (realloced)
392 fixup_islands_for_realloc(state);
393 else
394 INDEX(state, gridi, x, y) = is;
395
396 return is;
397}
398
399
400/* n = -1 means 'flip NOLINE flags [and set line to 0].' */
401static void island_join(struct island *i1, struct island *i2, int n, bool is_max)
402{
403 game_state *state = i1->state;
404 int s, e, x, y;
405
406 assert(i1->state == i2->state);
407 assert(n >= -1 && n <= i1->state->maxb);
408
409 if (i1->x == i2->x) {
410 x = i1->x;
411 if (i1->y < i2->y) {
412 s = i1->y+1; e = i2->y-1;
413 } else {
414 s = i2->y+1; e = i1->y-1;
415 }
416 for (y = s; y <= e; y++) {
417 if (is_max) {
418 INDEX(state,maxv,x,y) = n;
419 } else {
420 if (n < 0) {
421 GRID(state,x,y) ^= G_NOLINEV;
422 } else if (n == 0) {
423 GRID(state,x,y) &= ~G_LINEV;
424 } else {
425 GRID(state,x,y) |= G_LINEV;
426 INDEX(state,lines,x,y) = n;
427 }
428 }
429 }
430 } else if (i1->y == i2->y) {
431 y = i1->y;
432 if (i1->x < i2->x) {
433 s = i1->x+1; e = i2->x-1;
434 } else {
435 s = i2->x+1; e = i1->x-1;
436 }
437 for (x = s; x <= e; x++) {
438 if (is_max) {
439 INDEX(state,maxh,x,y) = n;
440 } else {
441 if (n < 0) {
442 GRID(state,x,y) ^= G_NOLINEH;
443 } else if (n == 0) {
444 GRID(state,x,y) &= ~G_LINEH;
445 } else {
446 GRID(state,x,y) |= G_LINEH;
447 INDEX(state,lines,x,y) = n;
448 }
449 }
450 }
451 } else {
452 assert(!"island_join: islands not orthogonal.");
453 }
454}
455
456/* Counts the number of bridges currently attached to the island. */
457static int island_countbridges(struct island *is)
458{
459 int i, c = 0;
460
461 for (i = 0; i < is->adj.npoints; i++) {
462 c += GRIDCOUNT(is->state,
463 is->adj.points[i].x, is->adj.points[i].y,
464 is->adj.points[i].dx ? G_LINEH : G_LINEV);
465 }
466 /*debug(("island count for (%d,%d) is %d.\n", is->x, is->y, c));*/
467 return c;
468}
469
470static int island_adjspace(struct island *is, bool marks, int missing,
471 int direction)
472{
473 int x, y, poss, curr, dx;
474 grid_type gline, mline;
475
476 x = is->adj.points[direction].x;
477 y = is->adj.points[direction].y;
478 dx = is->adj.points[direction].dx;
479 gline = dx ? G_LINEH : G_LINEV;
480
481 if (marks) {
482 mline = dx ? G_MARKH : G_MARKV;
483 if (GRID(is->state,x,y) & mline) return 0;
484 }
485 poss = POSSIBLES(is->state, dx, x, y);
486 poss = min(poss, missing);
487
488 curr = GRIDCOUNT(is->state, x, y, gline);
489 poss = min(poss, MAXIMUM(is->state, dx, x, y) - curr);
490
491 return poss;
492}
493
494/* Counts the number of bridge spaces left around the island;
495 * expects the possibles to be up-to-date. */
496static int island_countspaces(struct island *is, bool marks)
497{
498 int i, c = 0, missing;
499
500 missing = is->count - island_countbridges(is);
501 if (missing < 0) return 0;
502
503 for (i = 0; i < is->adj.npoints; i++) {
504 c += island_adjspace(is, marks, missing, i);
505 }
506 return c;
507}
508
509/* Returns a bridge count rather than a boolean */
510static int island_isadj(struct island *is, int direction)
511{
512 int x, y;
513 grid_type gline, mline;
514
515 x = is->adj.points[direction].x;
516 y = is->adj.points[direction].y;
517
518 mline = is->adj.points[direction].dx ? G_MARKH : G_MARKV;
519 gline = is->adj.points[direction].dx ? G_LINEH : G_LINEV;
520 if (GRID(is->state, x, y) & mline) {
521 /* If we're marked (i.e. the thing to attach to is complete)
522 * only count an adjacency if we're already attached. */
523 return GRIDCOUNT(is->state, x, y, gline);
524 } else {
525 /* If we're unmarked, count possible adjacency iff it's
526 * flagged as POSSIBLE. */
527 return POSSIBLES(is->state, is->adj.points[direction].dx, x, y);
528 }
529 return 0;
530}
531
532/* Counts the no. of possible adjacent islands (including islands
533 * we're already connected to). */
534static int island_countadj(struct island *is)
535{
536 int i, nadj = 0;
537
538 for (i = 0; i < is->adj.npoints; i++) {
539 if (island_isadj(is, i)) nadj++;
540 }
541 return nadj;
542}
543
544static void island_togglemark(struct island *is)
545{
546 int i, j, x, y, o;
547 struct island *is_loop;
548
549 /* mark the island... */
550 GRID(is->state, is->x, is->y) ^= G_MARK;
551
552 /* ...remove all marks on non-island squares... */
553 for (x = 0; x < is->state->w; x++) {
554 for (y = 0; y < is->state->h; y++) {
555 if (!(GRID(is->state, x, y) & G_ISLAND))
556 GRID(is->state, x, y) &= ~G_MARK;
557 }
558 }
559
560 /* ...and add marks to squares around marked islands. */
561 for (i = 0; i < is->state->n_islands; i++) {
562 is_loop = &is->state->islands[i];
563 if (!(GRID(is_loop->state, is_loop->x, is_loop->y) & G_MARK))
564 continue;
565
566 for (j = 0; j < is_loop->adj.npoints; j++) {
567 /* if this direction takes us to another island, mark all
568 * squares between the two islands. */
569 if (!is_loop->adj.points[j].off) continue;
570 assert(is_loop->adj.points[j].off > 1);
571 for (o = 1; o < is_loop->adj.points[j].off; o++) {
572 GRID(is_loop->state,
573 is_loop->x + is_loop->adj.points[j].dx*o,
574 is_loop->y + is_loop->adj.points[j].dy*o) |=
575 is_loop->adj.points[j].dy ? G_MARKV : G_MARKH;
576 }
577 }
578 }
579}
580
581static bool island_impossible(struct island *is, bool strict)
582{
583 int curr = island_countbridges(is), nspc = is->count - curr, nsurrspc;
584 int i, poss;
585 struct island *is_orth;
586
587 if (nspc < 0) {
588 debug(("island at (%d,%d) impossible because full.\n", is->x, is->y));
589 return true; /* too many bridges */
590 } else if ((curr + island_countspaces(is, false)) < is->count) {
591 debug(("island at (%d,%d) impossible because not enough spaces.\n", is->x, is->y));
592 return true; /* impossible to create enough bridges */
593 } else if (strict && curr < is->count) {
594 debug(("island at (%d,%d) impossible because locked.\n", is->x, is->y));
595 return true; /* not enough bridges and island is locked */
596 }
597
598 /* Count spaces in surrounding islands. */
599 nsurrspc = 0;
600 for (i = 0; i < is->adj.npoints; i++) {
601 int ifree, dx = is->adj.points[i].dx;
602
603 if (!is->adj.points[i].off) continue;
604 poss = POSSIBLES(is->state, dx,
605 is->adj.points[i].x, is->adj.points[i].y);
606 if (poss == 0) continue;
607 is_orth = INDEX(is->state, gridi,
608 ISLAND_ORTHX(is,i), ISLAND_ORTHY(is,i));
609 assert(is_orth);
610
611 ifree = is_orth->count - island_countbridges(is_orth);
612 if (ifree > 0) {
613 /*
614 * ifree is the number of bridges unfilled in the other
615 * island, which is clearly an upper bound on the number
616 * of extra bridges this island may run to it.
617 *
618 * Another upper bound is the number of bridges unfilled
619 * on the specific line between here and there. We must
620 * take the minimum of both.
621 */
622 int bmax = MAXIMUM(is->state, dx,
623 is->adj.points[i].x, is->adj.points[i].y);
624 int bcurr = GRIDCOUNT(is->state,
625 is->adj.points[i].x, is->adj.points[i].y,
626 dx ? G_LINEH : G_LINEV);
627 assert(bcurr <= bmax);
628 nsurrspc += min(ifree, bmax - bcurr);
629 }
630 }
631 if (nsurrspc < nspc) {
632 debug(("island at (%d,%d) impossible: surr. islands %d spc, need %d.\n",
633 is->x, is->y, nsurrspc, nspc));
634 return true; /* not enough spaces around surrounding islands to fill this one. */
635 }
636
637 return false;
638}
639
640/* --- Game parameter functions --- */
641
642#define DEFAULT_PRESET 0
643
644static const struct game_params bridges_presets[] = {
645 { 7, 7, 2, 30, 10, 1, 0 },
646 { 7, 7, 2, 30, 10, 1, 1 },
647 { 7, 7, 2, 30, 10, 1, 2 },
648 { 10, 10, 2, 30, 10, 1, 0 },
649 { 10, 10, 2, 30, 10, 1, 1 },
650 { 10, 10, 2, 30, 10, 1, 2 },
651 { 15, 15, 2, 30, 10, 1, 0 },
652 { 15, 15, 2, 30, 10, 1, 1 },
653 { 15, 15, 2, 30, 10, 1, 2 },
654};
655
656static game_params *default_params(void)
657{
658 game_params *ret = snew(game_params);
659 *ret = bridges_presets[DEFAULT_PRESET];
660
661 return ret;
662}
663
664static bool game_fetch_preset(int i, char **name, game_params **params)
665{
666 game_params *ret;
667 char buf[80];
668
669 if (i < 0 || i >= lenof(bridges_presets))
670 return false;
671
672 ret = default_params();
673 *ret = bridges_presets[i];
674 *params = ret;
675
676 sprintf(buf, "%dx%d %s", ret->w, ret->h,
677 ret->difficulty == 0 ? "easy" :
678 ret->difficulty == 1 ? "medium" : "hard");
679 *name = dupstr(buf);
680
681 return true;
682}
683
684static void free_params(game_params *params)
685{
686 sfree(params);
687}
688
689static game_params *dup_params(const game_params *params)
690{
691 game_params *ret = snew(game_params);
692 *ret = *params; /* structure copy */
693 return ret;
694}
695
696#define EATNUM(x) do { \
697 (x) = atoi(string); \
698 while (*string && isdigit((unsigned char)*string)) string++; \
699} while(0)
700
701static void decode_params(game_params *params, char const *string)
702{
703 EATNUM(params->w);
704 params->h = params->w;
705 if (*string == 'x') {
706 string++;
707 EATNUM(params->h);
708 }
709 if (*string == 'i') {
710 string++;
711 EATNUM(params->islands);
712 }
713 if (*string == 'e') {
714 string++;
715 EATNUM(params->expansion);
716 }
717 if (*string == 'm') {
718 string++;
719 EATNUM(params->maxb);
720 }
721 params->allowloops = true;
722 if (*string == 'L') {
723 string++;
724 params->allowloops = false;
725 }
726 if (*string == 'd') {
727 string++;
728 EATNUM(params->difficulty);
729 }
730}
731
732static char *encode_params(const game_params *params, bool full)
733{
734 char buf[80];
735
736 if (full) {
737 sprintf(buf, "%dx%di%de%dm%d%sd%d",
738 params->w, params->h, params->islands, params->expansion,
739 params->maxb, params->allowloops ? "" : "L",
740 params->difficulty);
741 } else {
742 sprintf(buf, "%dx%dm%d%s", params->w, params->h,
743 params->maxb, params->allowloops ? "" : "L");
744 }
745 return dupstr(buf);
746}
747
748static config_item *game_configure(const game_params *params)
749{
750 config_item *ret;
751 char buf[80];
752
753 ret = snewn(8, config_item);
754
755 ret[0].name = "Width";
756 ret[0].type = C_STRING;
757 sprintf(buf, "%d", params->w);
758 ret[0].u.string.sval = dupstr(buf);
759
760 ret[1].name = "Height";
761 ret[1].type = C_STRING;
762 sprintf(buf, "%d", params->h);
763 ret[1].u.string.sval = dupstr(buf);
764
765 ret[2].name = "Difficulty";
766 ret[2].type = C_CHOICES;
767 ret[2].u.choices.choicenames = ":Easy:Medium:Hard";
768 ret[2].u.choices.selected = params->difficulty;
769
770 ret[3].name = "Allow loops";
771 ret[3].type = C_BOOLEAN;
772 ret[3].u.boolean.bval = params->allowloops;
773
774 ret[4].name = "Max. bridges per direction";
775 ret[4].type = C_CHOICES;
776 ret[4].u.choices.choicenames = ":1:2:3:4"; /* keep up-to-date with
777 * MAX_BRIDGES */
778 ret[4].u.choices.selected = params->maxb - 1;
779
780 ret[5].name = "%age of island squares";
781 ret[5].type = C_CHOICES;
782 ret[5].u.choices.choicenames = ":5%:10%:15%:20%:25%:30%";
783 ret[5].u.choices.selected = (params->islands / 5)-1;
784
785 ret[6].name = "Expansion factor (%age)";
786 ret[6].type = C_CHOICES;
787 ret[6].u.choices.choicenames = ":0%:10%:20%:30%:40%:50%:60%:70%:80%:90%:100%";
788 ret[6].u.choices.selected = params->expansion / 10;
789
790 ret[7].name = NULL;
791 ret[7].type = C_END;
792
793 return ret;
794}
795
796static game_params *custom_params(const config_item *cfg)
797{
798 game_params *ret = snew(game_params);
799
800 ret->w = atoi(cfg[0].u.string.sval);
801 ret->h = atoi(cfg[1].u.string.sval);
802 ret->difficulty = cfg[2].u.choices.selected;
803 ret->allowloops = cfg[3].u.boolean.bval;
804 ret->maxb = cfg[4].u.choices.selected + 1;
805 ret->islands = (cfg[5].u.choices.selected + 1) * 5;
806 ret->expansion = cfg[6].u.choices.selected * 10;
807
808 return ret;
809}
810
811static const char *validate_params(const game_params *params, bool full)
812{
813 if (params->w < 3 || params->h < 3)
814 return "Width and height must be at least 3";
815 if (params->w > INT_MAX / params->h)
816 return "Width times height must not be unreasonably large";
817 if (params->maxb < 1 || params->maxb > MAX_BRIDGES)
818 return "Too many bridges.";
819 if (full) {
820 if (params->islands <= 0 || params->islands > 30)
821 return "%age of island squares must be between 1% and 30%";
822 if (params->expansion < 0 || params->expansion > 100)
823 return "Expansion factor must be between 0 and 100";
824 }
825 return NULL;
826}
827
828/* --- Game encoding and differences --- */
829
830static char *encode_game(game_state *state)
831{
832 char *ret, *p;
833 int wh = state->w*state->h, run, x, y;
834 struct island *is;
835
836 ret = snewn(wh + 1, char);
837 p = ret;
838 run = 0;
839 for (y = 0; y < state->h; y++) {
840 for (x = 0; x < state->w; x++) {
841 is = INDEX(state, gridi, x, y);
842 if (is) {
843 if (run) {
844 *p++ = ('a'-1) + run;
845 run = 0;
846 }
847 if (is->count < 10)
848 *p++ = '0' + is->count;
849 else
850 *p++ = 'A' + (is->count - 10);
851 } else {
852 if (run == 26) {
853 *p++ = ('a'-1) + run;
854 run = 0;
855 }
856 run++;
857 }
858 }
859 }
860 if (run) {
861 *p++ = ('a'-1) + run;
862 run = 0;
863 }
864 *p = '\0';
865 assert(p - ret <= wh);
866
867 return ret;
868}
869
870static char *game_state_diff(const game_state *src, const game_state *dest)
871{
872 int movesize = 256, movelen = 0;
873 char *move = snewn(movesize, char), buf[80];
874 int i, d, x, y, len;
875 grid_type gline, nline;
876 struct island *is_s, *is_d, *is_orth;
877
878#define APPEND do { \
879 if (movelen + len >= movesize) { \
880 movesize = movelen + len + 256; \
881 move = sresize(move, movesize, char); \
882 } \
883 strcpy(move + movelen, buf); \
884 movelen += len; \
885} while(0)
886
887 move[movelen++] = 'S';
888 move[movelen] = '\0';
889
890 assert(src->n_islands == dest->n_islands);
891
892 for (i = 0; i < src->n_islands; i++) {
893 is_s = &src->islands[i];
894 is_d = &dest->islands[i];
895 assert(is_s->x == is_d->x);
896 assert(is_s->y == is_d->y);
897 assert(is_s->adj.npoints == is_d->adj.npoints); /* more paranoia */
898
899 for (d = 0; d < is_s->adj.npoints; d++) {
900 if (is_s->adj.points[d].dx == -1 ||
901 is_s->adj.points[d].dy == -1) continue;
902
903 x = is_s->adj.points[d].x;
904 y = is_s->adj.points[d].y;
905 gline = is_s->adj.points[d].dx ? G_LINEH : G_LINEV;
906 nline = is_s->adj.points[d].dx ? G_NOLINEH : G_NOLINEV;
907 is_orth = INDEX(dest, gridi,
908 ISLAND_ORTHX(is_d, d), ISLAND_ORTHY(is_d, d));
909
910 if (GRIDCOUNT(src, x, y, gline) != GRIDCOUNT(dest, x, y, gline)) {
911 assert(is_orth);
912 len = sprintf(buf, ";L%d,%d,%d,%d,%d",
913 is_s->x, is_s->y, is_orth->x, is_orth->y,
914 GRIDCOUNT(dest, x, y, gline));
915 APPEND;
916 }
917 if ((GRID(src,x,y) & nline) != (GRID(dest, x, y) & nline)) {
918 assert(is_orth);
919 len = sprintf(buf, ";N%d,%d,%d,%d",
920 is_s->x, is_s->y, is_orth->x, is_orth->y);
921 APPEND;
922 }
923 }
924 if ((GRID(src, is_s->x, is_s->y) & G_MARK) !=
925 (GRID(dest, is_d->x, is_d->y) & G_MARK)) {
926 len = sprintf(buf, ";M%d,%d", is_s->x, is_s->y);
927 APPEND;
928 }
929 }
930 return move;
931}
932
933/* --- Game setup and solving utilities --- */
934
935/* This function is optimised; a Quantify showed that lots of grid-generation time
936 * (>50%) was spent in here. Hence the IDX() stuff. */
937
938static void map_update_possibles(game_state *state)
939{
940 int x, y, s, e, i, np, maxb, w = state->w, idx;
941 bool bl;
942 struct island *is_s = NULL, *is_f = NULL;
943
944 /* Run down vertical stripes [un]setting possv... */
945 for (x = 0; x < state->w; x++) {
946 idx = x;
947 s = e = -1;
948 bl = false;
949 maxb = state->params.maxb; /* placate optimiser */
950 /* Unset possible flags until we find an island. */
951 for (y = 0; y < state->h; y++) {
952 is_s = IDX(state, gridi, idx);
953 if (is_s) {
954 maxb = is_s->count;
955 break;
956 }
957
958 IDX(state, possv, idx) = 0;
959 idx += w;
960 }
961 for (; y < state->h; y++) {
962 maxb = min(maxb, IDX(state, maxv, idx));
963 is_f = IDX(state, gridi, idx);
964 if (is_f) {
965 assert(is_s);
966 np = min(maxb, is_f->count);
967
968 if (s != -1) {
969 for (i = s; i <= e; i++) {
970 INDEX(state, possv, x, i) = bl ? 0 : np;
971 }
972 }
973 s = y+1;
974 bl = false;
975 is_s = is_f;
976 maxb = is_s->count;
977 } else {
978 e = y;
979 if (IDX(state,grid,idx) & (G_LINEH|G_NOLINEV)) bl = true;
980 }
981 idx += w;
982 }
983 if (s != -1) {
984 for (i = s; i <= e; i++)
985 INDEX(state, possv, x, i) = 0;
986 }
987 }
988
989 /* ...and now do horizontal stripes [un]setting possh. */
990 /* can we lose this clone'n'hack? */
991 for (y = 0; y < state->h; y++) {
992 idx = y*w;
993 s = e = -1;
994 bl = false;
995 maxb = state->params.maxb; /* placate optimiser */
996 for (x = 0; x < state->w; x++) {
997 is_s = IDX(state, gridi, idx);
998 if (is_s) {
999 maxb = is_s->count;
1000 break;
1001 }
1002
1003 IDX(state, possh, idx) = 0;
1004 idx += 1;
1005 }
1006 for (; x < state->w; x++) {
1007 maxb = min(maxb, IDX(state, maxh, idx));
1008 is_f = IDX(state, gridi, idx);
1009 if (is_f) {
1010 assert(is_s);
1011 np = min(maxb, is_f->count);
1012
1013 if (s != -1) {
1014 for (i = s; i <= e; i++) {
1015 INDEX(state, possh, i, y) = bl ? 0 : np;
1016 }
1017 }
1018 s = x+1;
1019 bl = false;
1020 is_s = is_f;
1021 maxb = is_s->count;
1022 } else {
1023 e = x;
1024 if (IDX(state,grid,idx) & (G_LINEV|G_NOLINEH)) bl = true;
1025 }
1026 idx += 1;
1027 }
1028 if (s != -1) {
1029 for (i = s; i <= e; i++)
1030 INDEX(state, possh, i, y) = 0;
1031 }
1032 }
1033}
1034
1035static void map_count(game_state *state)
1036{
1037 int i, n, ax, ay;
1038 grid_type flag, grid;
1039 struct island *is;
1040
1041 for (i = 0; i < state->n_islands; i++) {
1042 is = &state->islands[i];
1043 is->count = 0;
1044 for (n = 0; n < is->adj.npoints; n++) {
1045 ax = is->adj.points[n].x;
1046 ay = is->adj.points[n].y;
1047 flag = (ax == is->x) ? G_LINEV : G_LINEH;
1048 grid = GRID(state,ax,ay);
1049 if (grid & flag) {
1050 is->count += INDEX(state,lines,ax,ay);
1051 }
1052 }
1053 }
1054}
1055
1056static void map_find_orthogonal(game_state *state)
1057{
1058 int i;
1059
1060 for (i = 0; i < state->n_islands; i++) {
1061 island_find_orthogonal(&state->islands[i]);
1062 }
1063}
1064
1065struct bridges_neighbour_ctx {
1066 game_state *state;
1067 int i, n, neighbours[4];
1068};
1069static int bridges_neighbour(int vertex, void *vctx)
1070{
1071 struct bridges_neighbour_ctx *ctx = (struct bridges_neighbour_ctx *)vctx;
1072 if (vertex >= 0) {
1073 game_state *state = ctx->state;
1074 int w = state->w, x = vertex % w, y = vertex / w;
1075 grid_type grid = GRID(state, x, y), gline = grid & G_LINE;
1076 struct island *is;
1077 int x1, y1, x2, y2, i;
1078
1079 ctx->i = ctx->n = 0;
1080
1081 is = INDEX(state, gridi, x, y);
1082 if (is) {
1083 for (i = 0; i < is->adj.npoints; i++) {
1084 gline = is->adj.points[i].dx ? G_LINEH : G_LINEV;
1085 if (GRID(state, is->adj.points[i].x,
1086 is->adj.points[i].y) & gline) {
1087 ctx->neighbours[ctx->n++] =
1088 (is->adj.points[i].y * w + is->adj.points[i].x);
1089 }
1090 }
1091 } else if (gline) {
1092 if (gline & G_LINEV) {
1093 x1 = x2 = x;
1094 y1 = y-1; y2 = y+1;
1095 } else {
1096 x1 = x-1; x2 = x+1;
1097 y1 = y2 = y;
1098 }
1099 /* Non-island squares with edges in should never be
1100 * pointing off the edge of the grid. */
1101 assert(INGRID(state, x1, y1));
1102 assert(INGRID(state, x2, y2));
1103 if (GRID(state, x1, y1) & (gline | G_ISLAND))
1104 ctx->neighbours[ctx->n++] = y1 * w + x1;
1105 if (GRID(state, x2, y2) & (gline | G_ISLAND))
1106 ctx->neighbours[ctx->n++] = y2 * w + x2;
1107 }
1108 }
1109
1110 if (ctx->i < ctx->n)
1111 return ctx->neighbours[ctx->i++];
1112 else
1113 return -1;
1114}
1115
1116static bool map_hasloops(game_state *state, bool mark)
1117{
1118 int x, y;
1119 struct findloopstate *fls;
1120 struct bridges_neighbour_ctx ctx;
1121 bool ret;
1122
1123 fls = findloop_new_state(state->w * state->h);
1124 ctx.state = state;
1125 ret = findloop_run(fls, state->w * state->h, bridges_neighbour, &ctx);
1126
1127 if (mark) {
1128 for (y = 0; y < state->h; y++) {
1129 for (x = 0; x < state->w; x++) {
1130 int u, v;
1131
1132 u = y * state->w + x;
1133 for (v = bridges_neighbour(u, &ctx); v >= 0;
1134 v = bridges_neighbour(-1, &ctx))
1135 if (findloop_is_loop_edge(fls, u, v))
1136 GRID(state,x,y) |= G_WARN;
1137 }
1138 }
1139 }
1140
1141 findloop_free_state(fls);
1142 return ret;
1143}
1144
1145static void map_group(game_state *state)
1146{
1147 int i, d1, d2;
1148 int x, y, x2, y2;
1149 DSF *dsf = state->solver->dsf;
1150 struct island *is, *is_join;
1151
1152 /* Initialise dsf. */
1153 dsf_reinit(dsf);
1154
1155 /* For each island, find connected islands right or down
1156 * and merge the dsf for the island squares as well as the
1157 * bridge squares. */
1158 for (x = 0; x < state->w; x++) {
1159 for (y = 0; y < state->h; y++) {
1160 GRID(state,x,y) &= ~(G_SWEEP|G_WARN); /* for group_full. */
1161
1162 is = INDEX(state, gridi, x, y);
1163 if (!is) continue;
1164 d1 = DINDEX(x,y);
1165 for (i = 0; i < is->adj.npoints; i++) {
1166 /* only want right/down */
1167 if (is->adj.points[i].dx == -1 ||
1168 is->adj.points[i].dy == -1) continue;
1169
1170 is_join = island_find_connection(is, i);
1171 if (!is_join) continue;
1172
1173 d2 = DINDEX(is_join->x, is_join->y);
1174 if (dsf_equivalent(dsf, d1, d2)) {
1175 ; /* we have a loop. See comment in map_hasloops. */
1176 /* However, we still want to merge all squares joining
1177 * this side-that-makes-a-loop. */
1178 }
1179 /* merge all squares between island 1 and island 2. */
1180 for (x2 = x; x2 <= is_join->x; x2++) {
1181 for (y2 = y; y2 <= is_join->y; y2++) {
1182 d2 = DINDEX(x2,y2);
1183 if (d1 != d2) dsf_merge(dsf,d1,d2);
1184 }
1185 }
1186 }
1187 }
1188 }
1189}
1190
1191static bool map_group_check(game_state *state, int canon, bool warn,
1192 int *nislands_r)
1193{
1194 DSF *dsf = state->solver->dsf;
1195 int nislands = 0;
1196 int x, y, i;
1197 bool allfull = true;
1198 struct island *is;
1199
1200 for (i = 0; i < state->n_islands; i++) {
1201 is = &state->islands[i];
1202 if (dsf_canonify(dsf, DINDEX(is->x,is->y)) != canon) continue;
1203
1204 GRID(state, is->x, is->y) |= G_SWEEP;
1205 nislands++;
1206 if (island_countbridges(is) != is->count)
1207 allfull = false;
1208 }
1209 if (warn && allfull && nislands != state->n_islands) {
1210 /* we're full and this island group isn't the whole set.
1211 * Mark all squares with this dsf canon as ERR. */
1212 for (x = 0; x < state->w; x++) {
1213 for (y = 0; y < state->h; y++) {
1214 if (dsf_canonify(dsf, DINDEX(x,y)) == canon) {
1215 GRID(state,x,y) |= G_WARN;
1216 }
1217 }
1218 }
1219
1220 }
1221 if (nislands_r) *nislands_r = nislands;
1222 return allfull;
1223}
1224
1225static bool map_group_full(game_state *state, int *ngroups_r)
1226{
1227 DSF *dsf = state->solver->dsf;
1228 int ngroups = 0;
1229 int i;
1230 bool anyfull = false;
1231 struct island *is;
1232
1233 /* NB this assumes map_group (or sth else) has cleared G_SWEEP. */
1234
1235 for (i = 0; i < state->n_islands; i++) {
1236 is = &state->islands[i];
1237 if (GRID(state,is->x,is->y) & G_SWEEP) continue;
1238
1239 ngroups++;
1240 if (map_group_check(state, dsf_canonify(dsf, DINDEX(is->x,is->y)),
1241 true, NULL))
1242 anyfull = true;
1243 }
1244
1245 *ngroups_r = ngroups;
1246 return anyfull;
1247}
1248
1249static bool map_check(game_state *state)
1250{
1251 int ngroups;
1252
1253 /* Check for loops, if necessary. */
1254 if (!state->allowloops) {
1255 if (map_hasloops(state, true))
1256 return false;
1257 }
1258
1259 /* Place islands into island groups and check for early
1260 * satisfied-groups. */
1261 map_group(state); /* clears WARN and SWEEP */
1262 if (map_group_full(state, &ngroups)) {
1263 if (ngroups == 1) return true;
1264 }
1265 return false;
1266}
1267
1268static void map_clear(game_state *state)
1269{
1270 int x, y;
1271
1272 for (x = 0; x < state->w; x++) {
1273 for (y = 0; y < state->h; y++) {
1274 /* clear most flags; might want to be slightly more careful here. */
1275 GRID(state,x,y) &= G_ISLAND;
1276 }
1277 }
1278}
1279
1280static void solve_join(struct island *is, int direction, int n, bool is_max)
1281{
1282 struct island *is_orth;
1283 int d1, d2;
1284 DSF *dsf = is->state->solver->dsf;
1285 game_state *state = is->state; /* for DINDEX */
1286
1287 is_orth = INDEX(is->state, gridi,
1288 ISLAND_ORTHX(is, direction),
1289 ISLAND_ORTHY(is, direction));
1290 assert(is_orth);
1291 /*debug(("...joining (%d,%d) to (%d,%d) with %d bridge(s).\n",
1292 is->x, is->y, is_orth->x, is_orth->y, n));*/
1293 island_join(is, is_orth, n, is_max);
1294
1295 if (n > 0 && !is_max) {
1296 d1 = DINDEX(is->x, is->y);
1297 d2 = DINDEX(is_orth->x, is_orth->y);
1298 if (!dsf_equivalent(dsf, d1, d2))
1299 dsf_merge(dsf, d1, d2);
1300 }
1301}
1302
1303static int solve_fillone(struct island *is)
1304{
1305 int i, nadded = 0;
1306
1307 debug(("solve_fillone for island (%d,%d).\n", is->x, is->y));
1308
1309 for (i = 0; i < is->adj.npoints; i++) {
1310 if (island_isadj(is, i)) {
1311 if (island_hasbridge(is, i)) {
1312 /* already attached; do nothing. */;
1313 } else {
1314 solve_join(is, i, 1, false);
1315 nadded++;
1316 }
1317 }
1318 }
1319 return nadded;
1320}
1321
1322static int solve_fill(struct island *is)
1323{
1324 /* for each unmarked adjacent, make sure we convert every possible bridge
1325 * to a real one, and then work out the possibles afresh. */
1326 int i, nnew, ncurr, nadded = 0, missing;
1327
1328 debug(("solve_fill for island (%d,%d).\n", is->x, is->y));
1329
1330 missing = is->count - island_countbridges(is);
1331 if (missing < 0) return 0;
1332
1333 /* very like island_countspaces. */
1334 for (i = 0; i < is->adj.npoints; i++) {
1335 nnew = island_adjspace(is, true, missing, i);
1336 if (nnew) {
1337 ncurr = GRIDCOUNT(is->state,
1338 is->adj.points[i].x, is->adj.points[i].y,
1339 is->adj.points[i].dx ? G_LINEH : G_LINEV);
1340
1341 solve_join(is, i, nnew + ncurr, false);
1342 nadded += nnew;
1343 }
1344 }
1345 return nadded;
1346}
1347
1348static bool solve_island_stage1(struct island *is, bool *didsth_r)
1349{
1350 int bridges = island_countbridges(is);
1351 int nspaces = island_countspaces(is, true);
1352 int nadj = island_countadj(is);
1353 bool didsth = false;
1354
1355 assert(didsth_r);
1356
1357 /*debug(("island at (%d,%d) filled %d/%d (%d spc) nadj %d\n",
1358 is->x, is->y, bridges, is->count, nspaces, nadj));*/
1359 if (bridges > is->count) {
1360 /* We only ever add bridges when we're sure they fit, or that's
1361 * the only place they can go. If we've added bridges such that
1362 * another island has become wrong, the puzzle must not have had
1363 * a solution. */
1364 debug(("...island at (%d,%d) is overpopulated!\n", is->x, is->y));
1365 return false;
1366 } else if (bridges == is->count) {
1367 /* This island is full. Make sure it's marked (and update
1368 * possibles if we did). */
1369 if (!(GRID(is->state, is->x, is->y) & G_MARK)) {
1370 debug(("...marking island (%d,%d) as full.\n", is->x, is->y));
1371 island_togglemark(is);
1372 didsth = true;
1373 }
1374 } else if (GRID(is->state, is->x, is->y) & G_MARK) {
1375 debug(("...island (%d,%d) is marked but unfinished!\n",
1376 is->x, is->y));
1377 return false; /* island has been marked unfinished; no solution from here. */
1378 } else {
1379 /* This is the interesting bit; we try and fill in more information
1380 * about this island. */
1381 if (is->count == bridges + nspaces) {
1382 if (solve_fill(is) > 0) didsth = true;
1383 } else if (is->count > ((nadj-1) * is->state->maxb)) {
1384 /* must have at least one bridge in each possible direction. */
1385 if (solve_fillone(is) > 0) didsth = true;
1386 }
1387 }
1388 if (didsth) {
1389 map_update_possibles(is->state);
1390 *didsth_r = true;
1391 }
1392 return true;
1393}
1394
1395/* returns true if a new line here would cause a loop. */
1396static bool solve_island_checkloop(struct island *is, int direction)
1397{
1398 struct island *is_orth;
1399 DSF *dsf = is->state->solver->dsf;
1400 int d1, d2;
1401 game_state *state = is->state;
1402
1403 if (is->state->allowloops)
1404 return false; /* don't care anyway */
1405 if (island_hasbridge(is, direction))
1406 return false; /* already has a bridge */
1407 if (island_isadj(is, direction) == 0)
1408 return false; /* no adj island */
1409
1410 is_orth = INDEX(is->state, gridi,
1411 ISLAND_ORTHX(is,direction),
1412 ISLAND_ORTHY(is,direction));
1413 if (!is_orth) return false;
1414
1415 d1 = DINDEX(is->x, is->y);
1416 d2 = DINDEX(is_orth->x, is_orth->y);
1417 if (dsf_equivalent(dsf, d1, d2)) {
1418 /* two islands are connected already; don't join them. */
1419 return true;
1420 }
1421 return false;
1422}
1423
1424static bool solve_island_stage2(struct island *is, bool *didsth_r)
1425{
1426 int navail = 0, nadj, i;
1427 bool added = false, removed = false;
1428
1429 assert(didsth_r);
1430
1431 for (i = 0; i < is->adj.npoints; i++) {
1432 if (solve_island_checkloop(is, i)) {
1433 debug(("removing possible loop at (%d,%d) direction %d.\n",
1434 is->x, is->y, i));
1435 solve_join(is, i, -1, false);
1436 map_update_possibles(is->state);
1437 removed = true;
1438 } else {
1439 navail += island_isadj(is, i);
1440 /*debug(("stage2: navail for (%d,%d) direction (%d,%d) is %d.\n",
1441 is->x, is->y,
1442 is->adj.points[i].dx, is->adj.points[i].dy,
1443 island_isadj(is, i)));*/
1444 }
1445 }
1446
1447 /*debug(("island at (%d,%d) navail %d: checking...\n", is->x, is->y, navail));*/
1448
1449 for (i = 0; i < is->adj.npoints; i++) {
1450 if (!island_hasbridge(is, i)) {
1451 nadj = island_isadj(is, i);
1452 if (nadj > 0 && (navail - nadj) < is->count) {
1453 /* we couldn't now complete the island without at
1454 * least one bridge here; put it in. */
1455 /*debug(("nadj %d, navail %d, is->count %d.\n",
1456 nadj, navail, is->count));*/
1457 debug(("island at (%d,%d) direction (%d,%d) must have 1 bridge\n",
1458 is->x, is->y,
1459 is->adj.points[i].dx, is->adj.points[i].dy));
1460 solve_join(is, i, 1, false);
1461 added = true;
1462 /*debug_state(is->state);
1463 debug_possibles(is->state);*/
1464 }
1465 }
1466 }
1467 if (added) map_update_possibles(is->state);
1468 if (added || removed) *didsth_r = true;
1469 return true;
1470}
1471
1472static bool solve_island_subgroup(struct island *is, int direction)
1473{
1474 struct island *is_join;
1475 int nislands;
1476 DSF *dsf = is->state->solver->dsf;
1477 game_state *state = is->state;
1478
1479 debug(("..checking subgroups.\n"));
1480
1481 /* if is isn't full, return 0. */
1482 if (island_countbridges(is) < is->count) {
1483 debug(("...orig island (%d,%d) not full.\n", is->x, is->y));
1484 return false;
1485 }
1486
1487 if (direction >= 0) {
1488 is_join = INDEX(state, gridi,
1489 ISLAND_ORTHX(is, direction),
1490 ISLAND_ORTHY(is, direction));
1491 assert(is_join);
1492
1493 /* if is_join isn't full, return 0. */
1494 if (island_countbridges(is_join) < is_join->count) {
1495 debug(("...dest island (%d,%d) not full.\n",
1496 is_join->x, is_join->y));
1497 return false;
1498 }
1499 }
1500
1501 /* Check group membership for is->dsf; if it's full return 1. */
1502 if (map_group_check(state, dsf_canonify(dsf, DINDEX(is->x,is->y)),
1503 false, &nislands)) {
1504 if (nislands < state->n_islands) {
1505 /* we have a full subgroup that isn't the whole set.
1506 * This isn't allowed. */
1507 debug(("island at (%d,%d) makes full subgroup, disallowing.\n",
1508 is->x, is->y));
1509 return true;
1510 } else {
1511 debug(("...has finished puzzle.\n"));
1512 }
1513 }
1514 return false;
1515}
1516
1517static bool solve_island_impossible(game_state *state)
1518{
1519 struct island *is;
1520 int i;
1521
1522 /* If any islands are impossible, return 1. */
1523 for (i = 0; i < state->n_islands; i++) {
1524 is = &state->islands[i];
1525 if (island_impossible(is, false)) {
1526 debug(("island at (%d,%d) has become impossible, disallowing.\n",
1527 is->x, is->y));
1528 return true;
1529 }
1530 }
1531 return false;
1532}
1533
1534/* Bear in mind that this function is really rather inefficient. */
1535static bool solve_island_stage3(struct island *is, bool *didsth_r)
1536{
1537 int i, n, x, y, missing, spc, curr, maxb;
1538 bool didsth = false;
1539 struct solver_state *ss = is->state->solver;
1540
1541 assert(didsth_r);
1542
1543 missing = is->count - island_countbridges(is);
1544 if (missing <= 0) return true;
1545
1546 for (i = 0; i < is->adj.npoints; i++) {
1547 x = is->adj.points[i].x;
1548 y = is->adj.points[i].y;
1549 spc = island_adjspace(is, true, missing, i);
1550 if (spc == 0) continue;
1551
1552 curr = GRIDCOUNT(is->state, x, y,
1553 is->adj.points[i].dx ? G_LINEH : G_LINEV);
1554 debug(("island at (%d,%d) s3, trying %d - %d bridges.\n",
1555 is->x, is->y, curr+1, curr+spc));
1556
1557 /* Now we know that this island could have more bridges,
1558 * to bring the total from curr+1 to curr+spc. */
1559 maxb = -1;
1560 /* We have to squirrel the dsf away and restore it afterwards;
1561 * it is additive only, and can't be removed from. */
1562 dsf_copy(ss->tmpdsf, ss->dsf);
1563 for (n = curr+1; n <= curr+spc; n++) {
1564 solve_join(is, i, n, false);
1565 map_update_possibles(is->state);
1566
1567 if (solve_island_subgroup(is, i) ||
1568 solve_island_impossible(is->state)) {
1569 maxb = n-1;
1570 debug(("island at (%d,%d) d(%d,%d) new max of %d bridges:\n",
1571 is->x, is->y,
1572 is->adj.points[i].dx, is->adj.points[i].dy,
1573 maxb));
1574 break;
1575 }
1576 }
1577 solve_join(is, i, curr, false); /* put back to before. */
1578 dsf_copy(ss->dsf, ss->tmpdsf);
1579
1580 if (maxb != -1) {
1581 /*debug_state(is->state);*/
1582 if (maxb == 0) {
1583 debug(("...adding NOLINE.\n"));
1584 solve_join(is, i, -1, false); /* we can't have any bridges here. */
1585 } else {
1586 debug(("...setting maximum\n"));
1587 solve_join(is, i, maxb, true);
1588 }
1589 didsth = true;
1590 }
1591 map_update_possibles(is->state);
1592 }
1593
1594 for (i = 0; i < is->adj.npoints; i++) {
1595 /*
1596 * Now check to see if any currently empty direction must have
1597 * at least one bridge in order to avoid forming an isolated
1598 * subgraph. This differs from the check above in that it
1599 * considers multiple target islands. For example:
1600 *
1601 * 2 2 4
1602 * 1 3 2
1603 * 3
1604 * 4
1605 *
1606 * The example on the left can be handled by the above loop:
1607 * it will observe that connecting the central 2 twice to the
1608 * left would form an isolated subgraph, and hence it will
1609 * restrict that 2 to at most one bridge in that direction.
1610 * But the example on the right won't be handled by that loop,
1611 * because the deduction requires us to imagine connecting the
1612 * 3 to _both_ the 1 and 2 at once to form an isolated
1613 * subgraph.
1614 *
1615 * This pass is necessary _as well_ as the above one, because
1616 * neither can do the other's job. In the left one,
1617 * restricting the direction which _would_ cause trouble can
1618 * be done even if it's not yet clear which of the remaining
1619 * directions has to have a compensatory bridge; whereas the
1620 * pass below that can handle the right-hand example does need
1621 * to know what direction to point the necessary bridge in.
1622 *
1623 * Neither pass can handle the most general case, in which we
1624 * observe that an arbitrary subset of an island's neighbours
1625 * would form an isolated subgraph with it if it connected
1626 * maximally to them, and hence that at least one bridge must
1627 * point to some neighbour outside that subset but we don't
1628 * know which neighbour. To handle that, we'd have to have a
1629 * richer data format for the solver, which could cope with
1630 * recording the idea that at least one of two edges must have
1631 * a bridge.
1632 */
1633 bool got = false;
1634 int before[4];
1635 int j;
1636
1637 spc = island_adjspace(is, true, missing, i);
1638 if (spc == 0) continue;
1639
1640 for (j = 0; j < is->adj.npoints; j++)
1641 before[j] = GRIDCOUNT(is->state,
1642 is->adj.points[j].x,
1643 is->adj.points[j].y,
1644 is->adj.points[j].dx ? G_LINEH : G_LINEV);
1645 if (before[i] != 0) continue; /* this idea is pointless otherwise */
1646
1647 dsf_copy(ss->tmpdsf, ss->dsf);
1648
1649 for (j = 0; j < is->adj.npoints; j++) {
1650 spc = island_adjspace(is, true, missing, j);
1651 if (spc == 0) continue;
1652 if (j == i) continue;
1653 solve_join(is, j, before[j] + spc, false);
1654 }
1655 map_update_possibles(is->state);
1656
1657 if (solve_island_subgroup(is, -1))
1658 got = true;
1659
1660 for (j = 0; j < is->adj.npoints; j++)
1661 solve_join(is, j, before[j], false);
1662 dsf_copy(ss->dsf, ss->tmpdsf);
1663
1664 if (got) {
1665 debug(("island at (%d,%d) must connect in direction (%d,%d) to"
1666 " avoid full subgroup.\n",
1667 is->x, is->y, is->adj.points[i].dx, is->adj.points[i].dy));
1668 solve_join(is, i, 1, false);
1669 didsth = true;
1670 }
1671
1672 map_update_possibles(is->state);
1673 }
1674
1675 if (didsth) *didsth_r = didsth;
1676 return true;
1677}
1678
1679#define CONTINUE_IF_FULL do { \
1680if (GRID(state, is->x, is->y) & G_MARK) { \
1681 /* island full, don't try fixing it */ \
1682 continue; \
1683} } while(0)
1684
1685static int solve_sub(game_state *state, int difficulty, int depth)
1686{
1687 struct island *is;
1688 int i;
1689
1690 while (1) {
1691 bool didsth = false;
1692
1693 /* First island iteration: things we can work out by looking at
1694 * properties of the island as a whole. */
1695 for (i = 0; i < state->n_islands; i++) {
1696 is = &state->islands[i];
1697 if (!solve_island_stage1(is, &didsth)) return 0;
1698 }
1699 if (didsth) continue;
1700 else if (difficulty < 1) break;
1701
1702 /* Second island iteration: thing we can work out by looking at
1703 * properties of individual island connections. */
1704 for (i = 0; i < state->n_islands; i++) {
1705 is = &state->islands[i];
1706 CONTINUE_IF_FULL;
1707 if (!solve_island_stage2(is, &didsth)) return 0;
1708 }
1709 if (didsth) continue;
1710 else if (difficulty < 2) break;
1711
1712 /* Third island iteration: things we can only work out by looking
1713 * at groups of islands. */
1714 for (i = 0; i < state->n_islands; i++) {
1715 is = &state->islands[i];
1716 if (!solve_island_stage3(is, &didsth)) return 0;
1717 }
1718 if (didsth) continue;
1719 else if (difficulty < 3) break;
1720
1721 /* If we can be bothered, write a recursive solver to finish here. */
1722 break;
1723 }
1724 if (map_check(state)) return 1; /* solved it */
1725 return 0;
1726}
1727
1728static void solve_for_hint(game_state *state)
1729{
1730 map_group(state);
1731 solve_sub(state, 10, 0);
1732}
1733
1734static int solve_from_scratch(game_state *state, int difficulty)
1735{
1736 map_clear(state);
1737 map_group(state);
1738 map_update_possibles(state);
1739 return solve_sub(state, difficulty, 0);
1740}
1741
1742/* --- New game functions --- */
1743
1744static game_state *new_state(const game_params *params)
1745{
1746 game_state *ret = snew(game_state);
1747 int wh = params->w * params->h, i;
1748
1749 ret->w = params->w;
1750 ret->h = params->h;
1751 ret->allowloops = params->allowloops;
1752 ret->maxb = params->maxb;
1753 ret->params = *params;
1754
1755 ret->grid = snewn(wh, grid_type);
1756 memset(ret->grid, 0, GRIDSZ(ret));
1757
1758 ret->wha = snewn(wh*N_WH_ARRAYS, char);
1759 memset(ret->wha, 0, wh*N_WH_ARRAYS*sizeof(char));
1760
1761 ret->possv = ret->wha;
1762 ret->possh = ret->wha + wh;
1763 ret->lines = ret->wha + wh*2;
1764 ret->maxv = ret->wha + wh*3;
1765 ret->maxh = ret->wha + wh*4;
1766
1767 memset(ret->maxv, ret->maxb, wh*sizeof(char));
1768 memset(ret->maxh, ret->maxb, wh*sizeof(char));
1769
1770 ret->islands = NULL;
1771 ret->n_islands = 0;
1772 ret->n_islands_alloc = 0;
1773
1774 ret->gridi = snewn(wh, struct island *);
1775 for (i = 0; i < wh; i++) ret->gridi[i] = NULL;
1776
1777 ret->solved = false;
1778 ret->completed = false;
1779
1780 ret->solver = snew(struct solver_state);
1781 ret->solver->dsf = dsf_new(wh);
1782 ret->solver->tmpdsf = dsf_new(wh);
1783
1784 ret->solver->refcount = 1;
1785
1786 return ret;
1787}
1788
1789static game_state *dup_game(const game_state *state)
1790{
1791 game_state *ret = snew(game_state);
1792 int wh = state->w*state->h;
1793
1794 ret->w = state->w;
1795 ret->h = state->h;
1796 ret->allowloops = state->allowloops;
1797 ret->maxb = state->maxb;
1798 ret->params = state->params;
1799
1800 ret->grid = snewn(wh, grid_type);
1801 memcpy(ret->grid, state->grid, GRIDSZ(ret));
1802
1803 ret->wha = snewn(wh*N_WH_ARRAYS, char);
1804 memcpy(ret->wha, state->wha, wh*N_WH_ARRAYS*sizeof(char));
1805
1806 ret->possv = ret->wha;
1807 ret->possh = ret->wha + wh;
1808 ret->lines = ret->wha + wh*2;
1809 ret->maxv = ret->wha + wh*3;
1810 ret->maxh = ret->wha + wh*4;
1811
1812 ret->islands = snewn(state->n_islands, struct island);
1813 memcpy(ret->islands, state->islands, state->n_islands * sizeof(struct island));
1814 ret->n_islands = ret->n_islands_alloc = state->n_islands;
1815
1816 ret->gridi = snewn(wh, struct island *);
1817 fixup_islands_for_realloc(ret);
1818
1819 ret->solved = state->solved;
1820 ret->completed = state->completed;
1821
1822 ret->solver = state->solver;
1823 ret->solver->refcount++;
1824
1825 return ret;
1826}
1827
1828static void free_game(game_state *state)
1829{
1830 if (--state->solver->refcount <= 0) {
1831 dsf_free(state->solver->dsf);
1832 dsf_free(state->solver->tmpdsf);
1833 sfree(state->solver);
1834 }
1835
1836 sfree(state->islands);
1837 sfree(state->gridi);
1838
1839 sfree(state->wha);
1840
1841 sfree(state->grid);
1842 sfree(state);
1843}
1844
1845#define MAX_NEWISLAND_TRIES 50
1846#define MIN_SENSIBLE_ISLANDS 3
1847
1848#define ORDER(a,b) do { if (a < b) { int tmp=a; int a=b; int b=tmp; } } while(0)
1849
1850static char *new_game_desc(const game_params *params, random_state *rs,
1851 char **aux, bool interactive)
1852{
1853 game_state *tobuild = NULL;
1854 int i, j, wh = params->w * params->h, x, y, dx, dy;
1855 int minx, miny, maxx, maxy, joinx, joiny, newx, newy, diffx, diffy;
1856 int ni_req = max((params->islands * wh) / 100, MIN_SENSIBLE_ISLANDS), ni_curr, ni_bad;
1857 struct island *is, *is2;
1858 char *ret;
1859 unsigned int echeck;
1860
1861 /* pick a first island position randomly. */
1862generate:
1863 if (tobuild) free_game(tobuild);
1864 tobuild = new_state(params);
1865
1866 x = random_upto(rs, params->w);
1867 y = random_upto(rs, params->h);
1868 island_add(tobuild, x, y, 0);
1869 ni_curr = 1;
1870 ni_bad = 0;
1871 debug(("Created initial island at (%d,%d).\n", x, y));
1872
1873 while (ni_curr < ni_req) {
1874 /* Pick a random island to try and extend from. */
1875 i = random_upto(rs, tobuild->n_islands);
1876 is = &tobuild->islands[i];
1877
1878 /* Pick a random direction to extend in. */
1879 j = random_upto(rs, is->adj.npoints);
1880 dx = is->adj.points[j].x - is->x;
1881 dy = is->adj.points[j].y - is->y;
1882
1883 /* Find out limits of where we could put a new island. */
1884 joinx = joiny = -1;
1885 minx = is->x + 2*dx; miny = is->y + 2*dy; /* closest is 2 units away. */
1886 x = is->x+dx; y = is->y+dy;
1887 if (GRID(tobuild,x,y) & (G_LINEV|G_LINEH)) {
1888 /* already a line next to the island, continue. */
1889 goto bad;
1890 }
1891 while (1) {
1892 if (x < 0 || x >= params->w || y < 0 || y >= params->h) {
1893 /* got past the edge; put a possible at the island
1894 * and exit. */
1895 maxx = x-dx; maxy = y-dy;
1896 goto foundmax;
1897 }
1898 if (GRID(tobuild,x,y) & G_ISLAND) {
1899 /* could join up to an existing island... */
1900 joinx = x; joiny = y;
1901 /* ... or make a new one 2 spaces away. */
1902 maxx = x - 2*dx; maxy = y - 2*dy;
1903 goto foundmax;
1904 } else if (GRID(tobuild,x,y) & (G_LINEV|G_LINEH)) {
1905 /* could make a new one 1 space away from the line. */
1906 maxx = x - dx; maxy = y - dy;
1907 goto foundmax;
1908 }
1909 x += dx; y += dy;
1910 }
1911
1912foundmax:
1913 debug(("Island at (%d,%d) with d(%d,%d) has new positions "
1914 "(%d,%d) -> (%d,%d), join (%d,%d).\n",
1915 is->x, is->y, dx, dy, minx, miny, maxx, maxy, joinx, joiny));
1916 /* Now we know where we could either put a new island
1917 * (between min and max), or (if loops are allowed) could join on
1918 * to an existing island (at join). */
1919 if (params->allowloops && joinx != -1 && joiny != -1) {
1920 if (random_upto(rs, 100) < (unsigned long)params->expansion) {
1921 is2 = INDEX(tobuild, gridi, joinx, joiny);
1922 debug(("Joining island at (%d,%d) to (%d,%d).\n",
1923 is->x, is->y, is2->x, is2->y));
1924 goto join;
1925 }
1926 }
1927 diffx = (maxx - minx) * dx;
1928 diffy = (maxy - miny) * dy;
1929 if (diffx < 0 || diffy < 0) goto bad;
1930 if (random_upto(rs,100) < (unsigned long)params->expansion) {
1931 newx = maxx; newy = maxy;
1932 debug(("Creating new island at (%d,%d) (expanded).\n", newx, newy));
1933 } else {
1934 newx = minx + random_upto(rs,diffx+1)*dx;
1935 newy = miny + random_upto(rs,diffy+1)*dy;
1936 debug(("Creating new island at (%d,%d).\n", newx, newy));
1937 }
1938 /* check we're not next to island in the other orthogonal direction. */
1939 if ((INGRID(tobuild,newx+dy,newy+dx) && (GRID(tobuild,newx+dy,newy+dx) & G_ISLAND)) ||
1940 (INGRID(tobuild,newx-dy,newy-dx) && (GRID(tobuild,newx-dy,newy-dx) & G_ISLAND))) {
1941 debug(("New location is adjacent to island, skipping.\n"));
1942 goto bad;
1943 }
1944 is2 = island_add(tobuild, newx, newy, 0);
1945 /* Must get is again at this point; the array might have
1946 * been realloced by island_add... */
1947 is = &tobuild->islands[i]; /* ...but order will not change. */
1948
1949 ni_curr++; ni_bad = 0;
1950join:
1951 island_join(is, is2, random_upto(rs, tobuild->maxb)+1, false);
1952 debug_state(tobuild);
1953 continue;
1954
1955bad:
1956 ni_bad++;
1957 if (ni_bad > MAX_NEWISLAND_TRIES) {
1958 debug(("Unable to create any new islands after %d tries; "
1959 "created %d [%d%%] (instead of %d [%d%%] requested).\n",
1960 MAX_NEWISLAND_TRIES,
1961 ni_curr, ni_curr * 100 / wh,
1962 ni_req, ni_req * 100 / wh));
1963 goto generated;
1964 }
1965 }
1966
1967generated:
1968 if (ni_curr == 1) {
1969 debug(("Only generated one island (!), retrying.\n"));
1970 goto generate;
1971 }
1972 /* Check we have at least one island on each extremity of the grid. */
1973 echeck = 0;
1974 for (x = 0; x < params->w; x++) {
1975 if (INDEX(tobuild, gridi, x, 0)) echeck |= 1;
1976 if (INDEX(tobuild, gridi, x, params->h-1)) echeck |= 2;
1977 }
1978 for (y = 0; y < params->h; y++) {
1979 if (INDEX(tobuild, gridi, 0, y)) echeck |= 4;
1980 if (INDEX(tobuild, gridi, params->w-1, y)) echeck |= 8;
1981 }
1982 if (echeck != 15) {
1983 debug(("Generated grid doesn't fill to sides, retrying.\n"));
1984 goto generate;
1985 }
1986
1987 map_count(tobuild);
1988 map_find_orthogonal(tobuild);
1989
1990 if (params->difficulty > 0) {
1991 if ((ni_curr > MIN_SENSIBLE_ISLANDS) &&
1992 (solve_from_scratch(tobuild, params->difficulty-1) > 0)) {
1993 debug(("Grid is solvable at difficulty %d (too easy); retrying.\n",
1994 params->difficulty-1));
1995 goto generate;
1996 }
1997 }
1998
1999 if (solve_from_scratch(tobuild, params->difficulty) == 0) {
2000 debug(("Grid not solvable at difficulty %d, (too hard); retrying.\n",
2001 params->difficulty));
2002 goto generate;
2003 }
2004
2005 /* ... tobuild is now solved. We rely on this making the diff for aux. */
2006 debug_state(tobuild);
2007 ret = encode_game(tobuild);
2008 {
2009 game_state *clean = dup_game(tobuild);
2010 map_clear(clean);
2011 map_update_possibles(clean);
2012 *aux = game_state_diff(clean, tobuild);
2013 free_game(clean);
2014 }
2015 free_game(tobuild);
2016
2017 return ret;
2018}
2019
2020static const char *validate_desc(const game_params *params, const char *desc)
2021{
2022 int i, j, wh = params->w * params->h, nislands = 0;
2023 bool *last_row = snewn(params->w, bool);
2024
2025 memset(last_row, 0, params->w * sizeof(bool));
2026 for (i = 0; i < wh; i++) {
2027 if ((*desc >= '1' && *desc <= '9') || (*desc >= 'A' && *desc <= 'G')) {
2028 nislands++;
2029 /* Look for other islands to the left and above. */
2030 if ((i % params->w > 0 && last_row[i % params->w - 1]) ||
2031 last_row[i % params->w]) {
2032 sfree(last_row);
2033 return "Game description contains joined islands";
2034 }
2035 last_row[i % params->w] = true;
2036 } else if (*desc >= 'a' && *desc <= 'z') {
2037 for (j = 0; j < *desc - 'a' + 1; j++)
2038 last_row[(i + j) % params->w] = false;
2039 i += *desc - 'a'; /* plus the i++ */
2040 } else if (!*desc) {
2041 sfree(last_row);
2042 return "Game description shorter than expected";
2043 } else {
2044 sfree(last_row);
2045 return "Game description contains unexpected character";
2046 }
2047 desc++;
2048 }
2049 sfree(last_row);
2050 if (*desc || i > wh)
2051 return "Game description longer than expected";
2052 if (nislands < 2)
2053 return "Game description has too few islands";
2054
2055 return NULL;
2056}
2057
2058static game_state *new_game_sub(const game_params *params, const char *desc)
2059{
2060 game_state *state = new_state(params);
2061 int x, y, run = 0;
2062
2063 debug(("new_game[_sub]: desc = '%s'.\n", desc));
2064
2065 for (y = 0; y < params->h; y++) {
2066 for (x = 0; x < params->w; x++) {
2067 char c = '\0';
2068
2069 if (run == 0) {
2070 c = *desc++;
2071 assert(c != 'S');
2072 if (c >= 'a' && c <= 'z')
2073 run = c - 'a' + 1;
2074 }
2075
2076 if (run > 0) {
2077 c = 'S';
2078 run--;
2079 }
2080
2081 switch (c) {
2082 case '1': case '2': case '3': case '4':
2083 case '5': case '6': case '7': case '8': case '9':
2084 island_add(state, x, y, (c - '0'));
2085 break;
2086
2087 case 'A': case 'B': case 'C': case 'D':
2088 case 'E': case 'F': case 'G':
2089 island_add(state, x, y, (c - 'A') + 10);
2090 break;
2091
2092 case 'S':
2093 /* empty square */
2094 break;
2095
2096 default:
2097 assert(!"Malformed desc.");
2098 break;
2099 }
2100 }
2101 }
2102 if (*desc) assert(!"Over-long desc.");
2103
2104 map_find_orthogonal(state);
2105 map_update_possibles(state);
2106
2107 return state;
2108}
2109
2110static game_state *new_game(midend *me, const game_params *params,
2111 const char *desc)
2112{
2113 return new_game_sub(params, desc);
2114}
2115
2116struct game_ui {
2117 int dragx_src, dragy_src; /* source; -1 means no drag */
2118 int dragx_dst, dragy_dst; /* src's closest orth island. */
2119 grid_type todraw;
2120 bool dragging, drag_is_noline;
2121 int nlines;
2122
2123 int cur_x, cur_y; /* cursor position */
2124 bool cur_visible;
2125 bool show_hints;
2126};
2127
2128static char *ui_cancel_drag(game_ui *ui)
2129{
2130 ui->dragx_src = ui->dragy_src = -1;
2131 ui->dragx_dst = ui->dragy_dst = -1;
2132 ui->dragging = false;
2133 return MOVE_UI_UPDATE;
2134}
2135
2136static game_ui *new_ui(const game_state *state)
2137{
2138 game_ui *ui = snew(game_ui);
2139 ui_cancel_drag(ui);
2140 if (state != NULL) {
2141 ui->cur_x = state->islands[0].x;
2142 ui->cur_y = state->islands[0].y;
2143 }
2144 ui->cur_visible = getenv_bool("PUZZLES_SHOW_CURSOR", false);
2145 ui->show_hints = false;
2146 return ui;
2147}
2148
2149static config_item *get_prefs(game_ui *ui)
2150{
2151 config_item *ret;
2152
2153 ret = snewn(N_PREF_ITEMS+1, config_item);
2154
2155 ret[PREF_SHOW_HINTS].name = "Show possible bridge locations";
2156 ret[PREF_SHOW_HINTS].kw = "show-hints";
2157 ret[PREF_SHOW_HINTS].type = C_BOOLEAN;
2158 ret[PREF_SHOW_HINTS].u.boolean.bval = ui->show_hints;
2159
2160 ret[N_PREF_ITEMS].name = NULL;
2161 ret[N_PREF_ITEMS].type = C_END;
2162
2163 return ret;
2164}
2165
2166static void set_prefs(game_ui *ui, const config_item *cfg)
2167{
2168 ui->show_hints = cfg[PREF_SHOW_HINTS].u.boolean.bval;
2169}
2170
2171static void free_ui(game_ui *ui)
2172{
2173 sfree(ui);
2174}
2175
2176static void game_changed_state(game_ui *ui, const game_state *oldstate,
2177 const game_state *newstate)
2178{
2179}
2180
2181static const char *current_key_label(const game_ui *ui,
2182 const game_state *state, int button)
2183{
2184 if (IS_CURSOR_SELECT(button)) {
2185 if (!ui->cur_visible)
2186 return ""; /* Actually shows cursor. */
2187 if (ui->dragging || button == CURSOR_SELECT2)
2188 return "Finished";
2189 if (GRID(state, ui->cur_x, ui->cur_y) & G_ISLAND)
2190 return "Select";
2191 }
2192 return "";
2193}
2194
2195struct game_drawstate {
2196 int tilesize;
2197 int w, h;
2198 unsigned long *grid, *newgrid;
2199 int *lv, *lh;
2200 bool started, dragging;
2201};
2202
2203
2204static void game_get_cursor_location(const game_ui *ui,
2205 const game_drawstate *ds,
2206 const game_state *state,
2207 const game_params *params,
2208 int *x, int *y, int *w, int *h)
2209{
2210 if(ui->cur_visible) {
2211 *x = COORD(ui->cur_x);
2212 *y = COORD(ui->cur_y);
2213 *w = *h = TILE_SIZE;
2214 }
2215}
2216
2217/*
2218 * The contents of ds->grid are complicated, because of the circular
2219 * islands which overlap their own grid square into neighbouring
2220 * squares. An island square can contain pieces of the bridges in all
2221 * directions, and conversely a bridge square can be intruded on by
2222 * islands from any direction.
2223 *
2224 * So we define one group of flags describing what's important about
2225 * an island, and another describing a bridge. Island squares' entries
2226 * in ds->grid contain one of the former and four of the latter; bridge
2227 * squares, four of the former and _two_ of the latter - because a
2228 * horizontal and vertical 'bridge' can cross, when one of them is a
2229 * 'no bridge here' pencil mark.
2230 *
2231 * Bridge flags need to indicate 0-4 actual bridges (3 bits), a 'no
2232 * bridge' row of crosses, or a grey hint line; that's 7
2233 * possibilities, so 3 bits suffice. But then we also need to vary the
2234 * colours: the bridges can turn COL_WARNING if they're part of a loop
2235 * in no-loops mode, COL_HIGHLIGHT during a victory flash, or
2236 * COL_SELECTED if they're the bridge the user is currently dragging,
2237 * so that's 2 more bits for foreground colour. Also bridges can be
2238 * backed by COL_MARK if they're locked by the user, so that's one
2239 * more bit, making 6 bits per bridge direction.
2240 *
2241 * Island flags omit the actual island clue (it never changes during
2242 * the game, so doesn't have to be stored in ds->grid to check against
2243 * the previous version), so they just need to include 2 bits for
2244 * foreground colour (an island can be normal, COL_HIGHLIGHT during
2245 * victory, COL_WARNING if its clue is unsatisfiable, or COL_SELECTED
2246 * if it's part of the user's drag) and 2 bits for background (normal,
2247 * COL_MARK for a locked island, COL_CURSOR for the keyboard cursor).
2248 * That's 4 bits per island direction. We must also indicate whether
2249 * no island is present at all (in the case where the island is
2250 * potentially intruding into the side of a line square), which we do
2251 * using the unused 4th value of the background field.
2252 *
2253 * So an island square needs 4 + 4*6 = 28 bits, while a bridge square
2254 * needs 4*4 + 2*6 = 28 bits too. Both only just fit in 32 bits, which
2255 * is handy, because otherwise we'd have to faff around forever with
2256 * little structs!
2257 */
2258/* Flags for line data */
2259#define DL_COUNTMASK 0x07
2260#define DL_COUNT_CROSS 0x06
2261#define DL_COUNT_HINT 0x07
2262#define DL_COLMASK 0x18
2263#define DL_COL_NORMAL 0x00
2264#define DL_COL_WARNING 0x08
2265#define DL_COL_FLASH 0x10
2266#define DL_COL_SELECTED 0x18
2267#define DL_LOCK 0x20
2268#define DL_MASK 0x3F
2269/* Flags for island data */
2270#define DI_COLMASK 0x03
2271#define DI_COL_NORMAL 0x00
2272#define DI_COL_FLASH 0x01
2273#define DI_COL_WARNING 0x02
2274#define DI_COL_SELECTED 0x03
2275#define DI_BGMASK 0x0C
2276#define DI_BG_NO_ISLAND 0x00
2277#define DI_BG_NORMAL 0x04
2278#define DI_BG_MARK 0x08
2279#define DI_BG_CURSOR 0x0C
2280#define DI_MASK 0x0F
2281/* Shift counts for the format of a 32-bit word in an island square */
2282#define D_I_ISLAND_SHIFT 0
2283#define D_I_LINE_SHIFT_L 4
2284#define D_I_LINE_SHIFT_R 10
2285#define D_I_LINE_SHIFT_U 16
2286#define D_I_LINE_SHIFT_D 24
2287/* Shift counts for the format of a 32-bit word in a line square */
2288#define D_L_ISLAND_SHIFT_L 0
2289#define D_L_ISLAND_SHIFT_R 4
2290#define D_L_ISLAND_SHIFT_U 8
2291#define D_L_ISLAND_SHIFT_D 12
2292#define D_L_LINE_SHIFT_H 16
2293#define D_L_LINE_SHIFT_V 22
2294
2295static char *update_drag_dst(const game_state *state, game_ui *ui,
2296 const game_drawstate *ds, int nx, int ny)
2297{
2298 int ox, oy, dx, dy, i, currl, maxb;
2299 struct island *is;
2300 grid_type gtype, ntype, mtype, curr;
2301
2302 if (ui->dragx_src == -1 || ui->dragy_src == -1) return NULL;
2303
2304 ui->dragx_dst = -1;
2305 ui->dragy_dst = -1;
2306
2307 /* work out which of the four directions we're closest to... */
2308 ox = COORD(ui->dragx_src) + TILE_SIZE/2;
2309 oy = COORD(ui->dragy_src) + TILE_SIZE/2;
2310
2311 if (abs(nx-ox) < abs(ny-oy)) {
2312 dx = 0;
2313 dy = (ny-oy) < 0 ? -1 : 1;
2314 if (!INGRID(state, ui->dragx_src+dx, ui->dragy_src+dy))
2315 return MOVE_UI_UPDATE;
2316 gtype = G_LINEV; ntype = G_NOLINEV; mtype = G_MARKV;
2317 maxb = INDEX(state, maxv, ui->dragx_src+dx, ui->dragy_src+dy);
2318 } else {
2319 dy = 0;
2320 dx = (nx-ox) < 0 ? -1 : 1;
2321 if (!INGRID(state, ui->dragx_src+dx, ui->dragy_src+dy))
2322 return MOVE_UI_UPDATE;
2323 gtype = G_LINEH; ntype = G_NOLINEH; mtype = G_MARKH;
2324 maxb = INDEX(state, maxh, ui->dragx_src+dx, ui->dragy_src+dy);
2325 }
2326 if (ui->drag_is_noline) {
2327 ui->todraw = ntype;
2328 } else {
2329 curr = GRID(state, ui->dragx_src+dx, ui->dragy_src+dy);
2330 currl = INDEX(state, lines, ui->dragx_src+dx, ui->dragy_src+dy);
2331
2332 if (curr & gtype) {
2333 if (currl == maxb) {
2334 ui->todraw = 0;
2335 ui->nlines = 0;
2336 } else {
2337 ui->todraw = gtype;
2338 ui->nlines = currl + 1;
2339 }
2340 } else {
2341 ui->todraw = gtype;
2342 ui->nlines = 1;
2343 }
2344 }
2345
2346 /* ... and see if there's an island off in that direction. */
2347 is = INDEX(state, gridi, ui->dragx_src, ui->dragy_src);
2348 for (i = 0; i < is->adj.npoints; i++) {
2349 if (is->adj.points[i].off == 0) continue;
2350 curr = GRID(state, is->x+dx, is->y+dy);
2351 if (curr & mtype) continue; /* don't allow changes to marked lines. */
2352 if (ui->drag_is_noline) {
2353 if (curr & gtype) continue; /* no no-line where already a line */
2354 } else {
2355 if (POSSIBLES(state, dx, is->x+dx, is->y+dy) == 0) continue; /* no line if !possible. */
2356 if (curr & ntype) continue; /* can't have a bridge where there's a no-line. */
2357 }
2358
2359 if (is->adj.points[i].dx == dx &&
2360 is->adj.points[i].dy == dy) {
2361 ui->dragx_dst = ISLAND_ORTHX(is,i);
2362 ui->dragy_dst = ISLAND_ORTHY(is,i);
2363 }
2364 }
2365 /*debug(("update_drag src (%d,%d) d(%d,%d) dst (%d,%d)\n",
2366 ui->dragx_src, ui->dragy_src, dx, dy,
2367 ui->dragx_dst, ui->dragy_dst));*/
2368 return MOVE_UI_UPDATE;
2369}
2370
2371static char *finish_drag(const game_state *state, game_ui *ui)
2372{
2373 char buf[80];
2374
2375 if (ui->dragx_src == -1 || ui->dragy_src == -1)
2376 return NULL;
2377 if (ui->dragx_dst == -1 || ui->dragy_dst == -1)
2378 return ui_cancel_drag(ui);
2379
2380 if (ui->drag_is_noline) {
2381 sprintf(buf, "N%d,%d,%d,%d",
2382 ui->dragx_src, ui->dragy_src,
2383 ui->dragx_dst, ui->dragy_dst);
2384 } else {
2385 sprintf(buf, "L%d,%d,%d,%d,%d",
2386 ui->dragx_src, ui->dragy_src,
2387 ui->dragx_dst, ui->dragy_dst, ui->nlines);
2388 }
2389
2390 ui_cancel_drag(ui);
2391
2392 return dupstr(buf);
2393}
2394
2395static char *interpret_move(const game_state *state, game_ui *ui,
2396 const game_drawstate *ds,
2397 int x, int y, int button)
2398{
2399 int gx = FROMCOORD(x), gy = FROMCOORD(y);
2400 char buf[80], *ret;
2401 grid_type ggrid = INGRID(state,gx,gy) ? GRID(state,gx,gy) : 0;
2402 bool shift = button & MOD_SHFT, control = button & MOD_CTRL;
2403 button = STRIP_BUTTON_MODIFIERS(button);
2404
2405 if (button == LEFT_BUTTON || button == RIGHT_BUTTON) {
2406 if (!INGRID(state, gx, gy)) return MOVE_UNUSED;
2407 ui->cur_visible = false;
2408 if (ggrid & G_ISLAND) {
2409 ui->dragx_src = gx;
2410 ui->dragy_src = gy;
2411 return MOVE_UI_UPDATE;
2412 } else
2413 return ui_cancel_drag(ui);
2414 } else if (button == LEFT_DRAG || button == RIGHT_DRAG) {
2415 if (INGRID(state, ui->dragx_src, ui->dragy_src)
2416 && (gx != ui->dragx_src || gy != ui->dragy_src)
2417 && !(GRID(state,ui->dragx_src,ui->dragy_src) & G_MARK)) {
2418 ui->dragging = true;
2419 ui->drag_is_noline = (button == RIGHT_DRAG);
2420 return update_drag_dst(state, ui, ds, x, y);
2421 } else {
2422 /* cancel a drag when we go back to the starting point */
2423 ui->dragx_dst = -1;
2424 ui->dragy_dst = -1;
2425 return MOVE_UI_UPDATE;
2426 }
2427 } else if (button == LEFT_RELEASE || button == RIGHT_RELEASE) {
2428 if (ui->dragging) {
2429 return finish_drag(state, ui);
2430 } else {
2431 if (!INGRID(state, ui->dragx_src, ui->dragy_src)
2432 || gx != ui->dragx_src || gy != ui->dragy_src) {
2433 return ui_cancel_drag(ui);
2434 }
2435 ui_cancel_drag(ui);
2436 if (!INGRID(state, gx, gy)) return MOVE_UNUSED;
2437 if (!(GRID(state, gx, gy) & G_ISLAND)) return MOVE_NO_EFFECT;
2438 sprintf(buf, "M%d,%d", gx, gy);
2439 return dupstr(buf);
2440 }
2441 } else if (button == 'h' || button == 'H') {
2442 game_state *solved = dup_game(state);
2443 solve_for_hint(solved);
2444 ret = game_state_diff(state, solved);
2445 free_game(solved);
2446 return ret;
2447 } else if (IS_CURSOR_MOVE(button)) {
2448 ui->cur_visible = true;
2449 if (control || shift) {
2450 ui->dragx_src = ui->cur_x;
2451 ui->dragy_src = ui->cur_y;
2452 ui->dragging = true;
2453 ui->drag_is_noline = !control;
2454 }
2455 if (ui->dragging) {
2456 int nx = ui->cur_x, ny = ui->cur_y;
2457
2458 move_cursor(button, &nx, &ny, state->w, state->h, false, NULL);
2459 if (nx == ui->cur_x && ny == ui->cur_y)
2460 return MOVE_NO_EFFECT;
2461 update_drag_dst(state, ui, ds,
2462 COORD(nx)+TILE_SIZE/2,
2463 COORD(ny)+TILE_SIZE/2);
2464 return finish_drag(state, ui);
2465 } else {
2466 int dx = (button == CURSOR_RIGHT) ? +1 : (button == CURSOR_LEFT) ? -1 : 0;
2467 int dy = (button == CURSOR_DOWN) ? +1 : (button == CURSOR_UP) ? -1 : 0;
2468 int dorthx = 1 - abs(dx), dorthy = 1 - abs(dy);
2469 int dir, orth, nx = x, ny = y;
2470
2471 /* 'orthorder' is a tweak to ensure that if you press RIGHT and
2472 * happen to move upwards, when you press LEFT you then tend
2473 * downwards (rather than upwards again). */
2474 int orthorder = (button == CURSOR_LEFT || button == CURSOR_UP) ? 1 : -1;
2475
2476 /* This attempts to find an island in the direction you're
2477 * asking for, broadly speaking. If you ask to go right, for
2478 * example, it'll look for islands to the right and slightly
2479 * above or below your current horiz. position, allowing
2480 * further above/below the further away it searches. */
2481
2482 assert(GRID(state, ui->cur_x, ui->cur_y) & G_ISLAND);
2483 /* currently this is depth-first (so orthogonally-adjacent
2484 * islands across the other side of the grid will be moved to
2485 * before closer islands slightly offset). Swap the order of
2486 * these two loops to change to breadth-first search. */
2487 for (orth = 0; ; orth++) {
2488 bool oingrid = false;
2489 for (dir = 1; ; dir++) {
2490 bool dingrid = false;
2491
2492 if (orth > dir) continue; /* only search in cone outwards. */
2493
2494 nx = ui->cur_x + dir*dx + orth*dorthx*orthorder;
2495 ny = ui->cur_y + dir*dy + orth*dorthy*orthorder;
2496 if (INGRID(state, nx, ny)) {
2497 dingrid = true;
2498 oingrid = true;
2499 if (GRID(state, nx, ny) & G_ISLAND) goto found;
2500 }
2501
2502 nx = ui->cur_x + dir*dx - orth*dorthx*orthorder;
2503 ny = ui->cur_y + dir*dy - orth*dorthy*orthorder;
2504 if (INGRID(state, nx, ny)) {
2505 dingrid = true;
2506 oingrid = true;
2507 if (GRID(state, nx, ny) & G_ISLAND) goto found;
2508 }
2509
2510 if (!dingrid) break;
2511 }
2512 if (!oingrid) return MOVE_UI_UPDATE;
2513 }
2514 /* not reached */
2515
2516found:
2517 ui->cur_x = nx;
2518 ui->cur_y = ny;
2519 return MOVE_UI_UPDATE;
2520 }
2521 } else if (IS_CURSOR_SELECT(button)) {
2522 if (!ui->cur_visible) {
2523 ui->cur_visible = true;
2524 return MOVE_UI_UPDATE;
2525 }
2526 if (ui->dragging || button == CURSOR_SELECT2) {
2527 ui_cancel_drag(ui);
2528 if (ui->dragx_dst == -1 && ui->dragy_dst == -1) {
2529 sprintf(buf, "M%d,%d", ui->cur_x, ui->cur_y);
2530 return dupstr(buf);
2531 } else
2532 return MOVE_UI_UPDATE;
2533 } else {
2534 grid_type v = GRID(state, ui->cur_x, ui->cur_y);
2535 if (v & G_ISLAND) {
2536 ui->dragging = true;
2537 ui->dragx_src = ui->cur_x;
2538 ui->dragy_src = ui->cur_y;
2539 ui->dragx_dst = ui->dragy_dst = -1;
2540 ui->drag_is_noline = (button == CURSOR_SELECT2);
2541 return MOVE_UI_UPDATE;
2542 }
2543 }
2544 } else if ((button >= '0' && button <= '9') ||
2545 (button >= 'a' && button <= 'f') ||
2546 (button >= 'A' && button <= 'F')) {
2547 /* jump to island with .count == number closest to cur_{x,y} */
2548 int best_x = -1, best_y = -1, best_sqdist = -1, number = -1, i;
2549
2550 if (button >= '0' && button <= '9')
2551 number = (button == '0' ? 16 : button - '0');
2552 else if (button >= 'a' && button <= 'f')
2553 number = 10 + button - 'a';
2554 else if (button >= 'A' && button <= 'F')
2555 number = 10 + button - 'A';
2556
2557 if (!ui->cur_visible) {
2558 ui->cur_visible = true;
2559 return MOVE_UI_UPDATE;
2560 }
2561
2562 for (i = 0; i < state->n_islands; ++i) {
2563 int x = state->islands[i].x, y = state->islands[i].y;
2564 int dx = x - ui->cur_x, dy = y - ui->cur_y;
2565 int sqdist = dx*dx + dy*dy;
2566
2567 if (state->islands[i].count != number)
2568 continue;
2569 if (x == ui->cur_x && y == ui->cur_y)
2570 continue;
2571
2572 /* new_game() reads the islands in row-major order, so by
2573 * breaking ties in favor of `first in state->islands' we
2574 * also break ties by `lexicographically smallest (y, x)'.
2575 * Thus, there's a stable pattern to how ties are broken
2576 * which the user can learn and use to navigate faster. */
2577 if (best_sqdist == -1 || sqdist < best_sqdist) {
2578 best_x = x;
2579 best_y = y;
2580 best_sqdist = sqdist;
2581 }
2582 }
2583 if (best_x != -1 && best_y != -1) {
2584 ui->cur_x = best_x;
2585 ui->cur_y = best_y;
2586 return MOVE_UI_UPDATE;
2587 } else
2588 return MOVE_NO_EFFECT;
2589 } else if (button == 'g' || button == 'G') {
2590 ui->show_hints = !ui->show_hints;
2591 return MOVE_UI_UPDATE;
2592 }
2593
2594 return MOVE_UNUSED;
2595}
2596
2597static game_state *execute_move(const game_state *state, const char *move)
2598{
2599 game_state *ret = dup_game(state);
2600 int x1, y1, x2, y2, nl, n;
2601 struct island *is1, *is2;
2602 char c;
2603
2604 debug(("execute_move: %s\n", move));
2605
2606 if (!*move) goto badmove;
2607 while (*move) {
2608 c = *move++;
2609 if (c == 'S') {
2610 ret->solved = true;
2611 n = 0;
2612 } else if (c == 'L') {
2613 if (sscanf(move, "%d,%d,%d,%d,%d%n",
2614 &x1, &y1, &x2, &y2, &nl, &n) != 5)
2615 goto badmove;
2616 if (!INGRID(ret, x1, y1) || !INGRID(ret, x2, y2))
2617 goto badmove;
2618 /* Precisely one co-ordinate must differ between islands. */
2619 if ((x1 != x2) + (y1 != y2) != 1) goto badmove;
2620 is1 = INDEX(ret, gridi, x1, y1);
2621 is2 = INDEX(ret, gridi, x2, y2);
2622 if (!is1 || !is2) goto badmove;
2623 if (nl < 0 || nl > state->maxb) goto badmove;
2624 island_join(is1, is2, nl, false);
2625 } else if (c == 'N') {
2626 if (sscanf(move, "%d,%d,%d,%d%n",
2627 &x1, &y1, &x2, &y2, &n) != 4)
2628 goto badmove;
2629 if (!INGRID(ret, x1, y1) || !INGRID(ret, x2, y2))
2630 goto badmove;
2631 if ((x1 != x2) + (y1 != y2) != 1) goto badmove;
2632 is1 = INDEX(ret, gridi, x1, y1);
2633 is2 = INDEX(ret, gridi, x2, y2);
2634 if (!is1 || !is2) goto badmove;
2635 island_join(is1, is2, -1, false);
2636 } else if (c == 'M') {
2637 if (sscanf(move, "%d,%d%n",
2638 &x1, &y1, &n) != 2)
2639 goto badmove;
2640 if (!INGRID(ret, x1, y1))
2641 goto badmove;
2642 is1 = INDEX(ret, gridi, x1, y1);
2643 if (!is1) goto badmove;
2644 island_togglemark(is1);
2645 } else
2646 goto badmove;
2647
2648 move += n;
2649 if (*move == ';')
2650 move++;
2651 else if (*move) goto badmove;
2652 }
2653
2654 map_update_possibles(ret);
2655 if (map_check(ret)) {
2656 debug(("Game completed.\n"));
2657 ret->completed = true;
2658 }
2659 return ret;
2660
2661badmove:
2662 debug(("%s: unrecognised move.\n", move));
2663 free_game(ret);
2664 return NULL;
2665}
2666
2667static char *solve_game(const game_state *state, const game_state *currstate,
2668 const char *aux, const char **error)
2669{
2670 char *ret;
2671 game_state *solved;
2672
2673 if (aux) {
2674 debug(("solve_game: aux = %s\n", aux));
2675 solved = execute_move(state, aux);
2676 if (!solved) {
2677 *error = "Generated aux string is not a valid move (!).";
2678 return NULL;
2679 }
2680 } else {
2681 solved = dup_game(state);
2682 /* solve with max strength... */
2683 if (solve_from_scratch(solved, 10) == 0) {
2684 free_game(solved);
2685 *error = "Game does not have a (non-recursive) solution.";
2686 return NULL;
2687 }
2688 }
2689 ret = game_state_diff(currstate, solved);
2690 free_game(solved);
2691 debug(("solve_game: ret = %s\n", ret));
2692 return ret;
2693}
2694
2695/* ----------------------------------------------------------------------
2696 * Drawing routines.
2697 */
2698
2699static void game_compute_size(const game_params *params, int tilesize,
2700 const game_ui *ui, int *x, int *y)
2701{
2702 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
2703 struct { int tilesize; } ads, *ds = &ads;
2704 ads.tilesize = tilesize;
2705
2706 *x = TILE_SIZE * params->w + 2 * BORDER;
2707 *y = TILE_SIZE * params->h + 2 * BORDER;
2708}
2709
2710static void game_set_size(drawing *dr, game_drawstate *ds,
2711 const game_params *params, int tilesize)
2712{
2713 ds->tilesize = tilesize;
2714}
2715
2716static float *game_colours(frontend *fe, int *ncolours)
2717{
2718 float *ret = snewn(3 * NCOLOURS, float);
2719 int i;
2720
2721 game_mkhighlight(fe, ret, COL_BACKGROUND, COL_HIGHLIGHT, COL_LOWLIGHT);
2722
2723 for (i = 0; i < 3; i++) {
2724 ret[COL_FOREGROUND * 3 + i] = 0.0F;
2725 ret[COL_HINT * 3 + i] = ret[COL_LOWLIGHT * 3 + i];
2726 ret[COL_GRID * 3 + i] =
2727 (ret[COL_HINT * 3 + i] + ret[COL_BACKGROUND * 3 + i]) * 0.5F;
2728 ret[COL_MARK * 3 + i] = ret[COL_HIGHLIGHT * 3 + i];
2729 }
2730 ret[COL_WARNING * 3 + 0] = 1.0F;
2731 ret[COL_WARNING * 3 + 1] = 0.25F;
2732 ret[COL_WARNING * 3 + 2] = 0.25F;
2733
2734 ret[COL_SELECTED * 3 + 0] = 0.25F;
2735 ret[COL_SELECTED * 3 + 1] = 1.00F;
2736 ret[COL_SELECTED * 3 + 2] = 0.25F;
2737
2738 ret[COL_CURSOR * 3 + 0] = min(ret[COL_BACKGROUND * 3 + 0] * 1.4F, 1.0F);
2739 ret[COL_CURSOR * 3 + 1] = ret[COL_BACKGROUND * 3 + 1] * 0.8F;
2740 ret[COL_CURSOR * 3 + 2] = ret[COL_BACKGROUND * 3 + 2] * 0.8F;
2741
2742 *ncolours = NCOLOURS;
2743 return ret;
2744}
2745
2746static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state)
2747{
2748 struct game_drawstate *ds = snew(struct game_drawstate);
2749 int wh = state->w*state->h;
2750 int i;
2751
2752 ds->tilesize = 0;
2753 ds->w = state->w;
2754 ds->h = state->h;
2755 ds->started = false;
2756 ds->dragging = false;
2757 ds->grid = snewn(wh, unsigned long);
2758 for (i = 0; i < wh; i++)
2759 ds->grid[i] = ~0UL;
2760 ds->newgrid = snewn(wh, unsigned long);
2761 ds->lv = snewn(wh, int);
2762 ds->lh = snewn(wh, int);
2763 memset(ds->lv, 0, wh*sizeof(int));
2764 memset(ds->lh, 0, wh*sizeof(int));
2765
2766 return ds;
2767}
2768
2769static void game_free_drawstate(drawing *dr, game_drawstate *ds)
2770{
2771 sfree(ds->lv);
2772 sfree(ds->lh);
2773 sfree(ds->newgrid);
2774 sfree(ds->grid);
2775 sfree(ds);
2776}
2777
2778#define LINE_WIDTH (TILE_SIZE/8)
2779#define TS8(x) (((x)*TILE_SIZE)/8)
2780
2781#define OFFSET(thing) ((TILE_SIZE/2) - ((thing)/2))
2782
2783static bool between_island(const game_state *state, int sx, int sy,
2784 int dx, int dy)
2785{
2786 int x = sx - dx, y = sy - dy;
2787
2788 while (INGRID(state, x, y)) {
2789 if (GRID(state, x, y) & G_ISLAND) goto found;
2790 x -= dx; y -= dy;
2791 }
2792 return false;
2793found:
2794 x = sx + dx, y = sy + dy;
2795 while (INGRID(state, x, y)) {
2796 if (GRID(state, x, y) & G_ISLAND) return true;
2797 x += dx; y += dy;
2798 }
2799 return false;
2800}
2801
2802static void lines_lvlh(const game_state *state, const game_ui *ui,
2803 int x, int y, grid_type v, int *lv_r, int *lh_r)
2804{
2805 int lh = 0, lv = 0;
2806
2807 if (v & G_LINEV) lv = INDEX(state,lines,x,y);
2808 if (v & G_LINEH) lh = INDEX(state,lines,x,y);
2809
2810 if (ui->show_hints) {
2811 if (between_island(state, x, y, 0, 1) && !lv) lv = 1;
2812 if (between_island(state, x, y, 1, 0) && !lh) lh = 1;
2813 }
2814 /*debug(("lvlh: (%d,%d) v 0x%x lv %d lh %d.\n", x, y, v, lv, lh));*/
2815 *lv_r = lv; *lh_r = lh;
2816}
2817
2818static void draw_cross(drawing *dr, game_drawstate *ds,
2819 int ox, int oy, int col)
2820{
2821 int off = TS8(2);
2822 draw_line(dr, ox, oy, ox+off, oy+off, col);
2823 draw_line(dr, ox+off, oy, ox, oy+off, col);
2824}
2825
2826static void draw_general_line(drawing *dr, game_drawstate *ds,
2827 int ox, int oy, int fx, int fy, int ax, int ay,
2828 int len, unsigned long ldata, int which)
2829{
2830 /*
2831 * Draw one direction of lines in a square. To permit the same
2832 * code to handle horizontal and vertical lines, fx,fy are the
2833 * 'forward' direction (along the lines) and ax,ay are the
2834 * 'across' direction.
2835 *
2836 * We draw the white background for a locked bridge if (which &
2837 * 1), and draw the bridges themselves if (which & 2). This
2838 * permits us to get two overlapping locked bridges right without
2839 * one of them erasing part of the other.
2840 */
2841 int fg;
2842
2843 fg = ((ldata & DL_COUNTMASK) == DL_COUNT_HINT ? COL_HINT :
2844 (ldata & DL_COLMASK) == DL_COL_SELECTED ? COL_SELECTED :
2845 (ldata & DL_COLMASK) == DL_COL_FLASH ? COL_HIGHLIGHT :
2846 (ldata & DL_COLMASK) == DL_COL_WARNING ? COL_WARNING :
2847 COL_FOREGROUND);
2848
2849 if ((ldata & DL_COUNTMASK) == DL_COUNT_CROSS) {
2850 draw_cross(dr, ds,
2851 ox + TS8(1)*fx + TS8(3)*ax,
2852 oy + TS8(1)*fy + TS8(3)*ay, fg);
2853 draw_cross(dr, ds,
2854 ox + TS8(5)*fx + TS8(3)*ax,
2855 oy + TS8(5)*fy + TS8(3)*ay, fg);
2856 } else if ((ldata & DL_COUNTMASK) != 0) {
2857 int lh, lw, gw, bw, i, loff;
2858
2859 lh = (ldata & DL_COUNTMASK);
2860 if (lh == DL_COUNT_HINT)
2861 lh = 1;
2862
2863 lw = gw = LINE_WIDTH;
2864 while ((bw = lw * lh + gw * (lh+1)) > TILE_SIZE)
2865 gw--;
2866
2867 loff = OFFSET(bw);
2868
2869 if (which & 1) {
2870 if ((ldata & DL_LOCK) && fg != COL_HINT)
2871 draw_rect(dr, ox + loff*ax, oy + loff*ay,
2872 len*fx+bw*ax, len*fy+bw*ay, COL_MARK);
2873 }
2874 if (which & 2) {
2875 for (i = 0; i < lh; i++, loff += lw + gw)
2876 draw_rect(dr, ox + (loff+gw)*ax, oy + (loff+gw)*ay,
2877 len*fx+lw*ax, len*fy+lw*ay, fg);
2878 }
2879 }
2880}
2881
2882static void draw_hline(drawing *dr, game_drawstate *ds,
2883 int ox, int oy, int w, unsigned long vdata, int which)
2884{
2885 draw_general_line(dr, ds, ox, oy, 1, 0, 0, 1, w, vdata, which);
2886}
2887
2888static void draw_vline(drawing *dr, game_drawstate *ds,
2889 int ox, int oy, int h, unsigned long vdata, int which)
2890{
2891 draw_general_line(dr, ds, ox, oy, 0, 1, 1, 0, h, vdata, which);
2892}
2893
2894#define ISLAND_RADIUS ((TILE_SIZE*12)/20)
2895#define ISLAND_NUMSIZE(clue) \
2896 (((clue) < 10) ? (TILE_SIZE*7)/10 : (TILE_SIZE*5)/10)
2897
2898static void draw_island(drawing *dr, game_drawstate *ds,
2899 int ox, int oy, int clue, unsigned long idata)
2900{
2901 int half, orad, irad, fg, bg;
2902
2903 if ((idata & DI_BGMASK) == DI_BG_NO_ISLAND)
2904 return;
2905
2906 half = TILE_SIZE/2;
2907 orad = ISLAND_RADIUS;
2908 irad = orad - LINE_WIDTH;
2909 fg = ((idata & DI_COLMASK) == DI_COL_SELECTED ? COL_SELECTED :
2910 (idata & DI_COLMASK) == DI_COL_WARNING ? COL_WARNING :
2911 (idata & DI_COLMASK) == DI_COL_FLASH ? COL_HIGHLIGHT :
2912 COL_FOREGROUND);
2913 bg = ((idata & DI_BGMASK) == DI_BG_CURSOR ? COL_CURSOR :
2914 (idata & DI_BGMASK) == DI_BG_MARK ? COL_MARK :
2915 COL_BACKGROUND);
2916
2917 /* draw a thick circle */
2918 draw_circle(dr, ox+half, oy+half, orad, fg, fg);
2919 draw_circle(dr, ox+half, oy+half, irad, bg, bg);
2920
2921 if (clue > 0) {
2922 char str[32];
2923 int textcolour = (fg == COL_SELECTED ? COL_FOREGROUND : fg);
2924 sprintf(str, "%d", clue);
2925 draw_text(dr, ox+half, oy+half, FONT_VARIABLE, ISLAND_NUMSIZE(clue),
2926 ALIGN_VCENTRE | ALIGN_HCENTRE, textcolour, str);
2927 }
2928}
2929
2930static void draw_island_tile(drawing *dr, game_drawstate *ds,
2931 int x, int y, int clue, unsigned long data)
2932{
2933 int ox = COORD(x), oy = COORD(y);
2934 int which;
2935
2936 clip(dr, ox, oy, TILE_SIZE, TILE_SIZE);
2937 draw_rect(dr, ox, oy, TILE_SIZE, TILE_SIZE, COL_BACKGROUND);
2938
2939 /*
2940 * Because of the possibility of incoming bridges just about
2941 * meeting at one corner, we must split the line-drawing into
2942 * background and foreground segments.
2943 */
2944 for (which = 1; which <= 2; which <<= 1) {
2945 draw_hline(dr, ds, ox, oy, TILE_SIZE/2,
2946 (data >> D_I_LINE_SHIFT_L) & DL_MASK, which);
2947 draw_hline(dr, ds, ox + TILE_SIZE - TILE_SIZE/2, oy, TILE_SIZE/2,
2948 (data >> D_I_LINE_SHIFT_R) & DL_MASK, which);
2949 draw_vline(dr, ds, ox, oy, TILE_SIZE/2,
2950 (data >> D_I_LINE_SHIFT_U) & DL_MASK, which);
2951 draw_vline(dr, ds, ox, oy + TILE_SIZE - TILE_SIZE/2, TILE_SIZE/2,
2952 (data >> D_I_LINE_SHIFT_D) & DL_MASK, which);
2953 }
2954 draw_island(dr, ds, ox, oy, clue, (data >> D_I_ISLAND_SHIFT) & DI_MASK);
2955
2956 unclip(dr);
2957 draw_update(dr, ox, oy, TILE_SIZE, TILE_SIZE);
2958}
2959
2960static void draw_line_tile(drawing *dr, game_drawstate *ds,
2961 int x, int y, unsigned long data)
2962{
2963 int ox = COORD(x), oy = COORD(y);
2964 unsigned long hdata, vdata;
2965
2966 clip(dr, ox, oy, TILE_SIZE, TILE_SIZE);
2967 draw_rect(dr, ox, oy, TILE_SIZE, TILE_SIZE, COL_BACKGROUND);
2968
2969 /*
2970 * We have to think about which of the horizontal and vertical
2971 * line to draw first, if both exist.
2972 *
2973 * The rule is that hint lines are drawn at the bottom, then
2974 * NOLINE crosses, then actual bridges. The enumeration in the
2975 * DL_COUNTMASK field is set up so that this drops out of a
2976 * straight comparison between the two.
2977 *
2978 * Since lines crossing in this type of square cannot both be
2979 * actual bridges, there's no need to pass a nontrivial 'which'
2980 * parameter to draw_[hv]line.
2981 */
2982 hdata = (data >> D_L_LINE_SHIFT_H) & DL_MASK;
2983 vdata = (data >> D_L_LINE_SHIFT_V) & DL_MASK;
2984 if ((hdata & DL_COUNTMASK) > (vdata & DL_COUNTMASK)) {
2985 draw_hline(dr, ds, ox, oy, TILE_SIZE, hdata, 3);
2986 draw_vline(dr, ds, ox, oy, TILE_SIZE, vdata, 3);
2987 } else {
2988 draw_vline(dr, ds, ox, oy, TILE_SIZE, vdata, 3);
2989 draw_hline(dr, ds, ox, oy, TILE_SIZE, hdata, 3);
2990 }
2991
2992 /*
2993 * The islands drawn at the edges of a line tile don't need clue
2994 * numbers.
2995 */
2996 draw_island(dr, ds, ox - TILE_SIZE, oy, -1,
2997 (data >> D_L_ISLAND_SHIFT_L) & DI_MASK);
2998 draw_island(dr, ds, ox + TILE_SIZE, oy, -1,
2999 (data >> D_L_ISLAND_SHIFT_R) & DI_MASK);
3000 draw_island(dr, ds, ox, oy - TILE_SIZE, -1,
3001 (data >> D_L_ISLAND_SHIFT_U) & DI_MASK);
3002 draw_island(dr, ds, ox, oy + TILE_SIZE, -1,
3003 (data >> D_L_ISLAND_SHIFT_D) & DI_MASK);
3004
3005 unclip(dr);
3006 draw_update(dr, ox, oy, TILE_SIZE, TILE_SIZE);
3007}
3008
3009static void draw_edge_tile(drawing *dr, game_drawstate *ds,
3010 int x, int y, int dx, int dy, unsigned long data)
3011{
3012 int ox = COORD(x), oy = COORD(y);
3013 int cx = ox, cy = oy, cw = TILE_SIZE, ch = TILE_SIZE;
3014
3015 if (dy) {
3016 if (dy > 0)
3017 cy += TILE_SIZE/2;
3018 ch -= TILE_SIZE/2;
3019 } else {
3020 if (dx > 0)
3021 cx += TILE_SIZE/2;
3022 cw -= TILE_SIZE/2;
3023 }
3024 clip(dr, cx, cy, cw, ch);
3025 draw_rect(dr, cx, cy, cw, ch, COL_BACKGROUND);
3026
3027 draw_island(dr, ds, ox + TILE_SIZE*dx, oy + TILE_SIZE*dy, -1,
3028 (data >> D_I_ISLAND_SHIFT) & DI_MASK);
3029
3030 unclip(dr);
3031 draw_update(dr, cx, cy, cw, ch);
3032}
3033
3034static void game_redraw(drawing *dr, game_drawstate *ds,
3035 const game_state *oldstate, const game_state *state,
3036 int dir, const game_ui *ui,
3037 float animtime, float flashtime)
3038{
3039 int x, y, lv, lh;
3040 grid_type v;
3041 bool flash = false;
3042 struct island *is, *is_drag_src = NULL, *is_drag_dst = NULL;
3043
3044 if (flashtime) {
3045 int f = (int)(flashtime * 5 / FLASH_TIME);
3046 if (f == 1 || f == 3) flash = true;
3047 }
3048
3049 /* Clear screen, if required. */
3050 if (!ds->started) {
3051#ifdef DRAW_GRID
3052 draw_rect_outline(dr,
3053 COORD(0)-1, COORD(0)-1,
3054 TILE_SIZE * ds->w + 2, TILE_SIZE * ds->h + 2,
3055 COL_GRID);
3056#endif
3057 draw_update(dr, 0, 0,
3058 TILE_SIZE * ds->w + 2 * BORDER,
3059 TILE_SIZE * ds->h + 2 * BORDER);
3060 ds->started = true;
3061 }
3062
3063 if (ui->dragx_src != -1 && ui->dragy_src != -1) {
3064 ds->dragging = true;
3065 is_drag_src = INDEX(state, gridi, ui->dragx_src, ui->dragy_src);
3066 assert(is_drag_src);
3067 if (ui->dragx_dst != -1 && ui->dragy_dst != -1) {
3068 is_drag_dst = INDEX(state, gridi, ui->dragx_dst, ui->dragy_dst);
3069 assert(is_drag_dst);
3070 }
3071 } else
3072 ds->dragging = false;
3073
3074 /*
3075 * Set up ds->newgrid with the current grid contents.
3076 */
3077 for (x = 0; x < ds->w; x++)
3078 for (y = 0; y < ds->h; y++)
3079 INDEX(ds,newgrid,x,y) = 0;
3080
3081 for (x = 0; x < ds->w; x++) {
3082 for (y = 0; y < ds->h; y++) {
3083 v = GRID(state, x, y);
3084
3085 if (v & G_ISLAND) {
3086 /*
3087 * An island square. Compute the drawing data for the
3088 * island, and put it in this square and surrounding
3089 * squares.
3090 */
3091 unsigned long idata = 0;
3092
3093 is = INDEX(state, gridi, x, y);
3094
3095 if (flash)
3096 idata |= DI_COL_FLASH;
3097 if (is_drag_src && (is == is_drag_src ||
3098 (is_drag_dst && is == is_drag_dst)))
3099 idata |= DI_COL_SELECTED;
3100 else if (island_impossible(is, v & G_MARK) || (v & G_WARN))
3101 idata |= DI_COL_WARNING;
3102 else
3103 idata |= DI_COL_NORMAL;
3104
3105 if (ui->cur_visible &&
3106 ui->cur_x == is->x && ui->cur_y == is->y)
3107 idata |= DI_BG_CURSOR;
3108 else if (v & G_MARK)
3109 idata |= DI_BG_MARK;
3110 else
3111 idata |= DI_BG_NORMAL;
3112
3113 INDEX(ds,newgrid,x,y) |= idata << D_I_ISLAND_SHIFT;
3114 if (x > 0 && !(GRID(state,x-1,y) & G_ISLAND))
3115 INDEX(ds,newgrid,x-1,y) |= idata << D_L_ISLAND_SHIFT_R;
3116 if (x+1 < state->w && !(GRID(state,x+1,y) & G_ISLAND))
3117 INDEX(ds,newgrid,x+1,y) |= idata << D_L_ISLAND_SHIFT_L;
3118 if (y > 0 && !(GRID(state,x,y-1) & G_ISLAND))
3119 INDEX(ds,newgrid,x,y-1) |= idata << D_L_ISLAND_SHIFT_D;
3120 if (y+1 < state->h && !(GRID(state,x,y+1) & G_ISLAND))
3121 INDEX(ds,newgrid,x,y+1) |= idata << D_L_ISLAND_SHIFT_U;
3122 } else {
3123 unsigned long hdata, vdata;
3124 bool selh = false, selv = false;
3125
3126 /*
3127 * A line (non-island) square. Compute the drawing
3128 * data for any horizontal and vertical lines in the
3129 * square, and put them in this square's entry and
3130 * optionally those for neighbouring islands too.
3131 */
3132
3133 if (is_drag_dst &&
3134 WITHIN(x,is_drag_src->x, is_drag_dst->x) &&
3135 WITHIN(y,is_drag_src->y, is_drag_dst->y)) {
3136 if (is_drag_src->x != is_drag_dst->x)
3137 selh = true;
3138 else
3139 selv = true;
3140 }
3141 lines_lvlh(state, ui, x, y, v, &lv, &lh);
3142
3143 hdata = (v & G_NOLINEH ? DL_COUNT_CROSS :
3144 v & G_LINEH ? lh :
3145 (ui->show_hints &&
3146 between_island(state,x,y,1,0)) ? DL_COUNT_HINT : 0);
3147 vdata = (v & G_NOLINEV ? DL_COUNT_CROSS :
3148 v & G_LINEV ? lv :
3149 (ui->show_hints &&
3150 between_island(state,x,y,0,1)) ? DL_COUNT_HINT : 0);
3151
3152 hdata |= (flash ? DL_COL_FLASH :
3153 v & G_WARN ? DL_COL_WARNING :
3154 selh ? DL_COL_SELECTED :
3155 DL_COL_NORMAL);
3156 vdata |= (flash ? DL_COL_FLASH :
3157 v & G_WARN ? DL_COL_WARNING :
3158 selv ? DL_COL_SELECTED :
3159 DL_COL_NORMAL);
3160
3161 if (v & G_MARKH)
3162 hdata |= DL_LOCK;
3163 if (v & G_MARKV)
3164 vdata |= DL_LOCK;
3165
3166 INDEX(ds,newgrid,x,y) |= hdata << D_L_LINE_SHIFT_H;
3167 INDEX(ds,newgrid,x,y) |= vdata << D_L_LINE_SHIFT_V;
3168 if (x > 0 && (GRID(state,x-1,y) & G_ISLAND))
3169 INDEX(ds,newgrid,x-1,y) |= hdata << D_I_LINE_SHIFT_R;
3170 if (x+1 < state->w && (GRID(state,x+1,y) & G_ISLAND))
3171 INDEX(ds,newgrid,x+1,y) |= hdata << D_I_LINE_SHIFT_L;
3172 if (y > 0 && (GRID(state,x,y-1) & G_ISLAND))
3173 INDEX(ds,newgrid,x,y-1) |= vdata << D_I_LINE_SHIFT_D;
3174 if (y+1 < state->h && (GRID(state,x,y+1) & G_ISLAND))
3175 INDEX(ds,newgrid,x,y+1) |= vdata << D_I_LINE_SHIFT_U;
3176 }
3177 }
3178 }
3179
3180 /*
3181 * Now go through and draw any changed grid square.
3182 */
3183 for (x = 0; x < ds->w; x++) {
3184 for (y = 0; y < ds->h; y++) {
3185 unsigned long newval = INDEX(ds,newgrid,x,y);
3186 if (INDEX(ds,grid,x,y) != newval) {
3187 v = GRID(state, x, y);
3188 if (v & G_ISLAND) {
3189 is = INDEX(state, gridi, x, y);
3190 draw_island_tile(dr, ds, x, y, is->count, newval);
3191
3192 /*
3193 * If this tile is right at the edge of the grid,
3194 * we must also draw the part of the island that
3195 * goes completely out of bounds. We don't bother
3196 * keeping separate entries in ds->newgrid for
3197 * these tiles; it's easier just to redraw them
3198 * iff we redraw their parent island tile.
3199 */
3200 if (x == 0)
3201 draw_edge_tile(dr, ds, x-1, y, +1, 0, newval);
3202 if (y == 0)
3203 draw_edge_tile(dr, ds, x, y-1, 0, +1, newval);
3204 if (x == state->w-1)
3205 draw_edge_tile(dr, ds, x+1, y, -1, 0, newval);
3206 if (y == state->h-1)
3207 draw_edge_tile(dr, ds, x, y+1, 0, -1, newval);
3208 } else {
3209 draw_line_tile(dr, ds, x, y, newval);
3210 }
3211 INDEX(ds,grid,x,y) = newval;
3212 }
3213 }
3214 }
3215}
3216
3217static float game_anim_length(const game_state *oldstate,
3218 const game_state *newstate, int dir, game_ui *ui)
3219{
3220 return 0.0F;
3221}
3222
3223static float game_flash_length(const game_state *oldstate,
3224 const game_state *newstate, int dir, game_ui *ui)
3225{
3226 if (!oldstate->completed && newstate->completed &&
3227 !oldstate->solved && !newstate->solved)
3228 return FLASH_TIME;
3229
3230 return 0.0F;
3231}
3232
3233static int game_status(const game_state *state)
3234{
3235 return state->completed ? +1 : 0;
3236}
3237
3238static void game_print_size(const game_params *params, const game_ui *ui,
3239 float *x, float *y)
3240{
3241 int pw, ph;
3242
3243 /* 10mm squares by default. */
3244 game_compute_size(params, 1000, ui, &pw, &ph);
3245 *x = pw / 100.0F;
3246 *y = ph / 100.0F;
3247}
3248
3249static void game_print(drawing *dr, const game_state *state, const game_ui *ui,
3250 int ts)
3251{
3252 int ink = print_mono_colour(dr, 0);
3253 int paper = print_mono_colour(dr, 1);
3254 int x, y, cx, cy, i, nl;
3255 int loff;
3256 grid_type grid;
3257
3258 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
3259 game_drawstate ads, *ds = &ads;
3260 ads.tilesize = ts;
3261
3262 /* I don't think this wants a border. */
3263
3264 /* Bridges */
3265 loff = ts / (8 * sqrt((state->params.maxb - 1)));
3266 print_line_width(dr, ts / 12);
3267 for (x = 0; x < state->w; x++) {
3268 for (y = 0; y < state->h; y++) {
3269 cx = COORD(x); cy = COORD(y);
3270 grid = GRID(state,x,y);
3271 nl = INDEX(state,lines,x,y);
3272
3273 if (grid & G_ISLAND) continue;
3274 if (grid & G_LINEV) {
3275 for (i = 0; i < nl; i++)
3276 draw_line(dr, cx+ts/2+(2*i-nl+1)*loff, cy,
3277 cx+ts/2+(2*i-nl+1)*loff, cy+ts, ink);
3278 }
3279 if (grid & G_LINEH) {
3280 for (i = 0; i < nl; i++)
3281 draw_line(dr, cx, cy+ts/2+(2*i-nl+1)*loff,
3282 cx+ts, cy+ts/2+(2*i-nl+1)*loff, ink);
3283 }
3284 }
3285 }
3286
3287 /* Islands */
3288 for (i = 0; i < state->n_islands; i++) {
3289 char str[32];
3290 struct island *is = &state->islands[i];
3291 grid = GRID(state, is->x, is->y);
3292 cx = COORD(is->x) + ts/2;
3293 cy = COORD(is->y) + ts/2;
3294
3295 draw_circle(dr, cx, cy, ISLAND_RADIUS, paper, ink);
3296
3297 sprintf(str, "%d", is->count);
3298 draw_text(dr, cx, cy, FONT_VARIABLE, ISLAND_NUMSIZE(is->count),
3299 ALIGN_VCENTRE | ALIGN_HCENTRE, ink, str);
3300 }
3301}
3302
3303#ifdef COMBINED
3304#define thegame bridges
3305#endif
3306
3307const struct game thegame = {
3308 "Bridges", "games.bridges", "bridges",
3309 default_params,
3310 game_fetch_preset, NULL,
3311 decode_params,
3312 encode_params,
3313 free_params,
3314 dup_params,
3315 true, game_configure, custom_params,
3316 validate_params,
3317 new_game_desc,
3318 validate_desc,
3319 new_game,
3320 dup_game,
3321 free_game,
3322 true, solve_game,
3323 true, game_can_format_as_text_now, game_text_format,
3324 get_prefs, set_prefs,
3325 new_ui,
3326 free_ui,
3327 NULL, /* encode_ui */
3328 NULL, /* decode_ui */
3329 NULL, /* game_request_keys */
3330 game_changed_state,
3331 current_key_label,
3332 interpret_move,
3333 execute_move,
3334 PREFERRED_TILE_SIZE, game_compute_size, game_set_size,
3335 game_colours,
3336 game_new_drawstate,
3337 game_free_drawstate,
3338 game_redraw,
3339 game_anim_length,
3340 game_flash_length,
3341 game_get_cursor_location,
3342 game_status,
3343 true, false, game_print_size, game_print,
3344 false, /* wants_statusbar */
3345 false, NULL, /* timing_state */
3346 REQUIRE_RBUTTON, /* flags */
3347};
3348
3349/* vim: set shiftwidth=4 tabstop=8: */