unfinished/slide.c

   1 /*
   2  * slide.c: Implementation of the block-sliding puzzle `Klotski'.
   3  */
   4
   5 /*
   6  * TODO:
   7  *
   8  *  - Improve the generator.
   9  *     * actually, we seem to be mostly sensible already now. I
  10  *       want more choice over the type of main block and location
  11  *       of the exit/target, and I think I probably ought to give
  12  *       up on compactness and just bite the bullet and have the
  13  *       target area right outside the main wall, but mostly I
  14  *       think it's OK.
  15  *     * the move limit tends to make the game _slower_ to
  16  *       generate, which is odd. Perhaps investigate why.
  17  *
  18  *  - Improve the graphics.
  19  *     * All the colours are a bit wishy-washy. _Some_ dark
  20  *       colours would surely not be excessive? Probably darken
  21  *       the tiles, the walls and the main block, and leave the
  22  *       target marker pale.
  23  *     * The cattle grid effect is still disgusting. Think of
  24  *       something completely different.
  25  *     * The highlight for next-piece-to-move in the solver is
  26  *       excessive, and the shadow blends in too well with the
  27  *       piece lowlights. Adjust both.
  28  */
  29
  30 #include <stdio.h>
  31 #include <stdlib.h>
  32 #include <string.h>
  33 #include <assert.h>
  34 #include <ctype.h>
  35 #include <math.h>
  36
  37 #include "puzzles.h"
  38 #include "tree234.h"
  39
  40 /*
  41  * The implementation of this game revolves around the insight
  42  * which makes an exhaustive-search solver feasible: although
  43  * there are many blocks which can be rearranged in many ways, any
  44  * two blocks of the same shape are _indistinguishable_ and hence
  45  * the number of _distinct_ board layouts is generally much
  46  * smaller. So we adopt a representation for board layouts which
  47  * is inherently canonical, i.e. there are no two distinct
  48  * representations which encode indistinguishable layouts.
  49  *
  50  * The way we do this is to encode each square of the board, in
  51  * the normal left-to-right top-to-bottom order, as being one of
  52  * the following things:
  53  *  - the first square (in the given order) of a block (`anchor')
  54  *  - special case of the above: the anchor for the _main_ block
  55  *    (i.e. the one which the aim of the game is to get to the
  56  *    target position)
  57  *  - a subsequent square of a block whose previous square was N
  58  *    squares ago
  59  *  - an impassable wall
  60  *
  61  * (We also separately store data about which board positions are
  62  * forcefields only passable by the main block. We can't encode
  63  * that in the main board data, because then the main block would
  64  * destroy forcefields as it went over them.)
  65  *
  66  * Hence, for example, a 2x2 square block would be encoded as
  67  * ANCHOR, followed by DIST(1), and w-2 squares later on there
  68  * would be DIST(w-1) followed by DIST(1). So if you start at the
  69  * last of those squares, the DIST numbers give you a linked list
  70  * pointing back through all the other squares in the same block.
  71  *
  72  * So the solver simply does a bfs over all reachable positions,
  73  * encoding them in this format and storing them in a tree234 to
  74  * ensure it doesn't ever revisit an already-analysed position.
  75  */
  76
  77 enum {
  78     /*
  79      * The colours are arranged here so that every base colour is
  80      * directly followed by its highlight colour and then its
  81      * lowlight colour. Do not break this, or draw_tile() will get
  82      * confused.
  83      */
  84     COL_BACKGROUND,
  85     COL_HIGHLIGHT,
  86     COL_LOWLIGHT,
  87     COL_DRAGGING,
  88     COL_DRAGGING_HIGHLIGHT,
  89     COL_DRAGGING_LOWLIGHT,
  90     COL_MAIN,
  91     COL_MAIN_HIGHLIGHT,
  92     COL_MAIN_LOWLIGHT,
  93     COL_MAIN_DRAGGING,
  94     COL_MAIN_DRAGGING_HIGHLIGHT,
  95     COL_MAIN_DRAGGING_LOWLIGHT,
  96     COL_TARGET,
  97     COL_TARGET_HIGHLIGHT,
  98     COL_TARGET_LOWLIGHT,
  99     NCOLOURS
 100 };
 101
 102 /*
 103  * Board layout is a simple array of bytes. Each byte holds:
 104  */
 105 #define ANCHOR      255                /* top-left-most square of some piece */
 106 #define MAINANCHOR  254                /* anchor of _main_ piece */
 107 #define EMPTY       253                /* empty square */
 108 #define WALL        252                /* immovable wall */
 109 #define MAXDIST     251
 110 /* all other values indicate distance back to previous square of same block */
 111 #define ISDIST(x) ( (unsigned char)((x)-1) <= MAXDIST-1 )
 112 #define DIST(x) (x)
 113 #define ISANCHOR(x) ( (x)==ANCHOR || (x)==MAINANCHOR )
 114 #define ISBLOCK(x) ( ISANCHOR(x) || ISDIST(x) )
 115
 116 /*
 117  * MAXDIST is the largest DIST value we can encode. This must
 118  * therefore also be the maximum puzzle width in theory (although
 119  * solver running time will dictate a much smaller limit in
 120  * practice).
 121  */
 122 #define MAXWID MAXDIST
 123
 124 struct game_params {
 125     int w, h;
 126     int maxmoves;
 127 };
 128
 129 struct game_immutable_state {
 130     int refcount;
 131     unsigned char *forcefield;
 132 };
 133
 134 struct game_solution {
 135     int nmoves;
 136     int *moves;                        /* just like from solve_board() */
 137     int refcount;
 138 };
 139
 140 struct game_state {
 141     int w, h;
 142     unsigned char *board;
 143     int tx, ty;                        /* target coords for MAINANCHOR */
 144     int minmoves;                      /* for display only */
 145     int lastmoved, lastmoved_pos;      /* for move counting */
 146     int movecount;
 147     int completed;
 148     int cheated;
 149     struct game_immutable_state *imm;
 150     struct game_solution *soln;
 151     int soln_index;
 152 };
 153
 154 static game_params *default_params(void)
 155 {
 156     game_params *ret = snew(game_params);
 157
 158     ret->w = 7;
 159     ret->h = 6;
 160     ret->maxmoves = 40;
 161
 162     return ret;
 163 }
 164
 165 static const struct game_params slide_presets[] = {
 166     {7, 6, 25},
 167     {7, 6, -1},
 168     {8, 6, -1},
 169 };
 170
 171 static int game_fetch_preset(int i, char **name, game_params **params)
 172 {
 173     game_params *ret;
 174     char str[80];
 175
 176     if (i < 0 || i >= lenof(slide_presets))
 177         return FALSE;
 178
 179     ret = snew(game_params);
 180     *ret = slide_presets[i];
 181
 182     sprintf(str, "%dx%d", ret->w, ret->h);
 183     if (ret->maxmoves >= 0)
 184         sprintf(str + strlen(str), ", max %d moves", ret->maxmoves);
 185     else
 186         sprintf(str + strlen(str), ", no move limit");
 187
 188     *name = dupstr(str);
 189     *params = ret;
 190     return TRUE;
 191 }
 192
 193 static void free_params(game_params *params)
 194 {
 195     sfree(params);
 196 }
 197
 198 static game_params *dup_params(game_params *params)
 199 {
 200     game_params *ret = snew(game_params);
 201     *ret = *params;                    /* structure copy */
 202     return ret;
 203 }
 204
 205 static void decode_params(game_params *params, char const *string)
 206 {
 207     params->w = params->h = atoi(string);
 208     while (*string && isdigit((unsigned char)*string)) string++;
 209     if (*string == 'x') {
 210         string++;
 211         params->h = atoi(string);
 212         while (*string && isdigit((unsigned char)*string)) string++;
 213     }
 214     if (*string == 'm') {
 215         string++;
 216         params->maxmoves = atoi(string);
 217         while (*string && isdigit((unsigned char)*string)) string++;
 218     } else if (*string == 'u') {
 219         string++;
 220         params->maxmoves = -1;
 221     }
 222 }
 223
 224 static char *encode_params(game_params *params, int full)
 225 {
 226     char data[256];
 227
 228     sprintf(data, "%dx%d", params->w, params->h);
 229     if (params->maxmoves >= 0)
 230         sprintf(data + strlen(data), "m%d", params->maxmoves);
 231     else
 232         sprintf(data + strlen(data), "u");
 233
 234     return dupstr(data);
 235 }
 236
 237 static config_item *game_configure(game_params *params)
 238 {
 239     config_item *ret;
 240     char buf[80];
 241
 242     ret = snewn(4, config_item);
 243
 244     ret[0].name = "Width";
 245     ret[0].type = C_STRING;
 246     sprintf(buf, "%d", params->w);
 247     ret[0].sval = dupstr(buf);
 248     ret[0].ival = 0;
 249
 250     ret[1].name = "Height";
 251     ret[1].type = C_STRING;
 252     sprintf(buf, "%d", params->h);
 253     ret[1].sval = dupstr(buf);
 254     ret[1].ival = 0;
 255
 256     ret[2].name = "Solution length limit";
 257     ret[2].type = C_STRING;
 258     sprintf(buf, "%d", params->maxmoves);
 259     ret[2].sval = dupstr(buf);
 260     ret[2].ival = 0;
 261
 262     ret[3].name = NULL;
 263     ret[3].type = C_END;
 264     ret[3].sval = NULL;
 265     ret[3].ival = 0;
 266
 267     return ret;
 268 }
 269
 270 static game_params *custom_params(config_item *cfg)
 271 {
 272     game_params *ret = snew(game_params);
 273
 274     ret->w = atoi(cfg[0].sval);
 275     ret->h = atoi(cfg[1].sval);
 276     ret->maxmoves = atoi(cfg[2].sval);
 277
 278     return ret;
 279 }
 280
 281 static char *validate_params(game_params *params, int full)
 282 {
 283     if (params->w > MAXWID)
 284         return "Width must be at most " STR(MAXWID);
 285
 286     if (params->w < 5)
 287         return "Width must be at least 5";
 288     if (params->h < 4)
 289         return "Height must be at least 4";
 290
 291     return NULL;
 292 }
 293
 294 static char *board_text_format(int w, int h, unsigned char *data,
 295                                unsigned char *forcefield)
 296 {
 297     int wh = w*h;
 298     int *dsf = snew_dsf(wh);
 299     int i, x, y;
 300     int retpos, retlen = (w*2+2)*(h*2+1)+1;
 301     char *ret = snewn(retlen, char);
 302
 303     for (i = 0; i < wh; i++)
 304         if (ISDIST(data[i]))
 305             dsf_merge(dsf, i - data[i], i);
 306     retpos = 0;
 307     for (y = 0; y < 2*h+1; y++) {
 308         for (x = 0; x < 2*w+1; x++) {
 309             int v;
 310             int i = (y/2)*w+(x/2);
 311
 312 #define dtype(i) (ISBLOCK(data[i]) ? \
 313                   dsf_canonify(dsf, i) : data[i])
 314 #define dchar(t) ((t)==EMPTY ? ' ' : (t)==WALL ? '#' : \
 315                   data[t] == MAINANCHOR ? '*' : '%')
 316
 317             if (y % 2 && x % 2) {
 318                 int j = dtype(i);
 319                 v = dchar(j);
 320             } else if (y % 2 && !(x % 2)) {
 321                 int j1 = (x > 0 ? dtype(i-1) : -1);
 322                 int j2 = (x < 2*w ? dtype(i) : -1);
 323                 if (j1 != j2)
 324                     v = '|';
 325                 else
 326                     v = dchar(j1);
 327             } else if (!(y % 2) && (x % 2)) {
 328                 int j1 = (y > 0 ? dtype(i-w) : -1);
 329                 int j2 = (y < 2*h ? dtype(i) : -1);
 330                 if (j1 != j2)
 331                     v = '-';
 332                 else
 333                     v = dchar(j1);
 334             } else {
 335                 int j1 = (x > 0 && y > 0 ? dtype(i-w-1) : -1);
 336                 int j2 = (x > 0 && y < 2*h ? dtype(i-1) : -1);
 337                 int j3 = (x < 2*w && y > 0 ? dtype(i-w) : -1);
 338                 int j4 = (x < 2*w && y < 2*h ? dtype(i) : -1);
 339                 if (j1 == j2 && j2 == j3 && j3 == j4)
 340                     v = dchar(j1);
 341                 else if (j1 == j2 && j3 == j4)
 342                     v = '|';
 343                 else if (j1 == j3 && j2 == j4)
 344                     v = '-';
 345                 else
 346                     v = '+';
 347             }
 348
 349             assert(retpos < retlen);
 350             ret[retpos++] = v;
 351         }
 352         assert(retpos < retlen);
 353         ret[retpos++] = '\n';
 354     }
 355     assert(retpos < retlen);
 356     ret[retpos++] = '\0';
 357     assert(retpos == retlen);
 358
 359     return ret;
 360 }
 361
 362 /* ----------------------------------------------------------------------
 363  * Solver.
 364  */
 365
 366 /*
 367  * During solver execution, the set of visited board positions is
 368  * stored as a tree234 of the following structures. `w', `h' and
 369  * `data' are obvious in meaning; `dist' represents the minimum
 370  * distance to reach this position from the starting point.
 371  *
 372  * `prev' links each board to the board position from which it was
 373  * most efficiently derived.
 374  */
 375 struct board {
 376     int w, h;
 377     int dist;
 378     struct board *prev;
 379     unsigned char *data;
 380 };
 381
 382 static int boardcmp(void *av, void *bv)
 383 {
 384     struct board *a = (struct board *)av;
 385     struct board *b = (struct board *)bv;
 386     return memcmp(a->data, b->data, a->w * a->h);
 387 }
 388
 389 static struct board *newboard(int w, int h, unsigned char *data)
 390 {
 391     struct board *b = malloc(sizeof(struct board) + w*h);
 392     b->data = (unsigned char *)b + sizeof(struct board);
 393     memcpy(b->data, data, w*h);
 394     b->w = w;
 395     b->h = h;
 396     b->dist = -1;
 397     b->prev = NULL;
 398     return b;
 399 }
 400
 401 /*
 402  * The actual solver. Given a board, attempt to find the minimum
 403  * length of move sequence which moves MAINANCHOR to (tx,ty), or
 404  * -1 if no solution exists. Returns that minimum length.
 405  *
 406  * Also, if `moveout' is provided, writes out the moves in the
 407  * form of a sequence of pairs of integers indicating the source
 408  * and destination points of the anchor of the moved piece in each
 409  * move. Exactly twice as many integers are written as the number
 410  * returned from solve_board(), and `moveout' receives an int *
 411  * which is a pointer to a dynamically allocated array.
 412  */
 413 static int solve_board(int w, int h, unsigned char *board,
 414                        unsigned char *forcefield, int tx, int ty,
 415                        int movelimit, int **moveout)
 416 {
 417     int wh = w*h;
 418     struct board *b, *b2, *b3;
 419     int *next, *anchors, *which;
 420     int *movereached, *movequeue, mqhead, mqtail;
 421     tree234 *sorted, *queue;
 422     int i, j, dir;
 423     int qlen, lastdist;
 424     int ret;
 425
 426 #ifdef SOLVER_DIAGNOSTICS
 427     {
 428         char *t = board_text_format(w, h, board);
 429         for (i = 0; i < h; i++) {
 430             for (j = 0; j < w; j++) {
 431                 int c = board[i*w+j];
 432                 if (ISDIST(c))
 433                     printf("D%-3d", c);
 434                 else if (c == MAINANCHOR)
 435                     printf("M   ");
 436                 else if (c == ANCHOR)
 437                     printf("A   ");
 438                 else if (c == WALL)
 439                     printf("W   ");
 440                 else if (c == EMPTY)
 441                     printf("E   ");
 442             }
 443             printf("\n");
 444         }
 445
 446         printf("Starting solver for:\n%s\n", t);
 447         sfree(t);
 448     }
 449 #endif
 450
 451     sorted = newtree234(boardcmp);
 452     queue = newtree234(NULL);
 453
 454     b = newboard(w, h, board);
 455     b->dist = 0;
 456     add234(sorted, b);
 457     addpos234(queue, b, 0);
 458     qlen = 1;
 459
 460     next = snewn(wh, int);
 461     anchors = snewn(wh, int);
 462     which = snewn(wh, int);
 463     movereached = snewn(wh, int);
 464     movequeue = snewn(wh, int);
 465     lastdist = -1;
 466
 467     while ((b = delpos234(queue, 0)) != NULL) {
 468         qlen--;
 469         if (movelimit >= 0 && b->dist >= movelimit) {
 470             /*
 471              * The problem is not soluble in under `movelimit'
 472              * moves, so we can quit right now.
 473              */
 474             b2 = NULL;
 475             goto done;
 476         }
 477         if (b->dist != lastdist) {
 478 #ifdef SOLVER_DIAGNOSTICS
 479             printf("dist %d (%d)\n", b->dist, count234(sorted));
 480 #endif
 481             lastdist = b->dist;
 482         }
 483         /*
 484          * Find all the anchors and form a linked list of the
 485          * squares within each block.
 486          */
 487         for (i = 0; i < wh; i++) {
 488             next[i] = -1;
 489             anchors[i] = FALSE;
 490             which[i] = -1;
 491             if (ISANCHOR(b->data[i])) {
 492                 anchors[i] = TRUE;
 493                 which[i] = i;
 494             } else if (ISDIST(b->data[i])) {
 495                 j = i - b->data[i];
 496                 next[j] = i;
 497                 which[i] = which[j];
 498             }
 499         }
 500
 501         /*
 502          * For each anchor, do an array-based BFS to find all the
 503          * places we can slide it to.
 504          */
 505         for (i = 0; i < wh; i++) {
 506             if (!anchors[i])
 507                 continue;
 508
 509             mqhead = mqtail = 0;
 510             for (j = 0; j < wh; j++)
 511                 movereached[j] = FALSE;
 512             movequeue[mqtail++] = i;
 513             while (mqhead < mqtail) {
 514                 int pos = movequeue[mqhead++];
 515
 516                 /*
 517                  * Try to move in each direction from here.
 518                  */
 519                 for (dir = 0; dir < 4; dir++) {
 520                     int dx = (dir == 0 ? -1 : dir == 1 ? +1 : 0);
 521                     int dy = (dir == 2 ? -1 : dir == 3 ? +1 : 0);
 522                     int offset = dy*w + dx;
 523                     int newpos = pos + offset;
 524                     int d = newpos - i;
 525
 526                     /*
 527                      * For each square involved in this block,
 528                      * check to see if the square d spaces away
 529                      * from it is either empty or part of the same
 530                      * block.
 531                      */
 532                     for (j = i; j >= 0; j = next[j]) {
 533                         int jy = (pos+j-i) / w + dy, jx = (pos+j-i) % w + dx;
 534                         if (jy >= 0 && jy < h && jx >= 0 && jx < w &&
 535                             ((b->data[j+d] == EMPTY || which[j+d] == i) &&
 536                              (b->data[i] == MAINANCHOR || !forcefield[j+d])))
 537                             /* ok */;
 538                         else
 539                             break;
 540                     }
 541                     if (j >= 0)
 542                         continue;              /* this direction wasn't feasible */
 543
 544                     /*
 545                      * If we've already tried moving this piece
 546                      * here, leave it.
 547                      */
 548                     if (movereached[newpos])
 549                         continue;
 550                     movereached[newpos] = TRUE;
 551                     movequeue[mqtail++] = newpos;
 552
 553                     /*
 554                      * We have a viable move. Make it.
 555                      */
 556                     b2 = newboard(w, h, b->data);
 557                     for (j = i; j >= 0; j = next[j])
 558                         b2->data[j] = EMPTY;
 559                     for (j = i; j >= 0; j = next[j])
 560                         b2->data[j+d] = b->data[j];
 561
 562                     b3 = add234(sorted, b2);
 563                     if (b3 != b2) {
 564                         sfree(b2);             /* we already got one */
 565                     } else {
 566                         b2->dist = b->dist + 1;
 567                         b2->prev = b;
 568                         addpos234(queue, b2, qlen++);
 569                         if (b2->data[ty*w+tx] == MAINANCHOR)
 570                             goto done;     /* search completed! */
 571                     }
 572                 }
 573             }
 574         }
 575     }
 576     b2 = NULL;
 577
 578     done:
 579
 580     if (b2) {
 581         ret = b2->dist;
 582         if (moveout) {
 583             /*
 584              * Now b2 represents the solved position. Backtrack to
 585              * output the solution.
 586              */
 587             *moveout = snewn(ret * 2, int);
 588             j = ret * 2;
 589
 590             while (b2->prev) {
 591                 int from = -1, to = -1;
 592
 593                 b = b2->prev;
 594
 595                 /*
 596                  * Scan b and b2 to find out which piece has
 597                  * moved.
 598                  */
 599                 for (i = 0; i < wh; i++) {
 600                     if (ISANCHOR(b->data[i]) && !ISANCHOR(b2->data[i])) {
 601                         assert(from == -1);
 602                         from = i;
 603                     } else if (!ISANCHOR(b->data[i]) && ISANCHOR(b2->data[i])){
 604                         assert(to == -1);
 605                         to = i;
 606                     }
 607                 }
 608
 609                 assert(from >= 0 && to >= 0);
 610                 assert(j >= 2);
 611                 (*moveout)[--j] = to;
 612                 (*moveout)[--j] = from;
 613
 614                 b2 = b;
 615             }
 616             assert(j == 0);
 617         }
 618     } else {
 619         ret = -1;                      /* no solution */
 620         if (moveout)
 621             *moveout = NULL;
 622     }
 623
 624     freetree234(queue);
 625
 626     while ((b = delpos234(sorted, 0)) != NULL)
 627         sfree(b);
 628     freetree234(sorted);
 629
 630     sfree(next);
 631     sfree(anchors);
 632     sfree(movereached);
 633     sfree(movequeue);
 634     sfree(which);
 635
 636     return ret;
 637 }
 638
 639 /* ----------------------------------------------------------------------
 640  * Random board generation.
 641  */
 642
 643 static void generate_board(int w, int h, int *rtx, int *rty, int *minmoves,
 644                            random_state *rs, unsigned char **rboard,
 645                            unsigned char **rforcefield, int movelimit)
 646 {
 647     int wh = w*h;
 648     unsigned char *board, *board2, *forcefield;
 649     unsigned char *tried_merge;
 650     int *dsf;
 651     int *list, nlist, pos;
 652     int tx, ty;
 653     int i, j;
 654     int moves = 0;                     /* placate optimiser */
 655
 656     /*
 657      * Set up a board and fill it with singletons, except for a
 658      * border of walls.
 659      */
 660     board = snewn(wh, unsigned char);
 661     forcefield = snewn(wh, unsigned char);
 662     board2 = snewn(wh, unsigned char);
 663     memset(board, ANCHOR, wh);
 664     memset(forcefield, FALSE, wh);
 665     for (i = 0; i < w; i++)
 666         board[i] = board[i+w*(h-1)] = WALL;
 667     for (i = 0; i < h; i++)
 668         board[i*w] = board[i*w+(w-1)] = WALL;
 669
 670     tried_merge = snewn(wh * wh, unsigned char);
 671     memset(tried_merge, 0, wh*wh);
 672     dsf = snew_dsf(wh);
 673
 674     /*
 675      * Invent a main piece at one extreme. (FIXME: vary the
 676      * extreme, and the piece.)
 677      */
 678     board[w+1] = MAINANCHOR;
 679     board[w+2] = DIST(1);
 680     board[w*2+1] = DIST(w-1);
 681     board[w*2+2] = DIST(1);
 682
 683     /*
 684      * Invent a target position. (FIXME: vary this too.)
 685      */
 686     tx = w-2;
 687     ty = h-3;
 688     forcefield[ty*w+tx+1] = forcefield[(ty+1)*w+tx+1] = TRUE;
 689     board[ty*w+tx+1] = board[(ty+1)*w+tx+1] = EMPTY;
 690
 691     /*
 692      * Gradually remove singletons until the game becomes soluble.
 693      */
 694     for (j = w; j-- > 0 ;)
 695         for (i = h; i-- > 0 ;)
 696             if (board[i*w+j] == ANCHOR) {
 697                 /*
 698                  * See if the board is already soluble.
 699                  */
 700                 if ((moves = solve_board(w, h, board, forcefield,
 701                                          tx, ty, movelimit, NULL)) >= 0)
 702                     goto soluble;
 703
 704                 /*
 705                  * Otherwise, remove this piece.
 706                  */
 707                 board[i*w+j] = EMPTY;
 708             }
 709     assert(!"We shouldn't get here");
 710     soluble:
 711
 712     /*
 713      * Make a list of all the inter-block edges on the board.
 714      */
 715     list = snewn(wh*2, int);
 716     nlist = 0;
 717     for (i = 0; i+1 < w; i++)
 718         for (j = 0; j < h; j++)
 719             list[nlist++] = (j*w+i) * 2 + 0;   /* edge to the right of j*w+i */
 720     for (j = 0; j+1 < h; j++)
 721         for (i = 0; i < w; i++)
 722             list[nlist++] = (j*w+i) * 2 + 1;   /* edge below j*w+i */
 723
 724     /*
 725      * Now go through that list in random order, trying to merge
 726      * the blocks on each side of each edge.
 727      */
 728     shuffle(list, nlist, sizeof(*list), rs);
 729     while (nlist > 0) {
 730         int x1, y1, p1, c1;
 731         int x2, y2, p2, c2;
 732
 733         pos = list[--nlist];
 734         y1 = y2 = pos / (w*2);
 735         x1 = x2 = (pos / 2) % w;
 736         if (pos % 2)
 737             y2++;
 738         else
 739             x2++;
 740         p1 = y1*w+x1;
 741         p2 = y2*w+x2;
 742
 743         /*
 744          * Immediately abandon the attempt if we've already tried
 745          * to merge the same pair of blocks along a different
 746          * edge.
 747          */
 748         c1 = dsf_canonify(dsf, p1);
 749         c2 = dsf_canonify(dsf, p2);
 750         if (tried_merge[c1 * wh + c2])
 751             continue;
 752
 753         /*
 754          * In order to be mergeable, these two squares must each
 755          * either be, or belong to, a non-main anchor, and their
 756          * anchors must also be distinct.
 757          */
 758         if (!ISBLOCK(board[p1]) || !ISBLOCK(board[p2]))
 759             continue;
 760         while (ISDIST(board[p1]))
 761             p1 -= board[p1];
 762         while (ISDIST(board[p2]))
 763             p2 -= board[p2];
 764         if (board[p1] == MAINANCHOR || board[p2] == MAINANCHOR || p1 == p2)
 765             continue;
 766
 767         /*
 768          * We can merge these blocks. Try it, and see if the
 769          * puzzle remains soluble.
 770          */
 771         memcpy(board2, board, wh);
 772         j = -1;
 773         while (p1 < wh || p2 < wh) {
 774             /*
 775              * p1 and p2 are the squares at the head of each block
 776              * list. Pick the smaller one and put it on the output
 777              * block list.
 778              */
 779             i = min(p1, p2);
 780             if (j < 0) {
 781                 board[i] = ANCHOR;
 782             } else {
 783                 assert(i - j <= MAXDIST);
 784                 board[i] = DIST(i - j);
 785             }
 786             j = i;
 787
 788             /*
 789              * Now advance whichever list that came from.
 790              */
 791             if (i == p1) {
 792                 do {
 793                     p1++;
 794                 } while (p1 < wh && board[p1] != DIST(p1-i));
 795             } else {
 796                 do {
 797                     p2++;
 798                 } while (p2 < wh && board[p2] != DIST(p2-i));
 799             }
 800         }
 801         j = solve_board(w, h, board, forcefield, tx, ty, movelimit, NULL);
 802         if (j < 0) {
 803             /*
 804              * Didn't work. Revert the merge.
 805              */
 806             memcpy(board, board2, wh);
 807             tried_merge[c1 * wh + c2] = tried_merge[c2 * wh + c1] = TRUE;
 808         } else {
 809             int c;
 810
 811             moves = j;
 812
 813             dsf_merge(dsf, c1, c2);
 814             c = dsf_canonify(dsf, c1);
 815             for (i = 0; i < wh; i++)
 816                 tried_merge[c*wh+i] = (tried_merge[c1*wh+i] |
 817                                        tried_merge[c2*wh+i]);
 818             for (i = 0; i < wh; i++)
 819                 tried_merge[i*wh+c] = (tried_merge[i*wh+c1] |
 820                                        tried_merge[i*wh+c2]);
 821         }
 822     }
 823
 824     sfree(dsf);
 825     sfree(list);
 826     sfree(tried_merge);
 827     sfree(board2);
 828
 829     *rtx = tx;
 830     *rty = ty;
 831     *rboard = board;
 832     *rforcefield = forcefield;
 833     *minmoves = moves;
 834 }
 835
 836 /* ----------------------------------------------------------------------
 837  * End of solver/generator code.
 838  */
 839
 840 static char *new_game_desc(game_params *params, random_state *rs,
 841                            char **aux, int interactive)
 842 {
 843     int w = params->w, h = params->h, wh = w*h;
 844     int tx, ty, minmoves;
 845     unsigned char *board, *forcefield;
 846     char *ret, *p;
 847     int i;
 848
 849     generate_board(params->w, params->h, &tx, &ty, &minmoves, rs,
 850                    &board, &forcefield, params->maxmoves);
 851 #ifdef GENERATOR_DIAGNOSTICS
 852     {
 853         char *t = board_text_format(params->w, params->h, board);
 854         printf("%s\n", t);
 855         sfree(t);
 856     }
 857 #endif
 858
 859     /*
 860      * Encode as a game ID.
 861      */
 862     ret = snewn(wh * 6 + 40, char);
 863     p = ret;
 864     i = 0;
 865     while (i < wh) {
 866         if (ISDIST(board[i])) {
 867             p += sprintf(p, "d%d", board[i]);
 868             i++;
 869         } else {
 870             int count = 1;
 871             int b = board[i], f = forcefield[i];
 872             int c = (b == ANCHOR ? 'a' :
 873                      b == MAINANCHOR ? 'm' :
 874                      b == EMPTY ? 'e' :
 875                      /* b == WALL ? */ 'w');
 876             if (f) *p++ = 'f';
 877             *p++ = c;
 878             i++;
 879             while (i < wh && board[i] == b && forcefield[i] == f)
 880                 i++, count++;
 881             if (count > 1)
 882                 p += sprintf(p, "%d", count);
 883         }
 884     }
 885     p += sprintf(p, ",%d,%d,%d", tx, ty, minmoves);
 886     ret = sresize(ret, p+1 - ret, char);
 887
 888     sfree(board);
 889     sfree(forcefield);
 890
 891     return ret;
 892 }
 893
 894 static char *validate_desc(game_params *params, char *desc)
 895 {
 896     int w = params->w, h = params->h, wh = w*h;
 897     int *active, *link;
 898     int mains = 0;
 899     int i, tx, ty, minmoves;
 900     char *ret;
 901
 902     active = snewn(wh, int);
 903     link = snewn(wh, int);
 904     i = 0;
 905
 906     while (*desc && *desc != ',') {
 907         if (i >= wh) {
 908             ret = "Too much data in game description";
 909             goto done;
 910         }
 911         link[i] = -1;
 912         active[i] = FALSE;
 913         if (*desc == 'f' || *desc == 'F') {
 914             desc++;
 915             if (!*desc) {
 916                 ret = "Expected another character after 'f' in game "
 917                     "description";
 918                 goto done;
 919             }
 920         }
 921
 922         if (*desc == 'd' || *desc == 'D') {
 923             int dist;
 924
 925             desc++;
 926             if (!isdigit((unsigned char)*desc)) {
 927                 ret = "Expected a number after 'd' in game description";
 928                 goto done;
 929             }
 930             dist = atoi(desc);
 931             while (*desc && isdigit((unsigned char)*desc)) desc++;
 932
 933             if (dist <= 0 || dist > i) {
 934                 ret = "Out-of-range number after 'd' in game description";
 935                 goto done;
 936             }
 937
 938             if (!active[i - dist]) {
 939                 ret = "Invalid back-reference in game description";
 940                 goto done;
 941             }
 942
 943             link[i] = i - dist;
 944
 945             active[i] = TRUE;
 946             active[link[i]] = FALSE;
 947             i++;
 948         } else {
 949             int c = *desc++;
 950             int count = 1;
 951
 952             if (!strchr("aAmMeEwW", c)) {
 953                 ret = "Invalid character in game description";
 954                 goto done;
 955             }
 956             if (isdigit((unsigned char)*desc)) {
 957                 count = atoi(desc);
 958                 while (*desc && isdigit((unsigned char)*desc)) desc++;
 959             }
 960             if (i + count > wh) {
 961                 ret = "Too much data in game description";
 962                 goto done;
 963             }
 964             while (count-- > 0) {
 965                 active[i] = (strchr("aAmM", c) != NULL);
 966                 link[i] = -1;
 967                 if (strchr("mM", c) != NULL) {
 968                     mains++;
 969                 }
 970                 i++;
 971             }
 972         }
 973     }
 974     if (mains != 1) {
 975         ret = (mains == 0 ? "No main piece specified in game description" :
 976                "More than one main piece specified in game description");
 977         goto done;
 978     }
 979     if (i < wh) {
 980         ret = "Not enough data in game description";
 981         goto done;
 982     }
 983
 984     /*
 985      * Now read the target coordinates.
 986      */
 987     i = sscanf(desc, ",%d,%d,%d", &tx, &ty, &minmoves);
 988     if (i < 2) {
 989         ret = "No target coordinates specified";
 990         goto done;
 991         /*
 992          * (but minmoves is optional)
 993          */
 994     }
 995
 996     ret = NULL;
 997
 998     done:
 999     sfree(active);
1000     sfree(link);
1001     return ret;
1002 }
1003
1004 static game_state *new_game(midend *me, game_params *params, char *desc)
1005 {
1006     int w = params->w, h = params->h, wh = w*h;
1007     game_state *state;
1008     int i;
1009
1010     state = snew(game_state);
1011     state->w = w;
1012     state->h = h;
1013     state->board = snewn(wh, unsigned char);
1014     state->lastmoved = state->lastmoved_pos = -1;
1015     state->movecount = 0;
1016     state->imm = snew(struct game_immutable_state);
1017     state->imm->refcount = 1;
1018     state->imm->forcefield = snewn(wh, unsigned char);
1019
1020     i = 0;
1021
1022     while (*desc && *desc != ',') {
1023         int f = FALSE;
1024
1025         assert(i < wh);
1026
1027         if (*desc == 'f') {
1028             f = TRUE;
1029             desc++;
1030             assert(*desc);
1031         }
1032
1033         if (*desc == 'd' || *desc == 'D') {
1034             int dist;
1035
1036             desc++;
1037             dist = atoi(desc);
1038             while (*desc && isdigit((unsigned char)*desc)) desc++;
1039
1040             state->board[i] = DIST(dist);
1041             state->imm->forcefield[i] = f;
1042
1043             i++;
1044         } else {
1045             int c = *desc++;
1046             int count = 1;
1047
1048             if (isdigit((unsigned char)*desc)) {
1049                 count = atoi(desc);
1050                 while (*desc && isdigit((unsigned char)*desc)) desc++;
1051             }
1052             assert(i + count <= wh);
1053
1054             c = (c == 'a' || c == 'A' ? ANCHOR :
1055                  c == 'm' || c == 'M' ? MAINANCHOR :
1056                  c == 'e' || c == 'E' ? EMPTY :
1057                  /* c == 'w' || c == 'W' ? */ WALL);
1058
1059             while (count-- > 0) {
1060                 state->board[i] = c;
1061                 state->imm->forcefield[i] = f;
1062                 i++;
1063             }
1064         }
1065     }
1066
1067     /*
1068      * Now read the target coordinates.
1069      */
1070     state->tx = state->ty = 0;
1071     state->minmoves = -1;
1072     i = sscanf(desc, ",%d,%d,%d", &state->tx, &state->ty, &state->minmoves);
1073
1074     if (state->board[state->ty*w+state->tx] == MAINANCHOR)
1075         state->completed = 0;          /* already complete! */
1076     else
1077         state->completed = -1;
1078
1079     state->cheated = FALSE;
1080     state->soln = NULL;
1081     state->soln_index = -1;
1082
1083     return state;
1084 }
1085
1086 static game_state *dup_game(game_state *state)
1087 {
1088     int w = state->w, h = state->h, wh = w*h;
1089     game_state *ret = snew(game_state);
1090
1091     ret->w = state->w;
1092     ret->h = state->h;
1093     ret->board = snewn(wh, unsigned char);
1094     memcpy(ret->board, state->board, wh);
1095     ret->tx = state->tx;
1096     ret->ty = state->ty;
1097     ret->minmoves = state->minmoves;
1098     ret->lastmoved = state->lastmoved;
1099     ret->lastmoved_pos = state->lastmoved_pos;
1100     ret->movecount = state->movecount;
1101     ret->completed = state->completed;
1102     ret->cheated = state->cheated;
1103     ret->imm = state->imm;
1104     ret->imm->refcount++;
1105     ret->soln = state->soln;
1106     ret->soln_index = state->soln_index;
1107     if (ret->soln)
1108         ret->soln->refcount++;
1109
1110     return ret;
1111 }
1112
1113 static void free_game(game_state *state)
1114 {
1115     if (--state->imm->refcount <= 0) {
1116         sfree(state->imm->forcefield);
1117         sfree(state->imm);
1118     }
1119     if (state->soln && --state->soln->refcount <= 0) {
1120         sfree(state->soln->moves);
1121         sfree(state->soln);
1122     }
1123     sfree(state->board);
1124     sfree(state);
1125 }
1126
1127 static char *solve_game(game_state *state, game_state *currstate,
1128                         char *aux, char **error)
1129 {
1130     int *moves;
1131     int nmoves;
1132     int i;
1133     char *ret, *p, sep;
1134
1135     /*
1136      * Run the solver and attempt to find the shortest solution
1137      * from the current position.
1138      */
1139     nmoves = solve_board(state->w, state->h, state->board,
1140                          state->imm->forcefield, state->tx, state->ty,
1141                          -1, &moves);
1142
1143     if (nmoves < 0) {
1144         *error = "Unable to find a solution to this puzzle";
1145         return NULL;
1146     }
1147     if (nmoves == 0) {
1148         *error = "Puzzle is already solved";
1149         return NULL;
1150     }
1151
1152     /*
1153      * Encode the resulting solution as a move string.
1154      */
1155     ret = snewn(nmoves * 40, char);
1156     p = ret;
1157     sep = 'S';
1158
1159     for (i = 0; i < nmoves; i++) {
1160         p += sprintf(p, "%c%d-%d", sep, moves[i*2], moves[i*2+1]);
1161         sep = ',';
1162     }
1163
1164     sfree(moves);
1165     assert(p - ret < nmoves * 40);
1166     ret = sresize(ret, p+1 - ret, char);
1167
1168     return ret;
1169 }
1170
1171 static int game_can_format_as_text_now(game_params *params)
1172 {
1173     return TRUE;
1174 }
1175
1176 static char *game_text_format(game_state *state)
1177 {
1178     return board_text_format(state->w, state->h, state->board,
1179                              state->imm->forcefield);
1180 }
1181
1182 struct game_ui {
1183     int dragging;
1184     int drag_anchor;
1185     int drag_offset_x, drag_offset_y;
1186     int drag_currpos;
1187     unsigned char *reachable;
1188     int *bfs_queue;                    /* used as scratch in interpret_move */
1189 };
1190
1191 static game_ui *new_ui(game_state *state)
1192 {
1193     int w = state->w, h = state->h, wh = w*h;
1194     game_ui *ui = snew(game_ui);
1195
1196     ui->dragging = FALSE;
1197     ui->drag_anchor = ui->drag_currpos = -1;
1198     ui->drag_offset_x = ui->drag_offset_y = -1;
1199     ui->reachable = snewn(wh, unsigned char);
1200     memset(ui->reachable, 0, wh);
1201     ui->bfs_queue = snewn(wh, int);
1202
1203     return ui;
1204 }
1205
1206 static void free_ui(game_ui *ui)
1207 {
1208     sfree(ui->bfs_queue);
1209     sfree(ui->reachable);
1210     sfree(ui);
1211 }
1212
1213 static char *encode_ui(game_ui *ui)
1214 {
1215     return NULL;
1216 }
1217
1218 static void decode_ui(game_ui *ui, char *encoding)
1219 {
1220 }
1221
1222 static void game_changed_state(game_ui *ui, game_state *oldstate,
1223                                game_state *newstate)
1224 {
1225 }
1226
1227 #define PREFERRED_TILESIZE 32
1228 #define TILESIZE (ds->tilesize)
1229 #define BORDER (TILESIZE/2)
1230 #define COORD(x)  ( (x) * TILESIZE + BORDER )
1231 #define FROMCOORD(x)  ( ((x) - BORDER + TILESIZE) / TILESIZE - 1 )
1232 #define BORDER_WIDTH (1 + TILESIZE/20)
1233 #define HIGHLIGHT_WIDTH (1 + TILESIZE/16)
1234
1235 #define FLASH_INTERVAL 0.10F
1236 #define FLASH_TIME 3*FLASH_INTERVAL
1237
1238 struct game_drawstate {
1239     int tilesize;
1240     int w, h;
1241     unsigned long *grid;               /* what's currently displayed */
1242     int started;
1243 };
1244
1245 static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds,
1246                             int x, int y, int button)
1247 {
1248     int w = state->w, h = state->h, wh = w*h;
1249     int tx, ty, i, j;
1250     int qhead, qtail;
1251
1252     if (button == LEFT_BUTTON) {
1253         tx = FROMCOORD(x);
1254         ty = FROMCOORD(y);
1255
1256         if (tx < 0 || tx >= w || ty < 0 || ty >= h ||
1257             !ISBLOCK(state->board[ty*w+tx]))
1258             return NULL;               /* this click has no effect */
1259
1260         /*
1261          * User has clicked on a block. Find the block's anchor
1262          * and register that we've started dragging it.
1263          */
1264         i = ty*w+tx;
1265         while (ISDIST(state->board[i]))
1266             i -= state->board[i];
1267         assert(i >= 0 && i < wh);
1268
1269         ui->dragging = TRUE;
1270         ui->drag_anchor = i;
1271         ui->drag_offset_x = tx - (i % w);
1272         ui->drag_offset_y = ty - (i / w);
1273         ui->drag_currpos = i;
1274
1275         /*
1276          * Now we immediately bfs out from the current location of
1277          * the anchor, to find all the places to which this block
1278          * can be dragged.
1279          */
1280         memset(ui->reachable, FALSE, wh);
1281         qhead = qtail = 0;
1282         ui->reachable[i] = TRUE;
1283         ui->bfs_queue[qtail++] = i;
1284         for (j = i; j < wh; j++)
1285             if (state->board[j] == DIST(j - i))
1286                 i = j;
1287         while (qhead < qtail) {
1288             int pos = ui->bfs_queue[qhead++];
1289             int x = pos % w, y = pos / w;
1290             int dir;
1291
1292             for (dir = 0; dir < 4; dir++) {
1293                 int dx = (dir == 0 ? -1 : dir == 1 ? +1 : 0);
1294                 int dy = (dir == 2 ? -1 : dir == 3 ? +1 : 0);
1295                 int newpos;
1296
1297                 if (x + dx < 0 || x + dx >= w ||
1298                     y + dy < 0 || y + dy >= h)
1299                     continue;
1300
1301                 newpos = pos + dy*w + dx;
1302                 if (ui->reachable[newpos])
1303                     continue;          /* already done this one */
1304
1305                 /*
1306                  * Now search the grid to see if the block we're
1307                  * dragging could fit into this space.
1308                  */
1309                 for (j = i; j >= 0; j = (ISDIST(state->board[j]) ?
1310                                          j - state->board[j] : -1)) {
1311                     int jx = (j+pos-ui->drag_anchor) % w;
1312                     int jy = (j+pos-ui->drag_anchor) / w;
1313                     int j2;
1314
1315                     if (jx + dx < 0 || jx + dx >= w ||
1316                         jy + dy < 0 || jy + dy >= h)
1317                         break;         /* this position isn't valid at all */
1318
1319                     j2 = (j+pos-ui->drag_anchor) + dy*w + dx;
1320
1321                     if (state->board[j2] == EMPTY &&
1322                         (!state->imm->forcefield[j2] ||
1323                          state->board[ui->drag_anchor] == MAINANCHOR))
1324                         continue;
1325                     while (ISDIST(state->board[j2]))
1326                         j2 -= state->board[j2];
1327                     assert(j2 >= 0 && j2 < wh);
1328                     if (j2 == ui->drag_anchor)
1329                         continue;
1330                     else
1331                         break;
1332                 }
1333
1334                 if (j < 0) {
1335                     /*
1336                      * If we got to the end of that loop without
1337                      * disqualifying this position, mark it as
1338                      * reachable for this drag.
1339                      */
1340                     ui->reachable[newpos] = TRUE;
1341                     ui->bfs_queue[qtail++] = newpos;
1342                 }
1343             }
1344         }
1345
1346         /*
1347          * And that's it. Update the display to reflect the start
1348          * of a drag.
1349          */
1350         return "";
1351     } else if (button == LEFT_DRAG && ui->dragging) {
1352         int dist, distlimit, dx, dy, s, px, py;
1353
1354         tx = FROMCOORD(x);
1355         ty = FROMCOORD(y);
1356
1357         tx -= ui->drag_offset_x;
1358         ty -= ui->drag_offset_y;
1359
1360         /*
1361          * Now search outwards from (tx,ty), in order of Manhattan
1362          * distance, until we find a reachable square.
1363          */
1364         distlimit = w+tx;
1365         distlimit = max(distlimit, h+ty);
1366         distlimit = max(distlimit, tx);
1367         distlimit = max(distlimit, ty);
1368         for (dist = 0; dist <= distlimit; dist++) {
1369             for (dx = -dist; dx <= dist; dx++)
1370                 for (s = -1; s <= +1; s += 2) {
1371                     dy = s * (dist - abs(dx));
1372                     px = tx + dx;
1373                     py = ty + dy;
1374                     if (px >= 0 && px < w && py >= 0 && py < h &&
1375                         ui->reachable[py*w+px]) {
1376                         ui->drag_currpos = py*w+px;
1377                         return "";
1378                     }
1379                 }
1380         }
1381         return NULL;                   /* give up - this drag has no effect */
1382     } else if (button == LEFT_RELEASE && ui->dragging) {
1383         char data[256], *str;
1384
1385         /*
1386          * Terminate the drag, and if the piece has actually moved
1387          * then return a move string quoting the old and new
1388          * locations of the piece's anchor.
1389          */
1390         if (ui->drag_anchor != ui->drag_currpos) {
1391             sprintf(data, "M%d-%d", ui->drag_anchor, ui->drag_currpos);
1392             str = dupstr(data);
1393         } else
1394             str = "";                  /* null move; just update the UI */
1395
1396         ui->dragging = FALSE;
1397         ui->drag_anchor = ui->drag_currpos = -1;
1398         ui->drag_offset_x = ui->drag_offset_y = -1;
1399         memset(ui->reachable, 0, wh);
1400
1401         return str;
1402     } else if (button == ' ' && state->soln) {
1403         /*
1404          * Make the next move in the stored solution.
1405          */
1406         char data[256];
1407         int a1, a2;
1408
1409         a1 = state->soln->moves[state->soln_index*2];
1410         a2 = state->soln->moves[state->soln_index*2+1];
1411         if (a1 == state->lastmoved_pos)
1412             a1 = state->lastmoved;
1413
1414         sprintf(data, "M%d-%d", a1, a2);
1415         return dupstr(data);
1416     }
1417
1418     return NULL;
1419 }
1420
1421 static int move_piece(int w, int h, const unsigned char *src,
1422                       unsigned char *dst, unsigned char *ff, int from, int to)
1423 {
1424     int wh = w*h;
1425     int i, j;
1426
1427     if (!ISANCHOR(dst[from]))
1428         return FALSE;
1429
1430     /*
1431      * Scan to the far end of the piece's linked list.
1432      */
1433     for (i = j = from; j < wh; j++)
1434         if (src[j] == DIST(j - i))
1435             i = j;
1436
1437     /*
1438      * Remove the piece from its old location in the new
1439      * game state.
1440      */
1441     for (j = i; j >= 0; j = (ISDIST(src[j]) ? j - src[j] : -1))
1442         dst[j] = EMPTY;
1443
1444     /*
1445      * And put it back in at the new location.
1446      */
1447     for (j = i; j >= 0; j = (ISDIST(src[j]) ? j - src[j] : -1)) {
1448         int jn = j + to - from;
1449         if (jn < 0 || jn >= wh)
1450             return FALSE;
1451         if (dst[jn] == EMPTY && (!ff[jn] || src[from] == MAINANCHOR)) {
1452             dst[jn] = src[j];
1453         } else {
1454             return FALSE;
1455         }
1456     }
1457
1458     return TRUE;
1459 }
1460
1461 static game_state *execute_move(game_state *state, char *move)
1462 {
1463     int w = state->w, h = state->h /* , wh = w*h */;
1464     char c;
1465     int a1, a2, n, movesize;
1466     game_state *ret = dup_game(state);
1467
1468     while (*move) {
1469         c = *move;
1470         if (c == 'S') {
1471             /*
1472              * This is a solve move, so we just set up a stored
1473              * solution path.
1474              */
1475             if (ret->soln && --ret->soln->refcount <= 0) {
1476                 sfree(ret->soln->moves);
1477                 sfree(ret->soln);
1478             }
1479             ret->soln = snew(struct game_solution);
1480             ret->soln->nmoves = 0;
1481             ret->soln->moves = NULL;
1482             ret->soln->refcount = 1;
1483             ret->soln_index = 0;
1484             ret->cheated = TRUE;
1485
1486             movesize = 0;
1487             move++;
1488             while (1) {
1489                 if (sscanf(move, "%d-%d%n", &a1, &a2, &n) != 2) {
1490                     free_game(ret);
1491                     return NULL;
1492                 }
1493
1494                 /*
1495                  * Special case: if the first move in the solution
1496                  * involves the piece for which we already have a
1497                  * partial stored move, adjust the source point to
1498                  * the original starting point of that piece.
1499                  */
1500                 if (ret->soln->nmoves == 0 && a1 == ret->lastmoved)
1501                     a1 = ret->lastmoved_pos;
1502
1503                 if (ret->soln->nmoves >= movesize) {
1504                     movesize = (ret->soln->nmoves + 48) * 4 / 3;
1505                     ret->soln->moves = sresize(ret->soln->moves,
1506                                                2*movesize, int);
1507                 }
1508
1509                 ret->soln->moves[2*ret->soln->nmoves] = a1;
1510                 ret->soln->moves[2*ret->soln->nmoves+1] = a2;
1511                 ret->soln->nmoves++;
1512                 move += n;
1513                 if (*move != ',')
1514                     break;
1515                 move++;                /* eat comma */
1516             }
1517         } else if (c == 'M') {
1518             move++;
1519             if (sscanf(move, "%d-%d%n", &a1, &a2, &n) != 2 ||
1520                 !move_piece(w, h, state->board, ret->board,
1521                             state->imm->forcefield, a1, a2)) {
1522                 free_game(ret);
1523                 return NULL;
1524             }
1525             if (a1 == ret->lastmoved) {
1526                 /*
1527                  * If the player has moved the same piece as they
1528                  * moved last time, don't increment the move
1529                  * count. In fact, if they've put the piece back
1530                  * where it started from, _decrement_ the move
1531                  * count.
1532                  */
1533                 if (a2 == ret->lastmoved_pos) {
1534                     ret->movecount--;  /* reverted last move */
1535                     ret->lastmoved = ret->lastmoved_pos = -1;
1536                 } else {
1537                     ret->lastmoved = a2;
1538                     /* don't change lastmoved_pos */
1539                 }
1540             } else {
1541                 ret->lastmoved = a2;
1542                 ret->lastmoved_pos = a1;
1543                 ret->movecount++;
1544             }
1545
1546             /*
1547              * If we have a stored solution path, see if we've
1548              * strayed from it or successfully made the next move
1549              * along it.
1550              */
1551             if (ret->soln && ret->lastmoved_pos >= 0) {
1552                 if (ret->lastmoved_pos !=
1553                     ret->soln->moves[ret->soln_index*2]) {
1554                     /* strayed from the path */
1555                     ret->soln->refcount--;
1556                     assert(ret->soln->refcount > 0);
1557                                        /* `state' at least still exists */
1558                     ret->soln = NULL;
1559                     ret->soln_index = -1;
1560                 } else if (ret->lastmoved ==
1561                            ret->soln->moves[ret->soln_index*2+1]) {
1562                     /* advanced along the path */
1563                     ret->soln_index++;
1564                     if (ret->soln_index >= ret->soln->nmoves) {
1565                         /* finished the path! */
1566                         ret->soln->refcount--;
1567                         assert(ret->soln->refcount > 0);
1568                                        /* `state' at least still exists */
1569                         ret->soln = NULL;
1570                         ret->soln_index = -1;
1571                     }
1572                 }
1573             }
1574
1575             if (ret->board[a2] == MAINANCHOR &&
1576                 a2 == ret->ty * w + ret->tx && ret->completed < 0)
1577                 ret->completed = ret->movecount;
1578             move += n;
1579         } else {
1580             free_game(ret);
1581             return NULL;
1582         }
1583         if (*move == ';')
1584             move++;
1585         else if (*move) {
1586             free_game(ret);
1587             return NULL;
1588         }
1589     }
1590
1591     return ret;
1592 }
1593
1594 /* ----------------------------------------------------------------------
1595  * Drawing routines.
1596  */
1597
1598 static void game_compute_size(game_params *params, int tilesize,
1599                               int *x, int *y)
1600 {
1601     /* fool the macros */
1602     struct dummy { int tilesize; } dummy, *ds = &dummy;
1603     dummy.tilesize = tilesize;
1604
1605     *x = params->w * TILESIZE + 2*BORDER;
1606     *y = params->h * TILESIZE + 2*BORDER;
1607 }
1608
1609 static void game_set_size(drawing *dr, game_drawstate *ds,
1610                           game_params *params, int tilesize)
1611 {
1612     ds->tilesize = tilesize;
1613 }
1614
1615 static void raise_colour(float *target, float *src, float *limit)
1616 {
1617     int i;
1618     for (i = 0; i < 3; i++)
1619         target[i] = (2*src[i] + limit[i]) / 3;
1620 }
1621
1622 static float *game_colours(frontend *fe, int *ncolours)
1623 {
1624     float *ret = snewn(3 * NCOLOURS, float);
1625
1626     game_mkhighlight(fe, ret, COL_BACKGROUND, COL_HIGHLIGHT, COL_LOWLIGHT);
1627
1628     /*
1629      * When dragging a tile, we light it up a bit.
1630      */
1631     raise_colour(ret+3*COL_DRAGGING,
1632                  ret+3*COL_BACKGROUND, ret+3*COL_HIGHLIGHT);
1633     raise_colour(ret+3*COL_DRAGGING_HIGHLIGHT,
1634                  ret+3*COL_HIGHLIGHT, ret+3*COL_HIGHLIGHT);
1635     raise_colour(ret+3*COL_DRAGGING_LOWLIGHT,
1636                  ret+3*COL_LOWLIGHT, ret+3*COL_HIGHLIGHT);
1637
1638     /*
1639      * The main tile is tinted blue.
1640      */
1641     ret[COL_MAIN * 3 + 0] = ret[COL_BACKGROUND * 3 + 0];
1642     ret[COL_MAIN * 3 + 1] = ret[COL_BACKGROUND * 3 + 1];
1643     ret[COL_MAIN * 3 + 2] = ret[COL_HIGHLIGHT * 3 + 2];
1644     game_mkhighlight_specific(fe, ret, COL_MAIN,
1645                               COL_MAIN_HIGHLIGHT, COL_MAIN_LOWLIGHT);
1646
1647     /*
1648      * And we light that up a bit too when dragging.
1649      */
1650     raise_colour(ret+3*COL_MAIN_DRAGGING,
1651                  ret+3*COL_MAIN, ret+3*COL_MAIN_HIGHLIGHT);
1652     raise_colour(ret+3*COL_MAIN_DRAGGING_HIGHLIGHT,
1653                  ret+3*COL_MAIN_HIGHLIGHT, ret+3*COL_MAIN_HIGHLIGHT);
1654     raise_colour(ret+3*COL_MAIN_DRAGGING_LOWLIGHT,
1655                  ret+3*COL_MAIN_LOWLIGHT, ret+3*COL_MAIN_HIGHLIGHT);
1656
1657     /*
1658      * The target area on the floor is tinted green.
1659      */
1660     ret[COL_TARGET * 3 + 0] = ret[COL_BACKGROUND * 3 + 0];
1661     ret[COL_TARGET * 3 + 1] = ret[COL_HIGHLIGHT * 3 + 1];
1662     ret[COL_TARGET * 3 + 2] = ret[COL_BACKGROUND * 3 + 2];
1663     game_mkhighlight_specific(fe, ret, COL_TARGET,
1664                               COL_TARGET_HIGHLIGHT, COL_TARGET_LOWLIGHT);
1665
1666     *ncolours = NCOLOURS;
1667     return ret;
1668 }
1669
1670 static game_drawstate *game_new_drawstate(drawing *dr, game_state *state)
1671 {
1672     int w = state->w, h = state->h, wh = w*h;
1673     struct game_drawstate *ds = snew(struct game_drawstate);
1674     int i;
1675
1676     ds->tilesize = 0;
1677     ds->w = w;
1678     ds->h = h;
1679     ds->started = FALSE;
1680     ds->grid = snewn(wh, unsigned long);
1681     for (i = 0; i < wh; i++)
1682         ds->grid[i] = ~(unsigned long)0;
1683
1684     return ds;
1685 }
1686
1687 static void game_free_drawstate(drawing *dr, game_drawstate *ds)
1688 {
1689     sfree(ds->grid);
1690     sfree(ds);
1691 }
1692
1693 #define BG_NORMAL       0x00000001UL
1694 #define BG_TARGET       0x00000002UL
1695 #define BG_FORCEFIELD   0x00000004UL
1696 #define FLASH_LOW       0x00000008UL
1697 #define FLASH_HIGH      0x00000010UL
1698 #define FG_WALL         0x00000020UL
1699 #define FG_MAIN         0x00000040UL
1700 #define FG_NORMAL       0x00000080UL
1701 #define FG_DRAGGING     0x00000100UL
1702 #define FG_SHADOW       0x00000200UL
1703 #define FG_SOLVEPIECE   0x00000400UL
1704 #define FG_MAINPIECESH  11
1705 #define FG_SHADOWSH     19
1706
1707 #define PIECE_LBORDER   0x00000001UL
1708 #define PIECE_TBORDER   0x00000002UL
1709 #define PIECE_RBORDER   0x00000004UL
1710 #define PIECE_BBORDER   0x00000008UL
1711 #define PIECE_TLCORNER  0x00000010UL
1712 #define PIECE_TRCORNER  0x00000020UL
1713 #define PIECE_BLCORNER  0x00000040UL
1714 #define PIECE_BRCORNER  0x00000080UL
1715 #define PIECE_MASK      0x000000FFUL
1716
1717 /*
1718  * Utility function.
1719  */
1720 #define TYPE_MASK 0xF000
1721 #define COL_MASK 0x0FFF
1722 #define TYPE_RECT 0x0000
1723 #define TYPE_TLCIRC 0x4000
1724 #define TYPE_TRCIRC 0x5000
1725 #define TYPE_BLCIRC 0x6000
1726 #define TYPE_BRCIRC 0x7000
1727 static void maybe_rect(drawing *dr, int x, int y, int w, int h,
1728                        int coltype, int col2)
1729 {
1730     int colour = coltype & COL_MASK, type = coltype & TYPE_MASK;
1731
1732     if (colour > NCOLOURS)
1733         return;
1734     if (type == TYPE_RECT) {
1735         draw_rect(dr, x, y, w, h, colour);
1736     } else {
1737         int cx, cy, r;
1738
1739         clip(dr, x, y, w, h);
1740
1741         cx = x;
1742         cy = y;
1743         r = w-1;
1744         if (type & 0x1000)
1745             cx += r;
1746         if (type & 0x2000)
1747             cy += r;
1748
1749         if (col2 == -1 || col2 == coltype) {
1750             assert(w == h);
1751             draw_circle(dr, cx, cy, r, colour, colour);
1752         } else {
1753             /*
1754              * We aim to draw a quadrant of a circle in two
1755              * different colours. We do this using Bresenham's
1756              * algorithm directly, because the Puzzles drawing API
1757              * doesn't have a draw-sector primitive.
1758              */
1759             int bx, by, bd, bd2;
1760             int xm = (type & 0x1000 ? -1 : +1);
1761             int ym = (type & 0x2000 ? -1 : +1);
1762
1763             by = r;
1764             bx = 0;
1765             bd = 0;
1766             while (by >= bx) {
1767                 /*
1768                  * Plot the point.
1769                  */
1770                 {
1771                     int x1 = cx+xm*bx, y1 = cy+ym*bx;
1772                     int x2, y2;
1773
1774                     x2 = cx+xm*by; y2 = y1;
1775                     draw_rect(dr, min(x1,x2), min(y1,y2),
1776                               abs(x1-x2)+1, abs(y1-y2)+1, colour);
1777                     x2 = x1; y2 = cy+ym*by;
1778                     draw_rect(dr, min(x1,x2), min(y1,y2),
1779                               abs(x1-x2)+1, abs(y1-y2)+1, col2);
1780                 }
1781
1782                 bd += 2*bx + 1;
1783                 bd2 = bd - (2*by - 1);
1784                 if (abs(bd2) < abs(bd)) {
1785                     bd = bd2;
1786                     by--;
1787                 }
1788                 bx++;
1789             }
1790         }
1791
1792         unclip(dr);
1793     }
1794 }
1795
1796 static void draw_wallpart(drawing *dr, game_drawstate *ds,
1797                           int tx, int ty, unsigned long val,
1798                           int cl, int cc, int ch)
1799 {
1800     int coords[6];
1801
1802     draw_rect(dr, tx, ty, TILESIZE, TILESIZE, cc);
1803     if (val & PIECE_LBORDER)
1804         draw_rect(dr, tx, ty, HIGHLIGHT_WIDTH, TILESIZE,
1805                   ch);
1806     if (val & PIECE_RBORDER)
1807         draw_rect(dr, tx+TILESIZE-HIGHLIGHT_WIDTH, ty,
1808                   HIGHLIGHT_WIDTH, TILESIZE, cl);
1809     if (val & PIECE_TBORDER)
1810         draw_rect(dr, tx, ty, TILESIZE, HIGHLIGHT_WIDTH, ch);
1811     if (val & PIECE_BBORDER)
1812         draw_rect(dr, tx, ty+TILESIZE-HIGHLIGHT_WIDTH,
1813                   TILESIZE, HIGHLIGHT_WIDTH, cl);
1814     if (!((PIECE_BBORDER | PIECE_LBORDER) &~ val)) {
1815         draw_rect(dr, tx, ty+TILESIZE-HIGHLIGHT_WIDTH,
1816                   HIGHLIGHT_WIDTH, HIGHLIGHT_WIDTH, cl);
1817         clip(dr, tx, ty+TILESIZE-HIGHLIGHT_WIDTH,
1818              HIGHLIGHT_WIDTH, HIGHLIGHT_WIDTH);
1819         coords[0] = tx - 1;
1820         coords[1] = ty + TILESIZE - HIGHLIGHT_WIDTH - 1;
1821         coords[2] = tx + HIGHLIGHT_WIDTH;
1822         coords[3] = ty + TILESIZE - HIGHLIGHT_WIDTH - 1;
1823         coords[4] = tx - 1;
1824         coords[5] = ty + TILESIZE;
1825         draw_polygon(dr, coords, 3, ch, ch);
1826         unclip(dr);
1827     } else if (val & PIECE_BLCORNER) {
1828         draw_rect(dr, tx, ty+TILESIZE-HIGHLIGHT_WIDTH,
1829                   HIGHLIGHT_WIDTH, HIGHLIGHT_WIDTH, ch);
1830         clip(dr, tx, ty+TILESIZE-HIGHLIGHT_WIDTH,
1831              HIGHLIGHT_WIDTH, HIGHLIGHT_WIDTH);
1832         coords[0] = tx - 1;
1833         coords[1] = ty + TILESIZE - HIGHLIGHT_WIDTH - 1;
1834         coords[2] = tx + HIGHLIGHT_WIDTH;
1835         coords[3] = ty + TILESIZE - HIGHLIGHT_WIDTH - 1;
1836         coords[4] = tx - 1;
1837         coords[5] = ty + TILESIZE;
1838         draw_polygon(dr, coords, 3, cl, cl);
1839         unclip(dr);
1840     }
1841     if (!((PIECE_TBORDER | PIECE_RBORDER) &~ val)) {
1842         draw_rect(dr, tx+TILESIZE-HIGHLIGHT_WIDTH, ty,
1843                   HIGHLIGHT_WIDTH, HIGHLIGHT_WIDTH, cl);
1844         clip(dr, tx+TILESIZE-HIGHLIGHT_WIDTH, ty,
1845              HIGHLIGHT_WIDTH, HIGHLIGHT_WIDTH);
1846         coords[0] = tx + TILESIZE - HIGHLIGHT_WIDTH - 1;
1847         coords[1] = ty - 1;
1848         coords[2] = tx + TILESIZE;
1849         coords[3] = ty - 1;
1850         coords[4] = tx + TILESIZE - HIGHLIGHT_WIDTH - 1;
1851         coords[5] = ty + HIGHLIGHT_WIDTH;
1852         draw_polygon(dr, coords, 3, ch, ch);
1853         unclip(dr);
1854     } else if (val & PIECE_TRCORNER) {
1855         draw_rect(dr, tx+TILESIZE-HIGHLIGHT_WIDTH, ty,
1856                   HIGHLIGHT_WIDTH, HIGHLIGHT_WIDTH, ch);
1857         clip(dr, tx+TILESIZE-HIGHLIGHT_WIDTH, ty,
1858              HIGHLIGHT_WIDTH, HIGHLIGHT_WIDTH);
1859         coords[0] = tx + TILESIZE - HIGHLIGHT_WIDTH - 1;
1860         coords[1] = ty - 1;
1861         coords[2] = tx + TILESIZE;
1862         coords[3] = ty - 1;
1863         coords[4] = tx + TILESIZE - HIGHLIGHT_WIDTH - 1;
1864         coords[5] = ty + HIGHLIGHT_WIDTH;
1865         draw_polygon(dr, coords, 3, cl, cl);
1866         unclip(dr);
1867     }
1868     if (val & PIECE_TLCORNER)
1869         draw_rect(dr, tx, ty, HIGHLIGHT_WIDTH, HIGHLIGHT_WIDTH, ch);
1870     if (val & PIECE_BRCORNER)
1871         draw_rect(dr, tx+TILESIZE-HIGHLIGHT_WIDTH,
1872                   ty+TILESIZE-HIGHLIGHT_WIDTH,
1873                   HIGHLIGHT_WIDTH, HIGHLIGHT_WIDTH, cl);
1874 }
1875
1876 static void draw_piecepart(drawing *dr, game_drawstate *ds,
1877                            int tx, int ty, unsigned long val,
1878                            int cl, int cc, int ch)
1879 {
1880     int x[6], y[6];
1881
1882     /*
1883      * Drawing the blocks is hellishly fiddly. The blocks don't
1884      * stretch to the full size of the tile; there's a border
1885      * around them of size BORDER_WIDTH. Then they have bevelled
1886      * borders of size HIGHLIGHT_WIDTH, and also rounded corners.
1887      *
1888      * I tried for some time to find a clean and clever way to
1889      * figure out what needed drawing from the corner and border
1890      * flags, but in the end the cleanest way I could find was the
1891      * following. We divide the grid square into 25 parts by
1892      * ruling four horizontal and four vertical lines across it;
1893      * those lines are at BORDER_WIDTH and BORDER_WIDTH +
1894      * HIGHLIGHT_WIDTH from the top, from the bottom, from the
1895      * left and from the right. Then we carefully consider each of
1896      * the resulting 25 sections of square, and decide separately
1897      * what needs to go in it based on the flags. In complicated
1898      * cases there can be up to five possibilities affecting any
1899      * given section (no corner or border flags, just the corner
1900      * flag, one border flag, the other border flag, both border
1901      * flags). So there's a lot of very fiddly logic here and all
1902      * I could really think to do was give it my best shot and
1903      * then test it and correct all the typos. Not fun to write,
1904      * and I'm sure it isn't fun to read either, but it seems to
1905      * work.
1906      */
1907
1908     x[0] = tx;
1909     x[1] = x[0] + BORDER_WIDTH;
1910     x[2] = x[1] + HIGHLIGHT_WIDTH;
1911     x[5] = tx + TILESIZE;
1912     x[4] = x[5] - BORDER_WIDTH;
1913     x[3] = x[4] - HIGHLIGHT_WIDTH;
1914
1915     y[0] = ty;
1916     y[1] = y[0] + BORDER_WIDTH;
1917     y[2] = y[1] + HIGHLIGHT_WIDTH;
1918     y[5] = ty + TILESIZE;
1919     y[4] = y[5] - BORDER_WIDTH;
1920     y[3] = y[4] - HIGHLIGHT_WIDTH;
1921
1922 #define RECT(p,q) x[p], y[q], x[(p)+1]-x[p], y[(q)+1]-y[q]
1923
1924     maybe_rect(dr, RECT(0,0),
1925                (val & (PIECE_TLCORNER | PIECE_TBORDER |
1926                        PIECE_LBORDER)) ? -1 : cc, -1);
1927     maybe_rect(dr, RECT(1,0),
1928                (val & PIECE_TLCORNER) ? ch : (val & PIECE_TBORDER) ? -1 :
1929                (val & PIECE_LBORDER) ? ch : cc, -1);
1930     maybe_rect(dr, RECT(2,0),
1931                (val & PIECE_TBORDER) ? -1 : cc, -1);
1932     maybe_rect(dr, RECT(3,0),
1933                (val & PIECE_TRCORNER) ? cl : (val & PIECE_TBORDER) ? -1 :
1934                (val & PIECE_RBORDER) ? cl : cc, -1);
1935     maybe_rect(dr, RECT(4,0),
1936                (val & (PIECE_TRCORNER | PIECE_TBORDER |
1937                        PIECE_RBORDER)) ? -1 : cc, -1);
1938     maybe_rect(dr, RECT(0,1),
1939                (val & PIECE_TLCORNER) ? ch : (val & PIECE_LBORDER) ? -1 :
1940                (val & PIECE_TBORDER) ? ch : cc, -1);
1941     maybe_rect(dr, RECT(1,1),
1942                (val & PIECE_TLCORNER) ? cc : -1, -1);
1943     maybe_rect(dr, RECT(1,1),
1944                (val & PIECE_TLCORNER) ? ch | TYPE_TLCIRC :
1945                !((PIECE_TBORDER | PIECE_LBORDER) &~ val) ? ch | TYPE_BRCIRC :
1946                (val & (PIECE_TBORDER | PIECE_LBORDER)) ? ch : cc, -1);
1947     maybe_rect(dr, RECT(2,1),
1948                (val & PIECE_TBORDER) ? ch : cc, -1);
1949     maybe_rect(dr, RECT(3,1),
1950                (val & PIECE_TRCORNER) ? cc : -1, -1);
1951     maybe_rect(dr, RECT(3,1),
1952                (val & (PIECE_TBORDER | PIECE_RBORDER)) == PIECE_TBORDER ? ch :
1953                (val & (PIECE_TBORDER | PIECE_RBORDER)) == PIECE_RBORDER ? cl :
1954                !((PIECE_TBORDER|PIECE_RBORDER) &~ val) ? cl | TYPE_BLCIRC :
1955                (val & PIECE_TRCORNER) ? cl | TYPE_TRCIRC :
1956                cc, ch);
1957     maybe_rect(dr, RECT(4,1),
1958                (val & PIECE_TRCORNER) ? ch : (val & PIECE_RBORDER) ? -1 :
1959                (val & PIECE_TBORDER) ? ch : cc, -1);
1960     maybe_rect(dr, RECT(0,2),
1961                (val & PIECE_LBORDER) ? -1 : cc, -1);
1962     maybe_rect(dr, RECT(1,2),
1963                (val & PIECE_LBORDER) ? ch : cc, -1);
1964     maybe_rect(dr, RECT(2,2),
1965                cc, -1);
1966     maybe_rect(dr, RECT(3,2),
1967                (val & PIECE_RBORDER) ? cl : cc, -1);
1968     maybe_rect(dr, RECT(4,2),
1969                (val & PIECE_RBORDER) ? -1 : cc, -1);
1970     maybe_rect(dr, RECT(0,3),
1971                (val & PIECE_BLCORNER) ? cl : (val & PIECE_LBORDER) ? -1 :
1972                (val & PIECE_BBORDER) ? cl : cc, -1);
1973     maybe_rect(dr, RECT(1,3),
1974                (val & PIECE_BLCORNER) ? cc : -1, -1);
1975     maybe_rect(dr, RECT(1,3),
1976                (val & (PIECE_BBORDER | PIECE_LBORDER)) == PIECE_BBORDER ? cl :
1977                (val & (PIECE_BBORDER | PIECE_LBORDER)) == PIECE_LBORDER ? ch :
1978                !((PIECE_BBORDER|PIECE_LBORDER) &~ val) ? ch | TYPE_TRCIRC :
1979                (val & PIECE_BLCORNER) ? ch | TYPE_BLCIRC :
1980                cc, cl);
1981     maybe_rect(dr, RECT(2,3),
1982                (val & PIECE_BBORDER) ? cl : cc, -1);
1983     maybe_rect(dr, RECT(3,3),
1984                (val & PIECE_BRCORNER) ? cc : -1, -1);
1985     maybe_rect(dr, RECT(3,3),
1986                (val & PIECE_BRCORNER) ? cl | TYPE_BRCIRC :
1987                !((PIECE_BBORDER | PIECE_RBORDER) &~ val) ? cl | TYPE_TLCIRC :
1988                (val & (PIECE_BBORDER | PIECE_RBORDER)) ? cl : cc, -1);
1989     maybe_rect(dr, RECT(4,3),
1990                (val & PIECE_BRCORNER) ? cl : (val & PIECE_RBORDER) ? -1 :
1991                (val & PIECE_BBORDER) ? cl : cc, -1);
1992     maybe_rect(dr, RECT(0,4),
1993                (val & (PIECE_BLCORNER | PIECE_BBORDER |
1994                        PIECE_LBORDER)) ? -1 : cc, -1);
1995     maybe_rect(dr, RECT(1,4),
1996                (val & PIECE_BLCORNER) ? ch : (val & PIECE_BBORDER) ? -1 :
1997                (val & PIECE_LBORDER) ? ch : cc, -1);
1998     maybe_rect(dr, RECT(2,4),
1999                (val & PIECE_BBORDER) ? -1 : cc, -1);
2000     maybe_rect(dr, RECT(3,4),
2001                (val & PIECE_BRCORNER) ? cl : (val & PIECE_BBORDER) ? -1 :
2002                (val & PIECE_RBORDER) ? cl : cc, -1);
2003     maybe_rect(dr, RECT(4,4),
2004                (val & (PIECE_BRCORNER | PIECE_BBORDER |
2005                        PIECE_RBORDER)) ? -1 : cc, -1);
2006
2007 #undef RECT
2008 }
2009
2010 static void draw_tile(drawing *dr, game_drawstate *ds,
2011                       int x, int y, unsigned long val)
2012 {
2013     int tx = COORD(x), ty = COORD(y);
2014     int cc, ch, cl;
2015
2016     /*
2017      * Draw the tile background.
2018      */
2019     if (val & BG_TARGET)
2020         cc = COL_TARGET;
2021     else
2022         cc = COL_BACKGROUND;
2023     ch = cc+1;
2024     cl = cc+2;
2025     if (val & FLASH_LOW)
2026         cc = cl;
2027     else if (val & FLASH_HIGH)
2028         cc = ch;
2029
2030     draw_rect(dr, tx, ty, TILESIZE, TILESIZE, cc);
2031     if (val & BG_FORCEFIELD) {
2032         /*
2033          * Cattle-grid effect to indicate that nothing but the
2034          * main block can slide over this square.
2035          */
2036         int n = 3 * (TILESIZE / (3*HIGHLIGHT_WIDTH));
2037         int i;
2038
2039         for (i = 1; i < n; i += 3) {
2040             draw_rect(dr, tx,ty+(TILESIZE*i/n), TILESIZE,HIGHLIGHT_WIDTH, cl);
2041             draw_rect(dr, tx+(TILESIZE*i/n),ty, HIGHLIGHT_WIDTH,TILESIZE, cl);
2042         }
2043     }
2044
2045     /*
2046      * Draw the tile midground: a shadow of a block, for
2047      * displaying partial solutions.
2048      */
2049     if (val & FG_SHADOW) {
2050         draw_piecepart(dr, ds, tx, ty, (val >> FG_SHADOWSH) & PIECE_MASK,
2051                        cl, cl, cl);
2052     }
2053
2054     /*
2055      * Draw the tile foreground, i.e. some section of a block or
2056      * wall.
2057      */
2058     if (val & FG_WALL) {
2059         cc = COL_BACKGROUND;
2060         ch = cc+1;
2061         cl = cc+2;
2062         if (val & FLASH_LOW)
2063             cc = cl;
2064         else if (val & FLASH_HIGH)
2065             cc = ch;
2066
2067         draw_wallpart(dr, ds, tx, ty, (val >> FG_MAINPIECESH) & PIECE_MASK,
2068                       cl, cc, ch);
2069     } else if (val & (FG_MAIN | FG_NORMAL)) {
2070         if (val & FG_DRAGGING)
2071             cc = (val & FG_MAIN ? COL_MAIN_DRAGGING : COL_DRAGGING);
2072         else
2073             cc = (val & FG_MAIN ? COL_MAIN : COL_BACKGROUND);
2074         ch = cc+1;
2075         cl = cc+2;
2076
2077         if (val & FLASH_LOW)
2078             cc = cl;
2079         else if (val & (FLASH_HIGH | FG_SOLVEPIECE))
2080             cc = ch;
2081
2082         draw_piecepart(dr, ds, tx, ty, (val >> FG_MAINPIECESH) & PIECE_MASK,
2083                        cl, cc, ch);
2084     }
2085
2086     draw_update(dr, tx, ty, TILESIZE, TILESIZE);
2087 }
2088
2089 static unsigned long find_piecepart(int w, int h, int *dsf, int x, int y)
2090 {
2091     int i = y*w+x;
2092     int canon = dsf_canonify(dsf, i);
2093     unsigned long val = 0;
2094
2095     if (x == 0 || canon != dsf_canonify(dsf, i-1))
2096         val |= PIECE_LBORDER;
2097     if (y== 0 || canon != dsf_canonify(dsf, i-w))
2098         val |= PIECE_TBORDER;
2099     if (x == w-1 || canon != dsf_canonify(dsf, i+1))
2100         val |= PIECE_RBORDER;
2101     if (y == h-1 || canon != dsf_canonify(dsf, i+w))
2102         val |= PIECE_BBORDER;
2103     if (!(val & (PIECE_TBORDER | PIECE_LBORDER)) &&
2104         canon != dsf_canonify(dsf, i-1-w))
2105         val |= PIECE_TLCORNER;
2106     if (!(val & (PIECE_TBORDER | PIECE_RBORDER)) &&
2107         canon != dsf_canonify(dsf, i+1-w))
2108         val |= PIECE_TRCORNER;
2109     if (!(val & (PIECE_BBORDER | PIECE_LBORDER)) &&
2110         canon != dsf_canonify(dsf, i-1+w))
2111         val |= PIECE_BLCORNER;
2112     if (!(val & (PIECE_BBORDER | PIECE_RBORDER)) &&
2113         canon != dsf_canonify(dsf, i+1+w))
2114         val |= PIECE_BRCORNER;
2115     return val;
2116 }
2117
2118 static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate,
2119                         game_state *state, int dir, game_ui *ui,
2120                         float animtime, float flashtime)
2121 {
2122     int w = state->w, h = state->h, wh = w*h;
2123     unsigned char *board;
2124     int *dsf;
2125     int x, y, mainanchor, mainpos, dragpos, solvepos, solvesrc, solvedst;
2126
2127     if (!ds->started) {
2128         /*
2129          * The initial contents of the window are not guaranteed
2130          * and can vary with front ends. To be on the safe side,
2131          * all games should start by drawing a big
2132          * background-colour rectangle covering the whole window.
2133          */
2134         draw_rect(dr, 0, 0, 10*ds->tilesize, 10*ds->tilesize, COL_BACKGROUND);
2135         ds->started = TRUE;
2136     }
2137
2138     /*
2139      * Construct the board we'll be displaying (which may be
2140      * different from the one in state if ui describes a drag in
2141      * progress).
2142      */
2143     board = snewn(wh, unsigned char);
2144     memcpy(board, state->board, wh);
2145     if (ui->dragging) {
2146         int mpret = move_piece(w, h, state->board, board,
2147                                state->imm->forcefield,
2148                                ui->drag_anchor, ui->drag_currpos);
2149         assert(mpret);
2150     }
2151
2152     if (state->soln) {
2153         solvesrc = state->soln->moves[state->soln_index*2];
2154         solvedst = state->soln->moves[state->soln_index*2+1];
2155         if (solvesrc == state->lastmoved_pos)
2156             solvesrc = state->lastmoved;
2157         if (solvesrc == ui->drag_anchor)
2158             solvesrc = ui->drag_currpos;
2159     } else
2160         solvesrc = solvedst = -1;
2161
2162     /*
2163      * Build a dsf out of that board, so we can conveniently tell
2164      * which edges are connected and which aren't.
2165      */
2166     dsf = snew_dsf(wh);
2167     mainanchor = -1;
2168     for (y = 0; y < h; y++)
2169         for (x = 0; x < w; x++) {
2170             int i = y*w+x;
2171
2172             if (ISDIST(board[i]))
2173                 dsf_merge(dsf, i, i - board[i]);
2174             if (board[i] == MAINANCHOR)
2175                 mainanchor = i;
2176             if (board[i] == WALL) {
2177                 if (x > 0 && board[i-1] == WALL)
2178                     dsf_merge(dsf, i, i-1);
2179                 if (y > 0 && board[i-w] == WALL)
2180                     dsf_merge(dsf, i, i-w);
2181             }
2182         }
2183     assert(mainanchor >= 0);
2184     mainpos = dsf_canonify(dsf, mainanchor);
2185     dragpos = ui->drag_currpos > 0 ? dsf_canonify(dsf, ui->drag_currpos) : -1;
2186     solvepos = solvesrc >= 0 ? dsf_canonify(dsf, solvesrc) : -1;
2187
2188     /*
2189      * Now we can construct the data about what we want to draw.
2190      */
2191     for (y = 0; y < h; y++)
2192         for (x = 0; x < w; x++) {
2193             int i = y*w+x;
2194             int j;
2195             unsigned long val;
2196             int canon;
2197
2198             /*
2199              * See if this square is part of the target area.
2200              */
2201             j = i + mainanchor - (state->ty * w + state->tx);
2202             while (j >= 0 && j < wh && ISDIST(board[j]))
2203                 j -= board[j];
2204             if (j == mainanchor)
2205                 val = BG_TARGET;
2206             else
2207                 val = BG_NORMAL;
2208
2209             if (state->imm->forcefield[i])
2210                 val |= BG_FORCEFIELD;
2211
2212             if (flashtime > 0) {
2213                 int flashtype = (int)(flashtime / FLASH_INTERVAL) & 1;
2214                 val |= (flashtype ? FLASH_LOW : FLASH_HIGH);
2215             }
2216
2217             if (board[i] != EMPTY) {
2218                 canon = dsf_canonify(dsf, i);
2219
2220                 if (board[i] == WALL)
2221                     val |= FG_WALL;
2222                 else if (canon == mainpos)
2223                     val |= FG_MAIN;
2224                 else
2225                     val |= FG_NORMAL;
2226                 if (canon == dragpos)
2227                     val |= FG_DRAGGING;
2228                 if (canon == solvepos)
2229                     val |= FG_SOLVEPIECE;
2230
2231                 /*
2232                  * Now look around to see if other squares
2233                  * belonging to the same block are adjacent to us.
2234                  */
2235                 val |= find_piecepart(w, h, dsf, x, y) << FG_MAINPIECESH;
2236             }
2237
2238             /*
2239              * If we're in the middle of showing a solution,
2240              * display a shadow piece for the target of the
2241              * current move.
2242              */
2243             if (solvepos >= 0) {
2244                 int si = i - solvedst + solvesrc;
2245                 if (si >= 0 && si < wh && dsf_canonify(dsf, si) == solvepos) {
2246                     val |= find_piecepart(w, h, dsf,
2247                                           si % w, si / w) << FG_SHADOWSH;
2248                     val |= FG_SHADOW;
2249                 }
2250             }
2251
2252             if (val != ds->grid[i]) {
2253                 draw_tile(dr, ds, x, y, val);
2254                 ds->grid[i] = val;
2255             }
2256         }
2257
2258     /*
2259      * Update the status bar.
2260      */
2261     {
2262         char statusbuf[256];
2263
2264         sprintf(statusbuf, "%sMoves: %d",
2265                 (state->completed >= 0 ?
2266                  (state->cheated ? "Auto-solved. " : "COMPLETED! ") :
2267                  (state->cheated ? "Auto-solver used. " : "")),
2268                 (state->completed >= 0 ? state->completed : state->movecount));
2269         if (state->minmoves >= 0)
2270             sprintf(statusbuf+strlen(statusbuf), " (min %d)",
2271                     state->minmoves);
2272
2273         status_bar(dr, statusbuf);
2274     }
2275
2276     sfree(dsf);
2277     sfree(board);
2278 }
2279
2280 static float game_anim_length(game_state *oldstate, game_state *newstate,
2281                               int dir, game_ui *ui)
2282 {
2283     return 0.0F;
2284 }
2285
2286 static float game_flash_length(game_state *oldstate, game_state *newstate,
2287                                int dir, game_ui *ui)
2288 {
2289     if (oldstate->completed < 0 && newstate->completed >= 0)
2290         return FLASH_TIME;
2291
2292     return 0.0F;
2293 }
2294
2295 static int game_status(game_state *state)
2296 {
2297     return state->completed ? +1 : 0;
2298 }
2299
2300 static int game_timing_state(game_state *state, game_ui *ui)
2301 {
2302     return TRUE;
2303 }
2304
2305 static void game_print_size(game_params *params, float *x, float *y)
2306 {
2307 }
2308
2309 static void game_print(drawing *dr, game_state *state, int tilesize)
2310 {
2311 }
2312
2313 #ifdef COMBINED
2314 #define thegame slide
2315 #endif
2316
2317 const struct game thegame = {
2318     "Slide", NULL, NULL,
2319     default_params,
2320     game_fetch_preset,
2321     decode_params,
2322     encode_params,
2323     free_params,
2324     dup_params,
2325     TRUE, game_configure, custom_params,
2326     validate_params,
2327     new_game_desc,
2328     validate_desc,
2329     new_game,
2330     dup_game,
2331     free_game,
2332     TRUE, solve_game,
2333     TRUE, game_can_format_as_text_now, game_text_format,
2334     new_ui,
2335     free_ui,
2336     encode_ui,
2337     decode_ui,
2338     game_changed_state,
2339     interpret_move,
2340     execute_move,
2341     PREFERRED_TILESIZE, game_compute_size, game_set_size,
2342     game_colours,
2343     game_new_drawstate,
2344     game_free_drawstate,
2345     game_redraw,
2346     game_anim_length,
2347     game_flash_length,
2348     game_status,
2349     FALSE, FALSE, game_print_size, game_print,
2350     TRUE,                              /* wants_statusbar */
2351     FALSE, game_timing_state,
2352     0,                                 /* flags */
2353 };
2354
2355 #ifdef STANDALONE_SOLVER
2356
2357 #include <stdarg.h>
2358
2359 int main(int argc, char **argv)
2360 {
2361     game_params *p;
2362     game_state *s;
2363     char *id = NULL, *desc, *err;
2364     int count = FALSE;
2365     int ret;
2366     int *moves;
2367
2368     while (--argc > 0) {
2369         char *p = *++argv;
2370         /*
2371         if (!strcmp(p, "-v")) {
2372             verbose = TRUE;
2373         } else
2374         */
2375         if (!strcmp(p, "-c")) {
2376             count = TRUE;
2377         } else if (*p == '-') {
2378             fprintf(stderr, "%s: unrecognised option `%s'\n", argv[0], p);
2379             return 1;
2380         } else {
2381             id = p;
2382         }
2383     }
2384
2385     if (!id) {
2386         fprintf(stderr, "usage: %s [-c | -v] <game_id>\n", argv[0]);
2387         return 1;
2388     }
2389
2390     desc = strchr(id, ':');
2391     if (!desc) {
2392         fprintf(stderr, "%s: game id expects a colon in it\n", argv[0]);
2393         return 1;
2394     }
2395     *desc++ = '\0';
2396
2397     p = default_params();
2398     decode_params(p, id);
2399     err = validate_desc(p, desc);
2400     if (err) {
2401         fprintf(stderr, "%s: %s\n", argv[0], err);
2402         return 1;
2403     }
2404     s = new_game(NULL, p, desc);
2405
2406     ret = solve_board(s->w, s->h, s->board, s->imm->forcefield,
2407                       s->tx, s->ty, -1, &moves);
2408     if (ret < 0) {
2409         printf("No solution found\n");
2410     } else {
2411         int index = 0;
2412         if (count) {
2413             printf("%d moves required\n", ret);
2414             return 0;
2415         }
2416         while (1) {
2417             int moveret;
2418             char *text = board_text_format(s->w, s->h, s->board,
2419                                            s->imm->forcefield);
2420             game_state *s2;
2421
2422             printf("position %d:\n%s", index, text);
2423
2424             if (index >= ret)
2425                 break;
2426
2427             s2 = dup_game(s);
2428             moveret = move_piece(s->w, s->h, s->board,
2429                                  s2->board, s->imm->forcefield,
2430                                  moves[index*2], moves[index*2+1]);
2431             assert(moveret);
2432
2433             free_game(s);
2434             s = s2;
2435             index++;
2436         }
2437     }
2438
2439     return 0;
2440 }
2441
2442 #endif