X-Git-Url: http://www.chiark.greenend.org.uk/ucgi/~ian/git?a=blobdiff_plain;f=flood.c;fp=flood.c;h=42dc56ecf40b4d0dc58781fcce2748bf9bbe5d43;hb=201b32983b5cd1f904da3614ee9136cfeec59818;hp=0000000000000000000000000000000000000000;hpb=b2f8f5fb5731a14b68372d09153cd6f04d0b7f67;p=sgt-puzzles.git diff --git a/flood.c b/flood.c new file mode 100644 index 0000000..42dc56e --- /dev/null +++ b/flood.c @@ -0,0 +1,1266 @@ +/* + * flood.c: puzzle in which you make a grid all the same colour by + * repeatedly flood-filling the top left corner, and try to do so in + * as few moves as possible. + */ + +/* + * Possible further work: + * + * - UI: perhaps we should only permit clicking on regions that can + * actually be reached by the next flood-fill - i.e. a click is + * only interpreted as a move if it would cause the clicked-on + * square to become part of the controlled area. This provides a + * hint in cases where you mistakenly thought that would happen, + * and protects you against typos in cases where you just + * mis-aimed. + * + * - UI: perhaps mark the fill square in some way? Or even mark the + * whole connected component _containing_ the fill square. Pro: + * that would make it easier to tell apart cases where almost all + * the yellow squares in the grid are part of the target component + * (hence, yellow is _done_ and you never have to fill in that + * colour again) from cases where there's still one yellow square + * that's only diagonally adjacent and hence will need coming back + * to. Con: but it would almost certainly be ugly. + */ + +#include +#include +#include +#include +#include +#include + +#include "puzzles.h" + +enum { + COL_BACKGROUND, COL_SEPARATOR, + COL_1, COL_2, COL_3, COL_4, COL_5, COL_6, COL_7, COL_8, COL_9, COL_10, + COL_HIGHLIGHT, COL_LOWLIGHT, + NCOLOURS +}; + +struct game_params { + int w, h; + int colours; + int leniency; +}; + +/* Just in case I want to make this changeable later, I'll put the + * coordinates of the flood-fill point here so that it'll be easy to + * find everywhere later that has to change. */ +#define FILLX 0 +#define FILLY 0 + +typedef struct soln { + int refcount; + int nmoves; + char *moves; +} soln; + +struct game_state { + int w, h, colours; + int moves, movelimit; + int complete; + char *grid; + int cheated; + int solnpos; + soln *soln; +}; + +static game_params *default_params(void) +{ + game_params *ret = snew(game_params); + + ret->w = ret->h = 12; + ret->colours = 6; + ret->leniency = 5; + + return ret; +} + +static const struct game_params flood_presets[] = { + {12, 12, 6, 5}, + {12, 12, 6, 2}, + {12, 12, 6, 0}, + {16, 16, 6, 5}, + {16, 16, 6, 2}, + {16, 16, 6, 0}, +}; + +static int game_fetch_preset(int i, char **name, game_params **params) +{ + game_params *ret; + char str[80]; + + if (i < 0 || i >= lenof(flood_presets)) + return FALSE; + + ret = snew(game_params); + *ret = flood_presets[i]; + + sprintf(str, "%dx%d, %d colours, %d extra moves", + ret->w, ret->h, ret->colours, ret->leniency); + + *name = dupstr(str); + *params = ret; + return TRUE; +} + +static void free_params(game_params *params) +{ + sfree(params); +} + +static game_params *dup_params(const game_params *params) +{ + game_params *ret = snew(game_params); + *ret = *params; /* structure copy */ + return ret; +} + +static void decode_params(game_params *ret, char const *string) +{ + ret->w = ret->h = atoi(string); + while (*string && isdigit((unsigned char)*string)) string++; + if (*string == 'x') { + string++; + ret->h = atoi(string); + while (*string && isdigit((unsigned char)*string)) string++; + } + while (*string) { + if (*string == 'c') { + string++; + ret->colours = atoi(string); + while (string[1] && isdigit((unsigned char)string[1])) string++; + } else if (*string == 'm') { + string++; + ret->leniency = atoi(string); + while (string[1] && isdigit((unsigned char)string[1])) string++; + } + string++; + } +} + +static char *encode_params(const game_params *params, int full) +{ + char buf[256]; + sprintf(buf, "%dx%d", params->w, params->h); + if (full) + sprintf(buf + strlen(buf), "c%dm%d", + params->colours, params->leniency); + return dupstr(buf); +} + +static config_item *game_configure(const game_params *params) +{ + config_item *ret; + char buf[80]; + + ret = snewn(5, config_item); + + ret[0].name = "Width"; + ret[0].type = C_STRING; + sprintf(buf, "%d", params->w); + ret[0].sval = dupstr(buf); + ret[0].ival = 0; + + ret[1].name = "Height"; + ret[1].type = C_STRING; + sprintf(buf, "%d", params->h); + ret[1].sval = dupstr(buf); + ret[1].ival = 0; + + ret[2].name = "Colours"; + ret[2].type = C_STRING; + sprintf(buf, "%d", params->colours); + ret[2].sval = dupstr(buf); + ret[2].ival = 0; + + ret[3].name = "Extra moves permitted"; + ret[3].type = C_STRING; + sprintf(buf, "%d", params->leniency); + ret[3].sval = dupstr(buf); + ret[3].ival = 0; + + ret[4].name = NULL; + ret[4].type = C_END; + ret[4].sval = NULL; + ret[4].ival = 0; + + return ret; +} + +static game_params *custom_params(const config_item *cfg) +{ + game_params *ret = snew(game_params); + + ret->w = atoi(cfg[0].sval); + ret->h = atoi(cfg[1].sval); + ret->colours = atoi(cfg[2].sval); + ret->leniency = atoi(cfg[3].sval); + + return ret; +} + +static char *validate_params(const game_params *params, int full) +{ + if (params->w < 2 && params->h < 2) + return "Grid must contain at least two squares"; + if (params->colours < 3 || params->colours > 10) + return "Must have between 3 and 10 colours"; + if (params->leniency < 0) + return "Leniency must be non-negative"; + return NULL; +} + +struct solver_scratch { + int *queue[2]; + int *dist; + char *grid, *grid2, *sparegrid; +}; + +static struct solver_scratch *new_scratch(int w, int h) +{ + struct solver_scratch *scratch = snew(struct solver_scratch); + scratch->queue[0] = snewn(w*h, int); + scratch->queue[1] = snewn(w*h, int); + scratch->dist = snewn(w*h, int); + scratch->grid = snewn(w*h, char); + scratch->grid2 = snewn(w*h, char); + scratch->sparegrid = snewn(w*h, char); + return scratch; +} + +static void free_scratch(struct solver_scratch *scratch) +{ + sfree(scratch->queue[0]); + sfree(scratch->queue[1]); + sfree(scratch->dist); + sfree(scratch->grid); + sfree(scratch->grid2); + sfree(scratch->sparegrid); + sfree(scratch); +} + +#if 0 +/* Diagnostic routines you can uncomment if you need them */ +void dump_grid(int w, int h, const char *grid, const char *title) +{ + int x, y; + printf("%s:\n", title ? title : "Grid"); + for (y = 0; y < h; y++) { + printf(" "); + for (x = 0; x < w; x++) { + printf("%1x", grid[y*w+x]); + } + printf("\n"); + } +} + +void dump_dist(int w, int h, const int *dists, const char *title) +{ + int x, y; + printf("%s:\n", title ? title : "Distances"); + for (y = 0; y < h; y++) { + printf(" "); + for (x = 0; x < w; x++) { + printf("%3d", dists[y*w+x]); + } + printf("\n"); + } +} +#endif + +/* + * Search a grid to find the most distant square(s). Return their + * distance and the number of them. + */ +static void search(int w, int h, char *grid, int x0, int y0, + struct solver_scratch *scratch, int *rdist, int *rnumber) +{ + int wh = w*h; + int i, qcurr, qhead, qtail, qnext, currdist, remaining; + + for (i = 0; i < wh; i++) + scratch->dist[i] = -1; + scratch->queue[0][0] = y0*w+x0; + scratch->queue[1][0] = y0*w+x0; + scratch->dist[y0*w+x0] = 0; + currdist = 0; + qcurr = 0; + qtail = 0; + qhead = 1; + qnext = 1; + remaining = wh - 1; + + while (1) { + if (qtail == qhead) { + /* Switch queues. */ + currdist++; + qcurr ^= 1; /* switch queues */ + qhead = qnext; + qtail = 0; + qnext = 0; +#if 0 + printf("switch queue, new dist %d, queue %d\n", currdist, qhead); +#endif + } else if (remaining == 0 && qnext == 0) { + break; + } else { + int pos = scratch->queue[qcurr][qtail++]; + int y = pos / w; + int x = pos % w; +#if 0 + printf("checking neighbours of %d,%d\n", x, y); +#endif + int dir; + for (dir = 0; dir < 4; dir++) { + int y1 = y + (dir == 1 ? 1 : dir == 3 ? -1 : 0); + int x1 = x + (dir == 0 ? 1 : dir == 2 ? -1 : 0); + if (0 <= x1 && x1 < w && 0 <= y1 && y1 < h) { + int pos1 = y1*w+x1; +#if 0 + printf("trying %d,%d: colours %d-%d dist %d\n", x1, y1, + grid[pos], grid[pos1], scratch->dist[pos]); +#endif + if (scratch->dist[pos1] == -1 && + ((grid[pos1] == grid[pos] && + scratch->dist[pos] == currdist) || + (grid[pos1] != grid[pos] && + scratch->dist[pos] == currdist - 1))) { +#if 0 + printf("marking %d,%d dist %d\n", x1, y1, currdist); +#endif + scratch->queue[qcurr][qhead++] = pos1; + scratch->queue[qcurr^1][qnext++] = pos1; + scratch->dist[pos1] = currdist; + remaining--; + } + } + } + } + } + + *rdist = currdist; + *rnumber = qhead; +} + +/* + * Enact a flood-fill move on a grid. + */ +static void fill(int w, int h, char *grid, int x0, int y0, char newcolour, + int *queue) +{ + char oldcolour; + int qhead, qtail; + + oldcolour = grid[y0*w+x0]; + assert(oldcolour != newcolour); + grid[y0*w+x0] = newcolour; + queue[0] = y0*w+x0; + qtail = 0; + qhead = 1; + + while (qtail < qhead) { + int pos = queue[qtail++]; + int y = pos / w; + int x = pos % w; + int dir; + for (dir = 0; dir < 4; dir++) { + int y1 = y + (dir == 1 ? 1 : dir == 3 ? -1 : 0); + int x1 = x + (dir == 0 ? 1 : dir == 2 ? -1 : 0); + if (0 <= x1 && x1 < w && 0 <= y1 && y1 < h) { + int pos1 = y1*w+x1; + if (grid[pos1] == oldcolour) { + grid[pos1] = newcolour; + queue[qhead++] = pos1; + } + } + } + } +} + +/* + * Try out every possible move on a grid, and choose whichever one + * reduced the result of search() by the most. + */ +static char choosemove(int w, int h, char *grid, int x0, int y0, + int maxmove, struct solver_scratch *scratch) +{ + int wh = w*h; + char move, bestmove; + int dist, number, bestdist, bestnumber; + + bestdist = wh + 1; + bestnumber = 0; + bestmove = -1; + +#if 0 + dump_grid(w, h, grid, "before choosemove"); +#endif + for (move = 0; move < maxmove; move++) { + char buf[256]; + sprintf(buf, "after move %d", move); + if (grid[y0*w+x0] == move) + continue; + memcpy(scratch->sparegrid, grid, wh * sizeof(*grid)); + fill(w, h, scratch->sparegrid, x0, y0, move, scratch->queue[0]); +#if 0 + dump_grid(w, h, scratch->sparegrid, buf); +#endif + search(w, h, scratch->sparegrid, x0, y0, scratch, &dist, &number); +#if 0 + dump_dist(w, h, scratch->dist, buf); + printf("move %d: %d at %d\n", move, number, dist); +#endif + if (dist < bestdist || (dist == bestdist && number < bestnumber)) { + bestdist = dist; + bestnumber = number; + bestmove = move; + } + } +#if 0 + printf("best was %d\n", bestmove); +#endif + + return bestmove; +} + +/* + * Detect a completed grid. + */ +static int completed(int w, int h, char *grid) +{ + int wh = w*h; + int i; + + for (i = 1; i < wh; i++) + if (grid[i] != grid[0]) + return FALSE; + + return TRUE; +} + +static char *new_game_desc(const game_params *params, random_state *rs, + char **aux, int interactive) +{ + int w = params->w, h = params->h, wh = w*h; + int i, moves; + char *desc; + struct solver_scratch *scratch; + + scratch = new_scratch(w, h); + + /* + * Invent a random grid. + */ + for (i = 0; i < wh; i++) + scratch->grid[i] = random_upto(rs, params->colours); + + /* + * Run the solver, and count how many moves it uses. + */ + memcpy(scratch->grid2, scratch->grid, wh * sizeof(*scratch->grid2)); + moves = 0; + while (!completed(w, h, scratch->grid2)) { + char move = choosemove(w, h, scratch->grid2, FILLX, FILLY, + params->colours, scratch); + fill(w, h, scratch->grid2, FILLX, FILLY, move, scratch->queue[0]); + moves++; + } + + /* + * Adjust for difficulty. + */ + moves += params->leniency; + + /* + * Encode the game id. + */ + desc = snewn(wh + 40, char); + for (i = 0; i < wh; i++) { + char colour = scratch->grid[i]; + char textcolour = (colour > 9 ? 'A' : '0') + colour; + desc[i] = textcolour; + } + sprintf(desc+i, ",%d", moves); + + free_scratch(scratch); + + return desc; +} + +static char *validate_desc(const game_params *params, const char *desc) +{ + int w = params->w, h = params->h, wh = w*h; + int i; + for (i = 0; i < wh; i++) { + char c = *desc++; + if (c == 0) + return "Not enough data in grid description"; + if (c >= '0' && c <= '9') + c -= '0'; + else if (c >= 'A' && c <= 'Z') + c = 10 + (c - 'A'); + else + return "Bad character in grid description"; + if (c < 0 || c >= params->colours) + return "Colour out of range in grid description"; + } + if (*desc != ',') + return "Expected ',' after grid description"; + desc++; + if (desc[strspn(desc, "0123456789")]) + return "Badly formatted move limit after grid description"; + return NULL; +} + +static game_state *new_game(midend *me, const game_params *params, + const char *desc) +{ + int w = params->w, h = params->h, wh = w*h; + game_state *state = snew(game_state); + int i; + + state->w = w; + state->h = h; + state->colours = params->colours; + state->moves = 0; + state->grid = snewn(wh, char); + + for (i = 0; i < wh; i++) { + char c = *desc++; + assert(c); + if (c >= '0' && c <= '9') + c -= '0'; + else if (c >= 'A' && c <= 'Z') + c = 10 + (c - 'A'); + else + assert(!"bad colour"); + state->grid[i] = c; + } + assert(*desc == ','); + desc++; + + state->movelimit = atoi(desc); + state->complete = FALSE; + state->cheated = FALSE; + state->solnpos = 0; + state->soln = NULL; + + return state; +} + +static game_state *dup_game(const game_state *state) +{ + game_state *ret = snew(game_state); + + ret->w = state->w; + ret->h = state->h; + ret->colours = state->colours; + ret->moves = state->moves; + ret->movelimit = state->movelimit; + ret->complete = state->complete; + ret->grid = snewn(state->w * state->h, char); + memcpy(ret->grid, state->grid, state->w * state->h * sizeof(*ret->grid)); + + 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->moves); + sfree(state->soln); + } + sfree(state->grid); + sfree(state); +} + +static char *solve_game(const game_state *state, const game_state *currstate, + const char *aux, char **error) +{ + int w = state->w, h = state->h, wh = w*h; + char *moves, *ret, *p; + int i, len, nmoves; + char buf[256]; + struct solver_scratch *scratch; + + if (currstate->complete) + return NULL; + + /* + * Find the best solution our solver can give. + */ + moves = snewn(wh, char); /* sure to be enough */ + nmoves = 0; + scratch = new_scratch(w, h); + memcpy(scratch->grid2, currstate->grid, wh * sizeof(*scratch->grid2)); + while (!completed(w, h, scratch->grid2)) { + char move = choosemove(w, h, scratch->grid2, FILLX, FILLY, + currstate->colours, scratch); + fill(w, h, scratch->grid2, FILLX, FILLY, move, scratch->queue[0]); + assert(nmoves < wh); + moves[nmoves++] = move; + } + free_scratch(scratch); + + /* + * Encode it as a move string. + */ + len = 1; /* trailing NUL */ + for (i = 0; i < nmoves; i++) + len += sprintf(buf, ",%d", moves[i]); + ret = snewn(len, char); + p = ret; + for (i = 0; i < nmoves; i++) + p += sprintf(p, "%c%d", (i==0 ? 'S' : ','), moves[i]); + assert(p - ret == len - 1); + + sfree(moves); + return ret; +} + +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->w, h = state->h; + char *ret, *p; + int x, y, len; + + len = h * (w+1); /* +1 for newline after each row */ + ret = snewn(len+1, char); /* and +1 for terminating \0 */ + p = ret; + + for (y = 0; y < h; y++) { + for (x = 0; x < w; x++) { + char colour = state->grid[y*w+x]; + char textcolour = (colour > 9 ? 'A' : '0') + colour; + *p++ = textcolour; + } + *p++ = '\n'; + } + + assert(p - ret == len); + *p = '\0'; + + return ret; +} + +struct game_ui { + int cursor_visible; + int cx, cy; + enum { VICTORY, DEFEAT } flash_type; +}; + +static game_ui *new_ui(const game_state *state) +{ + struct game_ui *ui = snew(struct game_ui); + ui->cursor_visible = FALSE; + ui->cx = FILLX; + ui->cy = FILLY; + return ui; +} + +static void free_ui(game_ui *ui) +{ + sfree(ui); +} + +static char *encode_ui(const game_ui *ui) +{ + return NULL; +} + +static void decode_ui(game_ui *ui, const char *encoding) +{ +} + +static void game_changed_state(game_ui *ui, const game_state *oldstate, + const game_state *newstate) +{ +} + +struct game_drawstate { + int started; + int tilesize; + int *grid; +}; + +#define TILESIZE (ds->tilesize) +#define PREFERRED_TILESIZE 32 +#define BORDER (TILESIZE / 2) +#define SEP_WIDTH (TILESIZE / 32) +#define CURSOR_INSET (TILESIZE / 8) +#define HIGHLIGHT_WIDTH (TILESIZE / 10) +#define COORD(x) ( (x) * TILESIZE + BORDER ) +#define FROMCOORD(x) ( ((x) - BORDER + TILESIZE) / TILESIZE - 1 ) +#define VICTORY_FLASH_FRAME 0.03F +#define DEFEAT_FLASH_FRAME 0.10F + +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; + int tx = -1, ty = -1, move = -1; + + if (button == LEFT_BUTTON) { + tx = FROMCOORD(x); + ty = FROMCOORD(y); + ui->cursor_visible = FALSE; + } else if (button == CURSOR_LEFT && ui->cx > 0) { + ui->cx--; + ui->cursor_visible = TRUE; + return ""; + } else if (button == CURSOR_RIGHT && ui->cx+1 < w) { + ui->cx++; + ui->cursor_visible = TRUE; + return ""; + } else if (button == CURSOR_UP && ui->cy > 0) { + ui->cy--; + ui->cursor_visible = TRUE; + return ""; + } else if (button == CURSOR_DOWN && ui->cy+1 < h) { + ui->cy++; + ui->cursor_visible = TRUE; + return ""; + } else if (button == CURSOR_SELECT) { + tx = ui->cx; + ty = ui->cy; + } else if (button == CURSOR_SELECT2 && + state->soln && state->solnpos < state->soln->nmoves) { + move = state->soln->moves[state->solnpos]; + } else { + return NULL; + } + + if (tx >= 0 && tx < w && ty >= 0 && ty < h && + state->grid[0] != state->grid[ty*w+tx]) + move = state->grid[ty*w+tx]; + + if (move >= 0 && !state->complete) { + char buf[256]; + sprintf(buf, "M%d", move); + return dupstr(buf); + } + + return NULL; +} + +static game_state *execute_move(const game_state *state, const char *move) +{ + game_state *ret; + int c; + + if (move[0] == 'M' && + sscanf(move+1, "%d", &c) == 1 && + c >= 0 && + !state->complete) { + int *queue = snewn(state->w * state->h, int); + ret = dup_game(state); + fill(ret->w, ret->h, ret->grid, FILLX, FILLY, c, queue); + ret->moves++; + ret->complete = completed(ret->w, ret->h, ret->grid); + + if (ret->soln) { + /* + * If this move is the correct next one in the stored + * solution path, advance solnpos. + */ + if (c == ret->soln->moves[ret->solnpos] && + ret->solnpos+1 < ret->soln->nmoves) { + ret->solnpos++; + } else { + /* + * Otherwise, the user has strayed from the path or + * else the path has come to an end; either way, the + * path is no longer valid. + */ + ret->soln->refcount--; + assert(ret->soln->refcount > 0);/* `state' at least still exists */ + ret->soln = NULL; + ret->solnpos = 0; + } + } + + sfree(queue); + return ret; + } else if (*move == 'S') { + soln *sol; + const char *p; + int i; + + /* + * This is a solve move, so we don't actually _change_ the + * grid but merely set up a stored solution path. + */ + move++; + sol = snew(soln); + + sol->nmoves = 1; + for (p = move; *p; p++) { + if (*p == ',') + sol->nmoves++; + } + + sol->moves = snewn(sol->nmoves, char); + for (i = 0, p = move; i < sol->nmoves; i++) { + assert(*p); + sol->moves[i] = atoi(p); + p += strspn(p, "0123456789"); + if (*p) { + assert(*p == ','); + p++; + } + } + + ret = dup_game(state); + ret->cheated = TRUE; + if (ret->soln && --ret->soln->refcount == 0) { + sfree(ret->soln->moves); + sfree(ret->soln); + } + ret->soln = sol; + ret->solnpos = 0; + sol->refcount = 1; + return ret; + } + + return NULL; +} + +/* ---------------------------------------------------------------------- + * Drawing routines. + */ + +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; + ads.tilesize = tilesize; + + *x = BORDER * 2 + TILESIZE * params->w; + *y = BORDER * 2 + TILESIZE * params->h; +} + +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, int *ncolours) +{ + float *ret = snewn(3 * NCOLOURS, float); + + game_mkhighlight(fe, ret, COL_BACKGROUND, COL_HIGHLIGHT, COL_LOWLIGHT); + + ret[COL_SEPARATOR * 3 + 0] = 0.0F; + ret[COL_SEPARATOR * 3 + 1] = 0.0F; + ret[COL_SEPARATOR * 3 + 2] = 0.0F; + + /* red */ + ret[COL_1 * 3 + 0] = 1.0F; + ret[COL_1 * 3 + 1] = 0.0F; + ret[COL_1 * 3 + 2] = 0.0F; + + /* yellow */ + ret[COL_2 * 3 + 0] = 1.0F; + ret[COL_2 * 3 + 1] = 1.0F; + ret[COL_2 * 3 + 2] = 0.0F; + + /* green */ + ret[COL_3 * 3 + 0] = 0.0F; + ret[COL_3 * 3 + 1] = 1.0F; + ret[COL_3 * 3 + 2] = 0.0F; + + /* blue */ + ret[COL_4 * 3 + 0] = 0.2F; + ret[COL_4 * 3 + 1] = 0.3F; + ret[COL_4 * 3 + 2] = 1.0F; + + /* orange */ + ret[COL_5 * 3 + 0] = 1.0F; + ret[COL_5 * 3 + 1] = 0.5F; + ret[COL_5 * 3 + 2] = 0.0F; + + /* purple */ + ret[COL_6 * 3 + 0] = 0.5F; + ret[COL_6 * 3 + 1] = 0.0F; + ret[COL_6 * 3 + 2] = 0.7F; + + /* brown */ + ret[COL_7 * 3 + 0] = 0.5F; + ret[COL_7 * 3 + 1] = 0.3F; + ret[COL_7 * 3 + 2] = 0.3F; + + /* light blue */ + ret[COL_8 * 3 + 0] = 0.4F; + ret[COL_8 * 3 + 1] = 0.8F; + ret[COL_8 * 3 + 2] = 1.0F; + + /* light green */ + ret[COL_9 * 3 + 0] = 0.7F; + ret[COL_9 * 3 + 1] = 1.0F; + ret[COL_9 * 3 + 2] = 0.7F; + + /* pink */ + ret[COL_10 * 3 + 0] = 1.0F; + ret[COL_10 * 3 + 1] = 0.6F; + ret[COL_10 * 3 + 2] = 1.0F; + + *ncolours = NCOLOURS; + return ret; +} + +static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state) +{ + struct game_drawstate *ds = snew(struct game_drawstate); + int w = state->w, h = state->h, wh = w*h; + int i; + + ds->started = FALSE; + ds->tilesize = 0; + ds->grid = snewn(wh, int); + for (i = 0; i < wh; i++) + ds->grid[i] = -1; + + return ds; +} + +static void game_free_drawstate(drawing *dr, game_drawstate *ds) +{ + sfree(ds->grid); + sfree(ds); +} + +#define BORDER_L 0x001 +#define BORDER_R 0x002 +#define BORDER_U 0x004 +#define BORDER_D 0x008 +#define CORNER_UL 0x010 +#define CORNER_UR 0x020 +#define CORNER_DL 0x040 +#define CORNER_DR 0x080 +#define CURSOR 0x100 +#define BADFLASH 0x200 +#define SOLNNEXT 0x400 +#define COLOUR_SHIFT 11 + +static void draw_tile(drawing *dr, game_drawstate *ds, + int x, int y, int tile) +{ + int colour; + int tx = COORD(x), ty = COORD(y); + + colour = tile >> COLOUR_SHIFT; + if (tile & BADFLASH) + colour = COL_SEPARATOR; + else + colour += COL_1; + draw_rect(dr, tx, ty, TILESIZE, TILESIZE, colour); + + if (tile & BORDER_L) + draw_rect(dr, tx, ty, + SEP_WIDTH, TILESIZE, COL_SEPARATOR); + if (tile & BORDER_R) + draw_rect(dr, tx + TILESIZE - SEP_WIDTH, ty, + SEP_WIDTH, TILESIZE, COL_SEPARATOR); + if (tile & BORDER_U) + draw_rect(dr, tx, ty, + TILESIZE, SEP_WIDTH, COL_SEPARATOR); + if (tile & BORDER_D) + draw_rect(dr, tx, ty + TILESIZE - SEP_WIDTH, + TILESIZE, SEP_WIDTH, COL_SEPARATOR); + + if (tile & CORNER_UL) + draw_rect(dr, tx, ty, + SEP_WIDTH, SEP_WIDTH, COL_SEPARATOR); + if (tile & CORNER_UR) + draw_rect(dr, tx + TILESIZE - SEP_WIDTH, ty, + SEP_WIDTH, SEP_WIDTH, COL_SEPARATOR); + if (tile & CORNER_DL) + draw_rect(dr, tx, ty + TILESIZE - SEP_WIDTH, + SEP_WIDTH, SEP_WIDTH, COL_SEPARATOR); + if (tile & CORNER_DR) + draw_rect(dr, tx + TILESIZE - SEP_WIDTH, ty + TILESIZE - SEP_WIDTH, + SEP_WIDTH, SEP_WIDTH, COL_SEPARATOR); + + if (tile & CURSOR) + draw_rect_outline(dr, tx + CURSOR_INSET, ty + CURSOR_INSET, + TILESIZE - 1 - CURSOR_INSET * 2, + TILESIZE - 1 - CURSOR_INSET * 2, + COL_SEPARATOR); + + if (tile & SOLNNEXT) { + draw_circle(dr, tx + TILESIZE/2, ty + TILESIZE/2, TILESIZE/6, + COL_SEPARATOR, COL_SEPARATOR); + } + + draw_update(dr, tx, ty, TILESIZE, TILESIZE); +} + +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->w, h = state->h, wh = w*h; + int x, y, flashframe, solnmove; + char *grid; + + /* This was entirely cloned from fifteen.c; it should probably be + * moved into some generic 'draw-recessed-rectangle' utility fn. */ + if (!ds->started) { + int coords[10]; + + draw_rect(dr, 0, 0, + TILESIZE * w + 2 * BORDER, + TILESIZE * h + 2 * BORDER, COL_BACKGROUND); + draw_update(dr, 0, 0, + TILESIZE * w + 2 * BORDER, + TILESIZE * h + 2 * BORDER); + + /* + * Recessed area containing the whole puzzle. + */ + coords[0] = COORD(w) + HIGHLIGHT_WIDTH - 1; + coords[1] = COORD(h) + HIGHLIGHT_WIDTH - 1; + coords[2] = COORD(w) + HIGHLIGHT_WIDTH - 1; + coords[3] = COORD(0) - HIGHLIGHT_WIDTH; + coords[4] = coords[2] - TILESIZE; + coords[5] = coords[3] + TILESIZE; + coords[8] = COORD(0) - HIGHLIGHT_WIDTH; + coords[9] = COORD(h) + HIGHLIGHT_WIDTH - 1; + coords[6] = coords[8] + TILESIZE; + coords[7] = coords[9] - TILESIZE; + draw_polygon(dr, coords, 5, COL_HIGHLIGHT, COL_HIGHLIGHT); + + coords[1] = COORD(0) - HIGHLIGHT_WIDTH; + coords[0] = COORD(0) - HIGHLIGHT_WIDTH; + draw_polygon(dr, coords, 5, COL_LOWLIGHT, COL_LOWLIGHT); + + draw_rect(dr, COORD(0) - SEP_WIDTH, COORD(0) - SEP_WIDTH, + TILESIZE * w + 2 * SEP_WIDTH, TILESIZE * h + 2 * SEP_WIDTH, + COL_SEPARATOR); + + ds->started = 1; + } + + if (flashtime > 0) { + float frame = (ui->flash_type == VICTORY ? + VICTORY_FLASH_FRAME : DEFEAT_FLASH_FRAME); + flashframe = (int)(flashtime / frame); + } else { + flashframe = -1; + } + + grid = snewn(wh, char); + memcpy(grid, state->grid, wh * sizeof(*grid)); + + if (state->soln && state->solnpos < state->soln->nmoves) { + int i, *queue; + + /* + * Highlight as 'next auto-solver move' every square of the + * target colour which is adjacent to the currently controlled + * region. We do this by first enacting the actual move, then + * flood-filling again in a nonexistent colour, and finally + * reverting to the original grid anything in the new colour + * that was part of the original controlled region. Then + * regions coloured in the dummy colour should be displayed as + * soln_move with the SOLNNEXT flag. + */ + solnmove = state->soln->moves[state->solnpos]; + + queue = snewn(wh, int); + fill(w, h, grid, FILLX, FILLY, solnmove, queue); + fill(w, h, grid, FILLX, FILLY, state->colours, queue); + sfree(queue); + + for (i = 0; i < wh; i++) + if (grid[i] == state->colours && state->grid[i] != solnmove) + grid[i] = state->grid[i]; + } else { + solnmove = 0; /* placate optimiser */ + } + + if (flashframe >= 0 && ui->flash_type == VICTORY) { + /* + * Modify the display grid by superimposing our rainbow flash + * on it. + */ + for (x = 0; x < w; x++) { + for (y = 0; y < h; y++) { + int flashpos = flashframe - (abs(x - FILLX) + abs(y - FILLY)); + if (flashpos >= 0 && flashpos < state->colours) + grid[y*w+x] = flashpos; + } + } + } + + for (x = 0; x < w; x++) { + for (y = 0; y < h; y++) { + int pos = y*w+x; + int tile; + + if (grid[pos] == state->colours) { + tile = (solnmove << COLOUR_SHIFT) | SOLNNEXT; + } else { + tile = (int)grid[pos] << COLOUR_SHIFT; + } + + if (x == 0 || grid[pos-1] != grid[pos]) + tile |= BORDER_L; + if (x==w-1 || grid[pos+1] != grid[pos]) + tile |= BORDER_R; + if (y == 0 || grid[pos-w] != grid[pos]) + tile |= BORDER_U; + if (y==h-1 || grid[pos+w] != grid[pos]) + tile |= BORDER_D; + if (x == 0 || y == 0 || grid[pos-w-1] != grid[pos]) + tile |= CORNER_UL; + if (x==w-1 || y == 0 || grid[pos-w+1] != grid[pos]) + tile |= CORNER_UR; + if (x == 0 || y==h-1 || grid[pos+w-1] != grid[pos]) + tile |= CORNER_DL; + if (x==w-1 || y==h-1 || grid[pos+w+1] != grid[pos]) + tile |= CORNER_DR; + if (ui->cursor_visible && ui->cx == x && ui->cy == y) + tile |= CURSOR; + + if (flashframe >= 0 && ui->flash_type == DEFEAT && flashframe != 1) + tile |= BADFLASH; + + if (ds->grid[pos] != tile) { + draw_tile(dr, ds, x, y, tile); + ds->grid[pos] = tile; + } + } + } + + sfree(grid); + + { + char status[255]; + + sprintf(status, "%s%d / %d moves", + (state->complete && state->moves <= state->movelimit ? + (state->cheated ? "Auto-solved. " : "COMPLETED! ") : + state->moves >= state->movelimit ? "FAILED! " : + state->cheated ? "Auto-solver used. " : + ""), + state->moves, + state->movelimit); + + status_bar(dr, status); + } +} + +static float game_anim_length(const game_state *oldstate, + const game_state *newstate, int dir, game_ui *ui) +{ + return 0.0F; +} + +static int game_status(const game_state *state) +{ + if (state->complete && state->moves <= state->movelimit) { + return +1; /* victory! */ + } else if (state->moves >= state->movelimit) { + return -1; /* defeat */ + } else { + return 0; /* still playing */ + } +} + +static float game_flash_length(const game_state *oldstate, + const game_state *newstate, int dir, game_ui *ui) +{ + if (dir == +1) { + int old_status = game_status(oldstate); + int new_status = game_status(newstate); + if (old_status != new_status) { + assert(old_status == 0); + + if (new_status == +1) { + int frames = newstate->w + newstate->h + newstate->colours - 2; + ui->flash_type = VICTORY; + return VICTORY_FLASH_FRAME * frames; + } else { + ui->flash_type = DEFEAT; + return DEFEAT_FLASH_FRAME * 3; + } + } + } + return 0.0F; +} + +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) +{ +} + +static void game_print(drawing *dr, const game_state *state, int tilesize) +{ +} + +#ifdef COMBINED +#define thegame flood +#endif + +const struct game thegame = { + "Flood", "games.flood", "flood", + default_params, + game_fetch_preset, + decode_params, + encode_params, + free_params, + dup_params, + TRUE, game_configure, custom_params, + validate_params, + new_game_desc, + validate_desc, + new_game, + dup_game, + free_game, + TRUE, solve_game, + TRUE, game_can_format_as_text_now, game_text_format, + new_ui, + free_ui, + encode_ui, + decode_ui, + game_changed_state, + interpret_move, + execute_move, + PREFERRED_TILESIZE, game_compute_size, game_set_size, + game_colours, + game_new_drawstate, + game_free_drawstate, + game_redraw, + game_anim_length, + game_flash_length, + game_status, + FALSE, FALSE, game_print_size, game_print, + TRUE, /* wants_statusbar */ + FALSE, game_timing_state, + 0, /* flags */ +};