In-game user interface to the solver.

[sgt/puzzles] / unfinished / slide.c

/*
 * slide.c: Implementation of the block-sliding puzzle `Klotski'.
 */

/*
 * TODO:
 * 
 *  - 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
 * 	 of the exit/target, and I think I probably ought to give
 * 	 up on compactness and just bite the bullet and have the
 * 	 target area right outside the main wall, but mostly I
 * 	 think it's OK.
 *     * the move limit tends to make the game _slower_ to
 * 	 generate, which is odd. Perhaps investigate why.
 * 
 *  - Improve the graphics.
 *     * 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.
 *     * The cattle grid effect is still disgusting. Think of
 * 	 something completely different.
 *     * I think TRCIRC and BLCIRC should actually be drawn, as a
 * 	 pair of differently coloured octants. Haul out the
 * 	 Bresenham code, I suspect.
 *     * 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>
#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;
    int maxmoves;
};

struct game_immutable_state {
    int refcount;
    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 tx, ty;			       /* target coords for MAINANCHOR */
    int minmoves;		       /* for display only */
    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)
{
    game_params *ret = snew(game_params);

    ret->w = 7;
    ret->h = 6;
    ret->maxmoves = 40;

    return ret;
}

static const struct game_params slide_presets[] = {
    {7, 6, 25},
    {7, 6, -1},
    {8, 6, -1},
};

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);
    if (ret->maxmoves >= 0)
	sprintf(str + strlen(str), ", max %d moves", ret->maxmoves);
    else
	sprintf(str + strlen(str), ", no move limit");

    *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);
	while (*string && isdigit((unsigned char)*string)) string++;
    }
    if (*string == 'm') {
        string++;
        params->maxmoves = atoi(string);
	while (*string && isdigit((unsigned char)*string)) string++;
    } else if (*string == 'u') {
	string++;
	params->maxmoves = -1;
    }
}

static char *encode_params(game_params *params, int full)
{
    char data[256];

    sprintf(data, "%dx%d", params->w, params->h);
    if (params->maxmoves >= 0)
	sprintf(data + strlen(data), "m%d", params->maxmoves);
    else
	sprintf(data + strlen(data), "u");

    return dupstr(data);
}

static config_item *game_configure(game_params *params)
{
    config_item *ret;
    char buf[80];

    ret = snewn(4, 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 = "Solution length limit";
    ret[2].type = C_STRING;
    sprintf(buf, "%d", params->maxmoves);
    ret[2].sval = dupstr(buf);
    ret[2].ival = 0;

    ret[3].name = NULL;
    ret[3].type = C_END;
    ret[3].sval = NULL;
    ret[3].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);
    ret->maxmoves = atoi(cfg[2].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.
 * 
 * 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 **moveout)
{
    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 (movelimit >= 0 && b->dist >= movelimit) {
	    /*
	     * The problem is not soluble in under `movelimit'
	     * moves, so we can quit right now.
	     */
	    b2 = NULL;
	    goto done;
	}
	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;
	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);

    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 movelimit)
{
    int wh = w*h;
    unsigned char *board, *board2, *forcefield;
    unsigned char *tried_merge;
    int *dsf;
    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;

    tried_merge = snewn(wh * wh, unsigned char);
    memset(tried_merge, 0, wh*wh);
    dsf = snew_dsf(wh);

    /*
     * 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, movelimit, NULL)) >= 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.
     */
    shuffle(list, nlist, sizeof(*list), rs);
    while (nlist > 0) {
	int x1, y1, p1, c1;
	int x2, y2, p2, c2;

	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;

	/*
	 * Immediately abandon the attempt if we've already tried
	 * to merge the same pair of blocks along a different
	 * edge.
	 */
	c1 = dsf_canonify(dsf, p1);
	c2 = dsf_canonify(dsf, p2);
	if (tried_merge[c1 * wh + c2])
	    continue;

	/*
	 * 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, movelimit, NULL);
	if (j < 0) {
	    /*
	     * Didn't work. Revert the merge.
	     */
	    memcpy(board, board2, wh);
	    tried_merge[c1 * wh + c2] = tried_merge[c2 * wh + c1] = TRUE;
	} else {
	    int c;

	    moves = j;

	    dsf_merge(dsf, c1, c2);
	    c = dsf_canonify(dsf, c1);
	    for (i = 0; i < wh; i++)
		tried_merge[c*wh+i] = (tried_merge[c1*wh+i] |
				       tried_merge[c2*wh+i]);
	    for (i = 0; i < wh; i++)
		tried_merge[i*wh+c] = (tried_merge[i*wh+c1] |
				       tried_merge[i*wh+c2]);
	}
    }

    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, params->maxmoves);
#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);

    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, 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;

	    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;

    state->cheated = FALSE;
    state->soln = NULL;
    state->soln_index = -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->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;
}

