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