ref: 7fce4f57c201fe6a60ab25ccb62f089c711e97cc
parent: 6da884911025f5bfe78ffbf5389725e2b487bb5d
author: Simon Tatham <anakin@pobox.com>
date: Mon May 7 10:49:05 EDT 2007
Close-to-finished auto-generating implementation of Klotski. [originally from svn r7547]
--- /dev/null
+++ b/unfinished/slide.R
@@ -1,0 +1,21 @@
+# -*- makefile -*-
+
+SLIDE = slide dsf tree234
+
+slide : [X] GTK COMMON SLIDE slide-icon|no-icon
+
+slide : [G] WINDOWS COMMON SLIDE slide.res|noicon.res
+
+ALL += SLIDE
+
+!begin gtk
+GAMES += slide
+!end
+
+!begin >list.c
+ A(slide) \
+!end
+
+!begin >wingames.lst
+slide.exe:Slide
+!end
--- /dev/null
+++ b/unfinished/slide.c
@@ -1,0 +1,1916 @@
+/*
+ * slide.c: Implementation of the block-sliding puzzle `Klotski'.
+ */
+
+/*
+ * 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.
+ *
+ * - All the colours are a bit wishy-washy. _Some_ dark colours
+ * would surely not be excessive? Probably darken the tiles,
+ * the walls and the main block, and leave the target marker
+ * pale.
+ */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <assert.h>
+#include <ctype.h>
+#include <math.h>
+
+#include "puzzles.h"
+#include "tree234.h"
+
+/*
+ * The implementation of this game revolves around the insight
+ * which makes an exhaustive-search solver feasible: although
+ * there are many blocks which can be rearranged in many ways, any
+ * two blocks of the same shape are _indistinguishable_ and hence
+ * the number of _distinct_ board layouts is generally much
+ * smaller. So we adopt a representation for board layouts which
+ * is inherently canonical, i.e. there are no two distinct
+ * representations which encode indistinguishable layouts.
+ *
+ * The way we do this is to encode each square of the board, in
+ * the normal left-to-right top-to-bottom order, as being one of
+ * the following things:
+ * - the first square (in the given order) of a block (`anchor')
+ * - special case of the above: the anchor for the _main_ block
+ * (i.e. the one which the aim of the game is to get to the
+ * target position)
+ * - a subsequent square of a block whose previous square was N
+ * squares ago
+ * - an impassable wall
+ *
+ * (We also separately store data about which board positions are
+ * forcefields only passable by the main block. We can't encode
+ * that in the main board data, because then the main block would
+ * destroy forcefields as it went over them.)
+ *
+ * Hence, for example, a 2x2 square block would be encoded as
+ * ANCHOR, followed by DIST(1), and w-2 squares later on there
+ * would be DIST(w-1) followed by DIST(1). So if you start at the
+ * last of those squares, the DIST numbers give you a linked list
+ * pointing back through all the other squares in the same block.
+ *
+ * So the solver simply does a bfs over all reachable positions,
+ * encoding them in this format and storing them in a tree234 to
+ * ensure it doesn't ever revisit an already-analysed position.
+ */
+
+enum {+ /*
+ * The colours are arranged here so that every base colour is
+ * directly followed by its highlight colour and then its
+ * lowlight colour. Do not break this, or draw_tile() will get
+ * confused.
+ */
+ COL_BACKGROUND,
+ COL_HIGHLIGHT,
+ COL_LOWLIGHT,
+ COL_DRAGGING,
+ COL_DRAGGING_HIGHLIGHT,
+ COL_DRAGGING_LOWLIGHT,
+ COL_MAIN,
+ COL_MAIN_HIGHLIGHT,
+ COL_MAIN_LOWLIGHT,
+ COL_MAIN_DRAGGING,
+ COL_MAIN_DRAGGING_HIGHLIGHT,
+ COL_MAIN_DRAGGING_LOWLIGHT,
+ COL_TARGET,
+ COL_TARGET_HIGHLIGHT,
+ COL_TARGET_LOWLIGHT,
+ NCOLOURS
+};
+
+/*
+ * Board layout is a simple array of bytes. Each byte holds:
+ */
+#define ANCHOR 255 /* top-left-most square of some piece */
+#define MAINANCHOR 254 /* anchor of _main_ piece */
+#define EMPTY 253 /* empty square */
+#define WALL 252 /* immovable wall */
+#define MAXDIST 251
+/* all other values indicate distance back to previous square of same block */
+#define ISDIST(x) ( (unsigned char)((x)-1) <= MAXDIST-1 )
+#define DIST(x) (x)
+#define ISANCHOR(x) ( (x)==ANCHOR || (x)==MAINANCHOR )
+#define ISBLOCK(x) ( ISANCHOR(x) || ISDIST(x) )
+
+/*
+ * MAXDIST is the largest DIST value we can encode. This must
+ * therefore also be the maximum puzzle width in theory (although
+ * solver running time will dictate a much smaller limit in
+ * practice).
+ */
+#define MAXWID MAXDIST
+
+struct game_params {+ int w, h;
+};
+
+struct game_immutable_state {+ int refcount;
+ unsigned char *forcefield;
+};
+
+struct game_state {+ int w, h;
+ unsigned char *board;
+ int tx, ty; /* target coords for MAINANCHOR */
+ int minmoves; /* for display only */
+ int lastmoved, lastmoved_pos; /* for move counting */
+ int movecount;
+ int completed;
+ struct game_immutable_state *imm;
+};
+
+static game_params *default_params(void)
+{+ game_params *ret = snew(game_params);
+
+ ret->w = 8;
+ ret->h = 6;
+
+ return ret;
+}
+
+static const struct game_params slide_presets[] = {+ {6, 5},+ {7, 5},+ {7, 6},+ {8, 6},+};
+
+static int game_fetch_preset(int i, char **name, game_params **params)
+{+ game_params *ret;
+ char str[80];
+
+ if (i < 0 || i >= lenof(slide_presets))
+ return FALSE;
+
+ ret = snew(game_params);
+ *ret = slide_presets[i];
+
+ sprintf(str, "%dx%d", ret->w, ret->h);
+
+ *name = dupstr(str);
+ *params = ret;
+ return TRUE;
+}
+
+static void free_params(game_params *params)
+{+ sfree(params);
+}
+
+static game_params *dup_params(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);
+ }
+}
+
+static char *encode_params(game_params *params, int full)
+{+ char data[256];
+
+ sprintf(data, "%dx%d", params->w, params->h);
+
+ return dupstr(data);
+}
+
+static config_item *game_configure(game_params *params)
+{+ config_item *ret;
+ char buf[80];
+
+ ret = snewn(3, 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 = NULL;
+ ret[2].type = C_END;
+ ret[2].sval = NULL;
+ ret[2].ival = 0;
+
+ return ret;
+}
+
+static game_params *custom_params(config_item *cfg)
+{+ game_params *ret = snew(game_params);
+
+ ret->w = atoi(cfg[0].sval);
+ ret->h = atoi(cfg[1].sval);
+
+ return ret;
+}
+
+static char *validate_params(game_params *params, int full)
+{+ if (params->w > MAXWID)
+ return "Width must be at most " STR(MAXWID);
+
+ if (params->w < 5)
+ return "Width must be at least 5";
+ if (params->h < 4)
+ return "Height must be at least 4";
+
+ return NULL;
+}
+
+static char *board_text_format(int w, int h, unsigned char *data,
+ unsigned char *forcefield)
+{+ int wh = w*h;
+ int *dsf = snew_dsf(wh);
+ int i, x, y;
+ int retpos, retlen = (w*2+2)*(h*2+1)+1;
+ char *ret = snewn(retlen, char);
+
+ for (i = 0; i < wh; i++)
+ if (ISDIST(data[i]))
+ dsf_merge(dsf, i - data[i], i);
+ retpos = 0;
+ for (y = 0; y < 2*h+1; y++) {+ for (x = 0; x < 2*w+1; x++) {+ int v;
+ int i = (y/2)*w+(x/2);
+
+#define dtype(i) (ISBLOCK(data[i]) ? \
+ dsf_canonify(dsf, i) : data[i])
+#define dchar(t) ((t)==EMPTY ? ' ' : (t)==WALL ? '#' : \
+ data[t] == MAINANCHOR ? '*' : '%')
+
+ if (y % 2 && x % 2) {+ int j = dtype(i);
+ v = dchar(j);
+ } else if (y % 2 && !(x % 2)) {+ int j1 = (x > 0 ? dtype(i-1) : -1);
+ int j2 = (x < 2*w ? dtype(i) : -1);
+ if (j1 != j2)
+ v = '|';
+ else
+ v = dchar(j1);
+ } else if (!(y % 2) && (x % 2)) {+ int j1 = (y > 0 ? dtype(i-w) : -1);
+ int j2 = (y < 2*h ? dtype(i) : -1);
+ if (j1 != j2)
+ v = '-';
+ else
+ v = dchar(j1);
+ } else {+ int j1 = (x > 0 && y > 0 ? dtype(i-w-1) : -1);
+ int j2 = (x > 0 && y < 2*h ? dtype(i-1) : -1);
+ int j3 = (x < 2*w && y > 0 ? dtype(i-w) : -1);
+ int j4 = (x < 2*w && y < 2*h ? dtype(i) : -1);
+ if (j1 == j2 && j2 == j3 && j3 == j4)
+ v = dchar(j1);
+ else if (j1 == j2 && j3 == j4)
+ v = '|';
+ else if (j1 == j3 && j2 == j4)
+ v = '-';
+ else
+ v = '+';
+ }
+
+ assert(retpos < retlen);
+ ret[retpos++] = v;
+ }
+ assert(retpos < retlen);
+ ret[retpos++] = '\n';
+ }
+ assert(retpos < retlen);
+ ret[retpos++] = '\0';
+ assert(retpos == retlen);
+
+ return ret;
+}
+
+/* ----------------------------------------------------------------------
+ * Solver.
+ */
+
+/*
+ * During solver execution, the set of visited board positions is
+ * stored as a tree234 of the following structures. `w', `h' and
+ * `data' are obvious in meaning; `dist' represents the minimum
+ * distance to reach this position from the starting point.
+ *
+ * `prev' links each board to the board position from which it was
+ * most efficiently derived.
+ */
+struct board {+ int w, h;
+ int dist;
+ struct board *prev;
+ unsigned char *data;
+};
+
+static int boardcmp(void *av, void *bv)
+{+ struct board *a = (struct board *)av;
+ struct board *b = (struct board *)bv;
+ return memcmp(a->data, b->data, a->w * a->h);
+}
+
+static struct board *newboard(int w, int h, unsigned char *data)
+{+ struct board *b = malloc(sizeof(struct board) + w*h);
+ b->data = (unsigned char *)b + sizeof(struct board);
+ memcpy(b->data, data, w*h);
+ b->w = w;
+ b->h = h;
+ b->dist = -1;
+ b->prev = NULL;
+ return b;
+}
+
+/*
+ * 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.
+ */
+static int solve_board(int w, int h, unsigned char *board,
+ unsigned char *forcefield, int tx, int ty)
+{+ int wh = w*h;
+ struct board *b, *b2, *b3;
+ int *next, *anchors, *which;
+ int *movereached, *movequeue, mqhead, mqtail;
+ tree234 *sorted, *queue;
+ int i, j, dir;
+ int qlen, lastdist;
+ int ret;
+
+#ifdef SOLVER_DIAGNOSTICS
+ {+ char *t = board_text_format(w, h, board);
+ for (i = 0; i < h; i++) {+ for (j = 0; j < w; j++) {+ int c = board[i*w+j];
+ if (ISDIST(c))
+ printf("D%-3d", c);+ else if (c == MAINANCHOR)
+ printf("M ");+ else if (c == ANCHOR)
+ printf("A ");+ else if (c == WALL)
+ printf("W ");+ else if (c == EMPTY)
+ printf("E ");+ }
+ printf("\n");+ }
+
+ printf("Starting solver for:\n%s\n", t);+ sfree(t);
+ }
+#endif
+
+ sorted = newtree234(boardcmp);
+ queue = newtree234(NULL);
+
+ b = newboard(w, h, board);
+ b->dist = 0;
+ add234(sorted, b);
+ addpos234(queue, b, 0);
+ qlen = 1;
+
+ next = snewn(wh, int);
+ anchors = snewn(wh, int);
+ which = snewn(wh, int);
+ movereached = snewn(wh, int);
+ movequeue = snewn(wh, int);
+ lastdist = -1;
+
+ while ((b = delpos234(queue, 0)) != NULL) {+ qlen--;
+ if (b->dist != lastdist) {+#ifdef SOLVER_DIAGNOSTICS
+ printf("dist %d (%d)\n", b->dist, count234(sorted));+#endif
+ lastdist = b->dist;
+ }
+ /*
+ * Find all the anchors and form a linked list of the
+ * squares within each block.
+ */
+ for (i = 0; i < wh; i++) {+ next[i] = -1;
+ anchors[i] = FALSE;
+ which[i] = -1;
+ if (ISANCHOR(b->data[i])) {+ anchors[i] = TRUE;
+ which[i] = i;
+ } else if (ISDIST(b->data[i])) {+ j = i - b->data[i];
+ next[j] = i;
+ which[i] = which[j];
+ }
+ }
+
+ /*
+ * For each anchor, do an array-based BFS to find all the
+ * places we can slide it to.
+ */
+ for (i = 0; i < wh; i++) {+ if (!anchors[i])
+ continue;
+
+ mqhead = mqtail = 0;
+ for (j = 0; j < wh; j++)
+ movereached[j] = FALSE;
+ movequeue[mqtail++] = i;
+ while (mqhead < mqtail) {+ int pos = movequeue[mqhead++];
+
+ /*
+ * Try to move in each direction from here.
+ */
+ for (dir = 0; dir < 4; dir++) {+ int dx = (dir == 0 ? -1 : dir == 1 ? +1 : 0);
+ int dy = (dir == 2 ? -1 : dir == 3 ? +1 : 0);
+ int offset = dy*w + dx;
+ int newpos = pos + offset;
+ int d = newpos - i;
+
+ /*
+ * For each square involved in this block,
+ * check to see if the square d spaces away
+ * from it is either empty or part of the same
+ * block.
+ */
+ for (j = i; j >= 0; j = next[j]) {+ int jy = (pos+j-i) / w + dy, jx = (pos+j-i) % w + dx;
+ if (jy >= 0 && jy < h && jx >= 0 && jx < w &&
+ ((b->data[j+d] == EMPTY || which[j+d] == i) &&
+ (b->data[i] == MAINANCHOR || !forcefield[j+d])))
+ /* ok */;
+ else
+ break;
+ }
+ if (j >= 0)
+ continue; /* this direction wasn't feasible */
+
+ /*
+ * If we've already tried moving this piece
+ * here, leave it.
+ */
+ if (movereached[newpos])
+ continue;
+ movereached[newpos] = TRUE;
+ movequeue[mqtail++] = newpos;
+
+ /*
+ * We have a viable move. Make it.
+ */
+ b2 = newboard(w, h, b->data);
+ for (j = i; j >= 0; j = next[j])
+ b2->data[j] = EMPTY;
+ for (j = i; j >= 0; j = next[j])
+ b2->data[j+d] = b->data[j];
+
+ b3 = add234(sorted, b2);
+ if (b3 != b2) {+ sfree(b2); /* we already got one */
+ } else {+ b2->dist = b->dist + 1;
+ b2->prev = b;
+ addpos234(queue, b2, qlen++);
+ if (b2->data[ty*w+tx] == MAINANCHOR)
+ goto done; /* search completed! */
+ }
+ }
+ }
+ }
+ }
+ b2 = NULL;
+
+ done:
+
+ if (b2)
+ ret = b2->dist;
+ else
+ ret = -1; /* no solution */
+
+ freetree234(queue);
+
+ while ((b = delpos234(sorted, 0)) != NULL)
+ sfree(b);
+ freetree234(sorted);
+
+ sfree(next);
+ sfree(anchors);
+ sfree(movereached);
+ sfree(movequeue);
+ sfree(which);
+
+ return ret;
+}
+
+/* ----------------------------------------------------------------------
+ * Random board generation.
+ */
+
+static void generate_board(int w, int h, int *rtx, int *rty, int *minmoves,
+ random_state *rs, unsigned char **rboard,
+ unsigned char **rforcefield)
+{+ int wh = w*h;
+ unsigned char *board, *board2, *forcefield;
+ int *list, nlist, pos;
+ int tx, ty;
+ int i, j;
+ int moves;
+
+ /*
+ * Set up a board and fill it with singletons, except for a
+ * border of walls.
+ */
+ board = snewn(wh, unsigned char);
+ forcefield = snewn(wh, unsigned char);
+ board2 = snewn(wh, unsigned char);
+ memset(board, ANCHOR, wh);
+ memset(forcefield, FALSE, wh);
+ for (i = 0; i < w; i++)
+ board[i] = board[i+w*(h-1)] = WALL;
+ for (i = 0; i < h; i++)
+ board[i*w] = board[i*w+(w-1)] = WALL;
+
+ /*
+ * Invent a main piece at one extreme. (FIXME: vary the
+ * extreme, and the piece.)
+ */
+ board[w+1] = MAINANCHOR;
+ board[w+2] = DIST(1);
+ board[w*2+1] = DIST(w-1);
+ board[w*2+2] = DIST(1);
+
+ /*
+ * Invent a target position. (FIXME: vary this too.)
+ */
+ tx = w-2;
+ ty = h-3;
+ forcefield[ty*w+tx+1] = forcefield[(ty+1)*w+tx+1] = TRUE;
+ board[ty*w+tx+1] = board[(ty+1)*w+tx+1] = EMPTY;
+
+ /*
+ * Gradually remove singletons until the game becomes soluble.
+ */
+ for (j = w; j-- > 0 ;)
+ for (i = h; i-- > 0 ;)
+ if (board[i*w+j] == ANCHOR) {+ /*
+ * See if the board is already soluble.
+ */
+ if ((moves = solve_board(w, h, board, forcefield,
+ tx, ty)) >= 0)
+ goto soluble;
+
+ /*
+ * Otherwise, remove this piece.
+ */
+ board[i*w+j] = EMPTY;
+ }
+ assert(!"We shouldn't get here");
+ soluble:
+
+ /*
+ * Make a list of all the inter-block edges on the board.
+ */
+ list = snewn(wh*2, int);
+ nlist = 0;
+ for (i = 0; i+1 < w; i++)
+ for (j = 0; j < h; j++)
+ list[nlist++] = (j*w+i) * 2 + 0; /* edge to the right of j*w+i */
+ for (j = 0; j+1 < h; j++)
+ for (i = 0; i < w; i++)
+ list[nlist++] = (j*w+i) * 2 + 1; /* edge below j*w+i */
+
+ /*
+ * Now go through that list in random order, trying to merge
+ * the blocks on each side of each edge.
+ *
+ * FIXME: this seems to produce unpleasantly unbalanced
+ * results. Perhaps we'd do better if we always tried to
+ * combine the _smallest_ block with something?
+ *
+ * FIXME: also one reason it's slow might be because we aren't
+ * tracking which blocks we've already tried to merge, when
+ * another edge ends up linking the same ones.
+ */
+ shuffle(list, nlist, sizeof(*list), rs);
+ while (nlist > 0) {+ int x1, y1, p1;
+ int x2, y2, p2;
+
+ pos = list[--nlist];
+ y1 = y2 = pos / (w*2);
+ x1 = x2 = (pos / 2) % w;
+ if (pos % 2)
+ y2++;
+ else
+ x2++;
+ p1 = y1*w+x1;
+ p2 = y2*w+x2;
+
+ /*
+ * In order to be mergeable, these two squares must each
+ * either be, or belong to, a non-main anchor, and their
+ * anchors must also be distinct.
+ */
+ if (!ISBLOCK(board[p1]) || !ISBLOCK(board[p2]))
+ continue;
+ while (ISDIST(board[p1]))
+ p1 -= board[p1];
+ while (ISDIST(board[p2]))
+ p2 -= board[p2];
+ if (board[p1] == MAINANCHOR || board[p2] == MAINANCHOR || p1 == p2)
+ continue;
+
+ /*
+ * We can merge these blocks. Try it, and see if the
+ * puzzle remains soluble.
+ */
+ memcpy(board2, board, wh);
+ j = -1;
+ while (p1 < wh || p2 < wh) {+ /*
+ * p1 and p2 are the squares at the head of each block
+ * list. Pick the smaller one and put it on the output
+ * block list.
+ */
+ i = min(p1, p2);
+ if (j < 0) {+ board[i] = ANCHOR;
+ } else {+ assert(i - j <= MAXDIST);
+ board[i] = DIST(i - j);
+ }
+ j = i;
+
+ /*
+ * Now advance whichever list that came from.
+ */
+ if (i == p1) {+ do {+ p1++;
+ } while (p1 < wh && board[p1] != DIST(p1-i));
+ } else {+ do {+ p2++;
+ } while (p2 < wh && board[p2] != DIST(p2-i));
+ }
+ }
+ j = solve_board(w, h, board, forcefield, tx, ty);
+ if (j < 0) {+ /*
+ * Didn't work. Revert the merge.
+ */
+ memcpy(board, board2, wh);
+ } else {+ moves = j;
+ }
+ }
+
+ sfree(board2);
+
+ *rtx = tx;
+ *rty = ty;
+ *rboard = board;
+ *rforcefield = forcefield;
+ *minmoves = moves;
+}
+
+/* ----------------------------------------------------------------------
+ * End of solver/generator code.
+ */
+
+static char *new_game_desc(game_params *params, random_state *rs,
+ char **aux, int interactive)
+{+ int w = params->w, h = params->h, wh = w*h;
+ int tx, ty, minmoves;
+ unsigned char *board, *forcefield;
+ char *ret, *p;
+ int i;
+
+ generate_board(params->w, params->h, &tx, &ty, &minmoves, rs,
+ &board, &forcefield);
+#ifdef GENERATOR_DIAGNOSTICS
+ {+ char *t = board_text_format(params->w, params->h, board);
+ printf("%s\n", t);+ sfree(t);
+ }
+#endif
+
+ /*
+ * Encode as a game ID.
+ */
+ ret = snewn(wh * 6 + 40, char);
+ p = ret;
+ i = 0;
+ while (i < wh) {+ if (ISDIST(board[i])) {+ p += sprintf(p, "d%d", board[i]);
+ i++;
+ } else {+ int count = 1;
+ int b = board[i], f = forcefield[i];
+ int c = (b == ANCHOR ? 'a' :
+ b == MAINANCHOR ? 'm' :
+ b == EMPTY ? 'e' :
+ /* b == WALL ? */ 'w');
+ if (f) *p++ = 'f';
+ *p++ = c;
+ i++;
+ while (i < wh && board[i] == b && forcefield[i] == f)
+ i++, count++;
+ if (count > 1)
+ p += sprintf(p, "%d", count);
+ }
+ }
+ 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);
+
+ return ret;
+}
+
+static char *validate_desc(game_params *params, char *desc)
+{+ int w = params->w, h = params->h, wh = w*h;
+ int *active, *link;
+ int mains = 0, mpos = -1;
+ int i, j, tx, ty, minmoves;
+ char *ret;
+
+ active = snewn(wh, int);
+ link = snewn(wh, int);
+ i = 0;
+
+ while (*desc && *desc != ',') {+ if (i >= wh) {+ ret = "Too much data in game description";
+ goto done;
+ }
+ link[i] = -1;
+ active[i] = FALSE;
+ if (*desc == 'f' || *desc == 'F') {+ desc++;
+ if (!*desc) {+ ret = "Expected another character after 'f' in game "
+ "description";
+ goto done;
+ }
+ }
+
+ if (*desc == 'd' || *desc == 'D') {+ int dist;
+
+ desc++;
+ if (!isdigit((unsigned char)*desc)) {+ ret = "Expected a number after 'd' in game description";
+ goto done;
+ }
+ dist = atoi(desc);
+ while (*desc && isdigit((unsigned char)*desc)) desc++;
+
+ if (dist <= 0 || dist > i) {+ ret = "Out-of-range number after 'd' in game description";
+ goto done;
+ }
+
+ if (!active[i - dist]) {+ ret = "Invalid back-reference in game description";
+ goto done;
+ }
+
+ 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;
+ i++;
+ } else {+ int c = *desc++;
+ int count = 1;
+
+ if (!strchr("aAmMeEwW", c)) {+ ret = "Invalid character in game description";
+ goto done;
+ }
+ if (isdigit((unsigned char)*desc)) {+ count = atoi(desc);
+ while (*desc && isdigit((unsigned char)*desc)) desc++;
+ }
+ if (i + count > wh) {+ ret = "Too much data in game description";
+ goto done;
+ }
+ while (count-- > 0) {+ active[i] = (strchr("aAmM", c) != NULL);+ link[i] = -1;
+ if (strchr("mM", c) != NULL) {+ mains++;
+ mpos = i;
+ }
+ i++;
+ }
+ }
+ }
+ if (mains != 1) {+ ret = (mains == 0 ? "No main piece specified in game description" :
+ "More than one main piece specified in game description");
+ goto done;
+ }
+ if (i < wh) {+ ret = "Not enough data in game description";
+ goto done;
+ }
+
+ /*
+ * Now read the target coordinates.
+ */
+ i = sscanf(desc, ",%d,%d,%d", &tx, &ty, &minmoves);
+ if (i < 2) {+ ret = "No target coordinates specified";
+ goto done;
+ /*
+ * (but minmoves is optional)
+ */
+ }
+
+ ret = NULL;
+
+ done:
+ sfree(active);
+ sfree(link);
+ return ret;
+}
+
+static game_state *new_game(midend *me, game_params *params, char *desc)
+{+ int w = params->w, h = params->h, wh = w*h;
+ game_state *state;
+ int i;
+
+ state = snew(game_state);
+ state->w = w;
+ state->h = h;
+ state->board = snewn(wh, unsigned char);
+ state->lastmoved = state->lastmoved_pos = -1;
+ state->movecount = 0;
+ state->imm = snew(struct game_immutable_state);
+ state->imm->refcount = 1;
+ state->imm->forcefield = snewn(wh, unsigned char);
+
+ i = 0;
+
+ while (*desc && *desc != ',') {+ int f = FALSE;
+
+ assert(i < wh);
+
+ if (*desc == 'f') {+ f = TRUE;
+ desc++;
+ assert(*desc);
+ }
+
+ if (*desc == 'd' || *desc == 'D') {+ int dist;
+
+ desc++;
+ dist = atoi(desc);
+ while (*desc && isdigit((unsigned char)*desc)) desc++;
+
+ state->board[i] = DIST(dist);
+ state->imm->forcefield[i] = f;
+
+ i++;
+ } else {+ int c = *desc++;
+ int count = 1;
+
+ if (isdigit((unsigned char)*desc)) {+ count = atoi(desc);
+ while (*desc && isdigit((unsigned char)*desc)) desc++;
+ }
+ assert(i + count <= wh);
+
+ c = (c == 'a' || c == 'A' ? ANCHOR :
+ c == 'm' || c == 'M' ? MAINANCHOR :
+ c == 'e' || c == 'E' ? EMPTY :
+ /* c == 'w' || c == 'W' ? */ WALL);
+
+ while (count-- > 0) {+ state->board[i] = c;
+ state->imm->forcefield[i] = f;
+ i++;
+ }
+ }
+ }
+
+ /*
+ * Now read the target coordinates.
+ */
+ state->tx = state->ty = 0;
+ state->minmoves = -1;
+ i = sscanf(desc, ",%d,%d,%d", &state->tx, &state->ty, &state->minmoves);
+
+ if (state->board[state->ty*w+state->tx] == MAINANCHOR)
+ state->completed = 0; /* already complete! */
+ else
+ state->completed = -1;
+
+ return state;
+}
+
+static game_state *dup_game(game_state *state)
+{+ int w = state->w, h = state->h, wh = w*h;
+ game_state *ret = snew(game_state);
+
+ ret->w = state->w;
+ ret->h = state->h;
+ ret->board = snewn(wh, unsigned char);
+ memcpy(ret->board, state->board, wh);
+ ret->tx = state->tx;
+ ret->ty = state->ty;
+ ret->minmoves = state->minmoves;
+ ret->lastmoved = state->lastmoved;
+ ret->lastmoved_pos = state->lastmoved_pos;
+ ret->movecount = state->movecount;
+ ret->completed = state->completed;
+ ret->imm = state->imm;
+ ret->imm->refcount++;
+
+ return ret;
+}
+
+static void free_game(game_state *state)
+{+ if (--state->imm->refcount <= 0) {+ sfree(state->imm->forcefield);
+ sfree(state->imm);
+ }
+ sfree(state->board);
+ sfree(state);
+}
+
+static char *solve_game(game_state *state, game_state *currstate,
+ char *aux, char **error)
+{+ /*
+ * FIXME: we have a solver, so use it
+ *
+ * FIXME: we should have generated an aux string, so use that
+ */
+ return NULL;
+}
+
+static char *game_text_format(game_state *state)
+{+ return board_text_format(state->w, state->h, state->board,
+ state->imm->forcefield);
+}
+
+struct game_ui {+ int dragging;
+ int drag_anchor;
+ int drag_offset_x, drag_offset_y;
+ int drag_currpos;
+ unsigned char *reachable;
+ int *bfs_queue; /* used as scratch in interpret_move */
+};
+
+static game_ui *new_ui(game_state *state)
+{+ int w = state->w, h = state->h, wh = w*h;
+ game_ui *ui = snew(game_ui);
+
+ ui->dragging = FALSE;
+ ui->drag_anchor = ui->drag_currpos = -1;
+ ui->drag_offset_x = ui->drag_offset_y = -1;
+ ui->reachable = snewn(wh, unsigned char);
+ memset(ui->reachable, 0, wh);
+ ui->bfs_queue = snewn(wh, int);
+
+ return ui;
+}
+
+static void free_ui(game_ui *ui)
+{+ sfree(ui->bfs_queue);
+ sfree(ui->reachable);
+ sfree(ui);
+}
+
+static char *encode_ui(game_ui *ui)
+{+ return NULL;
+}
+
+static void decode_ui(game_ui *ui, char *encoding)
+{+}
+
+static void game_changed_state(game_ui *ui, game_state *oldstate,
+ game_state *newstate)
+{+}
+
+#define PREFERRED_TILESIZE 32
+#define TILESIZE (ds->tilesize)
+#define BORDER (TILESIZE/2)
+#define COORD(x) ( (x) * TILESIZE + BORDER )
+#define FROMCOORD(x) ( ((x) - BORDER + TILESIZE) / TILESIZE - 1 )
+#define BORDER_WIDTH (1 + TILESIZE/20)
+#define HIGHLIGHT_WIDTH (1 + TILESIZE/16)
+
+#define FLASH_INTERVAL 0.10F
+#define FLASH_TIME 3*FLASH_INTERVAL
+
+struct game_drawstate {+ int tilesize;
+ int w, h;
+ unsigned long *grid; /* what's currently displayed */
+ int started;
+};
+
+static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds,
+ int x, int y, int button)
+{+ int w = state->w, h = state->h, wh = w*h;
+ int tx, ty, i, j;
+ int qhead, qtail;
+
+ if (button == LEFT_BUTTON) {+ tx = FROMCOORD(x);
+ ty = FROMCOORD(y);
+
+ if (tx < 0 || tx >= w || ty < 0 || ty >= h ||
+ !ISBLOCK(state->board[ty*w+tx]))
+ return NULL; /* this click has no effect */
+
+ /*
+ * User has clicked on a block. Find the block's anchor
+ * and register that we've started dragging it.
+ */
+ i = ty*w+tx;
+ while (ISDIST(state->board[i]))
+ i -= state->board[i];
+ assert(i >= 0 && i < wh);
+
+ ui->dragging = TRUE;
+ ui->drag_anchor = i;
+ ui->drag_offset_x = tx - (i % w);
+ ui->drag_offset_y = ty - (i / w);
+ ui->drag_currpos = i;
+
+ /*
+ * Now we immediately bfs out from the current location of
+ * the anchor, to find all the places to which this block
+ * can be dragged.
+ */
+ memset(ui->reachable, FALSE, wh);
+ qhead = qtail = 0;
+ ui->reachable[i] = TRUE;
+ ui->bfs_queue[qtail++] = i;
+ for (j = i; j < wh; j++)
+ if (state->board[j] == DIST(j - i))
+ i = j;
+ while (qhead < qtail) {+ int pos = ui->bfs_queue[qhead++];
+ int x = pos % w, y = pos / w;
+ int dir;
+
+ for (dir = 0; dir < 4; dir++) {+ int dx = (dir == 0 ? -1 : dir == 1 ? +1 : 0);
+ int dy = (dir == 2 ? -1 : dir == 3 ? +1 : 0);
+ int newpos;
+
+ if (x + dx < 0 || x + dx >= w ||
+ y + dy < 0 || y + dy >= h)
+ continue;
+
+ newpos = pos + dy*w + dx;
+ if (ui->reachable[newpos])
+ continue; /* already done this one */
+
+ /*
+ * Now search the grid to see if the block we're
+ * dragging could fit into this space.
+ */
+ for (j = i; j >= 0; j = (ISDIST(state->board[j]) ?
+ j - state->board[j] : -1)) {+ int jx = (j+pos-ui->drag_anchor) % w;
+ int jy = (j+pos-ui->drag_anchor) / w;
+ int j2;
+
+ if (jx + dx < 0 || jx + dx >= w ||
+ jy + dy < 0 || jy + dy >= h)
+ break; /* this position isn't valid at all */
+
+ j2 = (j+pos-ui->drag_anchor) + dy*w + dx;
+
+ if (state->board[j2] == EMPTY &&
+ (!state->imm->forcefield[j2] ||
+ state->board[ui->drag_anchor] == MAINANCHOR))
+ continue;
+ while (ISDIST(state->board[j2]))
+ j2 -= state->board[j2];
+ assert(j2 >= 0 && j2 < wh);
+ if (j2 == ui->drag_anchor)
+ continue;
+ else
+ break;
+ }
+
+ if (j < 0) {+ /*
+ * If we got to the end of that loop without
+ * disqualifying this position, mark it as
+ * reachable for this drag.
+ */
+ ui->reachable[newpos] = TRUE;
+ ui->bfs_queue[qtail++] = newpos;
+ }
+ }
+ }
+
+ /*
+ * And that's it. Update the display to reflect the start
+ * of a drag.
+ */
+ return "";
+ } else if (button == LEFT_DRAG && ui->dragging) {+ 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 "";
+ } else if (button == LEFT_RELEASE && ui->dragging) {+ char data[256], *str;
+
+ /*
+ * Terminate the drag, and if the piece has actually moved
+ * then return a move string quoting the old and new
+ * locations of the piece's anchor.
+ */
+ if (ui->drag_anchor != ui->drag_currpos) {+ sprintf(data, "M%d-%d", ui->drag_anchor, ui->drag_currpos);
+ str = dupstr(data);
+ } else
+ str = ""; /* null move; just update the UI */
+
+ ui->dragging = FALSE;
+ ui->drag_anchor = ui->drag_currpos = -1;
+ ui->drag_offset_x = ui->drag_offset_y = -1;
+ memset(ui->reachable, 0, wh);
+
+ return str;
+ }
+
+ return NULL;
+}
+
+static int move_piece(int w, int h, const unsigned char *src,
+ unsigned char *dst, unsigned char *ff, int from, int to)
+{+ int wh = w*h;
+ int i, j;
+
+ if (!ISANCHOR(dst[from]))
+ return FALSE;
+
+ /*
+ * Scan to the far end of the piece's linked list.
+ */
+ for (i = j = from; j < wh; j++)
+ if (src[j] == DIST(j - i))
+ i = j;
+
+ /*
+ * Remove the piece from its old location in the new
+ * game state.
+ */
+ for (j = i; j >= 0; j = (ISDIST(src[j]) ? j - src[j] : -1))
+ dst[j] = EMPTY;
+
+ /*
+ * And put it back in at the new location.
+ */
+ for (j = i; j >= 0; j = (ISDIST(src[j]) ? j - src[j] : -1)) {+ int jn = j + to - from;
+ if (jn < 0 || jn >= wh)
+ return FALSE;
+ if (dst[jn] == EMPTY && (!ff[jn] || src[from] == MAINANCHOR)) {+ dst[jn] = src[j];
+ } else {+ return FALSE;
+ }
+ }
+
+ return TRUE;
+}
+
+static game_state *execute_move(game_state *state, char *move)
+{+ int w = state->w, h = state->h /* , wh = w*h */;
+ char c;
+ int a1, a2, n;
+ game_state *ret = dup_game(state);
+
+ while (*move) {+ c = *move;
+ if (c == 'M') {+ move++;
+ if (sscanf(move, "%d-%d%n", &a1, &a2, &n) != 2 ||
+ !move_piece(w, h, state->board, ret->board,
+ state->imm->forcefield, a1, a2)) {+ free_game(ret);
+ return NULL;
+ }
+ if (a1 == ret->lastmoved) {+ /*
+ * If the player has moved the same piece as they
+ * moved last time, don't increment the move
+ * count. In fact, if they've put the piece back
+ * where it started from, _decrement_ the move
+ * count.
+ */
+ if (a2 == ret->lastmoved_pos) {+ ret->movecount--; /* reverted last move */
+ ret->lastmoved = ret->lastmoved_pos = -1;
+ } else {+ ret->lastmoved = a2;
+ /* don't change lastmoved_pos */
+ }
+ } else {+ ret->lastmoved = a2;
+ ret->lastmoved_pos = a1;
+ ret->movecount++;
+ }
+ if (ret->board[a2] == MAINANCHOR &&
+ a2 == ret->ty * w + ret->tx && ret->completed < 0)
+ ret->completed = ret->movecount;
+ move += n;
+ } else {+ free_game(ret);
+ return NULL;
+ }
+ if (*move == ';')
+ move++;
+ else if (*move) {+ free_game(ret);
+ return NULL;
+ }
+ }
+
+ return ret;
+}
+
+/* ----------------------------------------------------------------------
+ * Drawing routines.
+ */
+
+static void game_compute_size(game_params *params, int tilesize,
+ int *x, int *y)
+{+ /* fool the macros */
+ struct dummy { int tilesize; } dummy = { tilesize }, *ds = &dummy;+
+ *x = params->w * TILESIZE + 2*BORDER;
+ *y = params->h * TILESIZE + 2*BORDER;
+}
+
+static void game_set_size(drawing *dr, game_drawstate *ds,
+ game_params *params, int tilesize)
+{+ ds->tilesize = tilesize;
+}
+
+static void raise_colour(float *target, float *src, float *limit)
+{+ int i;
+ for (i = 0; i < 3; i++)
+ target[i] = (2*src[i] + limit[i]) / 3;
+}
+
+static float *game_colours(frontend *fe, int *ncolours)
+{+ float *ret = snewn(3 * NCOLOURS, float);
+
+ game_mkhighlight(fe, ret, COL_BACKGROUND, COL_HIGHLIGHT, COL_LOWLIGHT);
+
+ /*
+ * When dragging a tile, we light it up a bit.
+ */
+ raise_colour(ret+3*COL_DRAGGING,
+ ret+3*COL_BACKGROUND, ret+3*COL_HIGHLIGHT);
+ raise_colour(ret+3*COL_DRAGGING_HIGHLIGHT,
+ ret+3*COL_HIGHLIGHT, ret+3*COL_HIGHLIGHT);
+ raise_colour(ret+3*COL_DRAGGING_LOWLIGHT,
+ ret+3*COL_LOWLIGHT, ret+3*COL_HIGHLIGHT);
+
+ /*
+ * The main tile is tinted blue.
+ */
+ ret[COL_MAIN * 3 + 0] = ret[COL_BACKGROUND * 3 + 0];
+ ret[COL_MAIN * 3 + 1] = ret[COL_BACKGROUND * 3 + 1];
+ ret[COL_MAIN * 3 + 2] = ret[COL_HIGHLIGHT * 3 + 2];
+ game_mkhighlight_specific(fe, ret, COL_MAIN,
+ COL_MAIN_HIGHLIGHT, COL_MAIN_LOWLIGHT);
+
+ /*
+ * And we light that up a bit too when dragging.
+ */
+ raise_colour(ret+3*COL_MAIN_DRAGGING,
+ ret+3*COL_MAIN, ret+3*COL_MAIN_HIGHLIGHT);
+ raise_colour(ret+3*COL_MAIN_DRAGGING_HIGHLIGHT,
+ ret+3*COL_MAIN_HIGHLIGHT, ret+3*COL_MAIN_HIGHLIGHT);
+ raise_colour(ret+3*COL_MAIN_DRAGGING_LOWLIGHT,
+ ret+3*COL_MAIN_LOWLIGHT, ret+3*COL_MAIN_HIGHLIGHT);
+
+ /*
+ * The target area on the floor is tinted green.
+ */
+ ret[COL_TARGET * 3 + 0] = ret[COL_BACKGROUND * 3 + 0];
+ ret[COL_TARGET * 3 + 1] = ret[COL_HIGHLIGHT * 3 + 1];
+ ret[COL_TARGET * 3 + 2] = ret[COL_BACKGROUND * 3 + 2];
+ game_mkhighlight_specific(fe, ret, COL_TARGET,
+ COL_TARGET_HIGHLIGHT, COL_TARGET_LOWLIGHT);
+
+ *ncolours = NCOLOURS;
+ return ret;
+}
+
+static game_drawstate *game_new_drawstate(drawing *dr, game_state *state)
+{+ int w = state->w, h = state->h, wh = w*h;
+ struct game_drawstate *ds = snew(struct game_drawstate);
+ int i;
+
+ ds->tilesize = 0;
+ ds->w = w;
+ ds->h = h;
+ ds->started = FALSE;
+ ds->grid = snewn(wh, unsigned long);
+ for (i = 0; i < wh; i++)
+ ds->grid[i] = ~(unsigned long)0;
+
+ return ds;
+}
+
+static void game_free_drawstate(drawing *dr, game_drawstate *ds)
+{+ sfree(ds->grid);
+ sfree(ds);
+}
+
+#define BG_NORMAL 0x00000001UL
+#define BG_TARGET 0x00000002UL
+#define BG_FORCEFIELD 0x00000004UL
+#define FLASH_LOW 0x00000008UL
+#define FLASH_HIGH 0x00000010UL
+#define FG_WALL 0x00000020UL
+#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
+
+/*
+ * Utility function.
+ */
+#define TYPE_MASK 0xF000
+#define COL_MASK 0x0FFF
+#define TYPE_RECT 0x0000
+#define TYPE_TLCIRC 0x4000
+#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)
+{+ int colour = coltype & COL_MASK, type = coltype & TYPE_MASK;
+
+ if (colour > NCOLOURS)
+ return;
+ if (type == TYPE_RECT) {+ draw_rect(dr, x, y, w, h, colour);
+ } else {+ int cx, cy, r;
+
+ clip(dr, x, y, w, h);
+
+ 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);
+
+ unclip(dr);
+ }
+}
+
+static void draw_tile(drawing *dr, game_drawstate *ds,
+ int x, int y, unsigned long val)
+{+ int tx = COORD(x), ty = COORD(y);
+ int cc, ch, cl;
+
+ /*
+ * Draw the tile background.
+ */
+ if (val & BG_TARGET)
+ cc = COL_TARGET;
+ else
+ cc = COL_BACKGROUND;
+ ch = cc+1;
+ cl = cc+2;
+ if (val & FLASH_LOW)
+ cc = cl;
+ else if (val & FLASH_HIGH)
+ cc = ch;
+
+ draw_rect(dr, tx, ty, TILESIZE, TILESIZE, cc);
+ if (val & BG_FORCEFIELD) {+ /*
+ * Cattle-grid effect to indicate that nothing but the
+ * main block can slide over this square.
+ */
+ int n = 3 * (TILESIZE / (3*HIGHLIGHT_WIDTH));
+ int i;
+
+ for (i = 1; i < n; i += 3) {+ draw_rect(dr, tx,ty+(TILESIZE*i/n), TILESIZE,HIGHLIGHT_WIDTH, cl);
+ draw_rect(dr, tx+(TILESIZE*i/n),ty, HIGHLIGHT_WIDTH,TILESIZE, cl);
+ }
+ }
+
+ /*
+ * Draw the tile foreground, i.e. some section of a block or
+ * wall.
+ */
+ if (val & FG_WALL) {+ cc = COL_BACKGROUND;
+ ch = cc+1;
+ cl = cc+2;
+ if (val & FLASH_LOW)
+ cc = cl;
+ 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);
+ } 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
+ cc = (val & FG_MAIN ? COL_MAIN : COL_BACKGROUND);
+ ch = cc+1;
+ cl = cc+2;
+
+ if (val & FLASH_LOW)
+ cc = cl;
+ else if (val & FLASH_HIGH)
+ 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_update(dr, tx, ty, TILESIZE, TILESIZE);
+}
+
+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;
+
+ 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, 10*ds->tilesize, 10*ds->tilesize, COL_BACKGROUND);
+ ds->started = TRUE;
+ }
+
+ /*
+ * Construct the board we'll be displaying (which may be
+ * different from the one in state if ui describes a drag in
+ * progress).
+ */
+ board = snewn(wh, unsigned char);
+ memcpy(board, state->board, wh);
+ if (ui->dragging) {+ int mpret = move_piece(w, h, state->board, board,
+ state->imm->forcefield,
+ ui->drag_anchor, ui->drag_currpos);
+ assert(mpret);
+ }
+
+ /*
+ * Build a dsf out of that board, so we can conveniently tell
+ * which edges are connected and which aren't.
+ */
+ dsf = snew_dsf(wh);
+ mainanchor = -1;
+ for (y = 0; y < h; y++)
+ for (x = 0; x < w; x++) {+ int i = y*w+x;
+
+ if (ISDIST(board[i]))
+ dsf_merge(dsf, i, i - board[i]);
+ if (board[i] == MAINANCHOR)
+ mainanchor = i;
+ if (board[i] == WALL) {+ if (x > 0 && board[i-1] == WALL)
+ dsf_merge(dsf, i, i-1);
+ if (y > 0 && board[i-w] == WALL)
+ dsf_merge(dsf, i, i-w);
+ }
+ }
+ assert(mainanchor >= 0);
+ mainpos = dsf_canonify(dsf, mainanchor);
+ dragpos = ui->drag_currpos > 0 ? dsf_canonify(dsf, ui->drag_currpos) : -1;
+
+ /*
+ * Now we can construct the data about what we want to draw.
+ */
+ for (y = 0; y < h; y++)
+ for (x = 0; x < w; x++) {+ int i = y*w+x;
+ int j;
+ unsigned long val;
+ int canon;
+
+ /*
+ * See if this square is part of the target area.
+ */
+ j = i + mainanchor - (state->ty * w + state->tx);
+ while (j >= 0 && j < wh && ISDIST(board[j]))
+ j -= board[j];
+ if (j == mainanchor)
+ val = BG_TARGET;
+ else
+ val = BG_NORMAL;
+
+ if (state->imm->forcefield[i])
+ val |= BG_FORCEFIELD;
+
+ if (flashtime > 0) {+ int flashtype = (int)(flashtime / FLASH_INTERVAL) & 1;
+ val |= (flashtype ? FLASH_LOW : FLASH_HIGH);
+ }
+
+ if (board[i] != EMPTY) {+ canon = dsf_canonify(dsf, i);
+
+ if (board[i] == WALL)
+ val |= FG_WALL;
+ else if (canon == mainpos)
+ val |= FG_MAIN;
+ else
+ val |= FG_NORMAL;
+ if (canon == dragpos)
+ val |= FG_DRAGGING;
+
+ /*
+ * 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;
+ }
+
+ if (val != ds->grid[i]) {+ draw_tile(dr, ds, x, y, val);
+ ds->grid[i] = val;
+ }
+ }
+
+ /*
+ * Update the status bar.
+ */
+ {+ char statusbuf[256];
+
+ /*
+ * FIXME: do something about auto-solve?
+ */
+ sprintf(statusbuf, "%sMoves: %d",
+ (state->completed >= 0 ? "COMPLETED! " : ""),
+ (state->completed >= 0 ? state->completed : state->movecount));
+ if (state->minmoves)
+ sprintf(statusbuf+strlen(statusbuf), " (min %d)",
+ state->minmoves);
+
+ status_bar(dr, statusbuf);
+ }
+
+ sfree(dsf);
+ sfree(board);
+}
+
+static float game_anim_length(game_state *oldstate, 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)
+{+ if (oldstate->completed < 0 && newstate->completed >= 0)
+ return FLASH_TIME;
+
+ return 0.0F;
+}
+
+static int game_timing_state(game_state *state, game_ui *ui)
+{+ return TRUE;
+}
+
+static void game_print_size(game_params *params, float *x, float *y)
+{+}
+
+static void game_print(drawing *dr, game_state *state, int tilesize)
+{+}
+
+#ifdef COMBINED
+#define thegame nullgame
+#endif
+
+const struct game thegame = {+ "Slide", NULL, NULL,
+ default_params,
+ game_fetch_preset,
+ decode_params,
+ encode_params,
+ free_params,
+ dup_params,
+ TRUE, game_configure, custom_params,
+ validate_params,
+ new_game_desc,
+ validate_desc,
+ new_game,
+ dup_game,
+ free_game,
+ FALSE, solve_game, /* FIXME */
+ TRUE, game_text_format,
+ new_ui,
+ free_ui,
+ encode_ui,
+ decode_ui,
+ game_changed_state,
+ interpret_move,
+ execute_move,
+ PREFERRED_TILESIZE, game_compute_size, game_set_size,
+ game_colours,
+ game_new_drawstate,
+ game_free_drawstate,
+ game_redraw,
+ game_anim_length,
+ game_flash_length,
+ FALSE, FALSE, game_print_size, game_print,
+ TRUE, /* wants_statusbar */
+ FALSE, game_timing_state,
+ 0, /* flags */
+};