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