pegs.c

   1 /*
   2  * pegs.c: the classic Peg Solitaire game.
   3  */
   4
   5 #include <stdio.h>
   6 #include <stdlib.h>
   7 #include <string.h>
   8 #include <assert.h>
   9 #include <ctype.h>
  10 #include <math.h>
  11
  12 #include "puzzles.h"
  13 #include "tree234.h"
  14
  15 #define GRID_HOLE 0
  16 #define GRID_PEG  1
  17 #define GRID_OBST 2
  18
  19 #define GRID_CURSOR 10
  20 #define GRID_JUMPING 20
  21
  22 enum {
  23     COL_BACKGROUND,
  24     COL_HIGHLIGHT,
  25     COL_LOWLIGHT,
  26     COL_PEG,
  27     COL_CURSOR,
  28     NCOLOURS
  29 };
  30
  31 /*
  32  * Grid shapes. I do some macro ickery here to ensure that my enum
  33  * and the various forms of my name list always match up.
  34  */
  35 #define TYPELIST(A) \
  36     A(CROSS,Cross,cross) \
  37     A(OCTAGON,Octagon,octagon) \
  38     A(RANDOM,Random,random)
  39 #define ENUM(upper,title,lower) TYPE_ ## upper,
  40 #define TITLE(upper,title,lower) #title,
  41 #define LOWER(upper,title,lower) #lower,
  42 #define CONFIG(upper,title,lower) ":" #title
  43
  44 enum { TYPELIST(ENUM) TYPECOUNT };
  45 static char const *const pegs_titletypes[] = { TYPELIST(TITLE) };
  46 static char const *const pegs_lowertypes[] = { TYPELIST(LOWER) };
  47 #define TYPECONFIG TYPELIST(CONFIG)
  48
  49 #define FLASH_FRAME 0.13F
  50
  51 struct game_params {
  52     int w, h;
  53     int type;
  54 };
  55
  56 struct game_state {
  57     int w, h;
  58     int completed;
  59     unsigned char *grid;
  60 };
  61
  62 static game_params *default_params(void)
  63 {
  64     game_params *ret = snew(game_params);
  65
  66     ret->w = ret->h = 7;
  67     ret->type = TYPE_CROSS;
  68
  69     return ret;
  70 }
  71
  72 static const struct game_params pegs_presets[] = {
  73     {7, 7, TYPE_CROSS},
  74     {7, 7, TYPE_OCTAGON},
  75     {5, 5, TYPE_RANDOM},
  76     {7, 7, TYPE_RANDOM},
  77     {9, 9, TYPE_RANDOM},
  78 };
  79
  80 static int game_fetch_preset(int i, char **name, game_params **params)
  81 {
  82     game_params *ret;
  83     char str[80];
  84
  85     if (i < 0 || i >= lenof(pegs_presets))
  86         return FALSE;
  87
  88     ret = snew(game_params);
  89     *ret = pegs_presets[i];
  90
  91     strcpy(str, pegs_titletypes[ret->type]);
  92     if (ret->type == TYPE_RANDOM)
  93         sprintf(str + strlen(str), " %dx%d", ret->w, ret->h);
  94
  95     *name = dupstr(str);
  96     *params = ret;
  97     return TRUE;
  98 }
  99
 100 static void free_params(game_params *params)
 101 {
 102     sfree(params);
 103 }
 104
 105 static game_params *dup_params(const game_params *params)
 106 {
 107     game_params *ret = snew(game_params);
 108     *ret = *params;                    /* structure copy */
 109     return ret;
 110 }
 111
 112 static void decode_params(game_params *params, char const *string)
 113 {
 114     char const *p = string;
 115     int i;
 116
 117     params->w = atoi(p);
 118     while (*p && isdigit((unsigned char)*p)) p++;
 119     if (*p == 'x') {
 120         p++;
 121         params->h = atoi(p);
 122         while (*p && isdigit((unsigned char)*p)) p++;
 123     } else {
 124         params->h = params->w;
 125     }
 126
 127     for (i = 0; i < lenof(pegs_lowertypes); i++)
 128         if (!strcmp(p, pegs_lowertypes[i]))
 129             params->type = i;
 130 }
 131
 132 static char *encode_params(const game_params *params, int full)
 133 {
 134     char str[80];
 135
 136     sprintf(str, "%dx%d", params->w, params->h);
 137     if (full) {
 138         assert(params->type >= 0 && params->type < lenof(pegs_lowertypes));
 139         strcat(str, pegs_lowertypes[params->type]);
 140     }
 141     return dupstr(str);
 142 }
 143
 144 static config_item *game_configure(const game_params *params)
 145 {
 146     config_item *ret = snewn(4, config_item);
 147     char buf[80];
 148
 149     ret[0].name = "Width";
 150     ret[0].type = C_STRING;
 151     sprintf(buf, "%d", params->w);
 152     ret[0].sval = dupstr(buf);
 153     ret[0].ival = 0;
 154
 155     ret[1].name = "Height";
 156     ret[1].type = C_STRING;
 157     sprintf(buf, "%d", params->h);
 158     ret[1].sval = dupstr(buf);
 159     ret[1].ival = 0;
 160
 161     ret[2].name = "Board type";
 162     ret[2].type = C_CHOICES;
 163     ret[2].sval = TYPECONFIG;
 164     ret[2].ival = params->type;
 165
 166     ret[3].name = NULL;
 167     ret[3].type = C_END;
 168     ret[3].sval = NULL;
 169     ret[3].ival = 0;
 170
 171     return ret;
 172 }
 173
 174 static game_params *custom_params(const config_item *cfg)
 175 {
 176     game_params *ret = snew(game_params);
 177
 178     ret->w = atoi(cfg[0].sval);
 179     ret->h = atoi(cfg[1].sval);
 180     ret->type = cfg[2].ival;
 181
 182     return ret;
 183 }
 184
 185 static char *validate_params(const game_params *params, int full)
 186 {
 187     if (full && (params->w <= 3 || params->h <= 3))
 188         return "Width and height must both be greater than three";
 189
 190     /*
 191      * It might be possible to implement generalisations of Cross
 192      * and Octagon, but only if I can find a proof that they're all
 193      * soluble. For the moment, therefore, I'm going to disallow
 194      * them at any size other than the standard one.
 195      */
 196     if (full && (params->type == TYPE_CROSS || params->type == TYPE_OCTAGON)) {
 197         if (params->w != 7 || params->h != 7)
 198             return "This board type is only supported at 7x7";
 199     }
 200     return NULL;
 201 }
 202
 203 /* ----------------------------------------------------------------------
 204  * Beginning of code to generate random Peg Solitaire boards.
 205  *
 206  * This procedure is done with no aesthetic judgment, no effort at
 207  * symmetry, no difficulty grading and generally no finesse
 208  * whatsoever. We simply begin with an empty board containing a
 209  * single peg, and repeatedly make random reverse moves until it's
 210  * plausibly full. This typically yields a scrappy haphazard mess
 211  * with several holes, an uneven shape, and no redeeming features
 212  * except guaranteed solubility.
 213  *
 214  * My only concessions to sophistication are (a) to repeat the
 215  * generation process until I at least get a grid that touches
 216  * every edge of the specified board size, and (b) to try when
 217  * selecting moves to reuse existing space rather than expanding
 218  * into new space (so that non-rectangular board shape becomes a
 219  * factor during play).
 220  */
 221
 222 struct move {
 223     /*
 224      * x,y are the start point of the move during generation (hence
 225      * its endpoint during normal play).
 226      *
 227      * dx,dy are the direction of the move during generation.
 228      * Absolute value 1. Hence, for example, x=3,y=5,dx=1,dy=0
 229      * means that the move during generation starts at (3,5) and
 230      * ends at (5,5), and vice versa during normal play.
 231      */
 232     int x, y, dx, dy;
 233     /*
 234      * cost is 0, 1 or 2, depending on how many GRID_OBSTs we must
 235      * turn into GRID_HOLEs to play this move.
 236      */
 237     int cost;
 238 };
 239
 240 static int movecmp(void *av, void *bv)
 241 {
 242     struct move *a = (struct move *)av;
 243     struct move *b = (struct move *)bv;
 244
 245     if (a->y < b->y)
 246         return -1;
 247     else if (a->y > b->y)
 248         return +1;
 249
 250     if (a->x < b->x)
 251         return -1;
 252     else if (a->x > b->x)
 253         return +1;
 254
 255     if (a->dy < b->dy)
 256         return -1;
 257     else if (a->dy > b->dy)
 258         return +1;
 259
 260     if (a->dx < b->dx)
 261         return -1;
 262     else if (a->dx > b->dx)
 263         return +1;
 264
 265     return 0;
 266 }
 267
 268 static int movecmpcost(void *av, void *bv)
 269 {
 270     struct move *a = (struct move *)av;
 271     struct move *b = (struct move *)bv;
 272
 273     if (a->cost < b->cost)
 274         return -1;
 275     else if (a->cost > b->cost)
 276         return +1;
 277
 278     return movecmp(av, bv);
 279 }
 280
 281 struct movetrees {
 282     tree234 *bymove, *bycost;
 283 };
 284
 285 static void update_moves(unsigned char *grid, int w, int h, int x, int y,
 286                          struct movetrees *trees)
 287 {
 288     struct move move;
 289     int dir, pos;
 290
 291     /*
 292      * There are twelve moves that can include (x,y): three in each
 293      * of four directions. Check each one to see if it's possible.
 294      */
 295     for (dir = 0; dir < 4; dir++) {
 296         int dx, dy;
 297
 298         if (dir & 1)
 299             dx = 0, dy = dir - 2;
 300         else
 301             dy = 0, dx = dir - 1;
 302
 303         assert(abs(dx) + abs(dy) == 1);
 304
 305         for (pos = 0; pos < 3; pos++) {
 306             int v1, v2, v3;
 307
 308             move.dx = dx;
 309             move.dy = dy;
 310             move.x = x - pos*dx;
 311             move.y = y - pos*dy;
 312
 313             if (move.x < 0 || move.x >= w || move.y < 0 || move.y >= h)
 314                 continue;              /* completely invalid move */
 315             if (move.x+2*move.dx < 0 || move.x+2*move.dx >= w ||
 316                 move.y+2*move.dy < 0 || move.y+2*move.dy >= h)
 317                 continue;              /* completely invalid move */
 318
 319             v1 = grid[move.y * w + move.x];
 320             v2 = grid[(move.y+move.dy) * w + (move.x+move.dx)];
 321             v3 = grid[(move.y+2*move.dy)*w + (move.x+2*move.dx)];
 322             if (v1 == GRID_PEG && v2 != GRID_PEG && v3 != GRID_PEG) {
 323                 struct move *m;
 324
 325                 move.cost = (v2 == GRID_OBST) + (v3 == GRID_OBST);
 326
 327                 /*
 328                  * This move is possible. See if it's already in
 329                  * the tree.
 330                  */
 331                 m = find234(trees->bymove, &move, NULL);
 332                 if (m && m->cost != move.cost) {
 333                     /*
 334                      * It's in the tree but listed with the wrong
 335                      * cost. Remove the old version.
 336                      */
 337 #ifdef GENERATION_DIAGNOSTICS
 338                     printf("correcting %d%+d,%d%+d at cost %d\n",
 339                            m->x, m->dx, m->y, m->dy, m->cost);
 340 #endif
 341                     del234(trees->bymove, m);
 342                     del234(trees->bycost, m);
 343                     sfree(m);
 344                     m = NULL;
 345                 }
 346                 if (!m) {
 347                     struct move *m, *m2;
 348                     m = snew(struct move);
 349                     *m = move;
 350                     m2 = add234(trees->bymove, m);
 351                     m2 = add234(trees->bycost, m);
 352                     assert(m2 == m);
 353 #ifdef GENERATION_DIAGNOSTICS
 354                     printf("adding %d%+d,%d%+d at cost %d\n",
 355                            move.x, move.dx, move.y, move.dy, move.cost);
 356 #endif
 357                 } else {
 358 #ifdef GENERATION_DIAGNOSTICS
 359                     printf("not adding %d%+d,%d%+d at cost %d\n",
 360                            move.x, move.dx, move.y, move.dy, move.cost);
 361 #endif
 362                 }
 363             } else {
 364                 /*
 365                  * This move is impossible. If it is already in the
 366                  * tree, delete it.
 367                  *
 368                  * (We make use here of the fact that del234
 369                  * doesn't have to be passed a pointer to the
 370                  * _actual_ element it's deleting: it merely needs
 371                  * one that compares equal to it, and it will
 372                  * return the one it deletes.)
 373                  */
 374                 struct move *m = del234(trees->bymove, &move);
 375 #ifdef GENERATION_DIAGNOSTICS
 376                 printf("%sdeleting %d%+d,%d%+d\n", m ? "" : "not ",
 377                        move.x, move.dx, move.y, move.dy);
 378 #endif
 379                 if (m) {
 380                     del234(trees->bycost, m);
 381                     sfree(m);
 382                 }
 383             }
 384         }
 385     }
 386 }
 387
 388 static void pegs_genmoves(unsigned char *grid, int w, int h, random_state *rs)
 389 {
 390     struct movetrees atrees, *trees = &atrees;
 391     struct move *m;
 392     int x, y, i, nmoves;
 393
 394     trees->bymove = newtree234(movecmp);
 395     trees->bycost = newtree234(movecmpcost);
 396
 397     for (y = 0; y < h; y++)
 398         for (x = 0; x < w; x++)
 399             if (grid[y*w+x] == GRID_PEG)
 400                 update_moves(grid, w, h, x, y, trees);
 401
 402     nmoves = 0;
 403
 404     while (1) {
 405         int limit, maxcost, index;
 406         struct move mtmp, move, *m;
 407
 408         /*
 409          * See how many moves we can make at zero cost. Make one,
 410          * if possible. Failing that, make a one-cost move, and
 411          * then a two-cost one.
 412          *
 413          * After filling at least half the input grid, we no longer
 414          * accept cost-2 moves: if that's our only option, we give
 415          * up and finish.
 416          */
 417         mtmp.y = h+1;
 418         maxcost = (nmoves < w*h/2 ? 2 : 1);
 419         m = NULL;                      /* placate optimiser */
 420         for (mtmp.cost = 0; mtmp.cost <= maxcost; mtmp.cost++) {
 421             limit = -1;
 422             m = findrelpos234(trees->bycost, &mtmp, NULL, REL234_LT, &limit);
 423 #ifdef GENERATION_DIAGNOSTICS
 424             printf("%d moves available with cost %d\n", limit+1, mtmp.cost);
 425 #endif
 426             if (m)
 427                 break;
 428         }
 429         if (!m)
 430             break;
 431
 432         index = random_upto(rs, limit+1);
 433         move = *(struct move *)index234(trees->bycost, index);
 434
 435 #ifdef GENERATION_DIAGNOSTICS
 436         printf("selecting move %d%+d,%d%+d at cost %d\n",
 437                move.x, move.dx, move.y, move.dy, move.cost);
 438 #endif
 439
 440         grid[move.y * w + move.x] = GRID_HOLE;
 441         grid[(move.y+move.dy) * w + (move.x+move.dx)] = GRID_PEG;
 442         grid[(move.y+2*move.dy)*w + (move.x+2*move.dx)] = GRID_PEG;
 443
 444         for (i = 0; i <= 2; i++) {
 445             int tx = move.x + i*move.dx;
 446             int ty = move.y + i*move.dy;
 447             update_moves(grid, w, h, tx, ty, trees);
 448         }
 449
 450         nmoves++;
 451     }
 452
 453     while ((m = delpos234(trees->bymove, 0)) != NULL) {
 454         del234(trees->bycost, m);
 455         sfree(m);
 456     }
 457     freetree234(trees->bymove);
 458     freetree234(trees->bycost);
 459 }
 460
 461 static void pegs_generate(unsigned char *grid, int w, int h, random_state *rs)
 462 {
 463     while (1) {
 464         int x, y, extremes;
 465
 466         memset(grid, GRID_OBST, w*h);
 467         grid[(h/2) * w + (w/2)] = GRID_PEG;
 468 #ifdef GENERATION_DIAGNOSTICS
 469         printf("beginning move selection\n");
 470 #endif
 471         pegs_genmoves(grid, w, h, rs);
 472 #ifdef GENERATION_DIAGNOSTICS
 473         printf("finished move selection\n");
 474 #endif
 475
 476         extremes = 0;
 477         for (y = 0; y < h; y++) {
 478             if (grid[y*w+0] != GRID_OBST)
 479                 extremes |= 1;
 480             if (grid[y*w+w-1] != GRID_OBST)
 481                 extremes |= 2;
 482         }
 483         for (x = 0; x < w; x++) {
 484             if (grid[0*w+x] != GRID_OBST)
 485                 extremes |= 4;
 486             if (grid[(h-1)*w+x] != GRID_OBST)
 487                 extremes |= 8;
 488         }
 489
 490         if (extremes == 15)
 491             break;
 492 #ifdef GENERATION_DIAGNOSTICS
 493         printf("insufficient extent; trying again\n");
 494 #endif
 495     }
 496 #ifdef GENERATION_DIAGNOSTICS
 497     fflush(stdout);
 498 #endif
 499 }
 500
 501 /* ----------------------------------------------------------------------
 502  * End of board generation code. Now for the client code which uses
 503  * it as part of the puzzle.
 504  */
 505
 506 static char *new_game_desc(const game_params *params, random_state *rs,
 507                            char **aux, int interactive)
 508 {
 509     int w = params->w, h = params->h;
 510     unsigned char *grid;
 511     char *ret;
 512     int i;
 513
 514     grid = snewn(w*h, unsigned char);
 515     if (params->type == TYPE_RANDOM) {
 516         pegs_generate(grid, w, h, rs);
 517     } else {
 518         int x, y, cx, cy, v;
 519
 520         for (y = 0; y < h; y++)
 521             for (x = 0; x < w; x++) {
 522                 v = GRID_OBST;         /* placate optimiser */
 523                 switch (params->type) {
 524                   case TYPE_CROSS:
 525                     cx = abs(x - w/2);
 526                     cy = abs(y - h/2);
 527                     if (cx == 0 && cy == 0)
 528                         v = GRID_HOLE;
 529                     else if (cx > 1 && cy > 1)
 530                         v = GRID_OBST;
 531                     else
 532                         v = GRID_PEG;
 533                     break;
 534                   case TYPE_OCTAGON:
 535                     cx = abs(x - w/2);
 536                     cy = abs(y - h/2);
 537                     if (cx + cy > 1 + max(w,h)/2)
 538                         v = GRID_OBST;
 539                     else
 540                         v = GRID_PEG;
 541                     break;
 542                 }
 543                 grid[y*w+x] = v;
 544             }
 545
 546         if (params->type == TYPE_OCTAGON) {
 547             /*
 548              * The octagonal (European) solitaire layout is
 549              * actually _insoluble_ with the starting hole at the
 550              * centre. Here's a proof:
 551              *
 552              * Colour the squares of the board diagonally in
 553              * stripes of three different colours, which I'll call
 554              * A, B and C. So the board looks like this:
 555              *
 556              *     A B C
 557              *   A B C A B
 558              * A B C A B C A
 559              * B C A B C A B
 560              * C A B C A B C
 561              *   B C A B C
 562              *     A B C
 563              *
 564              * Suppose we keep running track of the number of pegs
 565              * occuping each colour of square. This colouring has
 566              * the property that any valid move whatsoever changes
 567              * all three of those counts by one (two of them go
 568              * down and one goes up), which means that the _parity_
 569              * of every count flips on every move.
 570              *
 571              * If the centre square starts off unoccupied, then
 572              * there are twelve pegs on each colour and all three
 573              * counts start off even; therefore, after 35 moves all
 574              * three counts would have to be odd, which isn't
 575              * possible if there's only one peg left. []
 576              *
 577              * This proof works just as well if the starting hole
 578              * is _any_ of the thirteen positions labelled B. Also,
 579              * we can stripe the board in the opposite direction
 580              * and rule out any square labelled B in that colouring
 581              * as well. This leaves:
 582              *
 583              *     Y n Y
 584              *   n n Y n n
 585              * Y n n Y n n Y
 586              * n Y Y n Y Y n
 587              * Y n n Y n n Y
 588              *   n n Y n n
 589              *     Y n Y
 590              *
 591              * where the ns are squares we've proved insoluble, and
 592              * the Ys are the ones remaining.
 593              *
 594              * That doesn't prove all those starting positions to
 595              * be soluble, of course; they're merely the ones we
 596              * _haven't_ proved to be impossible. Nevertheless, it
 597              * turns out that they are all soluble, so when the
 598              * user requests an Octagon board the simplest thing is
 599              * to pick one of these at random.
 600              *
 601              * Rather than picking equiprobably from those twelve
 602              * positions, we'll pick equiprobably from the three
 603              * equivalence classes
 604              */
 605             switch (random_upto(rs, 3)) {
 606               case 0:
 607                 /* Remove a random corner piece. */
 608                 {
 609                     int dx, dy;
 610
 611                     dx = random_upto(rs, 2) * 2 - 1;   /* +1 or -1 */
 612                     dy = random_upto(rs, 2) * 2 - 1;   /* +1 or -1 */
 613                     if (random_upto(rs, 2))
 614                         dy *= 3;
 615                     else
 616                         dx *= 3;
 617                     grid[(3+dy)*w+(3+dx)] = GRID_HOLE;
 618                 }
 619                 break;
 620               case 1:
 621                 /* Remove a random piece two from the centre. */
 622                 {
 623                     int dx, dy;
 624                     dx = 2 * (random_upto(rs, 2) * 2 - 1);
 625                     if (random_upto(rs, 2))
 626                         dy = 0;
 627                     else
 628                         dy = dx, dx = 0;
 629                     grid[(3+dy)*w+(3+dx)] = GRID_HOLE;
 630                 }
 631                 break;
 632               default /* case 2 */:
 633                 /* Remove a random piece one from the centre. */
 634                 {
 635                     int dx, dy;
 636                     dx = random_upto(rs, 2) * 2 - 1;
 637                     if (random_upto(rs, 2))
 638                         dy = 0;
 639                     else
 640                         dy = dx, dx = 0;
 641                     grid[(3+dy)*w+(3+dx)] = GRID_HOLE;
 642                 }
 643                 break;
 644             }
 645         }
 646     }
 647
 648     /*
 649      * Encode a game description which is simply a long list of P
 650      * for peg, H for hole or O for obstacle.
 651      */
 652     ret = snewn(w*h+1, char);
 653     for (i = 0; i < w*h; i++)
 654         ret[i] = (grid[i] == GRID_PEG ? 'P' :
 655                   grid[i] == GRID_HOLE ? 'H' : 'O');
 656     ret[w*h] = '\0';
 657
 658     sfree(grid);
 659
 660     return ret;
 661 }
 662
 663 static char *validate_desc(const game_params *params, const char *desc)
 664 {
 665     int len = params->w * params->h;
 666
 667     if (len != strlen(desc))
 668         return "Game description is wrong length";
 669     if (len != strspn(desc, "PHO"))
 670         return "Invalid character in game description";
 671
 672     return NULL;
 673 }
 674
 675 static game_state *new_game(midend *me, const game_params *params,
 676                             const char *desc)
 677 {
 678     int w = params->w, h = params->h;
 679     game_state *state = snew(game_state);
 680     int i;
 681
 682     state->w = w;
 683     state->h = h;
 684     state->completed = 0;
 685     state->grid = snewn(w*h, unsigned char);
 686     for (i = 0; i < w*h; i++)
 687         state->grid[i] = (desc[i] == 'P' ? GRID_PEG :
 688                           desc[i] == 'H' ? GRID_HOLE : GRID_OBST);
 689
 690     return state;
 691 }
 692
 693 static game_state *dup_game(const game_state *state)
 694 {
 695     int w = state->w, h = state->h;
 696     game_state *ret = snew(game_state);
 697
 698     ret->w = state->w;
 699     ret->h = state->h;
 700     ret->completed = state->completed;
 701     ret->grid = snewn(w*h, unsigned char);
 702     memcpy(ret->grid, state->grid, w*h);
 703
 704     return ret;
 705 }
 706
 707 static void free_game(game_state *state)
 708 {
 709     sfree(state->grid);
 710     sfree(state);
 711 }
 712
 713 static char *solve_game(const game_state *state, const game_state *currstate,
 714                         const char *aux, char **error)
 715 {
 716     return NULL;
 717 }
 718
 719 static int game_can_format_as_text_now(const game_params *params)
 720 {
 721     return TRUE;
 722 }
 723
 724 static char *game_text_format(const game_state *state)
 725 {
 726     int w = state->w, h = state->h;
 727     int x, y;
 728     char *ret;
 729
 730     ret = snewn((w+1)*h + 1, char);
 731
 732     for (y = 0; y < h; y++) {
 733         for (x = 0; x < w; x++)
 734             ret[y*(w+1)+x] = (state->grid[y*w+x] == GRID_HOLE ? '-' :
 735                               state->grid[y*w+x] == GRID_PEG ? '*' : ' ');
 736         ret[y*(w+1)+w] = '\n';
 737     }
 738     ret[h*(w+1)] = '\0';
 739
 740     return ret;
 741 }
 742
 743 struct game_ui {
 744     int dragging;                      /* boolean: is a drag in progress? */
 745     int sx, sy;                        /* grid coords of drag start cell */
 746     int dx, dy;                        /* pixel coords of current drag posn */
 747     int cur_x, cur_y, cur_visible, cur_jumping;
 748 };
 749
 750 static game_ui *new_ui(const game_state *state)
 751 {
 752     game_ui *ui = snew(game_ui);
 753     int x, y, v;
 754
 755     ui->sx = ui->sy = ui->dx = ui->dy = 0;
 756     ui->dragging = FALSE;
 757     ui->cur_visible = ui->cur_jumping = 0;
 758
 759     /* make sure we start the cursor somewhere on the grid. */
 760     for (x = 0; x < state->w; x++) {
 761         for (y = 0; y < state->h; y++) {
 762             v = state->grid[y*state->w+x];
 763             if (v == GRID_PEG || v == GRID_HOLE) {
 764                 ui->cur_x = x; ui->cur_y = y;
 765                 goto found;
 766             }
 767         }
 768     }
 769     assert(!"new_ui found nowhere for cursor");
 770 found:
 771
 772     return ui;
 773 }
 774
 775 static void free_ui(game_ui *ui)
 776 {
 777     sfree(ui);
 778 }
 779
 780 static char *encode_ui(const game_ui *ui)
 781 {
 782     return NULL;
 783 }
 784
 785 static void decode_ui(game_ui *ui, const char *encoding)
 786 {
 787 }
 788
 789 static void game_changed_state(game_ui *ui, const game_state *oldstate,
 790                                const game_state *newstate)
 791 {
 792     /*
 793      * Cancel a drag, in case the source square has become
 794      * unoccupied.
 795      */
 796     ui->dragging = FALSE;
 797 }
 798
 799 #define PREFERRED_TILE_SIZE 33
 800 #define TILESIZE (ds->tilesize)
 801 #define BORDER (TILESIZE / 2)
 802
 803 #define HIGHLIGHT_WIDTH (TILESIZE / 16)
 804
 805 #define COORD(x)     ( BORDER + (x) * TILESIZE )
 806 #define FROMCOORD(x) ( ((x) + TILESIZE - BORDER) / TILESIZE - 1 )
 807
 808 struct game_drawstate {
 809     int tilesize;
 810     blitter *drag_background;
 811     int dragging, dragx, dragy;
 812     int w, h;
 813     unsigned char *grid;
 814     int started;
 815     int bgcolour;
 816 };
 817
 818 static char *interpret_move(const game_state *state, game_ui *ui,
 819                             const game_drawstate *ds,
 820                             int x, int y, int button)
 821 {
 822     int w = state->w, h = state->h;
 823     char buf[80];
 824
 825     if (button == LEFT_BUTTON) {
 826         int tx, ty;
 827
 828         /*
 829          * Left button down: we attempt to start a drag.
 830          */
 831
 832         /*
 833          * There certainly shouldn't be a current drag in progress,
 834          * unless the midend failed to send us button events in
 835          * order; it has a responsibility to always get that right,
 836          * so we can legitimately punish it by failing an
 837          * assertion.
 838          */
 839         assert(!ui->dragging);
 840
 841         tx = FROMCOORD(x);
 842         ty = FROMCOORD(y);
 843         if (tx >= 0 && tx < w && ty >= 0 && ty < h &&
 844             state->grid[ty*w+tx] == GRID_PEG) {
 845             ui->dragging = TRUE;
 846             ui->sx = tx;
 847             ui->sy = ty;
 848             ui->dx = x;
 849             ui->dy = y;
 850             ui->cur_visible = ui->cur_jumping = 0;
 851             return "";                 /* ui modified */
 852         }
 853     } else if (button == LEFT_DRAG && ui->dragging) {
 854         /*
 855          * Mouse moved; just move the peg being dragged.
 856          */
 857         ui->dx = x;
 858         ui->dy = y;
 859         return "";                     /* ui modified */
 860     } else if (button == LEFT_RELEASE && ui->dragging) {
 861         int tx, ty, dx, dy;
 862
 863         /*
 864          * Button released. Identify the target square of the drag,
 865          * see if it represents a valid move, and if so make it.
 866          */
 867         ui->dragging = FALSE;          /* cancel the drag no matter what */
 868         tx = FROMCOORD(x);
 869         ty = FROMCOORD(y);
 870         if (tx < 0 || tx >= w || ty < 0 || ty >= h)
 871             return "";                 /* target out of range */
 872         dx = tx - ui->sx;
 873         dy = ty - ui->sy;
 874         if (max(abs(dx),abs(dy)) != 2 || min(abs(dx),abs(dy)) != 0)
 875             return "";                 /* move length was wrong */
 876         dx /= 2;
 877         dy /= 2;
 878
 879         if (state->grid[ty*w+tx] != GRID_HOLE ||
 880             state->grid[(ty-dy)*w+(tx-dx)] != GRID_PEG ||
 881             state->grid[ui->sy*w+ui->sx] != GRID_PEG)
 882             return "";                 /* grid contents were invalid */
 883
 884         /*
 885          * We have a valid move. Encode it simply as source and
 886          * destination coordinate pairs.
 887          */
 888         sprintf(buf, "%d,%d-%d,%d", ui->sx, ui->sy, tx, ty);
 889         return dupstr(buf);
 890     } else if (IS_CURSOR_MOVE(button)) {
 891         if (!ui->cur_jumping) {
 892             /* Not jumping; move cursor as usual, making sure we don't
 893              * leave the gameboard (which may be an irregular shape) */
 894             int cx = ui->cur_x, cy = ui->cur_y;
 895             move_cursor(button, &cx, &cy, w, h, 0);
 896             ui->cur_visible = 1;
 897             if (state->grid[cy*w+cx] == GRID_HOLE ||
 898                 state->grid[cy*w+cx] == GRID_PEG) {
 899                 ui->cur_x = cx;
 900                 ui->cur_y = cy;
 901             }
 902             return "";
 903         } else {
 904             int dx, dy, mx, my, jx, jy;
 905
 906             /* We're jumping; if the requested direction has a hole, and
 907              * there's a peg in the way, */
 908             assert(state->grid[ui->cur_y*w+ui->cur_x] == GRID_PEG);
 909             dx = (button == CURSOR_RIGHT) ? 1 : (button == CURSOR_LEFT) ? -1 : 0;
 910             dy = (button == CURSOR_DOWN) ? 1 : (button == CURSOR_UP) ? -1 : 0;
 911
 912             mx = ui->cur_x+dx; my = ui->cur_y+dy;
 913             jx = mx+dx; jy = my+dy;
 914
 915             ui->cur_jumping = 0; /* reset, whatever. */
 916             if (jx >= 0 && jy >= 0 && jx < w && jy < h &&
 917                 state->grid[my*w+mx] == GRID_PEG &&
 918                 state->grid[jy*w+jx] == GRID_HOLE) {
 919                 /* Move cursor to the jumped-to location (this felt more
 920                  * natural while playtesting) */
 921                 sprintf(buf, "%d,%d-%d,%d", ui->cur_x, ui->cur_y, jx, jy);
 922                 ui->cur_x = jx; ui->cur_y = jy;
 923                 return dupstr(buf);
 924             }
 925             return "";
 926         }
 927     } else if (IS_CURSOR_SELECT(button)) {
 928         if (!ui->cur_visible) {
 929             ui->cur_visible = 1;
 930             return "";
 931         }
 932         if (ui->cur_jumping) {
 933             ui->cur_jumping = 0;
 934             return "";
 935         }
 936         if (state->grid[ui->cur_y*w+ui->cur_x] == GRID_PEG) {
 937             /* cursor is on peg: next arrow-move wil jump. */
 938             ui->cur_jumping = 1;
 939             return "";
 940         }
 941         return NULL;
 942     }
 943
 944     return NULL;
 945 }
 946
 947 static game_state *execute_move(const game_state *state, const char *move)
 948 {
 949     int w = state->w, h = state->h;
 950     int sx, sy, tx, ty;
 951     game_state *ret;
 952
 953     if (sscanf(move, "%d,%d-%d,%d", &sx, &sy, &tx, &ty) == 4) {
 954         int mx, my, dx, dy;
 955
 956         if (sx < 0 || sx >= w || sy < 0 || sy >= h)
 957             return NULL;               /* source out of range */
 958         if (tx < 0 || tx >= w || ty < 0 || ty >= h)
 959             return NULL;               /* target out of range */
 960
 961         dx = tx - sx;
 962         dy = ty - sy;
 963         if (max(abs(dx),abs(dy)) != 2 || min(abs(dx),abs(dy)) != 0)
 964             return NULL;               /* move length was wrong */
 965         mx = sx + dx/2;
 966         my = sy + dy/2;
 967
 968         if (state->grid[sy*w+sx] != GRID_PEG ||
 969             state->grid[my*w+mx] != GRID_PEG ||
 970             state->grid[ty*w+tx] != GRID_HOLE)
 971             return NULL;               /* grid contents were invalid */
 972
 973         ret = dup_game(state);
 974         ret->grid[sy*w+sx] = GRID_HOLE;
 975         ret->grid[my*w+mx] = GRID_HOLE;
 976         ret->grid[ty*w+tx] = GRID_PEG;
 977
 978         /*
 979          * Opinion varies on whether getting to a single peg counts as
 980          * completing the game, or whether that peg has to be at a
 981          * specific location (central in the classic cross game, for
 982          * instance). For now we take the former, rather lax position.
 983          */
 984         if (!ret->completed) {
 985             int count = 0, i;
 986             for (i = 0; i < w*h; i++)
 987                 if (ret->grid[i] == GRID_PEG)
 988                     count++;
 989             if (count == 1)
 990                 ret->completed = 1;
 991         }
 992
 993         return ret;
 994     }
 995     return NULL;
 996 }
 997
 998 /* ----------------------------------------------------------------------
 999  * Drawing routines.
1000  */
1001
1002 static void game_compute_size(const game_params *params, int tilesize,
1003                               int *x, int *y)
1004 {
1005     /* Ick: fake up `ds->tilesize' for macro expansion purposes */
1006     struct { int tilesize; } ads, *ds = &ads;
1007     ads.tilesize = tilesize;
1008
1009     *x = TILESIZE * params->w + 2 * BORDER;
1010     *y = TILESIZE * params->h + 2 * BORDER;
1011 }
1012
1013 static void game_set_size(drawing *dr, game_drawstate *ds,
1014                           const game_params *params, int tilesize)
1015 {
1016     ds->tilesize = tilesize;
1017
1018     assert(TILESIZE > 0);
1019
1020     assert(!ds->drag_background);      /* set_size is never called twice */
1021     ds->drag_background = blitter_new(dr, TILESIZE, TILESIZE);
1022 }
1023
1024 static float *game_colours(frontend *fe, int *ncolours)
1025 {
1026     float *ret = snewn(3 * NCOLOURS, float);
1027
1028     game_mkhighlight(fe, ret, COL_BACKGROUND, COL_HIGHLIGHT, COL_LOWLIGHT);
1029
1030     ret[COL_PEG * 3 + 0] = 0.0F;
1031     ret[COL_PEG * 3 + 1] = 0.0F;
1032     ret[COL_PEG * 3 + 2] = 1.0F;
1033
1034     ret[COL_CURSOR * 3 + 0] = 0.5F;
1035     ret[COL_CURSOR * 3 + 1] = 0.5F;
1036     ret[COL_CURSOR * 3 + 2] = 1.0F;
1037
1038     *ncolours = NCOLOURS;
1039     return ret;
1040 }
1041
1042 static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state)
1043 {
1044     int w = state->w, h = state->h;
1045     struct game_drawstate *ds = snew(struct game_drawstate);
1046
1047     ds->tilesize = 0;                  /* not decided yet */
1048
1049     /* We can't allocate the blitter rectangle for the drag background
1050      * until we know what size to make it. */
1051     ds->drag_background = NULL;
1052     ds->dragging = FALSE;
1053
1054     ds->w = w;
1055     ds->h = h;
1056     ds->grid = snewn(w*h, unsigned char);
1057     memset(ds->grid, 255, w*h);
1058
1059     ds->started = FALSE;
1060     ds->bgcolour = -1;
1061
1062     return ds;
1063 }
1064
1065 static void game_free_drawstate(drawing *dr, game_drawstate *ds)
1066 {
1067     if (ds->drag_background)
1068         blitter_free(dr, ds->drag_background);
1069     sfree(ds->grid);
1070     sfree(ds);
1071 }
1072
1073 static void draw_tile(drawing *dr, game_drawstate *ds,
1074                       int x, int y, int v, int bgcolour)
1075 {
1076     int cursor = 0, jumping = 0, bg;
1077
1078     if (bgcolour >= 0) {
1079         draw_rect(dr, x, y, TILESIZE, TILESIZE, bgcolour);
1080     }
1081     if (v >= GRID_JUMPING) {
1082         jumping = 1; v -= GRID_JUMPING;
1083     }
1084     if (v >= GRID_CURSOR) {
1085         cursor = 1; v -= GRID_CURSOR;
1086     }
1087
1088     if (v == GRID_HOLE) {
1089         bg = cursor ? COL_HIGHLIGHT : COL_LOWLIGHT;
1090         assert(!jumping); /* can't jump from a hole! */
1091         draw_circle(dr, x+TILESIZE/2, y+TILESIZE/2, TILESIZE/4,
1092                     bg, bg);
1093     } else if (v == GRID_PEG) {
1094         bg = (cursor || jumping) ? COL_CURSOR : COL_PEG;
1095         draw_circle(dr, x+TILESIZE/2, y+TILESIZE/2, TILESIZE/3,
1096                     bg, bg);
1097         bg = (!cursor || jumping) ? COL_PEG : COL_CURSOR;
1098         draw_circle(dr, x+TILESIZE/2, y+TILESIZE/2, TILESIZE/4,
1099                     bg, bg);
1100     }
1101
1102     draw_update(dr, x, y, TILESIZE, TILESIZE);
1103 }
1104
1105 static void game_redraw(drawing *dr, game_drawstate *ds,
1106                         const game_state *oldstate, const game_state *state,
1107                         int dir, const game_ui *ui,
1108                         float animtime, float flashtime)
1109 {
1110     int w = state->w, h = state->h;
1111     int x, y;
1112     int bgcolour;
1113
1114     if (flashtime > 0) {
1115         int frame = (int)(flashtime / FLASH_FRAME);
1116         bgcolour = (frame % 2 ? COL_LOWLIGHT : COL_HIGHLIGHT);
1117     } else
1118         bgcolour = COL_BACKGROUND;
1119
1120     /*
1121      * Erase the sprite currently being dragged, if any.
1122      */
1123     if (ds->dragging) {
1124         assert(ds->drag_background);
1125         blitter_load(dr, ds->drag_background, ds->dragx, ds->dragy);
1126         draw_update(dr, ds->dragx, ds->dragy, TILESIZE, TILESIZE);
1127         ds->dragging = FALSE;
1128     }
1129
1130     if (!ds->started) {
1131         draw_rect(dr, 0, 0,
1132                   TILESIZE * state->w + 2 * BORDER,
1133                   TILESIZE * state->h + 2 * BORDER, COL_BACKGROUND);
1134
1135         /*
1136          * Draw relief marks around all the squares that aren't
1137          * GRID_OBST.
1138          */
1139         for (y = 0; y < h; y++)
1140             for (x = 0; x < w; x++)
1141                 if (state->grid[y*w+x] != GRID_OBST) {
1142                     /*
1143                      * First pass: draw the full relief square.
1144                      */
1145                     int coords[6];
1146                     coords[0] = COORD(x+1) + HIGHLIGHT_WIDTH - 1;
1147                     coords[1] = COORD(y) - HIGHLIGHT_WIDTH;
1148                     coords[2] = COORD(x) - HIGHLIGHT_WIDTH;
1149                     coords[3] = COORD(y+1) + HIGHLIGHT_WIDTH - 1;
1150                     coords[4] = COORD(x) - HIGHLIGHT_WIDTH;
1151                     coords[5] = COORD(y) - HIGHLIGHT_WIDTH;
1152                     draw_polygon(dr, coords, 3, COL_HIGHLIGHT, COL_HIGHLIGHT);
1153                     coords[4] = COORD(x+1) + HIGHLIGHT_WIDTH - 1;
1154                     coords[5] = COORD(y+1) + HIGHLIGHT_WIDTH - 1;
1155                     draw_polygon(dr, coords, 3, COL_LOWLIGHT, COL_LOWLIGHT);
1156                 }
1157         for (y = 0; y < h; y++)
1158             for (x = 0; x < w; x++)
1159                 if (state->grid[y*w+x] != GRID_OBST) {
1160                     /*
1161                      * Second pass: draw everything but the two
1162                      * diagonal corners.
1163                      */
1164                     draw_rect(dr, COORD(x) - HIGHLIGHT_WIDTH,
1165                               COORD(y) - HIGHLIGHT_WIDTH,
1166                               TILESIZE + HIGHLIGHT_WIDTH,
1167                               TILESIZE + HIGHLIGHT_WIDTH, COL_HIGHLIGHT);
1168                     draw_rect(dr, COORD(x),
1169                               COORD(y),
1170                               TILESIZE + HIGHLIGHT_WIDTH,
1171                               TILESIZE + HIGHLIGHT_WIDTH, COL_LOWLIGHT);
1172                 }
1173         for (y = 0; y < h; y++)
1174             for (x = 0; x < w; x++)
1175                 if (state->grid[y*w+x] != GRID_OBST) {
1176                     /*
1177                      * Third pass: draw a trapezium on each edge.
1178                      */
1179                     int coords[8];
1180                     int dx, dy, s, sn, c;
1181
1182                     for (dx = 0; dx < 2; dx++) {
1183                         dy = 1 - dx;
1184                         for (s = 0; s < 2; s++) {
1185                             sn = 2*s - 1;
1186                             c = s ? COL_LOWLIGHT : COL_HIGHLIGHT;
1187
1188                             coords[0] = COORD(x) + (s*dx)*(TILESIZE-1);
1189                             coords[1] = COORD(y) + (s*dy)*(TILESIZE-1);
1190                             coords[2] = COORD(x) + (s*dx+dy)*(TILESIZE-1);
1191                             coords[3] = COORD(y) + (s*dy+dx)*(TILESIZE-1);
1192                             coords[4] = coords[2] - HIGHLIGHT_WIDTH * (dy-sn*dx);
1193                             coords[5] = coords[3] - HIGHLIGHT_WIDTH * (dx-sn*dy);
1194                             coords[6] = coords[0] + HIGHLIGHT_WIDTH * (dy+sn*dx);
1195                             coords[7] = coords[1] + HIGHLIGHT_WIDTH * (dx+sn*dy);
1196                             draw_polygon(dr, coords, 4, c, c);
1197                         }
1198                     }
1199                 }
1200         for (y = 0; y < h; y++)
1201             for (x = 0; x < w; x++)
1202                 if (state->grid[y*w+x] != GRID_OBST) {
1203                     /*
1204                      * Second pass: draw everything but the two
1205                      * diagonal corners.
1206                      */
1207                     draw_rect(dr, COORD(x),
1208                               COORD(y),
1209                               TILESIZE,
1210                               TILESIZE, COL_BACKGROUND);
1211                 }
1212
1213         ds->started = TRUE;
1214
1215         draw_update(dr, 0, 0,
1216                     TILESIZE * state->w + 2 * BORDER,
1217                     TILESIZE * state->h + 2 * BORDER);
1218     }
1219
1220     /*
1221      * Loop over the grid redrawing anything that looks as if it
1222      * needs it.
1223      */
1224     for (y = 0; y < h; y++)
1225         for (x = 0; x < w; x++) {
1226             int v;
1227
1228             v = state->grid[y*w+x];
1229             /*
1230              * Blank the source of a drag so it looks as if the
1231              * user picked the peg up physically.
1232              */
1233             if (ui->dragging && ui->sx == x && ui->sy == y && v == GRID_PEG)
1234                 v = GRID_HOLE;
1235
1236             if (ui->cur_visible && ui->cur_x == x && ui->cur_y == y)
1237                 v += ui->cur_jumping ? GRID_JUMPING : GRID_CURSOR;
1238
1239             if (v != GRID_OBST &&
1240                 (bgcolour != ds->bgcolour || /* always redraw when flashing */
1241                  v != ds->grid[y*w+x])) {
1242                 draw_tile(dr, ds, COORD(x), COORD(y), v, bgcolour);
1243                 ds->grid[y*w+x] = v;
1244             }
1245         }
1246
1247     /*
1248      * Draw the dragging sprite if any.
1249      */
1250     if (ui->dragging) {
1251         ds->dragging = TRUE;
1252         ds->dragx = ui->dx - TILESIZE/2;
1253         ds->dragy = ui->dy - TILESIZE/2;
1254         blitter_save(dr, ds->drag_background, ds->dragx, ds->dragy);
1255         draw_tile(dr, ds, ds->dragx, ds->dragy, GRID_PEG, -1);
1256     }
1257
1258     ds->bgcolour = bgcolour;
1259 }
1260
1261 static float game_anim_length(const game_state *oldstate,
1262                               const game_state *newstate, int dir, game_ui *ui)
1263 {
1264     return 0.0F;
1265 }
1266
1267 static float game_flash_length(const game_state *oldstate,
1268                                const game_state *newstate, int dir, game_ui *ui)
1269 {
1270     if (!oldstate->completed && newstate->completed)
1271         return 2 * FLASH_FRAME;
1272     else
1273         return 0.0F;
1274 }
1275
1276 static int game_status(const game_state *state)
1277 {
1278     /*
1279      * Dead-end situations are assumed to be rescuable by Undo, so we
1280      * don't bother to identify them and return -1.
1281      */
1282     return state->completed ? +1 : 0;
1283 }
1284
1285 static int game_timing_state(const game_state *state, game_ui *ui)
1286 {
1287     return TRUE;
1288 }
1289
1290 static void game_print_size(const game_params *params, float *x, float *y)
1291 {
1292 }
1293
1294 static void game_print(drawing *dr, const game_state *state, int tilesize)
1295 {
1296 }
1297
1298 #ifdef COMBINED
1299 #define thegame pegs
1300 #endif
1301
1302 const struct game thegame = {
1303     "Pegs", "games.pegs", "pegs",
1304     default_params,
1305     game_fetch_preset,
1306     decode_params,
1307     encode_params,
1308     free_params,
1309     dup_params,
1310     TRUE, game_configure, custom_params,
1311     validate_params,
1312     new_game_desc,
1313     validate_desc,
1314     new_game,
1315     dup_game,
1316     free_game,
1317     FALSE, solve_game,
1318     TRUE, game_can_format_as_text_now, game_text_format,
1319     new_ui,
1320     free_ui,
1321     encode_ui,
1322     decode_ui,
1323     game_changed_state,
1324     interpret_move,
1325     execute_move,
1326     PREFERRED_TILE_SIZE, game_compute_size, game_set_size,
1327     game_colours,
1328     game_new_drawstate,
1329     game_free_drawstate,
1330     game_redraw,
1331     game_anim_length,
1332     game_flash_length,
1333     game_status,
1334     FALSE, FALSE, game_print_size, game_print,
1335     FALSE,                             /* wants_statusbar */
1336     FALSE, game_timing_state,
1337     0,                                 /* flags */
1338 };
1339
1340 /* vim: set shiftwidth=4 tabstop=8: */