X-Git-Url: http://www.chiark.greenend.org.uk/ucgi/~ian/git?a=blobdiff_plain;f=inertia.c;h=4cbdd5299b823359b48b6bad5d16c8eed1b0d92f;hb=3ce69e84cad15844282d691fa03e711c5353c05e;hp=95bdcc8890c8bf2f6bf94f699a551bf78671c0ea;hpb=04e26aaa7b04af90d8d42e77d3d9ccc1dade678c;p=sgt-puzzles.git diff --git a/inertia.c b/inertia.c index 95bdcc8..4cbdd52 100644 --- a/inertia.c +++ b/inertia.c @@ -32,6 +32,7 @@ #define UNDRAWN '?' #define DIRECTIONS 8 +#define DP1 (DIRECTIONS+1) #define DX(dir) ( (dir) & 3 ? (((dir) & 7) > 4 ? -1 : +1) : 0 ) #define DY(dir) ( DX((dir)+6) ) @@ -56,6 +57,7 @@ enum { COL_MINE, COL_GEM, COL_WALL, + COL_HINT, NCOLOURS }; @@ -63,6 +65,12 @@ struct game_params { int w, h; }; +typedef struct soln { + int refcount; + int len; + unsigned char *list; +} soln; + struct game_state { game_params p; int px, py; @@ -70,6 +78,9 @@ struct game_state { char *grid; int distance_moved; int dead; + int cheated; + int solnpos; + soln *soln; }; static game_params *default_params(void) @@ -77,8 +88,11 @@ static game_params *default_params(void) game_params *ret = snew(game_params); ret->w = 10; +#ifdef PORTRAIT_SCREEN + ret->h = 10; +#else ret->h = 8; - +#endif return ret; } @@ -87,7 +101,7 @@ static void free_params(game_params *params) sfree(params); } -static game_params *dup_params(game_params *params) +static game_params *dup_params(const game_params *params) { game_params *ret = snew(game_params); *ret = *params; /* structure copy */ @@ -95,9 +109,15 @@ static game_params *dup_params(game_params *params) } static const struct game_params inertia_presets[] = { +#ifdef PORTRAIT_SCREEN + { 10, 10 }, + { 12, 12 }, + { 16, 16 }, +#else { 10, 8 }, { 15, 12 }, { 20, 16 }, +#endif }; static int game_fetch_preset(int i, char **name, game_params **params) @@ -129,7 +149,7 @@ static void decode_params(game_params *params, char const *string) } } -static char *encode_params(game_params *params, int full) +static char *encode_params(const game_params *params, int full) { char data[256]; @@ -138,7 +158,7 @@ static char *encode_params(game_params *params, int full) return dupstr(data); } -static config_item *game_configure(game_params *params) +static config_item *game_configure(const game_params *params) { config_item *ret; char buf[80]; @@ -165,7 +185,7 @@ static config_item *game_configure(game_params *params) return ret; } -static game_params *custom_params(config_item *cfg) +static game_params *custom_params(const config_item *cfg) { game_params *ret = snew(game_params); @@ -175,7 +195,7 @@ static game_params *custom_params(config_item *cfg) return ret; } -static char *validate_params(game_params *params, int full) +static char *validate_params(const game_params *params, int full) { /* * Avoid completely degenerate cases which only have one @@ -563,13 +583,13 @@ static char *gengrid(int w, int h, random_state *rs) return grid; } -static char *new_game_desc(game_params *params, random_state *rs, +static char *new_game_desc(const game_params *params, random_state *rs, char **aux, int interactive) { return gengrid(params->w, params->h, rs); } -static char *validate_desc(game_params *params, char *desc) +static char *validate_desc(const game_params *params, const char *desc) { int w = params->w, h = params->h, wh = w*h; int starts = 0, gems = 0, i; @@ -597,7 +617,8 @@ static char *validate_desc(game_params *params, char *desc) return NULL; } -static game_state *new_game(midend *me, game_params *params, char *desc) +static game_state *new_game(midend *me, const game_params *params, + const char *desc) { int w = params->w, h = params->h, wh = w*h; int i; @@ -627,10 +648,14 @@ static game_state *new_game(midend *me, game_params *params, char *desc) state->distance_moved = 0; state->dead = FALSE; + state->cheated = FALSE; + state->solnpos = 0; + state->soln = NULL; + return state; } -static game_state *dup_game(game_state *state) +static game_state *dup_game(const game_state *state) { int w = state->p.w, h = state->p.h, wh = w*h; game_state *ret = snew(game_state); @@ -643,25 +668,826 @@ static game_state *dup_game(game_state *state) ret->distance_moved = state->distance_moved; ret->dead = FALSE; memcpy(ret->grid, state->grid, wh); + ret->cheated = state->cheated; + ret->soln = state->soln; + if (ret->soln) + ret->soln->refcount++; + ret->solnpos = state->solnpos; return ret; } static void free_game(game_state *state) { + if (state->soln && --state->soln->refcount == 0) { + sfree(state->soln->list); + sfree(state->soln); + } sfree(state->grid); sfree(state); } -static char *solve_game(game_state *state, game_state *currstate, - char *aux, char **error) +/* + * Internal function used by solver. + */ +static int move_goes_to(int w, int h, char *grid, int x, int y, int d) { - return NULL; + int dr; + + /* + * See where we'd get to if we made this move. + */ + dr = -1; /* placate optimiser */ + while (1) { + if (AT(w, h, grid, x+DX(d), y+DY(d)) == WALL) { + dr = DIRECTIONS; /* hit a wall, so end up stationary */ + break; + } + x += DX(d); + y += DY(d); + if (AT(w, h, grid, x, y) == STOP) { + dr = DIRECTIONS; /* hit a stop, so end up stationary */ + break; + } + if (AT(w, h, grid, x, y) == GEM) { + dr = d; /* hit a gem, so we're still moving */ + break; + } + if (AT(w, h, grid, x, y) == MINE) + return -1; /* hit a mine, so move is invalid */ + } + assert(dr >= 0); + return (y*w+x)*DP1+dr; } -static char *game_text_format(game_state *state) +static int compare_integers(const void *av, const void *bv) { - return NULL; + const int *a = (const int *)av; + const int *b = (const int *)bv; + if (*a < *b) + return -1; + else if (*a > *b) + return +1; + else + return 0; +} + +static char *solve_game(const game_state *state, const game_state *currstate, + const char *aux, char **error) +{ + int w = currstate->p.w, h = currstate->p.h, wh = w*h; + int *nodes, *nodeindex, *edges, *backedges, *edgei, *backedgei, *circuit; + int nedges; + int *dist, *dist2, *list; + int *unvisited; + int circuitlen, circuitsize; + int head, tail, pass, i, j, n, x, y, d, dd; + char *err, *soln, *p; + + /* + * Before anything else, deal with the special case in which + * all the gems are already collected. + */ + for (i = 0; i < wh; i++) + if (currstate->grid[i] == GEM) + break; + if (i == wh) { + *error = "Game is already solved"; + return NULL; + } + + /* + * Solving Inertia is a question of first building up the graph + * of where you can get to from where, and secondly finding a + * tour of the graph which takes in every gem. + * + * This is of course a close cousin of the travelling salesman + * problem, which is NP-complete; so I rather doubt that any + * _optimal_ tour can be found in plausible time. Hence I'll + * restrict myself to merely finding a not-too-bad one. + * + * First construct the graph, by bfsing out move by move from + * the current player position. Graph vertices will be + * - every endpoint of a move (place the ball can be + * stationary) + * - every gem (place the ball can go through in motion). + * Vertices of this type have an associated direction, since + * if a gem can be collected by sliding through it in two + * different directions it doesn't follow that you can + * change direction at it. + * + * I'm going to refer to a non-directional vertex as + * (y*w+x)*DP1+DIRECTIONS, and a directional one as + * (y*w+x)*DP1+d. + */ + + /* + * nodeindex[] maps node codes as shown above to numeric + * indices in the nodes[] array. + */ + nodeindex = snewn(DP1*wh, int); + for (i = 0; i < DP1*wh; i++) + nodeindex[i] = -1; + + /* + * Do the bfs to find all the interesting graph nodes. + */ + nodes = snewn(DP1*wh, int); + head = tail = 0; + + nodes[tail] = (currstate->py * w + currstate->px) * DP1 + DIRECTIONS; + nodeindex[nodes[0]] = tail; + tail++; + + while (head < tail) { + int nc = nodes[head++], nnc; + + d = nc % DP1; + + /* + * Plot all possible moves from this node. If the node is + * directed, there's only one. + */ + for (dd = 0; dd < DIRECTIONS; dd++) { + x = nc / DP1; + y = x / w; + x %= w; + + if (d < DIRECTIONS && d != dd) + continue; + + nnc = move_goes_to(w, h, currstate->grid, x, y, dd); + if (nnc >= 0 && nnc != nc) { + if (nodeindex[nnc] < 0) { + nodes[tail] = nnc; + nodeindex[nnc] = tail; + tail++; + } + } + } + } + n = head; + + /* + * Now we know how many nodes we have, allocate the edge array + * and go through setting up the edges. + */ + edges = snewn(DIRECTIONS*n, int); + edgei = snewn(n+1, int); + nedges = 0; + + for (i = 0; i < n; i++) { + int nc = nodes[i]; + + edgei[i] = nedges; + + d = nc % DP1; + x = nc / DP1; + y = x / w; + x %= w; + + for (dd = 0; dd < DIRECTIONS; dd++) { + int nnc; + + if (d >= DIRECTIONS || d == dd) { + nnc = move_goes_to(w, h, currstate->grid, x, y, dd); + + if (nnc >= 0 && nnc != nc) + edges[nedges++] = nodeindex[nnc]; + } + } + } + edgei[n] = nedges; + + /* + * Now set up the backedges array. + */ + backedges = snewn(nedges, int); + backedgei = snewn(n+1, int); + for (i = j = 0; i < nedges; i++) { + while (j+1 < n && i >= edgei[j+1]) + j++; + backedges[i] = edges[i] * n + j; + } + qsort(backedges, nedges, sizeof(int), compare_integers); + backedgei[0] = 0; + for (i = j = 0; i < nedges; i++) { + int k = backedges[i] / n; + backedges[i] %= n; + while (j < k) + backedgei[++j] = i; + } + backedgei[n] = nedges; + + /* + * Set up the initial tour. At all times, our tour is a circuit + * of graph vertices (which may, and probably will often, + * repeat vertices). To begin with, it's got exactly one vertex + * in it, which is the player's current starting point. + */ + circuitsize = 256; + circuit = snewn(circuitsize, int); + circuitlen = 0; + circuit[circuitlen++] = 0; /* node index 0 is the starting posn */ + + /* + * Track which gems are as yet unvisited. + */ + unvisited = snewn(wh, int); + for (i = 0; i < wh; i++) + unvisited[i] = FALSE; + for (i = 0; i < wh; i++) + if (currstate->grid[i] == GEM) + unvisited[i] = TRUE; + + /* + * Allocate space for doing bfses inside the main loop. + */ + dist = snewn(n, int); + dist2 = snewn(n, int); + list = snewn(n, int); + + err = NULL; + soln = NULL; + + /* + * Now enter the main loop, in each iteration of which we + * extend the tour to take in an as yet uncollected gem. + */ + while (1) { + int target, n1, n2, bestdist, extralen, targetpos; + +#ifdef TSP_DIAGNOSTICS + printf("circuit is"); + for (i = 0; i < circuitlen; i++) { + int nc = nodes[circuit[i]]; + printf(" (%d,%d,%d)", nc/DP1%w, nc/(DP1*w), nc%DP1); + } + printf("\n"); + printf("moves are "); + x = nodes[circuit[0]] / DP1 % w; + y = nodes[circuit[0]] / DP1 / w; + for (i = 1; i < circuitlen; i++) { + int x2, y2, dx, dy; + if (nodes[circuit[i]] % DP1 != DIRECTIONS) + continue; + x2 = nodes[circuit[i]] / DP1 % w; + y2 = nodes[circuit[i]] / DP1 / w; + dx = (x2 > x ? +1 : x2 < x ? -1 : 0); + dy = (y2 > y ? +1 : y2 < y ? -1 : 0); + for (d = 0; d < DIRECTIONS; d++) + if (DX(d) == dx && DY(d) == dy) + printf("%c", "89632147"[d]); + x = x2; + y = y2; + } + printf("\n"); +#endif + + /* + * First, start a pair of bfses at _every_ vertex currently + * in the tour, and extend them outwards to find the + * nearest as yet unreached gem vertex. + * + * This is largely a heuristic: we could pick _any_ doubly + * reachable node here and still get a valid tour as + * output. I hope that picking a nearby one will result in + * generally good tours. + */ + for (pass = 0; pass < 2; pass++) { + int *ep = (pass == 0 ? edges : backedges); + int *ei = (pass == 0 ? edgei : backedgei); + int *dp = (pass == 0 ? dist : dist2); + head = tail = 0; + for (i = 0; i < n; i++) + dp[i] = -1; + for (i = 0; i < circuitlen; i++) { + int ni = circuit[i]; + if (dp[ni] < 0) { + dp[ni] = 0; + list[tail++] = ni; + } + } + while (head < tail) { + int ni = list[head++]; + for (i = ei[ni]; i < ei[ni+1]; i++) { + int ti = ep[i]; + if (ti >= 0 && dp[ti] < 0) { + dp[ti] = dp[ni] + 1; + list[tail++] = ti; + } + } + } + } + /* Now find the nearest unvisited gem. */ + bestdist = -1; + target = -1; + for (i = 0; i < n; i++) { + if (unvisited[nodes[i] / DP1] && + dist[i] >= 0 && dist2[i] >= 0) { + int thisdist = dist[i] + dist2[i]; + if (bestdist < 0 || bestdist > thisdist) { + bestdist = thisdist; + target = i; + } + } + } + + if (target < 0) { + /* + * If we get to here, we haven't found a gem we can get + * at all, which means we terminate this loop. + */ + break; + } + + /* + * Now we have a graph vertex at list[tail-1] which is an + * unvisited gem. We want to add that vertex to our tour. + * So we run two more breadth-first searches: one starting + * from that vertex and following forward edges, and + * another starting from the same vertex and following + * backward edges. This allows us to determine, for each + * node on the current tour, how quickly we can get both to + * and from the target vertex from that node. + */ +#ifdef TSP_DIAGNOSTICS + printf("target node is %d (%d,%d,%d)\n", target, nodes[target]/DP1%w, + nodes[target]/DP1/w, nodes[target]%DP1); +#endif + + for (pass = 0; pass < 2; pass++) { + int *ep = (pass == 0 ? edges : backedges); + int *ei = (pass == 0 ? edgei : backedgei); + int *dp = (pass == 0 ? dist : dist2); + + for (i = 0; i < n; i++) + dp[i] = -1; + head = tail = 0; + + dp[target] = 0; + list[tail++] = target; + + while (head < tail) { + int ni = list[head++]; + for (i = ei[ni]; i < ei[ni+1]; i++) { + int ti = ep[i]; + if (ti >= 0 && dp[ti] < 0) { + dp[ti] = dp[ni] + 1; +/*printf("pass %d: set dist of vertex %d to %d (via %d)\n", pass, ti, dp[ti], ni);*/ + list[tail++] = ti; + } + } + } + } + + /* + * Now for every node n, dist[n] gives the length of the + * shortest path from the target vertex to n, and dist2[n] + * gives the length of the shortest path from n to the + * target vertex. + * + * Our next step is to search linearly along the tour to + * find the optimum place to insert a trip to the target + * vertex and back. Our two options are either + * (a) to find two adjacent vertices A,B in the tour and + * replace the edge A->B with the path A->target->B + * (b) to find a single vertex X in the tour and replace + * it with the complete round trip X->target->X. + * We do whichever takes the fewest moves. + */ + n1 = n2 = -1; + bestdist = -1; + for (i = 0; i < circuitlen; i++) { + int thisdist; + + /* + * Try a round trip from vertex i. + */ + if (dist[circuit[i]] >= 0 && + dist2[circuit[i]] >= 0) { + thisdist = dist[circuit[i]] + dist2[circuit[i]]; + if (bestdist < 0 || thisdist < bestdist) { + bestdist = thisdist; + n1 = n2 = i; + } + } + + /* + * Try a trip from vertex i via target to vertex i+1. + */ + if (i+1 < circuitlen && + dist2[circuit[i]] >= 0 && + dist[circuit[i+1]] >= 0) { + thisdist = dist2[circuit[i]] + dist[circuit[i+1]]; + if (bestdist < 0 || thisdist < bestdist) { + bestdist = thisdist; + n1 = i; + n2 = i+1; + } + } + } + if (bestdist < 0) { + /* + * We couldn't find a round trip taking in this gem _at + * all_. Give up. + */ + err = "Unable to find a solution from this starting point"; + break; + } +#ifdef TSP_DIAGNOSTICS + printf("insertion point: n1=%d, n2=%d, dist=%d\n", n1, n2, bestdist); +#endif + +#ifdef TSP_DIAGNOSTICS + printf("circuit before lengthening is"); + for (i = 0; i < circuitlen; i++) { + printf(" %d", circuit[i]); + } + printf("\n"); +#endif + + /* + * Now actually lengthen the tour to take in this round + * trip. + */ + extralen = dist2[circuit[n1]] + dist[circuit[n2]]; + if (n1 != n2) + extralen--; + circuitlen += extralen; + if (circuitlen >= circuitsize) { + circuitsize = circuitlen + 256; + circuit = sresize(circuit, circuitsize, int); + } + memmove(circuit + n2 + extralen, circuit + n2, + (circuitlen - n2 - extralen) * sizeof(int)); + n2 += extralen; + +#ifdef TSP_DIAGNOSTICS + printf("circuit in middle of lengthening is"); + for (i = 0; i < circuitlen; i++) { + printf(" %d", circuit[i]); + } + printf("\n"); +#endif + + /* + * Find the shortest-path routes to and from the target, + * and write them into the circuit. + */ + targetpos = n1 + dist2[circuit[n1]]; + assert(targetpos - dist2[circuit[n1]] == n1); + assert(targetpos + dist[circuit[n2]] == n2); + for (pass = 0; pass < 2; pass++) { + int dir = (pass == 0 ? -1 : +1); + int *ep = (pass == 0 ? backedges : edges); + int *ei = (pass == 0 ? backedgei : edgei); + int *dp = (pass == 0 ? dist : dist2); + int nn = (pass == 0 ? n2 : n1); + int ni = circuit[nn], ti, dest = nn; + + while (1) { + circuit[dest] = ni; + if (dp[ni] == 0) + break; + dest += dir; + ti = -1; +/*printf("pass %d: looking at vertex %d\n", pass, ni);*/ + for (i = ei[ni]; i < ei[ni+1]; i++) { + ti = ep[i]; + if (ti >= 0 && dp[ti] == dp[ni] - 1) + break; + } + assert(i < ei[ni+1] && ti >= 0); + ni = ti; + } + } + +#ifdef TSP_DIAGNOSTICS + printf("circuit after lengthening is"); + for (i = 0; i < circuitlen; i++) { + printf(" %d", circuit[i]); + } + printf("\n"); +#endif + + /* + * Finally, mark all gems that the new piece of circuit + * passes through as visited. + */ + for (i = n1; i <= n2; i++) { + int pos = nodes[circuit[i]] / DP1; + assert(pos >= 0 && pos < wh); + unvisited[pos] = FALSE; + } + } + +#ifdef TSP_DIAGNOSTICS + printf("before reduction, moves are "); + x = nodes[circuit[0]] / DP1 % w; + y = nodes[circuit[0]] / DP1 / w; + for (i = 1; i < circuitlen; i++) { + int x2, y2, dx, dy; + if (nodes[circuit[i]] % DP1 != DIRECTIONS) + continue; + x2 = nodes[circuit[i]] / DP1 % w; + y2 = nodes[circuit[i]] / DP1 / w; + dx = (x2 > x ? +1 : x2 < x ? -1 : 0); + dy = (y2 > y ? +1 : y2 < y ? -1 : 0); + for (d = 0; d < DIRECTIONS; d++) + if (DX(d) == dx && DY(d) == dy) + printf("%c", "89632147"[d]); + x = x2; + y = y2; + } + printf("\n"); +#endif + + /* + * That's got a basic solution. Now optimise it by removing + * redundant sections of the circuit: it's entirely possible + * that a piece of circuit we carefully inserted at one stage + * to collect a gem has become pointless because the steps + * required to collect some _later_ gem necessarily passed + * through the same one. + * + * So first we go through and work out how many times each gem + * is collected. Then we look for maximal sections of circuit + * which are redundant in the sense that their removal would + * not reduce any gem's collection count to zero, and replace + * each one with a bfs-derived fastest path between their + * endpoints. + */ + while (1) { + int oldlen = circuitlen; + int dir; + + for (dir = +1; dir >= -1; dir -= 2) { + + for (i = 0; i < wh; i++) + unvisited[i] = 0; + for (i = 0; i < circuitlen; i++) { + int xy = nodes[circuit[i]] / DP1; + if (currstate->grid[xy] == GEM) + unvisited[xy]++; + } + + /* + * If there's any gem we didn't end up visiting at all, + * give up. + */ + for (i = 0; i < wh; i++) { + if (currstate->grid[i] == GEM && unvisited[i] == 0) { + err = "Unable to find a solution from this starting point"; + break; + } + } + if (i < wh) + break; + + for (i = j = (dir > 0 ? 0 : circuitlen-1); + i < circuitlen && i >= 0; + i += dir) { + int xy = nodes[circuit[i]] / DP1; + if (currstate->grid[xy] == GEM && unvisited[xy] > 1) { + unvisited[xy]--; + } else if (currstate->grid[xy] == GEM || i == circuitlen-1) { + /* + * circuit[i] collects a gem for the only time, + * or is the last node in the circuit. + * Therefore it cannot be removed; so we now + * want to replace the path from circuit[j] to + * circuit[i] with a bfs-shortest path. + */ + int p, q, k, dest, ni, ti, thisdist; + + /* + * Set up the upper and lower bounds of the + * reduced section. + */ + p = min(i, j); + q = max(i, j); + +#ifdef TSP_DIAGNOSTICS + printf("optimising section from %d - %d\n", p, q); +#endif + + for (k = 0; k < n; k++) + dist[k] = -1; + head = tail = 0; + + dist[circuit[p]] = 0; + list[tail++] = circuit[p]; + + while (head < tail && dist[circuit[q]] < 0) { + int ni = list[head++]; + for (k = edgei[ni]; k < edgei[ni+1]; k++) { + int ti = edges[k]; + if (ti >= 0 && dist[ti] < 0) { + dist[ti] = dist[ni] + 1; + list[tail++] = ti; + } + } + } + + thisdist = dist[circuit[q]]; + assert(thisdist >= 0 && thisdist <= q-p); + + memmove(circuit+p+thisdist, circuit+q, + (circuitlen - q) * sizeof(int)); + circuitlen -= q-p; + q = p + thisdist; + circuitlen += q-p; + + if (dir > 0) + i = q; /* resume loop from the right place */ + +#ifdef TSP_DIAGNOSTICS + printf("new section runs from %d - %d\n", p, q); +#endif + + dest = q; + assert(dest >= 0); + ni = circuit[q]; + + while (1) { + /* printf("dest=%d circuitlen=%d ni=%d dist[ni]=%d\n", dest, circuitlen, ni, dist[ni]); */ + circuit[dest] = ni; + if (dist[ni] == 0) + break; + dest--; + ti = -1; + for (k = backedgei[ni]; k < backedgei[ni+1]; k++) { + ti = backedges[k]; + if (ti >= 0 && dist[ti] == dist[ni] - 1) + break; + } + assert(k < backedgei[ni+1] && ti >= 0); + ni = ti; + } + + /* + * Now re-increment the visit counts for the + * new path. + */ + while (++p < q) { + int xy = nodes[circuit[p]] / DP1; + if (currstate->grid[xy] == GEM) + unvisited[xy]++; + } + + j = i; + +#ifdef TSP_DIAGNOSTICS + printf("during reduction, circuit is"); + for (k = 0; k < circuitlen; k++) { + int nc = nodes[circuit[k]]; + printf(" (%d,%d,%d)", nc/DP1%w, nc/(DP1*w), nc%DP1); + } + printf("\n"); + printf("moves are "); + x = nodes[circuit[0]] / DP1 % w; + y = nodes[circuit[0]] / DP1 / w; + for (k = 1; k < circuitlen; k++) { + int x2, y2, dx, dy; + if (nodes[circuit[k]] % DP1 != DIRECTIONS) + continue; + x2 = nodes[circuit[k]] / DP1 % w; + y2 = nodes[circuit[k]] / DP1 / w; + dx = (x2 > x ? +1 : x2 < x ? -1 : 0); + dy = (y2 > y ? +1 : y2 < y ? -1 : 0); + for (d = 0; d < DIRECTIONS; d++) + if (DX(d) == dx && DY(d) == dy) + printf("%c", "89632147"[d]); + x = x2; + y = y2; + } + printf("\n"); +#endif + } + } + +#ifdef TSP_DIAGNOSTICS + printf("after reduction, moves are "); + x = nodes[circuit[0]] / DP1 % w; + y = nodes[circuit[0]] / DP1 / w; + for (i = 1; i < circuitlen; i++) { + int x2, y2, dx, dy; + if (nodes[circuit[i]] % DP1 != DIRECTIONS) + continue; + x2 = nodes[circuit[i]] / DP1 % w; + y2 = nodes[circuit[i]] / DP1 / w; + dx = (x2 > x ? +1 : x2 < x ? -1 : 0); + dy = (y2 > y ? +1 : y2 < y ? -1 : 0); + for (d = 0; d < DIRECTIONS; d++) + if (DX(d) == dx && DY(d) == dy) + printf("%c", "89632147"[d]); + x = x2; + y = y2; + } + printf("\n"); +#endif + } + + /* + * If we've managed an entire reduction pass in each + * direction and not made the solution any shorter, we're + * _really_ done. + */ + if (circuitlen == oldlen) + break; + } + + /* + * Encode the solution as a move string. + */ + if (!err) { + soln = snewn(circuitlen+2, char); + p = soln; + *p++ = 'S'; + x = nodes[circuit[0]] / DP1 % w; + y = nodes[circuit[0]] / DP1 / w; + for (i = 1; i < circuitlen; i++) { + int x2, y2, dx, dy; + if (nodes[circuit[i]] % DP1 != DIRECTIONS) + continue; + x2 = nodes[circuit[i]] / DP1 % w; + y2 = nodes[circuit[i]] / DP1 / w; + dx = (x2 > x ? +1 : x2 < x ? -1 : 0); + dy = (y2 > y ? +1 : y2 < y ? -1 : 0); + for (d = 0; d < DIRECTIONS; d++) + if (DX(d) == dx && DY(d) == dy) { + *p++ = '0' + d; + break; + } + assert(d < DIRECTIONS); + x = x2; + y = y2; + } + *p++ = '\0'; + assert(p - soln < circuitlen+2); + } + + sfree(list); + sfree(dist); + sfree(dist2); + sfree(unvisited); + sfree(circuit); + sfree(backedgei); + sfree(backedges); + sfree(edgei); + sfree(edges); + sfree(nodeindex); + sfree(nodes); + + if (err) + *error = err; + + return soln; +} + +static int game_can_format_as_text_now(const game_params *params) +{ + return TRUE; +} + +static char *game_text_format(const game_state *state) +{ + int w = state->p.w, h = state->p.h, r, c; + int cw = 4, ch = 2, gw = cw*w + 2, gh = ch * h + 1, len = gw * gh; + char *board = snewn(len + 1, char); + + sprintf(board, "%*s+\n", len - 2, ""); + + for (r = 0; r < h; ++r) { + for (c = 0; c < w; ++c) { + int cell = r*ch*gw + cw*c, center = cell + gw*ch/2 + cw/2; + int i = r*w + c; + switch (state->grid[i]) { + case BLANK: break; + case GEM: board[center] = 'o'; break; + case MINE: board[center] = 'M'; break; + case STOP: board[center-1] = '('; board[center+1] = ')'; break; + case WALL: memset(board + center - 1, 'X', 3); + } + + if (r == state->py && c == state->px) { + if (!state->dead) board[center] = '@'; + else memcpy(board + center - 1, ":-(", 3); + } + board[cell] = '+'; + memset(board + cell + 1, '-', cw - 1); + for (i = 1; i < ch; ++i) board[cell + i*gw] = '|'; + } + for (c = 0; c < ch; ++c) { + board[(r*ch+c)*gw + gw - 2] = "|+"[!c]; + board[(r*ch+c)*gw + gw - 1] = '\n'; + } + } + memset(board + len - gw, '-', gw - 2); + for (c = 0; c < w; ++c) board[len - gw + cw*c] = '+'; + + return board; } struct game_ui { @@ -672,7 +1498,7 @@ struct game_ui { int just_died; }; -static game_ui *new_ui(game_state *state) +static game_ui *new_ui(const game_state *state) { game_ui *ui = snew(game_ui); ui->anim_length = 0.0F; @@ -688,7 +1514,7 @@ static void free_ui(game_ui *ui) sfree(ui); } -static char *encode_ui(game_ui *ui) +static char *encode_ui(const game_ui *ui) { char buf[80]; /* @@ -698,23 +1524,23 @@ static char *encode_ui(game_ui *ui) return dupstr(buf); } -static void decode_ui(game_ui *ui, char *encoding) +static void decode_ui(game_ui *ui, const char *encoding) { int p = 0; sscanf(encoding, "D%d%n", &ui->deaths, &p); } -static void game_changed_state(game_ui *ui, game_state *oldstate, - game_state *newstate) +static void game_changed_state(game_ui *ui, const game_state *oldstate, + const game_state *newstate) { /* * Increment the deaths counter. We only do this if * ui->just_made_move is set (redoing a suicide move doesn't - * kill you _again_), and also we only do it if the game isn't - * completed (once you're finished, you can play). + * kill you _again_), and also we only do it if the game wasn't + * already completed (once you're finished, you can play). */ if (!oldstate->dead && newstate->dead && ui->just_made_move && - newstate->gems) { + oldstate->gems) { ui->deaths++; ui->just_died = TRUE; } else { @@ -734,13 +1560,18 @@ struct game_drawstate { #define PREFERRED_TILESIZE 32 #define TILESIZE (ds->tilesize) +#ifdef SMALL_SCREEN +#define BORDER (TILESIZE / 4) +#else #define BORDER (TILESIZE) +#endif #define HIGHLIGHT_WIDTH (TILESIZE / 10) #define COORD(x) ( (x) * TILESIZE + BORDER ) #define FROMCOORD(x) ( ((x) - BORDER + TILESIZE) / TILESIZE - 1 ) -static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds, - int x, int y, int button) +static char *interpret_move(const game_state *state, game_ui *ui, + const game_drawstate *ds, + int x, int y, int button) { int w = state->p.w, h = state->p.h /*, wh = w*h */; int dir; @@ -785,6 +1616,9 @@ static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds, dir = 1; else if (button == (MOD_NUM_KEYPAD | '3')) dir = 3; + else if (IS_CURSOR_SELECT(button) && + state->soln && state->solnpos < state->soln->len) + dir = state->soln->list[state->solnpos]; if (dir < 0) return NULL; @@ -811,12 +1645,55 @@ static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds, return dupstr(buf); } -static game_state *execute_move(game_state *state, char *move) +static void install_new_solution(game_state *ret, const char *move) +{ + int i; + soln *sol; + assert (*move == 'S'); + ++move; + + sol = snew(soln); + sol->len = strlen(move); + sol->list = snewn(sol->len, unsigned char); + for (i = 0; i < sol->len; ++i) sol->list[i] = move[i] - '0'; + + if (ret->soln && --ret->soln->refcount == 0) { + sfree(ret->soln->list); + sfree(ret->soln); + } + + ret->soln = sol; + sol->refcount = 1; + + ret->cheated = TRUE; + ret->solnpos = 0; +} + +static void discard_solution(game_state *ret) +{ + --ret->soln->refcount; + assert(ret->soln->refcount > 0); /* ret has a soln-pointing dup */ + ret->soln = NULL; + ret->solnpos = 0; +} + +static game_state *execute_move(const game_state *state, const char *move) { int w = state->p.w, h = state->p.h /*, wh = w*h */; - int dir = atoi(move); + int dir; game_state *ret; + if (*move == 'S') { + /* + * This is a solve move, so we don't actually _change_ the + * grid but merely set up a stored solution path. + */ + ret = dup_game(state); + install_new_solution(ret, move); + return ret; + } + + dir = atoi(move); if (dir < 0 || dir >= DIRECTIONS) return NULL; /* huh? */ @@ -852,6 +1729,22 @@ static game_state *execute_move(game_state *state, char *move) break; } + if (ret->soln) { + if (ret->dead || ret->gems == 0) + discard_solution(ret); + else if (ret->soln->list[ret->solnpos] == dir) { + ++ret->solnpos; + assert(ret->solnpos < ret->soln->len); /* or gems == 0 */ + assert(!ret->dead); /* or not a solution */ + } else { + char *error = NULL, *soln = solve_game(NULL, ret, NULL, &error); + if (!error) { + install_new_solution(ret, soln); + sfree(soln); + } else discard_solution(ret); + } + } + return ret; } @@ -859,8 +1752,8 @@ static game_state *execute_move(game_state *state, char *move) * Drawing routines. */ -static void game_compute_size(game_params *params, int tilesize, - int *x, int *y) +static void game_compute_size(const game_params *params, int tilesize, + int *x, int *y) { /* Ick: fake up `ds->tilesize' for macro expansion purposes */ struct { int tilesize; } ads, *ds = &ads; @@ -871,18 +1764,17 @@ static void game_compute_size(game_params *params, int tilesize, } static void game_set_size(drawing *dr, game_drawstate *ds, - game_params *params, int tilesize) + const game_params *params, int tilesize) { ds->tilesize = tilesize; + assert(!ds->player_background); /* set_size is never called twice */ assert(!ds->player_bg_saved); - if (ds->player_background) - blitter_free(dr, ds->player_background); ds->player_background = blitter_new(dr, TILESIZE, TILESIZE); } -static float *game_colours(frontend *fe, game_state *state, int *ncolours) +static float *game_colours(frontend *fe, int *ncolours) { float *ret = snewn(3 * NCOLOURS, float); int i; @@ -914,11 +1806,15 @@ static float *game_colours(frontend *fe, game_state *state, int *ncolours) 1 * ret[COL_HIGHLIGHT * 3 + i]) / 4; } + ret[COL_HINT * 3 + 0] = 1.0F; + ret[COL_HINT * 3 + 1] = 1.0F; + ret[COL_HINT * 3 + 2] = 0.0F; + *ncolours = NCOLOURS; return ret; } -static game_drawstate *game_new_drawstate(drawing *dr, game_state *state) +static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state) { int w = state->p.w, h = state->p.h, wh = w*h; struct game_drawstate *ds = snew(struct game_drawstate); @@ -950,7 +1846,7 @@ static void game_free_drawstate(drawing *dr, game_drawstate *ds) } static void draw_player(drawing *dr, game_drawstate *ds, int x, int y, - int dead) + int dead, int hintdir) { if (dead) { int coords[DIRECTIONS*4]; @@ -980,6 +1876,33 @@ static void draw_player(drawing *dr, game_drawstate *ds, int x, int y, draw_circle(dr, x + TILESIZE/2, y + TILESIZE/2, TILESIZE/3, COL_PLAYER, COL_OUTLINE); } + + if (!dead && hintdir >= 0) { + float scale = (DX(hintdir) && DY(hintdir) ? 0.8F : 1.0F); + int ax = (TILESIZE*2/5) * scale * DX(hintdir); + int ay = (TILESIZE*2/5) * scale * DY(hintdir); + int px = -ay, py = ax; + int ox = x + TILESIZE/2, oy = y + TILESIZE/2; + int coords[14], *c; + + c = coords; + *c++ = ox + px/9; + *c++ = oy + py/9; + *c++ = ox + px/9 + ax*2/3; + *c++ = oy + py/9 + ay*2/3; + *c++ = ox + px/3 + ax*2/3; + *c++ = oy + py/3 + ay*2/3; + *c++ = ox + ax; + *c++ = oy + ay; + *c++ = ox - px/3 + ax*2/3; + *c++ = oy - py/3 + ay*2/3; + *c++ = ox - px/9 + ax*2/3; + *c++ = oy - py/9 + ay*2/3; + *c++ = ox - px/9; + *c++ = oy - py/9; + draw_polygon(dr, coords, 7, COL_HINT, COL_OUTLINE); + } + draw_update(dr, x, y, TILESIZE, TILESIZE); } @@ -1020,32 +1943,10 @@ static void draw_tile(drawing *dr, game_drawstate *ds, int x, int y, int v) int cx = tx + TILESIZE / 2; int cy = ty + TILESIZE / 2; int r = TILESIZE / 2 - 3; - int coords[4*5*2]; - int xdx = 1, xdy = 0, ydx = 0, ydy = 1; - int tdx, tdy, i; - - for (i = 0; i < 4*5*2; i += 5*2) { - coords[i+2*0+0] = cx - r/6*xdx + r*4/5*ydx; - coords[i+2*0+1] = cy - r/6*xdy + r*4/5*ydy; - coords[i+2*1+0] = cx - r/6*xdx + r*ydx; - coords[i+2*1+1] = cy - r/6*xdy + r*ydy; - coords[i+2*2+0] = cx + r/6*xdx + r*ydx; - coords[i+2*2+1] = cy + r/6*xdy + r*ydy; - coords[i+2*3+0] = cx + r/6*xdx + r*4/5*ydx; - coords[i+2*3+1] = cy + r/6*xdy + r*4/5*ydy; - coords[i+2*4+0] = cx + r*3/5*xdx + r*3/5*ydx; - coords[i+2*4+1] = cy + r*3/5*xdy + r*3/5*ydy; - - tdx = ydx; - tdy = ydy; - ydx = xdx; - ydy = xdy; - xdx = -tdx; - xdy = -tdy; - } - - draw_polygon(dr, coords, 5*4, COL_MINE, COL_MINE); + draw_circle(dr, cx, cy, 5*r/6, COL_MINE, COL_MINE); + draw_rect(dr, cx - r/6, cy - r, 2*(r/6)+1, 2*r+1, COL_MINE); + draw_rect(dr, cx - r, cy - r/6, 2*r+1, 2*(r/6)+1, COL_MINE); draw_rect(dr, cx-r/3, cy-r/3, r/3, r/4, COL_HIGHLIGHT); } else if (v == STOP) { draw_circle(dr, tx + TILESIZE/2, ty + TILESIZE/2, @@ -1058,12 +1959,12 @@ static void draw_tile(drawing *dr, game_drawstate *ds, int x, int y, int v) int coords[8]; coords[0] = tx+TILESIZE/2; - coords[1] = ty+TILESIZE*1/7; - coords[2] = tx+TILESIZE*1/7; + coords[1] = ty+TILESIZE/2-TILESIZE*5/14; + coords[2] = tx+TILESIZE/2-TILESIZE*5/14; coords[3] = ty+TILESIZE/2; coords[4] = tx+TILESIZE/2; - coords[5] = ty+TILESIZE-TILESIZE*1/7; - coords[6] = tx+TILESIZE-TILESIZE*1/7; + coords[5] = ty+TILESIZE/2+TILESIZE*5/14; + coords[6] = tx+TILESIZE/2+TILESIZE*5/14; coords[7] = ty+TILESIZE/2; draw_polygon(dr, coords, 4, COL_GEM, COL_OUTLINE); @@ -1076,9 +1977,10 @@ static void draw_tile(drawing *dr, game_drawstate *ds, int x, int y, int v) #define BASE_ANIM_LENGTH 0.1F #define FLASH_LENGTH 0.3F -static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate, - game_state *state, int dir, game_ui *ui, - float animtime, float flashtime) +static void game_redraw(drawing *dr, game_drawstate *ds, + const game_state *oldstate, const game_state *state, + int dir, const game_ui *ui, + float animtime, float flashtime) { int w = state->p.w, h = state->p.h /*, wh = w*h */; int x, y; @@ -1205,12 +2107,19 @@ static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate, * shown between the collection of the last gem and the * completion of the move animation that did it.) */ - if (state->dead && (!oldstate || oldstate->dead)) + if (state->dead && (!oldstate || oldstate->dead)) { sprintf(status, "DEAD!"); - else if (state->gems || (oldstate && oldstate->gems)) - sprintf(status, "Gems: %d", gems); - else + } else if (state->gems || (oldstate && oldstate->gems)) { + if (state->cheated) + sprintf(status, "Auto-solver used. "); + else + *status = '\0'; + sprintf(status + strlen(status), "Gems: %d", gems); + } else if (state->cheated) { + sprintf(status, "Auto-solved."); + } else { sprintf(status, "COMPLETED!"); + } /* We subtract one from the visible death counter if we're still * animating the move at the end of which the death took place. */ deaths = ui->deaths; @@ -1242,12 +2151,15 @@ static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate, ds->pbgy = oy + ap * (ny - oy); } blitter_save(dr, ds->player_background, ds->pbgx, ds->pbgy); - draw_player(dr, ds, ds->pbgx, ds->pbgy, (state->dead && !oldstate)); + draw_player(dr, ds, ds->pbgx, ds->pbgy, + (state->dead && !oldstate), + (!oldstate && state->soln ? + state->soln->list[state->solnpos] : -1)); ds->player_bg_saved = TRUE; } -static float game_anim_length(game_state *oldstate, game_state *newstate, - int dir, game_ui *ui) +static float game_anim_length(const game_state *oldstate, + const game_state *newstate, int dir, game_ui *ui) { int dist; if (dir > 0) @@ -1258,8 +2170,8 @@ static float game_anim_length(game_state *oldstate, game_state *newstate, return ui->anim_length; } -static float game_flash_length(game_state *oldstate, game_state *newstate, - int dir, game_ui *ui) +static float game_flash_length(const game_state *oldstate, + const game_state *newstate, int dir, game_ui *ui) { if (!oldstate->dead && newstate->dead) { ui->flashtype = FLASH_DEAD; @@ -1271,21 +2183,26 @@ static float game_flash_length(game_state *oldstate, game_state *newstate, return 0.0F; } -static int game_wants_statusbar(void) +static int game_status(const game_state *state) { - return TRUE; + /* + * We never report the game as lost, on the grounds that if the + * player has died they're quite likely to want to undo and carry + * on. + */ + return state->gems == 0 ? +1 : 0; } -static int game_timing_state(game_state *state, game_ui *ui) +static int game_timing_state(const game_state *state, game_ui *ui) { return TRUE; } -static void game_print_size(game_params *params, float *x, float *y) +static void game_print_size(const game_params *params, float *x, float *y) { } -static void game_print(drawing *dr, game_state *state, int tilesize) +static void game_print(drawing *dr, const game_state *state, int tilesize) { } @@ -1294,7 +2211,7 @@ static void game_print(drawing *dr, game_state *state, int tilesize) #endif const struct game thegame = { - "Inertia", "games.inertia", + "Inertia", "games.inertia", "inertia", default_params, game_fetch_preset, decode_params, @@ -1308,8 +2225,8 @@ const struct game thegame = { new_game, dup_game, free_game, - FALSE, solve_game, - FALSE, game_text_format, + TRUE, solve_game, + TRUE, game_can_format_as_text_now, game_text_format, new_ui, free_ui, encode_ui, @@ -1324,8 +2241,9 @@ const struct game thegame = { game_redraw, game_anim_length, game_flash_length, + game_status, FALSE, FALSE, game_print_size, game_print, - game_wants_statusbar, + TRUE, /* wants_statusbar */ FALSE, game_timing_state, - 0, /* mouse_priorities */ + 0, /* flags */ };