From 881746789a489fad85aae8317555f73dbe261556 Mon Sep 17 00:00:00 2001 From: Franklin Wei Date: Sat, 29 Apr 2017 18:21:56 -0400 Subject: puzzles: refactor and resync with upstream This brings puzzles up-to-date with upstream revision 2d333750272c3967cfd5cd3677572cddeaad5932, though certain changes made by me, including cursor-only Untangle and some compilation fixes remain. Upstream code has been moved to its separate subdirectory and future syncs can be done by simply copying over the new sources. Change-Id: Ia6506ca5f78c3627165ea6791d38db414ace0804 --- apps/plugins/puzzles/src/tracks.c | 2660 +++++++++++++++++++++++++++++++++++++ 1 file changed, 2660 insertions(+) create mode 100644 apps/plugins/puzzles/src/tracks.c (limited to 'apps/plugins/puzzles/src/tracks.c') diff --git a/apps/plugins/puzzles/src/tracks.c b/apps/plugins/puzzles/src/tracks.c new file mode 100644 index 0000000000..43428a19e9 --- /dev/null +++ b/apps/plugins/puzzles/src/tracks.c @@ -0,0 +1,2660 @@ +/* + * Implementation of 'Train Tracks', a puzzle from the Times on Saturday. + * + * "Lay tracks to enable the train to travel from village A to village B. + * The numbers indicate how many sections of rail go in each row and + * column. There are only straight rails and curved rails. The track + * cannot cross itself." + * + * Puzzles: + * #9 8x8:d9s5c6zgAa,1,4,1,4,4,3,S3,5,2,2,4,S5,3,3,5,1 + * #112 8x8:w6x5mAa,1,3,1,4,6,4,S4,3,3,4,5,2,4,2,S5,1 + * #113 8x8:gCx5xAf,1,S4,2,5,4,6,2,3,4,2,5,2,S4,4,5,1 + * #114 8x8:p5fAzkAb,1,6,3,3,3,S6,2,3,5,4,S3,3,5,1,5,1 + * #115 8x8:zi9d5tAb,1,3,4,5,3,S4,2,4,2,6,2,3,6,S3,3,1 + */ + +#include +#include +#include +#include +#include +#include + +#include "puzzles.h" + +/* --- Game parameters --- */ + +/* + * Difficulty levels. I do some macro ickery here to ensure that my + * enum and the various forms of my name list always match up. + */ +#define DIFFLIST(A) \ + A(EASY,Easy,e) \ + A(TRICKY,Tricky,t) + +#define ENUM(upper,title,lower) DIFF_ ## upper, +#define TITLE(upper,title,lower) #title, +#define ENCODE(upper,title,lower) #lower +#define CONFIG(upper,title,lower) ":" #title +enum { DIFFLIST(ENUM) DIFFCOUNT }; +static char const *const tracks_diffnames[] = { DIFFLIST(TITLE) }; +static char const tracks_diffchars[] = DIFFLIST(ENCODE); +#define DIFFCONFIG DIFFLIST(CONFIG) + +struct game_params { + int w, h, diff, single_ones; +}; + +static game_params *default_params(void) +{ + game_params *ret = snew(game_params); + + ret->w = ret->h = 8; + ret->diff = DIFF_TRICKY; + ret->single_ones = TRUE; + + return ret; +} + +static const struct game_params tracks_presets[] = { + {8, 8, DIFF_EASY, 1}, + {8, 8, DIFF_TRICKY, 1}, + {10, 8, DIFF_EASY, 1}, + {10, 8, DIFF_TRICKY, 1 }, + {10, 10, DIFF_EASY, 1}, + {10, 10, DIFF_TRICKY, 1}, + {15, 10, DIFF_EASY, 1}, + {15, 10, DIFF_TRICKY, 1}, + {15, 15, DIFF_EASY, 1}, + {15, 15, DIFF_TRICKY, 1}, +}; + +static int game_fetch_preset(int i, char **name, game_params **params) +{ + game_params *ret; + char str[80]; + + if (i < 0 || i >= lenof(tracks_presets)) + return FALSE; + + ret = snew(game_params); + *ret = tracks_presets[i]; + + sprintf(str, "%dx%d %s", ret->w, ret->h, tracks_diffnames[ret->diff]); + + *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 *params, char const *string) +{ + params->w = params->h = atoi(string); + while (*string && isdigit((unsigned char)*string)) string++; + if (*string == 'x') { + string++; + params->h = atoi(string); + while (*string && isdigit((unsigned char)*string)) string++; + } + if (*string == 'd') { + int i; + string++; + params->diff = DIFF_TRICKY; + for (i = 0; i < DIFFCOUNT; i++) + if (*string == tracks_diffchars[i]) + params->diff = i; + if (*string) string++; + } + params->single_ones = TRUE; + if (*string == 'o') { + params->single_ones = FALSE; + string++; + } + +} + +static char *encode_params(const game_params *params, int full) +{ + char buf[120]; + + sprintf(buf, "%dx%d", params->w, params->h); + if (full) + sprintf(buf + strlen(buf), "d%c%s", + tracks_diffchars[params->diff], + params->single_ones ? "" : "o"); + 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 = "Difficulty"; + ret[2].type = C_CHOICES; + ret[2].sval = DIFFCONFIG; + ret[2].ival = params->diff; + + ret[3].name = "Disallow consecutive 1 clues"; + ret[3].type = C_BOOLEAN; + ret[3].ival = params->single_ones; + + 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->diff = cfg[2].ival; + ret->single_ones = cfg[3].ival; + + return ret; +} + +static char *validate_params(const game_params *params, int full) +{ + /* + * Generating anything under 4x4 runs into trouble of one kind + * or another. + */ + if (params->w < 4 || params->h < 4) + return "Width and height must both be at least four"; + return NULL; +} + +/* --- Game state --- */ + +/* flag usage copied from pearl */ + +#define R 1 +#define U 2 +#define L 4 +#define D 8 + +#define MOVECHAR(m) ((m==R)?'R':(m==U)?'U':(m==L)?'L':(m==D)?'D':'?') + +#define DX(d) ( ((d)==R) - ((d)==L) ) +#define DY(d) ( ((d)==D) - ((d)==U) ) + +#define F(d) (((d << 2) | (d >> 2)) & 0xF) +#define C(d) (((d << 3) | (d >> 1)) & 0xF) +#define A(d) (((d << 1) | (d >> 3)) & 0xF) + +#define LR (L | R) +#define RL (R | L) +#define UD (U | D) +#define DU (D | U) +#define LU (L | U) +#define UL (U | L) +#define LD (L | D) +#define DL (D | L) +#define RU (R | U) +#define UR (U | R) +#define RD (R | D) +#define DR (D | R) +#define ALLDIR 15 +#define BLANK 0 +#define UNKNOWN 15 + +int nbits[] = { 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4 }; + +/* square grid flags */ +#define S_TRACK 1 /* a track passes through this square (--> 2 edges) */ +#define S_NOTRACK 2 /* no track passes through this square */ +#define S_ERROR 4 +#define S_CLUE 8 +#define S_MARK 16 + +#define S_TRACK_SHIFT 16 /* U/D/L/R flags for edge track indicators */ +#define S_NOTRACK_SHIFT 20 /* U/D/L/R flags for edge no-track indicators */ + +/* edge grid flags */ +#define E_TRACK 1 /* a track passes through this edge */ +#define E_NOTRACK 2 /* no track passes through this edge */ + +struct numbers { + int refcount; + int *numbers; /* sz w+h */ + int row_s, col_s; /* stations: TODO think about multiple lines + (for bigger grids)? */ +}; + +#define INGRID(state, gx, gy) ((gx) >= 0 && (gx) < (state)->p.w && \ + (gy) >= 0 && (gy) < (state)->p.h) + +struct game_state { + game_params p; + unsigned int *sflags; /* size w*h */ + struct numbers *numbers; + int *num_errors; /* size w+h */ + int completed, used_solve, impossible; +}; + +/* Return the four directions in which a particular edge flag is set, around a square. */ +int S_E_DIRS(const game_state *state, int sx, int sy, unsigned int eflag) { + return (state->sflags[sy*state->p.w+sx] >> + ((eflag == E_TRACK) ? S_TRACK_SHIFT : S_NOTRACK_SHIFT)) & ALLDIR; +} + +/* Count the number of a particular edge flag around a grid square. */ +int S_E_COUNT(const game_state *state, int sx, int sy, unsigned int eflag) { + return nbits[S_E_DIRS(state, sx, sy, eflag)]; +} + +/* Return the two flags (E_TRACK and/or E_NOTRACK) set on a specific + * edge of a square. */ +unsigned S_E_FLAGS(const game_state *state, int sx, int sy, int d) { + unsigned f = state->sflags[sy*state->p.w+sx]; + int t = (f & (d << S_TRACK_SHIFT)), nt = (f & (d << S_NOTRACK_SHIFT)); + return (t ? E_TRACK : 0) | (nt ? E_NOTRACK : 0); +} + +int S_E_ADJ(const game_state *state, int sx, int sy, int d, int *ax, int *ay, unsigned int *ad) { + if (d == L && sx > 0) { *ax = sx-1; *ay = sy; *ad = R; return 1; } + if (d == R && sx < state->p.w-1) { *ax = sx+1; *ay = sy; *ad = L; return 1; } + if (d == U && sy > 0) { *ax = sx; *ay = sy-1; *ad = D; return 1; } + if (d == D && sy < state->p.h-1) { *ax = sx; *ay = sy+1; *ad = U; return 1; } + + return 0; +} + +/* Sets flag (E_TRACK or E_NOTRACK) on a given edge of a square. */ +void S_E_SET(game_state *state, int sx, int sy, int d, unsigned int eflag) { + unsigned shift = (eflag == E_TRACK) ? S_TRACK_SHIFT : S_NOTRACK_SHIFT, ad; + int ax, ay; + + state->sflags[sy*state->p.w+sx] |= (d << shift); + + if (S_E_ADJ(state, sx, sy, d, &ax, &ay, &ad)) { + state->sflags[ay*state->p.w+ax] |= (ad << shift); + } +} + +/* Clears flag (E_TRACK or E_NOTRACK) on a given edge of a square. */ +void S_E_CLEAR(game_state *state, int sx, int sy, int d, unsigned int eflag) { + unsigned shift = (eflag == E_TRACK) ? S_TRACK_SHIFT : S_NOTRACK_SHIFT, ad; + int ax, ay; + + state->sflags[sy*state->p.w+sx] &= ~(d << shift); + + if (S_E_ADJ(state, sx, sy, d, &ax, &ay, &ad)) { + state->sflags[ay*state->p.w+ax] &= ~(ad << shift); + } +} + +static void clear_game(game_state *state) +{ + int w = state->p.w, h = state->p.h; + + memset(state->sflags, 0, w*h * sizeof(unsigned int)); + + memset(state->numbers->numbers, 0, (w+h) * sizeof(int)); + state->numbers->col_s = state->numbers->row_s = -1; + + memset(state->num_errors, 0, (w+h) * sizeof(int)); + + state->completed = state->used_solve = state->impossible = FALSE; +} + +static game_state *blank_game(const game_params *params) +{ + game_state *state = snew(game_state); + int w = params->w, h = params->h; + + state->p = *params; + + state->sflags = snewn(w*h, unsigned int); + + state->numbers = snew(struct numbers); + state->numbers->refcount = 1; + state->numbers->numbers = snewn(w+h, int); + + state->num_errors = snewn(w+h, int); + + clear_game(state); + + return state; +} + +static void copy_game_flags(const game_state *src, game_state *dest) +{ + int w = src->p.w, h = src->p.h; + + memcpy(dest->sflags, src->sflags, w*h*sizeof(unsigned int)); +} + +static game_state *dup_game(const game_state *state) +{ + int w = state->p.w, h = state->p.h; + game_state *ret = snew(game_state); + + ret->p = state->p; /* structure copy */ + + ret->sflags = snewn(w*h, unsigned int); + copy_game_flags(state, ret); + + ret->numbers = state->numbers; + state->numbers->refcount++; + ret->num_errors = snewn(w+h, int); + memcpy(ret->num_errors, state->num_errors, (w+h)*sizeof(int)); + + ret->completed = state->completed; + ret->used_solve = state->used_solve; + ret->impossible = state->impossible; + + return ret; +} + +static void free_game(game_state *state) +{ + if (--state->numbers->refcount <= 0) { + sfree(state->numbers->numbers); + sfree(state->numbers); + } + sfree(state->num_errors); + sfree(state->sflags); + sfree(state); +} + +#define NDIRS 4 +const unsigned int dirs_const[] = { U, D, L, R }; + +static unsigned int find_direction(game_state *state, random_state *rs, + int x, int y) +{ + int i, nx, ny, w=state->p.w, h=state->p.h; + unsigned int dirs[NDIRS]; + + memcpy(dirs, dirs_const, sizeof(dirs)); + shuffle(dirs, NDIRS, sizeof(*dirs), rs); + for (i = 0; i < NDIRS; i++) { + nx = x + DX(dirs[i]); + ny = y + DY(dirs[i]); + if (nx >= 0 && nx < w && ny == h) { + /* off the bottom of the board: we've finished the path. */ + return dirs[i]; + } else if (!INGRID(state, nx, ny)) { + /* off the board: can't move here */ + continue; + } else if (S_E_COUNT(state, nx, ny, E_TRACK) > 0) { + /* already tracks here: can't move */ + continue; + } + return dirs[i]; + } + return 0; /* no possible directions left. */ +} + +static int check_completion(game_state *state, int mark); + +static void lay_path(game_state *state, random_state *rs) +{ + int px, py, w=state->p.w, h=state->p.h; + unsigned int d; + +start: + clear_game(state); + + /* pick a random entry point, lay its left edge */ + state->numbers->row_s = py = random_upto(rs, h); + px = 0; + S_E_SET(state, px, py, L, E_TRACK); + + while (INGRID(state, px, py)) { + d = find_direction(state, rs, px, py); + if (d == 0) + goto start; /* nowhere else to go, restart */ + + S_E_SET(state, px, py, d, E_TRACK); + px += DX(d); + py += DY(d); + } + /* double-check we got to the right place */ + assert(px >= 0 && px < w && py == h); + + state->numbers->col_s = px; +} + +static int tracks_solve(game_state *state, int diff); +static void debug_state(game_state *state, const char *what); + +/* Clue-setting algorithm: + + - first lay clues randomly until it's soluble + - then remove clues randomly if removing them doesn't affect solubility + + - We start with two clues, one at each path entrance. + + More details: + - start with an array of all square i positions + - if the grid is already soluble by a level easier than we've requested, + go back and make a new grid + - if the grid is already soluble by our requested difficulty level, skip + the clue-laying step + - count the number of flags the solver managed to place, remember this. + + - to lay clues: + - shuffle the i positions + - for each possible clue position: + - copy the solved board, strip it + - take the next position, add a clue there on the copy + - try and solve the copy + - if it's soluble by a level easier than we've requested, continue (on + to next clue position: putting a clue here makes it too easy) + - if it's soluble by our difficulty level, we're done: + - put the clue flag into the solved board + - go to strip-clues. + - if the solver didn't manage to place any more flags, continue (on to next + clue position: putting a clue here didn't help he solver) + - otherwise put the clue flag in the original board, and go on to the next + clue position + - if we get here and we've not solved it yet, we never will (did we really + fill _all_ the clues in?!). Go back and make a new grid. + + - to strip clues: + - shuffle the i positions + - for each possible clue position: + - if the solved grid doesn't have a clue here, skip + - copy the solved board, remove this clue, strip it + - try and solve the copy + - assert that it is not soluble by a level easier than we've requested + - (because this should never happen) + - if this is (still) soluble by our difficulty level: + - remove this clue from the solved board, it's redundant (with the other + clues) + + - that should be it. +*/ + +static game_state *copy_and_strip(const game_state *state, game_state *ret, int flipcluei) +{ + int i, j, w = state->p.w, h = state->p.h; + + copy_game_flags(state, ret); + + /* Add/remove a clue before stripping, if required */ + + if (flipcluei != -1) + ret->sflags[flipcluei] ^= S_CLUE; + + /* All squares that are not clue squares have square track info erased, and some edge flags.. */ + + for (i = 0; i < w*h; i++) { + if (!(ret->sflags[i] & S_CLUE)) { + ret->sflags[i] &= ~(S_TRACK|S_NOTRACK|S_ERROR|S_MARK); + for (j = 0; j < 4; j++) { + unsigned f = 1<sflags[yy*w+xx] & S_CLUE)) { + /* only erase an edge flag if neither side of the edge is S_CLUE. */ + S_E_CLEAR(ret, i%w, i/w, f, E_TRACK); + S_E_CLEAR(ret, i%w, i/w, f, E_NOTRACK); + } + } + } + } + return ret; +} + +static int solve_progress(const game_state *state) { + int i, w = state->p.w, h = state->p.h, progress = 0; + + /* Work out how many flags the solver managed to set (either TRACK + or NOTRACK) and return this as a progress measure, to check whether + a partially-solved board gets any further than a previous partially- + solved board. */ + + for (i = 0; i < w*h; i++) { + if (state->sflags[i] & S_TRACK) progress++; + if (state->sflags[i] & S_NOTRACK) progress++; + progress += S_E_COUNT(state, i%w, i/w, E_TRACK); + progress += S_E_COUNT(state, i%w, i/w, E_NOTRACK); + } + return progress; +} + +static int check_phantom_moves(const game_state *state) { + int x, y, i; + + /* Check that this state won't show 'phantom moves' at the start of the + * game: squares which have multiple edge flags set but no clue flag + * cause a piece of track to appear that isn't on a clue square. */ + + for (x = 0; x < state->p.w; x++) { + for (y = 0; y < state->p.h; y++) { + i = y*state->p.w+x; + if (state->sflags[i] & S_CLUE) + continue; + if (S_E_COUNT(state, x, y, E_TRACK) > 1) + return 1; /* found one! */ + } + } + return 0; +} + +static int add_clues(game_state *state, random_state *rs, int diff) +{ + int i, j, pi, w = state->p.w, h = state->p.h, progress, ret = 0, sr; + int *positions = snewn(w*h, int), npositions = 0; + int *nedges_previous_solve = snewn(w*h, int); + game_state *scratch = dup_game(state); + + debug_state(state, "gen: Initial board"); + + debug(("gen: Adding clues...")); + + /* set up the shuffly-position grid for later, used for adding clues: + * we only bother adding clues where any edges are set. */ + for (i = 0; i < w*h; i++) { + if (S_E_DIRS(state, i%w, i/w, E_TRACK) != 0) { + positions[npositions++] = i; + } + nedges_previous_solve[i] = 0; + } + + /* First, check whether the puzzle is already either too easy, or just right */ + scratch = copy_and_strip(state, scratch, -1); + if (diff > 0) { + sr = tracks_solve(scratch, diff-1); + if (sr < 0) + assert(!"Generator should not have created impossible puzzle"); + if (sr > 0) { + ret = -1; /* already too easy, even without adding clues. */ + debug(("gen: ...already too easy, need new board.")); + goto done; + } + } + sr = tracks_solve(scratch, diff); + if (sr < 0) + assert(!"Generator should not have created impossible puzzle"); + if (sr > 0) { + ret = 1; /* already soluble without any extra clues. */ + debug(("gen: ...soluble without clues, nothing to do.")); + goto done; + } + debug_state(scratch, "gen: Initial part-solved state: "); + progress = solve_progress(scratch); + debug(("gen: Initial solve progress is %d", progress)); + + /* First, lay clues until we're soluble. */ + shuffle(positions, npositions, sizeof(int), rs); + for (pi = 0; pi < npositions; pi++) { + i = positions[pi]; /* pick a random position */ + if (state->sflags[i] & S_CLUE) + continue; /* already a clue here (entrance location?) */ + if (nedges_previous_solve[i] == 2) + continue; /* no point putting a clue here, we could solve both edges + with the previous set of clues */ + + /* set a clue in that position (on a copy of the board) and test solubility */ + scratch = copy_and_strip(state, scratch, i); + + if (check_phantom_moves(scratch)) + continue; /* adding a clue here would add phantom track */ + + if (diff > 0) { + if (tracks_solve(scratch, diff-1) > 0) { + continue; /* adding a clue here makes it too easy */ + } + } + if (tracks_solve(scratch, diff) > 0) { + /* we're now soluble (and we weren't before): add this clue, and then + start stripping clues */ + debug(("gen: ...adding clue at (%d,%d), now soluble", i%w, i/w)); + state->sflags[i] |= S_CLUE; + goto strip_clues; + } + if (solve_progress(scratch) > progress) { + /* We've made more progress solving: add this clue, then. */ + progress = solve_progress(scratch); + debug(("gen: ... adding clue at (%d,%d), new progress %d", i%w, i/w, progress)); + state->sflags[i] |= S_CLUE; + + for (j = 0; j < w*h; j++) + nedges_previous_solve[j] = S_E_COUNT(scratch, j%w, j/w, E_TRACK); + } + } + /* If we got here we didn't ever manage to make the puzzle soluble + (without making it too easily soluble, that is): give up. */ + + debug(("gen: Unable to make soluble with clues, need new board.")); + ret = -1; + goto done; + +strip_clues: + debug(("gen: Stripping clues.")); + + /* Now, strip redundant clues (i.e. those without which the puzzle is still + soluble) */ + shuffle(positions, npositions, sizeof(int), rs); + for (pi = 0; pi < npositions; pi++) { + i = positions[pi]; /* pick a random position */ + if (!(state->sflags[i] & S_CLUE)) + continue; /* no clue here to strip */ + if ((i%w == 0 && i/w == state->numbers->row_s) || + (i/w == (h-1) && i%w == state->numbers->col_s)) + continue; /* don't strip clues at entrance/exit */ + + scratch = copy_and_strip(state, scratch, i); + if (check_phantom_moves(scratch)) + continue; /* removing a clue here would add phantom track */ + + if (tracks_solve(scratch, diff) > 0) { + debug(("gen: ... removing clue at (%d,%d), still soluble without it", i%w, i/w)); + state->sflags[i] &= ~S_CLUE; /* still soluble without this clue. */ + } + } + debug(("gen: Finished stripping clues.")); + ret = 1; + +done: + sfree(positions); + free_game(scratch); + return ret; +} + +static char *new_game_desc(const game_params *params, random_state *rs, + char **aux, int interactive) +{ + int i, j, w = params->w, h = params->h, x, y, ret; + game_state *state; + char *desc, *p; + game_params adjusted_params; + + /* + * 4x4 Tricky cannot be generated, so fall back to Easy. + */ + if (w == 4 && h == 4 && params->diff > DIFF_EASY) { + adjusted_params = *params; /* structure copy */ + adjusted_params.diff = DIFF_EASY; + params = &adjusted_params; + } + + state = blank_game(params); + + /* --- lay the random path */ + +newpath: + lay_path(state, rs); + for (x = 0; x < w; x++) { + for (y = 0; y < h; y++) { + if (S_E_COUNT(state, x, y, E_TRACK) > 0) { + state->sflags[y*w + x] |= S_TRACK; + } + if ((x == 0 && y == state->numbers->row_s) || + (y == (h-1) && x == state->numbers->col_s)) { + state->sflags[y*w + x] |= S_CLUE; + } + } + } + + /* --- Update the clue numbers based on the tracks we have generated. */ + for (x = 0; x < w; x++) { + for (y = 0; y < h; y++) { + if (state->sflags[y*w + x] & S_TRACK) { + state->numbers->numbers[x]++; + state->numbers->numbers[y+w]++; + } + } + } + for (i = 0; i < w+h; i++) { + if (state->numbers->numbers[i] == 0) + goto newpath; /* too boring */ + } + + if (params->single_ones) { + int last_was_one = 1, is_one; /* (disallow 1 clue at entry point) */ + for (i = 0; i < w+h; i++) { + is_one = (state->numbers->numbers[i] == 1); + if (is_one && last_was_one) + goto newpath; /* disallow consecutive 1 clues. */ + last_was_one = is_one; + } + if (state->numbers->numbers[w+h-1] == 1) + goto newpath; /* (disallow 1 clue at exit point) */ + } + + /* --- Add clues to make a soluble puzzle */ + ret = add_clues(state, rs, params->diff); + if (ret != 1) goto newpath; /* couldn't make it soluble, or too easy */ + + /* --- Generate the game desc based on the generated grid. */ + desc = snewn(w*h*3 + (w+h)*5, char); + for (i = j = 0; i < w*h; i++) { + if (!(state->sflags[i] & S_CLUE) && j > 0 && + desc[j-1] >= 'a' && desc[j-1] < 'z') + desc[j-1]++; + else if (!(state->sflags[i] & S_CLUE)) + desc[j++] = 'a'; + else { + unsigned int f = S_E_DIRS(state, i%w, i/w, E_TRACK); + desc[j++] = (f < 10) ? ('0' + f) : ('A' + (f-10)); + } + } + + p = desc + j; + for (x = 0; x < w; x++) { + p += sprintf(p, ",%s%d", x == state->numbers->col_s ? "S" : "", + state->numbers->numbers[x]); + } + for (y = 0; y < h; y++) { + p += sprintf(p, ",%s%d", y == state->numbers->row_s ? "S" : "", + state->numbers->numbers[y+w]); + } + *p++ = '\0'; + + ret = tracks_solve(state, DIFFCOUNT); + assert(ret >= 0); + free_game(state); + + debug(("new_game_desc: %s", desc)); + return desc; +} + +static char *validate_desc(const game_params *params, const char *desc) +{ + int i = 0, w = params->w, h = params->h, in = 0, out = 0; + + while (*desc) { + unsigned int f = 0; + if (*desc >= '0' && *desc <= '9') + f = (*desc - '0'); + else if (*desc >= 'A' && *desc <= 'F') + f = (*desc - 'A' + 10); + else if (*desc >= 'a' && *desc <= 'z') + i += *desc - 'a'; + else + return "Game description contained unexpected characters"; + + if (f != 0) { + if (nbits[f] != 2) + return "Clue did not provide 2 direction flags"; + } + i++; + desc++; + if (i == w*h) break; + } + for (i = 0; i < w+h; i++) { + if (!*desc) + return "Not enough numbers given after grid specification"; + else if (*desc != ',') + return "Invalid character in number list"; + desc++; + if (*desc == 'S') { + if (i < w) + out++; + else + in++; + desc++; + } + while (*desc && isdigit((unsigned char)*desc)) desc++; + } + if (in != 1 || out != 1) + return "Puzzle must have one entrance and one exit"; + if (*desc) + return "Unexpected additional character at end of game description"; + return NULL; +} + +static game_state *new_game(midend *me, const game_params *params, const char *desc) +{ + game_state *state = blank_game(params); + int w = params->w, h = params->h, i = 0; + + while (*desc) { + unsigned int f = 0; + if (*desc >= '0' && *desc <= '9') + f = (*desc - '0'); + else if (*desc >= 'A' && *desc <= 'F') + f = (*desc - 'A' + 10); + else if (*desc >= 'a' && *desc <= 'z') + i += *desc - 'a'; + + if (f != 0) { + int x = i % w, y = i / w; + assert(f < 16); + assert(nbits[f] == 2); + + state->sflags[i] |= (S_TRACK | S_CLUE); + if (f & U) S_E_SET(state, x, y, U, E_TRACK); + if (f & D) S_E_SET(state, x, y, D, E_TRACK); + if (f & L) S_E_SET(state, x, y, L, E_TRACK); + if (f & R) S_E_SET(state, x, y, R, E_TRACK); + } + i++; + desc++; + if (i == w*h) break; + } + for (i = 0; i < w+h; i++) { + assert(*desc == ','); + desc++; + + if (*desc == 'S') { + if (i < w) + state->numbers->col_s = i; + else + state->numbers->row_s = i-w; + desc++; + } + state->numbers->numbers[i] = atoi(desc); + while (*desc && isdigit((unsigned char)*desc)) desc++; + } + + assert(!*desc); + + return state; +} + +static int solve_set_sflag(game_state *state, int x, int y, + unsigned int f, const char *why) +{ + int w = state->p.w, i = y*w + x; + + if (state->sflags[i] & f) + return 0; + debug(("solve: square (%d,%d) -> %s: %s", + x, y, (f == S_TRACK ? "TRACK" : "NOTRACK"), why)); + if (state->sflags[i] & (f == S_TRACK ? S_NOTRACK : S_TRACK)) { + debug(("solve: opposite flag already set there, marking IMPOSSIBLE")); + state->impossible = TRUE; + } + state->sflags[i] |= f; + return 1; +} + +static int solve_set_eflag(game_state *state, int x, int y, int d, + unsigned int f, const char *why) +{ + int sf = S_E_FLAGS(state, x, y, d); + + if (sf & f) + return 0; + debug(("solve: edge (%d,%d)/%c -> %s: %s", x, y, + (d == U) ? 'U' : (d == D) ? 'D' : (d == L) ? 'L' : 'R', + (f == S_TRACK ? "TRACK" : "NOTRACK"), why)); + if (sf & (f == E_TRACK ? E_NOTRACK : E_TRACK)) { + debug(("solve: opposite flag already set there, marking IMPOSSIBLE")); + state->impossible = TRUE; + } + S_E_SET(state, x, y, d, f); + return 1; +} + +static int solve_update_flags(game_state *state) +{ + int x, y, i, w = state->p.w, h = state->p.h, did = 0; + + for (x = 0; x < w; x++) { + for (y = 0; y < h; y++) { + /* If a square is NOTRACK, all four edges must be. */ + if (state->sflags[y*w + x] & S_NOTRACK) { + for (i = 0; i < 4; i++) { + unsigned int d = 1<= 3) { + did += solve_set_sflag(state, x, y, S_NOTRACK, "square has >2 NOTRACK edges"); + } + + /* If any edge around a square is TRACK, the square is. */ + if (S_E_COUNT(state, x, y, E_TRACK) > 0) { + did += solve_set_sflag(state, x, y, S_TRACK, "square has TRACK edge"); + } + + /* If a square is TRACK and 2 edges are NOTRACK, + the other two edges must be TRACK. */ + if ((state->sflags[y*w + x] & S_TRACK) && + (S_E_COUNT(state, x, y, E_NOTRACK) == 2) && + (S_E_COUNT(state, x, y, E_TRACK) < 2)) { + for (i = 0; i < 4; i++) { + unsigned int d = 1<sflags[y*w + x] & S_TRACK) && + (S_E_COUNT(state, x, y, E_TRACK) == 2) && + (S_E_COUNT(state, x, y, E_NOTRACK) < 2)) { + for (i = 0; i < 4; i++) { + unsigned int d = 1<p.h, w = state->p.w; + for (n = 0, i = col; n < h; n++, i += w) { + if (state->sflags[i] & f) c++; + } + return c; +} + +static int solve_count_row(game_state *state, int row, unsigned int f) +{ + int i, n, c = 0, w = state->p.w; + for (n = 0, i = w*row; n < state->p.w; n++, i++) { + if (state->sflags[i] & f) c++; + } + return c; +} + +static int solve_count_clues_sub(game_state *state, int si, int id, int n, + int target, const char *what) +{ + int ctrack = 0, cnotrack = 0, did = 0, j, i, w = state->p.w; + + for (j = 0, i = si; j < n; j++, i += id) { + if (state->sflags[i] & S_TRACK) + ctrack++; + if (state->sflags[i] & S_NOTRACK) + cnotrack++; + } + if (ctrack == target) { + /* everything that's not S_TRACK must be S_NOTRACK. */ + for (j = 0, i = si; j < n; j++, i += id) { + if (!(state->sflags[i] & S_TRACK)) + did += solve_set_sflag(state, i%w, i/w, S_NOTRACK, what); + } + } + if (cnotrack == (n-target)) { + /* everything that's not S_NOTRACK must be S_TRACK. */ + for (j = 0, i = si; j < n; j++, i += id) { + if (!(state->sflags[i] & S_NOTRACK)) + did += solve_set_sflag(state, i%w, i/w, S_TRACK, what); + } + } + return did; +} + +static int solve_count_clues(game_state *state) +{ + int w = state->p.w, h = state->p.h, x, y, target, did = 0; + + for (x = 0; x < w; x++) { + target = state->numbers->numbers[x]; + did += solve_count_clues_sub(state, x, w, h, target, "col count"); + } + for (y = 0; y < h; y++) { + target = state->numbers->numbers[w+y]; + did += solve_count_clues_sub(state, y*w, 1, w, target, "row count"); + } + return did; +} + +static int solve_check_single_sub(game_state *state, int si, int id, int n, + int target, unsigned int perpf, + const char *what) +{ + int ctrack = 0, nperp = 0, did = 0, j, i, w = state->p.w; + int n1edge = 0, i1edge = 0, ox, oy, x, y; + unsigned int impossible = 0; + + /* For rows or columns which only have one more square to put a track in, we + know the only way a new track section could be there would be to run + perpendicular to the track (otherwise we'd need at least two free squares). + So, if there is nowhere we can run perpendicular to the track (e.g. because + we're on an edge) we know the extra track section much be on one end of an + existing section. */ + + for (j = 0, i = si; j < n; j++, i += id) { + if (state->sflags[i] & S_TRACK) + ctrack++; + impossible = S_E_DIRS(state, i%w, i/w, E_NOTRACK); + if ((perpf & impossible) == 0) + nperp++; + if (S_E_COUNT(state, i%w, i/w, E_TRACK) <= 1) { + n1edge++; + i1edge = i; + } + } + if (ctrack != (target-1)) return 0; + if (nperp > 0 || n1edge != 1) return 0; + + debug(("check_single from (%d,%d): 1 match from (%d,%d)", + si%w, si/w, i1edge%w, i1edge/w)); + + /* We have a match: anything that's more than 1 away from this square + cannot now contain a track. */ + ox = i1edge%w; + oy = i1edge/w; + for (j = 0, i = si; j < n; j++, i += id) { + x = i%w; + y = i/w; + if (abs(ox-x) > 1 || abs(oy-y) > 1) { + if (!(state->sflags[i] & S_TRACK)) + did += solve_set_sflag(state, x, y, S_NOTRACK, what); + } + } + + return did; +} + +static int solve_check_single(game_state *state) +{ + int w = state->p.w, h = state->p.h, x, y, target, did = 0; + + for (x = 0; x < w; x++) { + target = state->numbers->numbers[x]; + did += solve_check_single_sub(state, x, w, h, target, R|L, "single on col"); + } + for (y = 0; y < h; y++) { + target = state->numbers->numbers[w+y]; + did += solve_check_single_sub(state, y*w, 1, w, target, U|D, "single on row"); + } + return did; +} + +static int solve_check_loose_sub(game_state *state, int si, int id, int n, + int target, unsigned int perpf, + const char *what) +{ + int nperp = 0, nloose = 0, e2count = 0, did = 0, i, j, k; + int w = state->p.w; + unsigned int parf = ALLDIR & (~perpf); + + for (j = 0, i = si; j < n; j++, i += id) { + int fcount = S_E_COUNT(state, i%w, i/w, E_TRACK); + if (fcount == 2) + e2count++; /* this cell has 2 definite edges */ + state->sflags[i] &= ~S_MARK; + if (fcount == 1 && (parf & S_E_DIRS(state, i%w, i/w, E_TRACK))) { + nloose++; /* this cell has a loose end (single flag set parallel + to the direction of this row/column) */ + state->sflags[i] |= S_MARK; /* mark loose ends */ + } + if (fcount != 2 && !(perpf & S_E_DIRS(state, i%w, i/w, E_NOTRACK))) + nperp++; /* we could lay perpendicular across this cell */ + } + + if (nloose > (target - e2count)) { + debug(("check %s from (%d,%d): more loose (%d) than empty (%d), IMPOSSIBLE", + what, si%w, si/w, nloose, target-e2count)); + state->impossible = TRUE; + } + if (nloose > 0 && nloose == (target - e2count)) { + debug(("check %s from (%d,%d): nloose = empty (%d), forcing loners out.", + what, si%w, si/w, nloose)); + for (j = 0, i = si; j < n; j++, i += id) { + if (!(state->sflags[i] & S_MARK)) + continue; /* skip non-loose ends */ + if (j > 0 && state->sflags[i-id] & S_MARK) + continue; /* next to other loose end, could join up */ + if (j < (n-1) && state->sflags[i+id] & S_MARK) + continue; /* ditto */ + + for (k = 0; k < 4; k++) { + if ((parf & (1<sflags[i] & S_MARK)) + continue; /* skip non-loose ends */ + for (k = 0; k < 4; k++) { + if (parf & (1<p.w, h = state->p.h, x, y, target, did = 0; + + for (x = 0; x < w; x++) { + target = state->numbers->numbers[x]; + did += solve_check_loose_sub(state, x, w, h, target, R|L, "loose on col"); + } + for (y = 0; y < h; y++) { + target = state->numbers->numbers[w+y]; + did += solve_check_loose_sub(state, y*w, 1, w, target, U|D, "loose on row"); + } + return did; +} + +static int solve_check_loop_sub(game_state *state, int x, int y, int dir, + int *dsf, int startc, int endc) +{ + int w = state->p.w, h = state->p.h, i = y*w+x, j, k, satisfied = 1; + + j = (y+DY(dir))*w + (x+DX(dir)); + + assert(i < w*h && j < w*h); + + if ((state->sflags[i] & S_TRACK) && + (state->sflags[j] & S_TRACK) && + !(S_E_DIRS(state, x, y, E_TRACK) & dir) && + !(S_E_DIRS(state, x, y, E_NOTRACK) & dir)) { + int ic = dsf_canonify(dsf, i), jc = dsf_canonify(dsf, j); + if (ic == jc) { + return solve_set_eflag(state, x, y, dir, E_NOTRACK, "would close loop"); + } + if ((ic == startc && jc == endc) || (ic == endc && jc == startc)) { + debug(("Adding link at (%d,%d) would join start to end", x, y)); + /* We mustn't join the start to the end if: + - there are other bits of track that aren't attached to either end + - the clues are not fully satisfied yet + */ + for (k = 0; k < w*h; k++) { + if (state->sflags[k] & S_TRACK && + dsf_canonify(dsf, k) != startc && dsf_canonify(dsf, k) != endc) { + return solve_set_eflag(state, x, y, dir, E_NOTRACK, + "joins start to end but misses tracks"); + } + } + for (k = 0; k < w; k++) { + int target = state->numbers->numbers[k]; + int ntracks = solve_count_col(state, k, S_TRACK); + if (ntracks < target) satisfied = 0; + } + for (k = 0; k < h; k++) { + int target = state->numbers->numbers[w+k]; + int ntracks = solve_count_row(state, k, S_TRACK); + if (ntracks < target) satisfied = 0; + } + if (!satisfied) { + return solve_set_eflag(state, x, y, dir, E_NOTRACK, + "joins start to end with incomplete clues"); + } + } + } + return 0; +} + +static int solve_check_loop(game_state *state) +{ + int w = state->p.w, h = state->p.h, x, y, i, j, did = 0; + int *dsf, startc, endc; + + /* TODO eventually we should pull this out into a solver struct and keep it + updated as we connect squares. For now we recreate it every time we try + this particular solver step. */ + dsf = snewn(w*h, int); + dsf_init(dsf, w*h); + + /* Work out the connectedness of the current loop set. */ + for (x = 0; x < w; x++) { + for (y = 0; y < h; y++) { + i = y*w + x; + if (x < (w-1) && S_E_DIRS(state, x, y, E_TRACK) & R) { + /* connection to the right... */ + j = y*w + (x+1); + assert(i < w*h && j < w*h); + dsf_merge(dsf, i, j); + } + if (y < (h-1) && S_E_DIRS(state, x, y, E_TRACK) & D) { + /* connection down... */ + j = (y+1)*w + x; + assert(i < w*h && j < w*h); + dsf_merge(dsf, i, j); + } + /* NB no need to check up and left because they'll have been checked + by the other side. */ + } + } + + startc = dsf_canonify(dsf, state->numbers->row_s*w); + endc = dsf_canonify(dsf, (h-1)*w+state->numbers->col_s); + + /* Now look at all adjacent squares that are both S_TRACK: if connecting + any of them would complete a loop (i.e. they're both the same dsf class + already) then that edge must be NOTRACK. */ + for (x = 0; x < w; x++) { + for (y = 0; y < h; y++) { + if (x < (w-1)) + did += solve_check_loop_sub(state, x, y, R, dsf, startc, endc); + if (y < (h-1)) + did += solve_check_loop_sub(state, x, y, D, dsf, startc, endc); + } + } + + sfree(dsf); + + return did; +} + +static void solve_discount_edge(game_state *state, int x, int y, int d) +{ + if (S_E_DIRS(state, x, y, E_TRACK) & d) { + assert(state->sflags[y*state->p.w + x] & S_CLUE); + return; /* (only) clue squares can have outer edges set. */ + } + solve_set_eflag(state, x, y, d, E_NOTRACK, "outer edge"); +} + +static int tracks_solve(game_state *state, int diff) +{ + int didsth, x, y, w = state->p.w, h = state->p.h; + + debug(("solve...")); + state->impossible = FALSE; + + /* Set all the outer border edges as no-track. */ + for (x = 0; x < w; x++) { + solve_discount_edge(state, x, 0, U); + solve_discount_edge(state, x, h-1, D); + } + for (y = 0; y < h; y++) { + solve_discount_edge(state, 0, y, L); + solve_discount_edge(state, w-1, y, R); + } + + while (1) { + didsth = 0; + + didsth += solve_update_flags(state); + didsth += solve_count_clues(state); + didsth += solve_check_loop(state); + + if (diff >= DIFF_TRICKY) { + didsth += solve_check_single(state); + didsth += solve_check_loose_ends(state); + } + + if (!didsth || state->impossible) break; + } + + return state->impossible ? -1 : check_completion(state, FALSE) ? 1 : 0; +} + +static char *move_string_diff(const game_state *before, const game_state *after, int issolve) +{ + int w = after->p.w, h = after->p.h, i, j; + char *move = snewn(w*h*40, char), *p = move; + const char *sep = ""; + unsigned int otf, ntf, onf, nnf; + + if (issolve) { + *p++ = 'S'; + sep = ";"; + } + for (i = 0; i < w*h; i++) { + otf = S_E_DIRS(before, i%w, i/w, E_TRACK); + ntf = S_E_DIRS(after, i%w, i/w, E_TRACK); + onf = S_E_DIRS(before, i%w, i/w, E_NOTRACK); + nnf = S_E_DIRS(after, i%w, i/w, E_NOTRACK); + + for (j = 0; j < 4; j++) { + unsigned df = 1<sflags[i] & S_NOTRACK) != (after->sflags[i] & S_NOTRACK)) { + p += sprintf(p, "%s%cS%d,%d", sep, + (after->sflags[i] & S_NOTRACK) ? 'N' : 'n', i%w, i/w); + sep = ";"; + } + if ((before->sflags[i] & S_TRACK) != (after->sflags[i] & S_TRACK)) { + p += sprintf(p, "%s%cS%d,%d", sep, + (after->sflags[i] & S_TRACK) ? 'T' : 't', i%w, i/w); + sep = ";"; + } + } + *p++ = '\0'; + move = sresize(move, p - move, char); + + return move; +} + +static char *solve_game(const game_state *state, const game_state *currstate, + const char *aux, char **error) +{ + game_state *solved; + int ret; + char *move; + + solved = dup_game(currstate); + ret = tracks_solve(solved, DIFFCOUNT); + if (ret < 1) { + free_game(solved); + solved = dup_game(state); + ret = tracks_solve(solved, DIFFCOUNT); + } + + if (ret < 1) { + *error = "Unable to find solution"; + move = NULL; + } else { + move = move_string_diff(currstate, solved, TRUE); + } + + free_game(solved); + return move; +} + +static int game_can_format_as_text_now(const game_params *params) +{ + return TRUE; +} + +static char *game_text_format(const game_state *state) +{ + char *ret, *p; + int x, y, len, w = state->p.w, h = state->p.h; + + len = ((w*2) + 4) * ((h*2)+4) + 2; + ret = snewn(len+1, char); + p = ret; + + /* top line: column clues */ + *p++ = ' '; + *p++ = ' '; + for (x = 0; x < w; x++) { + *p++ = (state->numbers->numbers[x] < 10 ? + '0' + state->numbers->numbers[x] : + 'A' + state->numbers->numbers[x] - 10); + *p++ = ' '; + } + *p++ = '\n'; + + /* second line: top edge */ + *p++ = ' '; + *p++ = '+'; + for (x = 0; x < w*2-1; x++) + *p++ = '-'; + *p++ = '+'; + *p++ = '\n'; + + /* grid rows: one line of squares, one line of edges. */ + for (y = 0; y < h; y++) { + /* grid square line */ + *p++ = (y == state->numbers->row_s) ? 'A' : ' '; + *p++ = (y == state->numbers->row_s) ? '-' : '|'; + + for (x = 0; x < w; x++) { + unsigned int f = S_E_DIRS(state, x, y, E_TRACK); + if (state->sflags[y*w+x] & S_CLUE) *p++ = 'C'; + else if (f == LU || f == RD) *p++ = '/'; + else if (f == LD || f == RU) *p++ = '\\'; + else if (f == UD) *p++ = '|'; + else if (f == RL) *p++ = '-'; + else if (state->sflags[y*w+x] & S_NOTRACK) *p++ = 'x'; + else *p++ = ' '; + + if (x < w-1) { + *p++ = (f & R) ? '-' : ' '; + } else + *p++ = '|'; + } + *p++ = (state->numbers->numbers[w+y] < 10 ? + '0' + state->numbers->numbers[w+y] : + 'A' + state->numbers->numbers[w+y] - 10); + *p++ = '\n'; + + if (y == h-1) continue; + + /* edges line */ + *p++ = ' '; + *p++ = '|'; + for (x = 0; x < w; x++) { + unsigned int f = S_E_DIRS(state, x, y, E_TRACK); + *p++ = (f & D) ? '|' : ' '; + *p++ = (x < w-1) ? ' ' : '|'; + } + *p++ = '\n'; + } + + /* next line: bottom edge */ + *p++ = ' '; + *p++ = '+'; + for (x = 0; x < w*2-1; x++) + *p++ = (x == state->numbers->col_s*2) ? '|' : '-'; + *p++ = '+'; + *p++ = '\n'; + + /* final line: bottom clue */ + *p++ = ' '; + *p++ = ' '; + for (x = 0; x < w*2-1; x++) + *p++ = (x == state->numbers->col_s*2) ? 'B' : ' '; + *p++ = '\n'; + + *p = '\0'; + return ret; +} + +static void debug_state(game_state *state, const char *what) { + char *sstring = game_text_format(state); + debug(("%s: %s", what, sstring)); + sfree(sstring); +} + +static void dsf_update_completion(game_state *state, int ax, int ay, + char dir, int *dsf) +{ + int w = state->p.w, ai = ay*w+ax, bx, by, bi; + + if (!(S_E_DIRS(state, ax, ay, E_TRACK) & dir)) return; + bx = ax + DX(dir); + by = ay + DY(dir); + + if (!INGRID(state, bx, by)) return; + bi = by*w+bx; + + dsf_merge(dsf, ai, bi); +} + +struct tracks_neighbour_ctx { + game_state *state; + int i, n, neighbours[4]; +}; +static int tracks_neighbour(int vertex, void *vctx) +{ + struct tracks_neighbour_ctx *ctx = (struct tracks_neighbour_ctx *)vctx; + if (vertex >= 0) { + game_state *state = ctx->state; + int w = state->p.w, x = vertex % w, y = vertex / w; + int dirs = S_E_DIRS(state, x, y, E_TRACK); + int j; + + ctx->i = ctx->n = 0; + + for (j = 0; j < 4; j++) { + int dir = 1<neighbours[ctx->n++] = ny * w + nx; + } + } + } + + if (ctx->i < ctx->n) + return ctx->neighbours[ctx->i++]; + else + return -1; +} + +static int check_completion(game_state *state, int mark) +{ + int w = state->p.w, h = state->p.h, x, y, i, target, ret = TRUE; + int ntrack, nnotrack, ntrackcomplete; + int *dsf, pathclass; + struct findloopstate *fls; + struct tracks_neighbour_ctx ctx; + + if (mark) { + for (i = 0; i < w+h; i++) { + state->num_errors[i] = 0; + } + for (i = 0; i < w*h; i++) { + state->sflags[i] &= ~S_ERROR; + if (S_E_COUNT(state, i%w, i/w, E_TRACK) > 0) { + if (S_E_COUNT(state, i%w, i/w, E_TRACK) > 2) { + ret = FALSE; + state->sflags[i] |= S_ERROR; + } + } + } + } + + /* A cell is 'complete', for the purposes of marking the game as + * finished, if it has two edges marked as TRACK. But it only has + * to have one edge marked as TRACK, or be filled in as trackful + * without any specific edges known, to count towards checking + * row/column clue errors. */ + for (x = 0; x < w; x++) { + target = state->numbers->numbers[x]; + ntrack = nnotrack = ntrackcomplete = 0; + for (y = 0; y < h; y++) { + if (S_E_COUNT(state, x, y, E_TRACK) > 0 || + state->sflags[y*w+x] & S_TRACK) + ntrack++; + if (S_E_COUNT(state, x, y, E_TRACK) == 2) + ntrackcomplete++; + if (state->sflags[y*w+x] & S_NOTRACK) + nnotrack++; + } + if (mark) { + if (ntrack > target || nnotrack > (h-target)) { + debug(("col %d error: target %d, track %d, notrack %d", + x, target, ntrack, nnotrack)); + state->num_errors[x] = 1; + ret = FALSE; + } + } + if (ntrackcomplete != target) + ret = FALSE; + } + for (y = 0; y < h; y++) { + target = state->numbers->numbers[w+y]; + ntrack = nnotrack = ntrackcomplete = 0; + for (x = 0; x < w; x++) { + if (S_E_COUNT(state, x, y, E_TRACK) > 0 || + state->sflags[y*w+x] & S_TRACK) + ntrack++; + if (S_E_COUNT(state, x, y, E_TRACK) == 2) + ntrackcomplete++; + if (state->sflags[y*w+x] & S_NOTRACK) + nnotrack++; + } + if (mark) { + if (ntrack > target || nnotrack > (w-target)) { + debug(("row %d error: target %d, track %d, notrack %d", + y, target, ntrack, nnotrack)); + state->num_errors[w+y] = 1; + ret = FALSE; + } + } + if (ntrackcomplete != target) + ret = FALSE; + } + + dsf = snewn(w*h, int); + dsf_init(dsf, w*h); + + for (x = 0; x < w; x++) { + for (y = 0; y < h; y++) { + dsf_update_completion(state, x, y, R, dsf); + dsf_update_completion(state, x, y, D, dsf); + } + } + + fls = findloop_new_state(w*h); + ctx.state = state; + if (findloop_run(fls, w*h, tracks_neighbour, &ctx)) { + debug(("loop detected, not complete")); + ret = FALSE; /* no loop allowed */ + if (mark) { + for (x = 0; x < w; x++) { + for (y = 0; y < h; y++) { + int u, v; + + u = y*w + x; + for (v = tracks_neighbour(u, &ctx); v >= 0; + v = tracks_neighbour(-1, &ctx)) + if (findloop_is_loop_edge(fls, u, v)) + state->sflags[y*w+x] |= S_ERROR; + } + } + } + } + findloop_free_state(fls); + + if (mark) { + pathclass = dsf_canonify(dsf, state->numbers->row_s*w); + if (pathclass == dsf_canonify(dsf, (h-1)*w + state->numbers->col_s)) { + /* We have a continuous path between the entrance and the exit: any + other path must be in error. */ + for (i = 0; i < w*h; i++) { + if ((dsf_canonify(dsf, i) != pathclass) && + ((state->sflags[i] & S_TRACK) || + (S_E_COUNT(state, i%w, i/w, E_TRACK) > 0))) { + ret = FALSE; + state->sflags[i] |= S_ERROR; + } + } + } else { + /* If we _don't_ have such a path, then certainly the game + * can't be in a winning state. So even if we're not + * highlighting any _errors_, we certainly shouldn't + * return true. */ + ret = FALSE; + } + } + + if (mark) + state->completed = ret; + sfree(dsf); + return ret; +} + +/* Code borrowed from Pearl. */ + +struct game_ui { + int dragging, clearing, notrack; + int drag_sx, drag_sy, drag_ex, drag_ey; /* drag start and end grid coords */ + int clickx, clicky; /* pixel position of initial click */ + + int curx, cury; /* grid position of keyboard cursor; uses half-size grid */ + int cursor_active; /* TRUE iff cursor is shown */ +}; + +static game_ui *new_ui(const game_state *state) +{ + game_ui *ui = snew(game_ui); + + ui->clearing = ui->notrack = ui->dragging = 0; + ui->drag_sx = ui->drag_sy = ui->drag_ex = ui->drag_ey = -1; + ui->cursor_active = FALSE; + ui->curx = ui->cury = 1; + + 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) +{ +} + +#define PREFERRED_TILE_SIZE 30 +#define HALFSZ (ds->sz6*3) +#define THIRDSZ (ds->sz6*2) +#define TILE_SIZE (ds->sz6*6) + +#define BORDER (TILE_SIZE/8) +#define BORDER_WIDTH (max(TILE_SIZE / 32, 1)) + +#define COORD(x) ( (x+1) * TILE_SIZE + BORDER ) +#define CENTERED_COORD(x) ( COORD(x) + TILE_SIZE/2 ) +#define FROMCOORD(x) ( ((x) < BORDER) ? -1 : ( ((x) - BORDER) / TILE_SIZE) - 1 ) + +#define DS_DSHIFT 4 /* R/U/L/D shift, for drag-in-progress flags */ + +#define DS_ERROR (1 << 8) +#define DS_CLUE (1 << 9) +#define DS_NOTRACK (1 << 10) +#define DS_FLASH (1 << 11) +#define DS_CURSOR (1 << 12) /* cursor in square (centre, or on edge) */ +#define DS_TRACK (1 << 13) +#define DS_CLEARING (1 << 14) + +#define DS_NSHIFT 16 /* R/U/L/D shift, for no-track edge flags */ +#define DS_CSHIFT 20 /* R/U/L/D shift, for cursor-on-edge */ + +struct game_drawstate { + int sz6; + int started; + + int w, h, sz; + unsigned int *flags, *flags_drag; + int *num_errors; +}; + +static void update_ui_drag(const game_state *state, game_ui *ui, int gx, int gy) +{ + int w = state->p.w, h = state->p.h; + int dx = abs(ui->drag_sx - gx), dy = abs(ui->drag_sy - gy); + + if (dy == 0) { + ui->drag_ex = gx < 0 ? 0 : gx >= w ? w-1 : gx; + ui->drag_ey = ui->drag_sy; + ui->dragging = TRUE; + } else if (dx == 0) { + ui->drag_ex = ui->drag_sx; + ui->drag_ey = gy < 0 ? 0 : gy >= h ? h-1 : gy; + ui->dragging = TRUE; + } else { + ui->drag_ex = ui->drag_sx; + ui->drag_ey = ui->drag_sy; + ui->dragging = FALSE; + } +} + +static int ui_can_flip_edge(const game_state *state, int x, int y, int dir, + int notrack) +{ + int w = state->p.w /*, h = state->shared->h, sz = state->shared->sz */; + int x2 = x + DX(dir); + int y2 = y + DY(dir); + unsigned int sf1, sf2, ef; + + if (!INGRID(state, x, y) || !INGRID(state, x2, y2)) + return FALSE; + + sf1 = state->sflags[y*w + x]; + sf2 = state->sflags[y2*w + x2]; + if ( !notrack && ((sf1 & S_CLUE) || (sf2 & S_CLUE)) ) + return FALSE; + + ef = S_E_FLAGS(state, x, y, dir); + if (notrack) { + /* if we're going to _set_ NOTRACK (i.e. the flag is currently unset), + make sure the edge is not already set to TRACK. The adjacent squares + could be set to TRACK, because we don't know which edges the general + square setting refers to. */ + if (!(ef & E_NOTRACK) && (ef & E_TRACK)) + return FALSE; + } else { + if (!(ef & E_TRACK)) { + /* if we're going to _set_ TRACK, make sure neither adjacent square nor + the edge itself is already set to NOTRACK. */ + if ((sf1 & S_NOTRACK) || (sf2 & S_NOTRACK) || (ef & E_NOTRACK)) + return FALSE; + /* if we're going to _set_ TRACK, make sure neither adjacent square has + 2 track flags already. */ + if ((S_E_COUNT(state, x, y, E_TRACK) >= 2) || + (S_E_COUNT(state, x2, y2, E_TRACK) >= 2)) + return FALSE; + } + } + return TRUE; +} + +static int ui_can_flip_square(const game_state *state, int x, int y, int notrack) +{ + int w = state->p.w, trackc; + unsigned sf; + + if (!INGRID(state, x, y)) return FALSE; + sf = state->sflags[y*w+x]; + trackc = S_E_COUNT(state, x, y, E_TRACK); + + if (sf & S_CLUE) return FALSE; + + if (notrack) { + /* If we're setting S_NOTRACK, we cannot have either S_TRACK or any E_TRACK. */ + if (!(sf & S_NOTRACK) && ((sf & S_TRACK) || (trackc > 0))) + return FALSE; + } else { + /* If we're setting S_TRACK, we cannot have any S_NOTRACK (we could have + E_NOTRACK, though, because one or two wouldn't rule out a track) */ + if (!(sf & S_TRACK) && (sf & S_NOTRACK)) + return FALSE; + } + return TRUE; +} + +static char *edge_flip_str(const game_state *state, int x, int y, int dir, int notrack, char *buf) { + unsigned ef = S_E_FLAGS(state, x, y, dir); + char c; + + if (notrack) + c = (ef & E_NOTRACK) ? 'n' : 'N'; + else + c = (ef & E_TRACK) ? 't' : 'T'; + + sprintf(buf, "%c%c%d,%d", c, MOVECHAR(dir), x, y); + return dupstr(buf); +} + +static char *square_flip_str(const game_state *state, int x, int y, int notrack, char *buf) { + unsigned f = state->sflags[y*state->p.w+x]; + char c; + + if (notrack) + c = (f & E_NOTRACK) ? 'n' : 'N'; + else + c = (f & E_TRACK) ? 't' : 'T'; + + sprintf(buf, "%cS%d,%d", c, x, y); + return dupstr(buf); +} + +#define SIGN(x) ((x<0) ? -1 : (x>0)) + +static game_state *copy_and_apply_drag(const game_state *state, const game_ui *ui) +{ + game_state *after = dup_game(state); + int x1, y1, x2, y2, x, y, w = state->p.w; + unsigned f = ui->notrack ? S_NOTRACK : S_TRACK, ff; + + x1 = min(ui->drag_sx, ui->drag_ex); x2 = max(ui->drag_sx, ui->drag_ex); + y1 = min(ui->drag_sy, ui->drag_ey); y2 = max(ui->drag_sy, ui->drag_ey); + + /* actually either x1 == x2, or y1 == y2, but it's easier just to code + the nested loop. */ + for (x = x1; x <= x2; x++) { + for (y = y1; y <= y2; y++) { + ff = state->sflags[y*w+x]; + if (ui->clearing && !(ff & f)) + continue; /* nothing to do, clearing and already clear */ + else if (!ui->clearing && (ff & f)) + continue; /* nothing to do, setting and already set */ + else if (ui_can_flip_square(state, x, y, ui->notrack)) + after->sflags[y*w+x] ^= f; + } + } + return after; +} + +#define KEY_DIRECTION(btn) (\ + (btn) == CURSOR_DOWN ? D : (btn) == CURSOR_UP ? U :\ + (btn) == CURSOR_LEFT ? L : R) + +static char *interpret_move(const game_state *state, game_ui *ui, + const game_drawstate *ds, + int x, int y, int button) +{ + int w = state->p.w, h = state->p.h, direction; + int gx = FROMCOORD(x), gy = FROMCOORD(y); + char tmpbuf[80]; + + /* --- mouse operations --- */ + + if (IS_MOUSE_DOWN(button)) { + ui->cursor_active = FALSE; + ui->dragging = FALSE; + + if (!INGRID(state, gx, gy)) { + /* can't drag from off grid */ + return NULL; + } + + if (button == RIGHT_BUTTON) { + ui->notrack = TRUE; + ui->clearing = state->sflags[gy*w+gx] & S_NOTRACK; + } else { + ui->notrack = FALSE; + ui->clearing = state->sflags[gy*w+gx] & S_TRACK; + } + + ui->clickx = x; + ui->clicky = y; + ui->drag_sx = ui->drag_ex = gx; + ui->drag_sy = ui->drag_ey = gy; + + return ""; + } + + if (IS_MOUSE_DRAG(button)) { + ui->cursor_active = FALSE; + update_ui_drag(state, ui, gx, gy); + return ""; + } + + if (IS_MOUSE_RELEASE(button)) { + ui->cursor_active = FALSE; + if (ui->dragging && + (ui->drag_sx != ui->drag_ex || ui->drag_sy != ui->drag_ey)) { + game_state *dragged = copy_and_apply_drag(state, ui); + char *ret = move_string_diff(state, dragged, FALSE); + + ui->dragging = 0; + free_game(dragged); + + return ret; + } else { + int cx, cy; + + /* We might still have been dragging (and just done a one- + * square drag): cancel drag, so undo doesn't make it like + * a drag-in-progress. */ + ui->dragging = 0; + + /* Click (or tiny drag). Work out which edge we were + * closest to. */ + + /* + * We process clicks based on the mouse-down location, + * because that's more natural for a user to carefully + * control than the mouse-up. + */ + x = ui->clickx; + y = ui->clicky; + + cx = CENTERED_COORD(gx); + cy = CENTERED_COORD(gy); + + if (!INGRID(state, gx, gy) || FROMCOORD(x) != gx || FROMCOORD(y) != gy) + return ""; + + if (max(abs(x-cx),abs(y-cy)) < TILE_SIZE/4) { + if (ui_can_flip_square(state, gx, gy, button == RIGHT_RELEASE)) + return square_flip_str(state, gx, gy, button == RIGHT_RELEASE, tmpbuf); + return ""; + } else { + if (abs(x-cx) < abs(y-cy)) { + /* Closest to top/bottom edge. */ + direction = (y < cy) ? U : D; + } else { + /* Closest to left/right edge. */ + direction = (x < cx) ? L : R; + } + if (ui_can_flip_edge(state, gx, gy, direction, + button == RIGHT_RELEASE)) + return edge_flip_str(state, gx, gy, direction, + button == RIGHT_RELEASE, tmpbuf); + else + return ""; + } + } + } + + /* --- cursor/keyboard operations --- */ + + if (IS_CURSOR_MOVE(button)) { + int dx = (button == CURSOR_LEFT) ? -1 : ((button == CURSOR_RIGHT) ? +1 : 0); + int dy = (button == CURSOR_DOWN) ? +1 : ((button == CURSOR_UP) ? -1 : 0); + + if (!ui->cursor_active) { + ui->cursor_active = TRUE; + return ""; + } + + ui->curx = ui->curx + dx; + ui->cury = ui->cury + dy; + if ((ui->curx % 2 == 0) && (ui->cury % 2 == 0)) { + /* disallow cursor on square corners: centres and edges only */ + ui->curx += dx; ui->cury += dy; + } + ui->curx = min(max(ui->curx, 1), 2*w-1); + ui->cury = min(max(ui->cury, 1), 2*h-1); + return ""; + } + + if (IS_CURSOR_SELECT(button)) { + if (!ui->cursor_active) { + ui->cursor_active = TRUE; + return ""; + } + /* click on square corner does nothing (shouldn't get here) */ + if ((ui->curx % 2) == 0 && (ui->cury % 2 == 0)) + return ""; + + gx = ui->curx / 2; + gy = ui->cury / 2; + direction = ((ui->curx % 2) == 0) ? L : ((ui->cury % 2) == 0) ? U : 0; + + if (direction && + ui_can_flip_edge(state, gx, gy, direction, button == CURSOR_SELECT2)) + return edge_flip_str(state, gx, gy, direction, button == CURSOR_SELECT2, tmpbuf); + else if (!direction && + ui_can_flip_square(state, gx, gy, button == CURSOR_SELECT2)) + return square_flip_str(state, gx, gy, button == CURSOR_SELECT2, tmpbuf); + return ""; + } + +#if 0 + /* helps to debug the solver */ + if (button == 'H' || button == 'h') + return dupstr("H"); +#endif + + return NULL; +} + +static game_state *execute_move(const game_state *state, const char *move) +{ + int w = state->p.w, x, y, n, i; + char c, d; + unsigned f; + game_state *ret = dup_game(state); + + /* this is breaking the bank on GTK, which vsprintf's into a fixed-size buffer + * which is 4096 bytes long. vsnprintf needs a feature-test macro to use, faff. */ + /*debug(("move: %s\n", move));*/ + + while (*move) { + c = *move; + if (c == 'S') { + ret->used_solve = TRUE; + move++; + } else if (c == 'T' || c == 't' || c == 'N' || c == 'n') { + /* set track, clear track; set notrack, clear notrack */ + move++; + if (sscanf(move, "%c%d,%d%n", &d, &x, &y, &n) != 3) + goto badmove; + if (!INGRID(state, x, y)) goto badmove; + + f = (c == 'T' || c == 't') ? S_TRACK : S_NOTRACK; + + if (d == 'S') { + if (c == 'T' || c == 'N') + ret->sflags[y*w+x] |= f; + else + ret->sflags[y*w+x] &= ~f; + } else if (d == 'U' || d == 'D' || d == 'L' || d == 'R') { + for (i = 0; i < 4; i++) { + unsigned df = 1<tilesize' for macro expansion purposes */ + struct { + int sz6; + } ads, *ds = &ads; + ads.sz6 = tilesize/6; + + *x = (params->w+2) * TILE_SIZE + 2 * BORDER; + *y = (params->h+2) * TILE_SIZE + 2 * BORDER; +} + +static void game_set_size(drawing *dr, game_drawstate *ds, + const game_params *params, int tilesize) +{ + ds->sz6 = tilesize/6; +} + +enum { + COL_BACKGROUND, COL_LOWLIGHT, COL_HIGHLIGHT, + COL_TRACK_BACKGROUND = COL_LOWLIGHT, + COL_GRID, COL_CLUE, COL_CURSOR, + COL_TRACK, COL_TRACK_CLUE, COL_SLEEPER, + COL_DRAGON, COL_DRAGOFF, + COL_ERROR, COL_FLASH, + NCOLOURS +}; + +static float *game_colours(frontend *fe, int *ncolours) +{ + float *ret = snewn(3 * NCOLOURS, float); + int i; + + game_mkhighlight(fe, ret, COL_BACKGROUND, COL_HIGHLIGHT, COL_LOWLIGHT); + + for (i = 0; i < 3; i++) { + ret[COL_TRACK_CLUE * 3 + i] = 0.0F; + ret[COL_TRACK * 3 + i] = 0.5F; + ret[COL_CLUE * 3 + i] = 0.0F; + ret[COL_GRID * 3 + i] = 0.75F; + ret[COL_CURSOR * 3 + i] = 0.6F; + } + + ret[COL_SLEEPER * 3 + 0] = 0.5F; + ret[COL_SLEEPER * 3 + 1] = 0.4F; + ret[COL_SLEEPER * 3 + 2] = 0.1F; + + ret[COL_ERROR * 3 + 0] = 1.0F; + ret[COL_ERROR * 3 + 1] = 0.0F; + ret[COL_ERROR * 3 + 2] = 0.0F; + + ret[COL_DRAGON * 3 + 0] = 0.0F; + ret[COL_DRAGON * 3 + 1] = 0.0F; + ret[COL_DRAGON * 3 + 2] = 1.0F; + + ret[COL_DRAGOFF * 3 + 0] = 0.8F; + ret[COL_DRAGOFF * 3 + 1] = 0.8F; + ret[COL_DRAGOFF * 3 + 2] = 1.0F; + + ret[COL_FLASH * 3 + 0] = 1.0F; + ret[COL_FLASH * 3 + 1] = 1.0F; + ret[COL_FLASH * 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 i; + + ds->sz6 = 0; + ds->started = FALSE; + + ds->w = state->p.w; + ds->h = state->p.h; + ds->sz = ds->w*ds->h; + ds->flags = snewn(ds->sz, unsigned int); + ds->flags_drag = snewn(ds->sz, unsigned int); + for (i = 0; i < ds->sz; i++) + ds->flags[i] = ds->flags_drag[i] = 0; + + ds->num_errors = snewn(ds->w+ds->h, int); + for (i = 0; i < ds->w+ds->h; i++) + ds->num_errors[i] = 0; + + return ds; +} + +static void game_free_drawstate(drawing *dr, game_drawstate *ds) +{ + sfree(ds->flags); + sfree(ds->flags_drag); + sfree(ds->num_errors); + sfree(ds); +} + +static void draw_circle_sleepers(drawing *dr, game_drawstate *ds, + float cx, float cy, float r2, float thickness, int c) +{ + float qr6 = (float)PI/12, qr3 = (float)PI/6, th, x1, y1, x2, y2; + float t6 = THIRDSZ/2.0F, r1 = t6; + int i; + + for (i = 0; i < 12; i++) { + th = qr6 + (i*qr3); + x1 = r1*(float)cos(th); + x2 = r2*(float)cos(th); + y1 = r1*(float)sin(th); + y2 = r2*(float)sin(th); + draw_thick_line(dr, thickness, cx+x1, cy+y1, cx+x2, cy+y2, c); + } +} + +static void draw_thick_circle_outline(drawing *dr, float thickness, + float cx, float cy, float r, + int colour) +{ + float circ4 = 0.5F * (float)PI * r, ang, x1, y1, x2, y2; + int i, nseg; + + nseg = (int)(circ4 / 4.0F)*4; /* ensure a quarter-circle has a whole #segs */ + ang = 2.0F*(float)PI / nseg; + + for (i = 0; i < nseg; i++) { + float th = ang * i, th2 = ang * (i+1); + x1 = cx + r*(float)cos(th); + x2 = cx + r*(float)cos(th2); + y1 = cy + r*(float)sin(th); + y2 = cy + r*(float)sin(th2); + debug(("circ outline: x=%.2f -> %.2f, thick=%.2f", x1, x2, thickness)); + draw_thick_line(dr, thickness, x1, y1, x2, y2, colour); + } +} + +static void draw_tracks_specific(drawing *dr, game_drawstate *ds, + int x, int y, unsigned int flags, + int ctrack, int csleeper) +{ + float ox = (float)COORD(x), oy = (float)COORD(y), cx, cy; + float t1 = (float)TILE_SIZE, t3 = TILE_SIZE/3.0F, t6 = TILE_SIZE/6.0F; + int d, i; + float thick_track = TILE_SIZE/8.0F, thick_sleeper = TILE_SIZE/12.0F; + + if (flags == LR) { + for (i = 1; i <= 7; i+=2) { + cx = ox + TILE_SIZE/8.0F*i; + draw_thick_line(dr, thick_sleeper, + cx, oy+t6, cx, oy+t6+2*t3, csleeper); + } + draw_thick_line(dr, thick_track, ox, oy + t3, ox + TILE_SIZE, oy + t3, ctrack); + draw_thick_line(dr, thick_track, ox, oy + 2*t3, ox + TILE_SIZE, oy + 2*t3, ctrack); + return; + } + if (flags == UD) { + for (i = 1; i <= 7; i+=2) { + cy = oy + TILE_SIZE/8.0F*i; + draw_thick_line(dr, thick_sleeper, + ox+t6, cy, ox+t6+2*t3, cy, csleeper); + } + debug(("vert line: x=%.2f, thick=%.2f", ox + t3, thick_track)); + draw_thick_line(dr, thick_track, ox + t3, oy, ox + t3, oy + TILE_SIZE, ctrack); + draw_thick_line(dr, thick_track, ox + 2*t3, oy, ox + 2*t3, oy + TILE_SIZE, ctrack); + return; + } + if (flags == UL || flags == DL || flags == UR || flags == DR) { + cx = (flags & L) ? ox : ox + TILE_SIZE; + cy = (flags & U) ? oy : oy + TILE_SIZE; + + draw_circle_sleepers(dr, ds, cx, cy, (float)(5*t6), thick_sleeper, csleeper); + + draw_thick_circle_outline(dr, thick_track, (float)cx, (float)cy, + 2*t3, ctrack); + draw_thick_circle_outline(dr, thick_track, (float)cx, (float)cy, + t3, ctrack); + + return; + } + + for (d = 1; d < 16; d *= 2) { + float ox1 = 0, ox2 = 0, oy1 = 0, oy2 = 0; + + if (!(flags & d)) continue; + + for (i = 1; i <= 2; i++) { + if (d == L) { + ox1 = 0; + ox2 = thick_track; + oy1 = oy2 = i*t3; + } else if (d == R) { + ox1 = t1; + ox2 = t1 - thick_track; + oy1 = oy2 = i*t3; + } else if (d == U) { + ox1 = ox2 = i*t3; + oy1 = 0; + oy2 = thick_track; + } else if (d == D) { + ox1 = ox2 = i*t3; + oy1 = t1; + oy2 = t1 - thick_track; + } + draw_thick_line(dr, thick_track, ox+ox1, oy+oy1, ox+ox2, oy+oy2, ctrack); + } + } +} + +static unsigned int best_bits(unsigned int flags, unsigned int flags_drag, int *col) +{ + int nb_orig = nbits[flags & ALLDIR], nb_drag = nbits[flags_drag & ALLDIR]; + + if (nb_orig > nb_drag) { + *col = COL_DRAGOFF; + return flags & ALLDIR; + } else if (nb_orig < nb_drag) { + *col = COL_DRAGON; + return flags_drag & ALLDIR; + } + return flags & ALLDIR; /* same number of bits: no special colour. */ +} + +static void draw_square(drawing *dr, game_drawstate *ds, + int x, int y, unsigned int flags, unsigned int flags_drag) +{ + int t2 = HALFSZ, t16 = HALFSZ/4, off; + int ox = COORD(x), oy = COORD(y), cx = ox + t2, cy = oy + t2, d, c; + int bg = (flags & DS_TRACK) ? COL_TRACK_BACKGROUND : COL_BACKGROUND; + unsigned int flags_best; + + assert(dr); + + /* Clip to the grid square. */ + clip(dr, ox, oy, TILE_SIZE, TILE_SIZE); + + /* Clear the square. */ + best_bits((flags & DS_TRACK) == DS_TRACK, + (flags_drag & DS_TRACK) == DS_TRACK, &bg); + draw_rect(dr, ox, oy, TILE_SIZE, TILE_SIZE, bg); + + /* Draw outline of grid square */ + draw_line(dr, ox, oy, COORD(x+1), oy, COL_GRID); + draw_line(dr, ox, oy, ox, COORD(y+1), COL_GRID); + + /* More outlines for clue squares. */ + if (flags & DS_CURSOR) { + int curx, cury, curw, curh; + + off = t16; + curx = ox + off; cury = oy + off; + curw = curh = TILE_SIZE - (2*off) + 1; + + if (flags & (U << DS_CSHIFT)) { + cury = oy - off; curh = 2*off + 1; + } else if (flags & (D << DS_CSHIFT)) { + cury = oy + TILE_SIZE - off; curh = 2*off + 1; + } else if (flags & (L << DS_CSHIFT)) { + curx = ox - off; curw = 2*off + 1; + } else if (flags & (R << DS_CSHIFT)) { + curx = ox + TILE_SIZE - off; curw = 2*off + 1; + } + + draw_rect_outline(dr, curx, cury, curw, curh, COL_GRID); + } + + /* Draw tracks themselves */ + c = (flags & DS_ERROR) ? COL_ERROR : + (flags & DS_FLASH) ? COL_FLASH : + (flags & DS_CLUE) ? COL_TRACK_CLUE : COL_TRACK; + flags_best = best_bits(flags, flags_drag, &c); + draw_tracks_specific(dr, ds, x, y, flags_best, c, COL_SLEEPER); + + /* Draw no-track marks, if present, in square and on edges. */ + c = COL_TRACK; + flags_best = best_bits((flags & DS_NOTRACK) == DS_NOTRACK, + (flags_drag & DS_NOTRACK) == DS_NOTRACK, &c); + if (flags_best) { + off = HALFSZ/2; + draw_line(dr, cx - off, cy - off, cx + off, cy + off, c); + draw_line(dr, cx - off, cy + off, cx + off, cy - off, c); + } + + c = COL_TRACK; + flags_best = best_bits(flags >> DS_NSHIFT, flags_drag >> DS_NSHIFT, &c); + for (d = 1; d < 16; d *= 2) { + off = t16; + cx = ox + t2; + cy = oy + t2; + + if (flags_best & d) { + cx += (d == R) ? t2 : (d == L) ? -t2 : 0; + cy += (d == D) ? t2 : (d == U) ? -t2 : 0; + + draw_line(dr, cx - off, cy - off, cx + off, cy + off, c); + draw_line(dr, cx - off, cy + off, cx + off, cy - off, c); + } + } + + unclip(dr); + draw_update(dr, ox, oy, TILE_SIZE, TILE_SIZE); +} + +static void draw_clue(drawing *dr, game_drawstate *ds, int w, int clue, int i, int col) +{ + int cx, cy, tsz = TILE_SIZE/2; + char buf[20]; + + if (i < w) { + cx = CENTERED_COORD(i); + cy = CENTERED_COORD(-1); + } else { + cx = CENTERED_COORD(w); + cy = CENTERED_COORD(i-w); + } + + draw_rect(dr, cx - tsz + BORDER, cy - tsz + BORDER, + TILE_SIZE - BORDER, TILE_SIZE - BORDER, COL_BACKGROUND); + sprintf(buf, "%d", clue); + draw_text(dr, cx, cy, FONT_VARIABLE, tsz, ALIGN_VCENTRE|ALIGN_HCENTRE, + col, buf); + draw_update(dr, cx - tsz, cy - tsz, TILE_SIZE, TILE_SIZE); +} + +static void draw_loop_ends(drawing *dr, game_drawstate *ds, + const game_state *state, int c) +{ + int tsz = TILE_SIZE/2; + + draw_text(dr, CENTERED_COORD(-1), CENTERED_COORD(state->numbers->row_s), + FONT_VARIABLE, tsz, ALIGN_VCENTRE|ALIGN_HCENTRE, + c, "A"); + + draw_text(dr, CENTERED_COORD(state->numbers->col_s), CENTERED_COORD(state->p.h), + FONT_VARIABLE, tsz, ALIGN_VCENTRE|ALIGN_HCENTRE, + c, "B"); +} + +static unsigned int s2d_flags(const game_state *state, int x, int y, const game_ui *ui) +{ + unsigned int f; + int w = state->p.w; + + f = S_E_DIRS(state, x, y, E_TRACK); + f |= (S_E_DIRS(state, x, y, E_NOTRACK) << DS_NSHIFT); + + if (state->sflags[y*w+x] & S_ERROR) + f |= DS_ERROR; + if (state->sflags[y*w+x] & S_CLUE) + f |= DS_CLUE; + if (state->sflags[y*w+x] & S_NOTRACK) + f |= DS_NOTRACK; + if ((state->sflags[y*w+x] & S_TRACK) || (S_E_COUNT(state, x, y, E_TRACK) > 0)) + f |= DS_TRACK; + + if (ui->cursor_active) { + if (ui->curx >= x*2 && ui->curx <= (x+1)*2 && + ui->cury >= y*2 && ui->cury <= (y+1)*2) { + f |= DS_CURSOR; + if (ui->curx == x*2) f |= (L << DS_CSHIFT); + if (ui->curx == (x+1)*2) f |= (R << DS_CSHIFT); + if (ui->cury == y*2) f |= (U << DS_CSHIFT); + if (ui->cury == (y+1)*2) f |= (D << DS_CSHIFT); + } + } + + return f; +} + +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 i, x, y, force = 0, flashing = 0, w = ds->w, h = ds->h; + game_state *drag_state = NULL; + + if (!ds->started) { + /* + * The initial contents of the window are not guaranteed and + * can vary with front ends. To be on the safe side, all games + * should start by drawing a big background-colour rectangle + * covering the whole window. + */ + draw_rect(dr, 0, 0, (w+2)*TILE_SIZE + 2*BORDER, (h+2)*TILE_SIZE + 2*BORDER, + COL_BACKGROUND); + + draw_loop_ends(dr, ds, state, COL_CLUE); + + draw_line(dr, COORD(ds->w), COORD(0), COORD(ds->w), COORD(ds->h), COL_GRID); + draw_line(dr, COORD(0), COORD(ds->h), COORD(ds->w), COORD(ds->h), COL_GRID); + + draw_update(dr, 0, 0, (w+2)*TILE_SIZE + 2*BORDER, (h+2)*TILE_SIZE + 2*BORDER); + + ds->started = TRUE; + force = 1; + } + + for (i = 0; i < w+h; i++) { + if (force || (state->num_errors[i] != ds->num_errors[i])) { + ds->num_errors[i] = state->num_errors[i]; + draw_clue(dr, ds, w, state->numbers->numbers[i], i, + ds->num_errors[i] ? COL_ERROR : COL_CLUE); + } + } + + if (flashtime > 0 && + (flashtime <= FLASH_TIME/3 || + flashtime >= FLASH_TIME*2/3)) + flashing = DS_FLASH; + + if (ui->dragging) + drag_state = copy_and_apply_drag(state, ui); + + for (x = 0; x < w; x++) { + for (y = 0; y < h; y++) { + unsigned int f, f_d; + + f = s2d_flags(state, x, y, ui) | flashing; + f_d = drag_state ? s2d_flags(drag_state, x, y, ui) : f; + + if (f != ds->flags[y*w+x] || f_d != ds->flags_drag[y*w+x] || force) { + ds->flags[y*w+x] = f; + ds->flags_drag[y*w+x] = f_d; + draw_square(dr, ds, x, y, f, f_d); + } + } + } + + if (drag_state) free_game(drag_state); +} + +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(const game_state *oldstate, const game_state *newstate, + int dir, game_ui *ui) +{ + if (!oldstate->completed && + newstate->completed && !newstate->used_solve) + return FLASH_TIME; + else + return 0.0F; +} + +static int game_status(const game_state *state) +{ + return state->completed ? +1 : 0; +} + +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; + + /* The Times uses 7mm squares */ + game_compute_size(params, 700, &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->p.w, h = state->p.h; + int black = print_mono_colour(dr, 0), grey = print_grey_colour(dr, 0.5F); + int x, y, i; + + /* Ick: fake up `ds->tilesize' for macro expansion purposes */ + game_drawstate ads, *ds = &ads; + game_set_size(dr, ds, NULL, tilesize); + + /* Grid, then border (second so it is on top) */ + print_line_width(dr, TILE_SIZE / 24); + for (x = 1; x < w; x++) + draw_line(dr, COORD(x), COORD(0), COORD(x), COORD(h), grey); + for (y = 1; y < h; y++) + draw_line(dr, COORD(0), COORD(y), COORD(w), COORD(y), grey); + + print_line_width(dr, TILE_SIZE / 16); + draw_rect_outline(dr, COORD(0), COORD(0), w*TILE_SIZE, h*TILE_SIZE, black); + + print_line_width(dr, TILE_SIZE / 24); + + /* clue numbers, and loop ends */ + for (i = 0; i < w+h; i++) + draw_clue(dr, ds, w, state->numbers->numbers[i], i, black); + draw_loop_ends(dr, ds, state, black); + + /* clue tracks / solution */ + for (x = 0; x < w; x++) { + for (y = 0; y < h; y++) { + clip(dr, COORD(x), COORD(y), TILE_SIZE, TILE_SIZE); + draw_tracks_specific(dr, ds, x, y, S_E_DIRS(state, x, y, E_TRACK), + black, grey); + unclip(dr); + } + } +} + +#ifdef COMBINED +#define thegame tracks +#endif + +const struct game thegame = { + "Train Tracks", "games.tracks", "tracks", + default_params, + game_fetch_preset, NULL, + 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_TILE_SIZE, game_compute_size, game_set_size, + game_colours, + game_new_drawstate, + game_free_drawstate, + game_redraw, + game_anim_length, + game_flash_length, + game_status, + TRUE, FALSE, game_print_size, game_print, + FALSE, /* wants_statusbar */ + FALSE, game_timing_state, + 0, /* flags */ +}; + +/* vim: set shiftwidth=4 tabstop=8: */ -- cgit v1.2.3