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