* some confusing conditions.
*
* TODO:
- *
- * - error highlighting?
- * * highlighting adjacent tents is easy
- * * highlighting violated numeric clues is almost as easy
- * (might want to pay attention to NONTENTs here)
- * * but how in hell do we highlight a failure of maxflow
- * during completion checking?
- * + well, the _obvious_ approach is to use maxflow's own
- * error report: it will provide, via the `cut' parameter,
- * a set of trees which have too few tents between them.
- * It's unclear that this will be particularly obvious to
- * a user, however. Is there any other way?
- *
+ *
* - it might be nice to make setter-provided tent/nontent clues
* inviolable?
* * on the other hand, this would introduce considerable extra
COL_TREETRUNK,
COL_TREELEAF,
COL_TENT,
+ COL_ERROR,
+ COL_ERRTEXT,
+ COL_ERRTRUNK,
NCOLOURS
};
sfree(params);
}
-static game_params *dup_params(game_params *params)
+static game_params *dup_params(const game_params *params)
{
game_params *ret = snew(game_params);
*ret = *params; /* structure copy */
}
}
-static char *encode_params(game_params *params, int full)
+static char *encode_params(const game_params *params, int full)
{
char buf[120];
return dupstr(buf);
}
-static config_item *game_configure(game_params *params)
+static config_item *game_configure(const game_params *params)
{
config_item *ret;
char buf[80];
return ret;
}
-static game_params *custom_params(config_item *cfg)
+static game_params *custom_params(const config_item *cfg)
{
game_params *ret = snew(game_params);
return ret;
}
-static char *validate_params(game_params *params, int full)
+static char *validate_params(const game_params *params, int full)
{
/*
* Generating anything under 4x4 runs into trouble of one kind
char *soln, struct solver_scratch *sc, int diff)
{
int x, y, d, i, j;
- char *mrow, *mrow1, *mrow2, *trow, *trow1, *trow2;
+ char *mrow, *trow, *trow1, *trow2;
/*
* Set up solver data.
* hasn't been set up yet.
*/
mrow = sc->mrows;
- mrow1 = sc->mrows + len;
- mrow2 = sc->mrows + 2*len;
trow = sc->trows;
trow1 = sc->trows + len;
trow2 = sc->trows + 2*len;
return 1;
}
-static char *new_game_desc(game_params *params, random_state *rs,
+static char *new_game_desc(const game_params *params_in, random_state *rs,
char **aux, int interactive)
{
+ game_params params_copy = *params_in; /* structure copy */
+ game_params *params = ¶ms_copy;
int w = params->w, h = params->h;
int ntrees = w * h / 5;
char *grid = snewn(w*h, char);
j = maxflow(w*h+2, w*h+1, w*h, nedges, edges, capacity, flow, NULL);
if (j < ntrees)
- continue; /* couldn't place all the tents */
+ continue; /* couldn't place all the trees */
/*
* We've placed the trees. Now we need to work out _where_
return ret;
}
-static char *validate_desc(game_params *params, char *desc)
+static char *validate_desc(const game_params *params, const char *desc)
{
int w = params->w, h = params->h;
int area, i;
desc++;
}
+ if (area < w * h + 1)
+ return "Not enough data to fill grid";
+ else if (area > w * h + 1)
+ return "Too much data to fill grid";
for (i = 0; i < w+h; i++) {
if (!*desc)
return NULL;
}
-static game_state *new_game(midend *me, game_params *params, char *desc)
+static game_state *new_game(midend *me, const game_params *params,
+ const char *desc)
{
int w = params->w, h = params->h;
game_state *state = snew(game_state);
return state;
}
-static game_state *dup_game(game_state *state)
+static game_state *dup_game(const game_state *state)
{
int w = state->p.w, h = state->p.h;
game_state *ret = snew(game_state);
sfree(state);
}
-static char *solve_game(game_state *state, game_state *currstate,
- char *aux, char **error)
+static char *solve_game(const game_state *state, const game_state *currstate,
+ const char *aux, char **error)
{
int w = state->p.w, h = state->p.h;
}
}
-static char *game_text_format(game_state *state)
+static int game_can_format_as_text_now(const game_params *params)
{
- int w = state->p.w, h = state->p.h;
- char *ret, *p;
- int x, y;
+ return params->w <= 1998 && params->h <= 1998; /* 999 tents */
+}
- /*
- * FIXME: We currently do not print the numbers round the edges
- * of the grid. I need to work out a sensible way of doing this
- * even when the column numbers exceed 9.
- *
- * In the absence of those numbers, the result size is h lines
- * of w+1 characters each, plus a NUL.
- *
- * This function is currently only used by the standalone
- * solver; until I make it look more sensible, I won't enable
- * it in the main game structure.
- */
- ret = snewn(h*(w+1) + 1, char);
- p = ret;
- for (y = 0; y < h; y++) {
- for (x = 0; x < w; x++) {
- *p = (state->grid[y*w+x] == BLANK ? '.' :
- state->grid[y*w+x] == TREE ? 'T' :
- state->grid[y*w+x] == TENT ? '*' :
- state->grid[y*w+x] == NONTENT ? '-' : '?');
- p++;
+static char *game_text_format(const game_state *state)
+{
+ int w = state->p.w, h = state->p.h, r, c;
+ int cw = 4, ch = 2, gw = (w+1)*cw + 2, gh = (h+1)*ch + 1, len = gw * gh;
+ char *board = snewn(len + 1, char);
+
+ sprintf(board, "%*s\n", len - 2, "");
+ for (r = 0; r <= h; ++r) {
+ for (c = 0; c <= w; ++c) {
+ int cell = r*ch*gw + cw*c, center = cell + gw*ch/2 + cw/2;
+ int i = r*w + c, n = 1000;
+
+ if (r == h && c == w) /* NOP */;
+ else if (c == w) n = state->numbers->numbers[w + r];
+ else if (r == h) n = state->numbers->numbers[c];
+ else switch (state->grid[i]) {
+ case BLANK: board[center] = '.'; break;
+ case TREE: board[center] = 'T'; break;
+ case TENT: memcpy(board + center - 1, "//\\", 3); break;
+ case NONTENT: break;
+ default: memcpy(board + center - 1, "wtf", 3);
+ }
+
+ if (n < 100) {
+ board[center] = '0' + n % 10;
+ if (n >= 10) board[center - 1] = '0' + n / 10;
+ } else if (n < 1000) {
+ board[center + 1] = '0' + n % 10;
+ board[center] = '0' + n / 10 % 10;
+ board[center - 1] = '0' + n / 100;
+ }
+
+ board[cell] = '+';
+ memset(board + cell + 1, '-', cw - 1);
+ for (i = 1; i < ch; ++i) board[cell + i*gw] = '|';
+ }
+
+ for (c = 0; c < ch; ++c) {
+ board[(r*ch+c)*gw + gw - 2] =
+ c == 0 ? '+' : r < h ? '|' : ' ';
+ board[(r*ch+c)*gw + gw - 1] = '\n';
}
- *p++ = '\n';
}
- *p++ = '\0';
- return ret;
+ memset(board + len - gw, '-', gw - 2 - cw);
+ for (c = 0; c <= w; ++c) board[len - gw + cw*c] = '+';
+
+ return board;
}
struct game_ui {
int dex, dey; /* coords of drag end */
int drag_button; /* -1 for none, or a button code */
int drag_ok; /* dragged off the window, to cancel */
+
+ int cx, cy, cdisp; /* cursor position, and ?display. */
};
-static game_ui *new_ui(game_state *state)
+static game_ui *new_ui(const game_state *state)
{
game_ui *ui = snew(game_ui);
ui->dsx = ui->dsy = -1;
ui->dex = ui->dey = -1;
ui->drag_button = -1;
ui->drag_ok = FALSE;
+ ui->cx = ui->cy = ui->cdisp = 0;
return ui;
}
sfree(ui);
}
-static char *encode_ui(game_ui *ui)
+static char *encode_ui(const game_ui *ui)
{
return NULL;
}
-static void decode_ui(game_ui *ui, char *encoding)
+static void decode_ui(game_ui *ui, const char *encoding)
{
}
-static void game_changed_state(game_ui *ui, game_state *oldstate,
- game_state *newstate)
+static void game_changed_state(game_ui *ui, const game_state *oldstate,
+ const game_state *newstate)
{
}
int tilesize;
int started;
game_params p;
- char *drawn;
+ int *drawn, *numbersdrawn;
+ int cx, cy; /* last-drawn cursor pos, or (-1,-1) if absent. */
};
#define PREFERRED_TILESIZE 32
#define FLASH_TIME 0.30F
-static int drag_xform(game_ui *ui, int x, int y, int v)
+static int drag_xform(const game_ui *ui, int x, int y, int v)
{
int xmin, ymin, xmax, ymax;
ymin = min(ui->dsy, ui->dey);
ymax = max(ui->dsy, ui->dey);
+#ifndef STYLUS_BASED
/*
* Left-dragging has no effect, so we treat a left-drag as a
* single click on dsx,dsy.
xmin = xmax = ui->dsx;
ymin = ymax = ui->dsy;
}
+#endif
if (x < xmin || x > xmax || y < ymin || y > ymax)
return v; /* no change outside drag area */
* Results of a simple click. Left button sets blanks to
* tents; right button sets blanks to non-tents; either
* button clears a non-blank square.
+ * If stylus-based however, it loops instead.
*/
if (ui->drag_button == LEFT_BUTTON)
+#ifdef STYLUS_BASED
+ v = (v == BLANK ? TENT : (v == TENT ? NONTENT : BLANK));
+ else
+ v = (v == BLANK ? NONTENT : (v == NONTENT ? TENT : BLANK));
+#else
v = (v == BLANK ? TENT : BLANK);
else
v = (v == BLANK ? NONTENT : BLANK);
+#endif
} else {
/*
* Results of a drag. Left-dragging has no effect.
if (ui->drag_button == RIGHT_BUTTON)
v = (v == BLANK ? NONTENT : v);
else
+#ifdef STYLUS_BASED
+ v = (v == BLANK ? NONTENT : v);
+#else
/* do nothing */;
+#endif
}
return v;
}
-static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds,
- int x, int y, int button)
+static char *interpret_move(const game_state *state, game_ui *ui,
+ const game_drawstate *ds,
+ int x, int y, int button)
{
int w = state->p.w, h = state->p.h;
+ char tmpbuf[80];
+ int shift = button & MOD_SHFT, control = button & MOD_CTRL;
+
+ button &= ~MOD_MASK;
if (button == LEFT_BUTTON || button == RIGHT_BUTTON) {
x = FROMCOORD(x);
ui->dsx = ui->dex = x;
ui->dsy = ui->dey = y;
ui->drag_ok = TRUE;
+ ui->cdisp = 0;
return ""; /* ui updated */
}
if ((IS_MOUSE_DRAG(button) || IS_MOUSE_RELEASE(button)) &&
ui->drag_button > 0) {
int xmin, ymin, xmax, ymax;
- char *buf, *sep, tmpbuf[80];
+ char *buf, *sep;
int buflen, bufsize, tmplen;
x = FROMCOORD(x);
}
}
+ if (IS_CURSOR_MOVE(button)) {
+ ui->cdisp = 1;
+ if (shift || control) {
+ int len = 0, i, indices[2];
+ indices[0] = ui->cx + w * ui->cy;
+ move_cursor(button, &ui->cx, &ui->cy, w, h, 0);
+ indices[1] = ui->cx + w * ui->cy;
+
+ /* NONTENTify all unique traversed eligible squares */
+ for (i = 0; i <= (indices[0] != indices[1]); ++i)
+ if (state->grid[indices[i]] == BLANK ||
+ (control && state->grid[indices[i]] == TENT)) {
+ len += sprintf(tmpbuf + len, "%sN%d,%d", len ? ";" : "",
+ indices[i] % w, indices[i] / w);
+ assert(len < lenof(tmpbuf));
+ }
+
+ tmpbuf[len] = '\0';
+ if (len) return dupstr(tmpbuf);
+ } else
+ move_cursor(button, &ui->cx, &ui->cy, w, h, 0);
+ return "";
+ }
+ if (ui->cdisp) {
+ char rep = 0;
+ int v = state->grid[ui->cy*w+ui->cx];
+
+ if (v != TREE) {
+#ifdef SINGLE_CURSOR_SELECT
+ if (button == CURSOR_SELECT)
+ /* SELECT cycles T, N, B */
+ rep = v == BLANK ? 'T' : v == TENT ? 'N' : 'B';
+#else
+ if (button == CURSOR_SELECT)
+ rep = v == BLANK ? 'T' : 'B';
+ else if (button == CURSOR_SELECT2)
+ rep = v == BLANK ? 'N' : 'B';
+ else if (button == 'T' || button == 'N' || button == 'B')
+ rep = (char)button;
+#endif
+ }
+
+ if (rep) {
+ sprintf(tmpbuf, "%c%d,%d", (int)rep, ui->cx, ui->cy);
+ return dupstr(tmpbuf);
+ }
+ } else if (IS_CURSOR_SELECT(button)) {
+ ui->cdisp = 1;
+ return "";
+ }
+
return NULL;
}
-static game_state *execute_move(game_state *state, char *move)
+static game_state *execute_move(const game_state *state, const char *move)
{
int w = state->p.w, h = state->p.h;
char c;
* Drawing routines.
*/
-static void game_compute_size(game_params *params, int tilesize,
- int *x, int *y)
+static void game_compute_size(const game_params *params, int tilesize,
+ int *x, int *y)
{
/* fool the macros */
- struct dummy { int tilesize; } dummy = { tilesize }, *ds = &dummy;
+ struct dummy { int tilesize; } dummy, *ds = &dummy;
+ dummy.tilesize = tilesize;
*x = TLBORDER + BRBORDER + TILESIZE * params->w;
*y = TLBORDER + BRBORDER + TILESIZE * params->h;
}
static void game_set_size(drawing *dr, game_drawstate *ds,
- game_params *params, int tilesize)
+ const game_params *params, int tilesize)
{
ds->tilesize = tilesize;
}
ret[COL_TENT * 3 + 1] = 0.7F;
ret[COL_TENT * 3 + 2] = 0.0F;
+ ret[COL_ERROR * 3 + 0] = 1.0F;
+ ret[COL_ERROR * 3 + 1] = 0.0F;
+ ret[COL_ERROR * 3 + 2] = 0.0F;
+
+ ret[COL_ERRTEXT * 3 + 0] = 1.0F;
+ ret[COL_ERRTEXT * 3 + 1] = 1.0F;
+ ret[COL_ERRTEXT * 3 + 2] = 1.0F;
+
+ ret[COL_ERRTRUNK * 3 + 0] = 0.6F;
+ ret[COL_ERRTRUNK * 3 + 1] = 0.0F;
+ ret[COL_ERRTRUNK * 3 + 2] = 0.0F;
+
*ncolours = NCOLOURS;
return ret;
}
-static game_drawstate *game_new_drawstate(drawing *dr, game_state *state)
+static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state)
{
int w = state->p.w, h = state->p.h;
struct game_drawstate *ds = snew(struct game_drawstate);
+ int i;
ds->tilesize = 0;
ds->started = FALSE;
ds->p = state->p; /* structure copy */
- ds->drawn = snewn(w*h, char);
- memset(ds->drawn, MAGIC, w*h);
+ ds->drawn = snewn(w*h, int);
+ for (i = 0; i < w*h; i++)
+ ds->drawn[i] = MAGIC;
+ ds->numbersdrawn = snewn(w+h, int);
+ for (i = 0; i < w+h; i++)
+ ds->numbersdrawn[i] = 2;
+ ds->cx = ds->cy = -1;
return ds;
}
static void game_free_drawstate(drawing *dr, game_drawstate *ds)
{
sfree(ds->drawn);
+ sfree(ds->numbersdrawn);
sfree(ds);
}
+enum {
+ ERR_ADJ_TOPLEFT = 4,
+ ERR_ADJ_TOP,
+ ERR_ADJ_TOPRIGHT,
+ ERR_ADJ_LEFT,
+ ERR_ADJ_RIGHT,
+ ERR_ADJ_BOTLEFT,
+ ERR_ADJ_BOT,
+ ERR_ADJ_BOTRIGHT,
+ ERR_OVERCOMMITTED
+};
+
+static int *find_errors(const game_state *state, char *grid)
+{
+ int w = state->p.w, h = state->p.h;
+ int *ret = snewn(w*h + w + h, int);
+ int *tmp = snewn(w*h*2, int), *dsf = tmp + w*h;
+ int x, y;
+
+ /*
+ * This function goes through a grid and works out where to
+ * highlight play errors in red. The aim is that it should
+ * produce at least one error highlight for any complete grid
+ * (or complete piece of grid) violating a puzzle constraint, so
+ * that a grid containing no BLANK squares is either a win or is
+ * marked up in some way that indicates why not.
+ *
+ * So it's easy enough to highlight errors in the numeric clues
+ * - just light up any row or column number which is not
+ * fulfilled - and it's just as easy to highlight adjacent
+ * tents. The difficult bit is highlighting failures in the
+ * tent/tree matching criterion.
+ *
+ * A natural approach would seem to be to apply the maxflow
+ * algorithm to find the tent/tree matching; if this fails, it
+ * must necessarily terminate with a min-cut which can be
+ * reinterpreted as some set of trees which have too few tents
+ * between them (or vice versa). However, it's bad for
+ * localising errors, because it's not easy to make the
+ * algorithm narrow down to the _smallest_ such set of trees: if
+ * trees A and B have only one tent between them, for instance,
+ * it might perfectly well highlight not only A and B but also
+ * trees C and D which are correctly matched on the far side of
+ * the grid, on the grounds that those four trees between them
+ * have only three tents.
+ *
+ * Also, that approach fares badly when you introduce the
+ * additional requirement that incomplete grids should have
+ * errors highlighted only when they can be proved to be errors
+ * - so that trees should not be marked as having too few tents
+ * if there are enough BLANK squares remaining around them that
+ * could be turned into the missing tents (to do so would be
+ * patronising, since the overwhelming likelihood is not that
+ * the player has forgotten to put a tree there but that they
+ * have merely not put one there _yet_). However, tents with too
+ * few trees can be marked immediately, since those are
+ * definitely player error.
+ *
+ * So I adopt an alternative approach, which is to consider the
+ * bipartite adjacency graph between trees and tents
+ * ('bipartite' in the sense that for these purposes I
+ * deliberately ignore two adjacent trees or two adjacent
+ * tents), divide that graph up into its connected components
+ * using a dsf, and look for components which contain different
+ * numbers of trees and tents. This allows me to highlight
+ * groups of tents with too few trees between them immediately,
+ * and then in order to find groups of trees with too few tents
+ * I redo the same process but counting BLANKs as potential
+ * tents (so that the only trees highlighted are those
+ * surrounded by enough NONTENTs to make it impossible to give
+ * them enough tents).
+ *
+ * However, this technique is incomplete: it is not a sufficient
+ * condition for the existence of a perfect matching that every
+ * connected component of the graph has the same number of tents
+ * and trees. An example of a graph which satisfies the latter
+ * condition but still has no perfect matching is
+ *
+ * A B C
+ * | / ,/|
+ * | / ,'/ |
+ * | / ,' / |
+ * |/,' / |
+ * 1 2 3
+ *
+ * which can be realised in Tents as
+ *
+ * B
+ * A 1 C 2
+ * 3
+ *
+ * The matching-error highlighter described above will not mark
+ * this construction as erroneous. However, something else will:
+ * the three tents in the above diagram (let us suppose A,B,C
+ * are the tents, though it doesn't matter which) contain two
+ * diagonally adjacent pairs. So there will be _an_ error
+ * highlighted for the above layout, even though not all types
+ * of error will be highlighted.
+ *
+ * And in fact we can prove that this will always be the case:
+ * that the shortcomings of the matching-error highlighter will
+ * always be made up for by the easy tent adjacency highlighter.
+ *
+ * Lemma: Let G be a bipartite graph between n trees and n
+ * tents, which is connected, and in which no tree has degree
+ * more than two (but a tent may). Then G has a perfect matching.
+ *
+ * (Note: in the statement and proof of the Lemma I will
+ * consistently use 'tree' to indicate a type of graph vertex as
+ * opposed to a tent, and not to indicate a tree in the graph-
+ * theoretic sense.)
+ *
+ * Proof:
+ *
+ * If we can find a tent of degree 1 joined to a tree of degree
+ * 2, then any perfect matching must pair that tent with that
+ * tree. Hence, we can remove both, leaving a smaller graph G'
+ * which still satisfies all the conditions of the Lemma, and
+ * which has a perfect matching iff G does.
+ *
+ * So, wlog, we may assume G contains no tent of degree 1 joined
+ * to a tree of degree 2; if it does, we can reduce it as above.
+ *
+ * If G has no tent of degree 1 at all, then every tent has
+ * degree at least two, so there are at least 2n edges in the
+ * graph. But every tree has degree at most two, so there are at
+ * most 2n edges. Hence there must be exactly 2n edges, so every
+ * tree and every tent must have degree exactly two, which means
+ * that the whole graph consists of a single loop (by
+ * connectedness), and therefore certainly has a perfect
+ * matching.
+ *
+ * Alternatively, if G does have a tent of degree 1 but it is
+ * not connected to a tree of degree 2, then the tree it is
+ * connected to must have degree 1 - and, by connectedness, that
+ * must mean that that tent and that tree between them form the
+ * entire graph. This trivial graph has a trivial perfect
+ * matching. []
+ *
+ * That proves the lemma. Hence, in any case where the matching-
+ * error highlighter fails to highlight an erroneous component
+ * (because it has the same number of tents as trees, but they
+ * cannot be matched up), the above lemma tells us that there
+ * must be a tree with degree more than 2, i.e. a tree
+ * orthogonally adjacent to at least three tents. But in that
+ * case, there must be some pair of those three tents which are
+ * diagonally adjacent to each other, so the tent-adjacency
+ * highlighter will necessarily show an error. So any filled
+ * layout in Tents which is not a correct solution to the puzzle
+ * must have _some_ error highlighted by the subroutine below.
+ *
+ * (Of course it would be nicer if we could highlight all
+ * errors: in the above example layout, we would like to
+ * highlight tents A,B as having too few trees between them, and
+ * trees 2,3 as having too few tents, in addition to marking the
+ * adjacency problems. But I can't immediately think of any way
+ * to find the smallest sets of such tents and trees without an
+ * O(2^N) loop over all subsets of a given component.)
+ */
+
+ /*
+ * ret[0] through to ret[w*h-1] give error markers for the grid
+ * squares. After that, ret[w*h] to ret[w*h+w-1] give error
+ * markers for the column numbers, and ret[w*h+w] to
+ * ret[w*h+w+h-1] for the row numbers.
+ */
+
+ /*
+ * Spot tent-adjacency violations.
+ */
+ for (x = 0; x < w*h; x++)
+ ret[x] = 0;
+ for (y = 0; y < h; y++) {
+ for (x = 0; x < w; x++) {
+ if (y+1 < h && x+1 < w &&
+ ((grid[y*w+x] == TENT &&
+ grid[(y+1)*w+(x+1)] == TENT) ||
+ (grid[(y+1)*w+x] == TENT &&
+ grid[y*w+(x+1)] == TENT))) {
+ ret[y*w+x] |= 1 << ERR_ADJ_BOTRIGHT;
+ ret[(y+1)*w+x] |= 1 << ERR_ADJ_TOPRIGHT;
+ ret[y*w+(x+1)] |= 1 << ERR_ADJ_BOTLEFT;
+ ret[(y+1)*w+(x+1)] |= 1 << ERR_ADJ_TOPLEFT;
+ }
+ if (y+1 < h &&
+ grid[y*w+x] == TENT &&
+ grid[(y+1)*w+x] == TENT) {
+ ret[y*w+x] |= 1 << ERR_ADJ_BOT;
+ ret[(y+1)*w+x] |= 1 << ERR_ADJ_TOP;
+ }
+ if (x+1 < w &&
+ grid[y*w+x] == TENT &&
+ grid[y*w+(x+1)] == TENT) {
+ ret[y*w+x] |= 1 << ERR_ADJ_RIGHT;
+ ret[y*w+(x+1)] |= 1 << ERR_ADJ_LEFT;
+ }
+ }
+ }
+
+ /*
+ * Spot numeric clue violations.
+ */
+ for (x = 0; x < w; x++) {
+ int tents = 0, maybetents = 0;
+ for (y = 0; y < h; y++) {
+ if (grid[y*w+x] == TENT)
+ tents++;
+ else if (grid[y*w+x] == BLANK)
+ maybetents++;
+ }
+ ret[w*h+x] = (tents > state->numbers->numbers[x] ||
+ tents + maybetents < state->numbers->numbers[x]);
+ }
+ for (y = 0; y < h; y++) {
+ int tents = 0, maybetents = 0;
+ for (x = 0; x < w; x++) {
+ if (grid[y*w+x] == TENT)
+ tents++;
+ else if (grid[y*w+x] == BLANK)
+ maybetents++;
+ }
+ ret[w*h+w+y] = (tents > state->numbers->numbers[w+y] ||
+ tents + maybetents < state->numbers->numbers[w+y]);
+ }
+
+ /*
+ * Identify groups of tents with too few trees between them,
+ * which we do by constructing the connected components of the
+ * bipartite adjacency graph between tents and trees
+ * ('bipartite' in the sense that we deliberately ignore
+ * adjacency between tents or between trees), and highlighting
+ * all the tents in any component which has a smaller tree
+ * count.
+ */
+ dsf_init(dsf, w*h);
+ /* Construct the equivalence classes. */
+ for (y = 0; y < h; y++) {
+ for (x = 0; x < w-1; x++) {
+ if ((grid[y*w+x] == TREE && grid[y*w+x+1] == TENT) ||
+ (grid[y*w+x] == TENT && grid[y*w+x+1] == TREE))
+ dsf_merge(dsf, y*w+x, y*w+x+1);
+ }
+ }
+ for (y = 0; y < h-1; y++) {
+ for (x = 0; x < w; x++) {
+ if ((grid[y*w+x] == TREE && grid[(y+1)*w+x] == TENT) ||
+ (grid[y*w+x] == TENT && grid[(y+1)*w+x] == TREE))
+ dsf_merge(dsf, y*w+x, (y+1)*w+x);
+ }
+ }
+ /* Count up the tent/tree difference in each one. */
+ for (x = 0; x < w*h; x++)
+ tmp[x] = 0;
+ for (x = 0; x < w*h; x++) {
+ y = dsf_canonify(dsf, x);
+ if (grid[x] == TREE)
+ tmp[y]++;
+ else if (grid[x] == TENT)
+ tmp[y]--;
+ }
+ /* And highlight any tent belonging to an equivalence class with
+ * a score less than zero. */
+ for (x = 0; x < w*h; x++) {
+ y = dsf_canonify(dsf, x);
+ if (grid[x] == TENT && tmp[y] < 0)
+ ret[x] |= 1 << ERR_OVERCOMMITTED;
+ }
+
+ /*
+ * Identify groups of trees with too few tents between them.
+ * This is done similarly, except that we now count BLANK as
+ * equivalent to TENT, i.e. we only highlight such trees when
+ * the user hasn't even left _room_ to provide tents for them
+ * all. (Otherwise, we'd highlight all trees red right at the
+ * start of the game, before the user had done anything wrong!)
+ */
+#define TENT(x) ((x)==TENT || (x)==BLANK)
+ dsf_init(dsf, w*h);
+ /* Construct the equivalence classes. */
+ for (y = 0; y < h; y++) {
+ for (x = 0; x < w-1; x++) {
+ if ((grid[y*w+x] == TREE && TENT(grid[y*w+x+1])) ||
+ (TENT(grid[y*w+x]) && grid[y*w+x+1] == TREE))
+ dsf_merge(dsf, y*w+x, y*w+x+1);
+ }
+ }
+ for (y = 0; y < h-1; y++) {
+ for (x = 0; x < w; x++) {
+ if ((grid[y*w+x] == TREE && TENT(grid[(y+1)*w+x])) ||
+ (TENT(grid[y*w+x]) && grid[(y+1)*w+x] == TREE))
+ dsf_merge(dsf, y*w+x, (y+1)*w+x);
+ }
+ }
+ /* Count up the tent/tree difference in each one. */
+ for (x = 0; x < w*h; x++)
+ tmp[x] = 0;
+ for (x = 0; x < w*h; x++) {
+ y = dsf_canonify(dsf, x);
+ if (grid[x] == TREE)
+ tmp[y]++;
+ else if (TENT(grid[x]))
+ tmp[y]--;
+ }
+ /* And highlight any tree belonging to an equivalence class with
+ * a score more than zero. */
+ for (x = 0; x < w*h; x++) {
+ y = dsf_canonify(dsf, x);
+ if (grid[x] == TREE && tmp[y] > 0)
+ ret[x] |= 1 << ERR_OVERCOMMITTED;
+ }
+#undef TENT
+
+ sfree(tmp);
+ return ret;
+}
+
+static void draw_err_adj(drawing *dr, game_drawstate *ds, int x, int y)
+{
+ int coords[8];
+ int yext, xext;
+
+ /*
+ * Draw a diamond.
+ */
+ coords[0] = x - TILESIZE*2/5;
+ coords[1] = y;
+ coords[2] = x;
+ coords[3] = y - TILESIZE*2/5;
+ coords[4] = x + TILESIZE*2/5;
+ coords[5] = y;
+ coords[6] = x;
+ coords[7] = y + TILESIZE*2/5;
+ draw_polygon(dr, coords, 4, COL_ERROR, COL_GRID);
+
+ /*
+ * Draw an exclamation mark in the diamond. This turns out to
+ * look unpleasantly off-centre if done via draw_text, so I do
+ * it by hand on the basis that exclamation marks aren't that
+ * difficult to draw...
+ */
+ xext = TILESIZE/16;
+ yext = TILESIZE*2/5 - (xext*2+2);
+ draw_rect(dr, x-xext, y-yext, xext*2+1, yext*2+1 - (xext*3),
+ COL_ERRTEXT);
+ draw_rect(dr, x-xext, y+yext-xext*2+1, xext*2+1, xext*2, COL_ERRTEXT);
+}
+
static void draw_tile(drawing *dr, game_drawstate *ds,
- int x, int y, int v, int printing)
+ int x, int y, int v, int cur, int printing)
{
+ int err;
int tx = COORD(x), ty = COORD(y);
int cx = tx + TILESIZE/2, cy = ty + TILESIZE/2;
- clip(dr, tx+1, ty+1, TILESIZE-1, TILESIZE-1);
+ err = v & ~15;
+ v &= 15;
+
+ clip(dr, tx, ty, TILESIZE, TILESIZE);
- if (!printing)
+ if (!printing) {
+ draw_rect(dr, tx, ty, TILESIZE, TILESIZE, COL_GRID);
draw_rect(dr, tx+1, ty+1, TILESIZE-1, TILESIZE-1,
(v == BLANK ? COL_BACKGROUND : COL_GRASS));
+ }
if (v == TREE) {
int i;
(printing ? draw_rect_outline : draw_rect)
(dr, cx-TILESIZE/15, ty+TILESIZE*3/10,
2*(TILESIZE/15)+1, (TILESIZE*9/10 - TILESIZE*3/10),
- COL_TREETRUNK);
+ (err & (1<<ERR_OVERCOMMITTED) ? COL_ERRTRUNK : COL_TREETRUNK));
for (i = 0; i < (printing ? 2 : 1); i++) {
- int col = (i == 1 ? COL_BACKGROUND : COL_TREELEAF);
+ int col = (i == 1 ? COL_BACKGROUND :
+ (err & (1<<ERR_OVERCOMMITTED) ? COL_ERROR :
+ COL_TREELEAF));
int sub = i * (TILESIZE/32);
draw_circle(dr, cx, ty+TILESIZE*4/10, TILESIZE/4 - sub,
col, col);
}
} else if (v == TENT) {
int coords[6];
+ int col;
coords[0] = cx - TILESIZE/3;
coords[1] = cy + TILESIZE/3;
coords[2] = cx + TILESIZE/3;
coords[3] = cy + TILESIZE/3;
coords[4] = cx;
coords[5] = cy - TILESIZE/3;
- draw_polygon(dr, coords, 3, (printing ? -1 : COL_TENT), COL_TENT);
+ col = (err & (1<<ERR_OVERCOMMITTED) ? COL_ERROR : COL_TENT);
+ draw_polygon(dr, coords, 3, (printing ? -1 : col), col);
+ }
+
+ if (err & (1 << ERR_ADJ_TOPLEFT))
+ draw_err_adj(dr, ds, tx, ty);
+ if (err & (1 << ERR_ADJ_TOP))
+ draw_err_adj(dr, ds, tx+TILESIZE/2, ty);
+ if (err & (1 << ERR_ADJ_TOPRIGHT))
+ draw_err_adj(dr, ds, tx+TILESIZE, ty);
+ if (err & (1 << ERR_ADJ_LEFT))
+ draw_err_adj(dr, ds, tx, ty+TILESIZE/2);
+ if (err & (1 << ERR_ADJ_RIGHT))
+ draw_err_adj(dr, ds, tx+TILESIZE, ty+TILESIZE/2);
+ if (err & (1 << ERR_ADJ_BOTLEFT))
+ draw_err_adj(dr, ds, tx, ty+TILESIZE);
+ if (err & (1 << ERR_ADJ_BOT))
+ draw_err_adj(dr, ds, tx+TILESIZE/2, ty+TILESIZE);
+ if (err & (1 << ERR_ADJ_BOTRIGHT))
+ draw_err_adj(dr, ds, tx+TILESIZE, ty+TILESIZE);
+
+ if (cur) {
+ int coff = TILESIZE/8;
+ draw_rect_outline(dr, tx + coff, ty + coff,
+ TILESIZE - coff*2 + 1, TILESIZE - coff*2 + 1,
+ COL_GRID);
}
unclip(dr);
/*
* Internal redraw function, used for printing as well as drawing.
*/
-static void int_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate,
- game_state *state, int dir, game_ui *ui,
+static void int_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 printing)
{
int w = state->p.w, h = state->p.h;
int x, y, flashing;
+ int cx = -1, cy = -1;
+ int cmoved = 0;
+ char *tmpgrid;
+ int *errors;
+
+ if (ui) {
+ if (ui->cdisp) { cx = ui->cx; cy = ui->cy; }
+ if (cx != ds->cx || cy != ds->cy) cmoved = 1;
+ }
if (printing || !ds->started) {
if (!printing) {
draw_line(dr, COORD(0), COORD(y), COORD(w), COORD(y), COL_GRID);
for (x = 0; x <= w; x++)
draw_line(dr, COORD(x), COORD(0), COORD(x), COORD(h), COL_GRID);
-
- /*
- * Draw the numbers.
- */
- for (y = 0; y < h; y++) {
- char buf[80];
- sprintf(buf, "%d", state->numbers->numbers[y+w]);
- draw_text(dr, COORD(w+1), COORD(y) + TILESIZE/2,
- FONT_VARIABLE, TILESIZE/2, ALIGN_HRIGHT|ALIGN_VCENTRE,
- COL_GRID, buf);
- }
- for (x = 0; x < w; x++) {
- char buf[80];
- sprintf(buf, "%d", state->numbers->numbers[x]);
- draw_text(dr, COORD(x) + TILESIZE/2, COORD(h+1),
- FONT_VARIABLE, TILESIZE/2, ALIGN_HCENTRE|ALIGN_VNORMAL,
- COL_GRID, buf);
- }
}
if (flashtime > 0)
else
flashing = FALSE;
+ /*
+ * Find errors. For this we use _part_ of the information from a
+ * currently active drag: we transform dsx,dsy but not anything
+ * else. (This seems to strike a good compromise between having
+ * the error highlights respond instantly to single clicks, but
+ * not giving constant feedback during a right-drag.)
+ */
+ if (ui && ui->drag_button >= 0) {
+ tmpgrid = snewn(w*h, char);
+ memcpy(tmpgrid, state->grid, w*h);
+ tmpgrid[ui->dsy * w + ui->dsx] =
+ drag_xform(ui, ui->dsx, ui->dsy, tmpgrid[ui->dsy * w + ui->dsx]);
+ errors = find_errors(state, tmpgrid);
+ sfree(tmpgrid);
+ } else {
+ errors = find_errors(state, state->grid);
+ }
+
/*
* Draw the grid.
*/
- for (y = 0; y < h; y++)
+ for (y = 0; y < h; y++) {
for (x = 0; x < w; x++) {
int v = state->grid[y*w+x];
+ int credraw = 0;
/*
* We deliberately do not take drag_ok into account
if (flashing && (v == TREE || v == TENT))
v = NONTENT;
- if (printing || ds->drawn[y*w+x] != v) {
- draw_tile(dr, ds, x, y, v, printing);
+ if (cmoved) {
+ if ((x == cx && y == cy) ||
+ (x == ds->cx && y == ds->cy)) credraw = 1;
+ }
+
+ v |= errors[y*w+x];
+
+ if (printing || ds->drawn[y*w+x] != v || credraw) {
+ draw_tile(dr, ds, x, y, v, (x == cx && y == cy), printing);
if (!printing)
ds->drawn[y*w+x] = v;
}
}
+ }
+
+ /*
+ * Draw (or redraw, if their error-highlighted state has
+ * changed) the numbers.
+ */
+ for (x = 0; x < w; x++) {
+ if (printing || ds->numbersdrawn[x] != errors[w*h+x]) {
+ char buf[80];
+ draw_rect(dr, COORD(x), COORD(h)+1, TILESIZE, BRBORDER-1,
+ COL_BACKGROUND);
+ sprintf(buf, "%d", state->numbers->numbers[x]);
+ draw_text(dr, COORD(x) + TILESIZE/2, COORD(h+1),
+ FONT_VARIABLE, TILESIZE/2, ALIGN_HCENTRE|ALIGN_VNORMAL,
+ (errors[w*h+x] ? COL_ERROR : COL_GRID), buf);
+ draw_update(dr, COORD(x), COORD(h)+1, TILESIZE, BRBORDER-1);
+ if (!printing)
+ ds->numbersdrawn[x] = errors[w*h+x];
+ }
+ }
+ for (y = 0; y < h; y++) {
+ if (printing || ds->numbersdrawn[w+y] != errors[w*h+w+y]) {
+ char buf[80];
+ draw_rect(dr, COORD(w)+1, COORD(y), BRBORDER-1, TILESIZE,
+ COL_BACKGROUND);
+ sprintf(buf, "%d", state->numbers->numbers[w+y]);
+ draw_text(dr, COORD(w+1), COORD(y) + TILESIZE/2,
+ FONT_VARIABLE, TILESIZE/2, ALIGN_HRIGHT|ALIGN_VCENTRE,
+ (errors[w*h+w+y] ? COL_ERROR : COL_GRID), buf);
+ draw_update(dr, COORD(w)+1, COORD(y), BRBORDER-1, TILESIZE);
+ if (!printing)
+ ds->numbersdrawn[w+y] = errors[w*h+w+y];
+ }
+ }
+
+ if (cmoved) {
+ ds->cx = cx;
+ ds->cy = cy;
+ }
+
+ sfree(errors);
}
-static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate,
- game_state *state, int dir, game_ui *ui,
- float animtime, float flashtime)
+static void game_redraw(drawing *dr, game_drawstate *ds,
+ const game_state *oldstate, const game_state *state,
+ int dir, const game_ui *ui,
+ float animtime, float flashtime)
{
int_redraw(dr, ds, oldstate, state, dir, ui, animtime, flashtime, FALSE);
}
-static float game_anim_length(game_state *oldstate, game_state *newstate,
- int dir, game_ui *ui)
+static float game_anim_length(const game_state *oldstate,
+ const game_state *newstate, int dir, game_ui *ui)
{
return 0.0F;
}
-static float game_flash_length(game_state *oldstate, game_state *newstate,
- int dir, game_ui *ui)
+static float game_flash_length(const game_state *oldstate,
+ const game_state *newstate, int dir, game_ui *ui)
{
if (!oldstate->completed && newstate->completed &&
!oldstate->used_solve && !newstate->used_solve)
return 0.0F;
}
-static int game_timing_state(game_state *state, game_ui *ui)
+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(game_params *params, float *x, float *y)
+static void game_print_size(const game_params *params, float *x, float *y)
{
int pw, ph;
* I'll use 6mm squares by default.
*/
game_compute_size(params, 600, &pw, &ph);
- *x = pw / 100.0;
- *y = ph / 100.0;
+ *x = pw / 100.0F;
+ *y = ph / 100.0F;
}
-static void game_print(drawing *dr, game_state *state, int tilesize)
+static void game_print(drawing *dr, const game_state *state, int tilesize)
{
int c;
dup_game,
free_game,
TRUE, solve_game,
- FALSE, game_text_format,
+ TRUE, game_can_format_as_text_now, game_text_format,
new_ui,
free_ui,
encode_ui,
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 */
+ REQUIRE_RBUTTON, /* flags */
};
#ifdef STANDALONE_SOLVER
}
#endif
+
+/* vim: set shiftwidth=4 tabstop=8: */
~ian / sgt-puzzles.git / blobdiff