diff options
author | Franklin Wei <frankhwei536@gmail.com> | 2016-11-20 15:16:41 -0500 |
---|---|---|
committer | Franklin Wei <me@fwei.tk> | 2016-12-18 18:13:22 +0100 |
commit | 1a6a8b52f7aa4e2da6f4c34a0c743c760b8cfd99 (patch) | |
tree | 8e7f2d6b0cbdb5d15c13457b2c3e1de69f598440 /apps/plugins/puzzles/rect.c | |
parent | 3ee79724f6fb033d50e26ef37b33d3f8cedf0c5b (diff) | |
download | rockbox-1a6a8b52f7aa4e2da6f4c34a0c743c760b8cfd99.tar.gz rockbox-1a6a8b52f7aa4e2da6f4c34a0c743c760b8cfd99.zip |
Port of Simon Tatham's Puzzle Collection
Original revision: 5123b1bf68777ffa86e651f178046b26a87cf2d9
MIT Licensed. Some games still crash and others are unplayable due to
issues with controls. Still need a "real" polygon filling algorithm.
Currently builds one plugin per puzzle (about 40 in total, around 100K
each on ARM), but can easily be made to build a single monolithic
overlay (800K or so on ARM).
The following games are at least partially broken for various reasons,
and have been disabled on this commit:
Cube: failed assertion with "Icosahedron" setting
Keen: input issues
Mines: weird stuff happens on target
Palisade: input issues
Solo: input issues, occasional crash on target
Towers: input issues
Undead: input issues
Unequal: input and drawing issues (concave polys)
Untangle: input issues
Features left to do:
- In-game help system
- Figure out the weird bugs
Change-Id: I7c69b6860ab115f973c8d76799502e9bb3d52368
Diffstat (limited to 'apps/plugins/puzzles/rect.c')
-rw-r--r-- | apps/plugins/puzzles/rect.c | 3000 |
1 files changed, 3000 insertions, 0 deletions
diff --git a/apps/plugins/puzzles/rect.c b/apps/plugins/puzzles/rect.c new file mode 100644 index 0000000000..ca3cb984ea --- /dev/null +++ b/apps/plugins/puzzles/rect.c | |||
@@ -0,0 +1,3000 @@ | |||
1 | /* | ||
2 | * rect.c: Puzzle from nikoli.co.jp. You have a square grid with | ||
3 | * numbers in some squares; you must divide the square grid up into | ||
4 | * variously sized rectangles, such that every rectangle contains | ||
5 | * exactly one numbered square and the area of each rectangle is | ||
6 | * equal to the number contained in it. | ||
7 | */ | ||
8 | |||
9 | /* | ||
10 | * TODO: | ||
11 | * | ||
12 | * - Improve singleton removal. | ||
13 | * + It would be nice to limit the size of the generated | ||
14 | * rectangles in accordance with existing constraints such as | ||
15 | * the maximum rectangle size and the one about not | ||
16 | * generating a rectangle the full width or height of the | ||
17 | * grid. | ||
18 | * + This could be achieved by making a less random choice | ||
19 | * about which of the available options to use. | ||
20 | * + Alternatively, we could create our rectangle and then | ||
21 | * split it up. | ||
22 | */ | ||
23 | |||
24 | #include <stdio.h> | ||
25 | #include <stdlib.h> | ||
26 | #include <string.h> | ||
27 | #include "rbassert.h" | ||
28 | #include <ctype.h> | ||
29 | #include <math.h> | ||
30 | |||
31 | #include "puzzles.h" | ||
32 | |||
33 | enum { | ||
34 | COL_BACKGROUND, | ||
35 | COL_CORRECT, | ||
36 | COL_LINE, | ||
37 | COL_TEXT, | ||
38 | COL_GRID, | ||
39 | COL_DRAG, COL_DRAGERASE, | ||
40 | COL_CURSOR, | ||
41 | NCOLOURS | ||
42 | }; | ||
43 | |||
44 | struct game_params { | ||
45 | int w, h; | ||
46 | float expandfactor; | ||
47 | int unique; | ||
48 | }; | ||
49 | |||
50 | #define INDEX(state, x, y) (((y) * (state)->w) + (x)) | ||
51 | #define index(state, a, x, y) ((a) [ INDEX(state,x,y) ]) | ||
52 | #define grid(state,x,y) index(state, (state)->grid, x, y) | ||
53 | #define vedge(state,x,y) index(state, (state)->vedge, x, y) | ||
54 | #define hedge(state,x,y) index(state, (state)->hedge, x, y) | ||
55 | |||
56 | #define CRANGE(state,x,y,dx,dy) ( (x) >= dx && (x) < (state)->w && \ | ||
57 | (y) >= dy && (y) < (state)->h ) | ||
58 | #define RANGE(state,x,y) CRANGE(state,x,y,0,0) | ||
59 | #define HRANGE(state,x,y) CRANGE(state,x,y,0,1) | ||
60 | #define VRANGE(state,x,y) CRANGE(state,x,y,1,0) | ||
61 | |||
62 | #define PREFERRED_TILE_SIZE 24 | ||
63 | #define TILE_SIZE (ds->tilesize) | ||
64 | #ifdef SMALL_SCREEN | ||
65 | #define BORDER (2) | ||
66 | #else | ||
67 | #define BORDER (TILE_SIZE * 3 / 4) | ||
68 | #endif | ||
69 | |||
70 | #define CORNER_TOLERANCE 0.15F | ||
71 | #define CENTRE_TOLERANCE 0.15F | ||
72 | |||
73 | #define FLASH_TIME 0.13F | ||
74 | |||
75 | #define COORD(x) ( (x) * TILE_SIZE + BORDER ) | ||
76 | #define FROMCOORD(x) ( ((x) - BORDER) / TILE_SIZE ) | ||
77 | |||
78 | struct game_state { | ||
79 | int w, h; | ||
80 | int *grid; /* contains the numbers */ | ||
81 | unsigned char *vedge; /* (w+1) x h */ | ||
82 | unsigned char *hedge; /* w x (h+1) */ | ||
83 | int completed, cheated; | ||
84 | unsigned char *correct; | ||
85 | }; | ||
86 | |||
87 | static game_params *default_params(void) | ||
88 | { | ||
89 | game_params *ret = snew(game_params); | ||
90 | |||
91 | ret->w = ret->h = 7; | ||
92 | ret->expandfactor = 0.0F; | ||
93 | ret->unique = TRUE; | ||
94 | |||
95 | return ret; | ||
96 | } | ||
97 | |||
98 | static int game_fetch_preset(int i, char **name, game_params **params) | ||
99 | { | ||
100 | game_params *ret; | ||
101 | int w, h; | ||
102 | char buf[80]; | ||
103 | |||
104 | switch (i) { | ||
105 | case 0: w = 7, h = 7; break; | ||
106 | case 1: w = 9, h = 9; break; | ||
107 | case 2: w = 11, h = 11; break; | ||
108 | case 3: w = 13, h = 13; break; | ||
109 | case 4: w = 15, h = 15; break; | ||
110 | #ifndef SMALL_SCREEN | ||
111 | case 5: w = 17, h = 17; break; | ||
112 | case 6: w = 19, h = 19; break; | ||
113 | #endif | ||
114 | default: return FALSE; | ||
115 | } | ||
116 | |||
117 | sprintf(buf, "%dx%d", w, h); | ||
118 | *name = dupstr(buf); | ||
119 | *params = ret = snew(game_params); | ||
120 | ret->w = w; | ||
121 | ret->h = h; | ||
122 | ret->expandfactor = 0.0F; | ||
123 | ret->unique = TRUE; | ||
124 | return TRUE; | ||
125 | } | ||
126 | |||
127 | static void free_params(game_params *params) | ||
128 | { | ||
129 | sfree(params); | ||
130 | } | ||
131 | |||
132 | static game_params *dup_params(const game_params *params) | ||
133 | { | ||
134 | game_params *ret = snew(game_params); | ||
135 | *ret = *params; /* structure copy */ | ||
136 | return ret; | ||
137 | } | ||
138 | |||
139 | static void decode_params(game_params *ret, char const *string) | ||
140 | { | ||
141 | ret->w = ret->h = atoi(string); | ||
142 | while (*string && isdigit((unsigned char)*string)) string++; | ||
143 | if (*string == 'x') { | ||
144 | string++; | ||
145 | ret->h = atoi(string); | ||
146 | while (*string && isdigit((unsigned char)*string)) string++; | ||
147 | } | ||
148 | if (*string == 'e') { | ||
149 | string++; | ||
150 | ret->expandfactor = (float)atof(string); | ||
151 | while (*string && | ||
152 | (*string == '.' || isdigit((unsigned char)*string))) string++; | ||
153 | } | ||
154 | if (*string == 'a') { | ||
155 | string++; | ||
156 | ret->unique = FALSE; | ||
157 | } | ||
158 | } | ||
159 | |||
160 | static char *encode_params(const game_params *params, int full) | ||
161 | { | ||
162 | char data[256]; | ||
163 | |||
164 | sprintf(data, "%dx%d", params->w, params->h); | ||
165 | if (full && params->expandfactor) | ||
166 | sprintf(data + strlen(data), "e%g", params->expandfactor); | ||
167 | if (full && !params->unique) | ||
168 | strcat(data, "a"); | ||
169 | |||
170 | return dupstr(data); | ||
171 | } | ||
172 | |||
173 | static config_item *game_configure(const game_params *params) | ||
174 | { | ||
175 | config_item *ret; | ||
176 | char buf[80]; | ||
177 | |||
178 | ret = snewn(5, config_item); | ||
179 | |||
180 | ret[0].name = "Width"; | ||
181 | ret[0].type = C_STRING; | ||
182 | sprintf(buf, "%d", params->w); | ||
183 | ret[0].sval = dupstr(buf); | ||
184 | ret[0].ival = 0; | ||
185 | |||
186 | ret[1].name = "Height"; | ||
187 | ret[1].type = C_STRING; | ||
188 | sprintf(buf, "%d", params->h); | ||
189 | ret[1].sval = dupstr(buf); | ||
190 | ret[1].ival = 0; | ||
191 | |||
192 | ret[2].name = "Expansion factor"; | ||
193 | ret[2].type = C_STRING; | ||
194 | sprintf(buf, "%g", params->expandfactor); | ||
195 | ret[2].sval = dupstr(buf); | ||
196 | ret[2].ival = 0; | ||
197 | |||
198 | ret[3].name = "Ensure unique solution"; | ||
199 | ret[3].type = C_BOOLEAN; | ||
200 | ret[3].sval = NULL; | ||
201 | ret[3].ival = params->unique; | ||
202 | |||
203 | ret[4].name = NULL; | ||
204 | ret[4].type = C_END; | ||
205 | ret[4].sval = NULL; | ||
206 | ret[4].ival = 0; | ||
207 | |||
208 | return ret; | ||
209 | } | ||
210 | |||
211 | static game_params *custom_params(const config_item *cfg) | ||
212 | { | ||
213 | game_params *ret = snew(game_params); | ||
214 | |||
215 | ret->w = atoi(cfg[0].sval); | ||
216 | ret->h = atoi(cfg[1].sval); | ||
217 | ret->expandfactor = (float)atof(cfg[2].sval); | ||
218 | ret->unique = cfg[3].ival; | ||
219 | |||
220 | return ret; | ||
221 | } | ||
222 | |||
223 | static char *validate_params(const game_params *params, int full) | ||
224 | { | ||
225 | if (params->w <= 0 || params->h <= 0) | ||
226 | return "Width and height must both be greater than zero"; | ||
227 | if (params->w*params->h < 2) | ||
228 | return "Grid area must be greater than one"; | ||
229 | if (params->expandfactor < 0.0F) | ||
230 | return "Expansion factor may not be negative"; | ||
231 | return NULL; | ||
232 | } | ||
233 | |||
234 | struct point { | ||
235 | int x, y; | ||
236 | }; | ||
237 | |||
238 | struct rect { | ||
239 | int x, y; | ||
240 | int w, h; | ||
241 | }; | ||
242 | |||
243 | struct rectlist { | ||
244 | struct rect *rects; | ||
245 | int n; | ||
246 | }; | ||
247 | |||
248 | struct numberdata { | ||
249 | int area; | ||
250 | int npoints; | ||
251 | struct point *points; | ||
252 | }; | ||
253 | |||
254 | /* ---------------------------------------------------------------------- | ||
255 | * Solver for Rectangles games. | ||
256 | * | ||
257 | * This solver is souped up beyond the needs of actually _solving_ | ||
258 | * a puzzle. It is also designed to cope with uncertainty about | ||
259 | * where the numbers have been placed. This is because I run it on | ||
260 | * my generated grids _before_ placing the numbers, and have it | ||
261 | * tell me where I need to place the numbers to ensure a unique | ||
262 | * solution. | ||
263 | */ | ||
264 | |||
265 | static void remove_rect_placement(int w, int h, | ||
266 | struct rectlist *rectpositions, | ||
267 | int *overlaps, | ||
268 | int rectnum, int placement) | ||
269 | { | ||
270 | int x, y, xx, yy; | ||
271 | |||
272 | #ifdef SOLVER_DIAGNOSTICS | ||
273 | printf("ruling out rect %d placement at %d,%d w=%d h=%d\n", rectnum, | ||
274 | rectpositions[rectnum].rects[placement].x, | ||
275 | rectpositions[rectnum].rects[placement].y, | ||
276 | rectpositions[rectnum].rects[placement].w, | ||
277 | rectpositions[rectnum].rects[placement].h); | ||
278 | #endif | ||
279 | |||
280 | /* | ||
281 | * Decrement each entry in the overlaps array to reflect the | ||
282 | * removal of this rectangle placement. | ||
283 | */ | ||
284 | for (yy = 0; yy < rectpositions[rectnum].rects[placement].h; yy++) { | ||
285 | y = yy + rectpositions[rectnum].rects[placement].y; | ||
286 | for (xx = 0; xx < rectpositions[rectnum].rects[placement].w; xx++) { | ||
287 | x = xx + rectpositions[rectnum].rects[placement].x; | ||
288 | |||
289 | assert(overlaps[(rectnum * h + y) * w + x] != 0); | ||
290 | |||
291 | if (overlaps[(rectnum * h + y) * w + x] > 0) | ||
292 | overlaps[(rectnum * h + y) * w + x]--; | ||
293 | } | ||
294 | } | ||
295 | |||
296 | /* | ||
297 | * Remove the placement from the list of positions for that | ||
298 | * rectangle, by interchanging it with the one on the end. | ||
299 | */ | ||
300 | if (placement < rectpositions[rectnum].n - 1) { | ||
301 | struct rect t; | ||
302 | |||
303 | t = rectpositions[rectnum].rects[rectpositions[rectnum].n - 1]; | ||
304 | rectpositions[rectnum].rects[rectpositions[rectnum].n - 1] = | ||
305 | rectpositions[rectnum].rects[placement]; | ||
306 | rectpositions[rectnum].rects[placement] = t; | ||
307 | } | ||
308 | rectpositions[rectnum].n--; | ||
309 | } | ||
310 | |||
311 | static void remove_number_placement(int w, int h, struct numberdata *number, | ||
312 | int index, int *rectbyplace) | ||
313 | { | ||
314 | /* | ||
315 | * Remove the entry from the rectbyplace array. | ||
316 | */ | ||
317 | rectbyplace[number->points[index].y * w + number->points[index].x] = -1; | ||
318 | |||
319 | /* | ||
320 | * Remove the placement from the list of candidates for that | ||
321 | * number, by interchanging it with the one on the end. | ||
322 | */ | ||
323 | if (index < number->npoints - 1) { | ||
324 | struct point t; | ||
325 | |||
326 | t = number->points[number->npoints - 1]; | ||
327 | number->points[number->npoints - 1] = number->points[index]; | ||
328 | number->points[index] = t; | ||
329 | } | ||
330 | number->npoints--; | ||
331 | } | ||
332 | |||
333 | /* | ||
334 | * Returns 0 for failure to solve due to inconsistency; 1 for | ||
335 | * success; 2 for failure to complete a solution due to either | ||
336 | * ambiguity or it being too difficult. | ||
337 | */ | ||
338 | static int rect_solver(int w, int h, int nrects, struct numberdata *numbers, | ||
339 | unsigned char *hedge, unsigned char *vedge, | ||
340 | random_state *rs) | ||
341 | { | ||
342 | struct rectlist *rectpositions; | ||
343 | int *overlaps, *rectbyplace, *workspace; | ||
344 | int i, ret; | ||
345 | |||
346 | /* | ||
347 | * Start by setting up a list of candidate positions for each | ||
348 | * rectangle. | ||
349 | */ | ||
350 | rectpositions = snewn(nrects, struct rectlist); | ||
351 | for (i = 0; i < nrects; i++) { | ||
352 | int rw, rh, area = numbers[i].area; | ||
353 | int j, minx, miny, maxx, maxy; | ||
354 | struct rect *rlist; | ||
355 | int rlistn, rlistsize; | ||
356 | |||
357 | /* | ||
358 | * For each rectangle, begin by finding the bounding | ||
359 | * rectangle of its candidate number placements. | ||
360 | */ | ||
361 | maxx = maxy = -1; | ||
362 | minx = w; | ||
363 | miny = h; | ||
364 | for (j = 0; j < numbers[i].npoints; j++) { | ||
365 | if (minx > numbers[i].points[j].x) minx = numbers[i].points[j].x; | ||
366 | if (miny > numbers[i].points[j].y) miny = numbers[i].points[j].y; | ||
367 | if (maxx < numbers[i].points[j].x) maxx = numbers[i].points[j].x; | ||
368 | if (maxy < numbers[i].points[j].y) maxy = numbers[i].points[j].y; | ||
369 | } | ||
370 | |||
371 | /* | ||
372 | * Now loop over all possible rectangle placements | ||
373 | * overlapping a point within that bounding rectangle; | ||
374 | * ensure each one actually contains a candidate number | ||
375 | * placement, and add it to the list. | ||
376 | */ | ||
377 | rlist = NULL; | ||
378 | rlistn = rlistsize = 0; | ||
379 | |||
380 | for (rw = 1; rw <= area && rw <= w; rw++) { | ||
381 | int x, y; | ||
382 | |||
383 | if (area % rw) | ||
384 | continue; | ||
385 | rh = area / rw; | ||
386 | if (rh > h) | ||
387 | continue; | ||
388 | |||
389 | for (y = miny - rh + 1; y <= maxy; y++) { | ||
390 | if (y < 0 || y+rh > h) | ||
391 | continue; | ||
392 | |||
393 | for (x = minx - rw + 1; x <= maxx; x++) { | ||
394 | if (x < 0 || x+rw > w) | ||
395 | continue; | ||
396 | |||
397 | /* | ||
398 | * See if we can find a candidate number | ||
399 | * placement within this rectangle. | ||
400 | */ | ||
401 | for (j = 0; j < numbers[i].npoints; j++) | ||
402 | if (numbers[i].points[j].x >= x && | ||
403 | numbers[i].points[j].x < x+rw && | ||
404 | numbers[i].points[j].y >= y && | ||
405 | numbers[i].points[j].y < y+rh) | ||
406 | break; | ||
407 | |||
408 | if (j < numbers[i].npoints) { | ||
409 | /* | ||
410 | * Add this to the list of candidate | ||
411 | * placements for this rectangle. | ||
412 | */ | ||
413 | if (rlistn >= rlistsize) { | ||
414 | rlistsize = rlistn + 32; | ||
415 | rlist = sresize(rlist, rlistsize, struct rect); | ||
416 | } | ||
417 | rlist[rlistn].x = x; | ||
418 | rlist[rlistn].y = y; | ||
419 | rlist[rlistn].w = rw; | ||
420 | rlist[rlistn].h = rh; | ||
421 | #ifdef SOLVER_DIAGNOSTICS | ||
422 | printf("rect %d [area %d]: candidate position at" | ||
423 | " %d,%d w=%d h=%d\n", | ||
424 | i, area, x, y, rw, rh); | ||
425 | #endif | ||
426 | rlistn++; | ||
427 | } | ||
428 | } | ||
429 | } | ||
430 | } | ||
431 | |||
432 | rectpositions[i].rects = rlist; | ||
433 | rectpositions[i].n = rlistn; | ||
434 | } | ||
435 | |||
436 | /* | ||
437 | * Next, construct a multidimensional array tracking how many | ||
438 | * candidate positions for each rectangle overlap each square. | ||
439 | * | ||
440 | * Indexing of this array is by the formula | ||
441 | * | ||
442 | * overlaps[(rectindex * h + y) * w + x] | ||
443 | * | ||
444 | * A positive or zero value indicates what it sounds as if it | ||
445 | * should; -1 indicates that this square _cannot_ be part of | ||
446 | * this rectangle; and -2 indicates that it _definitely_ is | ||
447 | * (which is distinct from 1, because one might very well know | ||
448 | * that _if_ square S is part of rectangle R then it must be | ||
449 | * because R is placed in a certain position without knowing | ||
450 | * that it definitely _is_). | ||
451 | */ | ||
452 | overlaps = snewn(nrects * w * h, int); | ||
453 | memset(overlaps, 0, nrects * w * h * sizeof(int)); | ||
454 | for (i = 0; i < nrects; i++) { | ||
455 | int j; | ||
456 | |||
457 | for (j = 0; j < rectpositions[i].n; j++) { | ||
458 | int xx, yy; | ||
459 | |||
460 | for (yy = 0; yy < rectpositions[i].rects[j].h; yy++) | ||
461 | for (xx = 0; xx < rectpositions[i].rects[j].w; xx++) | ||
462 | overlaps[(i * h + yy+rectpositions[i].rects[j].y) * w + | ||
463 | xx+rectpositions[i].rects[j].x]++; | ||
464 | } | ||
465 | } | ||
466 | |||
467 | /* | ||
468 | * Also we want an array covering the grid once, to make it | ||
469 | * easy to figure out which squares are candidate number | ||
470 | * placements for which rectangles. (The existence of this | ||
471 | * single array assumes that no square starts off as a | ||
472 | * candidate number placement for more than one rectangle. This | ||
473 | * assumption is justified, because this solver is _either_ | ||
474 | * used to solve real problems - in which case there is a | ||
475 | * single placement for every number - _or_ used to decide on | ||
476 | * number placements for a new puzzle, in which case each | ||
477 | * number's placements are confined to the intended position of | ||
478 | * the rectangle containing that number.) | ||
479 | */ | ||
480 | rectbyplace = snewn(w * h, int); | ||
481 | for (i = 0; i < w*h; i++) | ||
482 | rectbyplace[i] = -1; | ||
483 | |||
484 | for (i = 0; i < nrects; i++) { | ||
485 | int j; | ||
486 | |||
487 | for (j = 0; j < numbers[i].npoints; j++) { | ||
488 | int x = numbers[i].points[j].x; | ||
489 | int y = numbers[i].points[j].y; | ||
490 | |||
491 | assert(rectbyplace[y * w + x] == -1); | ||
492 | rectbyplace[y * w + x] = i; | ||
493 | } | ||
494 | } | ||
495 | |||
496 | workspace = snewn(nrects, int); | ||
497 | |||
498 | /* | ||
499 | * Now run the actual deduction loop. | ||
500 | */ | ||
501 | while (1) { | ||
502 | int done_something = FALSE; | ||
503 | |||
504 | #ifdef SOLVER_DIAGNOSTICS | ||
505 | printf("starting deduction loop\n"); | ||
506 | |||
507 | for (i = 0; i < nrects; i++) { | ||
508 | printf("rect %d overlaps:\n", i); | ||
509 | { | ||
510 | int x, y; | ||
511 | for (y = 0; y < h; y++) { | ||
512 | for (x = 0; x < w; x++) { | ||
513 | printf("%3d", overlaps[(i * h + y) * w + x]); | ||
514 | } | ||
515 | printf("\n"); | ||
516 | } | ||
517 | } | ||
518 | } | ||
519 | printf("rectbyplace:\n"); | ||
520 | { | ||
521 | int x, y; | ||
522 | for (y = 0; y < h; y++) { | ||
523 | for (x = 0; x < w; x++) { | ||
524 | printf("%3d", rectbyplace[y * w + x]); | ||
525 | } | ||
526 | printf("\n"); | ||
527 | } | ||
528 | } | ||
529 | #endif | ||
530 | |||
531 | /* | ||
532 | * Housekeeping. Look for rectangles whose number has only | ||
533 | * one candidate position left, and mark that square as | ||
534 | * known if it isn't already. | ||
535 | */ | ||
536 | for (i = 0; i < nrects; i++) { | ||
537 | if (numbers[i].npoints == 1) { | ||
538 | int x = numbers[i].points[0].x; | ||
539 | int y = numbers[i].points[0].y; | ||
540 | if (overlaps[(i * h + y) * w + x] >= -1) { | ||
541 | int j; | ||
542 | |||
543 | if (overlaps[(i * h + y) * w + x] <= 0) { | ||
544 | ret = 0; /* inconsistency */ | ||
545 | goto cleanup; | ||
546 | } | ||
547 | #ifdef SOLVER_DIAGNOSTICS | ||
548 | printf("marking %d,%d as known for rect %d" | ||
549 | " (sole remaining number position)\n", x, y, i); | ||
550 | #endif | ||
551 | |||
552 | for (j = 0; j < nrects; j++) | ||
553 | overlaps[(j * h + y) * w + x] = -1; | ||
554 | |||
555 | overlaps[(i * h + y) * w + x] = -2; | ||
556 | } | ||
557 | } | ||
558 | } | ||
559 | |||
560 | /* | ||
561 | * Now look at the intersection of all possible placements | ||
562 | * for each rectangle, and mark all squares in that | ||
563 | * intersection as known for that rectangle if they aren't | ||
564 | * already. | ||
565 | */ | ||
566 | for (i = 0; i < nrects; i++) { | ||
567 | int minx, miny, maxx, maxy, xx, yy, j; | ||
568 | |||
569 | minx = miny = 0; | ||
570 | maxx = w; | ||
571 | maxy = h; | ||
572 | |||
573 | for (j = 0; j < rectpositions[i].n; j++) { | ||
574 | int x = rectpositions[i].rects[j].x; | ||
575 | int y = rectpositions[i].rects[j].y; | ||
576 | int w = rectpositions[i].rects[j].w; | ||
577 | int h = rectpositions[i].rects[j].h; | ||
578 | |||
579 | if (minx < x) minx = x; | ||
580 | if (miny < y) miny = y; | ||
581 | if (maxx > x+w) maxx = x+w; | ||
582 | if (maxy > y+h) maxy = y+h; | ||
583 | } | ||
584 | |||
585 | for (yy = miny; yy < maxy; yy++) | ||
586 | for (xx = minx; xx < maxx; xx++) | ||
587 | if (overlaps[(i * h + yy) * w + xx] >= -1) { | ||
588 | if (overlaps[(i * h + yy) * w + xx] <= 0) { | ||
589 | ret = 0; /* inconsistency */ | ||
590 | goto cleanup; | ||
591 | } | ||
592 | #ifdef SOLVER_DIAGNOSTICS | ||
593 | printf("marking %d,%d as known for rect %d" | ||
594 | " (intersection of all placements)\n", | ||
595 | xx, yy, i); | ||
596 | #endif | ||
597 | |||
598 | for (j = 0; j < nrects; j++) | ||
599 | overlaps[(j * h + yy) * w + xx] = -1; | ||
600 | |||
601 | overlaps[(i * h + yy) * w + xx] = -2; | ||
602 | } | ||
603 | } | ||
604 | |||
605 | /* | ||
606 | * Rectangle-focused deduction. Look at each rectangle in | ||
607 | * turn and try to rule out some of its candidate | ||
608 | * placements. | ||
609 | */ | ||
610 | for (i = 0; i < nrects; i++) { | ||
611 | int j; | ||
612 | |||
613 | for (j = 0; j < rectpositions[i].n; j++) { | ||
614 | int xx, yy, k; | ||
615 | int del = FALSE; | ||
616 | |||
617 | for (k = 0; k < nrects; k++) | ||
618 | workspace[k] = 0; | ||
619 | |||
620 | for (yy = 0; yy < rectpositions[i].rects[j].h; yy++) { | ||
621 | int y = yy + rectpositions[i].rects[j].y; | ||
622 | for (xx = 0; xx < rectpositions[i].rects[j].w; xx++) { | ||
623 | int x = xx + rectpositions[i].rects[j].x; | ||
624 | |||
625 | if (overlaps[(i * h + y) * w + x] == -1) { | ||
626 | /* | ||
627 | * This placement overlaps a square | ||
628 | * which is _known_ to be part of | ||
629 | * another rectangle. Therefore we must | ||
630 | * rule it out. | ||
631 | */ | ||
632 | #ifdef SOLVER_DIAGNOSTICS | ||
633 | printf("rect %d placement at %d,%d w=%d h=%d " | ||
634 | "contains %d,%d which is known-other\n", i, | ||
635 | rectpositions[i].rects[j].x, | ||
636 | rectpositions[i].rects[j].y, | ||
637 | rectpositions[i].rects[j].w, | ||
638 | rectpositions[i].rects[j].h, | ||
639 | x, y); | ||
640 | #endif | ||
641 | del = TRUE; | ||
642 | } | ||
643 | |||
644 | if (rectbyplace[y * w + x] != -1) { | ||
645 | /* | ||
646 | * This placement overlaps one of the | ||
647 | * candidate number placements for some | ||
648 | * rectangle. Count it. | ||
649 | */ | ||
650 | workspace[rectbyplace[y * w + x]]++; | ||
651 | } | ||
652 | } | ||
653 | } | ||
654 | |||
655 | if (!del) { | ||
656 | /* | ||
657 | * If we haven't ruled this placement out | ||
658 | * already, see if it overlaps _all_ of the | ||
659 | * candidate number placements for any | ||
660 | * rectangle. If so, we can rule it out. | ||
661 | */ | ||
662 | for (k = 0; k < nrects; k++) | ||
663 | if (k != i && workspace[k] == numbers[k].npoints) { | ||
664 | #ifdef SOLVER_DIAGNOSTICS | ||
665 | printf("rect %d placement at %d,%d w=%d h=%d " | ||
666 | "contains all number points for rect %d\n", | ||
667 | i, | ||
668 | rectpositions[i].rects[j].x, | ||
669 | rectpositions[i].rects[j].y, | ||
670 | rectpositions[i].rects[j].w, | ||
671 | rectpositions[i].rects[j].h, | ||
672 | k); | ||
673 | #endif | ||
674 | del = TRUE; | ||
675 | break; | ||
676 | } | ||
677 | |||
678 | /* | ||
679 | * Failing that, see if it overlaps at least | ||
680 | * one of the candidate number placements for | ||
681 | * itself! (This might not be the case if one | ||
682 | * of those number placements has been removed | ||
683 | * recently.). | ||
684 | */ | ||
685 | if (!del && workspace[i] == 0) { | ||
686 | #ifdef SOLVER_DIAGNOSTICS | ||
687 | printf("rect %d placement at %d,%d w=%d h=%d " | ||
688 | "contains none of its own number points\n", | ||
689 | i, | ||
690 | rectpositions[i].rects[j].x, | ||
691 | rectpositions[i].rects[j].y, | ||
692 | rectpositions[i].rects[j].w, | ||
693 | rectpositions[i].rects[j].h); | ||
694 | #endif | ||
695 | del = TRUE; | ||
696 | } | ||
697 | } | ||
698 | |||
699 | if (del) { | ||
700 | remove_rect_placement(w, h, rectpositions, overlaps, i, j); | ||
701 | |||
702 | j--; /* don't skip over next placement */ | ||
703 | |||
704 | done_something = TRUE; | ||
705 | } | ||
706 | } | ||
707 | } | ||
708 | |||
709 | /* | ||
710 | * Square-focused deduction. Look at each square not marked | ||
711 | * as known, and see if there are any which can only be | ||
712 | * part of a single rectangle. | ||
713 | */ | ||
714 | { | ||
715 | int x, y, n, index; | ||
716 | for (y = 0; y < h; y++) for (x = 0; x < w; x++) { | ||
717 | /* Known squares are marked as <0 everywhere, so we only need | ||
718 | * to check the overlaps entry for rect 0. */ | ||
719 | if (overlaps[y * w + x] < 0) | ||
720 | continue; /* known already */ | ||
721 | |||
722 | n = 0; | ||
723 | index = -1; | ||
724 | for (i = 0; i < nrects; i++) | ||
725 | if (overlaps[(i * h + y) * w + x] > 0) | ||
726 | n++, index = i; | ||
727 | |||
728 | if (n == 1) { | ||
729 | int j; | ||
730 | |||
731 | /* | ||
732 | * Now we can rule out all placements for | ||
733 | * rectangle `index' which _don't_ contain | ||
734 | * square x,y. | ||
735 | */ | ||
736 | #ifdef SOLVER_DIAGNOSTICS | ||
737 | printf("square %d,%d can only be in rectangle %d\n", | ||
738 | x, y, index); | ||
739 | #endif | ||
740 | for (j = 0; j < rectpositions[index].n; j++) { | ||
741 | struct rect *r = &rectpositions[index].rects[j]; | ||
742 | if (x >= r->x && x < r->x + r->w && | ||
743 | y >= r->y && y < r->y + r->h) | ||
744 | continue; /* this one is OK */ | ||
745 | remove_rect_placement(w, h, rectpositions, overlaps, | ||
746 | index, j); | ||
747 | j--; /* don't skip over next placement */ | ||
748 | done_something = TRUE; | ||
749 | } | ||
750 | } | ||
751 | } | ||
752 | } | ||
753 | |||
754 | /* | ||
755 | * If we've managed to deduce anything by normal means, | ||
756 | * loop round again and see if there's more to be done. | ||
757 | * Only if normal deduction has completely failed us should | ||
758 | * we now move on to narrowing down the possible number | ||
759 | * placements. | ||
760 | */ | ||
761 | if (done_something) | ||
762 | continue; | ||
763 | |||
764 | /* | ||
765 | * Now we have done everything we can with the current set | ||
766 | * of number placements. So we need to winnow the number | ||
767 | * placements so as to narrow down the possibilities. We do | ||
768 | * this by searching for a candidate placement (of _any_ | ||
769 | * rectangle) which overlaps a candidate placement of the | ||
770 | * number for some other rectangle. | ||
771 | */ | ||
772 | if (rs) { | ||
773 | struct rpn { | ||
774 | int rect; | ||
775 | int placement; | ||
776 | int number; | ||
777 | } *rpns = NULL; | ||
778 | size_t nrpns = 0, rpnsize = 0; | ||
779 | int j; | ||
780 | |||
781 | for (i = 0; i < nrects; i++) { | ||
782 | for (j = 0; j < rectpositions[i].n; j++) { | ||
783 | int xx, yy; | ||
784 | |||
785 | for (yy = 0; yy < rectpositions[i].rects[j].h; yy++) { | ||
786 | int y = yy + rectpositions[i].rects[j].y; | ||
787 | for (xx = 0; xx < rectpositions[i].rects[j].w; xx++) { | ||
788 | int x = xx + rectpositions[i].rects[j].x; | ||
789 | |||
790 | if (rectbyplace[y * w + x] >= 0 && | ||
791 | rectbyplace[y * w + x] != i) { | ||
792 | /* | ||
793 | * Add this to the list of | ||
794 | * winnowing possibilities. | ||
795 | */ | ||
796 | if (nrpns >= rpnsize) { | ||
797 | rpnsize = rpnsize * 3 / 2 + 32; | ||
798 | rpns = sresize(rpns, rpnsize, struct rpn); | ||
799 | } | ||
800 | rpns[nrpns].rect = i; | ||
801 | rpns[nrpns].placement = j; | ||
802 | rpns[nrpns].number = rectbyplace[y * w + x]; | ||
803 | nrpns++; | ||
804 | } | ||
805 | } | ||
806 | } | ||
807 | |||
808 | } | ||
809 | } | ||
810 | |||
811 | #ifdef SOLVER_DIAGNOSTICS | ||
812 | printf("%d candidate rect placements we could eliminate\n", nrpns); | ||
813 | #endif | ||
814 | if (nrpns > 0) { | ||
815 | /* | ||
816 | * Now choose one of these unwanted rectangle | ||
817 | * placements, and eliminate it. | ||
818 | */ | ||
819 | int index = random_upto(rs, nrpns); | ||
820 | int k, m; | ||
821 | struct rpn rpn = rpns[index]; | ||
822 | struct rect r; | ||
823 | sfree(rpns); | ||
824 | |||
825 | i = rpn.rect; | ||
826 | j = rpn.placement; | ||
827 | k = rpn.number; | ||
828 | r = rectpositions[i].rects[j]; | ||
829 | |||
830 | /* | ||
831 | * We rule out placement j of rectangle i by means | ||
832 | * of removing all of rectangle k's candidate | ||
833 | * number placements which do _not_ overlap it. | ||
834 | * This will ensure that it is eliminated during | ||
835 | * the next pass of rectangle-focused deduction. | ||
836 | */ | ||
837 | #ifdef SOLVER_DIAGNOSTICS | ||
838 | printf("ensuring number for rect %d is within" | ||
839 | " rect %d's placement at %d,%d w=%d h=%d\n", | ||
840 | k, i, r.x, r.y, r.w, r.h); | ||
841 | #endif | ||
842 | |||
843 | for (m = 0; m < numbers[k].npoints; m++) { | ||
844 | int x = numbers[k].points[m].x; | ||
845 | int y = numbers[k].points[m].y; | ||
846 | |||
847 | if (x < r.x || x >= r.x + r.w || | ||
848 | y < r.y || y >= r.y + r.h) { | ||
849 | #ifdef SOLVER_DIAGNOSTICS | ||
850 | printf("eliminating number for rect %d at %d,%d\n", | ||
851 | k, x, y); | ||
852 | #endif | ||
853 | remove_number_placement(w, h, &numbers[k], | ||
854 | m, rectbyplace); | ||
855 | m--; /* don't skip the next one */ | ||
856 | done_something = TRUE; | ||
857 | } | ||
858 | } | ||
859 | } | ||
860 | } | ||
861 | |||
862 | if (!done_something) { | ||
863 | #ifdef SOLVER_DIAGNOSTICS | ||
864 | printf("terminating deduction loop\n"); | ||
865 | #endif | ||
866 | break; | ||
867 | } | ||
868 | } | ||
869 | |||
870 | cleanup: | ||
871 | ret = 1; | ||
872 | for (i = 0; i < nrects; i++) { | ||
873 | #ifdef SOLVER_DIAGNOSTICS | ||
874 | printf("rect %d has %d possible placements\n", | ||
875 | i, rectpositions[i].n); | ||
876 | #endif | ||
877 | if (rectpositions[i].n <= 0) { | ||
878 | ret = 0; /* inconsistency */ | ||
879 | } else if (rectpositions[i].n > 1) { | ||
880 | ret = 2; /* remaining uncertainty */ | ||
881 | } else if (hedge && vedge) { | ||
882 | /* | ||
883 | * Place the rectangle in its only possible position. | ||
884 | */ | ||
885 | int x, y; | ||
886 | struct rect *r = &rectpositions[i].rects[0]; | ||
887 | |||
888 | for (y = 0; y < r->h; y++) { | ||
889 | if (r->x > 0) | ||
890 | vedge[(r->y+y) * w + r->x] = 1; | ||
891 | if (r->x+r->w < w) | ||
892 | vedge[(r->y+y) * w + r->x+r->w] = 1; | ||
893 | } | ||
894 | for (x = 0; x < r->w; x++) { | ||
895 | if (r->y > 0) | ||
896 | hedge[r->y * w + r->x+x] = 1; | ||
897 | if (r->y+r->h < h) | ||
898 | hedge[(r->y+r->h) * w + r->x+x] = 1; | ||
899 | } | ||
900 | } | ||
901 | } | ||
902 | |||
903 | /* | ||
904 | * Free up all allocated storage. | ||
905 | */ | ||
906 | sfree(workspace); | ||
907 | sfree(rectbyplace); | ||
908 | sfree(overlaps); | ||
909 | for (i = 0; i < nrects; i++) | ||
910 | sfree(rectpositions[i].rects); | ||
911 | sfree(rectpositions); | ||
912 | |||
913 | return ret; | ||
914 | } | ||
915 | |||
916 | /* ---------------------------------------------------------------------- | ||
917 | * Grid generation code. | ||
918 | */ | ||
919 | |||
920 | /* | ||
921 | * This function does one of two things. If passed r==NULL, it | ||
922 | * counts the number of possible rectangles which cover the given | ||
923 | * square, and returns it in *n. If passed r!=NULL then it _reads_ | ||
924 | * *n to find an index, counts the possible rectangles until it | ||
925 | * reaches the nth, and writes it into r. | ||
926 | * | ||
927 | * `scratch' is expected to point to an array of 2 * params->w | ||
928 | * ints, used internally as scratch space (and passed in like this | ||
929 | * to avoid re-allocating and re-freeing it every time round a | ||
930 | * tight loop). | ||
931 | */ | ||
932 | static void enum_rects(game_params *params, int *grid, struct rect *r, int *n, | ||
933 | int sx, int sy, int *scratch) | ||
934 | { | ||
935 | int rw, rh, mw, mh; | ||
936 | int x, y, dx, dy; | ||
937 | int maxarea, realmaxarea; | ||
938 | int index = 0; | ||
939 | int *top, *bottom; | ||
940 | |||
941 | /* | ||
942 | * Maximum rectangle area is 1/6 of total grid size, unless | ||
943 | * this means we can't place any rectangles at all in which | ||
944 | * case we set it to 2 at minimum. | ||
945 | */ | ||
946 | maxarea = params->w * params->h / 6; | ||
947 | if (maxarea < 2) | ||
948 | maxarea = 2; | ||
949 | |||
950 | /* | ||
951 | * Scan the grid to find the limits of the region within which | ||
952 | * any rectangle containing this point must fall. This will | ||
953 | * save us trawling the inside of every rectangle later on to | ||
954 | * see if it contains any used squares. | ||
955 | */ | ||
956 | top = scratch; | ||
957 | bottom = scratch + params->w; | ||
958 | for (dy = -1; dy <= +1; dy += 2) { | ||
959 | int *array = (dy == -1 ? top : bottom); | ||
960 | for (dx = -1; dx <= +1; dx += 2) { | ||
961 | for (x = sx; x >= 0 && x < params->w; x += dx) { | ||
962 | array[x] = -2 * params->h * dy; | ||
963 | for (y = sy; y >= 0 && y < params->h; y += dy) { | ||
964 | if (index(params, grid, x, y) == -1 && | ||
965 | (x == sx || dy*y <= dy*array[x-dx])) | ||
966 | array[x] = y; | ||
967 | else | ||
968 | break; | ||
969 | } | ||
970 | } | ||
971 | } | ||
972 | } | ||
973 | |||
974 | /* | ||
975 | * Now scan again to work out the largest rectangles we can fit | ||
976 | * in the grid, so that we can terminate the following loops | ||
977 | * early once we get down to not having much space left in the | ||
978 | * grid. | ||
979 | */ | ||
980 | realmaxarea = 0; | ||
981 | for (x = 0; x < params->w; x++) { | ||
982 | int x2; | ||
983 | |||
984 | rh = bottom[x] - top[x] + 1; | ||
985 | if (rh <= 0) | ||
986 | continue; /* no rectangles can start here */ | ||
987 | |||
988 | dx = (x > sx ? -1 : +1); | ||
989 | for (x2 = x; x2 >= 0 && x2 < params->w; x2 += dx) | ||
990 | if (bottom[x2] < bottom[x] || top[x2] > top[x]) | ||
991 | break; | ||
992 | |||
993 | rw = abs(x2 - x); | ||
994 | if (realmaxarea < rw * rh) | ||
995 | realmaxarea = rw * rh; | ||
996 | } | ||
997 | |||
998 | if (realmaxarea > maxarea) | ||
999 | realmaxarea = maxarea; | ||
1000 | |||
1001 | /* | ||
1002 | * Rectangles which go right the way across the grid are | ||
1003 | * boring, although they can't be helped in the case of | ||
1004 | * extremely small grids. (Also they might be generated later | ||
1005 | * on by the singleton-removal process; we can't help that.) | ||
1006 | */ | ||
1007 | mw = params->w - 1; | ||
1008 | if (mw < 3) mw++; | ||
1009 | mh = params->h - 1; | ||
1010 | if (mh < 3) mh++; | ||
1011 | |||
1012 | for (rw = 1; rw <= mw; rw++) | ||
1013 | for (rh = 1; rh <= mh; rh++) { | ||
1014 | if (rw * rh > realmaxarea) | ||
1015 | continue; | ||
1016 | if (rw * rh == 1) | ||
1017 | continue; | ||
1018 | for (x = max(sx - rw + 1, 0); x <= min(sx, params->w - rw); x++) | ||
1019 | for (y = max(sy - rh + 1, 0); y <= min(sy, params->h - rh); | ||
1020 | y++) { | ||
1021 | /* | ||
1022 | * Check this rectangle against the region we | ||
1023 | * defined above. | ||
1024 | */ | ||
1025 | if (top[x] <= y && top[x+rw-1] <= y && | ||
1026 | bottom[x] >= y+rh-1 && bottom[x+rw-1] >= y+rh-1) { | ||
1027 | if (r && index == *n) { | ||
1028 | r->x = x; | ||
1029 | r->y = y; | ||
1030 | r->w = rw; | ||
1031 | r->h = rh; | ||
1032 | return; | ||
1033 | } | ||
1034 | index++; | ||
1035 | } | ||
1036 | } | ||
1037 | } | ||
1038 | |||
1039 | assert(!r); | ||
1040 | *n = index; | ||
1041 | } | ||
1042 | |||
1043 | static void place_rect(game_params *params, int *grid, struct rect r) | ||
1044 | { | ||
1045 | int idx = INDEX(params, r.x, r.y); | ||
1046 | int x, y; | ||
1047 | |||
1048 | for (x = r.x; x < r.x+r.w; x++) | ||
1049 | for (y = r.y; y < r.y+r.h; y++) { | ||
1050 | index(params, grid, x, y) = idx; | ||
1051 | } | ||
1052 | #ifdef GENERATION_DIAGNOSTICS | ||
1053 | printf(" placing rectangle at (%d,%d) size %d x %d\n", | ||
1054 | r.x, r.y, r.w, r.h); | ||
1055 | #endif | ||
1056 | } | ||
1057 | |||
1058 | static struct rect find_rect(game_params *params, int *grid, int x, int y) | ||
1059 | { | ||
1060 | int idx, w, h; | ||
1061 | struct rect r; | ||
1062 | |||
1063 | /* | ||
1064 | * Find the top left of the rectangle. | ||
1065 | */ | ||
1066 | idx = index(params, grid, x, y); | ||
1067 | |||
1068 | if (idx < 0) { | ||
1069 | r.x = x; | ||
1070 | r.y = y; | ||
1071 | r.w = r.h = 1; | ||
1072 | return r; /* 1x1 singleton here */ | ||
1073 | } | ||
1074 | |||
1075 | y = idx / params->w; | ||
1076 | x = idx % params->w; | ||
1077 | |||
1078 | /* | ||
1079 | * Find the width and height of the rectangle. | ||
1080 | */ | ||
1081 | for (w = 1; | ||
1082 | (x+w < params->w && index(params,grid,x+w,y)==idx); | ||
1083 | w++); | ||
1084 | for (h = 1; | ||
1085 | (y+h < params->h && index(params,grid,x,y+h)==idx); | ||
1086 | h++); | ||
1087 | |||
1088 | r.x = x; | ||
1089 | r.y = y; | ||
1090 | r.w = w; | ||
1091 | r.h = h; | ||
1092 | |||
1093 | return r; | ||
1094 | } | ||
1095 | |||
1096 | #ifdef GENERATION_DIAGNOSTICS | ||
1097 | static void display_grid(game_params *params, int *grid, int *numbers, int all) | ||
1098 | { | ||
1099 | unsigned char *egrid = snewn((params->w*2+3) * (params->h*2+3), | ||
1100 | unsigned char); | ||
1101 | int x, y; | ||
1102 | int r = (params->w*2+3); | ||
1103 | |||
1104 | memset(egrid, 0, (params->w*2+3) * (params->h*2+3)); | ||
1105 | |||
1106 | for (x = 0; x < params->w; x++) | ||
1107 | for (y = 0; y < params->h; y++) { | ||
1108 | int i = index(params, grid, x, y); | ||
1109 | if (x == 0 || index(params, grid, x-1, y) != i) | ||
1110 | egrid[(2*y+2) * r + (2*x+1)] = 1; | ||
1111 | if (x == params->w-1 || index(params, grid, x+1, y) != i) | ||
1112 | egrid[(2*y+2) * r + (2*x+3)] = 1; | ||
1113 | if (y == 0 || index(params, grid, x, y-1) != i) | ||
1114 | egrid[(2*y+1) * r + (2*x+2)] = 1; | ||
1115 | if (y == params->h-1 || index(params, grid, x, y+1) != i) | ||
1116 | egrid[(2*y+3) * r + (2*x+2)] = 1; | ||
1117 | } | ||
1118 | |||
1119 | for (y = 1; y < 2*params->h+2; y++) { | ||
1120 | for (x = 1; x < 2*params->w+2; x++) { | ||
1121 | if (!((y|x)&1)) { | ||
1122 | int k = numbers ? index(params, numbers, x/2-1, y/2-1) : 0; | ||
1123 | if (k || (all && numbers)) printf("%2d", k); else printf(" "); | ||
1124 | } else if (!((y&x)&1)) { | ||
1125 | int v = egrid[y*r+x]; | ||
1126 | if ((y&1) && v) v = '-'; | ||
1127 | if ((x&1) && v) v = '|'; | ||
1128 | if (!v) v = ' '; | ||
1129 | putchar(v); | ||
1130 | if (!(x&1)) putchar(v); | ||
1131 | } else { | ||
1132 | int c, d = 0; | ||
1133 | if (egrid[y*r+(x+1)]) d |= 1; | ||
1134 | if (egrid[(y-1)*r+x]) d |= 2; | ||
1135 | if (egrid[y*r+(x-1)]) d |= 4; | ||
1136 | if (egrid[(y+1)*r+x]) d |= 8; | ||
1137 | c = " ??+?-++?+|+++++"[d]; | ||
1138 | putchar(c); | ||
1139 | if (!(x&1)) putchar(c); | ||
1140 | } | ||
1141 | } | ||
1142 | putchar('\n'); | ||
1143 | } | ||
1144 | |||
1145 | sfree(egrid); | ||
1146 | } | ||
1147 | #endif | ||
1148 | |||
1149 | static char *new_game_desc(const game_params *params_in, random_state *rs, | ||
1150 | char **aux, int interactive) | ||
1151 | { | ||
1152 | game_params params_copy = *params_in; /* structure copy */ | ||
1153 | game_params *params = ¶ms_copy; | ||
1154 | int *grid, *numbers = NULL; | ||
1155 | int x, y, y2, y2last, yx, run, i, nsquares; | ||
1156 | char *desc, *p; | ||
1157 | int *enum_rects_scratch; | ||
1158 | game_params params2real, *params2 = ¶ms2real; | ||
1159 | |||
1160 | while (1) { | ||
1161 | /* | ||
1162 | * Set up the smaller width and height which we will use to | ||
1163 | * generate the base grid. | ||
1164 | */ | ||
1165 | params2->w = (int)((float)params->w / (1.0F + params->expandfactor)); | ||
1166 | if (params2->w < 2 && params->w >= 2) params2->w = 2; | ||
1167 | params2->h = (int)((float)params->h / (1.0F + params->expandfactor)); | ||
1168 | if (params2->h < 2 && params->h >= 2) params2->h = 2; | ||
1169 | |||
1170 | grid = snewn(params2->w * params2->h, int); | ||
1171 | |||
1172 | enum_rects_scratch = snewn(2 * params2->w, int); | ||
1173 | |||
1174 | nsquares = 0; | ||
1175 | for (y = 0; y < params2->h; y++) | ||
1176 | for (x = 0; x < params2->w; x++) { | ||
1177 | index(params2, grid, x, y) = -1; | ||
1178 | nsquares++; | ||
1179 | } | ||
1180 | |||
1181 | /* | ||
1182 | * Place rectangles until we can't any more. We do this by | ||
1183 | * finding a square we haven't yet covered, and randomly | ||
1184 | * choosing a rectangle to cover it. | ||
1185 | */ | ||
1186 | |||
1187 | while (nsquares > 0) { | ||
1188 | int square = random_upto(rs, nsquares); | ||
1189 | int n; | ||
1190 | struct rect r; | ||
1191 | |||
1192 | x = params2->w; | ||
1193 | y = params2->h; | ||
1194 | for (y = 0; y < params2->h; y++) { | ||
1195 | for (x = 0; x < params2->w; x++) { | ||
1196 | if (index(params2, grid, x, y) == -1 && square-- == 0) | ||
1197 | break; | ||
1198 | } | ||
1199 | if (x < params2->w) | ||
1200 | break; | ||
1201 | } | ||
1202 | assert(x < params2->w && y < params2->h); | ||
1203 | |||
1204 | /* | ||
1205 | * Now see how many rectangles fit around this one. | ||
1206 | */ | ||
1207 | enum_rects(params2, grid, NULL, &n, x, y, enum_rects_scratch); | ||
1208 | |||
1209 | if (!n) { | ||
1210 | /* | ||
1211 | * There are no possible rectangles covering this | ||
1212 | * square, meaning it must be a singleton. Mark it | ||
1213 | * -2 so we know not to keep trying. | ||
1214 | */ | ||
1215 | index(params2, grid, x, y) = -2; | ||
1216 | nsquares--; | ||
1217 | } else { | ||
1218 | /* | ||
1219 | * Pick one at random. | ||
1220 | */ | ||
1221 | n = random_upto(rs, n); | ||
1222 | enum_rects(params2, grid, &r, &n, x, y, enum_rects_scratch); | ||
1223 | |||
1224 | /* | ||
1225 | * Place it. | ||
1226 | */ | ||
1227 | place_rect(params2, grid, r); | ||
1228 | nsquares -= r.w * r.h; | ||
1229 | } | ||
1230 | } | ||
1231 | |||
1232 | sfree(enum_rects_scratch); | ||
1233 | |||
1234 | /* | ||
1235 | * Deal with singleton spaces remaining in the grid, one by | ||
1236 | * one. | ||
1237 | * | ||
1238 | * We do this by making a local change to the layout. There are | ||
1239 | * several possibilities: | ||
1240 | * | ||
1241 | * +-----+-----+ Here, we can remove the singleton by | ||
1242 | * | | | extending the 1x2 rectangle below it | ||
1243 | * +--+--+-----+ into a 1x3. | ||
1244 | * | | | | | ||
1245 | * | +--+ | | ||
1246 | * | | | | | ||
1247 | * | | | | | ||
1248 | * | | | | | ||
1249 | * +--+--+-----+ | ||
1250 | * | ||
1251 | * +--+--+--+ Here, that trick doesn't work: there's no | ||
1252 | * | | | 1 x n rectangle with the singleton at one | ||
1253 | * | | | end. Instead, we extend a 1 x n rectangle | ||
1254 | * | | | _out_ from the singleton, shaving a layer | ||
1255 | * +--+--+ | off the end of another rectangle. So if we | ||
1256 | * | | | | extended up, we'd make our singleton part | ||
1257 | * | +--+--+ of a 1x3 and generate a 1x2 where the 2x2 | ||
1258 | * | | | used to be; or we could extend right into | ||
1259 | * +--+-----+ a 2x1, turning the 1x3 into a 1x2. | ||
1260 | * | ||
1261 | * +-----+--+ Here, we can't even do _that_, since any | ||
1262 | * | | | direction we choose to extend the singleton | ||
1263 | * +--+--+ | will produce a new singleton as a result of | ||
1264 | * | | | | truncating one of the size-2 rectangles. | ||
1265 | * | +--+--+ Fortunately, this case can _only_ occur when | ||
1266 | * | | | a singleton is surrounded by four size-2s | ||
1267 | * +--+-----+ in this fashion; so instead we can simply | ||
1268 | * replace the whole section with a single 3x3. | ||
1269 | */ | ||
1270 | for (x = 0; x < params2->w; x++) { | ||
1271 | for (y = 0; y < params2->h; y++) { | ||
1272 | if (index(params2, grid, x, y) < 0) { | ||
1273 | int dirs[4], ndirs; | ||
1274 | |||
1275 | #ifdef GENERATION_DIAGNOSTICS | ||
1276 | display_grid(params2, grid, NULL, FALSE); | ||
1277 | printf("singleton at %d,%d\n", x, y); | ||
1278 | #endif | ||
1279 | |||
1280 | /* | ||
1281 | * Check in which directions we can feasibly extend | ||
1282 | * the singleton. We can extend in a particular | ||
1283 | * direction iff either: | ||
1284 | * | ||
1285 | * - the rectangle on that side of the singleton | ||
1286 | * is not 2x1, and we are at one end of the edge | ||
1287 | * of it we are touching | ||
1288 | * | ||
1289 | * - it is 2x1 but we are on its short side. | ||
1290 | * | ||
1291 | * FIXME: we could plausibly choose between these | ||
1292 | * based on the sizes of the rectangles they would | ||
1293 | * create? | ||
1294 | */ | ||
1295 | ndirs = 0; | ||
1296 | if (x < params2->w-1) { | ||
1297 | struct rect r = find_rect(params2, grid, x+1, y); | ||
1298 | if ((r.w * r.h > 2 && (r.y==y || r.y+r.h-1==y)) || r.h==1) | ||
1299 | dirs[ndirs++] = 1; /* right */ | ||
1300 | } | ||
1301 | if (y > 0) { | ||
1302 | struct rect r = find_rect(params2, grid, x, y-1); | ||
1303 | if ((r.w * r.h > 2 && (r.x==x || r.x+r.w-1==x)) || r.w==1) | ||
1304 | dirs[ndirs++] = 2; /* up */ | ||
1305 | } | ||
1306 | if (x > 0) { | ||
1307 | struct rect r = find_rect(params2, grid, x-1, y); | ||
1308 | if ((r.w * r.h > 2 && (r.y==y || r.y+r.h-1==y)) || r.h==1) | ||
1309 | dirs[ndirs++] = 4; /* left */ | ||
1310 | } | ||
1311 | if (y < params2->h-1) { | ||
1312 | struct rect r = find_rect(params2, grid, x, y+1); | ||
1313 | if ((r.w * r.h > 2 && (r.x==x || r.x+r.w-1==x)) || r.w==1) | ||
1314 | dirs[ndirs++] = 8; /* down */ | ||
1315 | } | ||
1316 | |||
1317 | if (ndirs > 0) { | ||
1318 | int which, dir; | ||
1319 | struct rect r1, r2; | ||
1320 | memset(&r1, 0, sizeof(struct rect)); | ||
1321 | memset(&r2, 0, sizeof(struct rect)); | ||
1322 | which = random_upto(rs, ndirs); | ||
1323 | dir = dirs[which]; | ||
1324 | |||
1325 | switch (dir) { | ||
1326 | case 1: /* right */ | ||
1327 | assert(x < params2->w+1); | ||
1328 | #ifdef GENERATION_DIAGNOSTICS | ||
1329 | printf("extending right\n"); | ||
1330 | #endif | ||
1331 | r1 = find_rect(params2, grid, x+1, y); | ||
1332 | r2.x = x; | ||
1333 | r2.y = y; | ||
1334 | r2.w = 1 + r1.w; | ||
1335 | r2.h = 1; | ||
1336 | if (r1.y == y) | ||
1337 | r1.y++; | ||
1338 | r1.h--; | ||
1339 | break; | ||
1340 | case 2: /* up */ | ||
1341 | assert(y > 0); | ||
1342 | #ifdef GENERATION_DIAGNOSTICS | ||
1343 | printf("extending up\n"); | ||
1344 | #endif | ||
1345 | r1 = find_rect(params2, grid, x, y-1); | ||
1346 | r2.x = x; | ||
1347 | r2.y = r1.y; | ||
1348 | r2.w = 1; | ||
1349 | r2.h = 1 + r1.h; | ||
1350 | if (r1.x == x) | ||
1351 | r1.x++; | ||
1352 | r1.w--; | ||
1353 | break; | ||
1354 | case 4: /* left */ | ||
1355 | assert(x > 0); | ||
1356 | #ifdef GENERATION_DIAGNOSTICS | ||
1357 | printf("extending left\n"); | ||
1358 | #endif | ||
1359 | r1 = find_rect(params2, grid, x-1, y); | ||
1360 | r2.x = r1.x; | ||
1361 | r2.y = y; | ||
1362 | r2.w = 1 + r1.w; | ||
1363 | r2.h = 1; | ||
1364 | if (r1.y == y) | ||
1365 | r1.y++; | ||
1366 | r1.h--; | ||
1367 | break; | ||
1368 | case 8: /* down */ | ||
1369 | assert(y < params2->h+1); | ||
1370 | #ifdef GENERATION_DIAGNOSTICS | ||
1371 | printf("extending down\n"); | ||
1372 | #endif | ||
1373 | r1 = find_rect(params2, grid, x, y+1); | ||
1374 | r2.x = x; | ||
1375 | r2.y = y; | ||
1376 | r2.w = 1; | ||
1377 | r2.h = 1 + r1.h; | ||
1378 | if (r1.x == x) | ||
1379 | r1.x++; | ||
1380 | r1.w--; | ||
1381 | break; | ||
1382 | default: /* should never happen */ | ||
1383 | assert(!"invalid direction"); | ||
1384 | } | ||
1385 | if (r1.h > 0 && r1.w > 0) | ||
1386 | place_rect(params2, grid, r1); | ||
1387 | place_rect(params2, grid, r2); | ||
1388 | } else { | ||
1389 | #ifndef NDEBUG | ||
1390 | /* | ||
1391 | * Sanity-check that there really is a 3x3 | ||
1392 | * rectangle surrounding this singleton and it | ||
1393 | * contains absolutely everything we could | ||
1394 | * possibly need. | ||
1395 | */ | ||
1396 | { | ||
1397 | int xx, yy; | ||
1398 | assert(x > 0 && x < params2->w-1); | ||
1399 | assert(y > 0 && y < params2->h-1); | ||
1400 | |||
1401 | for (xx = x-1; xx <= x+1; xx++) | ||
1402 | for (yy = y-1; yy <= y+1; yy++) { | ||
1403 | struct rect r = find_rect(params2,grid,xx,yy); | ||
1404 | assert(r.x >= x-1); | ||
1405 | assert(r.y >= y-1); | ||
1406 | assert(r.x+r.w-1 <= x+1); | ||
1407 | assert(r.y+r.h-1 <= y+1); | ||
1408 | } | ||
1409 | } | ||
1410 | #endif | ||
1411 | |||
1412 | #ifdef GENERATION_DIAGNOSTICS | ||
1413 | printf("need the 3x3 trick\n"); | ||
1414 | #endif | ||
1415 | |||
1416 | /* | ||
1417 | * FIXME: If the maximum rectangle area for | ||
1418 | * this grid is less than 9, we ought to | ||
1419 | * subdivide the 3x3 in some fashion. There are | ||
1420 | * five other possibilities: | ||
1421 | * | ||
1422 | * - a 6 and a 3 | ||
1423 | * - a 4, a 3 and a 2 | ||
1424 | * - three 3s | ||
1425 | * - a 3 and three 2s (two different arrangements). | ||
1426 | */ | ||
1427 | |||
1428 | { | ||
1429 | struct rect r; | ||
1430 | r.x = x-1; | ||
1431 | r.y = y-1; | ||
1432 | r.w = r.h = 3; | ||
1433 | place_rect(params2, grid, r); | ||
1434 | } | ||
1435 | } | ||
1436 | } | ||
1437 | } | ||
1438 | } | ||
1439 | |||
1440 | /* | ||
1441 | * We have now constructed a grid of the size specified in | ||
1442 | * params2. Now we extend it into a grid of the size specified | ||
1443 | * in params. We do this in two passes: we extend it vertically | ||
1444 | * until it's the right height, then we transpose it, then | ||
1445 | * extend it vertically again (getting it effectively the right | ||
1446 | * width), then finally transpose again. | ||
1447 | */ | ||
1448 | for (i = 0; i < 2; i++) { | ||
1449 | int *grid2, *expand, *where; | ||
1450 | game_params params3real, *params3 = ¶ms3real; | ||
1451 | |||
1452 | #ifdef GENERATION_DIAGNOSTICS | ||
1453 | printf("before expansion:\n"); | ||
1454 | display_grid(params2, grid, NULL, TRUE); | ||
1455 | #endif | ||
1456 | |||
1457 | /* | ||
1458 | * Set up the new grid. | ||
1459 | */ | ||
1460 | grid2 = snewn(params2->w * params->h, int); | ||
1461 | expand = snewn(params2->h-1, int); | ||
1462 | where = snewn(params2->w, int); | ||
1463 | params3->w = params2->w; | ||
1464 | params3->h = params->h; | ||
1465 | |||
1466 | /* | ||
1467 | * Decide which horizontal edges are going to get expanded, | ||
1468 | * and by how much. | ||
1469 | */ | ||
1470 | for (y = 0; y < params2->h-1; y++) | ||
1471 | expand[y] = 0; | ||
1472 | for (y = params2->h; y < params->h; y++) { | ||
1473 | x = random_upto(rs, params2->h-1); | ||
1474 | expand[x]++; | ||
1475 | } | ||
1476 | |||
1477 | #ifdef GENERATION_DIAGNOSTICS | ||
1478 | printf("expand[] = {"); | ||
1479 | for (y = 0; y < params2->h-1; y++) | ||
1480 | printf(" %d", expand[y]); | ||
1481 | printf(" }\n"); | ||
1482 | #endif | ||
1483 | |||
1484 | /* | ||
1485 | * Perform the expansion. The way this works is that we | ||
1486 | * alternately: | ||
1487 | * | ||
1488 | * - copy a row from grid into grid2 | ||
1489 | * | ||
1490 | * - invent some number of additional rows in grid2 where | ||
1491 | * there was previously only a horizontal line between | ||
1492 | * rows in grid, and make random decisions about where | ||
1493 | * among these to place each rectangle edge that ran | ||
1494 | * along this line. | ||
1495 | */ | ||
1496 | for (y = y2 = y2last = 0; y < params2->h; y++) { | ||
1497 | /* | ||
1498 | * Copy a single line from row y of grid into row y2 of | ||
1499 | * grid2. | ||
1500 | */ | ||
1501 | for (x = 0; x < params2->w; x++) { | ||
1502 | int val = index(params2, grid, x, y); | ||
1503 | if (val / params2->w == y && /* rect starts on this line */ | ||
1504 | (y2 == 0 || /* we're at the very top, or... */ | ||
1505 | index(params3, grid2, x, y2-1) / params3->w < y2last | ||
1506 | /* this rect isn't already started */)) | ||
1507 | index(params3, grid2, x, y2) = | ||
1508 | INDEX(params3, val % params2->w, y2); | ||
1509 | else | ||
1510 | index(params3, grid2, x, y2) = | ||
1511 | index(params3, grid2, x, y2-1); | ||
1512 | } | ||
1513 | |||
1514 | /* | ||
1515 | * If that was the last line, terminate the loop early. | ||
1516 | */ | ||
1517 | if (++y2 == params3->h) | ||
1518 | break; | ||
1519 | |||
1520 | y2last = y2; | ||
1521 | |||
1522 | /* | ||
1523 | * Invent some number of additional lines. First walk | ||
1524 | * along this line working out where to put all the | ||
1525 | * edges that coincide with it. | ||
1526 | */ | ||
1527 | yx = -1; | ||
1528 | for (x = 0; x < params2->w; x++) { | ||
1529 | if (index(params2, grid, x, y) != | ||
1530 | index(params2, grid, x, y+1)) { | ||
1531 | /* | ||
1532 | * This is a horizontal edge, so it needs | ||
1533 | * placing. | ||
1534 | */ | ||
1535 | if (x == 0 || | ||
1536 | (index(params2, grid, x-1, y) != | ||
1537 | index(params2, grid, x, y) && | ||
1538 | index(params2, grid, x-1, y+1) != | ||
1539 | index(params2, grid, x, y+1))) { | ||
1540 | /* | ||
1541 | * Here we have the chance to make a new | ||
1542 | * decision. | ||
1543 | */ | ||
1544 | yx = random_upto(rs, expand[y]+1); | ||
1545 | } else { | ||
1546 | /* | ||
1547 | * Here we just reuse the previous value of | ||
1548 | * yx. | ||
1549 | */ | ||
1550 | } | ||
1551 | } else | ||
1552 | yx = -1; | ||
1553 | where[x] = yx; | ||
1554 | } | ||
1555 | |||
1556 | for (yx = 0; yx < expand[y]; yx++) { | ||
1557 | /* | ||
1558 | * Invent a single row. For each square in the row, | ||
1559 | * we copy the grid entry from the square above it, | ||
1560 | * unless we're starting the new rectangle here. | ||
1561 | */ | ||
1562 | for (x = 0; x < params2->w; x++) { | ||
1563 | if (yx == where[x]) { | ||
1564 | int val = index(params2, grid, x, y+1); | ||
1565 | val %= params2->w; | ||
1566 | val = INDEX(params3, val, y2); | ||
1567 | index(params3, grid2, x, y2) = val; | ||
1568 | } else | ||
1569 | index(params3, grid2, x, y2) = | ||
1570 | index(params3, grid2, x, y2-1); | ||
1571 | } | ||
1572 | |||
1573 | y2++; | ||
1574 | } | ||
1575 | } | ||
1576 | |||
1577 | sfree(expand); | ||
1578 | sfree(where); | ||
1579 | |||
1580 | #ifdef GENERATION_DIAGNOSTICS | ||
1581 | printf("after expansion:\n"); | ||
1582 | display_grid(params3, grid2, NULL, TRUE); | ||
1583 | #endif | ||
1584 | /* | ||
1585 | * Transpose. | ||
1586 | */ | ||
1587 | params2->w = params3->h; | ||
1588 | params2->h = params3->w; | ||
1589 | sfree(grid); | ||
1590 | grid = snewn(params2->w * params2->h, int); | ||
1591 | for (x = 0; x < params2->w; x++) | ||
1592 | for (y = 0; y < params2->h; y++) { | ||
1593 | int idx1 = INDEX(params2, x, y); | ||
1594 | int idx2 = INDEX(params3, y, x); | ||
1595 | int tmp; | ||
1596 | |||
1597 | tmp = grid2[idx2]; | ||
1598 | tmp = (tmp % params3->w) * params2->w + (tmp / params3->w); | ||
1599 | grid[idx1] = tmp; | ||
1600 | } | ||
1601 | |||
1602 | sfree(grid2); | ||
1603 | |||
1604 | { | ||
1605 | int tmp; | ||
1606 | tmp = params->w; | ||
1607 | params->w = params->h; | ||
1608 | params->h = tmp; | ||
1609 | } | ||
1610 | |||
1611 | #ifdef GENERATION_DIAGNOSTICS | ||
1612 | printf("after transposition:\n"); | ||
1613 | display_grid(params2, grid, NULL, TRUE); | ||
1614 | #endif | ||
1615 | } | ||
1616 | |||
1617 | /* | ||
1618 | * Run the solver to narrow down the possible number | ||
1619 | * placements. | ||
1620 | */ | ||
1621 | { | ||
1622 | struct numberdata *nd; | ||
1623 | int nnumbers, i, ret; | ||
1624 | |||
1625 | /* Count the rectangles. */ | ||
1626 | nnumbers = 0; | ||
1627 | for (y = 0; y < params->h; y++) { | ||
1628 | for (x = 0; x < params->w; x++) { | ||
1629 | int idx = INDEX(params, x, y); | ||
1630 | if (index(params, grid, x, y) == idx) | ||
1631 | nnumbers++; | ||
1632 | } | ||
1633 | } | ||
1634 | |||
1635 | nd = snewn(nnumbers, struct numberdata); | ||
1636 | |||
1637 | /* Now set up each number's candidate position list. */ | ||
1638 | i = 0; | ||
1639 | for (y = 0; y < params->h; y++) { | ||
1640 | for (x = 0; x < params->w; x++) { | ||
1641 | int idx = INDEX(params, x, y); | ||
1642 | if (index(params, grid, x, y) == idx) { | ||
1643 | struct rect r = find_rect(params, grid, x, y); | ||
1644 | int j, k, m; | ||
1645 | |||
1646 | nd[i].area = r.w * r.h; | ||
1647 | nd[i].npoints = nd[i].area; | ||
1648 | nd[i].points = snewn(nd[i].npoints, struct point); | ||
1649 | m = 0; | ||
1650 | for (j = 0; j < r.h; j++) | ||
1651 | for (k = 0; k < r.w; k++) { | ||
1652 | nd[i].points[m].x = k + r.x; | ||
1653 | nd[i].points[m].y = j + r.y; | ||
1654 | m++; | ||
1655 | } | ||
1656 | assert(m == nd[i].npoints); | ||
1657 | |||
1658 | i++; | ||
1659 | } | ||
1660 | } | ||
1661 | } | ||
1662 | |||
1663 | if (params->unique) | ||
1664 | ret = rect_solver(params->w, params->h, nnumbers, nd, | ||
1665 | NULL, NULL, rs); | ||
1666 | else | ||
1667 | ret = 1; /* allow any number placement at all */ | ||
1668 | |||
1669 | if (ret == 1) { | ||
1670 | /* | ||
1671 | * Now place the numbers according to the solver's | ||
1672 | * recommendations. | ||
1673 | */ | ||
1674 | numbers = snewn(params->w * params->h, int); | ||
1675 | |||
1676 | for (y = 0; y < params->h; y++) | ||
1677 | for (x = 0; x < params->w; x++) { | ||
1678 | index(params, numbers, x, y) = 0; | ||
1679 | } | ||
1680 | |||
1681 | for (i = 0; i < nnumbers; i++) { | ||
1682 | int idx = random_upto(rs, nd[i].npoints); | ||
1683 | int x = nd[i].points[idx].x; | ||
1684 | int y = nd[i].points[idx].y; | ||
1685 | index(params,numbers,x,y) = nd[i].area; | ||
1686 | } | ||
1687 | } | ||
1688 | |||
1689 | /* | ||
1690 | * Clean up. | ||
1691 | */ | ||
1692 | for (i = 0; i < nnumbers; i++) | ||
1693 | sfree(nd[i].points); | ||
1694 | sfree(nd); | ||
1695 | |||
1696 | /* | ||
1697 | * If we've succeeded, then terminate the loop. | ||
1698 | */ | ||
1699 | if (ret == 1) | ||
1700 | break; | ||
1701 | } | ||
1702 | |||
1703 | /* | ||
1704 | * Give up and go round again. | ||
1705 | */ | ||
1706 | sfree(grid); | ||
1707 | } | ||
1708 | |||
1709 | /* | ||
1710 | * Store the solution in aux. | ||
1711 | */ | ||
1712 | { | ||
1713 | char *ai; | ||
1714 | int len; | ||
1715 | |||
1716 | len = 2 + (params->w-1)*params->h + (params->h-1)*params->w; | ||
1717 | ai = snewn(len, char); | ||
1718 | |||
1719 | ai[0] = 'S'; | ||
1720 | |||
1721 | p = ai+1; | ||
1722 | |||
1723 | for (y = 0; y < params->h; y++) | ||
1724 | for (x = 1; x < params->w; x++) | ||
1725 | *p++ = (index(params, grid, x, y) != | ||
1726 | index(params, grid, x-1, y) ? '1' : '0'); | ||
1727 | |||
1728 | for (y = 1; y < params->h; y++) | ||
1729 | for (x = 0; x < params->w; x++) | ||
1730 | *p++ = (index(params, grid, x, y) != | ||
1731 | index(params, grid, x, y-1) ? '1' : '0'); | ||
1732 | |||
1733 | assert(p - ai == len-1); | ||
1734 | *p = '\0'; | ||
1735 | |||
1736 | *aux = ai; | ||
1737 | } | ||
1738 | |||
1739 | #ifdef GENERATION_DIAGNOSTICS | ||
1740 | display_grid(params, grid, numbers, FALSE); | ||
1741 | #endif | ||
1742 | |||
1743 | desc = snewn(11 * params->w * params->h, char); | ||
1744 | p = desc; | ||
1745 | run = 0; | ||
1746 | for (i = 0; i <= params->w * params->h; i++) { | ||
1747 | int n = (i < params->w * params->h ? numbers[i] : -1); | ||
1748 | |||
1749 | if (!n) | ||
1750 | run++; | ||
1751 | else { | ||
1752 | if (run) { | ||
1753 | while (run > 0) { | ||
1754 | int c = 'a' - 1 + run; | ||
1755 | if (run > 26) | ||
1756 | c = 'z'; | ||
1757 | *p++ = c; | ||
1758 | run -= c - ('a' - 1); | ||
1759 | } | ||
1760 | } else { | ||
1761 | /* | ||
1762 | * If there's a number in the very top left or | ||
1763 | * bottom right, there's no point putting an | ||
1764 | * unnecessary _ before or after it. | ||
1765 | */ | ||
1766 | if (p > desc && n > 0) | ||
1767 | *p++ = '_'; | ||
1768 | } | ||
1769 | if (n > 0) | ||
1770 | p += sprintf(p, "%d", n); | ||
1771 | run = 0; | ||
1772 | } | ||
1773 | } | ||
1774 | *p = '\0'; | ||
1775 | |||
1776 | sfree(grid); | ||
1777 | sfree(numbers); | ||
1778 | |||
1779 | return desc; | ||
1780 | } | ||
1781 | |||
1782 | static char *validate_desc(const game_params *params, const char *desc) | ||
1783 | { | ||
1784 | int area = params->w * params->h; | ||
1785 | int squares = 0; | ||
1786 | |||
1787 | while (*desc) { | ||
1788 | int n = *desc++; | ||
1789 | if (n >= 'a' && n <= 'z') { | ||
1790 | squares += n - 'a' + 1; | ||
1791 | } else if (n == '_') { | ||
1792 | /* do nothing */; | ||
1793 | } else if (n > '0' && n <= '9') { | ||
1794 | squares++; | ||
1795 | while (*desc >= '0' && *desc <= '9') | ||
1796 | desc++; | ||
1797 | } else | ||
1798 | return "Invalid character in game description"; | ||
1799 | } | ||
1800 | |||
1801 | if (squares < area) | ||
1802 | return "Not enough data to fill grid"; | ||
1803 | |||
1804 | if (squares > area) | ||
1805 | return "Too much data to fit in grid"; | ||
1806 | |||
1807 | return NULL; | ||
1808 | } | ||
1809 | |||
1810 | static unsigned char *get_correct(game_state *state) | ||
1811 | { | ||
1812 | unsigned char *ret; | ||
1813 | int x, y; | ||
1814 | |||
1815 | ret = snewn(state->w * state->h, unsigned char); | ||
1816 | memset(ret, 0xFF, state->w * state->h); | ||
1817 | |||
1818 | for (x = 0; x < state->w; x++) | ||
1819 | for (y = 0; y < state->h; y++) | ||
1820 | if (index(state,ret,x,y) == 0xFF) { | ||
1821 | int rw, rh; | ||
1822 | int xx, yy; | ||
1823 | int num, area, valid; | ||
1824 | |||
1825 | /* | ||
1826 | * Find a rectangle starting at this point. | ||
1827 | */ | ||
1828 | rw = 1; | ||
1829 | while (x+rw < state->w && !vedge(state,x+rw,y)) | ||
1830 | rw++; | ||
1831 | rh = 1; | ||
1832 | while (y+rh < state->h && !hedge(state,x,y+rh)) | ||
1833 | rh++; | ||
1834 | |||
1835 | /* | ||
1836 | * We know what the dimensions of the rectangle | ||
1837 | * should be if it's there at all. Find out if we | ||
1838 | * really have a valid rectangle. | ||
1839 | */ | ||
1840 | valid = TRUE; | ||
1841 | /* Check the horizontal edges. */ | ||
1842 | for (xx = x; xx < x+rw; xx++) { | ||
1843 | for (yy = y; yy <= y+rh; yy++) { | ||
1844 | int e = !HRANGE(state,xx,yy) || hedge(state,xx,yy); | ||
1845 | int ec = (yy == y || yy == y+rh); | ||
1846 | if (e != ec) | ||
1847 | valid = FALSE; | ||
1848 | } | ||
1849 | } | ||
1850 | /* Check the vertical edges. */ | ||
1851 | for (yy = y; yy < y+rh; yy++) { | ||
1852 | for (xx = x; xx <= x+rw; xx++) { | ||
1853 | int e = !VRANGE(state,xx,yy) || vedge(state,xx,yy); | ||
1854 | int ec = (xx == x || xx == x+rw); | ||
1855 | if (e != ec) | ||
1856 | valid = FALSE; | ||
1857 | } | ||
1858 | } | ||
1859 | |||
1860 | /* | ||
1861 | * If this is not a valid rectangle with no other | ||
1862 | * edges inside it, we just mark this square as not | ||
1863 | * complete and proceed to the next square. | ||
1864 | */ | ||
1865 | if (!valid) { | ||
1866 | index(state, ret, x, y) = 0; | ||
1867 | continue; | ||
1868 | } | ||
1869 | |||
1870 | /* | ||
1871 | * We have a rectangle. Now see what its area is, | ||
1872 | * and how many numbers are in it. | ||
1873 | */ | ||
1874 | num = 0; | ||
1875 | area = 0; | ||
1876 | for (xx = x; xx < x+rw; xx++) { | ||
1877 | for (yy = y; yy < y+rh; yy++) { | ||
1878 | area++; | ||
1879 | if (grid(state,xx,yy)) { | ||
1880 | if (num > 0) | ||
1881 | valid = FALSE; /* two numbers */ | ||
1882 | num = grid(state,xx,yy); | ||
1883 | } | ||
1884 | } | ||
1885 | } | ||
1886 | if (num != area) | ||
1887 | valid = FALSE; | ||
1888 | |||
1889 | /* | ||
1890 | * Now fill in the whole rectangle based on the | ||
1891 | * value of `valid'. | ||
1892 | */ | ||
1893 | for (xx = x; xx < x+rw; xx++) { | ||
1894 | for (yy = y; yy < y+rh; yy++) { | ||
1895 | index(state, ret, xx, yy) = valid; | ||
1896 | } | ||
1897 | } | ||
1898 | } | ||
1899 | |||
1900 | return ret; | ||
1901 | } | ||
1902 | |||
1903 | static game_state *new_game(midend *me, const game_params *params, | ||
1904 | const char *desc) | ||
1905 | { | ||
1906 | game_state *state = snew(game_state); | ||
1907 | int x, y, i, area; | ||
1908 | |||
1909 | state->w = params->w; | ||
1910 | state->h = params->h; | ||
1911 | |||
1912 | area = state->w * state->h; | ||
1913 | |||
1914 | state->grid = snewn(area, int); | ||
1915 | state->vedge = snewn(area, unsigned char); | ||
1916 | state->hedge = snewn(area, unsigned char); | ||
1917 | state->completed = state->cheated = FALSE; | ||
1918 | |||
1919 | i = 0; | ||
1920 | while (*desc) { | ||
1921 | int n = *desc++; | ||
1922 | if (n >= 'a' && n <= 'z') { | ||
1923 | int run = n - 'a' + 1; | ||
1924 | assert(i + run <= area); | ||
1925 | while (run-- > 0) | ||
1926 | state->grid[i++] = 0; | ||
1927 | } else if (n == '_') { | ||
1928 | /* do nothing */; | ||
1929 | } else if (n > '0' && n <= '9') { | ||
1930 | assert(i < area); | ||
1931 | state->grid[i++] = atoi(desc-1); | ||
1932 | while (*desc >= '0' && *desc <= '9') | ||
1933 | desc++; | ||
1934 | } else { | ||
1935 | assert(!"We can't get here"); | ||
1936 | } | ||
1937 | } | ||
1938 | assert(i == area); | ||
1939 | |||
1940 | for (y = 0; y < state->h; y++) | ||
1941 | for (x = 0; x < state->w; x++) | ||
1942 | vedge(state,x,y) = hedge(state,x,y) = 0; | ||
1943 | |||
1944 | state->correct = get_correct(state); | ||
1945 | |||
1946 | return state; | ||
1947 | } | ||
1948 | |||
1949 | static game_state *dup_game(const game_state *state) | ||
1950 | { | ||
1951 | game_state *ret = snew(game_state); | ||
1952 | |||
1953 | ret->w = state->w; | ||
1954 | ret->h = state->h; | ||
1955 | |||
1956 | ret->vedge = snewn(state->w * state->h, unsigned char); | ||
1957 | ret->hedge = snewn(state->w * state->h, unsigned char); | ||
1958 | ret->grid = snewn(state->w * state->h, int); | ||
1959 | ret->correct = snewn(ret->w * ret->h, unsigned char); | ||
1960 | |||
1961 | ret->completed = state->completed; | ||
1962 | ret->cheated = state->cheated; | ||
1963 | |||
1964 | memcpy(ret->grid, state->grid, state->w * state->h * sizeof(int)); | ||
1965 | memcpy(ret->vedge, state->vedge, state->w*state->h*sizeof(unsigned char)); | ||
1966 | memcpy(ret->hedge, state->hedge, state->w*state->h*sizeof(unsigned char)); | ||
1967 | |||
1968 | memcpy(ret->correct, state->correct, state->w*state->h*sizeof(unsigned char)); | ||
1969 | |||
1970 | return ret; | ||
1971 | } | ||
1972 | |||
1973 | static void free_game(game_state *state) | ||
1974 | { | ||
1975 | sfree(state->grid); | ||
1976 | sfree(state->vedge); | ||
1977 | sfree(state->hedge); | ||
1978 | sfree(state->correct); | ||
1979 | sfree(state); | ||
1980 | } | ||
1981 | |||
1982 | static char *solve_game(const game_state *state, const game_state *currstate, | ||
1983 | const char *ai, char **error) | ||
1984 | { | ||
1985 | unsigned char *vedge, *hedge; | ||
1986 | int x, y, len; | ||
1987 | char *ret, *p; | ||
1988 | int i, j, n; | ||
1989 | struct numberdata *nd; | ||
1990 | |||
1991 | if (ai) | ||
1992 | return dupstr(ai); | ||
1993 | |||
1994 | /* | ||
1995 | * Attempt the in-built solver. | ||
1996 | */ | ||
1997 | |||
1998 | /* Set up each number's (very short) candidate position list. */ | ||
1999 | for (i = n = 0; i < state->h * state->w; i++) | ||
2000 | if (state->grid[i]) | ||
2001 | n++; | ||
2002 | |||
2003 | nd = snewn(n, struct numberdata); | ||
2004 | |||
2005 | for (i = j = 0; i < state->h * state->w; i++) | ||
2006 | if (state->grid[i]) { | ||
2007 | nd[j].area = state->grid[i]; | ||
2008 | nd[j].npoints = 1; | ||
2009 | nd[j].points = snewn(1, struct point); | ||
2010 | nd[j].points[0].x = i % state->w; | ||
2011 | nd[j].points[0].y = i / state->w; | ||
2012 | j++; | ||
2013 | } | ||
2014 | |||
2015 | assert(j == n); | ||
2016 | |||
2017 | vedge = snewn(state->w * state->h, unsigned char); | ||
2018 | hedge = snewn(state->w * state->h, unsigned char); | ||
2019 | memset(vedge, 0, state->w * state->h); | ||
2020 | memset(hedge, 0, state->w * state->h); | ||
2021 | |||
2022 | rect_solver(state->w, state->h, n, nd, hedge, vedge, NULL); | ||
2023 | |||
2024 | /* | ||
2025 | * Clean up. | ||
2026 | */ | ||
2027 | for (i = 0; i < n; i++) | ||
2028 | sfree(nd[i].points); | ||
2029 | sfree(nd); | ||
2030 | |||
2031 | len = 2 + (state->w-1)*state->h + (state->h-1)*state->w; | ||
2032 | ret = snewn(len, char); | ||
2033 | |||
2034 | p = ret; | ||
2035 | *p++ = 'S'; | ||
2036 | for (y = 0; y < state->h; y++) | ||
2037 | for (x = 1; x < state->w; x++) | ||
2038 | *p++ = vedge[y*state->w+x] ? '1' : '0'; | ||
2039 | for (y = 1; y < state->h; y++) | ||
2040 | for (x = 0; x < state->w; x++) | ||
2041 | *p++ = hedge[y*state->w+x] ? '1' : '0'; | ||
2042 | *p++ = '\0'; | ||
2043 | assert(p - ret == len); | ||
2044 | |||
2045 | sfree(vedge); | ||
2046 | sfree(hedge); | ||
2047 | |||
2048 | return ret; | ||
2049 | } | ||
2050 | |||
2051 | static int game_can_format_as_text_now(const game_params *params) | ||
2052 | { | ||
2053 | return TRUE; | ||
2054 | } | ||
2055 | |||
2056 | static char *game_text_format(const game_state *state) | ||
2057 | { | ||
2058 | char *ret, *p, buf[80]; | ||
2059 | int i, x, y, col, maxlen; | ||
2060 | |||
2061 | /* | ||
2062 | * First determine the number of spaces required to display a | ||
2063 | * number. We'll use at least two, because one looks a bit | ||
2064 | * silly. | ||
2065 | */ | ||
2066 | col = 2; | ||
2067 | for (i = 0; i < state->w * state->h; i++) { | ||
2068 | x = sprintf(buf, "%d", state->grid[i]); | ||
2069 | if (col < x) col = x; | ||
2070 | } | ||
2071 | |||
2072 | /* | ||
2073 | * Now we know the exact total size of the grid we're going to | ||
2074 | * produce: it's got 2*h+1 rows, each containing w lots of col, | ||
2075 | * w+1 boundary characters and a trailing newline. | ||
2076 | */ | ||
2077 | maxlen = (2*state->h+1) * (state->w * (col+1) + 2); | ||
2078 | |||
2079 | ret = snewn(maxlen+1, char); | ||
2080 | p = ret; | ||
2081 | |||
2082 | for (y = 0; y <= 2*state->h; y++) { | ||
2083 | for (x = 0; x <= 2*state->w; x++) { | ||
2084 | if (x & y & 1) { | ||
2085 | /* | ||
2086 | * Display a number. | ||
2087 | */ | ||
2088 | int v = grid(state, x/2, y/2); | ||
2089 | if (v) | ||
2090 | sprintf(buf, "%*d", col, v); | ||
2091 | else | ||
2092 | sprintf(buf, "%*s", col, ""); | ||
2093 | memcpy(p, buf, col); | ||
2094 | p += col; | ||
2095 | } else if (x & 1) { | ||
2096 | /* | ||
2097 | * Display a horizontal edge or nothing. | ||
2098 | */ | ||
2099 | int h = (y==0 || y==2*state->h ? 1 : | ||
2100 | HRANGE(state, x/2, y/2) && hedge(state, x/2, y/2)); | ||
2101 | int i; | ||
2102 | if (h) | ||
2103 | h = '-'; | ||
2104 | else | ||
2105 | h = ' '; | ||
2106 | for (i = 0; i < col; i++) | ||
2107 | *p++ = h; | ||
2108 | } else if (y & 1) { | ||
2109 | /* | ||
2110 | * Display a vertical edge or nothing. | ||
2111 | */ | ||
2112 | int v = (x==0 || x==2*state->w ? 1 : | ||
2113 | VRANGE(state, x/2, y/2) && vedge(state, x/2, y/2)); | ||
2114 | if (v) | ||
2115 | *p++ = '|'; | ||
2116 | else | ||
2117 | *p++ = ' '; | ||
2118 | } else { | ||
2119 | /* | ||
2120 | * Display a corner, or a vertical edge, or a | ||
2121 | * horizontal edge, or nothing. | ||
2122 | */ | ||
2123 | int hl = (y==0 || y==2*state->h ? 1 : | ||
2124 | HRANGE(state, (x-1)/2, y/2) && hedge(state, (x-1)/2, y/2)); | ||
2125 | int hr = (y==0 || y==2*state->h ? 1 : | ||
2126 | HRANGE(state, (x+1)/2, y/2) && hedge(state, (x+1)/2, y/2)); | ||
2127 | int vu = (x==0 || x==2*state->w ? 1 : | ||
2128 | VRANGE(state, x/2, (y-1)/2) && vedge(state, x/2, (y-1)/2)); | ||
2129 | int vd = (x==0 || x==2*state->w ? 1 : | ||
2130 | VRANGE(state, x/2, (y+1)/2) && vedge(state, x/2, (y+1)/2)); | ||
2131 | if (!hl && !hr && !vu && !vd) | ||
2132 | *p++ = ' '; | ||
2133 | else if (hl && hr && !vu && !vd) | ||
2134 | *p++ = '-'; | ||
2135 | else if (!hl && !hr && vu && vd) | ||
2136 | *p++ = '|'; | ||
2137 | else | ||
2138 | *p++ = '+'; | ||
2139 | } | ||
2140 | } | ||
2141 | *p++ = '\n'; | ||
2142 | } | ||
2143 | |||
2144 | assert(p - ret == maxlen); | ||
2145 | *p = '\0'; | ||
2146 | return ret; | ||
2147 | } | ||
2148 | |||
2149 | struct game_ui { | ||
2150 | /* | ||
2151 | * These coordinates are 2 times the obvious grid coordinates. | ||
2152 | * Hence, the top left of the grid is (0,0), the grid point to | ||
2153 | * the right of that is (2,0), the one _below that_ is (2,2) | ||
2154 | * and so on. This is so that we can specify a drag start point | ||
2155 | * on an edge (one odd coordinate) or in the middle of a square | ||
2156 | * (two odd coordinates) rather than always at a corner. | ||
2157 | * | ||
2158 | * -1,-1 means no drag is in progress. | ||
2159 | */ | ||
2160 | int drag_start_x; | ||
2161 | int drag_start_y; | ||
2162 | int drag_end_x; | ||
2163 | int drag_end_y; | ||
2164 | /* | ||
2165 | * This flag is set as soon as a dragging action moves the | ||
2166 | * mouse pointer away from its starting point, so that even if | ||
2167 | * the pointer _returns_ to its starting point the action is | ||
2168 | * treated as a small drag rather than a click. | ||
2169 | */ | ||
2170 | int dragged; | ||
2171 | /* This flag is set if we're doing an erase operation (i.e. | ||
2172 | * removing edges in the centre of the rectangle without altering | ||
2173 | * the outlines). | ||
2174 | */ | ||
2175 | int erasing; | ||
2176 | /* | ||
2177 | * These are the co-ordinates of the top-left and bottom-right squares | ||
2178 | * in the drag box, respectively, or -1 otherwise. | ||
2179 | */ | ||
2180 | int x1; | ||
2181 | int y1; | ||
2182 | int x2; | ||
2183 | int y2; | ||
2184 | /* | ||
2185 | * These are the coordinates of a cursor, whether it's visible, and | ||
2186 | * whether it was used to start a drag. | ||
2187 | */ | ||
2188 | int cur_x, cur_y, cur_visible, cur_dragging; | ||
2189 | }; | ||
2190 | |||
2191 | static void reset_ui(game_ui *ui) | ||
2192 | { | ||
2193 | ui->drag_start_x = -1; | ||
2194 | ui->drag_start_y = -1; | ||
2195 | ui->drag_end_x = -1; | ||
2196 | ui->drag_end_y = -1; | ||
2197 | ui->x1 = -1; | ||
2198 | ui->y1 = -1; | ||
2199 | ui->x2 = -1; | ||
2200 | ui->y2 = -1; | ||
2201 | ui->dragged = FALSE; | ||
2202 | } | ||
2203 | |||
2204 | static game_ui *new_ui(const game_state *state) | ||
2205 | { | ||
2206 | game_ui *ui = snew(game_ui); | ||
2207 | reset_ui(ui); | ||
2208 | ui->erasing = FALSE; | ||
2209 | ui->cur_x = ui->cur_y = ui->cur_visible = ui->cur_dragging = 0; | ||
2210 | return ui; | ||
2211 | } | ||
2212 | |||
2213 | static void free_ui(game_ui *ui) | ||
2214 | { | ||
2215 | sfree(ui); | ||
2216 | } | ||
2217 | |||
2218 | static char *encode_ui(const game_ui *ui) | ||
2219 | { | ||
2220 | return NULL; | ||
2221 | } | ||
2222 | |||
2223 | static void decode_ui(game_ui *ui, const char *encoding) | ||
2224 | { | ||
2225 | } | ||
2226 | |||
2227 | static void coord_round(float x, float y, int *xr, int *yr) | ||
2228 | { | ||
2229 | float xs, ys, xv, yv, dx, dy, dist; | ||
2230 | |||
2231 | /* | ||
2232 | * Find the nearest square-centre. | ||
2233 | */ | ||
2234 | xs = (float)floor(x) + 0.5F; | ||
2235 | ys = (float)floor(y) + 0.5F; | ||
2236 | |||
2237 | /* | ||
2238 | * And find the nearest grid vertex. | ||
2239 | */ | ||
2240 | xv = (float)floor(x + 0.5F); | ||
2241 | yv = (float)floor(y + 0.5F); | ||
2242 | |||
2243 | /* | ||
2244 | * We allocate clicks in parts of the grid square to either | ||
2245 | * corners, edges or square centres, as follows: | ||
2246 | * | ||
2247 | * +--+--------+--+ | ||
2248 | * | | | | | ||
2249 | * +--+ +--+ | ||
2250 | * | `. ,' | | ||
2251 | * | +--+ | | ||
2252 | * | | | | | ||
2253 | * | +--+ | | ||
2254 | * | ,' `. | | ||
2255 | * +--+ +--+ | ||
2256 | * | | | | | ||
2257 | * +--+--------+--+ | ||
2258 | * | ||
2259 | * (Not to scale!) | ||
2260 | * | ||
2261 | * In other words: we measure the square distance (i.e. | ||
2262 | * max(dx,dy)) from the click to the nearest corner, and if | ||
2263 | * it's within CORNER_TOLERANCE then we return a corner click. | ||
2264 | * We measure the square distance from the click to the nearest | ||
2265 | * centre, and if that's within CENTRE_TOLERANCE we return a | ||
2266 | * centre click. Failing that, we find which of the two edge | ||
2267 | * centres is nearer to the click and return that edge. | ||
2268 | */ | ||
2269 | |||
2270 | /* | ||
2271 | * Check for corner click. | ||
2272 | */ | ||
2273 | dx = (float)fabs(x - xv); | ||
2274 | dy = (float)fabs(y - yv); | ||
2275 | dist = (dx > dy ? dx : dy); | ||
2276 | if (dist < CORNER_TOLERANCE) { | ||
2277 | *xr = 2 * (int)xv; | ||
2278 | *yr = 2 * (int)yv; | ||
2279 | } else { | ||
2280 | /* | ||
2281 | * Check for centre click. | ||
2282 | */ | ||
2283 | dx = (float)fabs(x - xs); | ||
2284 | dy = (float)fabs(y - ys); | ||
2285 | dist = (dx > dy ? dx : dy); | ||
2286 | if (dist < CENTRE_TOLERANCE) { | ||
2287 | *xr = 1 + 2 * (int)xs; | ||
2288 | *yr = 1 + 2 * (int)ys; | ||
2289 | } else { | ||
2290 | /* | ||
2291 | * Failing both of those, see which edge we're closer to. | ||
2292 | * Conveniently, this is simply done by testing the relative | ||
2293 | * magnitude of dx and dy (which are currently distances from | ||
2294 | * the square centre). | ||
2295 | */ | ||
2296 | if (dx > dy) { | ||
2297 | /* Vertical edge: x-coord of corner, | ||
2298 | * y-coord of square centre. */ | ||
2299 | *xr = 2 * (int)xv; | ||
2300 | *yr = 1 + 2 * (int)floor(ys); | ||
2301 | } else { | ||
2302 | /* Horizontal edge: x-coord of square centre, | ||
2303 | * y-coord of corner. */ | ||
2304 | *xr = 1 + 2 * (int)floor(xs); | ||
2305 | *yr = 2 * (int)yv; | ||
2306 | } | ||
2307 | } | ||
2308 | } | ||
2309 | } | ||
2310 | |||
2311 | /* | ||
2312 | * Returns TRUE if it has made any change to the grid. | ||
2313 | */ | ||
2314 | static int grid_draw_rect(const game_state *state, | ||
2315 | unsigned char *hedge, unsigned char *vedge, | ||
2316 | int c, int really, int outline, | ||
2317 | int x1, int y1, int x2, int y2) | ||
2318 | { | ||
2319 | int x, y; | ||
2320 | int changed = FALSE; | ||
2321 | |||
2322 | /* | ||
2323 | * Draw horizontal edges of rectangles. | ||
2324 | */ | ||
2325 | for (x = x1; x < x2; x++) | ||
2326 | for (y = y1; y <= y2; y++) | ||
2327 | if (HRANGE(state,x,y)) { | ||
2328 | int val = index(state,hedge,x,y); | ||
2329 | if (y == y1 || y == y2) { | ||
2330 | if (!outline) continue; | ||
2331 | val = c; | ||
2332 | } else if (c == 1) | ||
2333 | val = 0; | ||
2334 | changed = changed || (index(state,hedge,x,y) != val); | ||
2335 | if (really) | ||
2336 | index(state,hedge,x,y) = val; | ||
2337 | } | ||
2338 | |||
2339 | /* | ||
2340 | * Draw vertical edges of rectangles. | ||
2341 | */ | ||
2342 | for (y = y1; y < y2; y++) | ||
2343 | for (x = x1; x <= x2; x++) | ||
2344 | if (VRANGE(state,x,y)) { | ||
2345 | int val = index(state,vedge,x,y); | ||
2346 | if (x == x1 || x == x2) { | ||
2347 | if (!outline) continue; | ||
2348 | val = c; | ||
2349 | } else if (c == 1) | ||
2350 | val = 0; | ||
2351 | changed = changed || (index(state,vedge,x,y) != val); | ||
2352 | if (really) | ||
2353 | index(state,vedge,x,y) = val; | ||
2354 | } | ||
2355 | |||
2356 | return changed; | ||
2357 | } | ||
2358 | |||
2359 | static int ui_draw_rect(const game_state *state, const game_ui *ui, | ||
2360 | unsigned char *hedge, unsigned char *vedge, int c, | ||
2361 | int really, int outline) | ||
2362 | { | ||
2363 | return grid_draw_rect(state, hedge, vedge, c, really, outline, | ||
2364 | ui->x1, ui->y1, ui->x2, ui->y2); | ||
2365 | } | ||
2366 | |||
2367 | static void game_changed_state(game_ui *ui, const game_state *oldstate, | ||
2368 | const game_state *newstate) | ||
2369 | { | ||
2370 | } | ||
2371 | |||
2372 | struct game_drawstate { | ||
2373 | int started; | ||
2374 | int w, h, tilesize; | ||
2375 | unsigned long *visible; | ||
2376 | }; | ||
2377 | |||
2378 | static char *interpret_move(const game_state *from, game_ui *ui, | ||
2379 | const game_drawstate *ds, | ||
2380 | int x, int y, int button) | ||
2381 | { | ||
2382 | int xc, yc; | ||
2383 | int startdrag = FALSE, enddrag = FALSE, active = FALSE, erasing = FALSE; | ||
2384 | char buf[80], *ret; | ||
2385 | |||
2386 | button &= ~MOD_MASK; | ||
2387 | |||
2388 | coord_round(FROMCOORD((float)x), FROMCOORD((float)y), &xc, &yc); | ||
2389 | |||
2390 | if (button == LEFT_BUTTON || button == RIGHT_BUTTON) { | ||
2391 | if (ui->drag_start_x >= 0 && ui->cur_dragging) | ||
2392 | reset_ui(ui); /* cancel keyboard dragging */ | ||
2393 | startdrag = TRUE; | ||
2394 | ui->cur_visible = ui->cur_dragging = FALSE; | ||
2395 | active = TRUE; | ||
2396 | erasing = (button == RIGHT_BUTTON); | ||
2397 | } else if (button == LEFT_RELEASE || button == RIGHT_RELEASE) { | ||
2398 | /* We assert we should have had a LEFT_BUTTON first. */ | ||
2399 | if (ui->cur_visible) { | ||
2400 | ui->cur_visible = FALSE; | ||
2401 | active = TRUE; | ||
2402 | } | ||
2403 | assert(!ui->cur_dragging); | ||
2404 | enddrag = TRUE; | ||
2405 | erasing = (button == RIGHT_RELEASE); | ||
2406 | } else if (IS_CURSOR_MOVE(button)) { | ||
2407 | move_cursor(button, &ui->cur_x, &ui->cur_y, from->w, from->h, 0); | ||
2408 | ui->cur_visible = TRUE; | ||
2409 | active = TRUE; | ||
2410 | if (!ui->cur_dragging) return ""; | ||
2411 | coord_round((float)ui->cur_x + 0.5F, (float)ui->cur_y + 0.5F, &xc, &yc); | ||
2412 | } else if (IS_CURSOR_SELECT(button)) { | ||
2413 | if (ui->drag_start_x >= 0 && !ui->cur_dragging) { | ||
2414 | /* | ||
2415 | * If a mouse drag is in progress, ignore attempts to | ||
2416 | * start a keyboard one. | ||
2417 | */ | ||
2418 | return NULL; | ||
2419 | } | ||
2420 | if (!ui->cur_visible) { | ||
2421 | assert(!ui->cur_dragging); | ||
2422 | ui->cur_visible = TRUE; | ||
2423 | return ""; | ||
2424 | } | ||
2425 | coord_round((float)ui->cur_x + 0.5F, (float)ui->cur_y + 0.5F, &xc, &yc); | ||
2426 | erasing = (button == CURSOR_SELECT2); | ||
2427 | if (ui->cur_dragging) { | ||
2428 | ui->cur_dragging = FALSE; | ||
2429 | enddrag = TRUE; | ||
2430 | active = TRUE; | ||
2431 | } else { | ||
2432 | ui->cur_dragging = TRUE; | ||
2433 | startdrag = TRUE; | ||
2434 | active = TRUE; | ||
2435 | } | ||
2436 | } else if (button == '\b' || button == 27) { | ||
2437 | if (!ui->cur_dragging) { | ||
2438 | ui->cur_visible = FALSE; | ||
2439 | } else { | ||
2440 | assert(ui->cur_visible); | ||
2441 | reset_ui(ui); /* cancel keyboard dragging */ | ||
2442 | ui->cur_dragging = FALSE; | ||
2443 | } | ||
2444 | return ""; | ||
2445 | } else if (button != LEFT_DRAG && button != RIGHT_DRAG) { | ||
2446 | return NULL; | ||
2447 | } | ||
2448 | |||
2449 | if (startdrag && | ||
2450 | xc >= 0 && xc <= 2*from->w && | ||
2451 | yc >= 0 && yc <= 2*from->h) { | ||
2452 | |||
2453 | ui->drag_start_x = xc; | ||
2454 | ui->drag_start_y = yc; | ||
2455 | ui->drag_end_x = -1; | ||
2456 | ui->drag_end_y = -1; | ||
2457 | ui->dragged = FALSE; | ||
2458 | ui->erasing = erasing; | ||
2459 | active = TRUE; | ||
2460 | } | ||
2461 | |||
2462 | if (ui->drag_start_x >= 0 && | ||
2463 | (xc != ui->drag_end_x || yc != ui->drag_end_y)) { | ||
2464 | int t; | ||
2465 | |||
2466 | if (ui->drag_end_x != -1 && ui->drag_end_y != -1) | ||
2467 | ui->dragged = TRUE; | ||
2468 | ui->drag_end_x = xc; | ||
2469 | ui->drag_end_y = yc; | ||
2470 | active = TRUE; | ||
2471 | |||
2472 | if (xc >= 0 && xc <= 2*from->w && | ||
2473 | yc >= 0 && yc <= 2*from->h) { | ||
2474 | ui->x1 = ui->drag_start_x; | ||
2475 | ui->x2 = ui->drag_end_x; | ||
2476 | if (ui->x2 < ui->x1) { t = ui->x1; ui->x1 = ui->x2; ui->x2 = t; } | ||
2477 | |||
2478 | ui->y1 = ui->drag_start_y; | ||
2479 | ui->y2 = ui->drag_end_y; | ||
2480 | if (ui->y2 < ui->y1) { t = ui->y1; ui->y1 = ui->y2; ui->y2 = t; } | ||
2481 | |||
2482 | ui->x1 = ui->x1 / 2; /* rounds down */ | ||
2483 | ui->x2 = (ui->x2+1) / 2; /* rounds up */ | ||
2484 | ui->y1 = ui->y1 / 2; /* rounds down */ | ||
2485 | ui->y2 = (ui->y2+1) / 2; /* rounds up */ | ||
2486 | } else { | ||
2487 | ui->x1 = -1; | ||
2488 | ui->y1 = -1; | ||
2489 | ui->x2 = -1; | ||
2490 | ui->y2 = -1; | ||
2491 | } | ||
2492 | } | ||
2493 | |||
2494 | ret = NULL; | ||
2495 | |||
2496 | if (enddrag && (ui->drag_start_x >= 0)) { | ||
2497 | if (xc >= 0 && xc <= 2*from->w && | ||
2498 | yc >= 0 && yc <= 2*from->h && | ||
2499 | erasing == ui->erasing) { | ||
2500 | |||
2501 | if (ui->dragged) { | ||
2502 | if (ui_draw_rect(from, ui, from->hedge, | ||
2503 | from->vedge, 1, FALSE, !ui->erasing)) { | ||
2504 | sprintf(buf, "%c%d,%d,%d,%d", | ||
2505 | (int)(ui->erasing ? 'E' : 'R'), | ||
2506 | ui->x1, ui->y1, ui->x2 - ui->x1, ui->y2 - ui->y1); | ||
2507 | ret = dupstr(buf); | ||
2508 | } | ||
2509 | } else { | ||
2510 | if ((xc & 1) && !(yc & 1) && HRANGE(from,xc/2,yc/2)) { | ||
2511 | sprintf(buf, "H%d,%d", xc/2, yc/2); | ||
2512 | ret = dupstr(buf); | ||
2513 | } | ||
2514 | if ((yc & 1) && !(xc & 1) && VRANGE(from,xc/2,yc/2)) { | ||
2515 | sprintf(buf, "V%d,%d", xc/2, yc/2); | ||
2516 | ret = dupstr(buf); | ||
2517 | } | ||
2518 | } | ||
2519 | } | ||
2520 | |||
2521 | reset_ui(ui); | ||
2522 | active = TRUE; | ||
2523 | } | ||
2524 | |||
2525 | if (ret) | ||
2526 | return ret; /* a move has been made */ | ||
2527 | else if (active) | ||
2528 | return ""; /* UI activity has occurred */ | ||
2529 | else | ||
2530 | return NULL; | ||
2531 | } | ||
2532 | |||
2533 | static game_state *execute_move(const game_state *from, const char *move) | ||
2534 | { | ||
2535 | game_state *ret; | ||
2536 | int x1, y1, x2, y2, mode; | ||
2537 | |||
2538 | if (move[0] == 'S') { | ||
2539 | const char *p = move+1; | ||
2540 | int x, y; | ||
2541 | |||
2542 | ret = dup_game(from); | ||
2543 | ret->cheated = TRUE; | ||
2544 | |||
2545 | for (y = 0; y < ret->h; y++) | ||
2546 | for (x = 1; x < ret->w; x++) { | ||
2547 | vedge(ret, x, y) = (*p == '1'); | ||
2548 | if (*p) p++; | ||
2549 | } | ||
2550 | for (y = 1; y < ret->h; y++) | ||
2551 | for (x = 0; x < ret->w; x++) { | ||
2552 | hedge(ret, x, y) = (*p == '1'); | ||
2553 | if (*p) p++; | ||
2554 | } | ||
2555 | |||
2556 | sfree(ret->correct); | ||
2557 | ret->correct = get_correct(ret); | ||
2558 | |||
2559 | return ret; | ||
2560 | |||
2561 | } else if ((move[0] == 'R' || move[0] == 'E') && | ||
2562 | sscanf(move+1, "%d,%d,%d,%d", &x1, &y1, &x2, &y2) == 4 && | ||
2563 | x1 >= 0 && x2 >= 0 && x1+x2 <= from->w && | ||
2564 | y1 >= 0 && y2 >= 0 && y1+y2 <= from->h) { | ||
2565 | x2 += x1; | ||
2566 | y2 += y1; | ||
2567 | mode = move[0]; | ||
2568 | } else if ((move[0] == 'H' || move[0] == 'V') && | ||
2569 | sscanf(move+1, "%d,%d", &x1, &y1) == 2 && | ||
2570 | (move[0] == 'H' ? HRANGE(from, x1, y1) : | ||
2571 | VRANGE(from, x1, y1))) { | ||
2572 | mode = move[0]; | ||
2573 | } else | ||
2574 | return NULL; /* can't parse move string */ | ||
2575 | |||
2576 | ret = dup_game(from); | ||
2577 | |||
2578 | if (mode == 'R' || mode == 'E') { | ||
2579 | grid_draw_rect(ret, ret->hedge, ret->vedge, 1, TRUE, | ||
2580 | mode == 'R', x1, y1, x2, y2); | ||
2581 | } else if (mode == 'H') { | ||
2582 | hedge(ret,x1,y1) = !hedge(ret,x1,y1); | ||
2583 | } else if (mode == 'V') { | ||
2584 | vedge(ret,x1,y1) = !vedge(ret,x1,y1); | ||
2585 | } | ||
2586 | |||
2587 | sfree(ret->correct); | ||
2588 | ret->correct = get_correct(ret); | ||
2589 | |||
2590 | /* | ||
2591 | * We've made a real change to the grid. Check to see | ||
2592 | * if the game has been completed. | ||
2593 | */ | ||
2594 | if (!ret->completed) { | ||
2595 | int x, y, ok; | ||
2596 | |||
2597 | ok = TRUE; | ||
2598 | for (x = 0; x < ret->w; x++) | ||
2599 | for (y = 0; y < ret->h; y++) | ||
2600 | if (!index(ret, ret->correct, x, y)) | ||
2601 | ok = FALSE; | ||
2602 | |||
2603 | if (ok) | ||
2604 | ret->completed = TRUE; | ||
2605 | } | ||
2606 | |||
2607 | return ret; | ||
2608 | } | ||
2609 | |||
2610 | /* ---------------------------------------------------------------------- | ||
2611 | * Drawing routines. | ||
2612 | */ | ||
2613 | |||
2614 | #define CORRECT (1L<<16) | ||
2615 | #define CURSOR (1L<<17) | ||
2616 | |||
2617 | #define COLOUR(k) ( (k)==1 ? COL_LINE : (k)==2 ? COL_DRAG : COL_DRAGERASE ) | ||
2618 | #define MAX4(x,y,z,w) ( max(max(x,y),max(z,w)) ) | ||
2619 | |||
2620 | static void game_compute_size(const game_params *params, int tilesize, | ||
2621 | int *x, int *y) | ||
2622 | { | ||
2623 | /* Ick: fake up `ds->tilesize' for macro expansion purposes */ | ||
2624 | struct { int tilesize; } ads, *ds = &ads; | ||
2625 | ads.tilesize = tilesize; | ||
2626 | |||
2627 | *x = params->w * TILE_SIZE + 2*BORDER + 1; | ||
2628 | *y = params->h * TILE_SIZE + 2*BORDER + 1; | ||
2629 | } | ||
2630 | |||
2631 | static void game_set_size(drawing *dr, game_drawstate *ds, | ||
2632 | const game_params *params, int tilesize) | ||
2633 | { | ||
2634 | ds->tilesize = tilesize; | ||
2635 | } | ||
2636 | |||
2637 | static float *game_colours(frontend *fe, int *ncolours) | ||
2638 | { | ||
2639 | float *ret = snewn(3 * NCOLOURS, float); | ||
2640 | |||
2641 | frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]); | ||
2642 | |||
2643 | ret[COL_GRID * 3 + 0] = 0.5F * ret[COL_BACKGROUND * 3 + 0]; | ||
2644 | ret[COL_GRID * 3 + 1] = 0.5F * ret[COL_BACKGROUND * 3 + 1]; | ||
2645 | ret[COL_GRID * 3 + 2] = 0.5F * ret[COL_BACKGROUND * 3 + 2]; | ||
2646 | |||
2647 | ret[COL_DRAG * 3 + 0] = 1.0F; | ||
2648 | ret[COL_DRAG * 3 + 1] = 0.0F; | ||
2649 | ret[COL_DRAG * 3 + 2] = 0.0F; | ||
2650 | |||
2651 | ret[COL_DRAGERASE * 3 + 0] = 0.2F; | ||
2652 | ret[COL_DRAGERASE * 3 + 1] = 0.2F; | ||
2653 | ret[COL_DRAGERASE * 3 + 2] = 1.0F; | ||
2654 | |||
2655 | ret[COL_CORRECT * 3 + 0] = 0.75F * ret[COL_BACKGROUND * 3 + 0]; | ||
2656 | ret[COL_CORRECT * 3 + 1] = 0.75F * ret[COL_BACKGROUND * 3 + 1]; | ||
2657 | ret[COL_CORRECT * 3 + 2] = 0.75F * ret[COL_BACKGROUND * 3 + 2]; | ||
2658 | |||
2659 | ret[COL_LINE * 3 + 0] = 0.0F; | ||
2660 | ret[COL_LINE * 3 + 1] = 0.0F; | ||
2661 | ret[COL_LINE * 3 + 2] = 0.0F; | ||
2662 | |||
2663 | ret[COL_TEXT * 3 + 0] = 0.0F; | ||
2664 | ret[COL_TEXT * 3 + 1] = 0.0F; | ||
2665 | ret[COL_TEXT * 3 + 2] = 0.0F; | ||
2666 | |||
2667 | ret[COL_CURSOR * 3 + 0] = 1.0F; | ||
2668 | ret[COL_CURSOR * 3 + 1] = 0.5F; | ||
2669 | ret[COL_CURSOR * 3 + 2] = 0.5F; | ||
2670 | |||
2671 | *ncolours = NCOLOURS; | ||
2672 | return ret; | ||
2673 | } | ||
2674 | |||
2675 | static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state) | ||
2676 | { | ||
2677 | struct game_drawstate *ds = snew(struct game_drawstate); | ||
2678 | int i; | ||
2679 | |||
2680 | ds->started = FALSE; | ||
2681 | ds->w = state->w; | ||
2682 | ds->h = state->h; | ||
2683 | ds->visible = snewn(ds->w * ds->h, unsigned long); | ||
2684 | ds->tilesize = 0; /* not decided yet */ | ||
2685 | for (i = 0; i < ds->w * ds->h; i++) | ||
2686 | ds->visible[i] = 0xFFFF; | ||
2687 | |||
2688 | return ds; | ||
2689 | } | ||
2690 | |||
2691 | static void game_free_drawstate(drawing *dr, game_drawstate *ds) | ||
2692 | { | ||
2693 | sfree(ds->visible); | ||
2694 | sfree(ds); | ||
2695 | } | ||
2696 | |||
2697 | static void draw_tile(drawing *dr, game_drawstate *ds, const game_state *state, | ||
2698 | int x, int y, unsigned char *hedge, unsigned char *vedge, | ||
2699 | unsigned char *corners, unsigned long bgflags) | ||
2700 | { | ||
2701 | int cx = COORD(x), cy = COORD(y); | ||
2702 | char str[80]; | ||
2703 | |||
2704 | draw_rect(dr, cx, cy, TILE_SIZE+1, TILE_SIZE+1, COL_GRID); | ||
2705 | draw_rect(dr, cx+1, cy+1, TILE_SIZE-1, TILE_SIZE-1, | ||
2706 | (bgflags & CURSOR) ? COL_CURSOR : | ||
2707 | (bgflags & CORRECT) ? COL_CORRECT : COL_BACKGROUND); | ||
2708 | |||
2709 | if (grid(state,x,y)) { | ||
2710 | sprintf(str, "%d", grid(state,x,y)); | ||
2711 | draw_text(dr, cx+TILE_SIZE/2, cy+TILE_SIZE/2, FONT_VARIABLE, | ||
2712 | TILE_SIZE/2, ALIGN_HCENTRE | ALIGN_VCENTRE, COL_TEXT, str); | ||
2713 | } | ||
2714 | |||
2715 | /* | ||
2716 | * Draw edges. | ||
2717 | */ | ||
2718 | if (!HRANGE(state,x,y) || index(state,hedge,x,y)) | ||
2719 | draw_rect(dr, cx, cy, TILE_SIZE+1, 2, | ||
2720 | HRANGE(state,x,y) ? COLOUR(index(state,hedge,x,y)) : | ||
2721 | COL_LINE); | ||
2722 | if (!HRANGE(state,x,y+1) || index(state,hedge,x,y+1)) | ||
2723 | draw_rect(dr, cx, cy+TILE_SIZE-1, TILE_SIZE+1, 2, | ||
2724 | HRANGE(state,x,y+1) ? COLOUR(index(state,hedge,x,y+1)) : | ||
2725 | COL_LINE); | ||
2726 | if (!VRANGE(state,x,y) || index(state,vedge,x,y)) | ||
2727 | draw_rect(dr, cx, cy, 2, TILE_SIZE+1, | ||
2728 | VRANGE(state,x,y) ? COLOUR(index(state,vedge,x,y)) : | ||
2729 | COL_LINE); | ||
2730 | if (!VRANGE(state,x+1,y) || index(state,vedge,x+1,y)) | ||
2731 | draw_rect(dr, cx+TILE_SIZE-1, cy, 2, TILE_SIZE+1, | ||
2732 | VRANGE(state,x+1,y) ? COLOUR(index(state,vedge,x+1,y)) : | ||
2733 | COL_LINE); | ||
2734 | |||
2735 | /* | ||
2736 | * Draw corners. | ||
2737 | */ | ||
2738 | if (index(state,corners,x,y)) | ||
2739 | draw_rect(dr, cx, cy, 2, 2, | ||
2740 | COLOUR(index(state,corners,x,y))); | ||
2741 | if (x+1 < state->w && index(state,corners,x+1,y)) | ||
2742 | draw_rect(dr, cx+TILE_SIZE-1, cy, 2, 2, | ||
2743 | COLOUR(index(state,corners,x+1,y))); | ||
2744 | if (y+1 < state->h && index(state,corners,x,y+1)) | ||
2745 | draw_rect(dr, cx, cy+TILE_SIZE-1, 2, 2, | ||
2746 | COLOUR(index(state,corners,x,y+1))); | ||
2747 | if (x+1 < state->w && y+1 < state->h && index(state,corners,x+1,y+1)) | ||
2748 | draw_rect(dr, cx+TILE_SIZE-1, cy+TILE_SIZE-1, 2, 2, | ||
2749 | COLOUR(index(state,corners,x+1,y+1))); | ||
2750 | |||
2751 | draw_update(dr, cx, cy, TILE_SIZE+1, TILE_SIZE+1); | ||
2752 | } | ||
2753 | |||
2754 | static void game_redraw(drawing *dr, game_drawstate *ds, | ||
2755 | const game_state *oldstate, const game_state *state, | ||
2756 | int dir, const game_ui *ui, | ||
2757 | float animtime, float flashtime) | ||
2758 | { | ||
2759 | int x, y; | ||
2760 | unsigned char *hedge, *vedge, *corners; | ||
2761 | |||
2762 | if (ui->dragged) { | ||
2763 | hedge = snewn(state->w*state->h, unsigned char); | ||
2764 | vedge = snewn(state->w*state->h, unsigned char); | ||
2765 | memcpy(hedge, state->hedge, state->w*state->h); | ||
2766 | memcpy(vedge, state->vedge, state->w*state->h); | ||
2767 | ui_draw_rect(state, ui, hedge, vedge, ui->erasing ? 3 : 2, TRUE, TRUE); | ||
2768 | } else { | ||
2769 | hedge = state->hedge; | ||
2770 | vedge = state->vedge; | ||
2771 | } | ||
2772 | |||
2773 | corners = snewn(state->w * state->h, unsigned char); | ||
2774 | memset(corners, 0, state->w * state->h); | ||
2775 | for (x = 0; x < state->w; x++) | ||
2776 | for (y = 0; y < state->h; y++) { | ||
2777 | if (x > 0) { | ||
2778 | int e = index(state, vedge, x, y); | ||
2779 | if (index(state,corners,x,y) < e) | ||
2780 | index(state,corners,x,y) = e; | ||
2781 | if (y+1 < state->h && | ||
2782 | index(state,corners,x,y+1) < e) | ||
2783 | index(state,corners,x,y+1) = e; | ||
2784 | } | ||
2785 | if (y > 0) { | ||
2786 | int e = index(state, hedge, x, y); | ||
2787 | if (index(state,corners,x,y) < e) | ||
2788 | index(state,corners,x,y) = e; | ||
2789 | if (x+1 < state->w && | ||
2790 | index(state,corners,x+1,y) < e) | ||
2791 | index(state,corners,x+1,y) = e; | ||
2792 | } | ||
2793 | } | ||
2794 | |||
2795 | if (!ds->started) { | ||
2796 | draw_rect(dr, 0, 0, | ||
2797 | state->w * TILE_SIZE + 2*BORDER + 1, | ||
2798 | state->h * TILE_SIZE + 2*BORDER + 1, COL_BACKGROUND); | ||
2799 | draw_rect(dr, COORD(0)-1, COORD(0)-1, | ||
2800 | ds->w*TILE_SIZE+3, ds->h*TILE_SIZE+3, COL_LINE); | ||
2801 | ds->started = TRUE; | ||
2802 | draw_update(dr, 0, 0, | ||
2803 | state->w * TILE_SIZE + 2*BORDER + 1, | ||
2804 | state->h * TILE_SIZE + 2*BORDER + 1); | ||
2805 | } | ||
2806 | |||
2807 | for (x = 0; x < state->w; x++) | ||
2808 | for (y = 0; y < state->h; y++) { | ||
2809 | unsigned long c = 0; | ||
2810 | |||
2811 | if (HRANGE(state,x,y)) | ||
2812 | c |= index(state,hedge,x,y); | ||
2813 | if (HRANGE(state,x,y+1)) | ||
2814 | c |= index(state,hedge,x,y+1) << 2; | ||
2815 | if (VRANGE(state,x,y)) | ||
2816 | c |= index(state,vedge,x,y) << 4; | ||
2817 | if (VRANGE(state,x+1,y)) | ||
2818 | c |= index(state,vedge,x+1,y) << 6; | ||
2819 | c |= index(state,corners,x,y) << 8; | ||
2820 | if (x+1 < state->w) | ||
2821 | c |= index(state,corners,x+1,y) << 10; | ||
2822 | if (y+1 < state->h) | ||
2823 | c |= index(state,corners,x,y+1) << 12; | ||
2824 | if (x+1 < state->w && y+1 < state->h) | ||
2825 | /* cast to prevent 2<<14 sign-extending on promotion to long */ | ||
2826 | c |= (unsigned long)index(state,corners,x+1,y+1) << 14; | ||
2827 | if (index(state, state->correct, x, y) && !flashtime) | ||
2828 | c |= CORRECT; | ||
2829 | if (ui->cur_visible && ui->cur_x == x && ui->cur_y == y) | ||
2830 | c |= CURSOR; | ||
2831 | |||
2832 | if (index(ds,ds->visible,x,y) != c) { | ||
2833 | draw_tile(dr, ds, state, x, y, hedge, vedge, corners, | ||
2834 | (c & (CORRECT|CURSOR)) ); | ||
2835 | index(ds,ds->visible,x,y) = c; | ||
2836 | } | ||
2837 | } | ||
2838 | |||
2839 | { | ||
2840 | char buf[256]; | ||
2841 | |||
2842 | if (ui->dragged && | ||
2843 | ui->x1 >= 0 && ui->y1 >= 0 && | ||
2844 | ui->x2 >= 0 && ui->y2 >= 0) { | ||
2845 | sprintf(buf, "%dx%d ", | ||
2846 | ui->x2-ui->x1, | ||
2847 | ui->y2-ui->y1); | ||
2848 | } else { | ||
2849 | buf[0] = '\0'; | ||
2850 | } | ||
2851 | |||
2852 | if (state->cheated) | ||
2853 | strcat(buf, "Auto-solved."); | ||
2854 | else if (state->completed) | ||
2855 | strcat(buf, "COMPLETED!"); | ||
2856 | |||
2857 | status_bar(dr, buf); | ||
2858 | } | ||
2859 | |||
2860 | if (hedge != state->hedge) { | ||
2861 | sfree(hedge); | ||
2862 | sfree(vedge); | ||
2863 | } | ||
2864 | |||
2865 | sfree(corners); | ||
2866 | } | ||
2867 | |||
2868 | static float game_anim_length(const game_state *oldstate, | ||
2869 | const game_state *newstate, int dir, game_ui *ui) | ||
2870 | { | ||
2871 | return 0.0F; | ||
2872 | } | ||
2873 | |||
2874 | static float game_flash_length(const game_state *oldstate, | ||
2875 | const game_state *newstate, int dir, game_ui *ui) | ||
2876 | { | ||
2877 | if (!oldstate->completed && newstate->completed && | ||
2878 | !oldstate->cheated && !newstate->cheated) | ||
2879 | return FLASH_TIME; | ||
2880 | return 0.0F; | ||
2881 | } | ||
2882 | |||
2883 | static int game_status(const game_state *state) | ||
2884 | { | ||
2885 | return state->completed ? +1 : 0; | ||
2886 | } | ||
2887 | |||
2888 | static int game_timing_state(const game_state *state, game_ui *ui) | ||
2889 | { | ||
2890 | return TRUE; | ||
2891 | } | ||
2892 | |||
2893 | static void game_print_size(const game_params *params, float *x, float *y) | ||
2894 | { | ||
2895 | int pw, ph; | ||
2896 | |||
2897 | /* | ||
2898 | * I'll use 5mm squares by default. | ||
2899 | */ | ||
2900 | game_compute_size(params, 500, &pw, &ph); | ||
2901 | *x = pw / 100.0F; | ||
2902 | *y = ph / 100.0F; | ||
2903 | } | ||
2904 | |||
2905 | static void game_print(drawing *dr, const game_state *state, int tilesize) | ||
2906 | { | ||
2907 | int w = state->w, h = state->h; | ||
2908 | int ink = print_mono_colour(dr, 0); | ||
2909 | int x, y; | ||
2910 | |||
2911 | /* Ick: fake up `ds->tilesize' for macro expansion purposes */ | ||
2912 | game_drawstate ads, *ds = &ads; | ||
2913 | game_set_size(dr, ds, NULL, tilesize); | ||
2914 | |||
2915 | /* | ||
2916 | * Border. | ||
2917 | */ | ||
2918 | print_line_width(dr, TILE_SIZE / 10); | ||
2919 | draw_rect_outline(dr, COORD(0), COORD(0), w*TILE_SIZE, h*TILE_SIZE, ink); | ||
2920 | |||
2921 | /* | ||
2922 | * Grid. We have to make the grid lines particularly thin, | ||
2923 | * because users will be drawing lines _along_ them and we want | ||
2924 | * those lines to be visible. | ||
2925 | */ | ||
2926 | print_line_width(dr, TILE_SIZE / 256); | ||
2927 | for (x = 1; x < w; x++) | ||
2928 | draw_line(dr, COORD(x), COORD(0), COORD(x), COORD(h), ink); | ||
2929 | for (y = 1; y < h; y++) | ||
2930 | draw_line(dr, COORD(0), COORD(y), COORD(w), COORD(y), ink); | ||
2931 | |||
2932 | /* | ||
2933 | * Solution. | ||
2934 | */ | ||
2935 | print_line_width(dr, TILE_SIZE / 10); | ||
2936 | for (y = 0; y <= h; y++) | ||
2937 | for (x = 0; x <= w; x++) { | ||
2938 | if (HRANGE(state,x,y) && hedge(state,x,y)) | ||
2939 | draw_line(dr, COORD(x), COORD(y), COORD(x+1), COORD(y), ink); | ||
2940 | if (VRANGE(state,x,y) && vedge(state,x,y)) | ||
2941 | draw_line(dr, COORD(x), COORD(y), COORD(x), COORD(y+1), ink); | ||
2942 | } | ||
2943 | |||
2944 | /* | ||
2945 | * Clues. | ||
2946 | */ | ||
2947 | for (y = 0; y < h; y++) | ||
2948 | for (x = 0; x < w; x++) | ||
2949 | if (grid(state,x,y)) { | ||
2950 | char str[80]; | ||
2951 | sprintf(str, "%d", grid(state,x,y)); | ||
2952 | draw_text(dr, COORD(x)+TILE_SIZE/2, COORD(y)+TILE_SIZE/2, | ||
2953 | FONT_VARIABLE, TILE_SIZE/2, | ||
2954 | ALIGN_HCENTRE | ALIGN_VCENTRE, ink, str); | ||
2955 | } | ||
2956 | } | ||
2957 | |||
2958 | #ifdef COMBINED | ||
2959 | #define thegame rect | ||
2960 | #endif | ||
2961 | |||
2962 | const struct game thegame = { | ||
2963 | "Rectangles", "games.rectangles", "rect", | ||
2964 | default_params, | ||
2965 | game_fetch_preset, | ||
2966 | decode_params, | ||
2967 | encode_params, | ||
2968 | free_params, | ||
2969 | dup_params, | ||
2970 | TRUE, game_configure, custom_params, | ||
2971 | validate_params, | ||
2972 | new_game_desc, | ||
2973 | validate_desc, | ||
2974 | new_game, | ||
2975 | dup_game, | ||
2976 | free_game, | ||
2977 | TRUE, solve_game, | ||
2978 | TRUE, game_can_format_as_text_now, game_text_format, | ||
2979 | new_ui, | ||
2980 | free_ui, | ||
2981 | encode_ui, | ||
2982 | decode_ui, | ||
2983 | game_changed_state, | ||
2984 | interpret_move, | ||
2985 | execute_move, | ||
2986 | PREFERRED_TILE_SIZE, game_compute_size, game_set_size, | ||
2987 | game_colours, | ||
2988 | game_new_drawstate, | ||
2989 | game_free_drawstate, | ||
2990 | game_redraw, | ||
2991 | game_anim_length, | ||
2992 | game_flash_length, | ||
2993 | game_status, | ||
2994 | TRUE, FALSE, game_print_size, game_print, | ||
2995 | TRUE, /* wants_statusbar */ | ||
2996 | FALSE, game_timing_state, | ||
2997 | 0, /* flags */ | ||
2998 | }; | ||
2999 | |||
3000 | /* vim: set shiftwidth=4 tabstop=8: */ | ||