X-Git-Url: https://git.distorted.org.uk/~mdw/sgt/puzzles/blobdiff_plain/c51c7de6576daa0fbe9c63fc2aa98bff2e1bf950..44bf5f6fb23fec37056c36580bb4e02fdf610915:/map.c?ds=sidebyside diff --git a/map.c b/map.c index 5a9bf5e..45d6329 100644 --- a/map.c +++ b/map.c @@ -5,7 +5,6 @@ /* * TODO: * - * - error highlighting * - clue marking * - more solver brains? * - better four-colouring algorithm? @@ -43,7 +42,8 @@ static float flash_length; */ #define DIFFLIST(A) \ A(EASY,Easy,e) \ - A(NORMAL,Normal,n) + A(NORMAL,Normal,n) \ + A(RECURSE,Unreasonable,u) #define ENUM(upper,title,lower) DIFF_ ## upper, #define TITLE(upper,title,lower) #title, #define ENCODE(upper,title,lower) #lower @@ -59,6 +59,7 @@ enum { COL_BACKGROUND, COL_GRID, COL_0, COL_1, COL_2, COL_3, + COL_ERROR, COL_ERRTEXT, NCOLOURS }; @@ -73,6 +74,7 @@ struct map { int n; int ngraph; int *immutable; + int *edgex, *edgey; /* positions of a point on each edge */ }; struct game_state { @@ -607,7 +609,7 @@ static int gengraph(int w, int h, int n, int *map, int *graph) return j; } -static int graph_adjacent(int *graph, int n, int ngraph, int i, int j) +static int graph_edge_index(int *graph, int n, int ngraph, int i, int j) { int v = i*n+j; int top, bot, mid; @@ -617,15 +619,18 @@ static int graph_adjacent(int *graph, int n, int ngraph, int i, int j) while (top - bot > 1) { mid = (top + bot) / 2; if (graph[mid] == v) - return TRUE; + return mid; else if (graph[mid] < v) bot = mid; else top = mid; } - return FALSE; + return -1; } +#define graph_adjacent(graph, n, ngraph, i, j) \ + (graph_edge_index((graph), (n), (ngraph), (i), (j)) >= 0) + static int graph_vertex_start(int *graph, int n, int ngraph, int i) { int v = i*n; @@ -785,6 +790,7 @@ struct solver_scratch { int *graph; int n; int ngraph; + int depth; }; static struct solver_scratch *new_scratch(int *graph, int n, int ngraph) @@ -796,6 +802,7 @@ static struct solver_scratch *new_scratch(int *graph, int n, int ngraph) sc->n = n; sc->ngraph = ngraph; sc->possible = snewn(n, unsigned char); + sc->depth = 0; return sc; } @@ -953,13 +960,103 @@ static int map_solver(struct solver_scratch *sc, } /* - * We've run out of things to deduce. See if we've got the lot. + * See if we've got a complete solution, and return if so. */ for (i = 0; i < n; i++) if (colouring[i] < 0) - return 2; + break; + if (i == n) + return 1; /* success! */ + + /* + * If recursion is not permissible, we now give up. + */ + if (difficulty < DIFF_RECURSE) + return 2; /* unable to complete */ + + /* + * Now we've got to do something recursive. So first hunt for a + * currently-most-constrained region. + */ + { + int best, bestc; + struct solver_scratch *rsc; + int *subcolouring, *origcolouring; + int ret, subret; + int we_already_got_one; + + best = -1; + bestc = FIVE; + + for (i = 0; i < n; i++) if (colouring[i] < 0) { + int p = sc->possible[i]; + enum { compile_time_assertion = 1 / (FOUR <= 4) }; + int c; + + /* Count the set bits. */ + c = (p & 5) + ((p >> 1) & 5); + c = (c & 3) + ((c >> 2) & 3); + assert(c > 1); /* or colouring[i] would be >= 0 */ + + if (c < bestc) { + best = i; + bestc = c; + } + } + + assert(best >= 0); /* or we'd be solved already */ + + /* + * Now iterate over the possible colours for this region. + */ + rsc = new_scratch(graph, n, ngraph); + rsc->depth = sc->depth + 1; + origcolouring = snewn(n, int); + memcpy(origcolouring, colouring, n * sizeof(int)); + subcolouring = snewn(n, int); + we_already_got_one = FALSE; + ret = 0; + + for (i = 0; i < FOUR; i++) { + if (!(sc->possible[best] & (1 << i))) + continue; + + memcpy(subcolouring, origcolouring, n * sizeof(int)); + subcolouring[best] = i; + subret = map_solver(rsc, graph, n, ngraph, + subcolouring, difficulty); - return 1; /* success! */ + /* + * If this possibility turned up more than one valid + * solution, or if it turned up one and we already had + * one, we're definitely ambiguous. + */ + if (subret == 2 || (subret == 1 && we_already_got_one)) { + ret = 2; + break; + } + + /* + * If this possibility turned up one valid solution and + * it's the first we've seen, copy it into the output. + */ + if (subret == 1) { + memcpy(colouring, subcolouring, n * sizeof(int)); + we_already_got_one = TRUE; + ret = 1; + } + + /* + * Otherwise, this guess led to a contradiction, so we + * do nothing. + */ + } + + sfree(subcolouring); + free_scratch(rsc); + + return ret; + } } /* ---------------------------------------------------------------------- @@ -969,7 +1066,7 @@ static int map_solver(struct solver_scratch *sc, static char *new_game_desc(game_params *params, random_state *rs, char **aux, int interactive) { - struct solver_scratch *sc; + struct solver_scratch *sc = NULL; int *map, *graph, ngraph, *colouring, *colouring2, *regions; int i, j, w, h, n, solveret, cfreq[FOUR]; int wh; @@ -1103,6 +1200,7 @@ static char *new_game_desc(game_params *params, random_state *rs, shuffle(regions, n, sizeof(*regions), rs); + if (sc) free_scratch(sc); sc = new_scratch(graph, n, ngraph); for (i = 0; i < n; i++) { @@ -1141,8 +1239,8 @@ static char *new_game_desc(game_params *params, random_state *rs, * Finally, check that the puzzle is _at least_ as hard as * required, and indeed that it isn't already solved. * (Calling map_solver with negative difficulty ensures the - * latter - if a solver which _does nothing_ can't solve - * it, it's too easy!) + * latter - if a solver which _does nothing_ can solve it, + * it's too easy!) */ memcpy(colouring2, colouring, n*sizeof(int)); if (map_solver(sc, graph, n, ngraph, colouring2, @@ -1150,7 +1248,7 @@ static char *new_game_desc(game_params *params, random_state *rs, /* * Drop minimum difficulty if necessary. */ - if (mindiff > 0 && (n < 9 || n > 3*wh/2)) { + if (mindiff > 0 && (n < 9 || n > 2*wh/3)) { if (tries-- <= 0) mindiff = 0; /* give up and go for Easy */ } @@ -1388,7 +1486,7 @@ static char *validate_desc(game_params *params, char *desc) return NULL; } -static game_state *new_game(midend_data *me, game_params *params, char *desc) +static game_state *new_game(midend *me, game_params *params, char *desc) { int w = params->w, h = params->h, wh = w*h, n = params->n; int i, pos; @@ -1501,6 +1599,198 @@ static game_state *new_game(midend_data *me, game_params *params, char *desc) random_free(rs); } + /* + * Analyse the map to find a canonical line segment + * corresponding to each edge. These are where we'll eventually + * put error markers. + */ + { + int *bestx, *besty, *an, pass; + float *ax, *ay, *best; + + ax = snewn(state->map->ngraph, float); + ay = snewn(state->map->ngraph, float); + an = snewn(state->map->ngraph, int); + bestx = snewn(state->map->ngraph, int); + besty = snewn(state->map->ngraph, int); + best = snewn(state->map->ngraph, float); + + for (i = 0; i < state->map->ngraph; i++) { + bestx[i] = besty[i] = -1; + best[i] = 2*(w+h)+1; + ax[i] = ay[i] = 0.0F; + an[i] = 0; + } + + /* + * We make two passes over the map, finding all the line + * segments separating regions. In the first pass, we + * compute the _average_ x and y coordinate of all the line + * segments separating each pair of regions; in the second + * pass, for each such average point, we find the line + * segment closest to it and call that canonical. + * + * Line segments are considered to have coordinates in + * their centre. Thus, at least one coordinate for any line + * segment is always something-and-a-half; so we store our + * coordinates as twice their normal value. + */ + for (pass = 0; pass < 2; pass++) { + int x, y; + + for (y = 0; y < h; y++) + for (x = 0; x < w; x++) { + int ex[4], ey[4], ea[4], eb[4], en = 0; + + /* + * Look for an edge to the right of this + * square, an edge below it, and an edge in the + * middle of it. Also look to see if the point + * at the bottom right of this square is on an + * edge (and isn't a place where more than two + * regions meet). + */ + if (x+1 < w) { + /* right edge */ + ea[en] = state->map->map[RE * wh + y*w+x]; + eb[en] = state->map->map[LE * wh + y*w+(x+1)]; + if (ea[en] != eb[en]) { + ex[en] = (x+1)*2; + ey[en] = y*2+1; + en++; + } + } + if (y+1 < h) { + /* bottom edge */ + ea[en] = state->map->map[BE * wh + y*w+x]; + eb[en] = state->map->map[TE * wh + (y+1)*w+x]; + if (ea[en] != eb[en]) { + ex[en] = x*2+1; + ey[en] = (y+1)*2; + en++; + } + } + /* diagonal edge */ + ea[en] = state->map->map[TE * wh + y*w+x]; + eb[en] = state->map->map[BE * wh + y*w+x]; + if (ea[en] != eb[en]) { + ex[en] = x*2+1; + ey[en] = y*2+1; + en++; + } + if (x+1 < w && y+1 < h) { + /* bottom right corner */ + int oct[8], othercol, nchanges; + oct[0] = state->map->map[RE * wh + y*w+x]; + oct[1] = state->map->map[LE * wh + y*w+(x+1)]; + oct[2] = state->map->map[BE * wh + y*w+(x+1)]; + oct[3] = state->map->map[TE * wh + (y+1)*w+(x+1)]; + oct[4] = state->map->map[LE * wh + (y+1)*w+(x+1)]; + oct[5] = state->map->map[RE * wh + (y+1)*w+x]; + oct[6] = state->map->map[TE * wh + (y+1)*w+x]; + oct[7] = state->map->map[BE * wh + y*w+x]; + + othercol = -1; + nchanges = 0; + for (i = 0; i < 8; i++) { + if (oct[i] != oct[0]) { + if (othercol < 0) + othercol = oct[i]; + else if (othercol != oct[i]) + break; /* three colours at this point */ + } + if (oct[i] != oct[(i+1) & 7]) + nchanges++; + } + + /* + * Now if there are exactly two regions at + * this point (not one, and not three or + * more), and only two changes around the + * loop, then this is a valid place to put + * an error marker. + */ + if (i == 8 && othercol >= 0 && nchanges == 2) { + ea[en] = oct[0]; + eb[en] = othercol; + ex[en] = (x+1)*2; + ey[en] = (y+1)*2; + en++; + } + } + + /* + * Now process the edges we've found, one by + * one. + */ + for (i = 0; i < en; i++) { + int emin = min(ea[i], eb[i]); + int emax = max(ea[i], eb[i]); + int gindex = + graph_edge_index(state->map->graph, n, + state->map->ngraph, emin, emax); + + assert(gindex >= 0); + + if (pass == 0) { + /* + * In pass 0, accumulate the values + * we'll use to compute the average + * positions. + */ + ax[gindex] += ex[i]; + ay[gindex] += ey[i]; + an[gindex] += 1.0F; + } else { + /* + * In pass 1, work out whether this + * point is closer to the average than + * the last one we've seen. + */ + float dx, dy, d; + + assert(an[gindex] > 0); + dx = ex[i] - ax[gindex]; + dy = ey[i] - ay[gindex]; + d = sqrt(dx*dx + dy*dy); + if (d < best[gindex]) { + best[gindex] = d; + bestx[gindex] = ex[i]; + besty[gindex] = ey[i]; + } + } + } + } + + if (pass == 0) { + for (i = 0; i < state->map->ngraph; i++) + if (an[i] > 0) { + ax[i] /= an[i]; + ay[i] /= an[i]; + } + } + } + + state->map->edgex = bestx; + state->map->edgey = besty; + + for (i = 0; i < state->map->ngraph; i++) + if (state->map->edgex[i] < 0) { + /* Find the other representation of this edge. */ + int e = state->map->graph[i]; + int iprime = graph_edge_index(state->map->graph, n, + state->map->ngraph, e%n, e/n); + assert(state->map->edgex[iprime] >= 0); + state->map->edgex[i] = state->map->edgex[iprime]; + state->map->edgey[i] = state->map->edgey[iprime]; + } + + sfree(ax); + sfree(ay); + sfree(an); + sfree(best); + } + return state; } @@ -1525,6 +1815,8 @@ static void free_game(game_state *state) sfree(state->map->map); sfree(state->map->graph); sfree(state->map->immutable); + sfree(state->map->edgex); + sfree(state->map->edgey); sfree(state->map); } sfree(state->colouring); @@ -1562,8 +1854,10 @@ static char *solve_game(game_state *state, game_state *currstate, return NULL; } - retlen = retsize = 0; - ret = NULL; + retsize = 64; + ret = snewn(retsize, char); + strcpy(ret, "S"); + retlen = 1; for (i = 0; i < state->map->n; i++) { int len; @@ -1573,8 +1867,7 @@ static char *solve_game(game_state *state, game_state *currstate, continue; assert(!state->map->immutable[i]); - len = sprintf(buf, "%s%d:%d", retlen ? ";" : "S;", - colouring[i], i); + len = sprintf(buf, ";%d:%d", colouring[i], i); if (retlen + len >= retsize) { retsize = retlen + len + 256; ret = sresize(ret, retsize, char); @@ -1629,12 +1922,16 @@ static void game_changed_state(game_ui *ui, game_state *oldstate, struct game_drawstate { int tilesize; - unsigned char *drawn; + unsigned short *drawn, *todraw; int started; int dragx, dragy, drag_visible; blitter *bl; }; +/* Flags in `drawn'. */ +#define ERR_BASE 0x0080 +#define ERR_MASK 0xFF80 + #define TILESIZE (ds->tilesize) #define BORDER (TILESIZE) #define COORD(x) ( (x) * TILESIZE + BORDER ) @@ -1703,7 +2000,7 @@ static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds, if (state->colouring[r] == c) return ""; /* don't _need_ to change this region */ - sprintf(buf, "%c:%d", (c < 0 ? 'C' : '0' + c), r); + sprintf(buf, "%c:%d", (int)(c < 0 ? 'C' : '0' + c), r); return dupstr(buf); } @@ -1784,16 +2081,26 @@ static void game_compute_size(game_params *params, int tilesize, *y = params->h * TILESIZE + 2 * BORDER + 1; } -static void game_set_size(game_drawstate *ds, game_params *params, - int tilesize) +static void game_set_size(drawing *dr, game_drawstate *ds, + game_params *params, int tilesize) { ds->tilesize = tilesize; if (ds->bl) - blitter_free(ds->bl); - ds->bl = blitter_new(TILESIZE+3, TILESIZE+3); + blitter_free(dr, ds->bl); + ds->bl = blitter_new(dr, TILESIZE+3, TILESIZE+3); } +const float map_colours[FOUR][3] = { + {0.7F, 0.5F, 0.4F}, + {0.8F, 0.7F, 0.4F}, + {0.5F, 0.6F, 0.4F}, + {0.55F, 0.45F, 0.35F}, +}; +const int map_hatching[FOUR] = { + HATCH_VERT, HATCH_SLASH, HATCH_HORIZ, HATCH_BACKSLASH +}; + static float *game_colours(frontend *fe, game_state *state, int *ncolours) { float *ret = snewn(3 * NCOLOURS, float); @@ -1804,33 +2111,33 @@ static float *game_colours(frontend *fe, game_state *state, int *ncolours) ret[COL_GRID * 3 + 1] = 0.0F; ret[COL_GRID * 3 + 2] = 0.0F; - ret[COL_0 * 3 + 0] = 0.7F; - ret[COL_0 * 3 + 1] = 0.5F; - ret[COL_0 * 3 + 2] = 0.4F; - - ret[COL_1 * 3 + 0] = 0.8F; - ret[COL_1 * 3 + 1] = 0.7F; - ret[COL_1 * 3 + 2] = 0.4F; + memcpy(ret + COL_0 * 3, map_colours[0], 3 * sizeof(float)); + memcpy(ret + COL_1 * 3, map_colours[1], 3 * sizeof(float)); + memcpy(ret + COL_2 * 3, map_colours[2], 3 * sizeof(float)); + memcpy(ret + COL_3 * 3, map_colours[3], 3 * sizeof(float)); - ret[COL_2 * 3 + 0] = 0.5F; - ret[COL_2 * 3 + 1] = 0.6F; - ret[COL_2 * 3 + 2] = 0.4F; + ret[COL_ERROR * 3 + 0] = 1.0F; + ret[COL_ERROR * 3 + 1] = 0.0F; + ret[COL_ERROR * 3 + 2] = 0.0F; - ret[COL_3 * 3 + 0] = 0.55F; - ret[COL_3 * 3 + 1] = 0.45F; - ret[COL_3 * 3 + 2] = 0.35F; + ret[COL_ERRTEXT * 3 + 0] = 1.0F; + ret[COL_ERRTEXT * 3 + 1] = 1.0F; + ret[COL_ERRTEXT * 3 + 2] = 1.0F; *ncolours = NCOLOURS; return ret; } -static game_drawstate *game_new_drawstate(game_state *state) +static game_drawstate *game_new_drawstate(drawing *dr, game_state *state) { struct game_drawstate *ds = snew(struct game_drawstate); + int i; ds->tilesize = 0; - ds->drawn = snewn(state->p.w * state->p.h, unsigned char); - memset(ds->drawn, 0xFF, state->p.w * state->p.h); + ds->drawn = snewn(state->p.w * state->p.h, unsigned short); + for (i = 0; i < state->p.w * state->p.h; i++) + ds->drawn[i] = 0xFFFF; + ds->todraw = snewn(state->p.w * state->p.h, unsigned short); ds->started = FALSE; ds->bl = NULL; ds->drag_visible = FALSE; @@ -1839,26 +2146,64 @@ static game_drawstate *game_new_drawstate(game_state *state) return ds; } -static void game_free_drawstate(game_drawstate *ds) +static void game_free_drawstate(drawing *dr, game_drawstate *ds) { + sfree(ds->drawn); + sfree(ds->todraw); if (ds->bl) - blitter_free(ds->bl); + blitter_free(dr, ds->bl); sfree(ds); } -static void draw_square(frontend *fe, game_drawstate *ds, +static void draw_error(drawing *dr, game_drawstate *ds, int x, int y) +{ + int coords[8]; + int yext, xext; + + /* + * Draw a diamond. + */ + coords[0] = x - TILESIZE*2/5; + coords[1] = y; + coords[2] = x; + coords[3] = y - TILESIZE*2/5; + coords[4] = x + TILESIZE*2/5; + coords[5] = y; + coords[6] = x; + coords[7] = y + TILESIZE*2/5; + draw_polygon(dr, coords, 4, COL_ERROR, COL_GRID); + + /* + * Draw an exclamation mark in the diamond. This turns out to + * look unpleasantly off-centre if done via draw_text, so I do + * it by hand on the basis that exclamation marks aren't that + * difficult to draw... + */ + xext = TILESIZE/16; + yext = TILESIZE*2/5 - (xext*2+2); + draw_rect(dr, x-xext, y-yext, xext*2+1, yext*2+1 - (xext*3), + COL_ERRTEXT); + draw_rect(dr, x-xext, y+yext-xext*2+1, xext*2+1, xext*2, COL_ERRTEXT); +} + +static void draw_square(drawing *dr, game_drawstate *ds, game_params *params, struct map *map, int x, int y, int v) { int w = params->w, h = params->h, wh = w*h; - int tv = v / FIVE, bv = v % FIVE; + int tv, bv, xo, yo, errs; - clip(fe, COORD(x), COORD(y), TILESIZE, TILESIZE); + errs = v & ERR_MASK; + v &= ~ERR_MASK; + tv = v / FIVE; + bv = v % FIVE; + + clip(dr, COORD(x), COORD(y), TILESIZE, TILESIZE); /* * Draw the region colour. */ - draw_rect(fe, COORD(x), COORD(y), TILESIZE, TILESIZE, + draw_rect(dr, COORD(x), COORD(y), TILESIZE, TILESIZE, (tv == FOUR ? COL_BACKGROUND : COL_0 + tv)); /* * Draw the second region colour, if this is a diagonally @@ -1875,7 +2220,7 @@ static void draw_square(frontend *fe, game_drawstate *ds, coords[3] = COORD(y)-1; coords[4] = COORD(x+1)+1; coords[5] = COORD(y+1)+1; - draw_polygon(fe, coords, 3, + draw_polygon(dr, coords, 3, (bv == FOUR ? COL_BACKGROUND : COL_0 + bv), COL_GRID); } @@ -1883,29 +2228,40 @@ static void draw_square(frontend *fe, game_drawstate *ds, * Draw the grid lines, if required. */ if (x <= 0 || map->map[RE*wh+y*w+(x-1)] != map->map[LE*wh+y*w+x]) - draw_rect(fe, COORD(x), COORD(y), 1, TILESIZE, COL_GRID); + draw_rect(dr, COORD(x), COORD(y), 1, TILESIZE, COL_GRID); if (y <= 0 || map->map[BE*wh+(y-1)*w+x] != map->map[TE*wh+y*w+x]) - draw_rect(fe, COORD(x), COORD(y), TILESIZE, 1, COL_GRID); + draw_rect(dr, COORD(x), COORD(y), TILESIZE, 1, COL_GRID); if (x <= 0 || y <= 0 || map->map[RE*wh+(y-1)*w+(x-1)] != map->map[TE*wh+y*w+x] || map->map[BE*wh+(y-1)*w+(x-1)] != map->map[LE*wh+y*w+x]) - draw_rect(fe, COORD(x), COORD(y), 1, 1, COL_GRID); + draw_rect(dr, COORD(x), COORD(y), 1, 1, COL_GRID); + + /* + * Draw error markers. + */ + for (yo = 0; yo < 3; yo++) + for (xo = 0; xo < 3; xo++) + if (errs & (ERR_BASE << (yo*3+xo))) + draw_error(dr, ds, + (COORD(x)*2+TILESIZE*xo)/2, + (COORD(y)*2+TILESIZE*yo)/2); + + unclip(dr); - unclip(fe); - draw_update(fe, COORD(x), COORD(y), TILESIZE, TILESIZE); + draw_update(dr, COORD(x), COORD(y), TILESIZE, TILESIZE); } -static void game_redraw(frontend *fe, game_drawstate *ds, game_state *oldstate, +static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate, game_state *state, int dir, game_ui *ui, float animtime, float flashtime) { - int w = state->p.w, h = state->p.h, wh = w*h /*, n = state->p.n */; - int x, y; + int w = state->p.w, h = state->p.h, wh = w*h, n = state->p.n; + int x, y, i; int flash; if (ds->drag_visible) { - blitter_load(fe, ds->bl, ds->dragx, ds->dragy); - draw_update(fe, ds->dragx, ds->dragy, TILESIZE + 3, TILESIZE + 3); + blitter_load(dr, ds->bl, ds->dragx, ds->dragy); + draw_update(dr, ds->dragx, ds->dragy, TILESIZE + 3, TILESIZE + 3); ds->drag_visible = FALSE; } @@ -1919,11 +2275,11 @@ static void game_redraw(frontend *fe, game_drawstate *ds, game_state *oldstate, int ww, wh; game_compute_size(&state->p, TILESIZE, &ww, &wh); - draw_rect(fe, 0, 0, ww, wh, COL_BACKGROUND); - draw_rect(fe, COORD(0), COORD(0), w*TILESIZE+1, h*TILESIZE+1, + draw_rect(dr, 0, 0, ww, wh, COL_BACKGROUND); + draw_rect(dr, COORD(0), COORD(0), w*TILESIZE+1, h*TILESIZE+1, COL_GRID); - draw_update(fe, 0, 0, ww, wh); + draw_update(dr, 0, 0, ww, wh); ds->started = TRUE; } @@ -1935,6 +2291,9 @@ static void game_redraw(frontend *fe, game_drawstate *ds, game_state *oldstate, } else flash = -1; + /* + * Set up the `todraw' array. + */ for (y = 0; y < h; y++) for (x = 0; x < w; x++) { int tv = state->colouring[state->map->map[TE * wh + y*w+x]]; @@ -1965,8 +2324,51 @@ static void game_redraw(frontend *fe, game_drawstate *ds, game_state *oldstate, v = tv * FIVE + bv; + ds->todraw[y*w+x] = v; + } + + /* + * Add error markers to the `todraw' array. + */ + for (i = 0; i < state->map->ngraph; i++) { + int v1 = state->map->graph[i] / n; + int v2 = state->map->graph[i] % n; + int xo, yo; + + if (state->colouring[v1] < 0 || state->colouring[v2] < 0) + continue; + if (state->colouring[v1] != state->colouring[v2]) + continue; + + x = state->map->edgex[i]; + y = state->map->edgey[i]; + + xo = x % 2; x /= 2; + yo = y % 2; y /= 2; + + ds->todraw[y*w+x] |= ERR_BASE << (yo*3+xo); + if (xo == 0) { + assert(x > 0); + ds->todraw[y*w+(x-1)] |= ERR_BASE << (yo*3+2); + } + if (yo == 0) { + assert(y > 0); + ds->todraw[(y-1)*w+x] |= ERR_BASE << (2*3+xo); + } + if (xo == 0 && yo == 0) { + assert(x > 0 && y > 0); + ds->todraw[(y-1)*w+(x-1)] |= ERR_BASE << (2*3+2); + } + } + + /* + * Now actually draw everything. + */ + for (y = 0; y < h; y++) + for (x = 0; x < w; x++) { + int v = ds->todraw[y*w+x]; if (ds->drawn[y*w+x] != v) { - draw_square(fe, ds, &state->p, state->map, x, y, v); + draw_square(dr, ds, &state->p, state->map, x, y, v); ds->drawn[y*w+x] = v; } } @@ -1977,11 +2379,11 @@ static void game_redraw(frontend *fe, game_drawstate *ds, game_state *oldstate, if (ui->drag_colour > -2) { ds->dragx = ui->dragx - TILESIZE/2 - 2; ds->dragy = ui->dragy - TILESIZE/2 - 2; - blitter_save(fe, ds->bl, ds->dragx, ds->dragy); - draw_circle(fe, ui->dragx, ui->dragy, TILESIZE/2, + blitter_save(dr, ds->bl, ds->dragx, ds->dragy); + draw_circle(dr, ui->dragx, ui->dragy, TILESIZE/2, (ui->drag_colour < 0 ? COL_BACKGROUND : COL_0 + ui->drag_colour), COL_GRID); - draw_update(fe, ds->dragx, ds->dragy, TILESIZE + 3, TILESIZE + 3); + draw_update(dr, ds->dragx, ds->dragy, TILESIZE + 3, TILESIZE + 3); ds->drag_visible = TRUE; } } @@ -2020,6 +2422,157 @@ static int game_timing_state(game_state *state, game_ui *ui) return TRUE; } +static void game_print_size(game_params *params, float *x, float *y) +{ + int pw, ph; + + /* + * I'll use 4mm squares by default, I think. Simplest way to + * compute this size is to compute the pixel puzzle size at a + * given tile size and then scale. + */ + game_compute_size(params, 400, &pw, &ph); + *x = pw / 100.0; + *y = ph / 100.0; +} + +static void game_print(drawing *dr, game_state *state, int tilesize) +{ + int w = state->p.w, h = state->p.h, wh = w*h, n = state->p.n; + int ink, c[FOUR], i; + int x, y, r; + int *coords, ncoords, coordsize; + + /* Ick: fake up `ds->tilesize' for macro expansion purposes */ + struct { int tilesize; } ads, *ds = &ads; + ads.tilesize = tilesize; + + ink = print_mono_colour(dr, 0); + for (i = 0; i < FOUR; i++) + c[i] = print_rgb_colour(dr, map_hatching[i], map_colours[i][0], + map_colours[i][1], map_colours[i][2]); + + coordsize = 0; + coords = NULL; + + print_line_width(dr, TILESIZE / 16); + + /* + * Draw a single filled polygon around each region. + */ + for (r = 0; r < n; r++) { + int octants[8], lastdir, d1, d2, ox, oy; + + /* + * Start by finding a point on the region boundary. Any + * point will do. To do this, we'll search for a square + * containing the region and then decide which corner of it + * to use. + */ + x = w; + for (y = 0; y < h; y++) { + for (x = 0; x < w; x++) { + if (state->map->map[wh*0+y*w+x] == r || + state->map->map[wh*1+y*w+x] == r || + state->map->map[wh*2+y*w+x] == r || + state->map->map[wh*3+y*w+x] == r) + break; + } + if (x < w) + break; + } + assert(y < h && x < w); /* we must have found one somewhere */ + /* + * This is the first square in lexicographic order which + * contains part of this region. Therefore, one of the top + * two corners of the square must be what we're after. The + * only case in which it isn't the top left one is if the + * square is diagonally divided and the region is in the + * bottom right half. + */ + if (state->map->map[wh*TE+y*w+x] != r && + state->map->map[wh*LE+y*w+x] != r) + x++; /* could just as well have done y++ */ + + /* + * Now we have a point on the region boundary. Trace around + * the region until we come back to this point, + * accumulating coordinates for a polygon draw operation as + * we go. + */ + lastdir = -1; + ox = x; + oy = y; + ncoords = 0; + + do { + /* + * There are eight possible directions we could head in + * from here. We identify them by octant numbers, and + * we also use octant numbers to identify the spaces + * between them: + * + * 6 7 0 + * \ 7|0 / + * \ | / + * 6 \|/ 1 + * 5-----+-----1 + * 5 /|\ 2 + * / | \ + * / 4|3 \ + * 4 3 2 + */ + octants[0] = x0 ? state->map->map[wh*LE+(y-1)*w+x] : -1; + octants[1] = x0 ? state->map->map[wh*BE+(y-1)*w+x] : -1; + octants[2] = xmap->map[wh*TE+y*w+x] : -1; + octants[3] = xmap->map[wh*LE+y*w+x] : -1; + octants[4] = x>0 && ymap->map[wh*RE+y*w+(x-1)] : -1; + octants[5] = x>0 && ymap->map[wh*TE+y*w+(x-1)] : -1; + octants[6] = x>0 && y>0 ? state->map->map[wh*BE+(y-1)*w+(x-1)] :-1; + octants[7] = x>0 && y>0 ? state->map->map[wh*RE+(y-1)*w+(x-1)] :-1; + + d1 = d2 = -1; + for (i = 0; i < 8; i++) + if ((octants[i] == r) ^ (octants[(i+1)%8] == r)) { + assert(d2 == -1); + if (d1 == -1) + d1 = i; + else + d2 = i; + } +/* printf("%% %d,%d r=%d: d1=%d d2=%d lastdir=%d\n", x, y, r, d1, d2, lastdir); */ + assert(d1 != -1 && d2 != -1); + if (d1 == lastdir) + d1 = d2; + + /* + * Now we're heading in direction d1. Save the current + * coordinates. + */ + if (ncoords + 2 > coordsize) { + coordsize += 128; + coords = sresize(coords, coordsize, int); + } + coords[ncoords++] = COORD(x); + coords[ncoords++] = COORD(y); + + /* + * Compute the new coordinates. + */ + x += (d1 % 4 == 3 ? 0 : d1 < 4 ? +1 : -1); + y += (d1 % 4 == 1 ? 0 : d1 > 1 && d1 < 5 ? +1 : -1); + assert(x >= 0 && x <= w && y >= 0 && y <= h); + + lastdir = d1 ^ 4; + } while (x != ox || y != oy); + + draw_polygon(dr, coords, ncoords/2, + state->colouring[r] >= 0 ? + c[state->colouring[r]] : -1, ink); + } + sfree(coords); +} + #ifdef COMBINED #define thegame map #endif @@ -2055,6 +2608,7 @@ const struct game thegame = { game_redraw, game_anim_length, game_flash_length, + TRUE, TRUE, game_print_size, game_print, game_wants_statusbar, FALSE, game_timing_state, 0, /* mouse_priorities */