summaryrefslogtreecommitdiff
path: root/apps/plugins/puzzles/src/inertia.c
diff options
context:
space:
mode:
Diffstat (limited to 'apps/plugins/puzzles/src/inertia.c')
-rw-r--r--apps/plugins/puzzles/src/inertia.c2249
1 files changed, 2249 insertions, 0 deletions
diff --git a/apps/plugins/puzzles/src/inertia.c b/apps/plugins/puzzles/src/inertia.c
new file mode 100644
index 0000000000..c22d2e17d4
--- /dev/null
+++ b/apps/plugins/puzzles/src/inertia.c
@@ -0,0 +1,2249 @@
1/*
2 * inertia.c: Game involving navigating round a grid picking up
3 * gems.
4 *
5 * Game rules and basic generator design by Ben Olmstead.
6 * This re-implementation was written by Simon Tatham.
7 */
8
9#include <stdio.h>
10#include <stdlib.h>
11#include <string.h>
12#include <assert.h>
13#include <ctype.h>
14#include <math.h>
15
16#include "puzzles.h"
17
18/* Used in the game_state */
19#define BLANK 'b'
20#define GEM 'g'
21#define MINE 'm'
22#define STOP 's'
23#define WALL 'w'
24
25/* Used in the game IDs */
26#define START 'S'
27
28/* Used in the game generation */
29#define POSSGEM 'G'
30
31/* Used only in the game_drawstate*/
32#define UNDRAWN '?'
33
34#define DIRECTIONS 8
35#define DP1 (DIRECTIONS+1)
36#define DX(dir) ( (dir) & 3 ? (((dir) & 7) > 4 ? -1 : +1) : 0 )
37#define DY(dir) ( DX((dir)+6) )
38
39/*
40 * Lvalue macro which expects x and y to be in range.
41 */
42#define LV_AT(w, h, grid, x, y) ( (grid)[(y)*(w)+(x)] )
43
44/*
45 * Rvalue macro which can cope with x and y being out of range.
46 */
47#define AT(w, h, grid, x, y) ( (x)<0 || (x)>=(w) || (y)<0 || (y)>=(h) ? \
48 WALL : LV_AT(w, h, grid, x, y) )
49
50enum {
51 COL_BACKGROUND,
52 COL_OUTLINE,
53 COL_HIGHLIGHT,
54 COL_LOWLIGHT,
55 COL_PLAYER,
56 COL_DEAD_PLAYER,
57 COL_MINE,
58 COL_GEM,
59 COL_WALL,
60 COL_HINT,
61 NCOLOURS
62};
63
64struct game_params {
65 int w, h;
66};
67
68typedef struct soln {
69 int refcount;
70 int len;
71 unsigned char *list;
72} soln;
73
74struct game_state {
75 game_params p;
76 int px, py;
77 int gems;
78 char *grid;
79 int distance_moved;
80 int dead;
81 int cheated;
82 int solnpos;
83 soln *soln;
84};
85
86static game_params *default_params(void)
87{
88 game_params *ret = snew(game_params);
89
90 ret->w = 10;
91#ifdef PORTRAIT_SCREEN
92 ret->h = 10;
93#else
94 ret->h = 8;
95#endif
96 return ret;
97}
98
99static void free_params(game_params *params)
100{
101 sfree(params);
102}
103
104static game_params *dup_params(const game_params *params)
105{
106 game_params *ret = snew(game_params);
107 *ret = *params; /* structure copy */
108 return ret;
109}
110
111static const struct game_params inertia_presets[] = {
112#ifdef PORTRAIT_SCREEN
113 { 10, 10 },
114 { 12, 12 },
115 { 16, 16 },
116#else
117 { 10, 8 },
118 { 15, 12 },
119 { 20, 16 },
120#endif
121};
122
123static int game_fetch_preset(int i, char **name, game_params **params)
124{
125 game_params p, *ret;
126 char *retname;
127 char namebuf[80];
128
129 if (i < 0 || i >= lenof(inertia_presets))
130 return FALSE;
131
132 p = inertia_presets[i];
133 ret = dup_params(&p);
134 sprintf(namebuf, "%dx%d", ret->w, ret->h);
135 retname = dupstr(namebuf);
136
137 *params = ret;
138 *name = retname;
139 return TRUE;
140}
141
142static void decode_params(game_params *params, char const *string)
143{
144 params->w = params->h = atoi(string);
145 while (*string && isdigit((unsigned char)*string)) string++;
146 if (*string == 'x') {
147 string++;
148 params->h = atoi(string);
149 }
150}
151
152static char *encode_params(const game_params *params, int full)
153{
154 char data[256];
155
156 sprintf(data, "%dx%d", params->w, params->h);
157
158 return dupstr(data);
159}
160
161static config_item *game_configure(const game_params *params)
162{
163 config_item *ret;
164 char buf[80];
165
166 ret = snewn(3, config_item);
167
168 ret[0].name = "Width";
169 ret[0].type = C_STRING;
170 sprintf(buf, "%d", params->w);
171 ret[0].sval = dupstr(buf);
172 ret[0].ival = 0;
173
174 ret[1].name = "Height";
175 ret[1].type = C_STRING;
176 sprintf(buf, "%d", params->h);
177 ret[1].sval = dupstr(buf);
178 ret[1].ival = 0;
179
180 ret[2].name = NULL;
181 ret[2].type = C_END;
182 ret[2].sval = NULL;
183 ret[2].ival = 0;
184
185 return ret;
186}
187
188static game_params *custom_params(const config_item *cfg)
189{
190 game_params *ret = snew(game_params);
191
192 ret->w = atoi(cfg[0].sval);
193 ret->h = atoi(cfg[1].sval);
194
195 return ret;
196}
197
198static char *validate_params(const game_params *params, int full)
199{
200 /*
201 * Avoid completely degenerate cases which only have one
202 * row/column. We probably could generate completable puzzles
203 * of that shape, but they'd be forced to be extremely boring
204 * and at large sizes would take a while to happen upon at
205 * random as well.
206 */
207 if (params->w < 2 || params->h < 2)
208 return "Width and height must both be at least two";
209
210 /*
211 * The grid construction algorithm creates 1/5 as many gems as
212 * grid squares, and must create at least one gem to have an
213 * actual puzzle. However, an area-five grid is ruled out by
214 * the above constraint, so the practical minimum is six.
215 */
216 if (params->w * params->h < 6)
217 return "Grid area must be at least six squares";
218
219 return NULL;
220}
221
222/* ----------------------------------------------------------------------
223 * Solver used by grid generator.
224 */
225
226struct solver_scratch {
227 unsigned char *reachable_from, *reachable_to;
228 int *positions;
229};
230
231static struct solver_scratch *new_scratch(int w, int h)
232{
233 struct solver_scratch *sc = snew(struct solver_scratch);
234
235 sc->reachable_from = snewn(w * h * DIRECTIONS, unsigned char);
236 sc->reachable_to = snewn(w * h * DIRECTIONS, unsigned char);
237 sc->positions = snewn(w * h * DIRECTIONS, int);
238
239 return sc;
240}
241
242static void free_scratch(struct solver_scratch *sc)
243{
244 sfree(sc->reachable_from);
245 sfree(sc->reachable_to);
246 sfree(sc->positions);
247 sfree(sc);
248}
249
250static int can_go(int w, int h, char *grid,
251 int x1, int y1, int dir1, int x2, int y2, int dir2)
252{
253 /*
254 * Returns TRUE if we can transition directly from (x1,y1)
255 * going in direction dir1, to (x2,y2) going in direction dir2.
256 */
257
258 /*
259 * If we're actually in the middle of an unoccupyable square,
260 * we cannot make any move.
261 */
262 if (AT(w, h, grid, x1, y1) == WALL ||
263 AT(w, h, grid, x1, y1) == MINE)
264 return FALSE;
265
266 /*
267 * If a move is capable of stopping at x1,y1,dir1, and x2,y2 is
268 * the same coordinate as x1,y1, then we can make the
269 * transition (by stopping and changing direction).
270 *
271 * For this to be the case, we have to either have a wall
272 * beyond x1,y1,dir1, or have a stop on x1,y1.
273 */
274 if (x2 == x1 && y2 == y1 &&
275 (AT(w, h, grid, x1, y1) == STOP ||
276 AT(w, h, grid, x1, y1) == START ||
277 AT(w, h, grid, x1+DX(dir1), y1+DY(dir1)) == WALL))
278 return TRUE;
279
280 /*
281 * If a move is capable of continuing here, then x1,y1,dir1 can
282 * move one space further on.
283 */
284 if (x2 == x1+DX(dir1) && y2 == y1+DY(dir1) && dir1 == dir2 &&
285 (AT(w, h, grid, x2, y2) == BLANK ||
286 AT(w, h, grid, x2, y2) == GEM ||
287 AT(w, h, grid, x2, y2) == STOP ||
288 AT(w, h, grid, x2, y2) == START))
289 return TRUE;
290
291 /*
292 * That's it.
293 */
294 return FALSE;
295}
296
297static int find_gem_candidates(int w, int h, char *grid,
298 struct solver_scratch *sc)
299{
300 int wh = w*h;
301 int head, tail;
302 int sx, sy, gx, gy, gd, pass, possgems;
303
304 /*
305 * This function finds all the candidate gem squares, which are
306 * precisely those squares which can be picked up on a loop
307 * from the starting point back to the starting point. Doing
308 * this may involve passing through such a square in the middle
309 * of a move; so simple breadth-first search over the _squares_
310 * of the grid isn't quite adequate, because it might be that
311 * we can only reach a gem from the start by moving over it in
312 * one direction, but can only return to the start if we were
313 * moving over it in another direction.
314 *
315 * Instead, we BFS over a space which mentions each grid square
316 * eight times - once for each direction. We also BFS twice:
317 * once to find out what square+direction pairs we can reach
318 * _from_ the start point, and once to find out what pairs we
319 * can reach the start point from. Then a square is reachable
320 * if any of the eight directions for that square has both
321 * flags set.
322 */
323
324 memset(sc->reachable_from, 0, wh * DIRECTIONS);
325 memset(sc->reachable_to, 0, wh * DIRECTIONS);
326
327 /*
328 * Find the starting square.
329 */
330 sx = -1; /* placate optimiser */
331 for (sy = 0; sy < h; sy++) {
332 for (sx = 0; sx < w; sx++)
333 if (AT(w, h, grid, sx, sy) == START)
334 break;
335 if (sx < w)
336 break;
337 }
338 assert(sy < h);
339
340 for (pass = 0; pass < 2; pass++) {
341 unsigned char *reachable = (pass == 0 ? sc->reachable_from :
342 sc->reachable_to);
343 int sign = (pass == 0 ? +1 : -1);
344 int dir;
345
346#ifdef SOLVER_DIAGNOSTICS
347 printf("starting pass %d\n", pass);
348#endif
349
350 /*
351 * `head' and `tail' are indices within sc->positions which
352 * track the list of board positions left to process.
353 */
354 head = tail = 0;
355 for (dir = 0; dir < DIRECTIONS; dir++) {
356 int index = (sy*w+sx)*DIRECTIONS+dir;
357 sc->positions[tail++] = index;
358 reachable[index] = TRUE;
359#ifdef SOLVER_DIAGNOSTICS
360 printf("starting point %d,%d,%d\n", sx, sy, dir);
361#endif
362 }
363
364 /*
365 * Now repeatedly pick an element off the list and process
366 * it.
367 */
368 while (head < tail) {
369 int index = sc->positions[head++];
370 int dir = index % DIRECTIONS;
371 int x = (index / DIRECTIONS) % w;
372 int y = index / (w * DIRECTIONS);
373 int n, x2, y2, d2, i2;
374
375#ifdef SOLVER_DIAGNOSTICS
376 printf("processing point %d,%d,%d\n", x, y, dir);
377#endif
378 /*
379 * The places we attempt to switch to here are:
380 * - each possible direction change (all the other
381 * directions in this square)
382 * - one step further in the direction we're going (or
383 * one step back, if we're in the reachable_to pass).
384 */
385 for (n = -1; n < DIRECTIONS; n++) {
386 if (n < 0) {
387 x2 = x + sign * DX(dir);
388 y2 = y + sign * DY(dir);
389 d2 = dir;
390 } else {
391 x2 = x;
392 y2 = y;
393 d2 = n;
394 }
395 i2 = (y2*w+x2)*DIRECTIONS+d2;
396 if (x2 >= 0 && x2 < w &&
397 y2 >= 0 && y2 < h &&
398 !reachable[i2]) {
399 int ok;
400#ifdef SOLVER_DIAGNOSTICS
401 printf(" trying point %d,%d,%d", x2, y2, d2);
402#endif
403 if (pass == 0)
404 ok = can_go(w, h, grid, x, y, dir, x2, y2, d2);
405 else
406 ok = can_go(w, h, grid, x2, y2, d2, x, y, dir);
407#ifdef SOLVER_DIAGNOSTICS
408 printf(" - %sok\n", ok ? "" : "not ");
409#endif
410 if (ok) {
411 sc->positions[tail++] = i2;
412 reachable[i2] = TRUE;
413 }
414 }
415 }
416 }
417 }
418
419 /*
420 * And that should be it. Now all we have to do is find the
421 * squares for which there exists _some_ direction such that
422 * the square plus that direction form a tuple which is both
423 * reachable from the start and reachable to the start.
424 */
425 possgems = 0;
426 for (gy = 0; gy < h; gy++)
427 for (gx = 0; gx < w; gx++)
428 if (AT(w, h, grid, gx, gy) == BLANK) {
429 for (gd = 0; gd < DIRECTIONS; gd++) {
430 int index = (gy*w+gx)*DIRECTIONS+gd;
431 if (sc->reachable_from[index] && sc->reachable_to[index]) {
432#ifdef SOLVER_DIAGNOSTICS
433 printf("space at %d,%d is reachable via"
434 " direction %d\n", gx, gy, gd);
435#endif
436 LV_AT(w, h, grid, gx, gy) = POSSGEM;
437 possgems++;
438 break;
439 }
440 }
441 }
442
443 return possgems;
444}
445
446/* ----------------------------------------------------------------------
447 * Grid generation code.
448 */
449
450static char *gengrid(int w, int h, random_state *rs)
451{
452 int wh = w*h;
453 char *grid = snewn(wh+1, char);
454 struct solver_scratch *sc = new_scratch(w, h);
455 int maxdist_threshold, tries;
456
457 maxdist_threshold = 2;
458 tries = 0;
459
460 while (1) {
461 int i, j;
462 int possgems;
463 int *dist, *list, head, tail, maxdist;
464
465 /*
466 * We're going to fill the grid with the five basic piece
467 * types in about 1/5 proportion. For the moment, though,
468 * we leave out the gems, because we'll put those in
469 * _after_ we run the solver to tell us where the viable
470 * locations are.
471 */
472 i = 0;
473 for (j = 0; j < wh/5; j++)
474 grid[i++] = WALL;
475 for (j = 0; j < wh/5; j++)
476 grid[i++] = STOP;
477 for (j = 0; j < wh/5; j++)
478 grid[i++] = MINE;
479 assert(i < wh);
480 grid[i++] = START;
481 while (i < wh)
482 grid[i++] = BLANK;
483 shuffle(grid, wh, sizeof(*grid), rs);
484
485 /*
486 * Find the viable gem locations, and immediately give up
487 * and try again if there aren't enough of them.
488 */
489 possgems = find_gem_candidates(w, h, grid, sc);
490 if (possgems < wh/5)
491 continue;
492
493 /*
494 * We _could_ now select wh/5 of the POSSGEMs and set them
495 * to GEM, and have a viable level. However, there's a
496 * chance that a large chunk of the level will turn out to
497 * be unreachable, so first we test for that.
498 *
499 * We do this by finding the largest distance from any
500 * square to the nearest POSSGEM, by breadth-first search.
501 * If this is above a critical threshold, we abort and try
502 * again.
503 *
504 * (This search is purely geometric, without regard to
505 * walls and long ways round.)
506 */
507 dist = sc->positions;
508 list = sc->positions + wh;
509 for (i = 0; i < wh; i++)
510 dist[i] = -1;
511 head = tail = 0;
512 for (i = 0; i < wh; i++)
513 if (grid[i] == POSSGEM) {
514 dist[i] = 0;
515 list[tail++] = i;
516 }
517 maxdist = 0;
518 while (head < tail) {
519 int pos, x, y, d;
520
521 pos = list[head++];
522 if (maxdist < dist[pos])
523 maxdist = dist[pos];
524
525 x = pos % w;
526 y = pos / w;
527
528 for (d = 0; d < DIRECTIONS; d++) {
529 int x2, y2, p2;
530
531 x2 = x + DX(d);
532 y2 = y + DY(d);
533
534 if (x2 >= 0 && x2 < w && y2 >= 0 && y2 < h) {
535 p2 = y2*w+x2;
536 if (dist[p2] < 0) {
537 dist[p2] = dist[pos] + 1;
538 list[tail++] = p2;
539 }
540 }
541 }
542 }
543 assert(head == wh && tail == wh);
544
545 /*
546 * Now abandon this grid and go round again if maxdist is
547 * above the required threshold.
548 *
549 * We can safely start the threshold as low as 2. As we
550 * accumulate failed generation attempts, we gradually
551 * raise it as we get more desperate.
552 */
553 if (maxdist > maxdist_threshold) {
554 tries++;
555 if (tries == 50) {
556 maxdist_threshold++;
557 tries = 0;
558 }
559 continue;
560 }
561
562 /*
563 * Now our reachable squares are plausibly evenly
564 * distributed over the grid. I'm not actually going to
565 * _enforce_ that I place the gems in such a way as not to
566 * increase that maxdist value; I'm now just going to trust
567 * to the RNG to pick a sensible subset of the POSSGEMs.
568 */
569 j = 0;
570 for (i = 0; i < wh; i++)
571 if (grid[i] == POSSGEM)
572 list[j++] = i;
573 shuffle(list, j, sizeof(*list), rs);
574 for (i = 0; i < j; i++)
575 grid[list[i]] = (i < wh/5 ? GEM : BLANK);
576 break;
577 }
578
579 free_scratch(sc);
580
581 grid[wh] = '\0';
582
583 return grid;
584}
585
586static char *new_game_desc(const game_params *params, random_state *rs,
587 char **aux, int interactive)
588{
589 return gengrid(params->w, params->h, rs);
590}
591
592static char *validate_desc(const game_params *params, const char *desc)
593{
594 int w = params->w, h = params->h, wh = w*h;
595 int starts = 0, gems = 0, i;
596
597 for (i = 0; i < wh; i++) {
598 if (!desc[i])
599 return "Not enough data to fill grid";
600 if (desc[i] != WALL && desc[i] != START && desc[i] != STOP &&
601 desc[i] != GEM && desc[i] != MINE && desc[i] != BLANK)
602 return "Unrecognised character in game description";
603 if (desc[i] == START)
604 starts++;
605 if (desc[i] == GEM)
606 gems++;
607 }
608 if (desc[i])
609 return "Too much data to fill grid";
610 if (starts < 1)
611 return "No starting square specified";
612 if (starts > 1)
613 return "More than one starting square specified";
614 if (gems < 1)
615 return "No gems specified";
616
617 return NULL;
618}
619
620static game_state *new_game(midend *me, const game_params *params,
621 const char *desc)
622{
623 int w = params->w, h = params->h, wh = w*h;
624 int i;
625 game_state *state = snew(game_state);
626
627 state->p = *params; /* structure copy */
628
629 state->grid = snewn(wh, char);
630 assert(strlen(desc) == wh);
631 memcpy(state->grid, desc, wh);
632
633 state->px = state->py = -1;
634 state->gems = 0;
635 for (i = 0; i < wh; i++) {
636 if (state->grid[i] == START) {
637 state->grid[i] = STOP;
638 state->px = i % w;
639 state->py = i / w;
640 } else if (state->grid[i] == GEM) {
641 state->gems++;
642 }
643 }
644
645 assert(state->gems > 0);
646 assert(state->px >= 0 && state->py >= 0);
647
648 state->distance_moved = 0;
649 state->dead = FALSE;
650
651 state->cheated = FALSE;
652 state->solnpos = 0;
653 state->soln = NULL;
654
655 return state;
656}
657
658static game_state *dup_game(const game_state *state)
659{
660 int w = state->p.w, h = state->p.h, wh = w*h;
661 game_state *ret = snew(game_state);
662
663 ret->p = state->p;
664 ret->px = state->px;
665 ret->py = state->py;
666 ret->gems = state->gems;
667 ret->grid = snewn(wh, char);
668 ret->distance_moved = state->distance_moved;
669 ret->dead = FALSE;
670 memcpy(ret->grid, state->grid, wh);
671 ret->cheated = state->cheated;
672 ret->soln = state->soln;
673 if (ret->soln)
674 ret->soln->refcount++;
675 ret->solnpos = state->solnpos;
676
677 return ret;
678}
679
680static void free_game(game_state *state)
681{
682 if (state->soln && --state->soln->refcount == 0) {
683 sfree(state->soln->list);
684 sfree(state->soln);
685 }
686 sfree(state->grid);
687 sfree(state);
688}
689
690/*
691 * Internal function used by solver.
692 */
693static int move_goes_to(int w, int h, char *grid, int x, int y, int d)
694{
695 int dr;
696
697 /*
698 * See where we'd get to if we made this move.
699 */
700 dr = -1; /* placate optimiser */
701 while (1) {
702 if (AT(w, h, grid, x+DX(d), y+DY(d)) == WALL) {
703 dr = DIRECTIONS; /* hit a wall, so end up stationary */
704 break;
705 }
706 x += DX(d);
707 y += DY(d);
708 if (AT(w, h, grid, x, y) == STOP) {
709 dr = DIRECTIONS; /* hit a stop, so end up stationary */
710 break;
711 }
712 if (AT(w, h, grid, x, y) == GEM) {
713 dr = d; /* hit a gem, so we're still moving */
714 break;
715 }
716 if (AT(w, h, grid, x, y) == MINE)
717 return -1; /* hit a mine, so move is invalid */
718 }
719 assert(dr >= 0);
720 return (y*w+x)*DP1+dr;
721}
722
723static int compare_integers(const void *av, const void *bv)
724{
725 const int *a = (const int *)av;
726 const int *b = (const int *)bv;
727 if (*a < *b)
728 return -1;
729 else if (*a > *b)
730 return +1;
731 else
732 return 0;
733}
734
735static char *solve_game(const game_state *state, const game_state *currstate,
736 const char *aux, char **error)
737{
738 int w = currstate->p.w, h = currstate->p.h, wh = w*h;
739 int *nodes, *nodeindex, *edges, *backedges, *edgei, *backedgei, *circuit;
740 int nedges;
741 int *dist, *dist2, *list;
742 int *unvisited;
743 int circuitlen, circuitsize;
744 int head, tail, pass, i, j, n, x, y, d, dd;
745 char *err, *soln, *p;
746
747 /*
748 * Before anything else, deal with the special case in which
749 * all the gems are already collected.
750 */
751 for (i = 0; i < wh; i++)
752 if (currstate->grid[i] == GEM)
753 break;
754 if (i == wh) {
755 *error = "Game is already solved";
756 return NULL;
757 }
758
759 /*
760 * Solving Inertia is a question of first building up the graph
761 * of where you can get to from where, and secondly finding a
762 * tour of the graph which takes in every gem.
763 *
764 * This is of course a close cousin of the travelling salesman
765 * problem, which is NP-complete; so I rather doubt that any
766 * _optimal_ tour can be found in plausible time. Hence I'll
767 * restrict myself to merely finding a not-too-bad one.
768 *
769 * First construct the graph, by bfsing out move by move from
770 * the current player position. Graph vertices will be
771 * - every endpoint of a move (place the ball can be
772 * stationary)
773 * - every gem (place the ball can go through in motion).
774 * Vertices of this type have an associated direction, since
775 * if a gem can be collected by sliding through it in two
776 * different directions it doesn't follow that you can
777 * change direction at it.
778 *
779 * I'm going to refer to a non-directional vertex as
780 * (y*w+x)*DP1+DIRECTIONS, and a directional one as
781 * (y*w+x)*DP1+d.
782 */
783
784 /*
785 * nodeindex[] maps node codes as shown above to numeric
786 * indices in the nodes[] array.
787 */
788 nodeindex = snewn(DP1*wh, int);
789 for (i = 0; i < DP1*wh; i++)
790 nodeindex[i] = -1;
791
792 /*
793 * Do the bfs to find all the interesting graph nodes.
794 */
795 nodes = snewn(DP1*wh, int);
796 head = tail = 0;
797
798 nodes[tail] = (currstate->py * w + currstate->px) * DP1 + DIRECTIONS;
799 nodeindex[nodes[0]] = tail;
800 tail++;
801
802 while (head < tail) {
803 int nc = nodes[head++], nnc;
804
805 d = nc % DP1;
806
807 /*
808 * Plot all possible moves from this node. If the node is
809 * directed, there's only one.
810 */
811 for (dd = 0; dd < DIRECTIONS; dd++) {
812 x = nc / DP1;
813 y = x / w;
814 x %= w;
815
816 if (d < DIRECTIONS && d != dd)
817 continue;
818
819 nnc = move_goes_to(w, h, currstate->grid, x, y, dd);
820 if (nnc >= 0 && nnc != nc) {
821 if (nodeindex[nnc] < 0) {
822 nodes[tail] = nnc;
823 nodeindex[nnc] = tail;
824 tail++;
825 }
826 }
827 }
828 }
829 n = head;
830
831 /*
832 * Now we know how many nodes we have, allocate the edge array
833 * and go through setting up the edges.
834 */
835 edges = snewn(DIRECTIONS*n, int);
836 edgei = snewn(n+1, int);
837 nedges = 0;
838
839 for (i = 0; i < n; i++) {
840 int nc = nodes[i];
841
842 edgei[i] = nedges;
843
844 d = nc % DP1;
845 x = nc / DP1;
846 y = x / w;
847 x %= w;
848
849 for (dd = 0; dd < DIRECTIONS; dd++) {
850 int nnc;
851
852 if (d >= DIRECTIONS || d == dd) {
853 nnc = move_goes_to(w, h, currstate->grid, x, y, dd);
854
855 if (nnc >= 0 && nnc != nc)
856 edges[nedges++] = nodeindex[nnc];
857 }
858 }
859 }
860 edgei[n] = nedges;
861
862 /*
863 * Now set up the backedges array.
864 */
865 backedges = snewn(nedges, int);
866 backedgei = snewn(n+1, int);
867 for (i = j = 0; i < nedges; i++) {
868 while (j+1 < n && i >= edgei[j+1])
869 j++;
870 backedges[i] = edges[i] * n + j;
871 }
872 qsort(backedges, nedges, sizeof(int), compare_integers);
873 backedgei[0] = 0;
874 for (i = j = 0; i < nedges; i++) {
875 int k = backedges[i] / n;
876 backedges[i] %= n;
877 while (j < k)
878 backedgei[++j] = i;
879 }
880 backedgei[n] = nedges;
881
882 /*
883 * Set up the initial tour. At all times, our tour is a circuit
884 * of graph vertices (which may, and probably will often,
885 * repeat vertices). To begin with, it's got exactly one vertex
886 * in it, which is the player's current starting point.
887 */
888 circuitsize = 256;
889 circuit = snewn(circuitsize, int);
890 circuitlen = 0;
891 circuit[circuitlen++] = 0; /* node index 0 is the starting posn */
892
893 /*
894 * Track which gems are as yet unvisited.
895 */
896 unvisited = snewn(wh, int);
897 for (i = 0; i < wh; i++)
898 unvisited[i] = FALSE;
899 for (i = 0; i < wh; i++)
900 if (currstate->grid[i] == GEM)
901 unvisited[i] = TRUE;
902
903 /*
904 * Allocate space for doing bfses inside the main loop.
905 */
906 dist = snewn(n, int);
907 dist2 = snewn(n, int);
908 list = snewn(n, int);
909
910 err = NULL;
911 soln = NULL;
912
913 /*
914 * Now enter the main loop, in each iteration of which we
915 * extend the tour to take in an as yet uncollected gem.
916 */
917 while (1) {
918 int target, n1, n2, bestdist, extralen, targetpos;
919
920#ifdef TSP_DIAGNOSTICS
921 printf("circuit is");
922 for (i = 0; i < circuitlen; i++) {
923 int nc = nodes[circuit[i]];
924 printf(" (%d,%d,%d)", nc/DP1%w, nc/(DP1*w), nc%DP1);
925 }
926 printf("\n");
927 printf("moves are ");
928 x = nodes[circuit[0]] / DP1 % w;
929 y = nodes[circuit[0]] / DP1 / w;
930 for (i = 1; i < circuitlen; i++) {
931 int x2, y2, dx, dy;
932 if (nodes[circuit[i]] % DP1 != DIRECTIONS)
933 continue;
934 x2 = nodes[circuit[i]] / DP1 % w;
935 y2 = nodes[circuit[i]] / DP1 / w;
936 dx = (x2 > x ? +1 : x2 < x ? -1 : 0);
937 dy = (y2 > y ? +1 : y2 < y ? -1 : 0);
938 for (d = 0; d < DIRECTIONS; d++)
939 if (DX(d) == dx && DY(d) == dy)
940 printf("%c", "89632147"[d]);
941 x = x2;
942 y = y2;
943 }
944 printf("\n");
945#endif
946
947 /*
948 * First, start a pair of bfses at _every_ vertex currently
949 * in the tour, and extend them outwards to find the
950 * nearest as yet unreached gem vertex.
951 *
952 * This is largely a heuristic: we could pick _any_ doubly
953 * reachable node here and still get a valid tour as
954 * output. I hope that picking a nearby one will result in
955 * generally good tours.
956 */
957 for (pass = 0; pass < 2; pass++) {
958 int *ep = (pass == 0 ? edges : backedges);
959 int *ei = (pass == 0 ? edgei : backedgei);
960 int *dp = (pass == 0 ? dist : dist2);
961 head = tail = 0;
962 for (i = 0; i < n; i++)
963 dp[i] = -1;
964 for (i = 0; i < circuitlen; i++) {
965 int ni = circuit[i];
966 if (dp[ni] < 0) {
967 dp[ni] = 0;
968 list[tail++] = ni;
969 }
970 }
971 while (head < tail) {
972 int ni = list[head++];
973 for (i = ei[ni]; i < ei[ni+1]; i++) {
974 int ti = ep[i];
975 if (ti >= 0 && dp[ti] < 0) {
976 dp[ti] = dp[ni] + 1;
977 list[tail++] = ti;
978 }
979 }
980 }
981 }
982 /* Now find the nearest unvisited gem. */
983 bestdist = -1;
984 target = -1;
985 for (i = 0; i < n; i++) {
986 if (unvisited[nodes[i] / DP1] &&
987 dist[i] >= 0 && dist2[i] >= 0) {
988 int thisdist = dist[i] + dist2[i];
989 if (bestdist < 0 || bestdist > thisdist) {
990 bestdist = thisdist;
991 target = i;
992 }
993 }
994 }
995
996 if (target < 0) {
997 /*
998 * If we get to here, we haven't found a gem we can get
999 * at all, which means we terminate this loop.
1000 */
1001 break;
1002 }
1003
1004 /*
1005 * Now we have a graph vertex at list[tail-1] which is an
1006 * unvisited gem. We want to add that vertex to our tour.
1007 * So we run two more breadth-first searches: one starting
1008 * from that vertex and following forward edges, and
1009 * another starting from the same vertex and following
1010 * backward edges. This allows us to determine, for each
1011 * node on the current tour, how quickly we can get both to
1012 * and from the target vertex from that node.
1013 */
1014#ifdef TSP_DIAGNOSTICS
1015 printf("target node is %d (%d,%d,%d)\n", target, nodes[target]/DP1%w,
1016 nodes[target]/DP1/w, nodes[target]%DP1);
1017#endif
1018
1019 for (pass = 0; pass < 2; pass++) {
1020 int *ep = (pass == 0 ? edges : backedges);
1021 int *ei = (pass == 0 ? edgei : backedgei);
1022 int *dp = (pass == 0 ? dist : dist2);
1023
1024 for (i = 0; i < n; i++)
1025 dp[i] = -1;
1026 head = tail = 0;
1027
1028 dp[target] = 0;
1029 list[tail++] = target;
1030
1031 while (head < tail) {
1032 int ni = list[head++];
1033 for (i = ei[ni]; i < ei[ni+1]; i++) {
1034 int ti = ep[i];
1035 if (ti >= 0 && dp[ti] < 0) {
1036 dp[ti] = dp[ni] + 1;
1037/*printf("pass %d: set dist of vertex %d to %d (via %d)\n", pass, ti, dp[ti], ni);*/
1038 list[tail++] = ti;
1039 }
1040 }
1041 }
1042 }
1043
1044 /*
1045 * Now for every node n, dist[n] gives the length of the
1046 * shortest path from the target vertex to n, and dist2[n]
1047 * gives the length of the shortest path from n to the
1048 * target vertex.
1049 *
1050 * Our next step is to search linearly along the tour to
1051 * find the optimum place to insert a trip to the target
1052 * vertex and back. Our two options are either
1053 * (a) to find two adjacent vertices A,B in the tour and
1054 * replace the edge A->B with the path A->target->B
1055 * (b) to find a single vertex X in the tour and replace
1056 * it with the complete round trip X->target->X.
1057 * We do whichever takes the fewest moves.
1058 */
1059 n1 = n2 = -1;
1060 bestdist = -1;
1061 for (i = 0; i < circuitlen; i++) {
1062 int thisdist;
1063
1064 /*
1065 * Try a round trip from vertex i.
1066 */
1067 if (dist[circuit[i]] >= 0 &&
1068 dist2[circuit[i]] >= 0) {
1069 thisdist = dist[circuit[i]] + dist2[circuit[i]];
1070 if (bestdist < 0 || thisdist < bestdist) {
1071 bestdist = thisdist;
1072 n1 = n2 = i;
1073 }
1074 }
1075
1076 /*
1077 * Try a trip from vertex i via target to vertex i+1.
1078 */
1079 if (i+1 < circuitlen &&
1080 dist2[circuit[i]] >= 0 &&
1081 dist[circuit[i+1]] >= 0) {
1082 thisdist = dist2[circuit[i]] + dist[circuit[i+1]];
1083 if (bestdist < 0 || thisdist < bestdist) {
1084 bestdist = thisdist;
1085 n1 = i;
1086 n2 = i+1;
1087 }
1088 }
1089 }
1090 if (bestdist < 0) {
1091 /*
1092 * We couldn't find a round trip taking in this gem _at
1093 * all_. Give up.
1094 */
1095 err = "Unable to find a solution from this starting point";
1096 break;
1097 }
1098#ifdef TSP_DIAGNOSTICS
1099 printf("insertion point: n1=%d, n2=%d, dist=%d\n", n1, n2, bestdist);
1100#endif
1101
1102#ifdef TSP_DIAGNOSTICS
1103 printf("circuit before lengthening is");
1104 for (i = 0; i < circuitlen; i++) {
1105 printf(" %d", circuit[i]);
1106 }
1107 printf("\n");
1108#endif
1109
1110 /*
1111 * Now actually lengthen the tour to take in this round
1112 * trip.
1113 */
1114 extralen = dist2[circuit[n1]] + dist[circuit[n2]];
1115 if (n1 != n2)
1116 extralen--;
1117 circuitlen += extralen;
1118 if (circuitlen >= circuitsize) {
1119 circuitsize = circuitlen + 256;
1120 circuit = sresize(circuit, circuitsize, int);
1121 }
1122 memmove(circuit + n2 + extralen, circuit + n2,
1123 (circuitlen - n2 - extralen) * sizeof(int));
1124 n2 += extralen;
1125
1126#ifdef TSP_DIAGNOSTICS
1127 printf("circuit in middle of lengthening is");
1128 for (i = 0; i < circuitlen; i++) {
1129 printf(" %d", circuit[i]);
1130 }
1131 printf("\n");
1132#endif
1133
1134 /*
1135 * Find the shortest-path routes to and from the target,
1136 * and write them into the circuit.
1137 */
1138 targetpos = n1 + dist2[circuit[n1]];
1139 assert(targetpos - dist2[circuit[n1]] == n1);
1140 assert(targetpos + dist[circuit[n2]] == n2);
1141 for (pass = 0; pass < 2; pass++) {
1142 int dir = (pass == 0 ? -1 : +1);
1143 int *ep = (pass == 0 ? backedges : edges);
1144 int *ei = (pass == 0 ? backedgei : edgei);
1145 int *dp = (pass == 0 ? dist : dist2);
1146 int nn = (pass == 0 ? n2 : n1);
1147 int ni = circuit[nn], ti, dest = nn;
1148
1149 while (1) {
1150 circuit[dest] = ni;
1151 if (dp[ni] == 0)
1152 break;
1153 dest += dir;
1154 ti = -1;
1155/*printf("pass %d: looking at vertex %d\n", pass, ni);*/
1156 for (i = ei[ni]; i < ei[ni+1]; i++) {
1157 ti = ep[i];
1158 if (ti >= 0 && dp[ti] == dp[ni] - 1)
1159 break;
1160 }
1161 assert(i < ei[ni+1] && ti >= 0);
1162 ni = ti;
1163 }
1164 }
1165
1166#ifdef TSP_DIAGNOSTICS
1167 printf("circuit after lengthening is");
1168 for (i = 0; i < circuitlen; i++) {
1169 printf(" %d", circuit[i]);
1170 }
1171 printf("\n");
1172#endif
1173
1174 /*
1175 * Finally, mark all gems that the new piece of circuit
1176 * passes through as visited.
1177 */
1178 for (i = n1; i <= n2; i++) {
1179 int pos = nodes[circuit[i]] / DP1;
1180 assert(pos >= 0 && pos < wh);
1181 unvisited[pos] = FALSE;
1182 }
1183 }
1184
1185#ifdef TSP_DIAGNOSTICS
1186 printf("before reduction, moves are ");
1187 x = nodes[circuit[0]] / DP1 % w;
1188 y = nodes[circuit[0]] / DP1 / w;
1189 for (i = 1; i < circuitlen; i++) {
1190 int x2, y2, dx, dy;
1191 if (nodes[circuit[i]] % DP1 != DIRECTIONS)
1192 continue;
1193 x2 = nodes[circuit[i]] / DP1 % w;
1194 y2 = nodes[circuit[i]] / DP1 / w;
1195 dx = (x2 > x ? +1 : x2 < x ? -1 : 0);
1196 dy = (y2 > y ? +1 : y2 < y ? -1 : 0);
1197 for (d = 0; d < DIRECTIONS; d++)
1198 if (DX(d) == dx && DY(d) == dy)
1199 printf("%c", "89632147"[d]);
1200 x = x2;
1201 y = y2;
1202 }
1203 printf("\n");
1204#endif
1205
1206 /*
1207 * That's got a basic solution. Now optimise it by removing
1208 * redundant sections of the circuit: it's entirely possible
1209 * that a piece of circuit we carefully inserted at one stage
1210 * to collect a gem has become pointless because the steps
1211 * required to collect some _later_ gem necessarily passed
1212 * through the same one.
1213 *
1214 * So first we go through and work out how many times each gem
1215 * is collected. Then we look for maximal sections of circuit
1216 * which are redundant in the sense that their removal would
1217 * not reduce any gem's collection count to zero, and replace
1218 * each one with a bfs-derived fastest path between their
1219 * endpoints.
1220 */
1221 while (1) {
1222 int oldlen = circuitlen;
1223 int dir;
1224
1225 for (dir = +1; dir >= -1; dir -= 2) {
1226
1227 for (i = 0; i < wh; i++)
1228 unvisited[i] = 0;
1229 for (i = 0; i < circuitlen; i++) {
1230 int xy = nodes[circuit[i]] / DP1;
1231 if (currstate->grid[xy] == GEM)
1232 unvisited[xy]++;
1233 }
1234
1235 /*
1236 * If there's any gem we didn't end up visiting at all,
1237 * give up.
1238 */
1239 for (i = 0; i < wh; i++) {
1240 if (currstate->grid[i] == GEM && unvisited[i] == 0) {
1241 err = "Unable to find a solution from this starting point";
1242 break;
1243 }
1244 }
1245 if (i < wh)
1246 break;
1247
1248 for (i = j = (dir > 0 ? 0 : circuitlen-1);
1249 i < circuitlen && i >= 0;
1250 i += dir) {
1251 int xy = nodes[circuit[i]] / DP1;
1252 if (currstate->grid[xy] == GEM && unvisited[xy] > 1) {
1253 unvisited[xy]--;
1254 } else if (currstate->grid[xy] == GEM || i == circuitlen-1) {
1255 /*
1256 * circuit[i] collects a gem for the only time,
1257 * or is the last node in the circuit.
1258 * Therefore it cannot be removed; so we now
1259 * want to replace the path from circuit[j] to
1260 * circuit[i] with a bfs-shortest path.
1261 */
1262 int p, q, k, dest, ni, ti, thisdist;
1263
1264 /*
1265 * Set up the upper and lower bounds of the
1266 * reduced section.
1267 */
1268 p = min(i, j);
1269 q = max(i, j);
1270
1271#ifdef TSP_DIAGNOSTICS
1272 printf("optimising section from %d - %d\n", p, q);
1273#endif
1274
1275 for (k = 0; k < n; k++)
1276 dist[k] = -1;
1277 head = tail = 0;
1278
1279 dist[circuit[p]] = 0;
1280 list[tail++] = circuit[p];
1281
1282 while (head < tail && dist[circuit[q]] < 0) {
1283 int ni = list[head++];
1284 for (k = edgei[ni]; k < edgei[ni+1]; k++) {
1285 int ti = edges[k];
1286 if (ti >= 0 && dist[ti] < 0) {
1287 dist[ti] = dist[ni] + 1;
1288 list[tail++] = ti;
1289 }
1290 }
1291 }
1292
1293 thisdist = dist[circuit[q]];
1294 assert(thisdist >= 0 && thisdist <= q-p);
1295
1296 memmove(circuit+p+thisdist, circuit+q,
1297 (circuitlen - q) * sizeof(int));
1298 circuitlen -= q-p;
1299 q = p + thisdist;
1300 circuitlen += q-p;
1301
1302 if (dir > 0)
1303 i = q; /* resume loop from the right place */
1304
1305#ifdef TSP_DIAGNOSTICS
1306 printf("new section runs from %d - %d\n", p, q);
1307#endif
1308
1309 dest = q;
1310 assert(dest >= 0);
1311 ni = circuit[q];
1312
1313 while (1) {
1314 /* printf("dest=%d circuitlen=%d ni=%d dist[ni]=%d\n", dest, circuitlen, ni, dist[ni]); */
1315 circuit[dest] = ni;
1316 if (dist[ni] == 0)
1317 break;
1318 dest--;
1319 ti = -1;
1320 for (k = backedgei[ni]; k < backedgei[ni+1]; k++) {
1321 ti = backedges[k];
1322 if (ti >= 0 && dist[ti] == dist[ni] - 1)
1323 break;
1324 }
1325 assert(k < backedgei[ni+1] && ti >= 0);
1326 ni = ti;
1327 }
1328
1329 /*
1330 * Now re-increment the visit counts for the
1331 * new path.
1332 */
1333 while (++p < q) {
1334 int xy = nodes[circuit[p]] / DP1;
1335 if (currstate->grid[xy] == GEM)
1336 unvisited[xy]++;
1337 }
1338
1339 j = i;
1340
1341#ifdef TSP_DIAGNOSTICS
1342 printf("during reduction, circuit is");
1343 for (k = 0; k < circuitlen; k++) {
1344 int nc = nodes[circuit[k]];
1345 printf(" (%d,%d,%d)", nc/DP1%w, nc/(DP1*w), nc%DP1);
1346 }
1347 printf("\n");
1348 printf("moves are ");
1349 x = nodes[circuit[0]] / DP1 % w;
1350 y = nodes[circuit[0]] / DP1 / w;
1351 for (k = 1; k < circuitlen; k++) {
1352 int x2, y2, dx, dy;
1353 if (nodes[circuit[k]] % DP1 != DIRECTIONS)
1354 continue;
1355 x2 = nodes[circuit[k]] / DP1 % w;
1356 y2 = nodes[circuit[k]] / DP1 / w;
1357 dx = (x2 > x ? +1 : x2 < x ? -1 : 0);
1358 dy = (y2 > y ? +1 : y2 < y ? -1 : 0);
1359 for (d = 0; d < DIRECTIONS; d++)
1360 if (DX(d) == dx && DY(d) == dy)
1361 printf("%c", "89632147"[d]);
1362 x = x2;
1363 y = y2;
1364 }
1365 printf("\n");
1366#endif
1367 }
1368 }
1369
1370#ifdef TSP_DIAGNOSTICS
1371 printf("after reduction, moves are ");
1372 x = nodes[circuit[0]] / DP1 % w;
1373 y = nodes[circuit[0]] / DP1 / w;
1374 for (i = 1; i < circuitlen; i++) {
1375 int x2, y2, dx, dy;
1376 if (nodes[circuit[i]] % DP1 != DIRECTIONS)
1377 continue;
1378 x2 = nodes[circuit[i]] / DP1 % w;
1379 y2 = nodes[circuit[i]] / DP1 / w;
1380 dx = (x2 > x ? +1 : x2 < x ? -1 : 0);
1381 dy = (y2 > y ? +1 : y2 < y ? -1 : 0);
1382 for (d = 0; d < DIRECTIONS; d++)
1383 if (DX(d) == dx && DY(d) == dy)
1384 printf("%c", "89632147"[d]);
1385 x = x2;
1386 y = y2;
1387 }
1388 printf("\n");
1389#endif
1390 }
1391
1392 /*
1393 * If we've managed an entire reduction pass in each
1394 * direction and not made the solution any shorter, we're
1395 * _really_ done.
1396 */
1397 if (circuitlen == oldlen)
1398 break;
1399 }
1400
1401 /*
1402 * Encode the solution as a move string.
1403 */
1404 if (!err) {
1405 soln = snewn(circuitlen+2, char);
1406 p = soln;
1407 *p++ = 'S';
1408 x = nodes[circuit[0]] / DP1 % w;
1409 y = nodes[circuit[0]] / DP1 / w;
1410 for (i = 1; i < circuitlen; i++) {
1411 int x2, y2, dx, dy;
1412 if (nodes[circuit[i]] % DP1 != DIRECTIONS)
1413 continue;
1414 x2 = nodes[circuit[i]] / DP1 % w;
1415 y2 = nodes[circuit[i]] / DP1 / w;
1416 dx = (x2 > x ? +1 : x2 < x ? -1 : 0);
1417 dy = (y2 > y ? +1 : y2 < y ? -1 : 0);
1418 for (d = 0; d < DIRECTIONS; d++)
1419 if (DX(d) == dx && DY(d) == dy) {
1420 *p++ = '0' + d;
1421 break;
1422 }
1423 assert(d < DIRECTIONS);
1424 x = x2;
1425 y = y2;
1426 }
1427 *p++ = '\0';
1428 assert(p - soln < circuitlen+2);
1429 }
1430
1431 sfree(list);
1432 sfree(dist);
1433 sfree(dist2);
1434 sfree(unvisited);
1435 sfree(circuit);
1436 sfree(backedgei);
1437 sfree(backedges);
1438 sfree(edgei);
1439 sfree(edges);
1440 sfree(nodeindex);
1441 sfree(nodes);
1442
1443 if (err)
1444 *error = err;
1445
1446 return soln;
1447}
1448
1449static int game_can_format_as_text_now(const game_params *params)
1450{
1451 return TRUE;
1452}
1453
1454static char *game_text_format(const game_state *state)
1455{
1456 int w = state->p.w, h = state->p.h, r, c;
1457 int cw = 4, ch = 2, gw = cw*w + 2, gh = ch * h + 1, len = gw * gh;
1458 char *board = snewn(len + 1, char);
1459
1460 sprintf(board, "%*s+\n", len - 2, "");
1461
1462 for (r = 0; r < h; ++r) {
1463 for (c = 0; c < w; ++c) {
1464 int cell = r*ch*gw + cw*c, center = cell + gw*ch/2 + cw/2;
1465 int i = r*w + c;
1466 switch (state->grid[i]) {
1467 case BLANK: break;
1468 case GEM: board[center] = 'o'; break;
1469 case MINE: board[center] = 'M'; break;
1470 case STOP: board[center-1] = '('; board[center+1] = ')'; break;
1471 case WALL: memset(board + center - 1, 'X', 3);
1472 }
1473
1474 if (r == state->py && c == state->px) {
1475 if (!state->dead) board[center] = '@';
1476 else memcpy(board + center - 1, ":-(", 3);
1477 }
1478 board[cell] = '+';
1479 memset(board + cell + 1, '-', cw - 1);
1480 for (i = 1; i < ch; ++i) board[cell + i*gw] = '|';
1481 }
1482 for (c = 0; c < ch; ++c) {
1483 board[(r*ch+c)*gw + gw - 2] = "|+"[!c];
1484 board[(r*ch+c)*gw + gw - 1] = '\n';
1485 }
1486 }
1487 memset(board + len - gw, '-', gw - 2);
1488 for (c = 0; c < w; ++c) board[len - gw + cw*c] = '+';
1489
1490 return board;
1491}
1492
1493struct game_ui {
1494 float anim_length;
1495 int flashtype;
1496 int deaths;
1497 int just_made_move;
1498 int just_died;
1499};
1500
1501static game_ui *new_ui(const game_state *state)
1502{
1503 game_ui *ui = snew(game_ui);
1504 ui->anim_length = 0.0F;
1505 ui->flashtype = 0;
1506 ui->deaths = 0;
1507 ui->just_made_move = FALSE;
1508 ui->just_died = FALSE;
1509 return ui;
1510}
1511
1512static void free_ui(game_ui *ui)
1513{
1514 sfree(ui);
1515}
1516
1517static char *encode_ui(const game_ui *ui)
1518{
1519 char buf[80];
1520 /*
1521 * The deaths counter needs preserving across a serialisation.
1522 */
1523 sprintf(buf, "D%d", ui->deaths);
1524 return dupstr(buf);
1525}
1526
1527static void decode_ui(game_ui *ui, const char *encoding)
1528{
1529 int p = 0;
1530 sscanf(encoding, "D%d%n", &ui->deaths, &p);
1531}
1532
1533static void game_changed_state(game_ui *ui, const game_state *oldstate,
1534 const game_state *newstate)
1535{
1536 /*
1537 * Increment the deaths counter. We only do this if
1538 * ui->just_made_move is set (redoing a suicide move doesn't
1539 * kill you _again_), and also we only do it if the game wasn't
1540 * already completed (once you're finished, you can play).
1541 */
1542 if (!oldstate->dead && newstate->dead && ui->just_made_move &&
1543 oldstate->gems) {
1544 ui->deaths++;
1545 ui->just_died = TRUE;
1546 } else {
1547 ui->just_died = FALSE;
1548 }
1549 ui->just_made_move = FALSE;
1550}
1551
1552struct game_drawstate {
1553 game_params p;
1554 int tilesize;
1555 int started;
1556 unsigned short *grid;
1557 blitter *player_background;
1558 int player_bg_saved, pbgx, pbgy;
1559};
1560
1561#define PREFERRED_TILESIZE 32
1562#define TILESIZE (ds->tilesize)
1563#ifdef SMALL_SCREEN
1564#define BORDER (TILESIZE / 4)
1565#else
1566#define BORDER (TILESIZE)
1567#endif
1568#define HIGHLIGHT_WIDTH (TILESIZE / 10)
1569#define COORD(x) ( (x) * TILESIZE + BORDER )
1570#define FROMCOORD(x) ( ((x) - BORDER + TILESIZE) / TILESIZE - 1 )
1571
1572static char *interpret_move(const game_state *state, game_ui *ui,
1573 const game_drawstate *ds,
1574 int x, int y, int button)
1575{
1576 int w = state->p.w, h = state->p.h /*, wh = w*h */;
1577 int dir;
1578 char buf[80];
1579
1580 dir = -1;
1581
1582 if (button == LEFT_BUTTON) {
1583 /*
1584 * Mouse-clicking near the target point (or, more
1585 * accurately, in the appropriate octant) is an alternative
1586 * way to input moves.
1587 */
1588
1589 if (FROMCOORD(x) != state->px || FROMCOORD(y) != state->py) {
1590 int dx, dy;
1591 float angle;
1592
1593 dx = FROMCOORD(x) - state->px;
1594 dy = FROMCOORD(y) - state->py;
1595 /* I pass dx,dy rather than dy,dx so that the octants
1596 * end up the right way round. */
1597 angle = atan2(dx, -dy);
1598
1599 angle = (angle + (PI/8)) / (PI/4);
1600 assert(angle > -16.0F);
1601 dir = (int)(angle + 16.0F) & 7;
1602 }
1603 } else if (button == CURSOR_UP || button == (MOD_NUM_KEYPAD | '8'))
1604 dir = 0;
1605 else if (button == CURSOR_DOWN || button == (MOD_NUM_KEYPAD | '2'))
1606 dir = 4;
1607 else if (button == CURSOR_LEFT || button == (MOD_NUM_KEYPAD | '4'))
1608 dir = 6;
1609 else if (button == CURSOR_RIGHT || button == (MOD_NUM_KEYPAD | '6'))
1610 dir = 2;
1611 else if (button == (MOD_NUM_KEYPAD | '7'))
1612 dir = 7;
1613 else if (button == (MOD_NUM_KEYPAD | '1'))
1614 dir = 5;
1615 else if (button == (MOD_NUM_KEYPAD | '9'))
1616 dir = 1;
1617 else if (button == (MOD_NUM_KEYPAD | '3'))
1618 dir = 3;
1619 else if (IS_CURSOR_SELECT(button) &&
1620 state->soln && state->solnpos < state->soln->len)
1621 dir = state->soln->list[state->solnpos];
1622
1623 if (dir < 0)
1624 return NULL;
1625
1626 /*
1627 * Reject the move if we can't make it at all due to a wall
1628 * being in the way.
1629 */
1630 if (AT(w, h, state->grid, state->px+DX(dir), state->py+DY(dir)) == WALL)
1631 return NULL;
1632
1633 /*
1634 * Reject the move if we're dead!
1635 */
1636 if (state->dead)
1637 return NULL;
1638
1639 /*
1640 * Otherwise, we can make the move. All we need to specify is
1641 * the direction.
1642 */
1643 ui->just_made_move = TRUE;
1644 sprintf(buf, "%d", dir);
1645 return dupstr(buf);
1646}
1647
1648static void install_new_solution(game_state *ret, const char *move)
1649{
1650 int i;
1651 soln *sol;
1652 assert (*move == 'S');
1653 ++move;
1654
1655 sol = snew(soln);
1656 sol->len = strlen(move);
1657 sol->list = snewn(sol->len, unsigned char);
1658 for (i = 0; i < sol->len; ++i) sol->list[i] = move[i] - '0';
1659
1660 if (ret->soln && --ret->soln->refcount == 0) {
1661 sfree(ret->soln->list);
1662 sfree(ret->soln);
1663 }
1664
1665 ret->soln = sol;
1666 sol->refcount = 1;
1667
1668 ret->cheated = TRUE;
1669 ret->solnpos = 0;
1670}
1671
1672static void discard_solution(game_state *ret)
1673{
1674 --ret->soln->refcount;
1675 assert(ret->soln->refcount > 0); /* ret has a soln-pointing dup */
1676 ret->soln = NULL;
1677 ret->solnpos = 0;
1678}
1679
1680static game_state *execute_move(const game_state *state, const char *move)
1681{
1682 int w = state->p.w, h = state->p.h /*, wh = w*h */;
1683 int dir;
1684 game_state *ret;
1685
1686 if (*move == 'S') {
1687 /*
1688 * This is a solve move, so we don't actually _change_ the
1689 * grid but merely set up a stored solution path.
1690 */
1691 ret = dup_game(state);
1692 install_new_solution(ret, move);
1693 return ret;
1694 }
1695
1696 dir = atoi(move);
1697 if (dir < 0 || dir >= DIRECTIONS)
1698 return NULL; /* huh? */
1699
1700 if (state->dead)
1701 return NULL;
1702
1703 if (AT(w, h, state->grid, state->px+DX(dir), state->py+DY(dir)) == WALL)
1704 return NULL; /* wall in the way! */
1705
1706 /*
1707 * Now make the move.
1708 */
1709 ret = dup_game(state);
1710 ret->distance_moved = 0;
1711 while (1) {
1712 ret->px += DX(dir);
1713 ret->py += DY(dir);
1714 ret->distance_moved++;
1715
1716 if (AT(w, h, ret->grid, ret->px, ret->py) == GEM) {
1717 LV_AT(w, h, ret->grid, ret->px, ret->py) = BLANK;
1718 ret->gems--;
1719 }
1720
1721 if (AT(w, h, ret->grid, ret->px, ret->py) == MINE) {
1722 ret->dead = TRUE;
1723 break;
1724 }
1725
1726 if (AT(w, h, ret->grid, ret->px, ret->py) == STOP ||
1727 AT(w, h, ret->grid, ret->px+DX(dir),
1728 ret->py+DY(dir)) == WALL)
1729 break;
1730 }
1731
1732 if (ret->soln) {
1733 if (ret->dead || ret->gems == 0)
1734 discard_solution(ret);
1735 else if (ret->soln->list[ret->solnpos] == dir) {
1736 ++ret->solnpos;
1737 assert(ret->solnpos < ret->soln->len); /* or gems == 0 */
1738 assert(!ret->dead); /* or not a solution */
1739 } else {
1740 char *error = NULL, *soln = solve_game(NULL, ret, NULL, &error);
1741 if (!error) {
1742 install_new_solution(ret, soln);
1743 sfree(soln);
1744 } else discard_solution(ret);
1745 }
1746 }
1747
1748 return ret;
1749}
1750
1751/* ----------------------------------------------------------------------
1752 * Drawing routines.
1753 */
1754
1755static void game_compute_size(const game_params *params, int tilesize,
1756 int *x, int *y)
1757{
1758 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
1759 struct { int tilesize; } ads, *ds = &ads;
1760 ads.tilesize = tilesize;
1761
1762 *x = 2 * BORDER + 1 + params->w * TILESIZE;
1763 *y = 2 * BORDER + 1 + params->h * TILESIZE;
1764}
1765
1766static void game_set_size(drawing *dr, game_drawstate *ds,
1767 const game_params *params, int tilesize)
1768{
1769 ds->tilesize = tilesize;
1770
1771 assert(!ds->player_background); /* set_size is never called twice */
1772 assert(!ds->player_bg_saved);
1773
1774 ds->player_background = blitter_new(dr, TILESIZE, TILESIZE);
1775}
1776
1777static float *game_colours(frontend *fe, int *ncolours)
1778{
1779 float *ret = snewn(3 * NCOLOURS, float);
1780 int i;
1781
1782 game_mkhighlight(fe, ret, COL_BACKGROUND, COL_HIGHLIGHT, COL_LOWLIGHT);
1783
1784 ret[COL_OUTLINE * 3 + 0] = 0.0F;
1785 ret[COL_OUTLINE * 3 + 1] = 0.0F;
1786 ret[COL_OUTLINE * 3 + 2] = 0.0F;
1787
1788 ret[COL_PLAYER * 3 + 0] = 0.0F;
1789 ret[COL_PLAYER * 3 + 1] = 1.0F;
1790 ret[COL_PLAYER * 3 + 2] = 0.0F;
1791
1792 ret[COL_DEAD_PLAYER * 3 + 0] = 1.0F;
1793 ret[COL_DEAD_PLAYER * 3 + 1] = 0.0F;
1794 ret[COL_DEAD_PLAYER * 3 + 2] = 0.0F;
1795
1796 ret[COL_MINE * 3 + 0] = 0.0F;
1797 ret[COL_MINE * 3 + 1] = 0.0F;
1798 ret[COL_MINE * 3 + 2] = 0.0F;
1799
1800 ret[COL_GEM * 3 + 0] = 0.6F;
1801 ret[COL_GEM * 3 + 1] = 1.0F;
1802 ret[COL_GEM * 3 + 2] = 1.0F;
1803
1804 for (i = 0; i < 3; i++) {
1805 ret[COL_WALL * 3 + i] = (3 * ret[COL_BACKGROUND * 3 + i] +
1806 1 * ret[COL_HIGHLIGHT * 3 + i]) / 4;
1807 }
1808
1809 ret[COL_HINT * 3 + 0] = 1.0F;
1810 ret[COL_HINT * 3 + 1] = 1.0F;
1811 ret[COL_HINT * 3 + 2] = 0.0F;
1812
1813 *ncolours = NCOLOURS;
1814 return ret;
1815}
1816
1817static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state)
1818{
1819 int w = state->p.w, h = state->p.h, wh = w*h;
1820 struct game_drawstate *ds = snew(struct game_drawstate);
1821 int i;
1822
1823 ds->tilesize = 0;
1824
1825 /* We can't allocate the blitter rectangle for the player background
1826 * until we know what size to make it. */
1827 ds->player_background = NULL;
1828 ds->player_bg_saved = FALSE;
1829 ds->pbgx = ds->pbgy = -1;
1830
1831 ds->p = state->p; /* structure copy */
1832 ds->started = FALSE;
1833 ds->grid = snewn(wh, unsigned short);
1834 for (i = 0; i < wh; i++)
1835 ds->grid[i] = UNDRAWN;
1836
1837 return ds;
1838}
1839
1840static void game_free_drawstate(drawing *dr, game_drawstate *ds)
1841{
1842 if (ds->player_background)
1843 blitter_free(dr, ds->player_background);
1844 sfree(ds->grid);
1845 sfree(ds);
1846}
1847
1848static void draw_player(drawing *dr, game_drawstate *ds, int x, int y,
1849 int dead, int hintdir)
1850{
1851 if (dead) {
1852 int coords[DIRECTIONS*4];
1853 int d;
1854
1855 for (d = 0; d < DIRECTIONS; d++) {
1856 float x1, y1, x2, y2, x3, y3, len;
1857
1858 x1 = DX(d);
1859 y1 = DY(d);
1860 len = sqrt(x1*x1+y1*y1); x1 /= len; y1 /= len;
1861
1862 x3 = DX(d+1);
1863 y3 = DY(d+1);
1864 len = sqrt(x3*x3+y3*y3); x3 /= len; y3 /= len;
1865
1866 x2 = (x1+x3) / 4;
1867 y2 = (y1+y3) / 4;
1868
1869 coords[d*4+0] = x + TILESIZE/2 + (int)((TILESIZE*3/7) * x1);
1870 coords[d*4+1] = y + TILESIZE/2 + (int)((TILESIZE*3/7) * y1);
1871 coords[d*4+2] = x + TILESIZE/2 + (int)((TILESIZE*3/7) * x2);
1872 coords[d*4+3] = y + TILESIZE/2 + (int)((TILESIZE*3/7) * y2);
1873 }
1874 draw_polygon(dr, coords, DIRECTIONS*2, COL_DEAD_PLAYER, COL_OUTLINE);
1875 } else {
1876 draw_circle(dr, x + TILESIZE/2, y + TILESIZE/2,
1877 TILESIZE/3, COL_PLAYER, COL_OUTLINE);
1878 }
1879
1880 if (!dead && hintdir >= 0) {
1881 float scale = (DX(hintdir) && DY(hintdir) ? 0.8F : 1.0F);
1882 int ax = (TILESIZE*2/5) * scale * DX(hintdir);
1883 int ay = (TILESIZE*2/5) * scale * DY(hintdir);
1884 int px = -ay, py = ax;
1885 int ox = x + TILESIZE/2, oy = y + TILESIZE/2;
1886 int coords[14], *c;
1887
1888 c = coords;
1889 *c++ = ox + px/9;
1890 *c++ = oy + py/9;
1891 *c++ = ox + px/9 + ax*2/3;
1892 *c++ = oy + py/9 + ay*2/3;
1893 *c++ = ox + px/3 + ax*2/3;
1894 *c++ = oy + py/3 + ay*2/3;
1895 *c++ = ox + ax;
1896 *c++ = oy + ay;
1897 *c++ = ox - px/3 + ax*2/3;
1898 *c++ = oy - py/3 + ay*2/3;
1899 *c++ = ox - px/9 + ax*2/3;
1900 *c++ = oy - py/9 + ay*2/3;
1901 *c++ = ox - px/9;
1902 *c++ = oy - py/9;
1903 draw_polygon(dr, coords, 7, COL_HINT, COL_OUTLINE);
1904 }
1905
1906 draw_update(dr, x, y, TILESIZE, TILESIZE);
1907}
1908
1909#define FLASH_DEAD 0x100
1910#define FLASH_WIN 0x200
1911#define FLASH_MASK 0x300
1912
1913static void draw_tile(drawing *dr, game_drawstate *ds, int x, int y, int v)
1914{
1915 int tx = COORD(x), ty = COORD(y);
1916 int bg = (v & FLASH_DEAD ? COL_DEAD_PLAYER :
1917 v & FLASH_WIN ? COL_HIGHLIGHT : COL_BACKGROUND);
1918
1919 v &= ~FLASH_MASK;
1920
1921 clip(dr, tx+1, ty+1, TILESIZE-1, TILESIZE-1);
1922 draw_rect(dr, tx+1, ty+1, TILESIZE-1, TILESIZE-1, bg);
1923
1924 if (v == WALL) {
1925 int coords[6];
1926
1927 coords[0] = tx + TILESIZE;
1928 coords[1] = ty + TILESIZE;
1929 coords[2] = tx + TILESIZE;
1930 coords[3] = ty + 1;
1931 coords[4] = tx + 1;
1932 coords[5] = ty + TILESIZE;
1933 draw_polygon(dr, coords, 3, COL_LOWLIGHT, COL_LOWLIGHT);
1934
1935 coords[0] = tx + 1;
1936 coords[1] = ty + 1;
1937 draw_polygon(dr, coords, 3, COL_HIGHLIGHT, COL_HIGHLIGHT);
1938
1939 draw_rect(dr, tx + 1 + HIGHLIGHT_WIDTH, ty + 1 + HIGHLIGHT_WIDTH,
1940 TILESIZE - 2*HIGHLIGHT_WIDTH,
1941 TILESIZE - 2*HIGHLIGHT_WIDTH, COL_WALL);
1942 } else if (v == MINE) {
1943 int cx = tx + TILESIZE / 2;
1944 int cy = ty + TILESIZE / 2;
1945 int r = TILESIZE / 2 - 3;
1946
1947 draw_circle(dr, cx, cy, 5*r/6, COL_MINE, COL_MINE);
1948 draw_rect(dr, cx - r/6, cy - r, 2*(r/6)+1, 2*r+1, COL_MINE);
1949 draw_rect(dr, cx - r, cy - r/6, 2*r+1, 2*(r/6)+1, COL_MINE);
1950 draw_rect(dr, cx-r/3, cy-r/3, r/3, r/4, COL_HIGHLIGHT);
1951 } else if (v == STOP) {
1952 draw_circle(dr, tx + TILESIZE/2, ty + TILESIZE/2,
1953 TILESIZE*3/7, -1, COL_OUTLINE);
1954 draw_rect(dr, tx + TILESIZE*3/7, ty+1,
1955 TILESIZE - 2*(TILESIZE*3/7) + 1, TILESIZE-1, bg);
1956 draw_rect(dr, tx+1, ty + TILESIZE*3/7,
1957 TILESIZE-1, TILESIZE - 2*(TILESIZE*3/7) + 1, bg);
1958 } else if (v == GEM) {
1959 int coords[8];
1960
1961 coords[0] = tx+TILESIZE/2;
1962 coords[1] = ty+TILESIZE/2-TILESIZE*5/14;
1963 coords[2] = tx+TILESIZE/2-TILESIZE*5/14;
1964 coords[3] = ty+TILESIZE/2;
1965 coords[4] = tx+TILESIZE/2;
1966 coords[5] = ty+TILESIZE/2+TILESIZE*5/14;
1967 coords[6] = tx+TILESIZE/2+TILESIZE*5/14;
1968 coords[7] = ty+TILESIZE/2;
1969
1970 draw_polygon(dr, coords, 4, COL_GEM, COL_OUTLINE);
1971 }
1972
1973 unclip(dr);
1974 draw_update(dr, tx, ty, TILESIZE, TILESIZE);
1975}
1976
1977#define BASE_ANIM_LENGTH 0.1F
1978#define FLASH_LENGTH 0.3F
1979
1980static void game_redraw(drawing *dr, game_drawstate *ds,
1981 const game_state *oldstate, const game_state *state,
1982 int dir, const game_ui *ui,
1983 float animtime, float flashtime)
1984{
1985 int w = state->p.w, h = state->p.h /*, wh = w*h */;
1986 int x, y;
1987 float ap;
1988 int player_dist;
1989 int flashtype;
1990 int gems, deaths;
1991 char status[256];
1992
1993 if (flashtime &&
1994 !((int)(flashtime * 3 / FLASH_LENGTH) % 2))
1995 flashtype = ui->flashtype;
1996 else
1997 flashtype = 0;
1998
1999 /*
2000 * Erase the player sprite.
2001 */
2002 if (ds->player_bg_saved) {
2003 assert(ds->player_background);
2004 blitter_load(dr, ds->player_background, ds->pbgx, ds->pbgy);
2005 draw_update(dr, ds->pbgx, ds->pbgy, TILESIZE, TILESIZE);
2006 ds->player_bg_saved = FALSE;
2007 }
2008
2009 /*
2010 * Initialise a fresh drawstate.
2011 */
2012 if (!ds->started) {
2013 int wid, ht;
2014
2015 /*
2016 * Blank out the window initially.
2017 */
2018 game_compute_size(&ds->p, TILESIZE, &wid, &ht);
2019 draw_rect(dr, 0, 0, wid, ht, COL_BACKGROUND);
2020 draw_update(dr, 0, 0, wid, ht);
2021
2022 /*
2023 * Draw the grid lines.
2024 */
2025 for (y = 0; y <= h; y++)
2026 draw_line(dr, COORD(0), COORD(y), COORD(w), COORD(y),
2027 COL_LOWLIGHT);
2028 for (x = 0; x <= w; x++)
2029 draw_line(dr, COORD(x), COORD(0), COORD(x), COORD(h),
2030 COL_LOWLIGHT);
2031
2032 ds->started = TRUE;
2033 }
2034
2035 /*
2036 * If we're in the process of animating a move, let's start by
2037 * working out how far the player has moved from their _older_
2038 * state.
2039 */
2040 if (oldstate) {
2041 ap = animtime / ui->anim_length;
2042 player_dist = ap * (dir > 0 ? state : oldstate)->distance_moved;
2043 } else {
2044 player_dist = 0;
2045 ap = 0.0F;
2046 }
2047
2048 /*
2049 * Draw the grid contents.
2050 *
2051 * We count the gems as we go round this loop, for the purposes
2052 * of the status bar. Of course we have a gems counter in the
2053 * game_state already, but if we do the counting in this loop
2054 * then it tracks gems being picked up in a sliding move, and
2055 * updates one by one.
2056 */
2057 gems = 0;
2058 for (y = 0; y < h; y++)
2059 for (x = 0; x < w; x++) {
2060 unsigned short v = (unsigned char)state->grid[y*w+x];
2061
2062 /*
2063 * Special case: if the player is in the process of
2064 * moving over a gem, we draw the gem iff they haven't
2065 * gone past it yet.
2066 */
2067 if (oldstate && oldstate->grid[y*w+x] != state->grid[y*w+x]) {
2068 /*
2069 * Compute the distance from this square to the
2070 * original player position.
2071 */
2072 int dist = max(abs(x - oldstate->px), abs(y - oldstate->py));
2073
2074 /*
2075 * If the player has reached here, use the new grid
2076 * element. Otherwise use the old one.
2077 */
2078 if (player_dist < dist)
2079 v = oldstate->grid[y*w+x];
2080 else
2081 v = state->grid[y*w+x];
2082 }
2083
2084 /*
2085 * Special case: erase the mine the dead player is
2086 * sitting on. Only at the end of the move.
2087 */
2088 if (v == MINE && !oldstate && state->dead &&
2089 x == state->px && y == state->py)
2090 v = BLANK;
2091
2092 if (v == GEM)
2093 gems++;
2094
2095 v |= flashtype;
2096
2097 if (ds->grid[y*w+x] != v) {
2098 draw_tile(dr, ds, x, y, v);
2099 ds->grid[y*w+x] = v;
2100 }
2101 }
2102
2103 /*
2104 * Gem counter in the status bar. We replace it with
2105 * `COMPLETED!' when it reaches zero ... or rather, when the
2106 * _current state_'s gem counter is zero. (Thus, `Gems: 0' is
2107 * shown between the collection of the last gem and the
2108 * completion of the move animation that did it.)
2109 */
2110 if (state->dead && (!oldstate || oldstate->dead)) {
2111 sprintf(status, "DEAD!");
2112 } else if (state->gems || (oldstate && oldstate->gems)) {
2113 if (state->cheated)
2114 sprintf(status, "Auto-solver used. ");
2115 else
2116 *status = '\0';
2117 sprintf(status + strlen(status), "Gems: %d", gems);
2118 } else if (state->cheated) {
2119 sprintf(status, "Auto-solved.");
2120 } else {
2121 sprintf(status, "COMPLETED!");
2122 }
2123 /* We subtract one from the visible death counter if we're still
2124 * animating the move at the end of which the death took place. */
2125 deaths = ui->deaths;
2126 if (oldstate && ui->just_died) {
2127 assert(deaths > 0);
2128 deaths--;
2129 }
2130 if (deaths)
2131 sprintf(status + strlen(status), " Deaths: %d", deaths);
2132 status_bar(dr, status);
2133
2134 /*
2135 * Draw the player sprite.
2136 */
2137 assert(!ds->player_bg_saved);
2138 assert(ds->player_background);
2139 {
2140 int ox, oy, nx, ny;
2141 nx = COORD(state->px);
2142 ny = COORD(state->py);
2143 if (oldstate) {
2144 ox = COORD(oldstate->px);
2145 oy = COORD(oldstate->py);
2146 } else {
2147 ox = nx;
2148 oy = ny;
2149 }
2150 ds->pbgx = ox + ap * (nx - ox);
2151 ds->pbgy = oy + ap * (ny - oy);
2152 }
2153 blitter_save(dr, ds->player_background, ds->pbgx, ds->pbgy);
2154 draw_player(dr, ds, ds->pbgx, ds->pbgy,
2155 (state->dead && !oldstate),
2156 (!oldstate && state->soln ?
2157 state->soln->list[state->solnpos] : -1));
2158 ds->player_bg_saved = TRUE;
2159}
2160
2161static float game_anim_length(const game_state *oldstate,
2162 const game_state *newstate, int dir, game_ui *ui)
2163{
2164 int dist;
2165 if (dir > 0)
2166 dist = newstate->distance_moved;
2167 else
2168 dist = oldstate->distance_moved;
2169 ui->anim_length = sqrt(dist) * BASE_ANIM_LENGTH;
2170 return ui->anim_length;
2171}
2172
2173static float game_flash_length(const game_state *oldstate,
2174 const game_state *newstate, int dir, game_ui *ui)
2175{
2176 if (!oldstate->dead && newstate->dead) {
2177 ui->flashtype = FLASH_DEAD;
2178 return FLASH_LENGTH;
2179 } else if (oldstate->gems && !newstate->gems) {
2180 ui->flashtype = FLASH_WIN;
2181 return FLASH_LENGTH;
2182 }
2183 return 0.0F;
2184}
2185
2186static int game_status(const game_state *state)
2187{
2188 /*
2189 * We never report the game as lost, on the grounds that if the
2190 * player has died they're quite likely to want to undo and carry
2191 * on.
2192 */
2193 return state->gems == 0 ? +1 : 0;
2194}
2195
2196static int game_timing_state(const game_state *state, game_ui *ui)
2197{
2198 return TRUE;
2199}
2200
2201static void game_print_size(const game_params *params, float *x, float *y)
2202{
2203}
2204
2205static void game_print(drawing *dr, const game_state *state, int tilesize)
2206{
2207}
2208
2209#ifdef COMBINED
2210#define thegame inertia
2211#endif
2212
2213const struct game thegame = {
2214 "Inertia", "games.inertia", "inertia",
2215 default_params,
2216 game_fetch_preset, NULL,
2217 decode_params,
2218 encode_params,
2219 free_params,
2220 dup_params,
2221 TRUE, game_configure, custom_params,
2222 validate_params,
2223 new_game_desc,
2224 validate_desc,
2225 new_game,
2226 dup_game,
2227 free_game,
2228 TRUE, solve_game,
2229 TRUE, game_can_format_as_text_now, game_text_format,
2230 new_ui,
2231 free_ui,
2232 encode_ui,
2233 decode_ui,
2234 game_changed_state,
2235 interpret_move,
2236 execute_move,
2237 PREFERRED_TILESIZE, game_compute_size, game_set_size,
2238 game_colours,
2239 game_new_drawstate,
2240 game_free_drawstate,
2241 game_redraw,
2242 game_anim_length,
2243 game_flash_length,
2244 game_status,
2245 FALSE, FALSE, game_print_size, game_print,
2246 TRUE, /* wants_statusbar */
2247 FALSE, game_timing_state,
2248 0, /* flags */
2249};
generated by cgit v1.2.3 (git 2.39.1) at 2024-09-17 22:35:35 +0000