2 * inertia.c: Game involving navigating round a grid picking up
5 * Game rules and basic generator design by Ben Olmstead.
6 * This re-implementation was written by Simon Tatham.
18 /* Used in the game_state */
25 /* Used in the game IDs */
28 /* Used in the game generation */
31 /* Used only in the game_drawstate*/
35 #define DP1 (DIRECTIONS+1)
36 #define DX(dir) ( (dir) & 3 ? (((dir) & 7) > 4 ? -1 : +1) : 0 )
37 #define DY(dir) ( DX((dir)+6) )
40 * Lvalue macro which expects x and y to be in range.
42 #define LV_AT(w, h, grid, x, y) ( (grid)[(y)*(w)+(x)] )
45 * Rvalue macro which can cope with x and y being out of range.
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) )
86 static game_params *default_params(void)
88 game_params *ret = snew(game_params);
91 #ifdef PORTRAIT_SCREEN
99 static void free_params(game_params *params)
104 static game_params *dup_params(const game_params *params)
106 game_params *ret = snew(game_params);
107 *ret = *params; /* structure copy */
111 static const struct game_params inertia_presets[] = {
112 #ifdef PORTRAIT_SCREEN
123 static int game_fetch_preset(int i, char **name, game_params **params)
129 if (i < 0 || i >= lenof(inertia_presets))
132 p = inertia_presets[i];
133 ret = dup_params(&p);
134 sprintf(namebuf, "%dx%d", ret->w, ret->h);
135 retname = dupstr(namebuf);
142 static void decode_params(game_params *params, char const *string)
144 params->w = params->h = atoi(string);
145 while (*string && isdigit((unsigned char)*string)) string++;
146 if (*string == 'x') {
148 params->h = atoi(string);
152 static char *encode_params(const game_params *params, int full)
156 sprintf(data, "%dx%d", params->w, params->h);
161 static config_item *game_configure(const game_params *params)
166 ret = snewn(3, config_item);
168 ret[0].name = "Width";
169 ret[0].type = C_STRING;
170 sprintf(buf, "%d", params->w);
171 ret[0].u.string.sval = dupstr(buf);
173 ret[1].name = "Height";
174 ret[1].type = C_STRING;
175 sprintf(buf, "%d", params->h);
176 ret[1].u.string.sval = dupstr(buf);
184 static game_params *custom_params(const config_item *cfg)
186 game_params *ret = snew(game_params);
188 ret->w = atoi(cfg[0].u.string.sval);
189 ret->h = atoi(cfg[1].u.string.sval);
194 static char *validate_params(const game_params *params, int full)
197 * Avoid completely degenerate cases which only have one
198 * row/column. We probably could generate completable puzzles
199 * of that shape, but they'd be forced to be extremely boring
200 * and at large sizes would take a while to happen upon at
203 if (params->w < 2 || params->h < 2)
204 return "Width and height must both be at least two";
207 * The grid construction algorithm creates 1/5 as many gems as
208 * grid squares, and must create at least one gem to have an
209 * actual puzzle. However, an area-five grid is ruled out by
210 * the above constraint, so the practical minimum is six.
212 if (params->w * params->h < 6)
213 return "Grid area must be at least six squares";
218 /* ----------------------------------------------------------------------
219 * Solver used by grid generator.
222 struct solver_scratch {
223 unsigned char *reachable_from, *reachable_to;
227 static struct solver_scratch *new_scratch(int w, int h)
229 struct solver_scratch *sc = snew(struct solver_scratch);
231 sc->reachable_from = snewn(w * h * DIRECTIONS, unsigned char);
232 sc->reachable_to = snewn(w * h * DIRECTIONS, unsigned char);
233 sc->positions = snewn(w * h * DIRECTIONS, int);
238 static void free_scratch(struct solver_scratch *sc)
240 sfree(sc->reachable_from);
241 sfree(sc->reachable_to);
242 sfree(sc->positions);
246 static int can_go(int w, int h, char *grid,
247 int x1, int y1, int dir1, int x2, int y2, int dir2)
250 * Returns TRUE if we can transition directly from (x1,y1)
251 * going in direction dir1, to (x2,y2) going in direction dir2.
255 * If we're actually in the middle of an unoccupyable square,
256 * we cannot make any move.
258 if (AT(w, h, grid, x1, y1) == WALL ||
259 AT(w, h, grid, x1, y1) == MINE)
263 * If a move is capable of stopping at x1,y1,dir1, and x2,y2 is
264 * the same coordinate as x1,y1, then we can make the
265 * transition (by stopping and changing direction).
267 * For this to be the case, we have to either have a wall
268 * beyond x1,y1,dir1, or have a stop on x1,y1.
270 if (x2 == x1 && y2 == y1 &&
271 (AT(w, h, grid, x1, y1) == STOP ||
272 AT(w, h, grid, x1, y1) == START ||
273 AT(w, h, grid, x1+DX(dir1), y1+DY(dir1)) == WALL))
277 * If a move is capable of continuing here, then x1,y1,dir1 can
278 * move one space further on.
280 if (x2 == x1+DX(dir1) && y2 == y1+DY(dir1) && dir1 == dir2 &&
281 (AT(w, h, grid, x2, y2) == BLANK ||
282 AT(w, h, grid, x2, y2) == GEM ||
283 AT(w, h, grid, x2, y2) == STOP ||
284 AT(w, h, grid, x2, y2) == START))
293 static int find_gem_candidates(int w, int h, char *grid,
294 struct solver_scratch *sc)
298 int sx, sy, gx, gy, gd, pass, possgems;
301 * This function finds all the candidate gem squares, which are
302 * precisely those squares which can be picked up on a loop
303 * from the starting point back to the starting point. Doing
304 * this may involve passing through such a square in the middle
305 * of a move; so simple breadth-first search over the _squares_
306 * of the grid isn't quite adequate, because it might be that
307 * we can only reach a gem from the start by moving over it in
308 * one direction, but can only return to the start if we were
309 * moving over it in another direction.
311 * Instead, we BFS over a space which mentions each grid square
312 * eight times - once for each direction. We also BFS twice:
313 * once to find out what square+direction pairs we can reach
314 * _from_ the start point, and once to find out what pairs we
315 * can reach the start point from. Then a square is reachable
316 * if any of the eight directions for that square has both
320 memset(sc->reachable_from, 0, wh * DIRECTIONS);
321 memset(sc->reachable_to, 0, wh * DIRECTIONS);
324 * Find the starting square.
326 sx = -1; /* placate optimiser */
327 for (sy = 0; sy < h; sy++) {
328 for (sx = 0; sx < w; sx++)
329 if (AT(w, h, grid, sx, sy) == START)
336 for (pass = 0; pass < 2; pass++) {
337 unsigned char *reachable = (pass == 0 ? sc->reachable_from :
339 int sign = (pass == 0 ? +1 : -1);
342 #ifdef SOLVER_DIAGNOSTICS
343 printf("starting pass %d\n", pass);
347 * `head' and `tail' are indices within sc->positions which
348 * track the list of board positions left to process.
351 for (dir = 0; dir < DIRECTIONS; dir++) {
352 int index = (sy*w+sx)*DIRECTIONS+dir;
353 sc->positions[tail++] = index;
354 reachable[index] = TRUE;
355 #ifdef SOLVER_DIAGNOSTICS
356 printf("starting point %d,%d,%d\n", sx, sy, dir);
361 * Now repeatedly pick an element off the list and process
364 while (head < tail) {
365 int index = sc->positions[head++];
366 int dir = index % DIRECTIONS;
367 int x = (index / DIRECTIONS) % w;
368 int y = index / (w * DIRECTIONS);
369 int n, x2, y2, d2, i2;
371 #ifdef SOLVER_DIAGNOSTICS
372 printf("processing point %d,%d,%d\n", x, y, dir);
375 * The places we attempt to switch to here are:
376 * - each possible direction change (all the other
377 * directions in this square)
378 * - one step further in the direction we're going (or
379 * one step back, if we're in the reachable_to pass).
381 for (n = -1; n < DIRECTIONS; n++) {
383 x2 = x + sign * DX(dir);
384 y2 = y + sign * DY(dir);
391 i2 = (y2*w+x2)*DIRECTIONS+d2;
392 if (x2 >= 0 && x2 < w &&
396 #ifdef SOLVER_DIAGNOSTICS
397 printf(" trying point %d,%d,%d", x2, y2, d2);
400 ok = can_go(w, h, grid, x, y, dir, x2, y2, d2);
402 ok = can_go(w, h, grid, x2, y2, d2, x, y, dir);
403 #ifdef SOLVER_DIAGNOSTICS
404 printf(" - %sok\n", ok ? "" : "not ");
407 sc->positions[tail++] = i2;
408 reachable[i2] = TRUE;
416 * And that should be it. Now all we have to do is find the
417 * squares for which there exists _some_ direction such that
418 * the square plus that direction form a tuple which is both
419 * reachable from the start and reachable to the start.
422 for (gy = 0; gy < h; gy++)
423 for (gx = 0; gx < w; gx++)
424 if (AT(w, h, grid, gx, gy) == BLANK) {
425 for (gd = 0; gd < DIRECTIONS; gd++) {
426 int index = (gy*w+gx)*DIRECTIONS+gd;
427 if (sc->reachable_from[index] && sc->reachable_to[index]) {
428 #ifdef SOLVER_DIAGNOSTICS
429 printf("space at %d,%d is reachable via"
430 " direction %d\n", gx, gy, gd);
432 LV_AT(w, h, grid, gx, gy) = POSSGEM;
442 /* ----------------------------------------------------------------------
443 * Grid generation code.
446 static char *gengrid(int w, int h, random_state *rs)
449 char *grid = snewn(wh+1, char);
450 struct solver_scratch *sc = new_scratch(w, h);
451 int maxdist_threshold, tries;
453 maxdist_threshold = 2;
459 int *dist, *list, head, tail, maxdist;
462 * We're going to fill the grid with the five basic piece
463 * types in about 1/5 proportion. For the moment, though,
464 * we leave out the gems, because we'll put those in
465 * _after_ we run the solver to tell us where the viable
469 for (j = 0; j < wh/5; j++)
471 for (j = 0; j < wh/5; j++)
473 for (j = 0; j < wh/5; j++)
479 shuffle(grid, wh, sizeof(*grid), rs);
482 * Find the viable gem locations, and immediately give up
483 * and try again if there aren't enough of them.
485 possgems = find_gem_candidates(w, h, grid, sc);
490 * We _could_ now select wh/5 of the POSSGEMs and set them
491 * to GEM, and have a viable level. However, there's a
492 * chance that a large chunk of the level will turn out to
493 * be unreachable, so first we test for that.
495 * We do this by finding the largest distance from any
496 * square to the nearest POSSGEM, by breadth-first search.
497 * If this is above a critical threshold, we abort and try
500 * (This search is purely geometric, without regard to
501 * walls and long ways round.)
503 dist = sc->positions;
504 list = sc->positions + wh;
505 for (i = 0; i < wh; i++)
508 for (i = 0; i < wh; i++)
509 if (grid[i] == POSSGEM) {
514 while (head < tail) {
518 if (maxdist < dist[pos])
524 for (d = 0; d < DIRECTIONS; d++) {
530 if (x2 >= 0 && x2 < w && y2 >= 0 && y2 < h) {
533 dist[p2] = dist[pos] + 1;
539 assert(head == wh && tail == wh);
542 * Now abandon this grid and go round again if maxdist is
543 * above the required threshold.
545 * We can safely start the threshold as low as 2. As we
546 * accumulate failed generation attempts, we gradually
547 * raise it as we get more desperate.
549 if (maxdist > maxdist_threshold) {
559 * Now our reachable squares are plausibly evenly
560 * distributed over the grid. I'm not actually going to
561 * _enforce_ that I place the gems in such a way as not to
562 * increase that maxdist value; I'm now just going to trust
563 * to the RNG to pick a sensible subset of the POSSGEMs.
566 for (i = 0; i < wh; i++)
567 if (grid[i] == POSSGEM)
569 shuffle(list, j, sizeof(*list), rs);
570 for (i = 0; i < j; i++)
571 grid[list[i]] = (i < wh/5 ? GEM : BLANK);
582 static char *new_game_desc(const game_params *params, random_state *rs,
583 char **aux, int interactive)
585 return gengrid(params->w, params->h, rs);
588 static char *validate_desc(const game_params *params, const char *desc)
590 int w = params->w, h = params->h, wh = w*h;
591 int starts = 0, gems = 0, i;
593 for (i = 0; i < wh; i++) {
595 return "Not enough data to fill grid";
596 if (desc[i] != WALL && desc[i] != START && desc[i] != STOP &&
597 desc[i] != GEM && desc[i] != MINE && desc[i] != BLANK)
598 return "Unrecognised character in game description";
599 if (desc[i] == START)
605 return "Too much data to fill grid";
607 return "No starting square specified";
609 return "More than one starting square specified";
611 return "No gems specified";
616 static game_state *new_game(midend *me, const game_params *params,
619 int w = params->w, h = params->h, wh = w*h;
621 game_state *state = snew(game_state);
623 state->p = *params; /* structure copy */
625 state->grid = snewn(wh, char);
626 assert(strlen(desc) == wh);
627 memcpy(state->grid, desc, wh);
629 state->px = state->py = -1;
631 for (i = 0; i < wh; i++) {
632 if (state->grid[i] == START) {
633 state->grid[i] = STOP;
636 } else if (state->grid[i] == GEM) {
641 assert(state->gems > 0);
642 assert(state->px >= 0 && state->py >= 0);
644 state->distance_moved = 0;
647 state->cheated = FALSE;
654 static game_state *dup_game(const game_state *state)
656 int w = state->p.w, h = state->p.h, wh = w*h;
657 game_state *ret = snew(game_state);
662 ret->gems = state->gems;
663 ret->grid = snewn(wh, char);
664 ret->distance_moved = state->distance_moved;
666 memcpy(ret->grid, state->grid, wh);
667 ret->cheated = state->cheated;
668 ret->soln = state->soln;
670 ret->soln->refcount++;
671 ret->solnpos = state->solnpos;
676 static void free_game(game_state *state)
678 if (state->soln && --state->soln->refcount == 0) {
679 sfree(state->soln->list);
687 * Internal function used by solver.
689 static int move_goes_to(int w, int h, char *grid, int x, int y, int d)
694 * See where we'd get to if we made this move.
696 dr = -1; /* placate optimiser */
698 if (AT(w, h, grid, x+DX(d), y+DY(d)) == WALL) {
699 dr = DIRECTIONS; /* hit a wall, so end up stationary */
704 if (AT(w, h, grid, x, y) == STOP) {
705 dr = DIRECTIONS; /* hit a stop, so end up stationary */
708 if (AT(w, h, grid, x, y) == GEM) {
709 dr = d; /* hit a gem, so we're still moving */
712 if (AT(w, h, grid, x, y) == MINE)
713 return -1; /* hit a mine, so move is invalid */
716 return (y*w+x)*DP1+dr;
719 static int compare_integers(const void *av, const void *bv)
721 const int *a = (const int *)av;
722 const int *b = (const int *)bv;
731 static char *solve_game(const game_state *state, const game_state *currstate,
732 const char *aux, char **error)
734 int w = currstate->p.w, h = currstate->p.h, wh = w*h;
735 int *nodes, *nodeindex, *edges, *backedges, *edgei, *backedgei, *circuit;
737 int *dist, *dist2, *list;
739 int circuitlen, circuitsize;
740 int head, tail, pass, i, j, n, x, y, d, dd;
741 char *err, *soln, *p;
744 * Before anything else, deal with the special case in which
745 * all the gems are already collected.
747 for (i = 0; i < wh; i++)
748 if (currstate->grid[i] == GEM)
751 *error = "Game is already solved";
756 * Solving Inertia is a question of first building up the graph
757 * of where you can get to from where, and secondly finding a
758 * tour of the graph which takes in every gem.
760 * This is of course a close cousin of the travelling salesman
761 * problem, which is NP-complete; so I rather doubt that any
762 * _optimal_ tour can be found in plausible time. Hence I'll
763 * restrict myself to merely finding a not-too-bad one.
765 * First construct the graph, by bfsing out move by move from
766 * the current player position. Graph vertices will be
767 * - every endpoint of a move (place the ball can be
769 * - every gem (place the ball can go through in motion).
770 * Vertices of this type have an associated direction, since
771 * if a gem can be collected by sliding through it in two
772 * different directions it doesn't follow that you can
773 * change direction at it.
775 * I'm going to refer to a non-directional vertex as
776 * (y*w+x)*DP1+DIRECTIONS, and a directional one as
781 * nodeindex[] maps node codes as shown above to numeric
782 * indices in the nodes[] array.
784 nodeindex = snewn(DP1*wh, int);
785 for (i = 0; i < DP1*wh; i++)
789 * Do the bfs to find all the interesting graph nodes.
791 nodes = snewn(DP1*wh, int);
794 nodes[tail] = (currstate->py * w + currstate->px) * DP1 + DIRECTIONS;
795 nodeindex[nodes[0]] = tail;
798 while (head < tail) {
799 int nc = nodes[head++], nnc;
804 * Plot all possible moves from this node. If the node is
805 * directed, there's only one.
807 for (dd = 0; dd < DIRECTIONS; dd++) {
812 if (d < DIRECTIONS && d != dd)
815 nnc = move_goes_to(w, h, currstate->grid, x, y, dd);
816 if (nnc >= 0 && nnc != nc) {
817 if (nodeindex[nnc] < 0) {
819 nodeindex[nnc] = tail;
828 * Now we know how many nodes we have, allocate the edge array
829 * and go through setting up the edges.
831 edges = snewn(DIRECTIONS*n, int);
832 edgei = snewn(n+1, int);
835 for (i = 0; i < n; i++) {
845 for (dd = 0; dd < DIRECTIONS; dd++) {
848 if (d >= DIRECTIONS || d == dd) {
849 nnc = move_goes_to(w, h, currstate->grid, x, y, dd);
851 if (nnc >= 0 && nnc != nc)
852 edges[nedges++] = nodeindex[nnc];
859 * Now set up the backedges array.
861 backedges = snewn(nedges, int);
862 backedgei = snewn(n+1, int);
863 for (i = j = 0; i < nedges; i++) {
864 while (j+1 < n && i >= edgei[j+1])
866 backedges[i] = edges[i] * n + j;
868 qsort(backedges, nedges, sizeof(int), compare_integers);
870 for (i = j = 0; i < nedges; i++) {
871 int k = backedges[i] / n;
876 backedgei[n] = nedges;
879 * Set up the initial tour. At all times, our tour is a circuit
880 * of graph vertices (which may, and probably will often,
881 * repeat vertices). To begin with, it's got exactly one vertex
882 * in it, which is the player's current starting point.
885 circuit = snewn(circuitsize, int);
887 circuit[circuitlen++] = 0; /* node index 0 is the starting posn */
890 * Track which gems are as yet unvisited.
892 unvisited = snewn(wh, int);
893 for (i = 0; i < wh; i++)
894 unvisited[i] = FALSE;
895 for (i = 0; i < wh; i++)
896 if (currstate->grid[i] == GEM)
900 * Allocate space for doing bfses inside the main loop.
902 dist = snewn(n, int);
903 dist2 = snewn(n, int);
904 list = snewn(n, int);
910 * Now enter the main loop, in each iteration of which we
911 * extend the tour to take in an as yet uncollected gem.
914 int target, n1, n2, bestdist, extralen, targetpos;
916 #ifdef TSP_DIAGNOSTICS
917 printf("circuit is");
918 for (i = 0; i < circuitlen; i++) {
919 int nc = nodes[circuit[i]];
920 printf(" (%d,%d,%d)", nc/DP1%w, nc/(DP1*w), nc%DP1);
923 printf("moves are ");
924 x = nodes[circuit[0]] / DP1 % w;
925 y = nodes[circuit[0]] / DP1 / w;
926 for (i = 1; i < circuitlen; i++) {
928 if (nodes[circuit[i]] % DP1 != DIRECTIONS)
930 x2 = nodes[circuit[i]] / DP1 % w;
931 y2 = nodes[circuit[i]] / DP1 / w;
932 dx = (x2 > x ? +1 : x2 < x ? -1 : 0);
933 dy = (y2 > y ? +1 : y2 < y ? -1 : 0);
934 for (d = 0; d < DIRECTIONS; d++)
935 if (DX(d) == dx && DY(d) == dy)
936 printf("%c", "89632147"[d]);
944 * First, start a pair of bfses at _every_ vertex currently
945 * in the tour, and extend them outwards to find the
946 * nearest as yet unreached gem vertex.
948 * This is largely a heuristic: we could pick _any_ doubly
949 * reachable node here and still get a valid tour as
950 * output. I hope that picking a nearby one will result in
951 * generally good tours.
953 for (pass = 0; pass < 2; pass++) {
954 int *ep = (pass == 0 ? edges : backedges);
955 int *ei = (pass == 0 ? edgei : backedgei);
956 int *dp = (pass == 0 ? dist : dist2);
958 for (i = 0; i < n; i++)
960 for (i = 0; i < circuitlen; i++) {
967 while (head < tail) {
968 int ni = list[head++];
969 for (i = ei[ni]; i < ei[ni+1]; i++) {
971 if (ti >= 0 && dp[ti] < 0) {
978 /* Now find the nearest unvisited gem. */
981 for (i = 0; i < n; i++) {
982 if (unvisited[nodes[i] / DP1] &&
983 dist[i] >= 0 && dist2[i] >= 0) {
984 int thisdist = dist[i] + dist2[i];
985 if (bestdist < 0 || bestdist > thisdist) {
994 * If we get to here, we haven't found a gem we can get
995 * at all, which means we terminate this loop.
1001 * Now we have a graph vertex at list[tail-1] which is an
1002 * unvisited gem. We want to add that vertex to our tour.
1003 * So we run two more breadth-first searches: one starting
1004 * from that vertex and following forward edges, and
1005 * another starting from the same vertex and following
1006 * backward edges. This allows us to determine, for each
1007 * node on the current tour, how quickly we can get both to
1008 * and from the target vertex from that node.
1010 #ifdef TSP_DIAGNOSTICS
1011 printf("target node is %d (%d,%d,%d)\n", target, nodes[target]/DP1%w,
1012 nodes[target]/DP1/w, nodes[target]%DP1);
1015 for (pass = 0; pass < 2; pass++) {
1016 int *ep = (pass == 0 ? edges : backedges);
1017 int *ei = (pass == 0 ? edgei : backedgei);
1018 int *dp = (pass == 0 ? dist : dist2);
1020 for (i = 0; i < n; i++)
1025 list[tail++] = target;
1027 while (head < tail) {
1028 int ni = list[head++];
1029 for (i = ei[ni]; i < ei[ni+1]; i++) {
1031 if (ti >= 0 && dp[ti] < 0) {
1032 dp[ti] = dp[ni] + 1;
1033 /*printf("pass %d: set dist of vertex %d to %d (via %d)\n", pass, ti, dp[ti], ni);*/
1041 * Now for every node n, dist[n] gives the length of the
1042 * shortest path from the target vertex to n, and dist2[n]
1043 * gives the length of the shortest path from n to the
1046 * Our next step is to search linearly along the tour to
1047 * find the optimum place to insert a trip to the target
1048 * vertex and back. Our two options are either
1049 * (a) to find two adjacent vertices A,B in the tour and
1050 * replace the edge A->B with the path A->target->B
1051 * (b) to find a single vertex X in the tour and replace
1052 * it with the complete round trip X->target->X.
1053 * We do whichever takes the fewest moves.
1057 for (i = 0; i < circuitlen; i++) {
1061 * Try a round trip from vertex i.
1063 if (dist[circuit[i]] >= 0 &&
1064 dist2[circuit[i]] >= 0) {
1065 thisdist = dist[circuit[i]] + dist2[circuit[i]];
1066 if (bestdist < 0 || thisdist < bestdist) {
1067 bestdist = thisdist;
1073 * Try a trip from vertex i via target to vertex i+1.
1075 if (i+1 < circuitlen &&
1076 dist2[circuit[i]] >= 0 &&
1077 dist[circuit[i+1]] >= 0) {
1078 thisdist = dist2[circuit[i]] + dist[circuit[i+1]];
1079 if (bestdist < 0 || thisdist < bestdist) {
1080 bestdist = thisdist;
1088 * We couldn't find a round trip taking in this gem _at
1091 err = "Unable to find a solution from this starting point";
1094 #ifdef TSP_DIAGNOSTICS
1095 printf("insertion point: n1=%d, n2=%d, dist=%d\n", n1, n2, bestdist);
1098 #ifdef TSP_DIAGNOSTICS
1099 printf("circuit before lengthening is");
1100 for (i = 0; i < circuitlen; i++) {
1101 printf(" %d", circuit[i]);
1107 * Now actually lengthen the tour to take in this round
1110 extralen = dist2[circuit[n1]] + dist[circuit[n2]];
1113 circuitlen += extralen;
1114 if (circuitlen >= circuitsize) {
1115 circuitsize = circuitlen + 256;
1116 circuit = sresize(circuit, circuitsize, int);
1118 memmove(circuit + n2 + extralen, circuit + n2,
1119 (circuitlen - n2 - extralen) * sizeof(int));
1122 #ifdef TSP_DIAGNOSTICS
1123 printf("circuit in middle of lengthening is");
1124 for (i = 0; i < circuitlen; i++) {
1125 printf(" %d", circuit[i]);
1131 * Find the shortest-path routes to and from the target,
1132 * and write them into the circuit.
1134 targetpos = n1 + dist2[circuit[n1]];
1135 assert(targetpos - dist2[circuit[n1]] == n1);
1136 assert(targetpos + dist[circuit[n2]] == n2);
1137 for (pass = 0; pass < 2; pass++) {
1138 int dir = (pass == 0 ? -1 : +1);
1139 int *ep = (pass == 0 ? backedges : edges);
1140 int *ei = (pass == 0 ? backedgei : edgei);
1141 int *dp = (pass == 0 ? dist : dist2);
1142 int nn = (pass == 0 ? n2 : n1);
1143 int ni = circuit[nn], ti, dest = nn;
1151 /*printf("pass %d: looking at vertex %d\n", pass, ni);*/
1152 for (i = ei[ni]; i < ei[ni+1]; i++) {
1154 if (ti >= 0 && dp[ti] == dp[ni] - 1)
1157 assert(i < ei[ni+1] && ti >= 0);
1162 #ifdef TSP_DIAGNOSTICS
1163 printf("circuit after lengthening is");
1164 for (i = 0; i < circuitlen; i++) {
1165 printf(" %d", circuit[i]);
1171 * Finally, mark all gems that the new piece of circuit
1172 * passes through as visited.
1174 for (i = n1; i <= n2; i++) {
1175 int pos = nodes[circuit[i]] / DP1;
1176 assert(pos >= 0 && pos < wh);
1177 unvisited[pos] = FALSE;
1181 #ifdef TSP_DIAGNOSTICS
1182 printf("before reduction, moves are ");
1183 x = nodes[circuit[0]] / DP1 % w;
1184 y = nodes[circuit[0]] / DP1 / w;
1185 for (i = 1; i < circuitlen; i++) {
1187 if (nodes[circuit[i]] % DP1 != DIRECTIONS)
1189 x2 = nodes[circuit[i]] / DP1 % w;
1190 y2 = nodes[circuit[i]] / DP1 / w;
1191 dx = (x2 > x ? +1 : x2 < x ? -1 : 0);
1192 dy = (y2 > y ? +1 : y2 < y ? -1 : 0);
1193 for (d = 0; d < DIRECTIONS; d++)
1194 if (DX(d) == dx && DY(d) == dy)
1195 printf("%c", "89632147"[d]);
1203 * That's got a basic solution. Now optimise it by removing
1204 * redundant sections of the circuit: it's entirely possible
1205 * that a piece of circuit we carefully inserted at one stage
1206 * to collect a gem has become pointless because the steps
1207 * required to collect some _later_ gem necessarily passed
1208 * through the same one.
1210 * So first we go through and work out how many times each gem
1211 * is collected. Then we look for maximal sections of circuit
1212 * which are redundant in the sense that their removal would
1213 * not reduce any gem's collection count to zero, and replace
1214 * each one with a bfs-derived fastest path between their
1218 int oldlen = circuitlen;
1221 for (dir = +1; dir >= -1; dir -= 2) {
1223 for (i = 0; i < wh; i++)
1225 for (i = 0; i < circuitlen; i++) {
1226 int xy = nodes[circuit[i]] / DP1;
1227 if (currstate->grid[xy] == GEM)
1232 * If there's any gem we didn't end up visiting at all,
1235 for (i = 0; i < wh; i++) {
1236 if (currstate->grid[i] == GEM && unvisited[i] == 0) {
1237 err = "Unable to find a solution from this starting point";
1244 for (i = j = (dir > 0 ? 0 : circuitlen-1);
1245 i < circuitlen && i >= 0;
1247 int xy = nodes[circuit[i]] / DP1;
1248 if (currstate->grid[xy] == GEM && unvisited[xy] > 1) {
1250 } else if (currstate->grid[xy] == GEM || i == circuitlen-1) {
1252 * circuit[i] collects a gem for the only time,
1253 * or is the last node in the circuit.
1254 * Therefore it cannot be removed; so we now
1255 * want to replace the path from circuit[j] to
1256 * circuit[i] with a bfs-shortest path.
1258 int p, q, k, dest, ni, ti, thisdist;
1261 * Set up the upper and lower bounds of the
1267 #ifdef TSP_DIAGNOSTICS
1268 printf("optimising section from %d - %d\n", p, q);
1271 for (k = 0; k < n; k++)
1275 dist[circuit[p]] = 0;
1276 list[tail++] = circuit[p];
1278 while (head < tail && dist[circuit[q]] < 0) {
1279 int ni = list[head++];
1280 for (k = edgei[ni]; k < edgei[ni+1]; k++) {
1282 if (ti >= 0 && dist[ti] < 0) {
1283 dist[ti] = dist[ni] + 1;
1289 thisdist = dist[circuit[q]];
1290 assert(thisdist >= 0 && thisdist <= q-p);
1292 memmove(circuit+p+thisdist, circuit+q,
1293 (circuitlen - q) * sizeof(int));
1299 i = q; /* resume loop from the right place */
1301 #ifdef TSP_DIAGNOSTICS
1302 printf("new section runs from %d - %d\n", p, q);
1310 /* printf("dest=%d circuitlen=%d ni=%d dist[ni]=%d\n", dest, circuitlen, ni, dist[ni]); */
1316 for (k = backedgei[ni]; k < backedgei[ni+1]; k++) {
1318 if (ti >= 0 && dist[ti] == dist[ni] - 1)
1321 assert(k < backedgei[ni+1] && ti >= 0);
1326 * Now re-increment the visit counts for the
1330 int xy = nodes[circuit[p]] / DP1;
1331 if (currstate->grid[xy] == GEM)
1337 #ifdef TSP_DIAGNOSTICS
1338 printf("during reduction, circuit is");
1339 for (k = 0; k < circuitlen; k++) {
1340 int nc = nodes[circuit[k]];
1341 printf(" (%d,%d,%d)", nc/DP1%w, nc/(DP1*w), nc%DP1);
1344 printf("moves are ");
1345 x = nodes[circuit[0]] / DP1 % w;
1346 y = nodes[circuit[0]] / DP1 / w;
1347 for (k = 1; k < circuitlen; k++) {
1349 if (nodes[circuit[k]] % DP1 != DIRECTIONS)
1351 x2 = nodes[circuit[k]] / DP1 % w;
1352 y2 = nodes[circuit[k]] / DP1 / w;
1353 dx = (x2 > x ? +1 : x2 < x ? -1 : 0);
1354 dy = (y2 > y ? +1 : y2 < y ? -1 : 0);
1355 for (d = 0; d < DIRECTIONS; d++)
1356 if (DX(d) == dx && DY(d) == dy)
1357 printf("%c", "89632147"[d]);
1366 #ifdef TSP_DIAGNOSTICS
1367 printf("after reduction, moves are ");
1368 x = nodes[circuit[0]] / DP1 % w;
1369 y = nodes[circuit[0]] / DP1 / w;
1370 for (i = 1; i < circuitlen; i++) {
1372 if (nodes[circuit[i]] % DP1 != DIRECTIONS)
1374 x2 = nodes[circuit[i]] / DP1 % w;
1375 y2 = nodes[circuit[i]] / DP1 / w;
1376 dx = (x2 > x ? +1 : x2 < x ? -1 : 0);
1377 dy = (y2 > y ? +1 : y2 < y ? -1 : 0);
1378 for (d = 0; d < DIRECTIONS; d++)
1379 if (DX(d) == dx && DY(d) == dy)
1380 printf("%c", "89632147"[d]);
1389 * If we've managed an entire reduction pass in each
1390 * direction and not made the solution any shorter, we're
1393 if (circuitlen == oldlen)
1398 * Encode the solution as a move string.
1401 soln = snewn(circuitlen+2, char);
1404 x = nodes[circuit[0]] / DP1 % w;
1405 y = nodes[circuit[0]] / DP1 / w;
1406 for (i = 1; i < circuitlen; i++) {
1408 if (nodes[circuit[i]] % DP1 != DIRECTIONS)
1410 x2 = nodes[circuit[i]] / DP1 % w;
1411 y2 = nodes[circuit[i]] / DP1 / w;
1412 dx = (x2 > x ? +1 : x2 < x ? -1 : 0);
1413 dy = (y2 > y ? +1 : y2 < y ? -1 : 0);
1414 for (d = 0; d < DIRECTIONS; d++)
1415 if (DX(d) == dx && DY(d) == dy) {
1419 assert(d < DIRECTIONS);
1424 assert(p - soln < circuitlen+2);
1445 static int game_can_format_as_text_now(const game_params *params)
1450 static char *game_text_format(const game_state *state)
1452 int w = state->p.w, h = state->p.h, r, c;
1453 int cw = 4, ch = 2, gw = cw*w + 2, gh = ch * h + 1, len = gw * gh;
1454 char *board = snewn(len + 1, char);
1456 sprintf(board, "%*s+\n", len - 2, "");
1458 for (r = 0; r < h; ++r) {
1459 for (c = 0; c < w; ++c) {
1460 int cell = r*ch*gw + cw*c, center = cell + gw*ch/2 + cw/2;
1462 switch (state->grid[i]) {
1464 case GEM: board[center] = 'o'; break;
1465 case MINE: board[center] = 'M'; break;
1466 case STOP: board[center-1] = '('; board[center+1] = ')'; break;
1467 case WALL: memset(board + center - 1, 'X', 3);
1470 if (r == state->py && c == state->px) {
1471 if (!state->dead) board[center] = '@';
1472 else memcpy(board + center - 1, ":-(", 3);
1475 memset(board + cell + 1, '-', cw - 1);
1476 for (i = 1; i < ch; ++i) board[cell + i*gw] = '|';
1478 for (c = 0; c < ch; ++c) {
1479 board[(r*ch+c)*gw + gw - 2] = "|+"[!c];
1480 board[(r*ch+c)*gw + gw - 1] = '\n';
1483 memset(board + len - gw, '-', gw - 2);
1484 for (c = 0; c < w; ++c) board[len - gw + cw*c] = '+';
1497 static game_ui *new_ui(const game_state *state)
1499 game_ui *ui = snew(game_ui);
1500 ui->anim_length = 0.0F;
1503 ui->just_made_move = FALSE;
1504 ui->just_died = FALSE;
1508 static void free_ui(game_ui *ui)
1513 static char *encode_ui(const game_ui *ui)
1517 * The deaths counter needs preserving across a serialisation.
1519 sprintf(buf, "D%d", ui->deaths);
1523 static void decode_ui(game_ui *ui, const char *encoding)
1526 sscanf(encoding, "D%d%n", &ui->deaths, &p);
1529 static void game_changed_state(game_ui *ui, const game_state *oldstate,
1530 const game_state *newstate)
1533 * Increment the deaths counter. We only do this if
1534 * ui->just_made_move is set (redoing a suicide move doesn't
1535 * kill you _again_), and also we only do it if the game wasn't
1536 * already completed (once you're finished, you can play).
1538 if (!oldstate->dead && newstate->dead && ui->just_made_move &&
1541 ui->just_died = TRUE;
1543 ui->just_died = FALSE;
1545 ui->just_made_move = FALSE;
1548 struct game_drawstate {
1552 unsigned short *grid;
1553 blitter *player_background;
1554 int player_bg_saved, pbgx, pbgy;
1557 #define PREFERRED_TILESIZE 32
1558 #define TILESIZE (ds->tilesize)
1560 #define BORDER (TILESIZE / 4)
1562 #define BORDER (TILESIZE)
1564 #define HIGHLIGHT_WIDTH (TILESIZE / 10)
1565 #define COORD(x) ( (x) * TILESIZE + BORDER )
1566 #define FROMCOORD(x) ( ((x) - BORDER + TILESIZE) / TILESIZE - 1 )
1568 static char *interpret_move(const game_state *state, game_ui *ui,
1569 const game_drawstate *ds,
1570 int x, int y, int button)
1572 int w = state->p.w, h = state->p.h /*, wh = w*h */;
1578 if (button == LEFT_BUTTON) {
1580 * Mouse-clicking near the target point (or, more
1581 * accurately, in the appropriate octant) is an alternative
1582 * way to input moves.
1585 if (FROMCOORD(x) != state->px || FROMCOORD(y) != state->py) {
1589 dx = FROMCOORD(x) - state->px;
1590 dy = FROMCOORD(y) - state->py;
1591 /* I pass dx,dy rather than dy,dx so that the octants
1592 * end up the right way round. */
1593 angle = atan2(dx, -dy);
1595 angle = (angle + (PI/8)) / (PI/4);
1596 assert(angle > -16.0F);
1597 dir = (int)(angle + 16.0F) & 7;
1599 } else if (button == CURSOR_UP || button == (MOD_NUM_KEYPAD | '8'))
1601 else if (button == CURSOR_DOWN || button == (MOD_NUM_KEYPAD | '2'))
1603 else if (button == CURSOR_LEFT || button == (MOD_NUM_KEYPAD | '4'))
1605 else if (button == CURSOR_RIGHT || button == (MOD_NUM_KEYPAD | '6'))
1607 else if (button == (MOD_NUM_KEYPAD | '7'))
1609 else if (button == (MOD_NUM_KEYPAD | '1'))
1611 else if (button == (MOD_NUM_KEYPAD | '9'))
1613 else if (button == (MOD_NUM_KEYPAD | '3'))
1615 else if (IS_CURSOR_SELECT(button) &&
1616 state->soln && state->solnpos < state->soln->len)
1617 dir = state->soln->list[state->solnpos];
1623 * Reject the move if we can't make it at all due to a wall
1626 if (AT(w, h, state->grid, state->px+DX(dir), state->py+DY(dir)) == WALL)
1630 * Reject the move if we're dead!
1636 * Otherwise, we can make the move. All we need to specify is
1639 ui->just_made_move = TRUE;
1640 sprintf(buf, "%d", dir);
1644 static void install_new_solution(game_state *ret, const char *move)
1648 assert (*move == 'S');
1652 sol->len = strlen(move);
1653 sol->list = snewn(sol->len, unsigned char);
1654 for (i = 0; i < sol->len; ++i) sol->list[i] = move[i] - '0';
1656 if (ret->soln && --ret->soln->refcount == 0) {
1657 sfree(ret->soln->list);
1664 ret->cheated = TRUE;
1668 static void discard_solution(game_state *ret)
1670 --ret->soln->refcount;
1671 assert(ret->soln->refcount > 0); /* ret has a soln-pointing dup */
1676 static game_state *execute_move(const game_state *state, const char *move)
1678 int w = state->p.w, h = state->p.h /*, wh = w*h */;
1684 * This is a solve move, so we don't actually _change_ the
1685 * grid but merely set up a stored solution path.
1687 ret = dup_game(state);
1688 install_new_solution(ret, move);
1693 if (dir < 0 || dir >= DIRECTIONS)
1694 return NULL; /* huh? */
1699 if (AT(w, h, state->grid, state->px+DX(dir), state->py+DY(dir)) == WALL)
1700 return NULL; /* wall in the way! */
1703 * Now make the move.
1705 ret = dup_game(state);
1706 ret->distance_moved = 0;
1710 ret->distance_moved++;
1712 if (AT(w, h, ret->grid, ret->px, ret->py) == GEM) {
1713 LV_AT(w, h, ret->grid, ret->px, ret->py) = BLANK;
1717 if (AT(w, h, ret->grid, ret->px, ret->py) == MINE) {
1722 if (AT(w, h, ret->grid, ret->px, ret->py) == STOP ||
1723 AT(w, h, ret->grid, ret->px+DX(dir),
1724 ret->py+DY(dir)) == WALL)
1729 if (ret->dead || ret->gems == 0)
1730 discard_solution(ret);
1731 else if (ret->soln->list[ret->solnpos] == dir) {
1733 assert(ret->solnpos < ret->soln->len); /* or gems == 0 */
1734 assert(!ret->dead); /* or not a solution */
1736 char *error = NULL, *soln = solve_game(NULL, ret, NULL, &error);
1738 install_new_solution(ret, soln);
1740 } else discard_solution(ret);
1747 /* ----------------------------------------------------------------------
1751 static void game_compute_size(const game_params *params, int tilesize,
1754 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
1755 struct { int tilesize; } ads, *ds = &ads;
1756 ads.tilesize = tilesize;
1758 *x = 2 * BORDER + 1 + params->w * TILESIZE;
1759 *y = 2 * BORDER + 1 + params->h * TILESIZE;
1762 static void game_set_size(drawing *dr, game_drawstate *ds,
1763 const game_params *params, int tilesize)
1765 ds->tilesize = tilesize;
1767 assert(!ds->player_background); /* set_size is never called twice */
1768 assert(!ds->player_bg_saved);
1770 ds->player_background = blitter_new(dr, TILESIZE, TILESIZE);
1773 static float *game_colours(frontend *fe, int *ncolours)
1775 float *ret = snewn(3 * NCOLOURS, float);
1778 game_mkhighlight(fe, ret, COL_BACKGROUND, COL_HIGHLIGHT, COL_LOWLIGHT);
1780 ret[COL_OUTLINE * 3 + 0] = 0.0F;
1781 ret[COL_OUTLINE * 3 + 1] = 0.0F;
1782 ret[COL_OUTLINE * 3 + 2] = 0.0F;
1784 ret[COL_PLAYER * 3 + 0] = 0.0F;
1785 ret[COL_PLAYER * 3 + 1] = 1.0F;
1786 ret[COL_PLAYER * 3 + 2] = 0.0F;
1788 ret[COL_DEAD_PLAYER * 3 + 0] = 1.0F;
1789 ret[COL_DEAD_PLAYER * 3 + 1] = 0.0F;
1790 ret[COL_DEAD_PLAYER * 3 + 2] = 0.0F;
1792 ret[COL_MINE * 3 + 0] = 0.0F;
1793 ret[COL_MINE * 3 + 1] = 0.0F;
1794 ret[COL_MINE * 3 + 2] = 0.0F;
1796 ret[COL_GEM * 3 + 0] = 0.6F;
1797 ret[COL_GEM * 3 + 1] = 1.0F;
1798 ret[COL_GEM * 3 + 2] = 1.0F;
1800 for (i = 0; i < 3; i++) {
1801 ret[COL_WALL * 3 + i] = (3 * ret[COL_BACKGROUND * 3 + i] +
1802 1 * ret[COL_HIGHLIGHT * 3 + i]) / 4;
1805 ret[COL_HINT * 3 + 0] = 1.0F;
1806 ret[COL_HINT * 3 + 1] = 1.0F;
1807 ret[COL_HINT * 3 + 2] = 0.0F;
1809 *ncolours = NCOLOURS;
1813 static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state)
1815 int w = state->p.w, h = state->p.h, wh = w*h;
1816 struct game_drawstate *ds = snew(struct game_drawstate);
1821 /* We can't allocate the blitter rectangle for the player background
1822 * until we know what size to make it. */
1823 ds->player_background = NULL;
1824 ds->player_bg_saved = FALSE;
1825 ds->pbgx = ds->pbgy = -1;
1827 ds->p = state->p; /* structure copy */
1828 ds->started = FALSE;
1829 ds->grid = snewn(wh, unsigned short);
1830 for (i = 0; i < wh; i++)
1831 ds->grid[i] = UNDRAWN;
1836 static void game_free_drawstate(drawing *dr, game_drawstate *ds)
1838 if (ds->player_background)
1839 blitter_free(dr, ds->player_background);
1844 static void draw_player(drawing *dr, game_drawstate *ds, int x, int y,
1845 int dead, int hintdir)
1848 int coords[DIRECTIONS*4];
1851 for (d = 0; d < DIRECTIONS; d++) {
1852 float x1, y1, x2, y2, x3, y3, len;
1856 len = sqrt(x1*x1+y1*y1); x1 /= len; y1 /= len;
1860 len = sqrt(x3*x3+y3*y3); x3 /= len; y3 /= len;
1865 coords[d*4+0] = x + TILESIZE/2 + (int)((TILESIZE*3/7) * x1);
1866 coords[d*4+1] = y + TILESIZE/2 + (int)((TILESIZE*3/7) * y1);
1867 coords[d*4+2] = x + TILESIZE/2 + (int)((TILESIZE*3/7) * x2);
1868 coords[d*4+3] = y + TILESIZE/2 + (int)((TILESIZE*3/7) * y2);
1870 draw_polygon(dr, coords, DIRECTIONS*2, COL_DEAD_PLAYER, COL_OUTLINE);
1872 draw_circle(dr, x + TILESIZE/2, y + TILESIZE/2,
1873 TILESIZE/3, COL_PLAYER, COL_OUTLINE);
1876 if (!dead && hintdir >= 0) {
1877 float scale = (DX(hintdir) && DY(hintdir) ? 0.8F : 1.0F);
1878 int ax = (TILESIZE*2/5) * scale * DX(hintdir);
1879 int ay = (TILESIZE*2/5) * scale * DY(hintdir);
1880 int px = -ay, py = ax;
1881 int ox = x + TILESIZE/2, oy = y + TILESIZE/2;
1887 *c++ = ox + px/9 + ax*2/3;
1888 *c++ = oy + py/9 + ay*2/3;
1889 *c++ = ox + px/3 + ax*2/3;
1890 *c++ = oy + py/3 + ay*2/3;
1893 *c++ = ox - px/3 + ax*2/3;
1894 *c++ = oy - py/3 + ay*2/3;
1895 *c++ = ox - px/9 + ax*2/3;
1896 *c++ = oy - py/9 + ay*2/3;
1899 draw_polygon(dr, coords, 7, COL_HINT, COL_OUTLINE);
1902 draw_update(dr, x, y, TILESIZE, TILESIZE);
1905 #define FLASH_DEAD 0x100
1906 #define FLASH_WIN 0x200
1907 #define FLASH_MASK 0x300
1909 static void draw_tile(drawing *dr, game_drawstate *ds, int x, int y, int v)
1911 int tx = COORD(x), ty = COORD(y);
1912 int bg = (v & FLASH_DEAD ? COL_DEAD_PLAYER :
1913 v & FLASH_WIN ? COL_HIGHLIGHT : COL_BACKGROUND);
1917 clip(dr, tx+1, ty+1, TILESIZE-1, TILESIZE-1);
1918 draw_rect(dr, tx+1, ty+1, TILESIZE-1, TILESIZE-1, bg);
1923 coords[0] = tx + TILESIZE;
1924 coords[1] = ty + TILESIZE;
1925 coords[2] = tx + TILESIZE;
1928 coords[5] = ty + TILESIZE;
1929 draw_polygon(dr, coords, 3, COL_LOWLIGHT, COL_LOWLIGHT);
1933 draw_polygon(dr, coords, 3, COL_HIGHLIGHT, COL_HIGHLIGHT);
1935 draw_rect(dr, tx + 1 + HIGHLIGHT_WIDTH, ty + 1 + HIGHLIGHT_WIDTH,
1936 TILESIZE - 2*HIGHLIGHT_WIDTH,
1937 TILESIZE - 2*HIGHLIGHT_WIDTH, COL_WALL);
1938 } else if (v == MINE) {
1939 int cx = tx + TILESIZE / 2;
1940 int cy = ty + TILESIZE / 2;
1941 int r = TILESIZE / 2 - 3;
1943 draw_circle(dr, cx, cy, 5*r/6, COL_MINE, COL_MINE);
1944 draw_rect(dr, cx - r/6, cy - r, 2*(r/6)+1, 2*r+1, COL_MINE);
1945 draw_rect(dr, cx - r, cy - r/6, 2*r+1, 2*(r/6)+1, COL_MINE);
1946 draw_rect(dr, cx-r/3, cy-r/3, r/3, r/4, COL_HIGHLIGHT);
1947 } else if (v == STOP) {
1948 draw_circle(dr, tx + TILESIZE/2, ty + TILESIZE/2,
1949 TILESIZE*3/7, -1, COL_OUTLINE);
1950 draw_rect(dr, tx + TILESIZE*3/7, ty+1,
1951 TILESIZE - 2*(TILESIZE*3/7) + 1, TILESIZE-1, bg);
1952 draw_rect(dr, tx+1, ty + TILESIZE*3/7,
1953 TILESIZE-1, TILESIZE - 2*(TILESIZE*3/7) + 1, bg);
1954 } else if (v == GEM) {
1957 coords[0] = tx+TILESIZE/2;
1958 coords[1] = ty+TILESIZE/2-TILESIZE*5/14;
1959 coords[2] = tx+TILESIZE/2-TILESIZE*5/14;
1960 coords[3] = ty+TILESIZE/2;
1961 coords[4] = tx+TILESIZE/2;
1962 coords[5] = ty+TILESIZE/2+TILESIZE*5/14;
1963 coords[6] = tx+TILESIZE/2+TILESIZE*5/14;
1964 coords[7] = ty+TILESIZE/2;
1966 draw_polygon(dr, coords, 4, COL_GEM, COL_OUTLINE);
1970 draw_update(dr, tx, ty, TILESIZE, TILESIZE);
1973 #define BASE_ANIM_LENGTH 0.1F
1974 #define FLASH_LENGTH 0.3F
1976 static void game_redraw(drawing *dr, game_drawstate *ds,
1977 const game_state *oldstate, const game_state *state,
1978 int dir, const game_ui *ui,
1979 float animtime, float flashtime)
1981 int w = state->p.w, h = state->p.h /*, wh = w*h */;
1990 !((int)(flashtime * 3 / FLASH_LENGTH) % 2))
1991 flashtype = ui->flashtype;
1996 * Erase the player sprite.
1998 if (ds->player_bg_saved) {
1999 assert(ds->player_background);
2000 blitter_load(dr, ds->player_background, ds->pbgx, ds->pbgy);
2001 draw_update(dr, ds->pbgx, ds->pbgy, TILESIZE, TILESIZE);
2002 ds->player_bg_saved = FALSE;
2006 * Initialise a fresh drawstate.
2012 * Blank out the window initially.
2014 game_compute_size(&ds->p, TILESIZE, &wid, &ht);
2015 draw_rect(dr, 0, 0, wid, ht, COL_BACKGROUND);
2016 draw_update(dr, 0, 0, wid, ht);
2019 * Draw the grid lines.
2021 for (y = 0; y <= h; y++)
2022 draw_line(dr, COORD(0), COORD(y), COORD(w), COORD(y),
2024 for (x = 0; x <= w; x++)
2025 draw_line(dr, COORD(x), COORD(0), COORD(x), COORD(h),
2032 * If we're in the process of animating a move, let's start by
2033 * working out how far the player has moved from their _older_
2037 ap = animtime / ui->anim_length;
2038 player_dist = ap * (dir > 0 ? state : oldstate)->distance_moved;
2045 * Draw the grid contents.
2047 * We count the gems as we go round this loop, for the purposes
2048 * of the status bar. Of course we have a gems counter in the
2049 * game_state already, but if we do the counting in this loop
2050 * then it tracks gems being picked up in a sliding move, and
2051 * updates one by one.
2054 for (y = 0; y < h; y++)
2055 for (x = 0; x < w; x++) {
2056 unsigned short v = (unsigned char)state->grid[y*w+x];
2059 * Special case: if the player is in the process of
2060 * moving over a gem, we draw the gem iff they haven't
2063 if (oldstate && oldstate->grid[y*w+x] != state->grid[y*w+x]) {
2065 * Compute the distance from this square to the
2066 * original player position.
2068 int dist = max(abs(x - oldstate->px), abs(y - oldstate->py));
2071 * If the player has reached here, use the new grid
2072 * element. Otherwise use the old one.
2074 if (player_dist < dist)
2075 v = oldstate->grid[y*w+x];
2077 v = state->grid[y*w+x];
2081 * Special case: erase the mine the dead player is
2082 * sitting on. Only at the end of the move.
2084 if (v == MINE && !oldstate && state->dead &&
2085 x == state->px && y == state->py)
2093 if (ds->grid[y*w+x] != v) {
2094 draw_tile(dr, ds, x, y, v);
2095 ds->grid[y*w+x] = v;
2100 * Gem counter in the status bar. We replace it with
2101 * `COMPLETED!' when it reaches zero ... or rather, when the
2102 * _current state_'s gem counter is zero. (Thus, `Gems: 0' is
2103 * shown between the collection of the last gem and the
2104 * completion of the move animation that did it.)
2106 if (state->dead && (!oldstate || oldstate->dead)) {
2107 sprintf(status, "DEAD!");
2108 } else if (state->gems || (oldstate && oldstate->gems)) {
2110 sprintf(status, "Auto-solver used. ");
2113 sprintf(status + strlen(status), "Gems: %d", gems);
2114 } else if (state->cheated) {
2115 sprintf(status, "Auto-solved.");
2117 sprintf(status, "COMPLETED!");
2119 /* We subtract one from the visible death counter if we're still
2120 * animating the move at the end of which the death took place. */
2121 deaths = ui->deaths;
2122 if (oldstate && ui->just_died) {
2127 sprintf(status + strlen(status), " Deaths: %d", deaths);
2128 status_bar(dr, status);
2131 * Draw the player sprite.
2133 assert(!ds->player_bg_saved);
2134 assert(ds->player_background);
2137 nx = COORD(state->px);
2138 ny = COORD(state->py);
2140 ox = COORD(oldstate->px);
2141 oy = COORD(oldstate->py);
2146 ds->pbgx = ox + ap * (nx - ox);
2147 ds->pbgy = oy + ap * (ny - oy);
2149 blitter_save(dr, ds->player_background, ds->pbgx, ds->pbgy);
2150 draw_player(dr, ds, ds->pbgx, ds->pbgy,
2151 (state->dead && !oldstate),
2152 (!oldstate && state->soln ?
2153 state->soln->list[state->solnpos] : -1));
2154 ds->player_bg_saved = TRUE;
2157 static float game_anim_length(const game_state *oldstate,
2158 const game_state *newstate, int dir, game_ui *ui)
2162 dist = newstate->distance_moved;
2164 dist = oldstate->distance_moved;
2165 ui->anim_length = sqrt(dist) * BASE_ANIM_LENGTH;
2166 return ui->anim_length;
2169 static float game_flash_length(const game_state *oldstate,
2170 const game_state *newstate, int dir, game_ui *ui)
2172 if (!oldstate->dead && newstate->dead) {
2173 ui->flashtype = FLASH_DEAD;
2174 return FLASH_LENGTH;
2175 } else if (oldstate->gems && !newstate->gems) {
2176 ui->flashtype = FLASH_WIN;
2177 return FLASH_LENGTH;
2182 static int game_status(const game_state *state)
2185 * We never report the game as lost, on the grounds that if the
2186 * player has died they're quite likely to want to undo and carry
2189 return state->gems == 0 ? +1 : 0;
2192 static int game_timing_state(const game_state *state, game_ui *ui)
2197 static void game_print_size(const game_params *params, float *x, float *y)
2201 static void game_print(drawing *dr, const game_state *state, int tilesize)
2206 #define thegame inertia
2209 const struct game thegame = {
2210 "Inertia", "games.inertia", "inertia",
2212 game_fetch_preset, NULL,
2217 TRUE, game_configure, custom_params,
2225 TRUE, game_can_format_as_text_now, game_text_format,
2233 PREFERRED_TILESIZE, game_compute_size, game_set_size,
2236 game_free_drawstate,
2241 FALSE, FALSE, game_print_size, game_print,
2242 TRUE, /* wants_statusbar */
2243 FALSE, game_timing_state,