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(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(game_params *params, int full)
156 sprintf(data, "%dx%d", params->w, params->h);
161 static config_item *game_configure(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].sval = dupstr(buf);
174 ret[1].name = "Height";
175 ret[1].type = C_STRING;
176 sprintf(buf, "%d", params->h);
177 ret[1].sval = dupstr(buf);
188 static game_params *custom_params(config_item *cfg)
190 game_params *ret = snew(game_params);
192 ret->w = atoi(cfg[0].sval);
193 ret->h = atoi(cfg[1].sval);
198 static char *validate_params(game_params *params, int full)
201 * Avoid completely degenerate cases which only have one
202 * row/column. We probably could generate completable puzzles
203 * of that shape, but they'd be forced to be extremely boring
204 * and at large sizes would take a while to happen upon at
207 if (params->w < 2 || params->h < 2)
208 return "Width and height must both be at least two";
211 * The grid construction algorithm creates 1/5 as many gems as
212 * grid squares, and must create at least one gem to have an
213 * actual puzzle. However, an area-five grid is ruled out by
214 * the above constraint, so the practical minimum is six.
216 if (params->w * params->h < 6)
217 return "Grid area must be at least six squares";
222 /* ----------------------------------------------------------------------
223 * Solver used by grid generator.
226 struct solver_scratch {
227 unsigned char *reachable_from, *reachable_to;
231 static struct solver_scratch *new_scratch(int w, int h)
233 struct solver_scratch *sc = snew(struct solver_scratch);
235 sc->reachable_from = snewn(w * h * DIRECTIONS, unsigned char);
236 sc->reachable_to = snewn(w * h * DIRECTIONS, unsigned char);
237 sc->positions = snewn(w * h * DIRECTIONS, int);
242 static void free_scratch(struct solver_scratch *sc)
244 sfree(sc->reachable_from);
245 sfree(sc->reachable_to);
246 sfree(sc->positions);
250 static int can_go(int w, int h, char *grid,
251 int x1, int y1, int dir1, int x2, int y2, int dir2)
254 * Returns TRUE if we can transition directly from (x1,y1)
255 * going in direction dir1, to (x2,y2) going in direction dir2.
259 * If we're actually in the middle of an unoccupyable square,
260 * we cannot make any move.
262 if (AT(w, h, grid, x1, y1) == WALL ||
263 AT(w, h, grid, x1, y1) == MINE)
267 * If a move is capable of stopping at x1,y1,dir1, and x2,y2 is
268 * the same coordinate as x1,y1, then we can make the
269 * transition (by stopping and changing direction).
271 * For this to be the case, we have to either have a wall
272 * beyond x1,y1,dir1, or have a stop on x1,y1.
274 if (x2 == x1 && y2 == y1 &&
275 (AT(w, h, grid, x1, y1) == STOP ||
276 AT(w, h, grid, x1, y1) == START ||
277 AT(w, h, grid, x1+DX(dir1), y1+DY(dir1)) == WALL))
281 * If a move is capable of continuing here, then x1,y1,dir1 can
282 * move one space further on.
284 if (x2 == x1+DX(dir1) && y2 == y1+DY(dir1) && dir1 == dir2 &&
285 (AT(w, h, grid, x2, y2) == BLANK ||
286 AT(w, h, grid, x2, y2) == GEM ||
287 AT(w, h, grid, x2, y2) == STOP ||
288 AT(w, h, grid, x2, y2) == START))
297 static int find_gem_candidates(int w, int h, char *grid,
298 struct solver_scratch *sc)
302 int sx, sy, gx, gy, gd, pass, possgems;
305 * This function finds all the candidate gem squares, which are
306 * precisely those squares which can be picked up on a loop
307 * from the starting point back to the starting point. Doing
308 * this may involve passing through such a square in the middle
309 * of a move; so simple breadth-first search over the _squares_
310 * of the grid isn't quite adequate, because it might be that
311 * we can only reach a gem from the start by moving over it in
312 * one direction, but can only return to the start if we were
313 * moving over it in another direction.
315 * Instead, we BFS over a space which mentions each grid square
316 * eight times - once for each direction. We also BFS twice:
317 * once to find out what square+direction pairs we can reach
318 * _from_ the start point, and once to find out what pairs we
319 * can reach the start point from. Then a square is reachable
320 * if any of the eight directions for that square has both
324 memset(sc->reachable_from, 0, wh * DIRECTIONS);
325 memset(sc->reachable_to, 0, wh * DIRECTIONS);
328 * Find the starting square.
330 sx = -1; /* placate optimiser */
331 for (sy = 0; sy < h; sy++) {
332 for (sx = 0; sx < w; sx++)
333 if (AT(w, h, grid, sx, sy) == START)
340 for (pass = 0; pass < 2; pass++) {
341 unsigned char *reachable = (pass == 0 ? sc->reachable_from :
343 int sign = (pass == 0 ? +1 : -1);
346 #ifdef SOLVER_DIAGNOSTICS
347 printf("starting pass %d\n", pass);
351 * `head' and `tail' are indices within sc->positions which
352 * track the list of board positions left to process.
355 for (dir = 0; dir < DIRECTIONS; dir++) {
356 int index = (sy*w+sx)*DIRECTIONS+dir;
357 sc->positions[tail++] = index;
358 reachable[index] = TRUE;
359 #ifdef SOLVER_DIAGNOSTICS
360 printf("starting point %d,%d,%d\n", sx, sy, dir);
365 * Now repeatedly pick an element off the list and process
368 while (head < tail) {
369 int index = sc->positions[head++];
370 int dir = index % DIRECTIONS;
371 int x = (index / DIRECTIONS) % w;
372 int y = index / (w * DIRECTIONS);
373 int n, x2, y2, d2, i2;
375 #ifdef SOLVER_DIAGNOSTICS
376 printf("processing point %d,%d,%d\n", x, y, dir);
379 * The places we attempt to switch to here are:
380 * - each possible direction change (all the other
381 * directions in this square)
382 * - one step further in the direction we're going (or
383 * one step back, if we're in the reachable_to pass).
385 for (n = -1; n < DIRECTIONS; n++) {
387 x2 = x + sign * DX(dir);
388 y2 = y + sign * DY(dir);
395 i2 = (y2*w+x2)*DIRECTIONS+d2;
396 if (x2 >= 0 && x2 < w &&
400 #ifdef SOLVER_DIAGNOSTICS
401 printf(" trying point %d,%d,%d", x2, y2, d2);
404 ok = can_go(w, h, grid, x, y, dir, x2, y2, d2);
406 ok = can_go(w, h, grid, x2, y2, d2, x, y, dir);
407 #ifdef SOLVER_DIAGNOSTICS
408 printf(" - %sok\n", ok ? "" : "not ");
411 sc->positions[tail++] = i2;
412 reachable[i2] = TRUE;
420 * And that should be it. Now all we have to do is find the
421 * squares for which there exists _some_ direction such that
422 * the square plus that direction form a tuple which is both
423 * reachable from the start and reachable to the start.
426 for (gy = 0; gy < h; gy++)
427 for (gx = 0; gx < w; gx++)
428 if (AT(w, h, grid, gx, gy) == BLANK) {
429 for (gd = 0; gd < DIRECTIONS; gd++) {
430 int index = (gy*w+gx)*DIRECTIONS+gd;
431 if (sc->reachable_from[index] && sc->reachable_to[index]) {
432 #ifdef SOLVER_DIAGNOSTICS
433 printf("space at %d,%d is reachable via"
434 " direction %d\n", gx, gy, gd);
436 LV_AT(w, h, grid, gx, gy) = POSSGEM;
446 /* ----------------------------------------------------------------------
447 * Grid generation code.
450 static char *gengrid(int w, int h, random_state *rs)
453 char *grid = snewn(wh+1, char);
454 struct solver_scratch *sc = new_scratch(w, h);
455 int maxdist_threshold, tries;
457 maxdist_threshold = 2;
463 int *dist, *list, head, tail, maxdist;
466 * We're going to fill the grid with the five basic piece
467 * types in about 1/5 proportion. For the moment, though,
468 * we leave out the gems, because we'll put those in
469 * _after_ we run the solver to tell us where the viable
473 for (j = 0; j < wh/5; j++)
475 for (j = 0; j < wh/5; j++)
477 for (j = 0; j < wh/5; j++)
483 shuffle(grid, wh, sizeof(*grid), rs);
486 * Find the viable gem locations, and immediately give up
487 * and try again if there aren't enough of them.
489 possgems = find_gem_candidates(w, h, grid, sc);
494 * We _could_ now select wh/5 of the POSSGEMs and set them
495 * to GEM, and have a viable level. However, there's a
496 * chance that a large chunk of the level will turn out to
497 * be unreachable, so first we test for that.
499 * We do this by finding the largest distance from any
500 * square to the nearest POSSGEM, by breadth-first search.
501 * If this is above a critical threshold, we abort and try
504 * (This search is purely geometric, without regard to
505 * walls and long ways round.)
507 dist = sc->positions;
508 list = sc->positions + wh;
509 for (i = 0; i < wh; i++)
512 for (i = 0; i < wh; i++)
513 if (grid[i] == POSSGEM) {
518 while (head < tail) {
522 if (maxdist < dist[pos])
528 for (d = 0; d < DIRECTIONS; d++) {
534 if (x2 >= 0 && x2 < w && y2 >= 0 && y2 < h) {
537 dist[p2] = dist[pos] + 1;
543 assert(head == wh && tail == wh);
546 * Now abandon this grid and go round again if maxdist is
547 * above the required threshold.
549 * We can safely start the threshold as low as 2. As we
550 * accumulate failed generation attempts, we gradually
551 * raise it as we get more desperate.
553 if (maxdist > maxdist_threshold) {
563 * Now our reachable squares are plausibly evenly
564 * distributed over the grid. I'm not actually going to
565 * _enforce_ that I place the gems in such a way as not to
566 * increase that maxdist value; I'm now just going to trust
567 * to the RNG to pick a sensible subset of the POSSGEMs.
570 for (i = 0; i < wh; i++)
571 if (grid[i] == POSSGEM)
573 shuffle(list, j, sizeof(*list), rs);
574 for (i = 0; i < j; i++)
575 grid[list[i]] = (i < wh/5 ? GEM : BLANK);
586 static char *new_game_desc(game_params *params, random_state *rs,
587 char **aux, int interactive)
589 return gengrid(params->w, params->h, rs);
592 static char *validate_desc(game_params *params, char *desc)
594 int w = params->w, h = params->h, wh = w*h;
595 int starts = 0, gems = 0, i;
597 for (i = 0; i < wh; i++) {
599 return "Not enough data to fill grid";
600 if (desc[i] != WALL && desc[i] != START && desc[i] != STOP &&
601 desc[i] != GEM && desc[i] != MINE && desc[i] != BLANK)
602 return "Unrecognised character in game description";
603 if (desc[i] == START)
609 return "Too much data to fill grid";
611 return "No starting square specified";
613 return "More than one starting square specified";
615 return "No gems specified";
620 static game_state *new_game(midend *me, game_params *params, char *desc)
622 int w = params->w, h = params->h, wh = w*h;
624 game_state *state = snew(game_state);
626 state->p = *params; /* structure copy */
628 state->grid = snewn(wh, char);
629 assert(strlen(desc) == wh);
630 memcpy(state->grid, desc, wh);
632 state->px = state->py = -1;
634 for (i = 0; i < wh; i++) {
635 if (state->grid[i] == START) {
636 state->grid[i] = STOP;
639 } else if (state->grid[i] == GEM) {
644 assert(state->gems > 0);
645 assert(state->px >= 0 && state->py >= 0);
647 state->distance_moved = 0;
650 state->cheated = FALSE;
657 static game_state *dup_game(game_state *state)
659 int w = state->p.w, h = state->p.h, wh = w*h;
660 game_state *ret = snew(game_state);
665 ret->gems = state->gems;
666 ret->grid = snewn(wh, char);
667 ret->distance_moved = state->distance_moved;
669 memcpy(ret->grid, state->grid, wh);
670 ret->cheated = state->cheated;
671 ret->soln = state->soln;
673 ret->soln->refcount++;
674 ret->solnpos = state->solnpos;
679 static void free_game(game_state *state)
681 if (state->soln && --state->soln->refcount == 0) {
682 sfree(state->soln->list);
690 * Internal function used by solver.
692 static int move_goes_to(int w, int h, char *grid, int x, int y, int d)
697 * See where we'd get to if we made this move.
699 dr = -1; /* placate optimiser */
701 if (AT(w, h, grid, x+DX(d), y+DY(d)) == WALL) {
702 dr = DIRECTIONS; /* hit a wall, so end up stationary */
707 if (AT(w, h, grid, x, y) == STOP) {
708 dr = DIRECTIONS; /* hit a stop, so end up stationary */
711 if (AT(w, h, grid, x, y) == GEM) {
712 dr = d; /* hit a gem, so we're still moving */
715 if (AT(w, h, grid, x, y) == MINE)
716 return -1; /* hit a mine, so move is invalid */
719 return (y*w+x)*DP1+dr;
722 static int compare_integers(const void *av, const void *bv)
724 const int *a = (const int *)av;
725 const int *b = (const int *)bv;
734 static char *solve_game(game_state *state, game_state *currstate,
735 char *aux, char **error)
737 int w = state->p.w, h = state->p.h, wh = w*h;
738 int *nodes, *nodeindex, *edges, *backedges, *edgei, *backedgei, *circuit;
740 int *dist, *dist2, *list;
742 int circuitlen, circuitsize;
743 int head, tail, pass, i, j, n, x, y, d, dd;
744 char *err, *soln, *p;
747 * Before anything else, deal with the special case in which
748 * all the gems are already collected.
750 for (i = 0; i < wh; i++)
751 if (currstate->grid[i] == GEM)
754 *error = "Game is already solved";
759 * Solving Inertia is a question of first building up the graph
760 * of where you can get to from where, and secondly finding a
761 * tour of the graph which takes in every gem.
763 * This is of course a close cousin of the travelling salesman
764 * problem, which is NP-complete; so I rather doubt that any
765 * _optimal_ tour can be found in plausible time. Hence I'll
766 * restrict myself to merely finding a not-too-bad one.
768 * First construct the graph, by bfsing out move by move from
769 * the current player position. Graph vertices will be
770 * - every endpoint of a move (place the ball can be
772 * - every gem (place the ball can go through in motion).
773 * Vertices of this type have an associated direction, since
774 * if a gem can be collected by sliding through it in two
775 * different directions it doesn't follow that you can
776 * change direction at it.
778 * I'm going to refer to a non-directional vertex as
779 * (y*w+x)*DP1+DIRECTIONS, and a directional one as
784 * nodeindex[] maps node codes as shown above to numeric
785 * indices in the nodes[] array.
787 nodeindex = snewn(DP1*wh, int);
788 for (i = 0; i < DP1*wh; i++)
792 * Do the bfs to find all the interesting graph nodes.
794 nodes = snewn(DP1*wh, int);
797 nodes[tail] = (currstate->py * w + currstate->px) * DP1 + DIRECTIONS;
798 nodeindex[nodes[0]] = tail;
801 while (head < tail) {
802 int nc = nodes[head++], nnc;
807 * Plot all possible moves from this node. If the node is
808 * directed, there's only one.
810 for (dd = 0; dd < DIRECTIONS; dd++) {
815 if (d < DIRECTIONS && d != dd)
818 nnc = move_goes_to(w, h, currstate->grid, x, y, dd);
819 if (nnc >= 0 && nnc != nc) {
820 if (nodeindex[nnc] < 0) {
822 nodeindex[nnc] = tail;
831 * Now we know how many nodes we have, allocate the edge array
832 * and go through setting up the edges.
834 edges = snewn(DIRECTIONS*n, int);
835 edgei = snewn(n+1, int);
838 for (i = 0; i < n; i++) {
848 for (dd = 0; dd < DIRECTIONS; dd++) {
851 if (d >= DIRECTIONS || d == dd) {
852 nnc = move_goes_to(w, h, currstate->grid, x, y, dd);
854 if (nnc >= 0 && nnc != nc)
855 edges[nedges++] = nodeindex[nnc];
862 * Now set up the backedges array.
864 backedges = snewn(nedges, int);
865 backedgei = snewn(n+1, int);
866 for (i = j = 0; i < nedges; i++) {
867 while (j+1 < n && i >= edgei[j+1])
869 backedges[i] = edges[i] * n + j;
871 qsort(backedges, nedges, sizeof(int), compare_integers);
873 for (i = j = 0; i < nedges; i++) {
874 int k = backedges[i] / n;
879 backedgei[n] = nedges;
882 * Set up the initial tour. At all times, our tour is a circuit
883 * of graph vertices (which may, and probably will often,
884 * repeat vertices). To begin with, it's got exactly one vertex
885 * in it, which is the player's current starting point.
888 circuit = snewn(circuitsize, int);
890 circuit[circuitlen++] = 0; /* node index 0 is the starting posn */
893 * Track which gems are as yet unvisited.
895 unvisited = snewn(wh, int);
896 for (i = 0; i < wh; i++)
897 unvisited[i] = FALSE;
898 for (i = 0; i < wh; i++)
899 if (currstate->grid[i] == GEM)
903 * Allocate space for doing bfses inside the main loop.
905 dist = snewn(n, int);
906 dist2 = snewn(n, int);
907 list = snewn(n, int);
913 * Now enter the main loop, in each iteration of which we
914 * extend the tour to take in an as yet uncollected gem.
917 int target, n1, n2, bestdist, extralen, targetpos;
919 #ifdef TSP_DIAGNOSTICS
920 printf("circuit is");
921 for (i = 0; i < circuitlen; i++) {
922 int nc = nodes[circuit[i]];
923 printf(" (%d,%d,%d)", nc/DP1%w, nc/(DP1*w), nc%DP1);
926 printf("moves are ");
927 x = nodes[circuit[0]] / DP1 % w;
928 y = nodes[circuit[0]] / DP1 / w;
929 for (i = 1; i < circuitlen; i++) {
931 if (nodes[circuit[i]] % DP1 != DIRECTIONS)
933 x2 = nodes[circuit[i]] / DP1 % w;
934 y2 = nodes[circuit[i]] / DP1 / w;
935 dx = (x2 > x ? +1 : x2 < x ? -1 : 0);
936 dy = (y2 > y ? +1 : y2 < y ? -1 : 0);
937 for (d = 0; d < DIRECTIONS; d++)
938 if (DX(d) == dx && DY(d) == dy)
939 printf("%c", "89632147"[d]);
947 * First, start a pair of bfses at _every_ vertex currently
948 * in the tour, and extend them outwards to find the
949 * nearest as yet unreached gem vertex.
951 * This is largely a heuristic: we could pick _any_ doubly
952 * reachable node here and still get a valid tour as
953 * output. I hope that picking a nearby one will result in
954 * generally good tours.
956 for (pass = 0; pass < 2; pass++) {
957 int *ep = (pass == 0 ? edges : backedges);
958 int *ei = (pass == 0 ? edgei : backedgei);
959 int *dp = (pass == 0 ? dist : dist2);
961 for (i = 0; i < n; i++)
963 for (i = 0; i < circuitlen; i++) {
970 while (head < tail) {
971 int ni = list[head++];
972 for (i = ei[ni]; i < ei[ni+1]; i++) {
974 if (ti >= 0 && dp[ti] < 0) {
981 /* Now find the nearest unvisited gem. */
984 for (i = 0; i < n; i++) {
985 if (unvisited[nodes[i] / DP1] &&
986 dist[i] >= 0 && dist2[i] >= 0) {
987 int thisdist = dist[i] + dist2[i];
988 if (bestdist < 0 || bestdist > thisdist) {
997 * If we get to here, we haven't found a gem we can get
998 * at all, which means we terminate this loop.
1004 * Now we have a graph vertex at list[tail-1] which is an
1005 * unvisited gem. We want to add that vertex to our tour.
1006 * So we run two more breadth-first searches: one starting
1007 * from that vertex and following forward edges, and
1008 * another starting from the same vertex and following
1009 * backward edges. This allows us to determine, for each
1010 * node on the current tour, how quickly we can get both to
1011 * and from the target vertex from that node.
1013 #ifdef TSP_DIAGNOSTICS
1014 printf("target node is %d (%d,%d,%d)\n", target, nodes[target]/DP1%w,
1015 nodes[target]/DP1/w, nodes[target]%DP1);
1018 for (pass = 0; pass < 2; pass++) {
1019 int *ep = (pass == 0 ? edges : backedges);
1020 int *ei = (pass == 0 ? edgei : backedgei);
1021 int *dp = (pass == 0 ? dist : dist2);
1023 for (i = 0; i < n; i++)
1028 list[tail++] = target;
1030 while (head < tail) {
1031 int ni = list[head++];
1032 for (i = ei[ni]; i < ei[ni+1]; i++) {
1034 if (ti >= 0 && dp[ti] < 0) {
1035 dp[ti] = dp[ni] + 1;
1036 /*printf("pass %d: set dist of vertex %d to %d (via %d)\n", pass, ti, dp[ti], ni);*/
1044 * Now for every node n, dist[n] gives the length of the
1045 * shortest path from the target vertex to n, and dist2[n]
1046 * gives the length of the shortest path from n to the
1049 * Our next step is to search linearly along the tour to
1050 * find the optimum place to insert a trip to the target
1051 * vertex and back. Our two options are either
1052 * (a) to find two adjacent vertices A,B in the tour and
1053 * replace the edge A->B with the path A->target->B
1054 * (b) to find a single vertex X in the tour and replace
1055 * it with the complete round trip X->target->X.
1056 * We do whichever takes the fewest moves.
1060 for (i = 0; i < circuitlen; i++) {
1064 * Try a round trip from vertex i.
1066 if (dist[circuit[i]] >= 0 &&
1067 dist2[circuit[i]] >= 0) {
1068 thisdist = dist[circuit[i]] + dist2[circuit[i]];
1069 if (bestdist < 0 || thisdist < bestdist) {
1070 bestdist = thisdist;
1076 * Try a trip from vertex i via target to vertex i+1.
1078 if (i+1 < circuitlen &&
1079 dist2[circuit[i]] >= 0 &&
1080 dist[circuit[i+1]] >= 0) {
1081 thisdist = dist2[circuit[i]] + dist[circuit[i+1]];
1082 if (bestdist < 0 || thisdist < bestdist) {
1083 bestdist = thisdist;
1091 * We couldn't find a round trip taking in this gem _at
1094 err = "Unable to find a solution from this starting point";
1097 #ifdef TSP_DIAGNOSTICS
1098 printf("insertion point: n1=%d, n2=%d, dist=%d\n", n1, n2, bestdist);
1101 #ifdef TSP_DIAGNOSTICS
1102 printf("circuit before lengthening is");
1103 for (i = 0; i < circuitlen; i++) {
1104 printf(" %d", circuit[i]);
1110 * Now actually lengthen the tour to take in this round
1113 extralen = dist2[circuit[n1]] + dist[circuit[n2]];
1116 circuitlen += extralen;
1117 if (circuitlen >= circuitsize) {
1118 circuitsize = circuitlen + 256;
1119 circuit = sresize(circuit, circuitsize, int);
1121 memmove(circuit + n2 + extralen, circuit + n2,
1122 (circuitlen - n2 - extralen) * sizeof(int));
1125 #ifdef TSP_DIAGNOSTICS
1126 printf("circuit in middle of lengthening is");
1127 for (i = 0; i < circuitlen; i++) {
1128 printf(" %d", circuit[i]);
1134 * Find the shortest-path routes to and from the target,
1135 * and write them into the circuit.
1137 targetpos = n1 + dist2[circuit[n1]];
1138 assert(targetpos - dist2[circuit[n1]] == n1);
1139 assert(targetpos + dist[circuit[n2]] == n2);
1140 for (pass = 0; pass < 2; pass++) {
1141 int dir = (pass == 0 ? -1 : +1);
1142 int *ep = (pass == 0 ? backedges : edges);
1143 int *ei = (pass == 0 ? backedgei : edgei);
1144 int *dp = (pass == 0 ? dist : dist2);
1145 int nn = (pass == 0 ? n2 : n1);
1146 int ni = circuit[nn], ti, dest = nn;
1154 /*printf("pass %d: looking at vertex %d\n", pass, ni);*/
1155 for (i = ei[ni]; i < ei[ni+1]; i++) {
1157 if (ti >= 0 && dp[ti] == dp[ni] - 1)
1160 assert(i < ei[ni+1] && ti >= 0);
1165 #ifdef TSP_DIAGNOSTICS
1166 printf("circuit after lengthening is");
1167 for (i = 0; i < circuitlen; i++) {
1168 printf(" %d", circuit[i]);
1174 * Finally, mark all gems that the new piece of circuit
1175 * passes through as visited.
1177 for (i = n1; i <= n2; i++) {
1178 int pos = nodes[circuit[i]] / DP1;
1179 assert(pos >= 0 && pos < wh);
1180 unvisited[pos] = FALSE;
1184 #ifdef TSP_DIAGNOSTICS
1185 printf("before reduction, moves are ");
1186 x = nodes[circuit[0]] / DP1 % w;
1187 y = nodes[circuit[0]] / DP1 / w;
1188 for (i = 1; i < circuitlen; i++) {
1190 if (nodes[circuit[i]] % DP1 != DIRECTIONS)
1192 x2 = nodes[circuit[i]] / DP1 % w;
1193 y2 = nodes[circuit[i]] / DP1 / w;
1194 dx = (x2 > x ? +1 : x2 < x ? -1 : 0);
1195 dy = (y2 > y ? +1 : y2 < y ? -1 : 0);
1196 for (d = 0; d < DIRECTIONS; d++)
1197 if (DX(d) == dx && DY(d) == dy)
1198 printf("%c", "89632147"[d]);
1206 * That's got a basic solution. Now optimise it by removing
1207 * redundant sections of the circuit: it's entirely possible
1208 * that a piece of circuit we carefully inserted at one stage
1209 * to collect a gem has become pointless because the steps
1210 * required to collect some _later_ gem necessarily passed
1211 * through the same one.
1213 * So first we go through and work out how many times each gem
1214 * is collected. Then we look for maximal sections of circuit
1215 * which are redundant in the sense that their removal would
1216 * not reduce any gem's collection count to zero, and replace
1217 * each one with a bfs-derived fastest path between their
1221 int oldlen = circuitlen;
1224 for (dir = +1; dir >= -1; dir -= 2) {
1226 for (i = 0; i < wh; i++)
1228 for (i = 0; i < circuitlen; i++) {
1229 int xy = nodes[circuit[i]] / DP1;
1230 if (currstate->grid[xy] == GEM)
1235 * If there's any gem we didn't end up visiting at all,
1238 for (i = 0; i < wh; i++) {
1239 if (currstate->grid[i] == GEM && unvisited[i] == 0) {
1240 err = "Unable to find a solution from this starting point";
1247 for (i = j = (dir > 0 ? 0 : circuitlen-1);
1248 i < circuitlen && i >= 0;
1250 int xy = nodes[circuit[i]] / DP1;
1251 if (currstate->grid[xy] == GEM && unvisited[xy] > 1) {
1253 } else if (currstate->grid[xy] == GEM || i == circuitlen-1) {
1255 * circuit[i] collects a gem for the only time,
1256 * or is the last node in the circuit.
1257 * Therefore it cannot be removed; so we now
1258 * want to replace the path from circuit[j] to
1259 * circuit[i] with a bfs-shortest path.
1261 int p, q, k, dest, ni, ti, thisdist;
1264 * Set up the upper and lower bounds of the
1270 #ifdef TSP_DIAGNOSTICS
1271 printf("optimising section from %d - %d\n", p, q);
1274 for (k = 0; k < n; k++)
1278 dist[circuit[p]] = 0;
1279 list[tail++] = circuit[p];
1281 while (head < tail && dist[circuit[q]] < 0) {
1282 int ni = list[head++];
1283 for (k = edgei[ni]; k < edgei[ni+1]; k++) {
1285 if (ti >= 0 && dist[ti] < 0) {
1286 dist[ti] = dist[ni] + 1;
1292 thisdist = dist[circuit[q]];
1293 assert(thisdist >= 0 && thisdist <= q-p);
1295 memmove(circuit+p+thisdist, circuit+q,
1296 (circuitlen - q) * sizeof(int));
1302 i = q; /* resume loop from the right place */
1304 #ifdef TSP_DIAGNOSTICS
1305 printf("new section runs from %d - %d\n", p, q);
1313 /* printf("dest=%d circuitlen=%d ni=%d dist[ni]=%d\n", dest, circuitlen, ni, dist[ni]); */
1319 for (k = backedgei[ni]; k < backedgei[ni+1]; k++) {
1321 if (ti >= 0 && dist[ti] == dist[ni] - 1)
1324 assert(k < backedgei[ni+1] && ti >= 0);
1329 * Now re-increment the visit counts for the
1333 int xy = nodes[circuit[p]] / DP1;
1334 if (currstate->grid[xy] == GEM)
1340 #ifdef TSP_DIAGNOSTICS
1341 printf("during reduction, circuit is");
1342 for (k = 0; k < circuitlen; k++) {
1343 int nc = nodes[circuit[k]];
1344 printf(" (%d,%d,%d)", nc/DP1%w, nc/(DP1*w), nc%DP1);
1347 printf("moves are ");
1348 x = nodes[circuit[0]] / DP1 % w;
1349 y = nodes[circuit[0]] / DP1 / w;
1350 for (k = 1; k < circuitlen; k++) {
1352 if (nodes[circuit[k]] % DP1 != DIRECTIONS)
1354 x2 = nodes[circuit[k]] / DP1 % w;
1355 y2 = nodes[circuit[k]] / DP1 / w;
1356 dx = (x2 > x ? +1 : x2 < x ? -1 : 0);
1357 dy = (y2 > y ? +1 : y2 < y ? -1 : 0);
1358 for (d = 0; d < DIRECTIONS; d++)
1359 if (DX(d) == dx && DY(d) == dy)
1360 printf("%c", "89632147"[d]);
1369 #ifdef TSP_DIAGNOSTICS
1370 printf("after reduction, moves are ");
1371 x = nodes[circuit[0]] / DP1 % w;
1372 y = nodes[circuit[0]] / DP1 / w;
1373 for (i = 1; i < circuitlen; i++) {
1375 if (nodes[circuit[i]] % DP1 != DIRECTIONS)
1377 x2 = nodes[circuit[i]] / DP1 % w;
1378 y2 = nodes[circuit[i]] / DP1 / w;
1379 dx = (x2 > x ? +1 : x2 < x ? -1 : 0);
1380 dy = (y2 > y ? +1 : y2 < y ? -1 : 0);
1381 for (d = 0; d < DIRECTIONS; d++)
1382 if (DX(d) == dx && DY(d) == dy)
1383 printf("%c", "89632147"[d]);
1392 * If we've managed an entire reduction pass in each
1393 * direction and not made the solution any shorter, we're
1396 if (circuitlen == oldlen)
1401 * Encode the solution as a move string.
1404 soln = snewn(circuitlen+2, char);
1407 x = nodes[circuit[0]] / DP1 % w;
1408 y = nodes[circuit[0]] / DP1 / w;
1409 for (i = 1; i < circuitlen; i++) {
1411 if (nodes[circuit[i]] % DP1 != DIRECTIONS)
1413 x2 = nodes[circuit[i]] / DP1 % w;
1414 y2 = nodes[circuit[i]] / DP1 / w;
1415 dx = (x2 > x ? +1 : x2 < x ? -1 : 0);
1416 dy = (y2 > y ? +1 : y2 < y ? -1 : 0);
1417 for (d = 0; d < DIRECTIONS; d++)
1418 if (DX(d) == dx && DY(d) == dy) {
1422 assert(d < DIRECTIONS);
1427 assert(p - soln < circuitlen+2);
1448 static char *game_text_format(game_state *state)
1461 static game_ui *new_ui(game_state *state)
1463 game_ui *ui = snew(game_ui);
1464 ui->anim_length = 0.0F;
1467 ui->just_made_move = FALSE;
1468 ui->just_died = FALSE;
1472 static void free_ui(game_ui *ui)
1477 static char *encode_ui(game_ui *ui)
1481 * The deaths counter needs preserving across a serialisation.
1483 sprintf(buf, "D%d", ui->deaths);
1487 static void decode_ui(game_ui *ui, char *encoding)
1490 sscanf(encoding, "D%d%n", &ui->deaths, &p);
1493 static void game_changed_state(game_ui *ui, game_state *oldstate,
1494 game_state *newstate)
1497 * Increment the deaths counter. We only do this if
1498 * ui->just_made_move is set (redoing a suicide move doesn't
1499 * kill you _again_), and also we only do it if the game wasn't
1500 * already completed (once you're finished, you can play).
1502 if (!oldstate->dead && newstate->dead && ui->just_made_move &&
1505 ui->just_died = TRUE;
1507 ui->just_died = FALSE;
1509 ui->just_made_move = FALSE;
1512 struct game_drawstate {
1516 unsigned short *grid;
1517 blitter *player_background;
1518 int player_bg_saved, pbgx, pbgy;
1521 #define PREFERRED_TILESIZE 32
1522 #define TILESIZE (ds->tilesize)
1524 #define BORDER (TILESIZE / 4)
1526 #define BORDER (TILESIZE)
1528 #define HIGHLIGHT_WIDTH (TILESIZE / 10)
1529 #define COORD(x) ( (x) * TILESIZE + BORDER )
1530 #define FROMCOORD(x) ( ((x) - BORDER + TILESIZE) / TILESIZE - 1 )
1532 static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds,
1533 int x, int y, int button)
1535 int w = state->p.w, h = state->p.h /*, wh = w*h */;
1541 if (button == LEFT_BUTTON) {
1543 * Mouse-clicking near the target point (or, more
1544 * accurately, in the appropriate octant) is an alternative
1545 * way to input moves.
1548 if (FROMCOORD(x) != state->px || FROMCOORD(y) != state->py) {
1552 dx = FROMCOORD(x) - state->px;
1553 dy = FROMCOORD(y) - state->py;
1554 /* I pass dx,dy rather than dy,dx so that the octants
1555 * end up the right way round. */
1556 angle = atan2(dx, -dy);
1558 angle = (angle + (PI/8)) / (PI/4);
1559 assert(angle > -16.0F);
1560 dir = (int)(angle + 16.0F) & 7;
1562 } else if (button == CURSOR_UP || button == (MOD_NUM_KEYPAD | '8'))
1564 else if (button == CURSOR_DOWN || button == (MOD_NUM_KEYPAD | '2'))
1566 else if (button == CURSOR_LEFT || button == (MOD_NUM_KEYPAD | '4'))
1568 else if (button == CURSOR_RIGHT || button == (MOD_NUM_KEYPAD | '6'))
1570 else if (button == (MOD_NUM_KEYPAD | '7'))
1572 else if (button == (MOD_NUM_KEYPAD | '1'))
1574 else if (button == (MOD_NUM_KEYPAD | '9'))
1576 else if (button == (MOD_NUM_KEYPAD | '3'))
1578 else if (button == ' ' && state->soln && state->solnpos < state->soln->len)
1579 dir = state->soln->list[state->solnpos];
1585 * Reject the move if we can't make it at all due to a wall
1588 if (AT(w, h, state->grid, state->px+DX(dir), state->py+DY(dir)) == WALL)
1592 * Reject the move if we're dead!
1598 * Otherwise, we can make the move. All we need to specify is
1601 ui->just_made_move = TRUE;
1602 sprintf(buf, "%d", dir);
1606 static game_state *execute_move(game_state *state, char *move)
1608 int w = state->p.w, h = state->p.h /*, wh = w*h */;
1617 * This is a solve move, so we don't actually _change_ the
1618 * grid but merely set up a stored solution path.
1624 sol->list = snewn(len, unsigned char);
1625 for (i = 0; i < len; i++)
1626 sol->list[i] = move[i] - '0';
1627 ret = dup_game(state);
1628 ret->cheated = TRUE;
1636 if (dir < 0 || dir >= DIRECTIONS)
1637 return NULL; /* huh? */
1642 if (AT(w, h, state->grid, state->px+DX(dir), state->py+DY(dir)) == WALL)
1643 return NULL; /* wall in the way! */
1646 * Now make the move.
1648 ret = dup_game(state);
1649 ret->distance_moved = 0;
1653 ret->distance_moved++;
1655 if (AT(w, h, ret->grid, ret->px, ret->py) == GEM) {
1656 LV_AT(w, h, ret->grid, ret->px, ret->py) = BLANK;
1660 if (AT(w, h, ret->grid, ret->px, ret->py) == MINE) {
1665 if (AT(w, h, ret->grid, ret->px, ret->py) == STOP ||
1666 AT(w, h, ret->grid, ret->px+DX(dir),
1667 ret->py+DY(dir)) == WALL)
1673 * If this move is the correct next one in the stored
1674 * solution path, advance solnpos.
1676 if (ret->soln->list[ret->solnpos] == dir &&
1677 ret->solnpos+1 < ret->soln->len) {
1681 * Otherwise, the user has strayed from the path, so
1682 * the path is no longer valid.
1684 ret->soln->refcount--;
1685 assert(ret->soln->refcount > 0);/* `state' at least still exists */
1694 /* ----------------------------------------------------------------------
1698 static void game_compute_size(game_params *params, int tilesize,
1701 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
1702 struct { int tilesize; } ads, *ds = &ads;
1703 ads.tilesize = tilesize;
1705 *x = 2 * BORDER + 1 + params->w * TILESIZE;
1706 *y = 2 * BORDER + 1 + params->h * TILESIZE;
1709 static void game_set_size(drawing *dr, game_drawstate *ds,
1710 game_params *params, int tilesize)
1712 ds->tilesize = tilesize;
1714 assert(!ds->player_background); /* set_size is never called twice */
1715 assert(!ds->player_bg_saved);
1717 ds->player_background = blitter_new(dr, TILESIZE, TILESIZE);
1720 static float *game_colours(frontend *fe, int *ncolours)
1722 float *ret = snewn(3 * NCOLOURS, float);
1725 game_mkhighlight(fe, ret, COL_BACKGROUND, COL_HIGHLIGHT, COL_LOWLIGHT);
1727 ret[COL_OUTLINE * 3 + 0] = 0.0F;
1728 ret[COL_OUTLINE * 3 + 1] = 0.0F;
1729 ret[COL_OUTLINE * 3 + 2] = 0.0F;
1731 ret[COL_PLAYER * 3 + 0] = 0.0F;
1732 ret[COL_PLAYER * 3 + 1] = 1.0F;
1733 ret[COL_PLAYER * 3 + 2] = 0.0F;
1735 ret[COL_DEAD_PLAYER * 3 + 0] = 1.0F;
1736 ret[COL_DEAD_PLAYER * 3 + 1] = 0.0F;
1737 ret[COL_DEAD_PLAYER * 3 + 2] = 0.0F;
1739 ret[COL_MINE * 3 + 0] = 0.0F;
1740 ret[COL_MINE * 3 + 1] = 0.0F;
1741 ret[COL_MINE * 3 + 2] = 0.0F;
1743 ret[COL_GEM * 3 + 0] = 0.6F;
1744 ret[COL_GEM * 3 + 1] = 1.0F;
1745 ret[COL_GEM * 3 + 2] = 1.0F;
1747 for (i = 0; i < 3; i++) {
1748 ret[COL_WALL * 3 + i] = (3 * ret[COL_BACKGROUND * 3 + i] +
1749 1 * ret[COL_HIGHLIGHT * 3 + i]) / 4;
1752 ret[COL_HINT * 3 + 0] = 1.0F;
1753 ret[COL_HINT * 3 + 1] = 1.0F;
1754 ret[COL_HINT * 3 + 2] = 0.0F;
1756 *ncolours = NCOLOURS;
1760 static game_drawstate *game_new_drawstate(drawing *dr, game_state *state)
1762 int w = state->p.w, h = state->p.h, wh = w*h;
1763 struct game_drawstate *ds = snew(struct game_drawstate);
1768 /* We can't allocate the blitter rectangle for the player background
1769 * until we know what size to make it. */
1770 ds->player_background = NULL;
1771 ds->player_bg_saved = FALSE;
1772 ds->pbgx = ds->pbgy = -1;
1774 ds->p = state->p; /* structure copy */
1775 ds->started = FALSE;
1776 ds->grid = snewn(wh, unsigned short);
1777 for (i = 0; i < wh; i++)
1778 ds->grid[i] = UNDRAWN;
1783 static void game_free_drawstate(drawing *dr, game_drawstate *ds)
1785 if (ds->player_background)
1786 blitter_free(dr, ds->player_background);
1791 static void draw_player(drawing *dr, game_drawstate *ds, int x, int y,
1792 int dead, int hintdir)
1795 int coords[DIRECTIONS*4];
1798 for (d = 0; d < DIRECTIONS; d++) {
1799 float x1, y1, x2, y2, x3, y3, len;
1803 len = sqrt(x1*x1+y1*y1); x1 /= len; y1 /= len;
1807 len = sqrt(x3*x3+y3*y3); x3 /= len; y3 /= len;
1812 coords[d*4+0] = x + TILESIZE/2 + (int)((TILESIZE*3/7) * x1);
1813 coords[d*4+1] = y + TILESIZE/2 + (int)((TILESIZE*3/7) * y1);
1814 coords[d*4+2] = x + TILESIZE/2 + (int)((TILESIZE*3/7) * x2);
1815 coords[d*4+3] = y + TILESIZE/2 + (int)((TILESIZE*3/7) * y2);
1817 draw_polygon(dr, coords, DIRECTIONS*2, COL_DEAD_PLAYER, COL_OUTLINE);
1819 draw_circle(dr, x + TILESIZE/2, y + TILESIZE/2,
1820 TILESIZE/3, COL_PLAYER, COL_OUTLINE);
1823 if (!dead && hintdir >= 0) {
1824 float scale = (DX(hintdir) && DY(hintdir) ? 0.8F : 1.0F);
1825 int ax = (TILESIZE*2/5) * scale * DX(hintdir);
1826 int ay = (TILESIZE*2/5) * scale * DY(hintdir);
1827 int px = -ay, py = ax;
1828 int ox = x + TILESIZE/2, oy = y + TILESIZE/2;
1834 *c++ = ox + px/9 + ax*2/3;
1835 *c++ = oy + py/9 + ay*2/3;
1836 *c++ = ox + px/3 + ax*2/3;
1837 *c++ = oy + py/3 + ay*2/3;
1840 *c++ = ox - px/3 + ax*2/3;
1841 *c++ = oy - py/3 + ay*2/3;
1842 *c++ = ox - px/9 + ax*2/3;
1843 *c++ = oy - py/9 + ay*2/3;
1846 draw_polygon(dr, coords, 7, COL_HINT, COL_OUTLINE);
1849 draw_update(dr, x, y, TILESIZE, TILESIZE);
1852 #define FLASH_DEAD 0x100
1853 #define FLASH_WIN 0x200
1854 #define FLASH_MASK 0x300
1856 static void draw_tile(drawing *dr, game_drawstate *ds, int x, int y, int v)
1858 int tx = COORD(x), ty = COORD(y);
1859 int bg = (v & FLASH_DEAD ? COL_DEAD_PLAYER :
1860 v & FLASH_WIN ? COL_HIGHLIGHT : COL_BACKGROUND);
1864 clip(dr, tx+1, ty+1, TILESIZE-1, TILESIZE-1);
1865 draw_rect(dr, tx+1, ty+1, TILESIZE-1, TILESIZE-1, bg);
1870 coords[0] = tx + TILESIZE;
1871 coords[1] = ty + TILESIZE;
1872 coords[2] = tx + TILESIZE;
1875 coords[5] = ty + TILESIZE;
1876 draw_polygon(dr, coords, 3, COL_LOWLIGHT, COL_LOWLIGHT);
1880 draw_polygon(dr, coords, 3, COL_HIGHLIGHT, COL_HIGHLIGHT);
1882 draw_rect(dr, tx + 1 + HIGHLIGHT_WIDTH, ty + 1 + HIGHLIGHT_WIDTH,
1883 TILESIZE - 2*HIGHLIGHT_WIDTH,
1884 TILESIZE - 2*HIGHLIGHT_WIDTH, COL_WALL);
1885 } else if (v == MINE) {
1886 int cx = tx + TILESIZE / 2;
1887 int cy = ty + TILESIZE / 2;
1888 int r = TILESIZE / 2 - 3;
1890 int xdx = 1, xdy = 0, ydx = 0, ydy = 1;
1893 for (i = 0; i < 4*5*2; i += 5*2) {
1894 coords[i+2*0+0] = cx - r/6*xdx + r*4/5*ydx;
1895 coords[i+2*0+1] = cy - r/6*xdy + r*4/5*ydy;
1896 coords[i+2*1+0] = cx - r/6*xdx + r*ydx;
1897 coords[i+2*1+1] = cy - r/6*xdy + r*ydy;
1898 coords[i+2*2+0] = cx + r/6*xdx + r*ydx;
1899 coords[i+2*2+1] = cy + r/6*xdy + r*ydy;
1900 coords[i+2*3+0] = cx + r/6*xdx + r*4/5*ydx;
1901 coords[i+2*3+1] = cy + r/6*xdy + r*4/5*ydy;
1902 coords[i+2*4+0] = cx + r*3/5*xdx + r*3/5*ydx;
1903 coords[i+2*4+1] = cy + r*3/5*xdy + r*3/5*ydy;
1913 draw_polygon(dr, coords, 5*4, COL_MINE, COL_MINE);
1915 draw_rect(dr, cx-r/3, cy-r/3, r/3, r/4, COL_HIGHLIGHT);
1916 } else if (v == STOP) {
1917 draw_circle(dr, tx + TILESIZE/2, ty + TILESIZE/2,
1918 TILESIZE*3/7, -1, COL_OUTLINE);
1919 draw_rect(dr, tx + TILESIZE*3/7, ty+1,
1920 TILESIZE - 2*(TILESIZE*3/7) + 1, TILESIZE-1, bg);
1921 draw_rect(dr, tx+1, ty + TILESIZE*3/7,
1922 TILESIZE-1, TILESIZE - 2*(TILESIZE*3/7) + 1, bg);
1923 } else if (v == GEM) {
1926 coords[0] = tx+TILESIZE/2;
1927 coords[1] = ty+TILESIZE/2-TILESIZE*5/14;
1928 coords[2] = tx+TILESIZE/2-TILESIZE*5/14;
1929 coords[3] = ty+TILESIZE/2;
1930 coords[4] = tx+TILESIZE/2;
1931 coords[5] = ty+TILESIZE/2+TILESIZE*5/14;
1932 coords[6] = tx+TILESIZE/2+TILESIZE*5/14;
1933 coords[7] = ty+TILESIZE/2;
1935 draw_polygon(dr, coords, 4, COL_GEM, COL_OUTLINE);
1939 draw_update(dr, tx, ty, TILESIZE, TILESIZE);
1942 #define BASE_ANIM_LENGTH 0.1F
1943 #define FLASH_LENGTH 0.3F
1945 static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate,
1946 game_state *state, int dir, game_ui *ui,
1947 float animtime, float flashtime)
1949 int w = state->p.w, h = state->p.h /*, wh = w*h */;
1958 !((int)(flashtime * 3 / FLASH_LENGTH) % 2))
1959 flashtype = ui->flashtype;
1964 * Erase the player sprite.
1966 if (ds->player_bg_saved) {
1967 assert(ds->player_background);
1968 blitter_load(dr, ds->player_background, ds->pbgx, ds->pbgy);
1969 draw_update(dr, ds->pbgx, ds->pbgy, TILESIZE, TILESIZE);
1970 ds->player_bg_saved = FALSE;
1974 * Initialise a fresh drawstate.
1980 * Blank out the window initially.
1982 game_compute_size(&ds->p, TILESIZE, &wid, &ht);
1983 draw_rect(dr, 0, 0, wid, ht, COL_BACKGROUND);
1984 draw_update(dr, 0, 0, wid, ht);
1987 * Draw the grid lines.
1989 for (y = 0; y <= h; y++)
1990 draw_line(dr, COORD(0), COORD(y), COORD(w), COORD(y),
1992 for (x = 0; x <= w; x++)
1993 draw_line(dr, COORD(x), COORD(0), COORD(x), COORD(h),
2000 * If we're in the process of animating a move, let's start by
2001 * working out how far the player has moved from their _older_
2005 ap = animtime / ui->anim_length;
2006 player_dist = ap * (dir > 0 ? state : oldstate)->distance_moved;
2013 * Draw the grid contents.
2015 * We count the gems as we go round this loop, for the purposes
2016 * of the status bar. Of course we have a gems counter in the
2017 * game_state already, but if we do the counting in this loop
2018 * then it tracks gems being picked up in a sliding move, and
2019 * updates one by one.
2022 for (y = 0; y < h; y++)
2023 for (x = 0; x < w; x++) {
2024 unsigned short v = (unsigned char)state->grid[y*w+x];
2027 * Special case: if the player is in the process of
2028 * moving over a gem, we draw the gem iff they haven't
2031 if (oldstate && oldstate->grid[y*w+x] != state->grid[y*w+x]) {
2033 * Compute the distance from this square to the
2034 * original player position.
2036 int dist = max(abs(x - oldstate->px), abs(y - oldstate->py));
2039 * If the player has reached here, use the new grid
2040 * element. Otherwise use the old one.
2042 if (player_dist < dist)
2043 v = oldstate->grid[y*w+x];
2045 v = state->grid[y*w+x];
2049 * Special case: erase the mine the dead player is
2050 * sitting on. Only at the end of the move.
2052 if (v == MINE && !oldstate && state->dead &&
2053 x == state->px && y == state->py)
2061 if (ds->grid[y*w+x] != v) {
2062 draw_tile(dr, ds, x, y, v);
2063 ds->grid[y*w+x] = v;
2068 * Gem counter in the status bar. We replace it with
2069 * `COMPLETED!' when it reaches zero ... or rather, when the
2070 * _current state_'s gem counter is zero. (Thus, `Gems: 0' is
2071 * shown between the collection of the last gem and the
2072 * completion of the move animation that did it.)
2074 if (state->dead && (!oldstate || oldstate->dead)) {
2075 sprintf(status, "DEAD!");
2076 } else if (state->gems || (oldstate && oldstate->gems)) {
2078 sprintf(status, "Auto-solver used. ");
2081 sprintf(status + strlen(status), "Gems: %d", gems);
2082 } else if (state->cheated) {
2083 sprintf(status, "Auto-solved.");
2085 sprintf(status, "COMPLETED!");
2087 /* We subtract one from the visible death counter if we're still
2088 * animating the move at the end of which the death took place. */
2089 deaths = ui->deaths;
2090 if (oldstate && ui->just_died) {
2095 sprintf(status + strlen(status), " Deaths: %d", deaths);
2096 status_bar(dr, status);
2099 * Draw the player sprite.
2101 assert(!ds->player_bg_saved);
2102 assert(ds->player_background);
2105 nx = COORD(state->px);
2106 ny = COORD(state->py);
2108 ox = COORD(oldstate->px);
2109 oy = COORD(oldstate->py);
2114 ds->pbgx = ox + ap * (nx - ox);
2115 ds->pbgy = oy + ap * (ny - oy);
2117 blitter_save(dr, ds->player_background, ds->pbgx, ds->pbgy);
2118 draw_player(dr, ds, ds->pbgx, ds->pbgy,
2119 (state->dead && !oldstate),
2120 (!oldstate && state->soln ?
2121 state->soln->list[state->solnpos] : -1));
2122 ds->player_bg_saved = TRUE;
2125 static float game_anim_length(game_state *oldstate, game_state *newstate,
2126 int dir, game_ui *ui)
2130 dist = newstate->distance_moved;
2132 dist = oldstate->distance_moved;
2133 ui->anim_length = sqrt(dist) * BASE_ANIM_LENGTH;
2134 return ui->anim_length;
2137 static float game_flash_length(game_state *oldstate, game_state *newstate,
2138 int dir, game_ui *ui)
2140 if (!oldstate->dead && newstate->dead) {
2141 ui->flashtype = FLASH_DEAD;
2142 return FLASH_LENGTH;
2143 } else if (oldstate->gems && !newstate->gems) {
2144 ui->flashtype = FLASH_WIN;
2145 return FLASH_LENGTH;
2150 static int game_timing_state(game_state *state, game_ui *ui)
2155 static void game_print_size(game_params *params, float *x, float *y)
2159 static void game_print(drawing *dr, game_state *state, int tilesize)
2164 #define thegame inertia
2167 const struct game thegame = {
2168 "Inertia", "games.inertia", "inertia",
2175 TRUE, game_configure, custom_params,
2183 FALSE, game_text_format,
2191 PREFERRED_TILESIZE, game_compute_size, game_set_size,
2194 game_free_drawstate,
2198 FALSE, FALSE, game_print_size, game_print,
2199 TRUE, /* wants_statusbar */
2200 FALSE, game_timing_state,