static void free_game(game_state *state)
{
    if (--state->imm->refcount <= 0) {
	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;

    /*
     * Run the solver and attempt to find the shortest solution
     * from the current position.
     */
    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 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;
    } 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;
}

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, movesize;
    game_state *ret = dup_game(state);

    while (*move) {
        c = *move;
	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,
			    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 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;
            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_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_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_wallpart(drawing *dr, game_drawstate *ds,
			  int tx, int ty, unsigned long val,
			  int cl, int cc, int ch)
{
    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, cc);
    if (!((PIECE_TBORDER | PIECE_RBORDER) &~ val))
	draw_rect(dr, tx+TILESIZE-HIGHLIGHT_WIDTH, ty,
		  HIGHLIGHT_WIDTH, HIGHLIGHT_WIDTH, cc);
    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);
    maybe_rect(dr, RECT(1,0),
	       (val & PIECE_TLCORNER) ? ch : (val & PIECE_TBORDER) ? -1 :
	       (val & PIECE_LBORDER) ? ch : cc);
    maybe_rect(dr, RECT(2,0),
	       (val & PIECE_TBORDER) ? -1 : cc);
    maybe_rect(dr, RECT(3,0),
	       (val & PIECE_TRCORNER) ? cl : (val & PIECE_TBORDER) ? -1 :
	       (val & PIECE_RBORDER) ? cl : cc);
    maybe_rect(dr, RECT(4,0),
	       (val & (PIECE_TRCORNER | PIECE_TBORDER |
		       PIECE_RBORDER)) ? -1 : cc);
    maybe_rect(dr, RECT(0,1),
	       (val & PIECE_TLCORNER) ? ch : (val & PIECE_LBORDER) ? -1 :
	       (val & PIECE_TBORDER) ? ch : cc);
    maybe_rect(dr, RECT(1,1),
	       (val & PIECE_TLCORNER) ? cc : -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);
    maybe_rect(dr, RECT(2,1),
	       (val & PIECE_TBORDER) ? ch : cc);
    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) ? cc | TYPE_BLCIRC :
	       cc);
    maybe_rect(dr, RECT(4,1),
	       (val & PIECE_TRCORNER) ? ch : (val & PIECE_RBORDER) ? -1 :
	       (val & PIECE_TBORDER) ? ch : cc);
    maybe_rect(dr, RECT(0,2),
	       (val & PIECE_LBORDER) ? -1 : cc);
    maybe_rect(dr, RECT(1,2),
	       (val & PIECE_LBORDER) ? ch : cc);
    maybe_rect(dr, RECT(2,2),
	       cc);
    maybe_rect(dr, RECT(3,2),
	       (val & PIECE_RBORDER) ? cl : cc);
    maybe_rect(dr, RECT(4,2),
	       (val & PIECE_RBORDER) ? -1 : cc);
    maybe_rect(dr, RECT(0,3),
	       (val & PIECE_BLCORNER) ? cl : (val & PIECE_LBORDER) ? -1 :
	       (val & PIECE_BBORDER) ? cl : cc);
    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) ? cc | TYPE_TRCIRC :
	       cc);
    maybe_rect(dr, RECT(2,3),
	       (val & PIECE_BBORDER) ? cl : cc);
    maybe_rect(dr, RECT(3,3),
	       (val & PIECE_BRCORNER) ? cc : -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);
    maybe_rect(dr, RECT(4,3),
	       (val & PIECE_BRCORNER) ? cl : (val & PIECE_RBORDER) ? -1 :
	       (val & PIECE_BBORDER) ? cl : cc);
    maybe_rect(dr, RECT(0,4),
	       (val & (PIECE_BLCORNER | PIECE_BBORDER | PIECE_LBORDER)) ? -1 : cc);
    maybe_rect(dr, RECT(1,4),
	       (val & PIECE_BLCORNER) ? ch : (val & PIECE_BBORDER) ? -1 :
	       (val & PIECE_LBORDER) ? ch : cc);
    maybe_rect(dr, RECT(2,4),
	       (val & PIECE_BBORDER) ? -1 : cc);
    maybe_rect(dr, RECT(3,4),
	       (val & PIECE_BRCORNER) ? cl : (val & PIECE_BBORDER) ? -1 :
	       (val & PIECE_RBORDER) ? cl : cc);
    maybe_rect(dr, RECT(4,4),
	       (val & (PIECE_BRCORNER | PIECE_BBORDER |
		       PIECE_RBORDER)) ? -1 : cc);

#undef RECT
}

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 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.
     */
    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_wallpart(dr, ds, tx, ty, (val >> FG_MAINPIECESH) & PIECE_MASK,
		      cl, cc, ch);
    } else if (val & (FG_MAIN | FG_NORMAL)) {
	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 | FG_SOLVEPIECE))
	    cc = ch;

	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, solvepos, solvesrc, solvedst;

    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);
    }

    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.
     */
    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;
    solvepos = solvesrc >= 0 ? dsf_canonify(dsf, solvesrc) : -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;
		if (canon == solvepos)
		    val |= FG_SOLVEPIECE;

		/*
		 * Now look around to see if other squares
		 * belonging to the same block are adjacent to us.
		 */
		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]) {
		draw_tile(dr, ds, x, y, val);
		ds->grid[i] = val;
	    }
	}

    /*
     * Update the status bar.
     */
    {
	char statusbuf[256];

	sprintf(statusbuf, "%sMoves: %d",
		(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)",
		    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,
    TRUE, solve_game,
    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 */
};

#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