X-Git-Url: https://git.distorted.org.uk/~mdw/sgt/puzzles/blobdiff_plain/8b5b08f78dbca1843ba9460cc54dd647fbb0e364..9856b2637ad6d34dc05b6a4b41a0809db619537c:/inertia.c diff --git a/inertia.c b/inertia.c index 41bcc89..74fc3c1 100644 --- a/inertia.c +++ b/inertia.c @@ -88,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; } @@ -106,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) @@ -735,6 +744,18 @@ static char *solve_game(game_state *state, game_state *currstate, 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. @@ -1198,159 +1219,179 @@ static char *solve_game(game_state *state, game_state *currstate, */ while (1) { int oldlen = circuitlen; + int dir; - 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]++; - } + for (dir = +1; dir >= -1; dir -= 2) { - /* - * 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; + 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 (i < wh) - break; - for (i = j = 0; i < circuitlen; i++) { - 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 k, dest, ni, ti, thisdist; + /* + * 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", j, i); + printf("optimising section from %d - %d\n", p, q); #endif - for (k = 0; k < n; k++) - dist[k] = -1; - head = tail = 0; - - dist[circuit[j]] = 0; - list[tail++] = circuit[j]; - - while (head < tail && dist[circuit[i]] < 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; + 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[i]]; - assert(thisdist >= 0 && thisdist <= i-j); + thisdist = dist[circuit[q]]; + assert(thisdist >= 0 && thisdist <= q-p); - memmove(circuit+j+thisdist, circuit+i, - (circuitlen - i) * sizeof(int)); - circuitlen -= i-j; - i = j + thisdist; - circuitlen += i-j; + 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", j, i); + printf("new section runs from %d - %d\n", p, q); #endif - dest = i; - assert(dest >= 0); - ni = circuit[i]; + 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) + 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; } - assert(k < backedgei[ni+1] && ti >= 0); - ni = ti; - } - /* - * Now re-increment the visit counts for the new - * path. - */ - while (++j < i) { - int xy = nodes[circuit[j]] / DP1; - if (currstate->grid[xy] == GEM) - unvisited[xy]++; - } + /* + * 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"); + 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"); + 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 and not made - * the solution any shorter, we're _really_ done. + * 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; @@ -1404,6 +1445,11 @@ static char *solve_game(game_state *state, game_state *currstate, return soln; } +static int game_can_format_as_text_now(game_params *params) +{ + return TRUE; +} + static char *game_text_format(game_state *state) { return NULL; @@ -1479,7 +1525,11 @@ 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 ) @@ -1530,7 +1580,8 @@ 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 (button == ' ' && state->soln && state->solnpos < state->soln->len) + else if (IS_CURSOR_SELECT(button) && + state->soln && state->solnpos < state->soln->len) dir = state->soln->list[state->solnpos]; if (dir < 0) @@ -1581,6 +1632,10 @@ static game_state *execute_move(game_state *state, char *move) sol->list[i] = move[i] - '0'; ret = dup_game(state); ret->cheated = TRUE; + if (ret->soln && --ret->soln->refcount == 0) { + sfree(ret->soln->list); + sfree(ret->soln); + } ret->soln = sol; ret->solnpos = 0; sol->refcount = 1; @@ -1672,7 +1727,7 @@ static void game_set_size(drawing *dr, game_drawstate *ds, 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; @@ -1841,32 +1896,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, @@ -1879,12 +1912,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); @@ -2102,9 +2135,14 @@ static float game_flash_length(game_state *oldstate, game_state *newstate, return 0.0F; } -static int game_wants_statusbar(void) +static int game_status(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) @@ -2125,7 +2163,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, @@ -2140,7 +2178,7 @@ const struct game thegame = { dup_game, free_game, TRUE, solve_game, - FALSE, game_text_format, + FALSE, game_can_format_as_text_now, game_text_format, new_ui, free_ui, encode_ui, @@ -2155,8 +2193,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 */ };