/*
* TODO:
*
- * - Solve function:
- * * try to generate a solution when Solve is pressed
- * + from the start, or from here? From here, I fear.
- * + hence, not much point saving the solution in an aux
- * string
- * * Inertia-like method for telling the user the solution
- * * standalone solver which draws diagrams
- *
- * - The dragging semantics are still subtly wrong in complex
- * cases.
- *
* - Improve the generator.
* * actually, we seem to be mostly sensible already now. I
* want more choice over the type of main block and location
* target marker pale.
* * The cattle grid effect is still disgusting. Think of
* something completely different.
+ * * The highlight for next-piece-to-move in the solver is
+ * excessive, and the shadow blends in too well with the
+ * piece lowlights. Adjust both.
*/
#include <stdio.h>
unsigned char *forcefield;
};
+struct game_solution {
+ int nmoves;
+ int *moves; /* just like from solve_board() */
+ int refcount;
+};
+
struct game_state {
int w, h;
unsigned char *board;
int lastmoved, lastmoved_pos; /* for move counting */
int movecount;
int completed;
+ int cheated;
struct game_immutable_state *imm;
+ struct game_solution *soln;
+ int soln_index;
};
static game_params *default_params(void)
/*
* The actual solver. Given a board, attempt to find the minimum
* length of move sequence which moves MAINANCHOR to (tx,ty), or
- * -1 if no solution exists. Returns that minimum length, and
- * (FIXME) optionally also writes out the actual moves into an
- * as-yet-unprovided parameter.
+ * -1 if no solution exists. Returns that minimum length.
+ *
+ * Also, if `moveout' is provided, writes out the moves in the
+ * form of a sequence of pairs of integers indicating the source
+ * and destination points of the anchor of the moved piece in each
+ * move. Exactly twice as many integers are written as the number
+ * returned from solve_board(), and `moveout' receives an int *
+ * which is a pointer to a dynamically allocated array.
*/
static int solve_board(int w, int h, unsigned char *board,
unsigned char *forcefield, int tx, int ty,
- int movelimit)
+ int movelimit, int **moveout)
{
int wh = w*h;
struct board *b, *b2, *b3;
done:
- if (b2)
+ if (b2) {
ret = b2->dist;
- else
+ if (moveout) {
+ /*
+ * Now b2 represents the solved position. Backtrack to
+ * output the solution.
+ */
+ *moveout = snewn(ret * 2, int);
+ j = ret * 2;
+
+ while (b2->prev) {
+ int from = -1, to = -1;
+
+ b = b2->prev;
+
+ /*
+ * Scan b and b2 to find out which piece has
+ * moved.
+ */
+ for (i = 0; i < wh; i++) {
+ if (ISANCHOR(b->data[i]) && !ISANCHOR(b2->data[i])) {
+ assert(from == -1);
+ from = i;
+ } else if (!ISANCHOR(b->data[i]) && ISANCHOR(b2->data[i])){
+ assert(to == -1);
+ to = i;
+ }
+ }
+
+ assert(from >= 0 && to >= 0);
+ assert(j >= 2);
+ (*moveout)[--j] = to;
+ (*moveout)[--j] = from;
+
+ b2 = b;
+ }
+ assert(j == 0);
+ }
+ } else {
ret = -1; /* no solution */
+ if (moveout)
+ *moveout = NULL;
+ }
freetree234(queue);
int *list, nlist, pos;
int tx, ty;
int i, j;
- int moves;
+ int moves = 0; /* placate optimiser */
/*
* Set up a board and fill it with singletons, except for a
* See if the board is already soluble.
*/
if ((moves = solve_board(w, h, board, forcefield,
- tx, ty, movelimit)) >= 0)
+ tx, ty, movelimit, NULL)) >= 0)
goto soluble;
/*
} while (p2 < wh && board[p2] != DIST(p2-i));
}
}
- j = solve_board(w, h, board, forcefield, tx, ty, movelimit);
+ j = solve_board(w, h, board, forcefield, tx, ty, movelimit, NULL);
if (j < 0) {
/*
* Didn't work. Revert the merge.
p += sprintf(p, ",%d,%d,%d", tx, ty, minmoves);
ret = sresize(ret, p+1 - ret, char);
- /*
- * FIXME: generate an aux string
- */
-
sfree(board);
sfree(forcefield);
int w = params->w, h = params->h, wh = w*h;
int *active, *link;
int mains = 0, mpos = -1;
- int i, j, tx, ty, minmoves;
+ int i, tx, ty, minmoves;
char *ret;
active = snewn(wh, int);
}
link[i] = i - dist;
- for (j = i; j > 0; j = link[j])
- if (j == i-1 || j == i-w)
- break;
- if (j < 0) {
- ret = "Disconnected piece in game description";
- goto done;
- }
active[i] = TRUE;
active[link[i]] = FALSE;
else
state->completed = -1;
+ state->cheated = FALSE;
+ state->soln = NULL;
+ state->soln_index = -1;
+
return state;
}
ret->lastmoved_pos = state->lastmoved_pos;
ret->movecount = state->movecount;
ret->completed = state->completed;
+ ret->cheated = state->cheated;
ret->imm = state->imm;
ret->imm->refcount++;
+ ret->soln = state->soln;
+ ret->soln_index = state->soln_index;
+ if (ret->soln)
+ ret->soln->refcount++;
return ret;
}
sfree(state->imm->forcefield);
sfree(state->imm);
}
+ if (state->soln && --state->soln->refcount <= 0) {
+ sfree(state->soln->moves);
+ sfree(state->soln);
+ }
sfree(state->board);
sfree(state);
}
static char *solve_game(game_state *state, game_state *currstate,
char *aux, char **error)
{
+ int *moves;
+ int nmoves;
+ int i;
+ char *ret, *p, sep;
+
/*
- * FIXME: we have a solver, so use it
- *
- * FIXME: we should have generated an aux string, so use that
+ * Run the solver and attempt to find the shortest solution
+ * from the current position.
*/
- return NULL;
+ nmoves = solve_board(state->w, state->h, state->board,
+ state->imm->forcefield, state->tx, state->ty,
+ -1, &moves);
+
+ if (nmoves < 0) {
+ *error = "Unable to find a solution to this puzzle";
+ return NULL;
+ }
+ if (nmoves == 0) {
+ *error = "Puzzle is already solved";
+ return NULL;
+ }
+
+ /*
+ * Encode the resulting solution as a move string.
+ */
+ ret = snewn(nmoves * 40, char);
+ p = ret;
+ sep = 'S';
+
+ for (i = 0; i < nmoves; i++) {
+ p += sprintf(p, "%c%d-%d", sep, moves[i*2], moves[i*2+1]);
+ sep = ',';
+ }
+
+ sfree(moves);
+ assert(p - ret < nmoves * 40);
+ ret = sresize(ret, p+1 - ret, char);
+
+ return ret;
}
static char *game_text_format(game_state *state)
*/
return "";
} else if (button == LEFT_DRAG && ui->dragging) {
+ int dist, distlimit, dx, dy, s, px, py;
+
tx = FROMCOORD(x);
ty = FROMCOORD(y);
tx -= ui->drag_offset_x;
ty -= ui->drag_offset_y;
- if (tx < 0 || tx >= w || ty < 0 || ty >= h ||
- !ui->reachable[ty*w+tx])
- return NULL; /* this drag has no effect */
- ui->drag_currpos = ty*w+tx;
- return "";
+ /*
+ * Now search outwards from (tx,ty), in order of Manhattan
+ * distance, until we find a reachable square.
+ */
+ distlimit = w+tx;
+ distlimit = max(distlimit, h+ty);
+ distlimit = max(distlimit, tx);
+ distlimit = max(distlimit, ty);
+ for (dist = 0; dist <= distlimit; dist++) {
+ for (dx = -dist; dx <= dist; dx++)
+ for (s = -1; s <= +1; s += 2) {
+ dy = s * (dist - abs(dx));
+ px = tx + dx;
+ py = ty + dy;
+ if (px >= 0 && px < w && py >= 0 && py < h &&
+ ui->reachable[py*w+px]) {
+ ui->drag_currpos = py*w+px;
+ return "";
+ }
+ }
+ }
+ return NULL; /* give up - this drag has no effect */
} else if (button == LEFT_RELEASE && ui->dragging) {
char data[256], *str;
memset(ui->reachable, 0, wh);
return str;
+ } else if (button == ' ' && state->soln) {
+ /*
+ * Make the next move in the stored solution.
+ */
+ char data[256];
+ int a1, a2;
+
+ a1 = state->soln->moves[state->soln_index*2];
+ a2 = state->soln->moves[state->soln_index*2+1];
+ if (a1 == state->lastmoved_pos)
+ a1 = state->lastmoved;
+
+ sprintf(data, "M%d-%d", a1, a2);
+ return dupstr(data);
}
return NULL;
{
int w = state->w, h = state->h /* , wh = w*h */;
char c;
- int a1, a2, n;
+ int a1, a2, n, movesize;
game_state *ret = dup_game(state);
while (*move) {
c = *move;
- if (c == 'M') {
+ if (c == 'S') {
+ /*
+ * This is a solve move, so we just set up a stored
+ * solution path.
+ */
+ if (ret->soln && --ret->soln->refcount <= 0) {
+ sfree(ret->soln->moves);
+ sfree(ret->soln);
+ }
+ ret->soln = snew(struct game_solution);
+ ret->soln->nmoves = 0;
+ ret->soln->moves = NULL;
+ ret->soln->refcount = 1;
+ ret->soln_index = 0;
+ ret->cheated = TRUE;
+
+ movesize = 0;
+ move++;
+ while (1) {
+ if (sscanf(move, "%d-%d%n", &a1, &a2, &n) != 2) {
+ free_game(ret);
+ return NULL;
+ }
+
+ /*
+ * Special case: if the first move in the solution
+ * involves the piece for which we already have a
+ * partial stored move, adjust the source point to
+ * the original starting point of that piece.
+ */
+ if (ret->soln->nmoves == 0 && a1 == ret->lastmoved)
+ a1 = ret->lastmoved_pos;
+
+ if (ret->soln->nmoves >= movesize) {
+ movesize = (ret->soln->nmoves + 48) * 4 / 3;
+ ret->soln->moves = sresize(ret->soln->moves,
+ 2*movesize, int);
+ }
+
+ ret->soln->moves[2*ret->soln->nmoves] = a1;
+ ret->soln->moves[2*ret->soln->nmoves+1] = a2;
+ ret->soln->nmoves++;
+ move += n;
+ if (*move != ',')
+ break;
+ move++; /* eat comma */
+ }
+ } else if (c == 'M') {
move++;
if (sscanf(move, "%d-%d%n", &a1, &a2, &n) != 2 ||
!move_piece(w, h, state->board, ret->board,
ret->lastmoved_pos = a1;
ret->movecount++;
}
+
+ /*
+ * If we have a stored solution path, see if we've
+ * strayed from it or successfully made the next move
+ * along it.
+ */
+ if (ret->soln && ret->lastmoved_pos >= 0) {
+ if (ret->lastmoved_pos !=
+ ret->soln->moves[ret->soln_index*2]) {
+ /* strayed from the path */
+ ret->soln->refcount--;
+ assert(ret->soln->refcount > 0);
+ /* `state' at least still exists */
+ ret->soln = NULL;
+ ret->soln_index = -1;
+ } else if (ret->lastmoved ==
+ ret->soln->moves[ret->soln_index*2+1]) {
+ /* advanced along the path */
+ ret->soln_index++;
+ if (ret->soln_index >= ret->soln->nmoves) {
+ /* finished the path! */
+ ret->soln->refcount--;
+ assert(ret->soln->refcount > 0);
+ /* `state' at least still exists */
+ ret->soln = NULL;
+ ret->soln_index = -1;
+ }
+ }
+ }
+
if (ret->board[a2] == MAINANCHOR &&
a2 == ret->ty * w + ret->tx && ret->completed < 0)
ret->completed = ret->movecount;
#define FG_MAIN 0x00000040UL
#define FG_NORMAL 0x00000080UL
#define FG_DRAGGING 0x00000100UL
-#define FG_LBORDER 0x00000200UL
-#define FG_TBORDER 0x00000400UL
-#define FG_RBORDER 0x00000800UL
-#define FG_BBORDER 0x00001000UL
-#define FG_TLCORNER 0x00002000UL
-#define FG_TRCORNER 0x00004000UL
-#define FG_BLCORNER 0x00008000UL
-#define FG_BRCORNER 0x00010000UL
+#define FG_SHADOW 0x00000200UL
+#define FG_SOLVEPIECE 0x00000400UL
+#define FG_MAINPIECESH 11
+#define FG_SHADOWSH 19
+
+#define PIECE_LBORDER 0x00000001UL
+#define PIECE_TBORDER 0x00000002UL
+#define PIECE_RBORDER 0x00000004UL
+#define PIECE_BBORDER 0x00000008UL
+#define PIECE_TLCORNER 0x00000010UL
+#define PIECE_TRCORNER 0x00000020UL
+#define PIECE_BLCORNER 0x00000040UL
+#define PIECE_BRCORNER 0x00000080UL
+#define PIECE_MASK 0x000000FFUL
/*
* Utility function.
#define TYPE_TRCIRC 0x5000
#define TYPE_BLCIRC 0x6000
#define TYPE_BRCIRC 0x7000
-static void maybe_rect(drawing *dr, int x, int y, int w, int h, int coltype)
+static void maybe_rect(drawing *dr, int x, int y, int w, int h,
+ int coltype, int col2)
{
int colour = coltype & COL_MASK, type = coltype & TYPE_MASK;
cx = x;
cy = y;
- assert(w == h);
r = w-1;
if (type & 0x1000)
cx += r;
if (type & 0x2000)
cy += r;
- draw_circle(dr, cx, cy, r, colour, colour);
+ if (col2 == -1 || col2 == coltype) {
+ assert(w == h);
+ draw_circle(dr, cx, cy, r, colour, colour);
+ } else {
+ /*
+ * We aim to draw a quadrant of a circle in two
+ * different colours. We do this using Bresenham's
+ * algorithm directly, because the Puzzles drawing API
+ * doesn't have a draw-sector primitive.
+ */
+ int bx, by, bd, bd2;
+ int xm = (type & 0x1000 ? -1 : +1);
+ int ym = (type & 0x2000 ? -1 : +1);
+
+ by = r;
+ bx = 0;
+ bd = 0;
+ while (by >= bx) {
+ /*
+ * Plot the point.
+ */
+ {
+ int x1 = cx+xm*bx, y1 = cy+ym*bx;
+ int x2, y2;
+
+ x2 = cx+xm*by; y2 = y1;
+ draw_rect(dr, min(x1,x2), min(y1,y2),
+ abs(x1-x2)+1, abs(y1-y2)+1, colour);
+ x2 = x1; y2 = cy+ym*by;
+ draw_rect(dr, min(x1,x2), min(y1,y2),
+ abs(x1-x2)+1, abs(y1-y2)+1, col2);
+ }
+
+ bd += 2*bx + 1;
+ bd2 = bd - (2*by - 1);
+ if (abs(bd2) < abs(bd)) {
+ bd = bd2;
+ by--;
+ }
+ bx++;
+ }
+ }
+
+ unclip(dr);
+ }
+}
+
+static void draw_wallpart(drawing *dr, game_drawstate *ds,
+ int tx, int ty, unsigned long val,
+ int cl, int cc, int ch)
+{
+ int coords[6];
+
+ draw_rect(dr, tx, ty, TILESIZE, TILESIZE, cc);
+ if (val & PIECE_LBORDER)
+ draw_rect(dr, tx, ty, HIGHLIGHT_WIDTH, TILESIZE,
+ ch);
+ if (val & PIECE_RBORDER)
+ draw_rect(dr, tx+TILESIZE-HIGHLIGHT_WIDTH, ty,
+ HIGHLIGHT_WIDTH, TILESIZE, cl);
+ if (val & PIECE_TBORDER)
+ draw_rect(dr, tx, ty, TILESIZE, HIGHLIGHT_WIDTH, ch);
+ if (val & PIECE_BBORDER)
+ draw_rect(dr, tx, ty+TILESIZE-HIGHLIGHT_WIDTH,
+ TILESIZE, HIGHLIGHT_WIDTH, cl);
+ if (!((PIECE_BBORDER | PIECE_LBORDER) &~ val)) {
+ draw_rect(dr, tx, ty+TILESIZE-HIGHLIGHT_WIDTH,
+ HIGHLIGHT_WIDTH, HIGHLIGHT_WIDTH, cl);
+ clip(dr, tx, ty+TILESIZE-HIGHLIGHT_WIDTH,
+ HIGHLIGHT_WIDTH, HIGHLIGHT_WIDTH);
+ coords[0] = tx - 1;
+ coords[1] = ty + TILESIZE - HIGHLIGHT_WIDTH - 1;
+ coords[2] = tx + HIGHLIGHT_WIDTH;
+ coords[3] = ty + TILESIZE - HIGHLIGHT_WIDTH - 1;
+ coords[4] = tx - 1;
+ coords[5] = ty + TILESIZE;
+ draw_polygon(dr, coords, 3, ch, ch);
+ unclip(dr);
+ } else if (val & PIECE_BLCORNER) {
+ draw_rect(dr, tx, ty+TILESIZE-HIGHLIGHT_WIDTH,
+ HIGHLIGHT_WIDTH, HIGHLIGHT_WIDTH, ch);
+ clip(dr, tx, ty+TILESIZE-HIGHLIGHT_WIDTH,
+ HIGHLIGHT_WIDTH, HIGHLIGHT_WIDTH);
+ coords[0] = tx - 1;
+ coords[1] = ty + TILESIZE - HIGHLIGHT_WIDTH - 1;
+ coords[2] = tx + HIGHLIGHT_WIDTH;
+ coords[3] = ty + TILESIZE - HIGHLIGHT_WIDTH - 1;
+ coords[4] = tx - 1;
+ coords[5] = ty + TILESIZE;
+ draw_polygon(dr, coords, 3, cl, cl);
unclip(dr);
}
+ if (!((PIECE_TBORDER | PIECE_RBORDER) &~ val)) {
+ draw_rect(dr, tx+TILESIZE-HIGHLIGHT_WIDTH, ty,
+ HIGHLIGHT_WIDTH, HIGHLIGHT_WIDTH, cl);
+ clip(dr, tx+TILESIZE-HIGHLIGHT_WIDTH, ty,
+ HIGHLIGHT_WIDTH, HIGHLIGHT_WIDTH);
+ coords[0] = tx + TILESIZE - HIGHLIGHT_WIDTH - 1;
+ coords[1] = ty - 1;
+ coords[2] = tx + TILESIZE;
+ coords[3] = ty - 1;
+ coords[4] = tx + TILESIZE - HIGHLIGHT_WIDTH - 1;
+ coords[5] = ty + HIGHLIGHT_WIDTH;
+ draw_polygon(dr, coords, 3, ch, ch);
+ unclip(dr);
+ } else if (val & PIECE_TRCORNER) {
+ draw_rect(dr, tx+TILESIZE-HIGHLIGHT_WIDTH, ty,
+ HIGHLIGHT_WIDTH, HIGHLIGHT_WIDTH, ch);
+ clip(dr, tx+TILESIZE-HIGHLIGHT_WIDTH, ty,
+ HIGHLIGHT_WIDTH, HIGHLIGHT_WIDTH);
+ coords[0] = tx + TILESIZE - HIGHLIGHT_WIDTH - 1;
+ coords[1] = ty - 1;
+ coords[2] = tx + TILESIZE;
+ coords[3] = ty - 1;
+ coords[4] = tx + TILESIZE - HIGHLIGHT_WIDTH - 1;
+ coords[5] = ty + HIGHLIGHT_WIDTH;
+ draw_polygon(dr, coords, 3, cl, cl);
+ unclip(dr);
+ }
+ if (val & PIECE_TLCORNER)
+ draw_rect(dr, tx, ty, HIGHLIGHT_WIDTH, HIGHLIGHT_WIDTH, ch);
+ if (val & PIECE_BRCORNER)
+ draw_rect(dr, tx+TILESIZE-HIGHLIGHT_WIDTH,
+ ty+TILESIZE-HIGHLIGHT_WIDTH,
+ HIGHLIGHT_WIDTH, HIGHLIGHT_WIDTH, cl);
+}
+
+static void draw_piecepart(drawing *dr, game_drawstate *ds,
+ int tx, int ty, unsigned long val,
+ int cl, int cc, int ch)
+{
+ int x[6], y[6];
+
+ /*
+ * Drawing the blocks is hellishly fiddly. The blocks don't
+ * stretch to the full size of the tile; there's a border
+ * around them of size BORDER_WIDTH. Then they have bevelled
+ * borders of size HIGHLIGHT_WIDTH, and also rounded corners.
+ *
+ * I tried for some time to find a clean and clever way to
+ * figure out what needed drawing from the corner and border
+ * flags, but in the end the cleanest way I could find was the
+ * following. We divide the grid square into 25 parts by
+ * ruling four horizontal and four vertical lines across it;
+ * those lines are at BORDER_WIDTH and BORDER_WIDTH +
+ * HIGHLIGHT_WIDTH from the top, from the bottom, from the
+ * left and from the right. Then we carefully consider each of
+ * the resulting 25 sections of square, and decide separately
+ * what needs to go in it based on the flags. In complicated
+ * cases there can be up to five possibilities affecting any
+ * given section (no corner or border flags, just the corner
+ * flag, one border flag, the other border flag, both border
+ * flags). So there's a lot of very fiddly logic here and all
+ * I could really think to do was give it my best shot and
+ * then test it and correct all the typos. Not fun to write,
+ * and I'm sure it isn't fun to read either, but it seems to
+ * work.
+ */
+
+ x[0] = tx;
+ x[1] = x[0] + BORDER_WIDTH;
+ x[2] = x[1] + HIGHLIGHT_WIDTH;
+ x[5] = tx + TILESIZE;
+ x[4] = x[5] - BORDER_WIDTH;
+ x[3] = x[4] - HIGHLIGHT_WIDTH;
+
+ y[0] = ty;
+ y[1] = y[0] + BORDER_WIDTH;
+ y[2] = y[1] + HIGHLIGHT_WIDTH;
+ y[5] = ty + TILESIZE;
+ y[4] = y[5] - BORDER_WIDTH;
+ y[3] = y[4] - HIGHLIGHT_WIDTH;
+
+#define RECT(p,q) x[p], y[q], x[(p)+1]-x[p], y[(q)+1]-y[q]
+
+ maybe_rect(dr, RECT(0,0),
+ (val & (PIECE_TLCORNER | PIECE_TBORDER |
+ PIECE_LBORDER)) ? -1 : cc, -1);
+ maybe_rect(dr, RECT(1,0),
+ (val & PIECE_TLCORNER) ? ch : (val & PIECE_TBORDER) ? -1 :
+ (val & PIECE_LBORDER) ? ch : cc, -1);
+ maybe_rect(dr, RECT(2,0),
+ (val & PIECE_TBORDER) ? -1 : cc, -1);
+ maybe_rect(dr, RECT(3,0),
+ (val & PIECE_TRCORNER) ? cl : (val & PIECE_TBORDER) ? -1 :
+ (val & PIECE_RBORDER) ? cl : cc, -1);
+ maybe_rect(dr, RECT(4,0),
+ (val & (PIECE_TRCORNER | PIECE_TBORDER |
+ PIECE_RBORDER)) ? -1 : cc, -1);
+ maybe_rect(dr, RECT(0,1),
+ (val & PIECE_TLCORNER) ? ch : (val & PIECE_LBORDER) ? -1 :
+ (val & PIECE_TBORDER) ? ch : cc, -1);
+ maybe_rect(dr, RECT(1,1),
+ (val & PIECE_TLCORNER) ? cc : -1, -1);
+ maybe_rect(dr, RECT(1,1),
+ (val & PIECE_TLCORNER) ? ch | TYPE_TLCIRC :
+ !((PIECE_TBORDER | PIECE_LBORDER) &~ val) ? ch | TYPE_BRCIRC :
+ (val & (PIECE_TBORDER | PIECE_LBORDER)) ? ch : cc, -1);
+ maybe_rect(dr, RECT(2,1),
+ (val & PIECE_TBORDER) ? ch : cc, -1);
+ maybe_rect(dr, RECT(3,1),
+ (val & PIECE_TRCORNER) ? cc : -1, -1);
+ maybe_rect(dr, RECT(3,1),
+ (val & (PIECE_TBORDER | PIECE_RBORDER)) == PIECE_TBORDER ? ch :
+ (val & (PIECE_TBORDER | PIECE_RBORDER)) == PIECE_RBORDER ? cl :
+ !((PIECE_TBORDER|PIECE_RBORDER) &~ val) ? cl | TYPE_BLCIRC :
+ (val & PIECE_TRCORNER) ? cl | TYPE_TRCIRC :
+ cc, ch);
+ maybe_rect(dr, RECT(4,1),
+ (val & PIECE_TRCORNER) ? ch : (val & PIECE_RBORDER) ? -1 :
+ (val & PIECE_TBORDER) ? ch : cc, -1);
+ maybe_rect(dr, RECT(0,2),
+ (val & PIECE_LBORDER) ? -1 : cc, -1);
+ maybe_rect(dr, RECT(1,2),
+ (val & PIECE_LBORDER) ? ch : cc, -1);
+ maybe_rect(dr, RECT(2,2),
+ cc, -1);
+ maybe_rect(dr, RECT(3,2),
+ (val & PIECE_RBORDER) ? cl : cc, -1);
+ maybe_rect(dr, RECT(4,2),
+ (val & PIECE_RBORDER) ? -1 : cc, -1);
+ maybe_rect(dr, RECT(0,3),
+ (val & PIECE_BLCORNER) ? cl : (val & PIECE_LBORDER) ? -1 :
+ (val & PIECE_BBORDER) ? cl : cc, -1);
+ maybe_rect(dr, RECT(1,3),
+ (val & PIECE_BLCORNER) ? cc : -1, -1);
+ maybe_rect(dr, RECT(1,3),
+ (val & (PIECE_BBORDER | PIECE_LBORDER)) == PIECE_BBORDER ? cl :
+ (val & (PIECE_BBORDER | PIECE_LBORDER)) == PIECE_LBORDER ? ch :
+ !((PIECE_BBORDER|PIECE_LBORDER) &~ val) ? ch | TYPE_TRCIRC :
+ (val & PIECE_BLCORNER) ? ch | TYPE_BLCIRC :
+ cc, cl);
+ maybe_rect(dr, RECT(2,3),
+ (val & PIECE_BBORDER) ? cl : cc, -1);
+ maybe_rect(dr, RECT(3,3),
+ (val & PIECE_BRCORNER) ? cc : -1, -1);
+ maybe_rect(dr, RECT(3,3),
+ (val & PIECE_BRCORNER) ? cl | TYPE_BRCIRC :
+ !((PIECE_BBORDER | PIECE_RBORDER) &~ val) ? cl | TYPE_TLCIRC :
+ (val & (PIECE_BBORDER | PIECE_RBORDER)) ? cl : cc, -1);
+ maybe_rect(dr, RECT(4,3),
+ (val & PIECE_BRCORNER) ? cl : (val & PIECE_RBORDER) ? -1 :
+ (val & PIECE_BBORDER) ? cl : cc, -1);
+ maybe_rect(dr, RECT(0,4),
+ (val & (PIECE_BLCORNER | PIECE_BBORDER |
+ PIECE_LBORDER)) ? -1 : cc, -1);
+ maybe_rect(dr, RECT(1,4),
+ (val & PIECE_BLCORNER) ? ch : (val & PIECE_BBORDER) ? -1 :
+ (val & PIECE_LBORDER) ? ch : cc, -1);
+ maybe_rect(dr, RECT(2,4),
+ (val & PIECE_BBORDER) ? -1 : cc, -1);
+ maybe_rect(dr, RECT(3,4),
+ (val & PIECE_BRCORNER) ? cl : (val & PIECE_BBORDER) ? -1 :
+ (val & PIECE_RBORDER) ? cl : cc, -1);
+ maybe_rect(dr, RECT(4,4),
+ (val & (PIECE_BRCORNER | PIECE_BBORDER |
+ PIECE_RBORDER)) ? -1 : cc, -1);
+
+#undef RECT
}
static void draw_tile(drawing *dr, game_drawstate *ds,
}
}
+ /*
+ * Draw the tile midground: a shadow of a block, for
+ * displaying partial solutions.
+ */
+ if (val & FG_SHADOW) {
+ draw_piecepart(dr, ds, tx, ty, (val >> FG_SHADOWSH) & PIECE_MASK,
+ cl, cl, cl);
+ }
+
/*
* Draw the tile foreground, i.e. some section of a block or
* wall.
else if (val & FLASH_HIGH)
cc = ch;
- draw_rect(dr, tx, ty, TILESIZE, TILESIZE, cc);
- if (val & FG_LBORDER)
- draw_rect(dr, tx, ty, HIGHLIGHT_WIDTH, TILESIZE,
- ch);
- if (val & FG_RBORDER)
- draw_rect(dr, tx+TILESIZE-HIGHLIGHT_WIDTH, ty,
- HIGHLIGHT_WIDTH, TILESIZE, cl);
- if (val & FG_TBORDER)
- draw_rect(dr, tx, ty, TILESIZE, HIGHLIGHT_WIDTH, ch);
- if (val & FG_BBORDER)
- draw_rect(dr, tx, ty+TILESIZE-HIGHLIGHT_WIDTH,
- TILESIZE, HIGHLIGHT_WIDTH, cl);
- if (!((FG_BBORDER | FG_LBORDER) &~ val))
- draw_rect(dr, tx, ty+TILESIZE-HIGHLIGHT_WIDTH,
- HIGHLIGHT_WIDTH, HIGHLIGHT_WIDTH, cc);
- if (!((FG_TBORDER | FG_RBORDER) &~ val))
- draw_rect(dr, tx+TILESIZE-HIGHLIGHT_WIDTH, ty,
- HIGHLIGHT_WIDTH, HIGHLIGHT_WIDTH, cc);
- if (val & FG_TLCORNER)
- draw_rect(dr, tx, ty, HIGHLIGHT_WIDTH, HIGHLIGHT_WIDTH, ch);
- if (val & FG_BRCORNER)
- draw_rect(dr, tx+TILESIZE-HIGHLIGHT_WIDTH,
- ty+TILESIZE-HIGHLIGHT_WIDTH,
- HIGHLIGHT_WIDTH, HIGHLIGHT_WIDTH, cl);
+ draw_wallpart(dr, ds, tx, ty, (val >> FG_MAINPIECESH) & PIECE_MASK,
+ cl, cc, ch);
} else if (val & (FG_MAIN | FG_NORMAL)) {
- int x[6], y[6];
-
if (val & FG_DRAGGING)
cc = (val & FG_MAIN ? COL_MAIN_DRAGGING : COL_DRAGGING);
else
if (val & FLASH_LOW)
cc = cl;
- else if (val & FLASH_HIGH)
+ else if (val & (FLASH_HIGH | FG_SOLVEPIECE))
cc = ch;
- /*
- * Drawing the blocks is hellishly fiddly. The blocks
- * don't stretch to the full size of the tile; there's a
- * border around them of size BORDER_WIDTH. Then they have
- * bevelled borders of size HIGHLIGHT_WIDTH, and also
- * rounded corners.
- *
- * I tried for some time to find a clean and clever way to
- * figure out what needed drawing from the corner and
- * border flags, but in the end the cleanest way I could
- * find was the following. We divide the grid square into
- * 25 parts by ruling four horizontal and four vertical
- * lines across it; those lines are at BORDER_WIDTH and
- * BORDER_WIDTH+HIGHLIGHT_WIDTH from the top, from the
- * bottom, from the left and from the right. Then we
- * carefully consider each of the resulting 25 sections of
- * square, and decide separately what needs to go in it
- * based on the flags. In complicated cases there can be
- * up to five possibilities affecting any given section
- * (no corner or border flags, just the corner flag, one
- * border flag, the other border flag, both border flags).
- * So there's a lot of very fiddly logic here and all I
- * could really think to do was give it my best shot and
- * then test it and correct all the typos. Not fun to
- * write, and I'm sure it isn't fun to read either, but it
- * seems to work.
- */
-
- x[0] = tx;
- x[1] = x[0] + BORDER_WIDTH;
- x[2] = x[1] + HIGHLIGHT_WIDTH;
- x[5] = tx + TILESIZE;
- x[4] = x[5] - BORDER_WIDTH;
- x[3] = x[4] - HIGHLIGHT_WIDTH;
-
- y[0] = ty;
- y[1] = y[0] + BORDER_WIDTH;
- y[2] = y[1] + HIGHLIGHT_WIDTH;
- y[5] = ty + TILESIZE;
- y[4] = y[5] - BORDER_WIDTH;
- y[3] = y[4] - HIGHLIGHT_WIDTH;
-
-#define RECT(p,q) x[p], y[q], x[(p)+1]-x[p], y[(q)+1]-y[q]
-
- maybe_rect(dr, RECT(0,0),
- (val & (FG_TLCORNER | FG_TBORDER | FG_LBORDER)) ? -1 : cc);
- maybe_rect(dr, RECT(1,0),
- (val & FG_TLCORNER) ? ch : (val & FG_TBORDER) ? -1 :
- (val & FG_LBORDER) ? ch : cc);
- maybe_rect(dr, RECT(2,0),
- (val & FG_TBORDER) ? -1 : cc);
- maybe_rect(dr, RECT(3,0),
- (val & FG_TRCORNER) ? cl : (val & FG_TBORDER) ? -1 :
- (val & FG_RBORDER) ? cl : cc);
- maybe_rect(dr, RECT(4,0),
- (val & (FG_TRCORNER | FG_TBORDER | FG_RBORDER)) ? -1 : cc);
- maybe_rect(dr, RECT(0,1),
- (val & FG_TLCORNER) ? ch : (val & FG_LBORDER) ? -1 :
- (val & FG_TBORDER) ? ch : cc);
- maybe_rect(dr, RECT(1,1),
- (val & FG_TLCORNER) ? cc : -1);
- maybe_rect(dr, RECT(1,1),
- (val & FG_TLCORNER) ? ch | TYPE_TLCIRC :
- !((FG_TBORDER | FG_LBORDER) &~ val) ? ch | TYPE_BRCIRC :
- (val & (FG_TBORDER | FG_LBORDER)) ? ch : cc);
- maybe_rect(dr, RECT(2,1),
- (val & FG_TBORDER) ? ch : cc);
- maybe_rect(dr, RECT(3,1),
- (val & (FG_TBORDER | FG_RBORDER)) == FG_TBORDER ? ch :
- (val & (FG_TBORDER | FG_RBORDER)) == FG_RBORDER ? cl :
- !((FG_TBORDER|FG_RBORDER) &~ val) ? cc | TYPE_BLCIRC : cc);
- maybe_rect(dr, RECT(4,1),
- (val & FG_TRCORNER) ? ch : (val & FG_RBORDER) ? -1 :
- (val & FG_TBORDER) ? ch : cc);
- maybe_rect(dr, RECT(0,2),
- (val & FG_LBORDER) ? -1 : cc);
- maybe_rect(dr, RECT(1,2),
- (val & FG_LBORDER) ? ch : cc);
- maybe_rect(dr, RECT(2,2),
- cc);
- maybe_rect(dr, RECT(3,2),
- (val & FG_RBORDER) ? cl : cc);
- maybe_rect(dr, RECT(4,2),
- (val & FG_RBORDER) ? -1 : cc);
- maybe_rect(dr, RECT(0,3),
- (val & FG_BLCORNER) ? cl : (val & FG_LBORDER) ? -1 :
- (val & FG_BBORDER) ? cl : cc);
- maybe_rect(dr, RECT(1,3),
- (val & (FG_BBORDER | FG_LBORDER)) == FG_BBORDER ? cl :
- (val & (FG_BBORDER | FG_LBORDER)) == FG_LBORDER ? ch :
- !((FG_BBORDER|FG_LBORDER) &~ val) ? cc | TYPE_TRCIRC : cc);
- maybe_rect(dr, RECT(2,3),
- (val & FG_BBORDER) ? cl : cc);
- maybe_rect(dr, RECT(3,3),
- (val & FG_BRCORNER) ? cc : -1);
- maybe_rect(dr, RECT(3,3),
- (val & FG_BRCORNER) ? cl | TYPE_BRCIRC :
- !((FG_BBORDER | FG_RBORDER) &~ val) ? cl | TYPE_TLCIRC :
- (val & (FG_BBORDER | FG_RBORDER)) ? cl : cc);
- maybe_rect(dr, RECT(4,3),
- (val & FG_BRCORNER) ? cl : (val & FG_RBORDER) ? -1 :
- (val & FG_BBORDER) ? cl : cc);
- maybe_rect(dr, RECT(0,4),
- (val & (FG_BLCORNER | FG_BBORDER | FG_LBORDER)) ? -1 : cc);
- maybe_rect(dr, RECT(1,4),
- (val & FG_BLCORNER) ? ch : (val & FG_BBORDER) ? -1 :
- (val & FG_LBORDER) ? ch : cc);
- maybe_rect(dr, RECT(2,4),
- (val & FG_BBORDER) ? -1 : cc);
- maybe_rect(dr, RECT(3,4),
- (val & FG_BRCORNER) ? cl : (val & FG_BBORDER) ? -1 :
- (val & FG_RBORDER) ? cl : cc);
- maybe_rect(dr, RECT(4,4),
- (val & (FG_BRCORNER | FG_BBORDER | FG_RBORDER)) ? -1 : cc);
-
-#undef RECT
-
+ draw_piecepart(dr, ds, tx, ty, (val >> FG_MAINPIECESH) & PIECE_MASK,
+ cl, cc, ch);
}
draw_update(dr, tx, ty, TILESIZE, TILESIZE);
}
+static unsigned long find_piecepart(int w, int h, int *dsf, int x, int y)
+{
+ int i = y*w+x;
+ int canon = dsf_canonify(dsf, i);
+ unsigned long val = 0;
+
+ if (x == 0 || canon != dsf_canonify(dsf, i-1))
+ val |= PIECE_LBORDER;
+ if (y== 0 || canon != dsf_canonify(dsf, i-w))
+ val |= PIECE_TBORDER;
+ if (x == w-1 || canon != dsf_canonify(dsf, i+1))
+ val |= PIECE_RBORDER;
+ if (y == h-1 || canon != dsf_canonify(dsf, i+w))
+ val |= PIECE_BBORDER;
+ if (!(val & (PIECE_TBORDER | PIECE_LBORDER)) &&
+ canon != dsf_canonify(dsf, i-1-w))
+ val |= PIECE_TLCORNER;
+ if (!(val & (PIECE_TBORDER | PIECE_RBORDER)) &&
+ canon != dsf_canonify(dsf, i+1-w))
+ val |= PIECE_TRCORNER;
+ if (!(val & (PIECE_BBORDER | PIECE_LBORDER)) &&
+ canon != dsf_canonify(dsf, i-1+w))
+ val |= PIECE_BLCORNER;
+ if (!(val & (PIECE_BBORDER | PIECE_RBORDER)) &&
+ canon != dsf_canonify(dsf, i+1+w))
+ val |= PIECE_BRCORNER;
+ return val;
+}
+
static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate,
game_state *state, int dir, game_ui *ui,
float animtime, float flashtime)
int w = state->w, h = state->h, wh = w*h;
unsigned char *board;
int *dsf;
- int x, y, mainanchor, mainpos, dragpos;
+ int x, y, mainanchor, mainpos, dragpos, solvepos, solvesrc, solvedst;
if (!ds->started) {
/*
assert(mpret);
}
+ if (state->soln) {
+ solvesrc = state->soln->moves[state->soln_index*2];
+ solvedst = state->soln->moves[state->soln_index*2+1];
+ if (solvesrc == state->lastmoved_pos)
+ solvesrc = state->lastmoved;
+ if (solvesrc == ui->drag_anchor)
+ solvesrc = ui->drag_currpos;
+ } else
+ solvesrc = solvedst = -1;
+
/*
* Build a dsf out of that board, so we can conveniently tell
* which edges are connected and which aren't.
assert(mainanchor >= 0);
mainpos = dsf_canonify(dsf, mainanchor);
dragpos = ui->drag_currpos > 0 ? dsf_canonify(dsf, ui->drag_currpos) : -1;
+ solvepos = solvesrc >= 0 ? dsf_canonify(dsf, solvesrc) : -1;
/*
* Now we can construct the data about what we want to draw.
val |= FG_NORMAL;
if (canon == dragpos)
val |= FG_DRAGGING;
+ if (canon == solvepos)
+ val |= FG_SOLVEPIECE;
/*
* Now look around to see if other squares
* belonging to the same block are adjacent to us.
*/
- if (x == 0 || canon != dsf_canonify(dsf, i-1))
- val |= FG_LBORDER;
- if (y== 0 || canon != dsf_canonify(dsf, i-w))
- val |= FG_TBORDER;
- if (x == w-1 || canon != dsf_canonify(dsf, i+1))
- val |= FG_RBORDER;
- if (y == h-1 || canon != dsf_canonify(dsf, i+w))
- val |= FG_BBORDER;
- if (!(val & (FG_TBORDER | FG_LBORDER)) &&
- canon != dsf_canonify(dsf, i-1-w))
- val |= FG_TLCORNER;
- if (!(val & (FG_TBORDER | FG_RBORDER)) &&
- canon != dsf_canonify(dsf, i+1-w))
- val |= FG_TRCORNER;
- if (!(val & (FG_BBORDER | FG_LBORDER)) &&
- canon != dsf_canonify(dsf, i-1+w))
- val |= FG_BLCORNER;
- if (!(val & (FG_BBORDER | FG_RBORDER)) &&
- canon != dsf_canonify(dsf, i+1+w))
- val |= FG_BRCORNER;
+ val |= find_piecepart(w, h, dsf, x, y) << FG_MAINPIECESH;
+ }
+
+ /*
+ * If we're in the middle of showing a solution,
+ * display a shadow piece for the target of the
+ * current move.
+ */
+ if (solvepos >= 0) {
+ int si = i - solvedst + solvesrc;
+ if (si >= 0 && si < wh && dsf_canonify(dsf, si) == solvepos) {
+ val |= find_piecepart(w, h, dsf,
+ si % w, si / w) << FG_SHADOWSH;
+ val |= FG_SHADOW;
+ }
}
if (val != ds->grid[i]) {
{
char statusbuf[256];
- /*
- * FIXME: do something about auto-solve?
- */
sprintf(statusbuf, "%sMoves: %d",
- (state->completed >= 0 ? "COMPLETED! " : ""),
+ (state->completed >= 0 ?
+ (state->cheated ? "Auto-solved. " : "COMPLETED! ") :
+ (state->cheated ? "Auto-solver used. " : "")),
(state->completed >= 0 ? state->completed : state->movecount));
if (state->minmoves >= 0)
sprintf(statusbuf+strlen(statusbuf), " (min %d)",
new_game,
dup_game,
free_game,
- FALSE, solve_game, /* FIXME */
+ TRUE, solve_game,
TRUE, game_text_format,
new_ui,
free_ui,
FALSE, game_timing_state,
0, /* flags */
};
+
+#ifdef STANDALONE_SOLVER
+
+#include <stdarg.h>
+
+int main(int argc, char **argv)
+{
+ game_params *p;
+ game_state *s;
+ char *id = NULL, *desc, *err;
+ int count = FALSE;
+ int ret, really_verbose = FALSE;
+ int *moves;
+
+ while (--argc > 0) {
+ char *p = *++argv;
+ if (!strcmp(p, "-v")) {
+ really_verbose = TRUE;
+ } else if (!strcmp(p, "-c")) {
+ count = TRUE;
+ } else if (*p == '-') {
+ fprintf(stderr, "%s: unrecognised option `%s'\n", argv[0], p);
+ return 1;
+ } else {
+ id = p;
+ }
+ }
+
+ if (!id) {
+ fprintf(stderr, "usage: %s [-c | -v] <game_id>\n", argv[0]);
+ return 1;
+ }
+
+ desc = strchr(id, ':');
+ if (!desc) {
+ fprintf(stderr, "%s: game id expects a colon in it\n", argv[0]);
+ return 1;
+ }
+ *desc++ = '\0';
+
+ p = default_params();
+ decode_params(p, id);
+ err = validate_desc(p, desc);
+ if (err) {
+ fprintf(stderr, "%s: %s\n", argv[0], err);
+ return 1;
+ }
+ s = new_game(NULL, p, desc);
+
+ ret = solve_board(s->w, s->h, s->board, s->imm->forcefield,
+ s->tx, s->ty, -1, &moves);
+ if (ret < 0) {
+ printf("No solution found\n");
+ } else {
+ int index = 0;
+ if (count) {
+ printf("%d moves required\n", ret);
+ return 0;
+ }
+ while (1) {
+ int moveret;
+ char *text = board_text_format(s->w, s->h, s->board,
+ s->imm->forcefield);
+ game_state *s2;
+
+ printf("position %d:\n%s", index, text);
+
+ if (index >= ret)
+ break;
+
+ s2 = dup_game(s);
+ moveret = move_piece(s->w, s->h, s->board,
+ s2->board, s->imm->forcefield,
+ moves[index*2], moves[index*2+1]);
+ assert(moveret);
+
+ free_game(s);
+ s = s2;
+ index++;
+ }
+ }
+
+ return 0;
+}
+
+#endif