4efb3868 |
1 | /* |
2 | * fifteen.c: standard 15-puzzle. |
3 | */ |
4 | |
5 | #include <stdio.h> |
6 | #include <stdlib.h> |
7 | #include <string.h> |
8 | #include <assert.h> |
9 | #include <math.h> |
10 | |
11 | #include "puzzles.h" |
12 | |
13 | const char *const game_name = "Fifteen"; |
c8230524 |
14 | const int game_can_configure = TRUE; |
4efb3868 |
15 | |
16 | #define TILE_SIZE 48 |
17 | #define BORDER (TILE_SIZE / 2) |
18 | #define HIGHLIGHT_WIDTH (TILE_SIZE / 20) |
19 | #define COORD(x) ( (x) * TILE_SIZE + BORDER ) |
20 | #define FROMCOORD(x) ( ((x) - BORDER + TILE_SIZE) / TILE_SIZE - 1 ) |
21 | |
22 | #define ANIM_TIME 0.1F |
23 | #define FLASH_FRAME 0.1F |
24 | |
25 | #define X(state, i) ( (i) % (state)->w ) |
26 | #define Y(state, i) ( (i) / (state)->w ) |
27 | #define C(state, x, y) ( (y) * (state)->w + (x) ) |
28 | |
29 | enum { |
30 | COL_BACKGROUND, |
31 | COL_TEXT, |
32 | COL_HIGHLIGHT, |
33 | COL_LOWLIGHT, |
34 | NCOLOURS |
35 | }; |
36 | |
37 | struct game_params { |
38 | int w, h; |
39 | }; |
40 | |
41 | struct game_state { |
42 | int w, h, n; |
43 | int *tiles; |
44 | int gap_pos; |
45 | int completed; |
fd1a1a2b |
46 | int movecount; |
4efb3868 |
47 | }; |
48 | |
49 | game_params *default_params(void) |
50 | { |
51 | game_params *ret = snew(game_params); |
52 | |
53 | ret->w = ret->h = 4; |
54 | |
55 | return ret; |
56 | } |
57 | |
58 | int game_fetch_preset(int i, char **name, game_params **params) |
59 | { |
60 | return FALSE; |
61 | } |
62 | |
63 | void free_params(game_params *params) |
64 | { |
65 | sfree(params); |
66 | } |
67 | |
68 | game_params *dup_params(game_params *params) |
69 | { |
70 | game_params *ret = snew(game_params); |
71 | *ret = *params; /* structure copy */ |
72 | return ret; |
73 | } |
74 | |
c8230524 |
75 | config_item *game_configure(game_params *params) |
76 | { |
77 | config_item *ret; |
78 | char buf[80]; |
79 | |
80 | ret = snewn(3, config_item); |
81 | |
82 | ret[0].name = "Width"; |
95709966 |
83 | ret[0].type = C_STRING; |
c8230524 |
84 | sprintf(buf, "%d", params->w); |
85 | ret[0].sval = dupstr(buf); |
86 | ret[0].ival = 0; |
87 | |
88 | ret[1].name = "Height"; |
95709966 |
89 | ret[1].type = C_STRING; |
c8230524 |
90 | sprintf(buf, "%d", params->h); |
91 | ret[1].sval = dupstr(buf); |
92 | ret[1].ival = 0; |
93 | |
94 | ret[2].name = NULL; |
95709966 |
95 | ret[2].type = C_END; |
c8230524 |
96 | ret[2].sval = NULL; |
97 | ret[2].ival = 0; |
98 | |
99 | return ret; |
100 | } |
101 | |
102 | game_params *custom_params(config_item *cfg) |
103 | { |
104 | game_params *ret = snew(game_params); |
105 | |
106 | ret->w = atoi(cfg[0].sval); |
107 | ret->h = atoi(cfg[1].sval); |
108 | |
109 | return ret; |
110 | } |
111 | |
112 | char *validate_params(game_params *params) |
113 | { |
114 | if (params->w < 2 && params->h < 2) |
115 | return "Width and height must both be at least two"; |
116 | |
117 | return NULL; |
118 | } |
119 | |
4efb3868 |
120 | int perm_parity(int *perm, int n) |
121 | { |
122 | int i, j, ret; |
123 | |
124 | ret = 0; |
125 | |
126 | for (i = 0; i < n-1; i++) |
127 | for (j = i+1; j < n; j++) |
128 | if (perm[i] > perm[j]) |
129 | ret = !ret; |
130 | |
131 | return ret; |
132 | } |
133 | |
134 | char *new_game_seed(game_params *params) |
135 | { |
136 | int gap, n, i, x; |
137 | int x1, x2, p1, p2, parity; |
138 | int *tiles, *used; |
139 | char *ret; |
140 | int retlen; |
141 | |
142 | n = params->w * params->h; |
143 | |
144 | tiles = snewn(n, int); |
145 | used = snewn(n, int); |
146 | |
147 | for (i = 0; i < n; i++) { |
148 | tiles[i] = -1; |
149 | used[i] = FALSE; |
150 | } |
151 | |
152 | gap = rand_upto(n); |
153 | tiles[gap] = 0; |
154 | used[0] = TRUE; |
155 | |
156 | /* |
157 | * Place everything else except the last two tiles. |
158 | */ |
159 | for (x = 0, i = n-1; i > 2; i--) { |
160 | int k = rand_upto(i); |
161 | int j; |
162 | |
163 | for (j = 0; j < n; j++) |
164 | if (!used[j] && (k-- == 0)) |
165 | break; |
166 | |
167 | assert(j < n && !used[j]); |
168 | used[j] = TRUE; |
169 | |
170 | while (tiles[x] >= 0) |
171 | x++; |
172 | assert(x < n); |
173 | tiles[x] = j; |
174 | } |
175 | |
176 | /* |
177 | * Find the last two locations, and the last two pieces. |
178 | */ |
179 | while (tiles[x] >= 0) |
180 | x++; |
181 | assert(x < n); |
182 | x1 = x; |
183 | x++; |
184 | while (tiles[x] >= 0) |
185 | x++; |
186 | assert(x < n); |
187 | x2 = x; |
188 | |
189 | for (i = 0; i < n; i++) |
190 | if (!used[i]) |
191 | break; |
192 | p1 = i; |
193 | for (i = p1+1; i < n; i++) |
194 | if (!used[i]) |
195 | break; |
196 | p2 = i; |
197 | |
198 | /* |
199 | * Determine the required parity of the overall permutation. |
200 | * This is the XOR of: |
201 | * |
202 | * - The chessboard parity ((x^y)&1) of the gap square. The |
203 | * bottom right, and therefore also the top left, count as |
204 | * even. |
205 | * |
206 | * - The parity of n. (The target permutation is 1,...,n-1,0 |
207 | * rather than 0,...,n-1; this is a cyclic permutation of |
208 | * the starting point and hence is odd iff n is even.) |
209 | */ |
210 | parity = (X(params, gap) ^ Y(params, gap) ^ (n+1)) & 1; |
211 | |
212 | /* |
213 | * Try the last two tiles one way round. If that fails, swap |
214 | * them. |
215 | */ |
216 | tiles[x1] = p1; |
217 | tiles[x2] = p2; |
218 | if (perm_parity(tiles, n) != parity) { |
219 | tiles[x1] = p2; |
220 | tiles[x2] = p1; |
221 | assert(perm_parity(tiles, n) == parity); |
222 | } |
223 | |
224 | /* |
225 | * Now construct the game seed, by describing the tile array as |
226 | * a simple sequence of comma-separated integers. |
227 | */ |
228 | ret = NULL; |
229 | retlen = 0; |
230 | for (i = 0; i < n; i++) { |
231 | char buf[80]; |
232 | int k; |
233 | |
234 | k = sprintf(buf, "%d,", tiles[i]); |
235 | |
236 | ret = sresize(ret, retlen + k + 1, char); |
237 | strcpy(ret + retlen, buf); |
238 | retlen += k; |
239 | } |
240 | ret[retlen-1] = '\0'; /* delete last comma */ |
241 | |
242 | sfree(tiles); |
243 | sfree(used); |
244 | |
245 | return ret; |
246 | } |
247 | |
248 | game_state *new_game(game_params *params, char *seed) |
249 | { |
250 | game_state *state = snew(game_state); |
251 | int i; |
252 | char *p; |
253 | |
254 | state->w = params->w; |
255 | state->h = params->h; |
256 | state->n = params->w * params->h; |
257 | state->tiles = snewn(state->n, int); |
258 | |
259 | state->gap_pos = 0; |
260 | p = seed; |
261 | i = 0; |
262 | for (i = 0; i < state->n; i++) { |
263 | assert(*p); |
264 | state->tiles[i] = atoi(p); |
265 | if (state->tiles[i] == 0) |
266 | state->gap_pos = i; |
267 | while (*p && *p != ',') |
268 | p++; |
269 | if (*p) p++; /* eat comma */ |
270 | } |
271 | assert(!*p); |
272 | assert(state->tiles[state->gap_pos] == 0); |
273 | |
fd1a1a2b |
274 | state->completed = state->movecount = 0; |
4efb3868 |
275 | |
276 | return state; |
277 | } |
278 | |
279 | game_state *dup_game(game_state *state) |
280 | { |
281 | game_state *ret = snew(game_state); |
282 | |
283 | ret->w = state->w; |
284 | ret->h = state->h; |
285 | ret->n = state->n; |
286 | ret->tiles = snewn(state->w * state->h, int); |
287 | memcpy(ret->tiles, state->tiles, state->w * state->h * sizeof(int)); |
288 | ret->gap_pos = state->gap_pos; |
289 | ret->completed = state->completed; |
fd1a1a2b |
290 | ret->movecount = state->movecount; |
4efb3868 |
291 | |
292 | return ret; |
293 | } |
294 | |
295 | void free_game(game_state *state) |
296 | { |
297 | sfree(state); |
298 | } |
299 | |
300 | game_state *make_move(game_state *from, int x, int y, int button) |
301 | { |
302 | int gx, gy, dx, dy, ux, uy, up, p; |
303 | game_state *ret; |
304 | |
305 | gx = X(from, from->gap_pos); |
306 | gy = Y(from, from->gap_pos); |
307 | |
308 | if (button == CURSOR_RIGHT && gx > 0) |
309 | dx = gx - 1, dy = gy; |
310 | else if (button == CURSOR_LEFT && gx < from->w-1) |
311 | dx = gx + 1, dy = gy; |
312 | else if (button == CURSOR_DOWN && gy > 0) |
313 | dy = gy - 1, dx = gx; |
314 | else if (button == CURSOR_UP && gy < from->h-1) |
315 | dy = gy + 1, dx = gx; |
316 | else if (button == LEFT_BUTTON) { |
317 | dx = FROMCOORD(x); |
318 | dy = FROMCOORD(y); |
319 | if (dx < 0 || dx >= from->w || dy < 0 || dy >= from->h) |
320 | return NULL; /* out of bounds */ |
321 | /* |
322 | * Any click location should be equal to the gap location |
323 | * in _precisely_ one coordinate. |
324 | */ |
325 | if ((dx == gx && dy == gy) || (dx != gx && dy != gy)) |
326 | return NULL; |
327 | } else |
328 | return NULL; /* no move */ |
329 | |
330 | /* |
331 | * Find the unit displacement from the original gap |
332 | * position towards this one. |
333 | */ |
334 | ux = (dx < gx ? -1 : dx > gx ? +1 : 0); |
335 | uy = (dy < gy ? -1 : dy > gy ? +1 : 0); |
336 | up = C(from, ux, uy); |
337 | |
338 | ret = dup_game(from); |
339 | |
340 | ret->gap_pos = C(from, dx, dy); |
341 | assert(ret->gap_pos >= 0 && ret->gap_pos < ret->n); |
342 | |
343 | ret->tiles[ret->gap_pos] = 0; |
344 | |
345 | for (p = from->gap_pos; p != ret->gap_pos; p += up) { |
346 | assert(p >= 0 && p < from->n); |
347 | ret->tiles[p] = from->tiles[p + up]; |
fd1a1a2b |
348 | ret->movecount++; |
4efb3868 |
349 | } |
350 | |
351 | /* |
352 | * See if the game has been completed. |
353 | */ |
354 | if (!ret->completed) { |
fd1a1a2b |
355 | ret->completed = ret->movecount; |
4efb3868 |
356 | for (p = 0; p < ret->n; p++) |
357 | if (ret->tiles[p] != (p < ret->n-1 ? p+1 : 0)) |
fd1a1a2b |
358 | ret->completed = 0; |
4efb3868 |
359 | } |
360 | |
361 | return ret; |
362 | } |
363 | |
364 | /* ---------------------------------------------------------------------- |
365 | * Drawing routines. |
366 | */ |
367 | |
368 | struct game_drawstate { |
369 | int started; |
370 | int w, h, bgcolour; |
371 | int *tiles; |
372 | }; |
373 | |
374 | void game_size(game_params *params, int *x, int *y) |
375 | { |
376 | *x = TILE_SIZE * params->w + 2 * BORDER; |
377 | *y = TILE_SIZE * params->h + 2 * BORDER; |
378 | } |
379 | |
380 | float *game_colours(frontend *fe, game_state *state, int *ncolours) |
381 | { |
382 | float *ret = snewn(3 * NCOLOURS, float); |
383 | int i; |
384 | float max; |
385 | |
386 | frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]); |
387 | |
388 | /* |
389 | * Drop the background colour so that the highlight is |
390 | * noticeably brighter than it while still being under 1. |
391 | */ |
392 | max = ret[COL_BACKGROUND*3]; |
393 | for (i = 1; i < 3; i++) |
394 | if (ret[COL_BACKGROUND*3+i] > max) |
395 | max = ret[COL_BACKGROUND*3+i]; |
396 | if (max * 1.2F > 1.0F) { |
397 | for (i = 0; i < 3; i++) |
398 | ret[COL_BACKGROUND*3+i] /= (max * 1.2F); |
399 | } |
400 | |
401 | for (i = 0; i < 3; i++) { |
402 | ret[COL_HIGHLIGHT * 3 + i] = ret[COL_BACKGROUND * 3 + i] * 1.2F; |
403 | ret[COL_LOWLIGHT * 3 + i] = ret[COL_BACKGROUND * 3 + i] * 0.8F; |
404 | ret[COL_TEXT * 3 + i] = 0.0; |
405 | } |
406 | |
407 | *ncolours = NCOLOURS; |
408 | return ret; |
409 | } |
410 | |
411 | game_drawstate *game_new_drawstate(game_state *state) |
412 | { |
413 | struct game_drawstate *ds = snew(struct game_drawstate); |
414 | int i; |
415 | |
416 | ds->started = FALSE; |
417 | ds->w = state->w; |
418 | ds->h = state->h; |
419 | ds->bgcolour = COL_BACKGROUND; |
420 | ds->tiles = snewn(ds->w*ds->h, int); |
421 | for (i = 0; i < ds->w*ds->h; i++) |
422 | ds->tiles[i] = -1; |
423 | |
424 | return ds; |
425 | } |
426 | |
427 | void game_free_drawstate(game_drawstate *ds) |
428 | { |
429 | sfree(ds->tiles); |
430 | sfree(ds); |
431 | } |
432 | |
433 | static void draw_tile(frontend *fe, game_state *state, int x, int y, |
434 | int tile, int flash_colour) |
435 | { |
436 | if (tile == 0) { |
437 | draw_rect(fe, x, y, TILE_SIZE, TILE_SIZE, |
438 | flash_colour); |
439 | } else { |
440 | int coords[6]; |
441 | char str[40]; |
442 | |
443 | coords[0] = x + TILE_SIZE - 1; |
444 | coords[1] = y + TILE_SIZE - 1; |
445 | coords[2] = x + TILE_SIZE - 1; |
446 | coords[3] = y; |
447 | coords[4] = x; |
448 | coords[5] = y + TILE_SIZE - 1; |
449 | draw_polygon(fe, coords, 3, TRUE, COL_LOWLIGHT); |
450 | draw_polygon(fe, coords, 3, FALSE, COL_LOWLIGHT); |
451 | |
452 | coords[0] = x; |
453 | coords[1] = y; |
454 | draw_polygon(fe, coords, 3, TRUE, COL_HIGHLIGHT); |
455 | draw_polygon(fe, coords, 3, FALSE, COL_HIGHLIGHT); |
456 | |
457 | draw_rect(fe, x + HIGHLIGHT_WIDTH, y + HIGHLIGHT_WIDTH, |
458 | TILE_SIZE - 2*HIGHLIGHT_WIDTH, TILE_SIZE - 2*HIGHLIGHT_WIDTH, |
459 | flash_colour); |
460 | |
461 | sprintf(str, "%d", tile); |
462 | draw_text(fe, x + TILE_SIZE/2, y + TILE_SIZE/2, |
463 | FONT_VARIABLE, TILE_SIZE/3, ALIGN_VCENTRE | ALIGN_HCENTRE, |
464 | COL_TEXT, str); |
465 | } |
466 | draw_update(fe, x, y, TILE_SIZE, TILE_SIZE); |
467 | } |
468 | |
469 | void game_redraw(frontend *fe, game_drawstate *ds, game_state *oldstate, |
470 | game_state *state, float animtime, float flashtime) |
471 | { |
472 | int i, pass, bgcolour; |
473 | |
474 | if (flashtime > 0) { |
475 | int frame = (int)(flashtime / FLASH_FRAME); |
476 | bgcolour = (frame % 2 ? COL_LOWLIGHT : COL_HIGHLIGHT); |
477 | } else |
478 | bgcolour = COL_BACKGROUND; |
479 | |
480 | if (!ds->started) { |
481 | int coords[6]; |
482 | |
483 | draw_rect(fe, 0, 0, |
484 | TILE_SIZE * state->w + 2 * BORDER, |
485 | TILE_SIZE * state->h + 2 * BORDER, COL_BACKGROUND); |
486 | draw_update(fe, 0, 0, |
487 | TILE_SIZE * state->w + 2 * BORDER, |
488 | TILE_SIZE * state->h + 2 * BORDER); |
489 | |
490 | /* |
491 | * Recessed area containing the whole puzzle. |
492 | */ |
493 | coords[0] = COORD(state->w) + HIGHLIGHT_WIDTH - 1; |
494 | coords[1] = COORD(state->h) + HIGHLIGHT_WIDTH - 1; |
495 | coords[2] = COORD(state->w) + HIGHLIGHT_WIDTH - 1; |
496 | coords[3] = COORD(0) - HIGHLIGHT_WIDTH; |
497 | coords[4] = COORD(0) - HIGHLIGHT_WIDTH; |
498 | coords[5] = COORD(state->h) + HIGHLIGHT_WIDTH - 1; |
499 | draw_polygon(fe, coords, 3, TRUE, COL_HIGHLIGHT); |
500 | draw_polygon(fe, coords, 3, FALSE, COL_HIGHLIGHT); |
501 | |
502 | coords[1] = COORD(0) - HIGHLIGHT_WIDTH; |
503 | coords[0] = COORD(0) - HIGHLIGHT_WIDTH; |
504 | draw_polygon(fe, coords, 3, TRUE, COL_LOWLIGHT); |
505 | draw_polygon(fe, coords, 3, FALSE, COL_LOWLIGHT); |
506 | |
507 | ds->started = TRUE; |
508 | } |
509 | |
510 | /* |
511 | * Now draw each tile. We do this in two passes to make |
512 | * animation easy. |
513 | */ |
514 | for (pass = 0; pass < 2; pass++) { |
515 | for (i = 0; i < state->n; i++) { |
516 | int t, t0; |
517 | /* |
518 | * Figure out what should be displayed at this |
519 | * location. It's either a simple tile, or it's a |
520 | * transition between two tiles (in which case we say |
521 | * -1 because it must always be drawn). |
522 | */ |
523 | |
524 | if (oldstate && oldstate->tiles[i] != state->tiles[i]) |
525 | t = -1; |
526 | else |
527 | t = state->tiles[i]; |
528 | |
529 | t0 = t; |
530 | |
531 | if (ds->bgcolour != bgcolour || /* always redraw when flashing */ |
532 | ds->tiles[i] != t || ds->tiles[i] == -1 || t == -1) { |
533 | int x, y; |
534 | |
535 | /* |
536 | * Figure out what to _actually_ draw, and where to |
537 | * draw it. |
538 | */ |
539 | if (t == -1) { |
540 | int x0, y0, x1, y1; |
541 | int j; |
542 | |
543 | /* |
544 | * On the first pass, just blank the tile. |
545 | */ |
546 | if (pass == 0) { |
547 | x = COORD(X(state, i)); |
548 | y = COORD(Y(state, i)); |
549 | t = 0; |
550 | } else { |
551 | float c; |
552 | |
553 | t = state->tiles[i]; |
554 | |
555 | /* |
556 | * Don't bother moving the gap; just don't |
557 | * draw it. |
558 | */ |
559 | if (t == 0) |
560 | continue; |
561 | |
562 | /* |
563 | * Find the coordinates of this tile in the old and |
564 | * new states. |
565 | */ |
566 | x1 = COORD(X(state, i)); |
567 | y1 = COORD(Y(state, i)); |
568 | for (j = 0; j < oldstate->n; j++) |
569 | if (oldstate->tiles[j] == state->tiles[i]) |
570 | break; |
571 | assert(j < oldstate->n); |
572 | x0 = COORD(X(state, j)); |
573 | y0 = COORD(Y(state, j)); |
574 | |
575 | c = (animtime / ANIM_TIME); |
576 | if (c < 0.0F) c = 0.0F; |
577 | if (c > 1.0F) c = 1.0F; |
578 | |
579 | x = x0 + (int)(c * (x1 - x0)); |
580 | y = y0 + (int)(c * (y1 - y0)); |
581 | } |
582 | |
583 | } else { |
584 | if (pass == 0) |
585 | continue; |
586 | x = COORD(X(state, i)); |
587 | y = COORD(Y(state, i)); |
588 | } |
589 | |
590 | draw_tile(fe, state, x, y, t, bgcolour); |
591 | } |
592 | ds->tiles[i] = t0; |
593 | } |
594 | } |
595 | ds->bgcolour = bgcolour; |
fd1a1a2b |
596 | |
597 | /* |
598 | * Update the status bar. |
599 | */ |
600 | { |
601 | char statusbuf[256]; |
602 | |
d108c342 |
603 | /* |
604 | * Don't show the new status until we're also showing the |
605 | * new _state_ - after the game animation is complete. |
606 | */ |
607 | if (oldstate) |
608 | state = oldstate; |
609 | |
fd1a1a2b |
610 | sprintf(statusbuf, "%sMoves: %d", |
611 | (state->completed ? "COMPLETED! " : ""), |
612 | (state->completed ? state->completed : state->movecount)); |
613 | |
614 | status_bar(fe, statusbuf); |
615 | } |
4efb3868 |
616 | } |
617 | |
618 | float game_anim_length(game_state *oldstate, game_state *newstate) |
619 | { |
620 | return ANIM_TIME; |
621 | } |
622 | |
623 | float game_flash_length(game_state *oldstate, game_state *newstate) |
624 | { |
625 | if (!oldstate->completed && newstate->completed) |
626 | return 2 * FLASH_FRAME; |
627 | else |
628 | return 0.0F; |
629 | } |
fd1a1a2b |
630 | |
631 | int game_wants_statusbar(void) |
632 | { |
633 | return TRUE; |
634 | } |