X-Git-Url: http://www.chiark.greenend.org.uk/ucgi/~ian/git?a=blobdiff_plain;f=dominosa.c;h=c86ba19dfade335d9925fbef8ca1b354513e5037;hb=db313b3948d27244dd7c34c2609c66d6204d8931;hp=766ccfebdd839a5e8c41a70b6d0296bb8f3830d0;hpb=69410c7961e901b03ae694e80e39918e30e316c9;p=sgt-puzzles.git diff --git a/dominosa.c b/dominosa.c index 766ccfe..c86ba19 100644 --- a/dominosa.c +++ b/dominosa.c @@ -9,8 +9,34 @@ * * - improve solver so as to use more interesting forms of * deduction - * * odd area + * + * * rule out a domino placement if it would divide an unfilled + * region such that at least one resulting region had an odd + * area + * + use b.f.s. to determine the area of an unfilled region + * + a square is unfilled iff it has at least two possible + * placements, and two adjacent unfilled squares are part + * of the same region iff the domino placement joining + * them is possible + * * * perhaps set analysis + * + look at all unclaimed squares containing a given number + * + for each one, find the set of possible numbers that it + * can connect to (i.e. each neighbouring tile such that + * the placement between it and that neighbour has not yet + * been ruled out) + * + now proceed similarly to Solo set analysis: try to find + * a subset of the squares such that the union of their + * possible numbers is the same size as the subset. If so, + * rule out those possible numbers for all other squares. + * * important wrinkle: the double dominoes complicate + * matters. Connecting a number to itself uses up _two_ + * of the unclaimed squares containing a number. Thus, + * when finding the initial subset we must never + * include two adjacent squares; and also, when ruling + * things out after finding the subset, we must be + * careful that we don't rule out precisely the domino + * placement that was _included_ in our set! */ #include @@ -38,6 +64,8 @@ enum { COL_DOMINOCLASH, COL_DOMINOTEXT, COL_EDGE, + COL_HIGHLIGHT_1, + COL_HIGHLIGHT_2, NCOLOURS }; @@ -83,8 +111,12 @@ static int game_fetch_preset(int i, char **name, game_params **params) switch (i) { case 0: n = 3; break; - case 1: n = 6; break; - case 2: n = 9; break; + case 1: n = 4; break; + case 2: n = 5; break; + case 3: n = 6; break; + case 4: n = 7; break; + case 5: n = 8; break; + case 6: n = 9; break; default: return FALSE; } @@ -103,7 +135,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 */ @@ -118,7 +150,7 @@ static void decode_params(game_params *params, char const *string) params->unique = FALSE; } -static char *encode_params(game_params *params, int full) +static char *encode_params(const game_params *params, int full) { char buf[80]; sprintf(buf, "%d", params->n); @@ -127,7 +159,7 @@ static char *encode_params(game_params *params, int full) return dupstr(buf); } -static config_item *game_configure(game_params *params) +static config_item *game_configure(const game_params *params) { config_item *ret; char buf[80]; @@ -153,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); @@ -163,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) { if (params->n < 1) return "Maximum face number must be at least one"; @@ -515,12 +547,12 @@ static int solver(int w, int h, int n, int *grid, int *output) * End of solver code. */ -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) { int n = params->n, w = n+2, h = n+1, wh = w*h; int *grid, *grid2, *list; - int i, j, k, m, todo, done, len; + int i, j, k, len; char *ret; /* @@ -530,242 +562,37 @@ static char *new_game_desc(game_params *params, random_state *rs, grid2 = snewn(wh, int); list = snewn(2*wh, int); - do { - /* - * To begin with, set grid[i] = i for all i to indicate - * that all squares are currently singletons. Later we'll - * set grid[i] to be the index of the other end of the - * domino on i. - */ - for (i = 0; i < wh; i++) - grid[i] = i; - - /* - * Now prepare a list of the possible domino locations. There - * are w*(h-1) possible vertical locations, and (w-1)*h - * horizontal ones, for a total of 2*wh - h - w. - * - * I'm going to denote the vertical domino placement with - * its top in square i as 2*i, and the horizontal one with - * its left half in square i as 2*i+1. - */ - k = 0; - for (j = 0; j < h-1; j++) - for (i = 0; i < w; i++) - list[k++] = 2 * (j*w+i); /* vertical positions */ - for (j = 0; j < h; j++) - for (i = 0; i < w-1; i++) - list[k++] = 2 * (j*w+i) + 1; /* horizontal positions */ - assert(k == 2*wh - h - w); - - /* - * Shuffle the list. - */ - shuffle(list, k, sizeof(*list), rs); - - /* - * Work down the shuffled list, placing a domino everywhere - * we can. - */ - for (i = 0; i < k; i++) { - int horiz, xy, xy2; - - horiz = list[i] % 2; - xy = list[i] / 2; - xy2 = xy + (horiz ? 1 : w); - - if (grid[xy] == xy && grid[xy2] == xy2) { - /* - * We can place this domino. Do so. - */ - grid[xy] = xy2; - grid[xy2] = xy; - } - } - -#ifdef GENERATION_DIAGNOSTICS - printf("generated initial layout\n"); -#endif - - /* - * Now we've placed as many dominoes as we can immediately - * manage. There will be squares remaining, but they'll be - * singletons. So loop round and deal with the singletons - * two by two. - */ - while (1) { -#ifdef GENERATION_DIAGNOSTICS - for (j = 0; j < h; j++) { - for (i = 0; i < w; i++) { - int xy = j*w+i; - int v = grid[xy]; - int c = (v == xy+1 ? '[' : v == xy-1 ? ']' : - v == xy+w ? 'n' : v == xy-w ? 'U' : '.'); - putchar(c); - } - putchar('\n'); - } - putchar('\n'); -#endif - - /* - * Our strategy is: - * - * First find a singleton square. - * - * Then breadth-first search out from the starting - * square. From that square (and any others we reach on - * the way), examine all four neighbours of the square. - * If one is an end of a domino, we move to the _other_ - * end of that domino before looking at neighbours - * again. When we encounter another singleton on this - * search, stop. - * - * This will give us a path of adjacent squares such - * that all but the two ends are covered in dominoes. - * So we can now shuffle every domino on the path up by - * one. - * - * (Chessboard colours are mathematically important - * here: we always end up pairing each singleton with a - * singleton of the other colour. However, we never - * have to track this manually, since it's - * automatically taken care of by the fact that we - * always make an even number of orthogonal moves.) - */ - for (i = 0; i < wh; i++) - if (grid[i] == i) - break; - if (i == wh) - break; /* no more singletons; we're done. */ - -#ifdef GENERATION_DIAGNOSTICS - printf("starting b.f.s. at singleton %d\n", i); -#endif - /* - * Set grid2 to -1 everywhere. It will hold our - * distance-from-start values, and also our - * backtracking data, during the b.f.s. - */ - for (j = 0; j < wh; j++) - grid2[j] = -1; - grid2[i] = 0; /* starting square has distance zero */ - - /* - * Start our to-do list of squares. It'll live in - * `list'; since the b.f.s can cover every square at - * most once there is no need for it to be circular. - * We'll just have two counters tracking the end of the - * list and the squares we've already dealt with. - */ - done = 0; - todo = 1; - list[0] = i; - - /* - * Now begin the b.f.s. loop. - */ - while (done < todo) { - int d[4], nd, x, y; - - i = list[done++]; - -#ifdef GENERATION_DIAGNOSTICS - printf("b.f.s. iteration from %d\n", i); -#endif - x = i % w; - y = i / w; - nd = 0; - if (x > 0) - d[nd++] = i - 1; - if (x+1 < w) - d[nd++] = i + 1; - if (y > 0) - d[nd++] = i - w; - if (y+1 < h) - d[nd++] = i + w; - /* - * To avoid directional bias, process the - * neighbours of this square in a random order. - */ - shuffle(d, nd, sizeof(*d), rs); - - for (j = 0; j < nd; j++) { - k = d[j]; - if (grid[k] == k) { -#ifdef GENERATION_DIAGNOSTICS - printf("found neighbouring singleton %d\n", k); -#endif - grid2[k] = i; - break; /* found a target singleton! */ - } - - /* - * We're moving through a domino here, so we - * have two entries in grid2 to fill with - * useful data. In grid[k] - the square - * adjacent to where we came from - I'm going - * to put the address _of_ the square we came - * from. In the other end of the domino - the - * square from which we will continue the - * search - I'm going to put the distance. - */ - m = grid[k]; - - if (grid2[m] < 0 || grid2[m] > grid2[i]+1) { -#ifdef GENERATION_DIAGNOSTICS - printf("found neighbouring domino %d/%d\n", k, m); -#endif - grid2[m] = grid2[i]+1; - grid2[k] = i; - /* - * And since we've now visited a new - * domino, add m to the to-do list. - */ - assert(todo < wh); - list[todo++] = m; - } - } - - if (j < nd) { - i = k; -#ifdef GENERATION_DIAGNOSTICS - printf("terminating b.f.s. loop, i = %d\n", i); -#endif - break; - } - - i = -1; /* just in case the loop terminates */ - } - - /* - * We expect this b.f.s. to have found us a target - * square. - */ - assert(i >= 0); - - /* - * Now we can follow the trail back to our starting - * singleton, re-laying dominoes as we go. - */ - while (1) { - j = grid2[i]; - assert(j >= 0 && j < wh); - k = grid[j]; + /* + * I haven't been able to think of any particularly clever + * techniques for generating instances of Dominosa with a + * unique solution. Many of the deductions used in this puzzle + * are based on information involving half the grid at a time + * (`of all the 6s, exactly one is next to a 3'), so a strategy + * of partially solving the grid and then perturbing the place + * where the solver got stuck seems particularly likely to + * accidentally destroy the information which the solver had + * used in getting that far. (Contrast with, say, Mines, in + * which most deductions are local so this is an excellent + * strategy.) + * + * Therefore I resort to the basest of brute force methods: + * generate a random grid, see if it's solvable, throw it away + * and try again if not. My only concession to sophistication + * and cleverness is to at least _try_ not to generate obvious + * 2x2 ambiguous sections (see comment below in the domino- + * flipping section). + * + * During tests performed on 2005-07-15, I found that the brute + * force approach without that tweak had to throw away about 87 + * grids on average (at the default n=6) before finding a + * unique one, or a staggering 379 at n=9; good job the + * generator and solver are fast! When I added the + * ambiguous-section avoidance, those numbers came down to 19 + * and 26 respectively, which is a lot more sensible. + */ - grid[i] = j; - grid[j] = i; -#ifdef GENERATION_DIAGNOSTICS - printf("filling in domino %d/%d (next %d)\n", i, j, k); -#endif - if (j == k) - break; /* we've reached the other singleton */ - i = k; - } -#ifdef GENERATION_DIAGNOSTICS - printf("fixup path completed\n"); -#endif - } + do { + domino_layout_prealloc(w, h, rs, grid, grid2, list); /* * Now we have a complete layout covering the whole @@ -783,7 +610,61 @@ static char *new_game_desc(game_params *params, random_state *rs, for (i = 0; i < wh; i++) if (grid[i] > i) { /* Optionally flip the domino round. */ - int flip = random_upto(rs, 2); + int flip = -1; + + if (params->unique) { + int t1, t2; + /* + * If we're after a unique solution, we can do + * something here to improve the chances. If + * we're placing a domino so that it forms a + * 2x2 rectangle with one we've already placed, + * and if that domino and this one share a + * number, we can try not to put them so that + * the identical numbers are diagonally + * separated, because that automatically causes + * non-uniqueness: + * + * +---+ +-+-+ + * |2 3| |2|3| + * +---+ -> | | | + * |4 2| |4|2| + * +---+ +-+-+ + */ + t1 = i; + t2 = grid[i]; + if (t2 == t1 + w) { /* this domino is vertical */ + if (t1 % w > 0 &&/* and not on the left hand edge */ + grid[t1-1] == t2-1 &&/* alongside one to left */ + (grid2[t1-1] == list[j] || /* and has a number */ + grid2[t1-1] == list[j+1] || /* in common */ + grid2[t2-1] == list[j] || + grid2[t2-1] == list[j+1])) { + if (grid2[t1-1] == list[j] || + grid2[t2-1] == list[j+1]) + flip = 0; + else + flip = 1; + } + } else { /* this domino is horizontal */ + if (t1 / w > 0 &&/* and not on the top edge */ + grid[t1-w] == t2-w &&/* alongside one above */ + (grid2[t1-w] == list[j] || /* and has a number */ + grid2[t1-w] == list[j+1] || /* in common */ + grid2[t2-w] == list[j] || + grid2[t2-w] == list[j+1])) { + if (grid2[t1-w] == list[j] || + grid2[t2-w] == list[j+1]) + flip = 0; + else + flip = 1; + } + } + } + + if (flip < 0) + flip = random_upto(rs, 2); + grid2[i] = list[j + flip]; grid2[grid[i]] = list[j + 1 - flip]; j += 2; @@ -867,7 +748,7 @@ static char *new_game_desc(game_params *params, random_state *rs, return ret; } -static char *validate_desc(game_params *params, char *desc) +static char *validate_desc(const game_params *params, const char *desc) { int n = params->n, w = n+2, h = n+1, wh = w*h; int *occurrences; @@ -918,7 +799,8 @@ static char *validate_desc(game_params *params, char *desc) return ret; } -static game_state *new_game(midend_data *me, game_params *params, char *desc) +static game_state *new_game(midend *me, const game_params *params, + const char *desc) { int n = params->n, w = n+2, h = n+1, wh = w*h; game_state *state = snew(game_state); @@ -961,7 +843,7 @@ static game_state *new_game(midend_data *me, game_params *params, char *desc) return state; } -static game_state *dup_game(game_state *state) +static game_state *dup_game(const game_state *state) { int n = state->params.n, w = n+2, h = n+1, wh = w*h; game_state *ret = snew(game_state); @@ -984,6 +866,7 @@ static game_state *dup_game(game_state *state) static void free_game(game_state *state) { sfree(state->grid); + sfree(state->edges); if (--state->numbers->refcount <= 0) { sfree(state->numbers->numbers); sfree(state->numbers); @@ -991,8 +874,8 @@ static void free_game(game_state *state) sfree(state); } -static char *solve_game(game_state *state, game_state *currstate, - char *aux, char **error) +static char *solve_game(const game_state *state, const game_state *currstate, + const char *aux, char **error) { int n = state->params.n, w = n+2, h = n+1, wh = w*h; int *placements; @@ -1045,7 +928,7 @@ static char *solve_game(game_state *state, game_state *currstate, int p2 = (i & 1) ? p1+1 : p1+w; extra = sprintf(buf, ";%c%d,%d", - v==-1 ? 'E' : 'D', p1, p2); + (int)(v==-1 ? 'E' : 'D'), p1, p2); if (retlen + extra + 1 >= retsize) { retsize = retlen + extra + 256; @@ -1061,32 +944,110 @@ static char *solve_game(game_state *state, game_state *currstate, return ret; } -static char *game_text_format(game_state *state) +static int game_can_format_as_text_now(const game_params *params) { - return NULL; + return params->n < 1000; } -static game_ui *new_ui(game_state *state) +static void draw_domino(char *board, int start, char corner, + int dshort, int nshort, char cshort, + int dlong, int nlong, char clong) { - return NULL; + int go_short = nshort*dshort, go_long = nlong*dlong, i; + + board[start] = corner; + board[start + go_short] = corner; + board[start + go_long] = corner; + board[start + go_short + go_long] = corner; + + for (i = 1; i < nshort; ++i) { + int j = start + i*dshort, k = start + i*dshort + go_long; + if (board[j] != corner) board[j] = cshort; + if (board[k] != corner) board[k] = cshort; + } + + for (i = 1; i < nlong; ++i) { + int j = start + i*dlong, k = start + i*dlong + go_short; + if (board[j] != corner) board[j] = clong; + if (board[k] != corner) board[k] = clong; + } +} + +static char *game_text_format(const game_state *state) +{ + int w = state->w, h = state->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); + + memset(board, ' ', len); + + 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, num = state->numbers->numbers[i]; + + if (num < 100) { + board[center] = '0' + num % 10; + if (num >= 10) board[center - 1] = '0' + num / 10; + } else { + board[center+1] = '0' + num % 10; + board[center] = '0' + num / 10 % 10; + board[center-1] = '0' + num / 100; + } + + if (state->edges[i] & EDGE_L) board[center - cw/2] = '|'; + if (state->edges[i] & EDGE_R) board[center + cw/2] = '|'; + if (state->edges[i] & EDGE_T) board[center - gw] = '-'; + if (state->edges[i] & EDGE_B) board[center + gw] = '-'; + + if (state->grid[i] == i) continue; /* no domino pairing */ + if (state->grid[i] < i) continue; /* already done */ + assert (state->grid[i] == i + 1 || state->grid[i] == i + w); + if (state->grid[i] == i + 1) + draw_domino(board, cell, '+', gw, ch, '|', +1, 2*cw, '-'); + else if (state->grid[i] == i + w) + draw_domino(board, cell, '+', +1, cw, '-', gw, 2*ch, '|'); + } + board[r*ch*gw + gw - 1] = '\n'; + board[r*ch*gw + gw + gw - 1] = '\n'; + } + board[len - 1] = '\n'; + board[len] = '\0'; + return board; +} + +struct game_ui { + int cur_x, cur_y, cur_visible, highlight_1, highlight_2; +}; + +static game_ui *new_ui(const game_state *state) +{ + game_ui *ui = snew(game_ui); + ui->cur_x = ui->cur_y = 0; + ui->cur_visible = 0; + ui->highlight_1 = ui->highlight_2 = -1; + return ui; } static void free_ui(game_ui *ui) { + sfree(ui); } -static char *encode_ui(game_ui *ui) +static char *encode_ui(const game_ui *ui) { return NULL; } -static void decode_ui(game_ui *ui, char *encoding) +static void decode_ui(game_ui *ui, const char *encoding) { } -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) { + if (!oldstate->completed && newstate->completed) + ui->cur_visible = 0; } #define PREFERRED_TILESIZE 32 @@ -1095,6 +1056,7 @@ static void game_changed_state(game_ui *ui, game_state *oldstate, #define DOMINO_GUTTER (TILESIZE / 16) #define DOMINO_RADIUS (TILESIZE / 8) #define DOMINO_COFFSET (DOMINO_GUTTER + DOMINO_RADIUS) +#define CURSOR_RADIUS (TILESIZE / 4) #define COORD(x) ( (x) * TILESIZE + BORDER ) #define FROMCOORD(x) ( ((x) - BORDER + TILESIZE) / TILESIZE - 1 ) @@ -1105,8 +1067,9 @@ struct game_drawstate { unsigned long *visible; }; -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->w, h = state->h; char buf[80]; @@ -1148,14 +1111,54 @@ static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds, (state->grid[d1] != d1 || state->grid[d2] != d2)) return NULL; - sprintf(buf, "%c%d,%d", button == RIGHT_BUTTON ? 'E' : 'D', d1, d2); + ui->cur_visible = 0; + sprintf(buf, "%c%d,%d", (int)(button == RIGHT_BUTTON ? 'E' : 'D'), d1, d2); return dupstr(buf); + } else if (IS_CURSOR_MOVE(button)) { + ui->cur_visible = 1; + + move_cursor(button, &ui->cur_x, &ui->cur_y, 2*w-1, 2*h-1, 0); + + return ""; + } else if (IS_CURSOR_SELECT(button)) { + int d1, d2; + + if (!((ui->cur_x ^ ui->cur_y) & 1)) + return NULL; /* must have exactly one dimension odd */ + d1 = (ui->cur_y / 2) * w + (ui->cur_x / 2); + d2 = ((ui->cur_y+1) / 2) * w + ((ui->cur_x+1) / 2); + + /* + * We can't mark an edge next to any domino. + */ + if (button == CURSOR_SELECT2 && + (state->grid[d1] != d1 || state->grid[d2] != d2)) + return NULL; + + sprintf(buf, "%c%d,%d", (int)(button == CURSOR_SELECT2 ? 'E' : 'D'), d1, d2); + return dupstr(buf); + } else if (isdigit(button)) { + int n = state->params.n, num = button - '0'; + if (num > n) { + return NULL; + } else if (ui->highlight_1 == num) { + ui->highlight_1 = -1; + } else if (ui->highlight_2 == num) { + ui->highlight_2 = -1; + } else if (ui->highlight_1 == -1) { + ui->highlight_1 = num; + } else if (ui->highlight_2 == -1) { + ui->highlight_2 = num; + } else { + return NULL; + } + return ""; } return NULL; } -static game_state *execute_move(game_state *state, char *move) +static game_state *execute_move(const game_state *state, const char *move) { int n = state->params.n, w = n+2, h = n+1, wh = w*h; int d1, d2, d3, p; @@ -1310,8 +1313,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) { int n = params->n, w = n+2, h = n+1; @@ -1323,13 +1326,13 @@ static void game_compute_size(game_params *params, int tilesize, *y = h * TILESIZE + 2*BORDER; } -static void game_set_size(game_drawstate *ds, game_params *params, - int tilesize) +static void game_set_size(drawing *dr, game_drawstate *ds, + const game_params *params, int tilesize) { ds->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); @@ -1351,15 +1354,23 @@ static float *game_colours(frontend *fe, game_state *state, int *ncolours) ret[COL_DOMINOTEXT * 3 + 1] = 1.0F; ret[COL_DOMINOTEXT * 3 + 2] = 1.0F; - ret[COL_EDGE * 3 + 0] = ret[COL_BACKGROUND * 3 + 0] * 2 / 3; + ret[COL_EDGE * 3 + 0] = ret[COL_BACKGROUND * 3 + 0] * 2 / 3; ret[COL_EDGE * 3 + 1] = ret[COL_BACKGROUND * 3 + 1] * 2 / 3; ret[COL_EDGE * 3 + 2] = ret[COL_BACKGROUND * 3 + 2] * 2 / 3; + ret[COL_HIGHLIGHT_1 * 3 + 0] = 0.85; + ret[COL_HIGHLIGHT_1 * 3 + 1] = 0.20; + ret[COL_HIGHLIGHT_1 * 3 + 2] = 0.20; + + ret[COL_HIGHLIGHT_2 * 3 + 0] = 0.30; + ret[COL_HIGHLIGHT_2 * 3 + 1] = 0.85; + ret[COL_HIGHLIGHT_2 * 3 + 2] = 0.20; + *ncolours = NCOLOURS; return ret; } -static game_drawstate *game_new_drawstate(game_state *state) +static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state) { struct game_drawstate *ds = snew(struct game_drawstate); int i; @@ -1375,7 +1386,7 @@ 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->visible); sfree(ds); @@ -1390,8 +1401,28 @@ enum { TYPE_MASK = 0x0F }; -static void draw_tile(frontend *fe, game_drawstate *ds, game_state *state, - int x, int y, int type) +/* These flags must be disjoint with: + * the above enum (TYPE_*) [0x000 -- 0x00F] + * EDGE_* [0x100 -- 0xF00] + * and must fit into an unsigned long (32 bits). + */ +#define DF_HIGHLIGHT_1 0x10 +#define DF_HIGHLIGHT_2 0x20 +#define DF_FLASH 0x40 +#define DF_CLASH 0x80 + +#define DF_CURSOR 0x01000 +#define DF_CURSOR_USEFUL 0x02000 +#define DF_CURSOR_XBASE 0x10000 +#define DF_CURSOR_XMASK 0x30000 +#define DF_CURSOR_YBASE 0x40000 +#define DF_CURSOR_YMASK 0xC0000 + +#define CEDGE_OFF (TILESIZE / 8) +#define IS_EMPTY(s,x,y) ((s)->grid[(y)*(s)->w+(x)] == ((y)*(s)->w+(x))) + +static void draw_tile(drawing *dr, game_drawstate *ds, const game_state *state, + int x, int y, int type, int highlight_1, int highlight_2) { int w = state->w /*, h = state->h */; int cx = COORD(x), cy = COORD(y); @@ -1399,7 +1430,8 @@ static void draw_tile(frontend *fe, game_drawstate *ds, game_state *state, char str[80]; int flags; - draw_rect(fe, cx, cy, TILESIZE, TILESIZE, COL_BACKGROUND); + clip(dr, cx, cy, TILESIZE, TILESIZE); + draw_rect(dr, cx, cy, TILESIZE, TILESIZE, COL_BACKGROUND); flags = type &~ TYPE_MASK; type &= TYPE_MASK; @@ -1415,29 +1447,29 @@ static void draw_tile(frontend *fe, game_drawstate *ds, game_state *state, * - a slight shift in the number */ - if (flags & 0x80) + if (flags & DF_CLASH) bg = COL_DOMINOCLASH; else bg = COL_DOMINO; nc = COL_DOMINOTEXT; - if (flags & 0x40) { + if (flags & DF_FLASH) { int tmp = nc; nc = bg; bg = tmp; } if (type == TYPE_L || type == TYPE_T) - draw_circle(fe, cx+DOMINO_COFFSET, cy+DOMINO_COFFSET, + draw_circle(dr, cx+DOMINO_COFFSET, cy+DOMINO_COFFSET, DOMINO_RADIUS, bg, bg); if (type == TYPE_R || type == TYPE_T) - draw_circle(fe, cx+TILESIZE-1-DOMINO_COFFSET, cy+DOMINO_COFFSET, + draw_circle(dr, cx+TILESIZE-1-DOMINO_COFFSET, cy+DOMINO_COFFSET, DOMINO_RADIUS, bg, bg); if (type == TYPE_L || type == TYPE_B) - draw_circle(fe, cx+DOMINO_COFFSET, cy+TILESIZE-1-DOMINO_COFFSET, + draw_circle(dr, cx+DOMINO_COFFSET, cy+TILESIZE-1-DOMINO_COFFSET, DOMINO_RADIUS, bg, bg); if (type == TYPE_R || type == TYPE_B) - draw_circle(fe, cx+TILESIZE-1-DOMINO_COFFSET, + draw_circle(dr, cx+TILESIZE-1-DOMINO_COFFSET, cy+TILESIZE-1-DOMINO_COFFSET, DOMINO_RADIUS, bg, bg); @@ -1449,42 +1481,61 @@ static void draw_tile(frontend *fe, game_drawstate *ds, game_state *state, x2 = cx + TILESIZE-1 - (i ? DOMINO_GUTTER : DOMINO_COFFSET); y2 = cy + TILESIZE-1 - (i ? DOMINO_COFFSET : DOMINO_GUTTER); if (type == TYPE_L) - x2 = cx + TILESIZE-1; + x2 = cx + TILESIZE + TILESIZE/16; else if (type == TYPE_R) - x1 = cx; + x1 = cx - TILESIZE/16; else if (type == TYPE_T) - y2 = cy + TILESIZE-1; + y2 = cy + TILESIZE + TILESIZE/16; else if (type == TYPE_B) - y1 = cy; + y1 = cy - TILESIZE/16; - draw_rect(fe, x1, y1, x2-x1+1, y2-y1+1, bg); + draw_rect(dr, x1, y1, x2-x1+1, y2-y1+1, bg); } } else { if (flags & EDGE_T) - draw_rect(fe, cx+DOMINO_GUTTER, cy, + draw_rect(dr, cx+DOMINO_GUTTER, cy, TILESIZE-2*DOMINO_GUTTER, 1, COL_EDGE); if (flags & EDGE_B) - draw_rect(fe, cx+DOMINO_GUTTER, cy+TILESIZE-1, + draw_rect(dr, cx+DOMINO_GUTTER, cy+TILESIZE-1, TILESIZE-2*DOMINO_GUTTER, 1, COL_EDGE); if (flags & EDGE_L) - draw_rect(fe, cx, cy+DOMINO_GUTTER, + draw_rect(dr, cx, cy+DOMINO_GUTTER, 1, TILESIZE-2*DOMINO_GUTTER, COL_EDGE); if (flags & EDGE_R) - draw_rect(fe, cx+TILESIZE-1, cy+DOMINO_GUTTER, + draw_rect(dr, cx+TILESIZE-1, cy+DOMINO_GUTTER, 1, TILESIZE-2*DOMINO_GUTTER, COL_EDGE); nc = COL_TEXT; } + if (flags & DF_CURSOR) { + int curx = ((flags & DF_CURSOR_XMASK) / DF_CURSOR_XBASE) & 3; + int cury = ((flags & DF_CURSOR_YMASK) / DF_CURSOR_YBASE) & 3; + int ox = cx + curx*TILESIZE/2; + int oy = cy + cury*TILESIZE/2; + + draw_rect_corners(dr, ox, oy, CURSOR_RADIUS, nc); + if (flags & DF_CURSOR_USEFUL) + draw_rect_corners(dr, ox, oy, CURSOR_RADIUS+1, nc); + } + + if (flags & DF_HIGHLIGHT_1) { + nc = COL_HIGHLIGHT_1; + } else if (flags & DF_HIGHLIGHT_2) { + nc = COL_HIGHLIGHT_2; + } + sprintf(str, "%d", state->numbers->numbers[y*w+x]); - draw_text(fe, cx+TILESIZE/2, cy+TILESIZE/2, FONT_VARIABLE, TILESIZE/2, + draw_text(dr, cx+TILESIZE/2, cy+TILESIZE/2, FONT_VARIABLE, TILESIZE/2, ALIGN_HCENTRE | ALIGN_VCENTRE, nc, str); - draw_update(fe, cx, cy, TILESIZE, TILESIZE); + draw_update(dr, cx, cy, TILESIZE, TILESIZE); + unclip(dr); } -static void game_redraw(frontend *fe, 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 n = state->params.n, w = state->w, h = state->h, wh = w*h; int x, y, i; @@ -1493,8 +1544,8 @@ static void game_redraw(frontend *fe, game_drawstate *ds, game_state *oldstate, if (!ds->started) { int pw, ph; game_compute_size(&state->params, TILESIZE, &pw, &ph); - draw_rect(fe, 0, 0, pw, ph, COL_BACKGROUND); - draw_update(fe, 0, 0, pw, ph); + draw_rect(dr, 0, 0, pw, ph, COL_BACKGROUND); + draw_update(dr, 0, 0, pw, ph); ds->started = TRUE; } @@ -1535,21 +1586,39 @@ static void game_redraw(frontend *fe, game_drawstate *ds, game_state *oldstate, else c = TYPE_BLANK; + n1 = state->numbers->numbers[n]; if (c != TYPE_BLANK) { - n1 = state->numbers->numbers[n]; n2 = state->numbers->numbers[state->grid[n]]; di = DINDEX(n1, n2); if (used[di] > 1) - c |= 0x80; /* highlight a clash */ + c |= DF_CLASH; /* highlight a clash */ } else { c |= state->edges[n]; } + if (n1 == ui->highlight_1) + c |= DF_HIGHLIGHT_1; + if (n1 == ui->highlight_2) + c |= DF_HIGHLIGHT_2; + if (flashtime != 0) - c |= 0x40; /* we're flashing */ + c |= DF_FLASH; /* we're flashing */ + + if (ui->cur_visible) { + unsigned curx = (unsigned)(ui->cur_x - (2*x-1)); + unsigned cury = (unsigned)(ui->cur_y - (2*y-1)); + if (curx < 3 && cury < 3) { + c |= (DF_CURSOR | + (curx * DF_CURSOR_XBASE) | + (cury * DF_CURSOR_YBASE)); + if ((ui->cur_x ^ ui->cur_y) & 1) + c |= DF_CURSOR_USEFUL; + } + } if (ds->visible[n] != c) { - draw_tile(fe, ds, state, x, y, c); + draw_tile(dr, ds, state, x, y, c, + ui->highlight_1, ui->highlight_2); ds->visible[n] = c; } } @@ -1557,39 +1626,90 @@ static void game_redraw(frontend *fe, game_drawstate *ds, game_state *oldstate, sfree(used); } -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) { return 0.0F; } -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->completed && newstate->completed && !oldstate->cheated && !newstate->cheated) + { + ui->highlight_1 = ui->highlight_2 = -1; return FLASH_TIME; + } return 0.0F; } -static int game_wants_statusbar(void) +static int game_status(const game_state *state) { - return FALSE; + return state->completed ? +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(const game_params *params, float *x, float *y) +{ + int pw, ph; + + /* + * I'll use 6mm squares by default. + */ + game_compute_size(params, 600, &pw, &ph); + *x = pw / 100.0F; + *y = ph / 100.0F; +} + +static void game_print(drawing *dr, const game_state *state, int tilesize) +{ + int w = state->w, h = state->h; + int c, x, y; + + /* Ick: fake up `ds->tilesize' for macro expansion purposes */ + game_drawstate ads, *ds = &ads; + game_set_size(dr, ds, NULL, tilesize); + + c = print_mono_colour(dr, 1); assert(c == COL_BACKGROUND); + c = print_mono_colour(dr, 0); assert(c == COL_TEXT); + c = print_mono_colour(dr, 0); assert(c == COL_DOMINO); + c = print_mono_colour(dr, 0); assert(c == COL_DOMINOCLASH); + c = print_mono_colour(dr, 1); assert(c == COL_DOMINOTEXT); + c = print_mono_colour(dr, 0); assert(c == COL_EDGE); + + for (y = 0; y < h; y++) + for (x = 0; x < w; x++) { + int n = y*w+x; + unsigned long c; + + if (state->grid[n] == n-1) + c = TYPE_R; + else if (state->grid[n] == n+1) + c = TYPE_L; + else if (state->grid[n] == n-w) + c = TYPE_B; + else if (state->grid[n] == n+w) + c = TYPE_T; + else + c = TYPE_BLANK; + + draw_tile(dr, ds, state, x, y, c, -1, -1); + } +} + #ifdef COMBINED #define thegame dominosa #endif const struct game thegame = { - "Dominosa", "games.dominosa", + "Dominosa", "games.dominosa", "dominosa", default_params, - game_fetch_preset, + game_fetch_preset, NULL, decode_params, encode_params, free_params, @@ -1602,7 +1722,7 @@ const struct game thegame = { dup_game, free_game, TRUE, solve_game, - FALSE, game_text_format, + TRUE, game_can_format_as_text_now, game_text_format, new_ui, free_ui, encode_ui, @@ -1617,7 +1737,12 @@ const struct game thegame = { game_redraw, game_anim_length, game_flash_length, - game_wants_statusbar, + game_status, + TRUE, FALSE, game_print_size, game_print, + FALSE, /* wants_statusbar */ FALSE, game_timing_state, - 0, /* mouse_priorities */ + 0, /* flags */ }; + +/* vim: set shiftwidth=4 :set textwidth=80: */ +