unfinished/slide.c

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