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