6bbab0fe |
1 | /* |
2 | * 'same game' -- try to remove all the coloured squares by |
3 | * selecting regions of contiguous colours. |
4 | */ |
5 | |
e4a7ab56 |
6 | /* |
7 | * TODO on grid generation: |
8 | * |
9 | * - Generation speed could still be improved. |
10 | * * 15x10c3 is the only really difficult one of the existing |
11 | * presets. The others are all either small enough, or have |
12 | * the great flexibility given by four colours, that they |
13 | * don't take long at all. |
14 | * * I still suspect many problems arise from separate |
15 | * subareas. I wonder if we can also somehow prioritise left- |
16 | * or rightmost insertions so as to avoid area splitting at |
17 | * all where feasible? It's not easy, though, because the |
18 | * current shuffle-then-try-all-options approach to move |
19 | * choice doesn't leave room for `soft' probabilistic |
20 | * prioritisation: we either try all class A moves before any |
21 | * class B ones, or we don't. |
22 | * |
23 | * - The current generation algorithm inserts exactly two squares |
24 | * at a time, with a single exception at the beginning of |
25 | * generation for grids of odd overall size. An obvious |
26 | * extension would be to permit larger inverse moves during |
27 | * generation. |
28 | * * this might reduce the number of failed generations by |
29 | * making the insertion algorithm more flexible |
30 | * * on the other hand, it would be significantly more complex |
31 | * * if I do this I'll need to take out the odd-subarea |
32 | * avoidance |
33 | * * a nice feature of the current algorithm is that the |
34 | * computer's `intended' solution always receives the minimum |
35 | * possible score, so that pretty much the player's entire |
36 | * score represents how much better they did than the |
37 | * computer. |
38 | * |
39 | * - Is it possible we can _temporarily_ tolerate neighbouring |
40 | * squares of the same colour, until we've finished setting up |
41 | * our inverse move? |
42 | * * or perhaps even not choose the colour of our inserted |
43 | * region until we have finished placing it, and _then_ look |
44 | * at what colours border on it? |
45 | * * I don't think this is currently meaningful unless we're |
46 | * placing more than a domino at a time. |
47 | * |
48 | * - possibly write out a full solution so that Solve can somehow |
49 | * show it step by step? |
50 | * * aux_info would have to encode the click points |
51 | * * solve_game() would have to encode not only those click |
52 | * points but also give a move string which reconstructed the |
53 | * initial state |
54 | * * the game_state would include a pointer to a solution move |
55 | * list, plus an index into that list |
56 | * * game_changed_state would auto-select the next move if |
57 | * handed a new state which had a solution move list active |
58 | * * execute_move, if passed such a state as input, would check |
59 | * to see whether the move being made was the same as the one |
60 | * stated by the solution, and if so would advance the move |
61 | * index. Failing that it would return a game_state without a |
62 | * solution move list active at all. |
63 | */ |
64 | |
6bbab0fe |
65 | #include <stdio.h> |
66 | #include <stdlib.h> |
67 | #include <string.h> |
68 | #include <assert.h> |
69 | #include <ctype.h> |
70 | #include <math.h> |
71 | |
72 | #include "puzzles.h" |
73 | |
74 | #define TILE_INNER (ds->tileinner) |
75 | #define TILE_GAP (ds->tilegap) |
76 | #define TILE_SIZE (TILE_INNER + TILE_GAP) |
77 | #define PREFERRED_TILE_SIZE 32 |
78 | #define BORDER (TILE_SIZE / 2) |
79 | #define HIGHLIGHT_WIDTH 2 |
80 | |
81 | #define FLASH_FRAME 0.13F |
82 | |
83 | #define COORD(x) ( (x) * TILE_SIZE + BORDER ) |
84 | #define FROMCOORD(x) ( ((x) - BORDER + TILE_SIZE) / TILE_SIZE - 1 ) |
85 | |
86 | #define X(state, i) ( (i) % (state)->params.w ) |
87 | #define Y(state, i) ( (i) / (state)->params.w ) |
88 | #define C(state, x, y) ( (y) * (state)->w + (x) ) |
89 | |
90 | enum { |
91 | COL_BACKGROUND, |
92 | COL_1, COL_2, COL_3, COL_4, COL_5, COL_6, COL_7, COL_8, COL_9, |
93 | COL_IMPOSSIBLE, COL_SEL, COL_HIGHLIGHT, COL_LOWLIGHT, |
94 | NCOLOURS |
95 | }; |
96 | |
97 | /* scoresub is 1 or 2 (for (n-1)^2 or (n-2)^2) */ |
98 | struct game_params { |
99 | int w, h, ncols, scoresub; |
e4a7ab56 |
100 | int soluble; /* choose generation algorithm */ |
6bbab0fe |
101 | }; |
102 | |
103 | /* These flags must be unique across all uses; in the game_state, |
104 | * the game_ui, and the drawstate (as they all get combined in the |
105 | * drawstate). */ |
f1359c5e |
106 | #define TILE_COLMASK 0x00ff |
107 | #define TILE_SELECTED 0x0100 /* used in ui and drawstate */ |
108 | #define TILE_JOINRIGHT 0x0200 /* used in drawstate */ |
109 | #define TILE_JOINDOWN 0x0400 /* used in drawstate */ |
110 | #define TILE_JOINDIAG 0x0800 /* used in drawstate */ |
111 | #define TILE_HASSEL 0x1000 /* used in drawstate */ |
d951510d |
112 | #define TILE_IMPOSSIBLE 0x2000 /* used in drawstate */ |
6bbab0fe |
113 | |
114 | #define TILE(gs,x,y) ((gs)->tiles[(gs)->params.w*(y)+(x)]) |
115 | #define COL(gs,x,y) (TILE(gs,x,y) & TILE_COLMASK) |
116 | #define ISSEL(gs,x,y) (TILE(gs,x,y) & TILE_SELECTED) |
117 | |
118 | #define SWAPTILE(gs,x1,y1,x2,y2) do { \ |
119 | int t = TILE(gs,x1,y1); \ |
120 | TILE(gs,x1,y1) = TILE(gs,x2,y2); \ |
121 | TILE(gs,x2,y2) = t; \ |
122 | } while (0) |
123 | |
124 | static int npoints(game_params *params, int nsel) |
125 | { |
126 | int sdiff = nsel - params->scoresub; |
127 | return (sdiff > 0) ? sdiff * sdiff : 0; |
128 | } |
129 | |
130 | struct game_state { |
131 | struct game_params params; |
132 | int n; |
133 | int *tiles; /* colour only */ |
134 | int score; |
135 | int complete, impossible; |
136 | }; |
137 | |
138 | static game_params *default_params(void) |
139 | { |
140 | game_params *ret = snew(game_params); |
141 | ret->w = 5; |
142 | ret->h = 5; |
143 | ret->ncols = 3; |
144 | ret->scoresub = 2; |
e4a7ab56 |
145 | ret->soluble = TRUE; |
6bbab0fe |
146 | return ret; |
147 | } |
148 | |
149 | static const struct game_params samegame_presets[] = { |
e4a7ab56 |
150 | { 5, 5, 3, 2, TRUE }, |
151 | { 10, 5, 3, 2, TRUE }, |
0e1a6ac4 |
152 | #ifdef SLOW_SYSTEM |
153 | { 10, 10, 3, 2, TRUE }, |
154 | #else |
e4a7ab56 |
155 | { 15, 10, 3, 2, TRUE }, |
0e1a6ac4 |
156 | #endif |
e4a7ab56 |
157 | { 15, 10, 4, 2, TRUE }, |
158 | { 20, 15, 4, 2, TRUE } |
6bbab0fe |
159 | }; |
160 | |
161 | static int game_fetch_preset(int i, char **name, game_params **params) |
162 | { |
163 | game_params *ret; |
164 | char str[80]; |
165 | |
166 | if (i < 0 || i >= lenof(samegame_presets)) |
167 | return FALSE; |
168 | |
169 | ret = snew(game_params); |
170 | *ret = samegame_presets[i]; |
171 | |
172 | sprintf(str, "%dx%d, %d colours", ret->w, ret->h, ret->ncols); |
173 | |
174 | *name = dupstr(str); |
175 | *params = ret; |
176 | return TRUE; |
177 | } |
178 | |
179 | static void free_params(game_params *params) |
180 | { |
181 | sfree(params); |
182 | } |
183 | |
184 | static game_params *dup_params(game_params *params) |
185 | { |
186 | game_params *ret = snew(game_params); |
187 | *ret = *params; /* structure copy */ |
188 | return ret; |
189 | } |
190 | |
191 | static void decode_params(game_params *params, char const *string) |
192 | { |
193 | char const *p = string; |
194 | |
195 | params->w = atoi(p); |
196 | while (*p && isdigit((unsigned char)*p)) p++; |
197 | if (*p == 'x') { |
198 | p++; |
199 | params->h = atoi(p); |
200 | while (*p && isdigit((unsigned char)*p)) p++; |
201 | } else { |
202 | params->h = params->w; |
203 | } |
e4a7ab56 |
204 | if (*p == 'c') { |
205 | p++; |
6bbab0fe |
206 | params->ncols = atoi(p); |
207 | while (*p && isdigit((unsigned char)*p)) p++; |
208 | } else { |
209 | params->ncols = 3; |
210 | } |
e4a7ab56 |
211 | if (*p == 's') { |
212 | p++; |
6bbab0fe |
213 | params->scoresub = atoi(p); |
214 | while (*p && isdigit((unsigned char)*p)) p++; |
215 | } else { |
216 | params->scoresub = 2; |
217 | } |
e4a7ab56 |
218 | if (*p == 'r') { |
219 | p++; |
220 | params->soluble = FALSE; |
221 | } |
6bbab0fe |
222 | } |
223 | |
224 | static char *encode_params(game_params *params, int full) |
225 | { |
226 | char ret[80]; |
227 | |
e4a7ab56 |
228 | sprintf(ret, "%dx%dc%ds%d%s", |
229 | params->w, params->h, params->ncols, params->scoresub, |
230 | full && !params->soluble ? "r" : ""); |
6bbab0fe |
231 | return dupstr(ret); |
232 | } |
233 | |
234 | static config_item *game_configure(game_params *params) |
235 | { |
236 | config_item *ret; |
237 | char buf[80]; |
238 | |
e4a7ab56 |
239 | ret = snewn(6, config_item); |
6bbab0fe |
240 | |
241 | ret[0].name = "Width"; |
242 | ret[0].type = C_STRING; |
243 | sprintf(buf, "%d", params->w); |
244 | ret[0].sval = dupstr(buf); |
245 | ret[0].ival = 0; |
246 | |
247 | ret[1].name = "Height"; |
248 | ret[1].type = C_STRING; |
249 | sprintf(buf, "%d", params->h); |
250 | ret[1].sval = dupstr(buf); |
251 | ret[1].ival = 0; |
252 | |
253 | ret[2].name = "No. of colours"; |
254 | ret[2].type = C_STRING; |
255 | sprintf(buf, "%d", params->ncols); |
256 | ret[2].sval = dupstr(buf); |
257 | ret[2].ival = 0; |
258 | |
259 | ret[3].name = "Scoring system"; |
260 | ret[3].type = C_CHOICES; |
261 | ret[3].sval = ":(n-1)^2:(n-2)^2"; |
262 | ret[3].ival = params->scoresub-1; |
263 | |
e4a7ab56 |
264 | ret[4].name = "Ensure solubility"; |
265 | ret[4].type = C_BOOLEAN; |
6bbab0fe |
266 | ret[4].sval = NULL; |
e4a7ab56 |
267 | ret[4].ival = params->soluble; |
268 | |
269 | ret[5].name = NULL; |
270 | ret[5].type = C_END; |
271 | ret[5].sval = NULL; |
272 | ret[5].ival = 0; |
6bbab0fe |
273 | |
274 | return ret; |
275 | } |
276 | |
277 | static game_params *custom_params(config_item *cfg) |
278 | { |
279 | game_params *ret = snew(game_params); |
280 | |
281 | ret->w = atoi(cfg[0].sval); |
282 | ret->h = atoi(cfg[1].sval); |
283 | ret->ncols = atoi(cfg[2].sval); |
284 | ret->scoresub = cfg[3].ival + 1; |
e4a7ab56 |
285 | ret->soluble = cfg[4].ival; |
6bbab0fe |
286 | |
287 | return ret; |
288 | } |
289 | |
3ff276f2 |
290 | static char *validate_params(game_params *params, int full) |
6bbab0fe |
291 | { |
292 | if (params->w < 1 || params->h < 1) |
293 | return "Width and height must both be positive"; |
e4a7ab56 |
294 | |
6bbab0fe |
295 | if (params->ncols > 9) |
296 | return "Maximum of 9 colours"; |
297 | |
e4a7ab56 |
298 | if (params->soluble) { |
299 | if (params->ncols < 3) |
300 | return "Number of colours must be at least three"; |
301 | if (params->w * params->h <= 1) |
302 | return "Grid area must be greater than 1"; |
303 | } else { |
304 | if (params->ncols < 2) |
305 | return "Number of colours must be at least three"; |
306 | /* ...and we must make sure we can generate at least 2 squares |
307 | * of each colour so it's theoretically soluble. */ |
308 | if ((params->w * params->h) < (params->ncols * 2)) |
309 | return "Too many colours makes given grid size impossible"; |
310 | } |
6bbab0fe |
311 | |
312 | if ((params->scoresub < 1) || (params->scoresub > 2)) |
313 | return "Scoring system not recognised"; |
314 | |
315 | return NULL; |
316 | } |
317 | |
e4a7ab56 |
318 | /* |
319 | * Guaranteed-soluble grid generator. |
6bbab0fe |
320 | */ |
e4a7ab56 |
321 | static void gen_grid(int w, int h, int nc, int *grid, random_state *rs) |
322 | { |
323 | int wh = w*h, tc = nc+1; |
324 | int i, j, k, c, x, y, pos, n; |
325 | int *list, *grid2; |
326 | int ok, failures = 0; |
327 | |
328 | /* |
329 | * We'll use `list' to track the possible places to put our |
330 | * next insertion. There are up to h places to insert in each |
331 | * column: in a column of height n there are n+1 places because |
332 | * we can insert at the very bottom or the very top, but a |
333 | * column of height h can't have anything at all inserted in it |
334 | * so we have up to h in each column. Likewise, with n columns |
335 | * present there are n+1 places to fit a new one in between but |
336 | * we can't insert a column if there are already w; so there |
337 | * are a maximum of w new columns too. Total is wh + w. |
338 | */ |
339 | list = snewn(wh + w, int); |
340 | grid2 = snewn(wh, int); |
341 | |
342 | do { |
343 | /* |
344 | * Start with two or three squares - depending on parity of w*h |
345 | * - of a random colour. |
346 | */ |
347 | for (i = 0; i < wh; i++) |
348 | grid[i] = 0; |
349 | j = 2 + (wh % 2); |
350 | c = 1 + random_upto(rs, nc); |
351 | if (j <= w) { |
352 | for (i = 0; i < j; i++) |
353 | grid[(h-1)*w+i] = c; |
354 | } else { |
355 | assert(j <= h); |
356 | for (i = 0; i < j; i++) |
357 | grid[(h-1-i)*w] = c; |
358 | } |
6bbab0fe |
359 | |
e4a7ab56 |
360 | /* |
361 | * Now repeatedly insert a two-square blob in the grid, of |
362 | * whatever colour will go at the position we chose. |
363 | */ |
364 | while (1) { |
365 | n = 0; |
366 | |
367 | /* |
368 | * Build up a list of insertion points. Each point is |
369 | * encoded as y*w+x; insertion points between columns are |
370 | * encoded as h*w+x. |
371 | */ |
372 | |
373 | if (grid[wh - 1] == 0) { |
374 | /* |
375 | * The final column is empty, so we can insert new |
376 | * columns. |
377 | */ |
378 | for (i = 0; i < w; i++) { |
379 | list[n++] = wh + i; |
380 | if (grid[(h-1)*w + i] == 0) |
381 | break; |
382 | } |
383 | } |
384 | |
385 | /* |
386 | * Now look for places to insert within columns. |
387 | */ |
388 | for (i = 0; i < w; i++) { |
389 | if (grid[(h-1)*w+i] == 0) |
390 | break; /* no more columns */ |
391 | |
392 | if (grid[i] != 0) |
393 | continue; /* this column is full */ |
394 | |
395 | for (j = h; j-- > 0 ;) { |
396 | list[n++] = j*w+i; |
397 | if (grid[j*w+i] == 0) |
398 | break; /* this column is exhausted */ |
399 | } |
400 | } |
401 | |
402 | if (n == 0) |
403 | break; /* we're done */ |
404 | |
e4a7ab56 |
405 | #ifdef GENERATION_DIAGNOSTICS |
406 | printf("initial grid:\n"); |
407 | { |
408 | int x,y; |
409 | for (y = 0; y < h; y++) { |
410 | for (x = 0; x < w; x++) { |
411 | if (grid[y*w+x] == 0) |
412 | printf("-"); |
413 | else |
414 | printf("%d", grid[y*w+x]); |
415 | } |
416 | printf("\n"); |
417 | } |
418 | } |
419 | #endif |
420 | |
421 | /* |
43093e37 |
422 | * Now go through the list one element at a time in |
423 | * random order, and actually attempt to insert |
424 | * something there. |
e4a7ab56 |
425 | */ |
426 | while (n-- > 0) { |
427 | int dirs[4], ndirs, dir; |
428 | |
43093e37 |
429 | i = random_upto(rs, n+1); |
430 | pos = list[i]; |
431 | list[i] = list[n]; |
432 | |
e4a7ab56 |
433 | x = pos % w; |
434 | y = pos / w; |
435 | |
436 | memcpy(grid2, grid, wh * sizeof(int)); |
437 | |
438 | if (y == h) { |
439 | /* |
440 | * Insert a column at position x. |
441 | */ |
442 | for (i = w-1; i > x; i--) |
443 | for (j = 0; j < h; j++) |
444 | grid2[j*w+i] = grid2[j*w+(i-1)]; |
445 | /* |
446 | * Clear the new column. |
447 | */ |
448 | for (j = 0; j < h; j++) |
449 | grid2[j*w+x] = 0; |
450 | /* |
451 | * Decrement y so that our first square is actually |
452 | * inserted _in_ the grid rather than just below it. |
453 | */ |
454 | y--; |
455 | } |
456 | |
457 | /* |
458 | * Insert a square within column x at position y. |
459 | */ |
460 | for (i = 0; i+1 <= y; i++) |
461 | grid2[i*w+x] = grid2[(i+1)*w+x]; |
462 | |
463 | #ifdef GENERATION_DIAGNOSTICS |
464 | printf("trying at n=%d (%d,%d)\n", n, x, y); |
465 | grid2[y*w+x] = tc; |
466 | { |
467 | int x,y; |
468 | for (y = 0; y < h; y++) { |
469 | for (x = 0; x < w; x++) { |
470 | if (grid2[y*w+x] == 0) |
471 | printf("-"); |
472 | else if (grid2[y*w+x] <= nc) |
473 | printf("%d", grid2[y*w+x]); |
474 | else |
475 | printf("*"); |
476 | } |
477 | printf("\n"); |
478 | } |
479 | } |
480 | #endif |
481 | |
482 | /* |
483 | * Pick our square colour so that it doesn't match any |
484 | * of its neighbours. |
485 | */ |
486 | { |
487 | int wrongcol[4], nwrong = 0; |
488 | |
489 | /* |
490 | * List the neighbouring colours. |
491 | */ |
492 | if (x > 0) |
493 | wrongcol[nwrong++] = grid2[y*w+(x-1)]; |
494 | if (x+1 < w) |
495 | wrongcol[nwrong++] = grid2[y*w+(x+1)]; |
496 | if (y > 0) |
497 | wrongcol[nwrong++] = grid2[(y-1)*w+x]; |
498 | if (y+1 < h) |
499 | wrongcol[nwrong++] = grid2[(y+1)*w+x]; |
500 | |
501 | /* |
502 | * Eliminate duplicates. We can afford a shoddy |
503 | * algorithm here because the problem size is |
504 | * bounded. |
505 | */ |
506 | for (i = j = 0 ;; i++) { |
507 | int pos = -1, min = 0; |
508 | if (j > 0) |
509 | min = wrongcol[j-1]; |
510 | for (k = i; k < nwrong; k++) |
511 | if (wrongcol[k] > min && |
512 | (pos == -1 || wrongcol[k] < wrongcol[pos])) |
513 | pos = k; |
514 | if (pos >= 0) { |
515 | int v = wrongcol[pos]; |
516 | wrongcol[pos] = wrongcol[j]; |
517 | wrongcol[j++] = v; |
518 | } else |
519 | break; |
520 | } |
521 | nwrong = j; |
522 | |
523 | /* |
524 | * If no colour will go here, stop trying. |
525 | */ |
526 | if (nwrong == nc) |
527 | continue; |
528 | |
529 | /* |
530 | * Otherwise, pick a colour from the remaining |
531 | * ones. |
532 | */ |
533 | c = 1 + random_upto(rs, nc - nwrong); |
534 | for (i = 0; i < nwrong; i++) { |
535 | if (c >= wrongcol[i]) |
536 | c++; |
537 | else |
538 | break; |
539 | } |
540 | } |
541 | |
542 | /* |
543 | * Place the new square. |
544 | * |
545 | * Although I've _chosen_ the new region's colour |
546 | * (so that we can check adjacency), I'm going to |
547 | * actually place it as an invalid colour (tc) |
548 | * until I'm sure it's viable. This is so that I |
549 | * can conveniently check that I really have made a |
550 | * _valid_ inverse move later on. |
551 | */ |
552 | #ifdef GENERATION_DIAGNOSTICS |
553 | printf("picked colour %d\n", c); |
554 | #endif |
555 | grid2[y*w+x] = tc; |
556 | |
557 | /* |
558 | * Now attempt to extend it in one of three ways: left, |
559 | * right or up. |
560 | */ |
561 | ndirs = 0; |
562 | if (x > 0 && |
563 | grid2[y*w+(x-1)] != c && |
564 | grid2[x-1] == 0 && |
565 | (y+1 >= h || grid2[(y+1)*w+(x-1)] != c) && |
566 | (y+1 >= h || grid2[(y+1)*w+(x-1)] != 0) && |
567 | (x <= 1 || grid2[y*w+(x-2)] != c)) |
568 | dirs[ndirs++] = -1; /* left */ |
569 | if (x+1 < w && |
570 | grid2[y*w+(x+1)] != c && |
571 | grid2[x+1] == 0 && |
572 | (y+1 >= h || grid2[(y+1)*w+(x+1)] != c) && |
573 | (y+1 >= h || grid2[(y+1)*w+(x+1)] != 0) && |
574 | (x+2 >= w || grid2[y*w+(x+2)] != c)) |
575 | dirs[ndirs++] = +1; /* right */ |
576 | if (y > 0 && |
577 | grid2[x] == 0 && |
578 | (x <= 0 || grid2[(y-1)*w+(x-1)] != c) && |
579 | (x+1 >= w || grid2[(y-1)*w+(x+1)] != c)) { |
580 | /* |
581 | * We add this possibility _twice_, so that the |
582 | * probability of placing a vertical domino is |
583 | * about the same as that of a horizontal. This |
584 | * should yield less bias in the generated |
585 | * grids. |
586 | */ |
587 | dirs[ndirs++] = 0; /* up */ |
588 | dirs[ndirs++] = 0; /* up */ |
589 | } |
590 | |
591 | if (ndirs == 0) |
592 | continue; |
593 | |
594 | dir = dirs[random_upto(rs, ndirs)]; |
595 | |
596 | #ifdef GENERATION_DIAGNOSTICS |
597 | printf("picked dir %d\n", dir); |
598 | #endif |
599 | |
600 | /* |
601 | * Insert a square within column (x+dir) at position y. |
602 | */ |
603 | for (i = 0; i+1 <= y; i++) |
604 | grid2[i*w+x+dir] = grid2[(i+1)*w+x+dir]; |
605 | grid2[y*w+x+dir] = tc; |
606 | |
607 | /* |
608 | * See if we've divided the remaining grid squares |
609 | * into sub-areas. If so, we need every sub-area to |
610 | * have an even area or we won't be able to |
611 | * complete generation. |
612 | * |
613 | * If the height is odd and not all columns are |
614 | * present, we can increase the area of a subarea |
615 | * by adding a new column in it, so in that |
616 | * situation we don't mind having as many odd |
617 | * subareas as there are spare columns. |
618 | * |
619 | * If the height is even, we can't fix it at all. |
620 | */ |
621 | { |
622 | int nerrs = 0, nfix = 0; |
623 | k = 0; /* current subarea size */ |
624 | for (i = 0; i < w; i++) { |
625 | if (grid2[(h-1)*w+i] == 0) { |
626 | if (h % 2) |
627 | nfix++; |
628 | continue; |
629 | } |
630 | for (j = 0; j < h && grid2[j*w+i] == 0; j++); |
631 | assert(j < h); |
632 | if (j == 0) { |
633 | /* |
634 | * End of previous subarea. |
635 | */ |
636 | if (k % 2) |
637 | nerrs++; |
638 | k = 0; |
639 | } else { |
640 | k += j; |
641 | } |
642 | } |
643 | if (k % 2) |
644 | nerrs++; |
645 | if (nerrs > nfix) |
646 | continue; /* try a different placement */ |
647 | } |
648 | |
649 | /* |
650 | * We've made a move. Verify that it is a valid |
651 | * move and that if made it would indeed yield the |
652 | * previous grid state. The criteria are: |
653 | * |
654 | * (a) removing all the squares of colour tc (and |
655 | * shuffling the columns up etc) from grid2 |
656 | * would yield grid |
657 | * (b) no square of colour tc is adjacent to one |
658 | * of colour c |
659 | * (c) all the squares of colour tc form a single |
660 | * connected component |
661 | * |
662 | * We verify the latter property at the same time |
663 | * as checking that removing all the tc squares |
664 | * would yield the previous grid. Then we colour |
665 | * the tc squares in colour c by breadth-first |
666 | * search, which conveniently permits us to test |
667 | * that they're all connected. |
668 | */ |
669 | { |
670 | int x1, x2, y1, y2; |
671 | int ok = TRUE; |
672 | int fillstart = -1, ntc = 0; |
673 | |
674 | #ifdef GENERATION_DIAGNOSTICS |
675 | { |
676 | int x,y; |
677 | printf("testing move (new, old):\n"); |
678 | for (y = 0; y < h; y++) { |
679 | for (x = 0; x < w; x++) { |
680 | if (grid2[y*w+x] == 0) |
681 | printf("-"); |
682 | else if (grid2[y*w+x] <= nc) |
683 | printf("%d", grid2[y*w+x]); |
684 | else |
685 | printf("*"); |
686 | } |
687 | printf(" "); |
688 | for (x = 0; x < w; x++) { |
689 | if (grid[y*w+x] == 0) |
690 | printf("-"); |
691 | else |
692 | printf("%d", grid[y*w+x]); |
693 | } |
694 | printf("\n"); |
695 | } |
696 | } |
697 | #endif |
698 | |
699 | for (x1 = x2 = 0; x2 < w; x2++) { |
700 | int usedcol = FALSE; |
701 | |
702 | for (y1 = y2 = h-1; y2 >= 0; y2--) { |
703 | if (grid2[y2*w+x2] == tc) { |
704 | ntc++; |
705 | if (fillstart == -1) |
706 | fillstart = y2*w+x2; |
707 | if ((y2+1 < h && grid2[(y2+1)*w+x2] == c) || |
708 | (y2-1 >= 0 && grid2[(y2-1)*w+x2] == c) || |
709 | (x2+1 < w && grid2[y2*w+x2+1] == c) || |
710 | (x2-1 >= 0 && grid2[y2*w+x2-1] == c)) { |
711 | #ifdef GENERATION_DIAGNOSTICS |
712 | printf("adjacency failure at %d,%d\n", |
713 | x2, y2); |
714 | #endif |
715 | ok = FALSE; |
716 | } |
717 | continue; |
718 | } |
719 | if (grid2[y2*w+x2] == 0) |
720 | break; |
721 | usedcol = TRUE; |
722 | if (grid2[y2*w+x2] != grid[y1*w+x1]) { |
723 | #ifdef GENERATION_DIAGNOSTICS |
724 | printf("matching failure at %d,%d vs %d,%d\n", |
725 | x2, y2, x1, y1); |
726 | #endif |
727 | ok = FALSE; |
728 | } |
729 | y1--; |
730 | } |
731 | |
732 | /* |
733 | * If we've reached the top of the column |
734 | * in grid2, verify that we've also reached |
735 | * the top of the column in `grid'. |
736 | */ |
737 | if (usedcol) { |
738 | while (y1 >= 0) { |
739 | if (grid[y1*w+x1] != 0) { |
740 | #ifdef GENERATION_DIAGNOSTICS |
741 | printf("junk at column top (%d,%d)\n", |
742 | x1, y1); |
743 | #endif |
744 | ok = FALSE; |
745 | } |
746 | y1--; |
747 | } |
748 | } |
749 | |
750 | if (!ok) |
751 | break; |
752 | |
753 | if (usedcol) |
754 | x1++; |
755 | } |
756 | |
757 | if (!ok) { |
758 | assert(!"This should never happen"); |
759 | |
760 | /* |
761 | * If this game is compiled NDEBUG so that |
762 | * the assertion doesn't bring it to a |
763 | * crashing halt, the only thing we can do |
764 | * is to give up, loop round again, and |
765 | * hope to randomly avoid making whatever |
766 | * type of move just caused this failure. |
767 | */ |
768 | continue; |
769 | } |
770 | |
771 | /* |
772 | * Now use bfs to fill in the tc section as |
773 | * colour c. We use `list' to store the set of |
774 | * squares we have to process. |
775 | */ |
776 | i = j = 0; |
777 | assert(fillstart >= 0); |
778 | list[i++] = fillstart; |
779 | #ifdef OUTPUT_SOLUTION |
780 | printf("M"); |
781 | #endif |
782 | while (j < i) { |
783 | k = list[j]; |
784 | x = k % w; |
785 | y = k / w; |
786 | #ifdef OUTPUT_SOLUTION |
787 | printf("%s%d", j ? "," : "", k); |
788 | #endif |
789 | j++; |
790 | |
791 | assert(grid2[k] == tc); |
792 | grid2[k] = c; |
793 | |
794 | if (x > 0 && grid2[k-1] == tc) |
795 | list[i++] = k-1; |
796 | if (x+1 < w && grid2[k+1] == tc) |
797 | list[i++] = k+1; |
798 | if (y > 0 && grid2[k-w] == tc) |
799 | list[i++] = k-w; |
800 | if (y+1 < h && grid2[k+w] == tc) |
801 | list[i++] = k+w; |
802 | } |
803 | #ifdef OUTPUT_SOLUTION |
804 | printf("\n"); |
805 | #endif |
806 | |
807 | /* |
808 | * Check that we've filled the same number of |
809 | * tc squares as we originally found. |
810 | */ |
811 | assert(j == ntc); |
812 | } |
813 | |
814 | memcpy(grid, grid2, wh * sizeof(int)); |
815 | |
816 | break; /* done it! */ |
817 | } |
818 | |
819 | #ifdef GENERATION_DIAGNOSTICS |
820 | { |
821 | int x,y; |
822 | printf("n=%d\n", n); |
823 | for (y = 0; y < h; y++) { |
824 | for (x = 0; x < w; x++) { |
825 | if (grid[y*w+x] == 0) |
826 | printf("-"); |
827 | else |
828 | printf("%d", grid[y*w+x]); |
829 | } |
830 | printf("\n"); |
831 | } |
832 | } |
833 | #endif |
834 | |
835 | if (n < 0) |
836 | break; |
837 | } |
838 | |
839 | ok = TRUE; |
840 | for (i = 0; i < wh; i++) |
841 | if (grid[i] == 0) { |
842 | ok = FALSE; |
843 | failures++; |
844 | #if defined GENERATION_DIAGNOSTICS || defined SHOW_INCOMPLETE |
845 | { |
846 | int x,y; |
847 | printf("incomplete grid:\n"); |
848 | for (y = 0; y < h; y++) { |
849 | for (x = 0; x < w; x++) { |
850 | if (grid[y*w+x] == 0) |
851 | printf("-"); |
852 | else |
853 | printf("%d", grid[y*w+x]); |
854 | } |
855 | printf("\n"); |
856 | } |
857 | } |
858 | #endif |
859 | break; |
860 | } |
861 | |
862 | } while (!ok); |
863 | |
864 | #if defined GENERATION_DIAGNOSTICS || defined COUNT_FAILURES |
865 | printf("%d failures\n", failures); |
866 | #endif |
867 | #ifdef GENERATION_DIAGNOSTICS |
868 | { |
869 | int x,y; |
870 | printf("final grid:\n"); |
871 | for (y = 0; y < h; y++) { |
872 | for (x = 0; x < w; x++) { |
873 | printf("%d", grid[y*w+x]); |
874 | } |
875 | printf("\n"); |
876 | } |
877 | } |
878 | #endif |
879 | |
880 | sfree(grid2); |
881 | sfree(list); |
882 | } |
883 | |
884 | /* |
885 | * Not-guaranteed-soluble grid generator; kept as a legacy, and in |
886 | * case someone finds the slightly odd quality of the guaranteed- |
887 | * soluble grids to be aesthetically displeasing or finds its CPU |
888 | * utilisation to be excessive. |
889 | */ |
890 | static void gen_grid_random(int w, int h, int nc, int *grid, random_state *rs) |
6bbab0fe |
891 | { |
e4a7ab56 |
892 | int i, j, c; |
893 | int n = w * h; |
6bbab0fe |
894 | |
e4a7ab56 |
895 | for (i = 0; i < n; i++) |
896 | grid[i] = 0; |
6bbab0fe |
897 | |
e4a7ab56 |
898 | /* |
899 | * Our sole concession to not gratuitously generating insoluble |
900 | * grids is to ensure we have at least two of every colour. |
901 | */ |
902 | for (c = 1; c <= nc; c++) { |
6bbab0fe |
903 | for (j = 0; j < 2; j++) { |
904 | do { |
905 | i = (int)random_upto(rs, n); |
e4a7ab56 |
906 | } while (grid[i] != 0); |
907 | grid[i] = c; |
6bbab0fe |
908 | } |
909 | } |
910 | |
e4a7ab56 |
911 | /* |
912 | * Fill in the rest of the grid at random. |
913 | */ |
6bbab0fe |
914 | for (i = 0; i < n; i++) { |
e4a7ab56 |
915 | if (grid[i] == 0) |
916 | grid[i] = (int)random_upto(rs, nc)+1; |
6bbab0fe |
917 | } |
e4a7ab56 |
918 | } |
919 | |
920 | static char *new_game_desc(game_params *params, random_state *rs, |
921 | char **aux, int interactive) |
922 | { |
923 | char *ret; |
924 | int n, i, retlen, *tiles; |
925 | |
926 | n = params->w * params->h; |
927 | tiles = snewn(n, int); |
928 | |
929 | if (params->soluble) |
930 | gen_grid(params->w, params->h, params->ncols, tiles, rs); |
931 | else |
932 | gen_grid_random(params->w, params->h, params->ncols, tiles, rs); |
6bbab0fe |
933 | |
934 | ret = NULL; |
935 | retlen = 0; |
936 | for (i = 0; i < n; i++) { |
937 | char buf[80]; |
938 | int k; |
939 | |
940 | k = sprintf(buf, "%d,", tiles[i]); |
941 | ret = sresize(ret, retlen + k + 1, char); |
942 | strcpy(ret + retlen, buf); |
943 | retlen += k; |
944 | } |
945 | ret[retlen-1] = '\0'; /* delete last comma */ |
946 | |
947 | sfree(tiles); |
948 | return ret; |
949 | } |
950 | |
6bbab0fe |
951 | static char *validate_desc(game_params *params, char *desc) |
952 | { |
953 | int area = params->w * params->h, i; |
954 | char *p = desc; |
955 | |
956 | for (i = 0; i < area; i++) { |
957 | char *q = p; |
958 | int n; |
959 | |
89167dad |
960 | if (!isdigit((unsigned char)*p)) |
6bbab0fe |
961 | return "Not enough numbers in string"; |
89167dad |
962 | while (isdigit((unsigned char)*p)) p++; |
6bbab0fe |
963 | |
964 | if (i < area-1 && *p != ',') |
965 | return "Expected comma after number"; |
966 | else if (i == area-1 && *p) |
967 | return "Excess junk at end of string"; |
968 | |
969 | n = atoi(q); |
970 | if (n < 0 || n > params->ncols) |
971 | return "Colour out of range"; |
972 | |
973 | if (*p) p++; /* eat comma */ |
974 | } |
975 | return NULL; |
976 | } |
977 | |
dafd6cf6 |
978 | static game_state *new_game(midend *me, game_params *params, char *desc) |
6bbab0fe |
979 | { |
980 | game_state *state = snew(game_state); |
981 | char *p = desc; |
982 | int i; |
983 | |
984 | state->params = *params; /* struct copy */ |
985 | state->n = state->params.w * state->params.h; |
986 | state->tiles = snewn(state->n, int); |
987 | |
988 | for (i = 0; i < state->n; i++) { |
989 | assert(*p); |
990 | state->tiles[i] = atoi(p); |
991 | while (*p && *p != ',') |
992 | p++; |
993 | if (*p) p++; /* eat comma */ |
994 | } |
995 | state->complete = state->impossible = 0; |
996 | state->score = 0; |
997 | |
998 | return state; |
999 | } |
1000 | |
1001 | static game_state *dup_game(game_state *state) |
1002 | { |
1003 | game_state *ret = snew(game_state); |
1004 | |
1005 | *ret = *state; /* structure copy, except... */ |
1006 | |
1007 | ret->tiles = snewn(state->n, int); |
1008 | memcpy(ret->tiles, state->tiles, state->n * sizeof(int)); |
1009 | |
1010 | return ret; |
1011 | } |
1012 | |
1013 | static void free_game(game_state *state) |
1014 | { |
1015 | sfree(state->tiles); |
1016 | sfree(state); |
1017 | } |
1018 | |
df11cd4e |
1019 | static char *solve_game(game_state *state, game_state *currstate, |
c566778e |
1020 | char *aux, char **error) |
6bbab0fe |
1021 | { |
1022 | return NULL; |
1023 | } |
1024 | |
1025 | static char *game_text_format(game_state *state) |
1026 | { |
1027 | char *ret, *p; |
1028 | int x, y, maxlen; |
1029 | |
1030 | maxlen = state->params.h * (state->params.w + 1); |
1031 | ret = snewn(maxlen+1, char); |
1032 | p = ret; |
1033 | |
1034 | for (y = 0; y < state->params.h; y++) { |
1035 | for (x = 0; x < state->params.w; x++) { |
1036 | int t = TILE(state,x,y); |
1037 | if (t <= 0) *p++ = ' '; |
1038 | else if (t < 10) *p++ = '0'+t; |
1039 | else *p++ = 'a'+(t-10); |
1040 | } |
1041 | *p++ = '\n'; |
1042 | } |
1043 | assert(p - ret == maxlen); |
1044 | *p = '\0'; |
1045 | return ret; |
1046 | } |
1047 | |
1048 | struct game_ui { |
1049 | struct game_params params; |
1050 | int *tiles; /* selected-ness only */ |
1051 | int nselected; |
f1359c5e |
1052 | int xsel, ysel, displaysel; |
6bbab0fe |
1053 | }; |
1054 | |
1055 | static game_ui *new_ui(game_state *state) |
1056 | { |
1057 | game_ui *ui = snew(game_ui); |
1058 | |
1059 | ui->params = state->params; /* structure copy */ |
1060 | ui->tiles = snewn(state->n, int); |
1061 | memset(ui->tiles, 0, state->n*sizeof(int)); |
1062 | ui->nselected = 0; |
1063 | |
f1359c5e |
1064 | ui->xsel = ui->ysel = ui->displaysel = 0; |
1065 | |
6bbab0fe |
1066 | return ui; |
1067 | } |
1068 | |
1069 | static void free_ui(game_ui *ui) |
1070 | { |
1071 | sfree(ui->tiles); |
1072 | sfree(ui); |
1073 | } |
1074 | |
844f605f |
1075 | static char *encode_ui(game_ui *ui) |
ae8290c6 |
1076 | { |
1077 | return NULL; |
1078 | } |
1079 | |
844f605f |
1080 | static void decode_ui(game_ui *ui, char *encoding) |
ae8290c6 |
1081 | { |
1082 | } |
1083 | |
6bbab0fe |
1084 | static void sel_clear(game_ui *ui, game_state *state) |
1085 | { |
1086 | int i; |
1087 | |
1088 | for (i = 0; i < state->n; i++) |
1089 | ui->tiles[i] &= ~TILE_SELECTED; |
1090 | ui->nselected = 0; |
6bbab0fe |
1091 | } |
1092 | |
1093 | |
1094 | static void game_changed_state(game_ui *ui, game_state *oldstate, |
1095 | game_state *newstate) |
1096 | { |
1097 | sel_clear(ui, newstate); |
faff1e07 |
1098 | |
1099 | /* |
1100 | * If the game state has just changed into an unplayable one |
1101 | * (either completed or impossible), we vanish the keyboard- |
1102 | * control cursor. |
1103 | */ |
1104 | if (newstate->complete || newstate->impossible) |
1105 | ui->displaysel = 0; |
6bbab0fe |
1106 | } |
1107 | |
df11cd4e |
1108 | static char *sel_movedesc(game_ui *ui, game_state *state) |
6bbab0fe |
1109 | { |
df11cd4e |
1110 | int i; |
1111 | char *ret, *sep, buf[80]; |
1112 | int retlen, retsize; |
6bbab0fe |
1113 | |
df11cd4e |
1114 | retsize = 256; |
1115 | ret = snewn(retsize, char); |
1116 | retlen = 0; |
1117 | ret[retlen++] = 'M'; |
1118 | sep = ""; |
6bbab0fe |
1119 | |
1120 | for (i = 0; i < state->n; i++) { |
1121 | if (ui->tiles[i] & TILE_SELECTED) { |
df11cd4e |
1122 | sprintf(buf, "%s%d", sep, i); |
1123 | sep = ","; |
1124 | if (retlen + strlen(buf) >= retsize) { |
1125 | retsize = retlen + strlen(buf) + 256; |
1126 | ret = sresize(ret, retsize, char); |
1127 | } |
1128 | strcpy(ret + retlen, buf); |
1129 | retlen += strlen(buf); |
1130 | |
6bbab0fe |
1131 | ui->tiles[i] &= ~TILE_SELECTED; |
1132 | } |
1133 | } |
1134 | ui->nselected = 0; |
df11cd4e |
1135 | |
1136 | assert(retlen < retsize); |
1137 | ret[retlen++] = '\0'; |
1138 | return sresize(ret, retlen, char); |
6bbab0fe |
1139 | } |
1140 | |
1141 | static void sel_expand(game_ui *ui, game_state *state, int tx, int ty) |
1142 | { |
1143 | int ns = 1, nadded, x, y, c; |
1144 | |
1145 | TILE(ui,tx,ty) |= TILE_SELECTED; |
6bbab0fe |
1146 | do { |
1147 | nadded = 0; |
1148 | |
1149 | for (x = 0; x < state->params.w; x++) { |
1150 | for (y = 0; y < state->params.h; y++) { |
1151 | if (x == tx && y == ty) continue; |
1152 | if (ISSEL(ui,x,y)) continue; |
1153 | |
1154 | c = COL(state,x,y); |
1155 | if ((x > 0) && |
1156 | ISSEL(ui,x-1,y) && COL(state,x-1,y) == c) { |
1157 | TILE(ui,x,y) |= TILE_SELECTED; |
1158 | nadded++; |
1159 | continue; |
1160 | } |
1161 | |
1162 | if ((x+1 < state->params.w) && |
1163 | ISSEL(ui,x+1,y) && COL(state,x+1,y) == c) { |
1164 | TILE(ui,x,y) |= TILE_SELECTED; |
1165 | nadded++; |
1166 | continue; |
1167 | } |
1168 | |
1169 | if ((y > 0) && |
1170 | ISSEL(ui,x,y-1) && COL(state,x,y-1) == c) { |
1171 | TILE(ui,x,y) |= TILE_SELECTED; |
1172 | nadded++; |
1173 | continue; |
1174 | } |
1175 | |
1176 | if ((y+1 < state->params.h) && |
1177 | ISSEL(ui,x,y+1) && COL(state,x,y+1) == c) { |
1178 | TILE(ui,x,y) |= TILE_SELECTED; |
1179 | nadded++; |
1180 | continue; |
1181 | } |
1182 | } |
1183 | } |
1184 | ns += nadded; |
6bbab0fe |
1185 | } while (nadded > 0); |
1186 | |
1187 | if (ns > 1) { |
1188 | ui->nselected = ns; |
1189 | } else { |
1190 | sel_clear(ui, state); |
1191 | } |
1192 | } |
1193 | |
1194 | static int sg_emptycol(game_state *ret, int x) |
1195 | { |
1196 | int y; |
1197 | for (y = 0; y < ret->params.h; y++) { |
1198 | if (COL(ret,x,y)) return 0; |
1199 | } |
1200 | return 1; |
1201 | } |
1202 | |
1203 | |
1204 | static void sg_snuggle(game_state *ret) |
1205 | { |
1206 | int x,y, ndone; |
1207 | |
1208 | /* make all unsupported tiles fall down. */ |
1209 | do { |
1210 | ndone = 0; |
1211 | for (x = 0; x < ret->params.w; x++) { |
1212 | for (y = ret->params.h-1; y > 0; y--) { |
1213 | if (COL(ret,x,y) != 0) continue; |
1214 | if (COL(ret,x,y-1) != 0) { |
1215 | SWAPTILE(ret,x,y,x,y-1); |
1216 | ndone++; |
1217 | } |
1218 | } |
1219 | } |
1220 | } while (ndone); |
1221 | |
1222 | /* shuffle all columns as far left as they can go. */ |
1223 | do { |
1224 | ndone = 0; |
1225 | for (x = 0; x < ret->params.w-1; x++) { |
1226 | if (sg_emptycol(ret,x) && !sg_emptycol(ret,x+1)) { |
6bbab0fe |
1227 | ndone++; |
1228 | for (y = 0; y < ret->params.h; y++) { |
1229 | SWAPTILE(ret,x,y,x+1,y); |
1230 | } |
1231 | } |
1232 | } |
1233 | } while (ndone); |
1234 | } |
1235 | |
1236 | static void sg_check(game_state *ret) |
1237 | { |
1238 | int x,y, complete = 1, impossible = 1; |
1239 | |
1240 | for (x = 0; x < ret->params.w; x++) { |
1241 | for (y = 0; y < ret->params.h; y++) { |
1242 | if (COL(ret,x,y) == 0) |
1243 | continue; |
1244 | complete = 0; |
1245 | if (x+1 < ret->params.w) { |
1246 | if (COL(ret,x,y) == COL(ret,x+1,y)) |
1247 | impossible = 0; |
1248 | } |
1249 | if (y+1 < ret->params.h) { |
1250 | if (COL(ret,x,y) == COL(ret,x,y+1)) |
1251 | impossible = 0; |
1252 | } |
1253 | } |
1254 | } |
1255 | ret->complete = complete; |
1256 | ret->impossible = impossible; |
1257 | } |
1258 | |
1259 | struct game_drawstate { |
1260 | int started, bgcolour; |
1261 | int tileinner, tilegap; |
1262 | int *tiles; /* contains colour and SELECTED. */ |
1263 | }; |
1264 | |
df11cd4e |
1265 | static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds, |
1266 | int x, int y, int button) |
6bbab0fe |
1267 | { |
1268 | int tx, ty; |
df11cd4e |
1269 | char *ret = ""; |
6bbab0fe |
1270 | |
f1359c5e |
1271 | ui->displaysel = 0; |
1272 | |
1273 | if (button == RIGHT_BUTTON || button == LEFT_BUTTON) { |
1274 | tx = FROMCOORD(x); ty= FROMCOORD(y); |
1275 | } else if (button == CURSOR_UP || button == CURSOR_DOWN || |
1276 | button == CURSOR_LEFT || button == CURSOR_RIGHT) { |
1277 | int dx = 0, dy = 0; |
1278 | ui->displaysel = 1; |
1279 | dx = (button == CURSOR_LEFT) ? -1 : ((button == CURSOR_RIGHT) ? +1 : 0); |
1280 | dy = (button == CURSOR_DOWN) ? +1 : ((button == CURSOR_UP) ? -1 : 0); |
df11cd4e |
1281 | ui->xsel = (ui->xsel + state->params.w + dx) % state->params.w; |
1282 | ui->ysel = (ui->ysel + state->params.h + dy) % state->params.h; |
f1359c5e |
1283 | return ret; |
1284 | } else if (button == CURSOR_SELECT || button == ' ' || button == '\r' || |
1285 | button == '\n') { |
1286 | ui->displaysel = 1; |
1287 | tx = ui->xsel; |
1288 | ty = ui->ysel; |
f1359c5e |
1289 | } else |
6bbab0fe |
1290 | return NULL; |
1291 | |
df11cd4e |
1292 | if (tx < 0 || tx >= state->params.w || ty < 0 || ty >= state->params.h) |
6bbab0fe |
1293 | return NULL; |
df11cd4e |
1294 | if (COL(state, tx, ty) == 0) return NULL; |
6bbab0fe |
1295 | |
1296 | if (ISSEL(ui,tx,ty)) { |
1297 | if (button == RIGHT_BUTTON) |
df11cd4e |
1298 | sel_clear(ui, state); |
faff1e07 |
1299 | else |
df11cd4e |
1300 | ret = sel_movedesc(ui, state); |
6bbab0fe |
1301 | } else { |
df11cd4e |
1302 | sel_clear(ui, state); /* might be no-op */ |
1303 | sel_expand(ui, state, tx, ty); |
6bbab0fe |
1304 | } |
1305 | |
1306 | return ret; |
1307 | } |
1308 | |
df11cd4e |
1309 | static game_state *execute_move(game_state *from, char *move) |
1310 | { |
1311 | int i, n; |
1312 | game_state *ret; |
1313 | |
1314 | if (move[0] == 'M') { |
1315 | ret = dup_game(from); |
1316 | |
1317 | n = 0; |
1318 | move++; |
1319 | |
1320 | while (*move) { |
1321 | i = atoi(move); |
1322 | if (i < 0 || i >= ret->n) { |
1323 | free_game(ret); |
1324 | return NULL; |
1325 | } |
1326 | n++; |
1327 | ret->tiles[i] = 0; |
1328 | |
1329 | while (*move && isdigit((unsigned char)*move)) move++; |
1330 | if (*move == ',') move++; |
1331 | } |
1332 | |
1333 | ret->score += npoints(&ret->params, n); |
1334 | |
1335 | sg_snuggle(ret); /* shifts blanks down and to the left */ |
1336 | sg_check(ret); /* checks for completeness or impossibility */ |
1337 | |
1338 | return ret; |
1339 | } else |
1340 | return NULL; /* couldn't parse move string */ |
1341 | } |
1342 | |
6bbab0fe |
1343 | /* ---------------------------------------------------------------------- |
1344 | * Drawing routines. |
1345 | */ |
1346 | |
dafd6cf6 |
1347 | static void game_set_size(drawing *dr, game_drawstate *ds, |
1348 | game_params *params, int tilesize) |
1f3ee4ee |
1349 | { |
6bbab0fe |
1350 | ds->tilegap = 2; |
1f3ee4ee |
1351 | ds->tileinner = tilesize - ds->tilegap; |
1352 | } |
6bbab0fe |
1353 | |
1f3ee4ee |
1354 | static void game_compute_size(game_params *params, int tilesize, |
1355 | int *x, int *y) |
1356 | { |
1357 | /* Ick: fake up tile size variables for macro expansion purposes */ |
1358 | game_drawstate ads, *ds = &ads; |
dafd6cf6 |
1359 | game_set_size(NULL, ds, params, tilesize); |
6bbab0fe |
1360 | |
1361 | *x = TILE_SIZE * params->w + 2 * BORDER - TILE_GAP; |
1362 | *y = TILE_SIZE * params->h + 2 * BORDER - TILE_GAP; |
1363 | } |
1364 | |
8266f3fc |
1365 | static float *game_colours(frontend *fe, int *ncolours) |
6bbab0fe |
1366 | { |
1367 | float *ret = snewn(3 * NCOLOURS, float); |
1368 | |
1369 | frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]); |
1370 | |
1371 | ret[COL_1 * 3 + 0] = 0.0F; |
1372 | ret[COL_1 * 3 + 1] = 0.0F; |
1373 | ret[COL_1 * 3 + 2] = 1.0F; |
1374 | |
1375 | ret[COL_2 * 3 + 0] = 0.0F; |
1376 | ret[COL_2 * 3 + 1] = 0.5F; |
1377 | ret[COL_2 * 3 + 2] = 0.0F; |
1378 | |
1379 | ret[COL_3 * 3 + 0] = 1.0F; |
1380 | ret[COL_3 * 3 + 1] = 0.0F; |
1381 | ret[COL_3 * 3 + 2] = 0.0F; |
1382 | |
367cfc41 |
1383 | ret[COL_4 * 3 + 0] = 1.0F; |
1384 | ret[COL_4 * 3 + 1] = 1.0F; |
1385 | ret[COL_4 * 3 + 2] = 0.0F; |
6bbab0fe |
1386 | |
367cfc41 |
1387 | ret[COL_5 * 3 + 0] = 1.0F; |
1388 | ret[COL_5 * 3 + 1] = 0.0F; |
1389 | ret[COL_5 * 3 + 2] = 1.0F; |
6bbab0fe |
1390 | |
367cfc41 |
1391 | ret[COL_6 * 3 + 0] = 0.0F; |
1392 | ret[COL_6 * 3 + 1] = 1.0F; |
1393 | ret[COL_6 * 3 + 2] = 1.0F; |
6bbab0fe |
1394 | |
367cfc41 |
1395 | ret[COL_7 * 3 + 0] = 0.5F; |
1396 | ret[COL_7 * 3 + 1] = 0.5F; |
1397 | ret[COL_7 * 3 + 2] = 1.0F; |
6bbab0fe |
1398 | |
367cfc41 |
1399 | ret[COL_8 * 3 + 0] = 0.5F; |
1400 | ret[COL_8 * 3 + 1] = 1.0F; |
1401 | ret[COL_8 * 3 + 2] = 0.5F; |
6bbab0fe |
1402 | |
367cfc41 |
1403 | ret[COL_9 * 3 + 0] = 1.0F; |
1404 | ret[COL_9 * 3 + 1] = 0.5F; |
1405 | ret[COL_9 * 3 + 2] = 0.5F; |
6bbab0fe |
1406 | |
1407 | ret[COL_IMPOSSIBLE * 3 + 0] = 0.0F; |
1408 | ret[COL_IMPOSSIBLE * 3 + 1] = 0.0F; |
1409 | ret[COL_IMPOSSIBLE * 3 + 2] = 0.0F; |
1410 | |
1411 | ret[COL_SEL * 3 + 0] = 1.0F; |
1412 | ret[COL_SEL * 3 + 1] = 1.0F; |
1413 | ret[COL_SEL * 3 + 2] = 1.0F; |
1414 | |
1415 | ret[COL_HIGHLIGHT * 3 + 0] = 1.0F; |
1416 | ret[COL_HIGHLIGHT * 3 + 1] = 1.0F; |
1417 | ret[COL_HIGHLIGHT * 3 + 2] = 1.0F; |
1418 | |
1419 | ret[COL_LOWLIGHT * 3 + 0] = ret[COL_BACKGROUND * 3 + 0] * 2.0 / 3.0; |
1420 | ret[COL_LOWLIGHT * 3 + 1] = ret[COL_BACKGROUND * 3 + 1] * 2.0 / 3.0; |
1421 | ret[COL_LOWLIGHT * 3 + 2] = ret[COL_BACKGROUND * 3 + 2] * 2.0 / 3.0; |
1422 | |
1423 | *ncolours = NCOLOURS; |
1424 | return ret; |
1425 | } |
1426 | |
dafd6cf6 |
1427 | static game_drawstate *game_new_drawstate(drawing *dr, game_state *state) |
6bbab0fe |
1428 | { |
1429 | struct game_drawstate *ds = snew(struct game_drawstate); |
1430 | int i; |
1431 | |
1432 | ds->started = 0; |
1433 | ds->tileinner = ds->tilegap = 0; /* not decided yet */ |
1434 | ds->tiles = snewn(state->n, int); |
7dfe3b1f |
1435 | ds->bgcolour = -1; |
6bbab0fe |
1436 | for (i = 0; i < state->n; i++) |
1437 | ds->tiles[i] = -1; |
1438 | |
1439 | return ds; |
1440 | } |
1441 | |
dafd6cf6 |
1442 | static void game_free_drawstate(drawing *dr, game_drawstate *ds) |
6bbab0fe |
1443 | { |
1444 | sfree(ds->tiles); |
1445 | sfree(ds); |
1446 | } |
1447 | |
1448 | /* Drawing routing for the tile at (x,y) is responsible for drawing |
1449 | * itself and the gaps to its right and below. If we're the same colour |
1450 | * as the tile to our right, then we fill in the gap; ditto below, and if |
1451 | * both then we fill the teeny tiny square in the corner as well. |
1452 | */ |
1453 | |
dafd6cf6 |
1454 | static void tile_redraw(drawing *dr, game_drawstate *ds, |
6bbab0fe |
1455 | int x, int y, int dright, int dbelow, |
d951510d |
1456 | int tile, int bgcolour) |
6bbab0fe |
1457 | { |
1458 | int outer = bgcolour, inner = outer, col = tile & TILE_COLMASK; |
1459 | |
1460 | if (col) { |
d951510d |
1461 | if (tile & TILE_IMPOSSIBLE) { |
6bbab0fe |
1462 | outer = col; |
1463 | inner = COL_IMPOSSIBLE; |
1464 | } else if (tile & TILE_SELECTED) { |
1465 | outer = COL_SEL; |
1466 | inner = col; |
1467 | } else { |
1468 | outer = inner = col; |
1469 | } |
1470 | } |
dafd6cf6 |
1471 | draw_rect(dr, COORD(x), COORD(y), TILE_INNER, TILE_INNER, outer); |
1472 | draw_rect(dr, COORD(x)+TILE_INNER/4, COORD(y)+TILE_INNER/4, |
6bbab0fe |
1473 | TILE_INNER/2, TILE_INNER/2, inner); |
1474 | |
1475 | if (dright) |
dafd6cf6 |
1476 | draw_rect(dr, COORD(x)+TILE_INNER, COORD(y), TILE_GAP, TILE_INNER, |
6bbab0fe |
1477 | (tile & TILE_JOINRIGHT) ? outer : bgcolour); |
1478 | if (dbelow) |
dafd6cf6 |
1479 | draw_rect(dr, COORD(x), COORD(y)+TILE_INNER, TILE_INNER, TILE_GAP, |
6bbab0fe |
1480 | (tile & TILE_JOINDOWN) ? outer : bgcolour); |
1481 | if (dright && dbelow) |
dafd6cf6 |
1482 | draw_rect(dr, COORD(x)+TILE_INNER, COORD(y)+TILE_INNER, TILE_GAP, TILE_GAP, |
6bbab0fe |
1483 | (tile & TILE_JOINDIAG) ? outer : bgcolour); |
1484 | |
f1359c5e |
1485 | if (tile & TILE_HASSEL) { |
1486 | int sx = COORD(x)+2, sy = COORD(y)+2, ssz = TILE_INNER-5; |
1487 | int scol = (outer == COL_SEL) ? COL_LOWLIGHT : COL_HIGHLIGHT; |
dafd6cf6 |
1488 | draw_line(dr, sx, sy, sx+ssz, sy, scol); |
1489 | draw_line(dr, sx+ssz, sy, sx+ssz, sy+ssz, scol); |
1490 | draw_line(dr, sx+ssz, sy+ssz, sx, sy+ssz, scol); |
1491 | draw_line(dr, sx, sy+ssz, sx, sy, scol); |
f1359c5e |
1492 | } |
1493 | |
dafd6cf6 |
1494 | draw_update(dr, COORD(x), COORD(y), TILE_SIZE, TILE_SIZE); |
6bbab0fe |
1495 | } |
1496 | |
dafd6cf6 |
1497 | static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate, |
6bbab0fe |
1498 | game_state *state, int dir, game_ui *ui, |
1499 | float animtime, float flashtime) |
1500 | { |
1501 | int bgcolour, x, y; |
1502 | |
6bbab0fe |
1503 | /* This was entirely cloned from fifteen.c; it should probably be |
1504 | * moved into some generic 'draw-recessed-rectangle' utility fn. */ |
1505 | if (!ds->started) { |
1506 | int coords[10]; |
1507 | |
dafd6cf6 |
1508 | draw_rect(dr, 0, 0, |
6bbab0fe |
1509 | TILE_SIZE * state->params.w + 2 * BORDER, |
1510 | TILE_SIZE * state->params.h + 2 * BORDER, COL_BACKGROUND); |
dafd6cf6 |
1511 | draw_update(dr, 0, 0, |
6bbab0fe |
1512 | TILE_SIZE * state->params.w + 2 * BORDER, |
1513 | TILE_SIZE * state->params.h + 2 * BORDER); |
1514 | |
1515 | /* |
1516 | * Recessed area containing the whole puzzle. |
1517 | */ |
1518 | coords[0] = COORD(state->params.w) + HIGHLIGHT_WIDTH - 1 - TILE_GAP; |
1519 | coords[1] = COORD(state->params.h) + HIGHLIGHT_WIDTH - 1 - TILE_GAP; |
1520 | coords[2] = COORD(state->params.w) + HIGHLIGHT_WIDTH - 1 - TILE_GAP; |
1521 | coords[3] = COORD(0) - HIGHLIGHT_WIDTH; |
1522 | coords[4] = coords[2] - TILE_SIZE; |
1523 | coords[5] = coords[3] + TILE_SIZE; |
1524 | coords[8] = COORD(0) - HIGHLIGHT_WIDTH; |
1525 | coords[9] = COORD(state->params.h) + HIGHLIGHT_WIDTH - 1 - TILE_GAP; |
1526 | coords[6] = coords[8] + TILE_SIZE; |
1527 | coords[7] = coords[9] - TILE_SIZE; |
dafd6cf6 |
1528 | draw_polygon(dr, coords, 5, COL_HIGHLIGHT, COL_HIGHLIGHT); |
6bbab0fe |
1529 | |
1530 | coords[1] = COORD(0) - HIGHLIGHT_WIDTH; |
1531 | coords[0] = COORD(0) - HIGHLIGHT_WIDTH; |
dafd6cf6 |
1532 | draw_polygon(dr, coords, 5, COL_LOWLIGHT, COL_LOWLIGHT); |
6bbab0fe |
1533 | |
1534 | ds->started = 1; |
1535 | } |
1536 | |
1537 | if (flashtime > 0.0) { |
1538 | int frame = (int)(flashtime / FLASH_FRAME); |
1539 | bgcolour = (frame % 2 ? COL_LOWLIGHT : COL_HIGHLIGHT); |
1540 | } else |
1541 | bgcolour = COL_BACKGROUND; |
1542 | |
1543 | for (x = 0; x < state->params.w; x++) { |
1544 | for (y = 0; y < state->params.h; y++) { |
1545 | int i = (state->params.w * y) + x; |
1546 | int col = COL(state,x,y), tile = col; |
1547 | int dright = (x+1 < state->params.w); |
1548 | int dbelow = (y+1 < state->params.h); |
1549 | |
1550 | tile |= ISSEL(ui,x,y); |
d951510d |
1551 | if (state->impossible) |
1552 | tile |= TILE_IMPOSSIBLE; |
6bbab0fe |
1553 | if (dright && COL(state,x+1,y) == col) |
1554 | tile |= TILE_JOINRIGHT; |
1555 | if (dbelow && COL(state,x,y+1) == col) |
1556 | tile |= TILE_JOINDOWN; |
1557 | if ((tile & TILE_JOINRIGHT) && (tile & TILE_JOINDOWN) && |
1558 | COL(state,x+1,y+1) == col) |
1559 | tile |= TILE_JOINDIAG; |
1560 | |
f1359c5e |
1561 | if (ui->displaysel && ui->xsel == x && ui->ysel == y) |
1562 | tile |= TILE_HASSEL; |
1563 | |
6bbab0fe |
1564 | /* For now we're never expecting oldstate at all (because we have |
1565 | * no animation); when we do we might well want to be looking |
1566 | * at the tile colours from oldstate, not state. */ |
1567 | if ((oldstate && COL(oldstate,x,y) != col) || |
6bbab0fe |
1568 | (ds->bgcolour != bgcolour) || |
1569 | (tile != ds->tiles[i])) { |
dafd6cf6 |
1570 | tile_redraw(dr, ds, x, y, dright, dbelow, tile, bgcolour); |
6bbab0fe |
1571 | ds->tiles[i] = tile; |
1572 | } |
1573 | } |
1574 | } |
1575 | ds->bgcolour = bgcolour; |
1576 | |
1577 | { |
1578 | char status[255], score[80]; |
1579 | |
1580 | sprintf(score, "Score: %d", state->score); |
1581 | |
1582 | if (state->complete) |
1583 | sprintf(status, "COMPLETE! %s", score); |
1584 | else if (state->impossible) |
1585 | sprintf(status, "Cannot move! %s", score); |
1586 | else if (ui->nselected) |
1587 | sprintf(status, "%s Selected: %d (%d)", |
1588 | score, ui->nselected, npoints(&state->params, ui->nselected)); |
1589 | else |
1590 | sprintf(status, "%s", score); |
dafd6cf6 |
1591 | status_bar(dr, status); |
6bbab0fe |
1592 | } |
1593 | } |
1594 | |
1595 | static float game_anim_length(game_state *oldstate, game_state *newstate, |
1596 | int dir, game_ui *ui) |
1597 | { |
1598 | return 0.0F; |
1599 | } |
1600 | |
1601 | static float game_flash_length(game_state *oldstate, game_state *newstate, |
1602 | int dir, game_ui *ui) |
1603 | { |
1604 | if ((!oldstate->complete && newstate->complete) || |
1605 | (!oldstate->impossible && newstate->impossible)) |
1606 | return 2 * FLASH_FRAME; |
1607 | else |
1608 | return 0.0F; |
1609 | } |
1610 | |
4d08de49 |
1611 | static int game_timing_state(game_state *state, game_ui *ui) |
6bbab0fe |
1612 | { |
1613 | return TRUE; |
1614 | } |
1615 | |
dafd6cf6 |
1616 | static void game_print_size(game_params *params, float *x, float *y) |
1617 | { |
1618 | } |
1619 | |
1620 | static void game_print(drawing *dr, game_state *state, int tilesize) |
1621 | { |
1622 | } |
1623 | |
6bbab0fe |
1624 | #ifdef COMBINED |
1625 | #define thegame samegame |
1626 | #endif |
1627 | |
1628 | const struct game thegame = { |
f3cc3e50 |
1629 | "Same Game", "games.samegame", |
6bbab0fe |
1630 | default_params, |
1631 | game_fetch_preset, |
1632 | decode_params, |
1633 | encode_params, |
1634 | free_params, |
1635 | dup_params, |
1636 | TRUE, game_configure, custom_params, |
1637 | validate_params, |
1638 | new_game_desc, |
6bbab0fe |
1639 | validate_desc, |
1640 | new_game, |
1641 | dup_game, |
1642 | free_game, |
1643 | FALSE, solve_game, |
1644 | TRUE, game_text_format, |
1645 | new_ui, |
1646 | free_ui, |
ae8290c6 |
1647 | encode_ui, |
1648 | decode_ui, |
6bbab0fe |
1649 | game_changed_state, |
df11cd4e |
1650 | interpret_move, |
1651 | execute_move, |
1f3ee4ee |
1652 | PREFERRED_TILE_SIZE, game_compute_size, game_set_size, |
6bbab0fe |
1653 | game_colours, |
1654 | game_new_drawstate, |
1655 | game_free_drawstate, |
1656 | game_redraw, |
1657 | game_anim_length, |
1658 | game_flash_length, |
dafd6cf6 |
1659 | FALSE, FALSE, game_print_size, game_print, |
ac9f41c4 |
1660 | TRUE, /* wants_statusbar */ |
6bbab0fe |
1661 | FALSE, game_timing_state, |
2705d374 |
1662 | 0, /* flags */ |
6bbab0fe |
1663 | }; |