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(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(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(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(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(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(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(game_params *params, 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, game_params *params, char *desc)
 676 {
 677     int w = params->w, h = params->h;
 678     game_state *state = snew(game_state);
 679     int i;
 680
 681     state->w = w;
 682     state->h = h;
 683     state->completed = 0;
 684     state->grid = snewn(w*h, unsigned char);
 685     for (i = 0; i < w*h; i++)
 686         state->grid[i] = (desc[i] == 'P' ? GRID_PEG :
 687                           desc[i] == 'H' ? GRID_HOLE : GRID_OBST);
 688
 689     return state;
 690 }
 691
 692 static game_state *dup_game(game_state *state)
 693 {
 694     int w = state->w, h = state->h;
 695     game_state *ret = snew(game_state);
 696
 697     ret->w = state->w;
 698     ret->h = state->h;
 699     ret->completed = state->completed;
 700     ret->grid = snewn(w*h, unsigned char);
 701     memcpy(ret->grid, state->grid, w*h);
 702
 703     return ret;
 704 }
 705
 706 static void free_game(game_state *state)
 707 {
 708     sfree(state->grid);
 709     sfree(state);
 710 }
 711
 712 static char *solve_game(game_state *state, game_state *currstate,
 713                         char *aux, char **error)
 714 {
 715     return NULL;
 716 }
 717
 718 static int game_can_format_as_text_now(game_params *params)
 719 {
 720     return TRUE;
 721 }
 722
 723 static char *game_text_format(game_state *state)
 724 {
 725     int w = state->w, h = state->h;
 726     int x, y;
 727     char *ret;
 728
 729     ret = snewn((w+1)*h + 1, char);
 730
 731     for (y = 0; y < h; y++) {
 732         for (x = 0; x < w; x++)
 733             ret[y*(w+1)+x] = (state->grid[y*w+x] == GRID_HOLE ? '-' :
 734                               state->grid[y*w+x] == GRID_PEG ? '*' : ' ');
 735         ret[y*(w+1)+w] = '\n';
 736     }
 737     ret[h*(w+1)] = '\0';
 738
 739     return ret;
 740 }
 741
 742 struct game_ui {
 743     int dragging;                      /* boolean: is a drag in progress? */
 744     int sx, sy;                        /* grid coords of drag start cell */
 745     int dx, dy;                        /* pixel coords of current drag posn */
 746     int cur_x, cur_y, cur_visible, cur_jumping;
 747 };
 748
 749 static game_ui *new_ui(game_state *state)
 750 {
 751     game_ui *ui = snew(game_ui);
 752     int x, y, v;
 753
 754     ui->sx = ui->sy = ui->dx = ui->dy = 0;
 755     ui->dragging = FALSE;
 756     ui->cur_visible = ui->cur_jumping = 0;
 757
 758     /* make sure we start the cursor somewhere on the grid. */
 759     for (x = 0; x < state->w; x++) {
 760         for (y = 0; y < state->h; y++) {
 761             v = state->grid[y*state->w+x];
 762             if (v == GRID_PEG || v == GRID_HOLE) {
 763                 ui->cur_x = x; ui->cur_y = y;
 764                 goto found;
 765             }
 766         }
 767     }
 768     assert(!"new_ui found nowhere for cursor");
 769 found:
 770
 771     return ui;
 772 }
 773
 774 static void free_ui(game_ui *ui)
 775 {
 776     sfree(ui);
 777 }
 778
 779 static char *encode_ui(game_ui *ui)
 780 {
 781     return NULL;
 782 }
 783
 784 static void decode_ui(game_ui *ui, char *encoding)
 785 {
 786 }
 787
 788 static void game_changed_state(game_ui *ui, game_state *oldstate,
 789                                game_state *newstate)
 790 {
 791     /*
 792      * Cancel a drag, in case the source square has become
 793      * unoccupied.
 794      */
 795     ui->dragging = FALSE;
 796 }
 797
 798 #define PREFERRED_TILE_SIZE 33
 799 #define TILESIZE (ds->tilesize)
 800 #define BORDER (TILESIZE / 2)
 801
 802 #define HIGHLIGHT_WIDTH (TILESIZE / 16)
 803
 804 #define COORD(x)     ( BORDER + (x) * TILESIZE )
 805 #define FROMCOORD(x) ( ((x) + TILESIZE - BORDER) / TILESIZE - 1 )
 806
 807 struct game_drawstate {
 808     int tilesize;
 809     blitter *drag_background;
 810     int dragging, dragx, dragy;
 811     int w, h;
 812     unsigned char *grid;
 813     int started;
 814     int bgcolour;
 815 };
 816
 817 static char *interpret_move(game_state *state, game_ui *ui, const game_drawstate *ds,
 818                             int x, int y, int button)
 819 {
 820     int w = state->w, h = state->h;
 821     char buf[80];
 822
 823     if (button == LEFT_BUTTON) {
 824         int tx, ty;
 825
 826         /*
 827          * Left button down: we attempt to start a drag.
 828          */
 829
 830         /*
 831          * There certainly shouldn't be a current drag in progress,
 832          * unless the midend failed to send us button events in
 833          * order; it has a responsibility to always get that right,
 834          * so we can legitimately punish it by failing an
 835          * assertion.
 836          */
 837         assert(!ui->dragging);
 838
 839         tx = FROMCOORD(x);
 840         ty = FROMCOORD(y);
 841         if (tx >= 0 && tx < w && ty >= 0 && ty < h &&
 842             state->grid[ty*w+tx] == GRID_PEG) {
 843             ui->dragging = TRUE;
 844             ui->sx = tx;
 845             ui->sy = ty;
 846             ui->dx = x;
 847             ui->dy = y;
 848             ui->cur_visible = ui->cur_jumping = 0;
 849             return "";                 /* ui modified */
 850         }
 851     } else if (button == LEFT_DRAG && ui->dragging) {
 852         /*
 853          * Mouse moved; just move the peg being dragged.
 854          */
 855         ui->dx = x;
 856         ui->dy = y;
 857         return "";                     /* ui modified */
 858     } else if (button == LEFT_RELEASE && ui->dragging) {
 859         int tx, ty, dx, dy;
 860
 861         /*
 862          * Button released. Identify the target square of the drag,
 863          * see if it represents a valid move, and if so make it.
 864          */
 865         ui->dragging = FALSE;          /* cancel the drag no matter what */
 866         tx = FROMCOORD(x);
 867         ty = FROMCOORD(y);
 868         if (tx < 0 || tx >= w || ty < 0 || ty >= h)
 869             return "";                 /* target out of range */
 870         dx = tx - ui->sx;
 871         dy = ty - ui->sy;
 872         if (max(abs(dx),abs(dy)) != 2 || min(abs(dx),abs(dy)) != 0)
 873             return "";                 /* move length was wrong */
 874         dx /= 2;
 875         dy /= 2;
 876
 877         if (state->grid[ty*w+tx] != GRID_HOLE ||
 878             state->grid[(ty-dy)*w+(tx-dx)] != GRID_PEG ||
 879             state->grid[ui->sy*w+ui->sx] != GRID_PEG)
 880             return "";                 /* grid contents were invalid */
 881
 882         /*
 883          * We have a valid move. Encode it simply as source and
 884          * destination coordinate pairs.
 885          */
 886         sprintf(buf, "%d,%d-%d,%d", ui->sx, ui->sy, tx, ty);
 887         return dupstr(buf);
 888     } else if (IS_CURSOR_MOVE(button)) {
 889         if (!ui->cur_jumping) {
 890             /* Not jumping; move cursor as usual, making sure we don't
 891              * leave the gameboard (which may be an irregular shape) */
 892             int cx = ui->cur_x, cy = ui->cur_y;
 893             move_cursor(button, &cx, &cy, w, h, 0);
 894             ui->cur_visible = 1;
 895             if (state->grid[cy*w+cx] == GRID_HOLE ||
 896                 state->grid[cy*w+cx] == GRID_PEG) {
 897                 ui->cur_x = cx;
 898                 ui->cur_y = cy;
 899             }
 900             return "";
 901         } else {
 902             int dx, dy, mx, my, jx, jy;
 903
 904             /* We're jumping; if the requested direction has a hole, and
 905              * there's a peg in the way, */
 906             assert(state->grid[ui->cur_y*w+ui->cur_x] == GRID_PEG);
 907             dx = (button == CURSOR_RIGHT) ? 1 : (button == CURSOR_LEFT) ? -1 : 0;
 908             dy = (button == CURSOR_DOWN) ? 1 : (button == CURSOR_UP) ? -1 : 0;
 909
 910             mx = ui->cur_x+dx; my = ui->cur_y+dy;
 911             jx = mx+dx; jy = my+dy;
 912
 913             ui->cur_jumping = 0; /* reset, whatever. */
 914             if (jx >= 0 && jy >= 0 && jx < w && jy < h &&
 915                 state->grid[my*w+mx] == GRID_PEG &&
 916                 state->grid[jy*w+jx] == GRID_HOLE) {
 917                 /* Move cursor to the jumped-to location (this felt more
 918                  * natural while playtesting) */
 919                 sprintf(buf, "%d,%d-%d,%d", ui->cur_x, ui->cur_y, jx, jy);
 920                 ui->cur_x = jx; ui->cur_y = jy;
 921                 return dupstr(buf);
 922             }
 923             return "";
 924         }
 925     } else if (IS_CURSOR_SELECT(button)) {
 926         if (!ui->cur_visible) {
 927             ui->cur_visible = 1;
 928             return "";
 929         }
 930         if (ui->cur_jumping) {
 931             ui->cur_jumping = 0;
 932             return "";
 933         }
 934         if (state->grid[ui->cur_y*w+ui->cur_x] == GRID_PEG) {
 935             /* cursor is on peg: next arrow-move wil jump. */
 936             ui->cur_jumping = 1;
 937             return "";
 938         }
 939         return NULL;
 940     }
 941
 942     return NULL;
 943 }
 944
 945 static game_state *execute_move(game_state *state, char *move)
 946 {
 947     int w = state->w, h = state->h;
 948     int sx, sy, tx, ty;
 949     game_state *ret;
 950
 951     if (sscanf(move, "%d,%d-%d,%d", &sx, &sy, &tx, &ty) == 4) {
 952         int mx, my, dx, dy;
 953
 954         if (sx < 0 || sx >= w || sy < 0 || sy >= h)
 955             return NULL;               /* source out of range */
 956         if (tx < 0 || tx >= w || ty < 0 || ty >= h)
 957             return NULL;               /* target out of range */
 958
 959         dx = tx - sx;
 960         dy = ty - sy;
 961         if (max(abs(dx),abs(dy)) != 2 || min(abs(dx),abs(dy)) != 0)
 962             return NULL;               /* move length was wrong */
 963         mx = sx + dx/2;
 964         my = sy + dy/2;
 965
 966         if (state->grid[sy*w+sx] != GRID_PEG ||
 967             state->grid[my*w+mx] != GRID_PEG ||
 968             state->grid[ty*w+tx] != GRID_HOLE)
 969             return NULL;               /* grid contents were invalid */
 970
 971         ret = dup_game(state);
 972         ret->grid[sy*w+sx] = GRID_HOLE;
 973         ret->grid[my*w+mx] = GRID_HOLE;
 974         ret->grid[ty*w+tx] = GRID_PEG;
 975
 976         /*
 977          * Opinion varies on whether getting to a single peg counts as
 978          * completing the game, or whether that peg has to be at a
 979          * specific location (central in the classic cross game, for
 980          * instance). For now we take the former, rather lax position.
 981          */
 982         if (!ret->completed) {
 983             int count = 0, i;
 984             for (i = 0; i < w*h; i++)
 985                 if (ret->grid[i] == GRID_PEG)
 986                     count++;
 987             if (count == 1)
 988                 ret->completed = 1;
 989         }
 990
 991         return ret;
 992     }
 993     return NULL;
 994 }
 995
 996 /* ----------------------------------------------------------------------
 997  * Drawing routines.
 998  */
 999
1000 static void game_compute_size(game_params *params, int tilesize,
1001                               int *x, int *y)
1002 {
1003     /* Ick: fake up `ds->tilesize' for macro expansion purposes */
1004     struct { int tilesize; } ads, *ds = &ads;
1005     ads.tilesize = tilesize;
1006
1007     *x = TILESIZE * params->w + 2 * BORDER;
1008     *y = TILESIZE * params->h + 2 * BORDER;
1009 }
1010
1011 static void game_set_size(drawing *dr, game_drawstate *ds,
1012                           game_params *params, int tilesize)
1013 {
1014     ds->tilesize = tilesize;
1015
1016     assert(TILESIZE > 0);
1017
1018     assert(!ds->drag_background);      /* set_size is never called twice */
1019     ds->drag_background = blitter_new(dr, TILESIZE, TILESIZE);
1020 }
1021
1022 static float *game_colours(frontend *fe, int *ncolours)
1023 {
1024     float *ret = snewn(3 * NCOLOURS, float);
1025
1026     game_mkhighlight(fe, ret, COL_BACKGROUND, COL_HIGHLIGHT, COL_LOWLIGHT);
1027
1028     ret[COL_PEG * 3 + 0] = 0.0F;
1029     ret[COL_PEG * 3 + 1] = 0.0F;
1030     ret[COL_PEG * 3 + 2] = 1.0F;
1031
1032     ret[COL_CURSOR * 3 + 0] = 0.5F;
1033     ret[COL_CURSOR * 3 + 1] = 0.5F;
1034     ret[COL_CURSOR * 3 + 2] = 1.0F;
1035
1036     *ncolours = NCOLOURS;
1037     return ret;
1038 }
1039
1040 static game_drawstate *game_new_drawstate(drawing *dr, game_state *state)
1041 {
1042     int w = state->w, h = state->h;
1043     struct game_drawstate *ds = snew(struct game_drawstate);
1044
1045     ds->tilesize = 0;                  /* not decided yet */
1046
1047     /* We can't allocate the blitter rectangle for the drag background
1048      * until we know what size to make it. */
1049     ds->drag_background = NULL;
1050     ds->dragging = FALSE;
1051
1052     ds->w = w;
1053     ds->h = h;
1054     ds->grid = snewn(w*h, unsigned char);
1055     memset(ds->grid, 255, w*h);
1056
1057     ds->started = FALSE;
1058     ds->bgcolour = -1;
1059
1060     return ds;
1061 }
1062
1063 static void game_free_drawstate(drawing *dr, game_drawstate *ds)
1064 {
1065     if (ds->drag_background)
1066         blitter_free(dr, ds->drag_background);
1067     sfree(ds->grid);
1068     sfree(ds);
1069 }
1070
1071 static void draw_tile(drawing *dr, game_drawstate *ds,
1072                       int x, int y, int v, int bgcolour)
1073 {
1074     int cursor = 0, jumping = 0, bg;
1075
1076     if (bgcolour >= 0) {
1077         draw_rect(dr, x, y, TILESIZE, TILESIZE, bgcolour);
1078     }
1079     if (v >= GRID_JUMPING) {
1080         jumping = 1; v -= GRID_JUMPING;
1081     }
1082     if (v >= GRID_CURSOR) {
1083         cursor = 1; v -= GRID_CURSOR;
1084     }
1085
1086     if (v == GRID_HOLE) {
1087         bg = cursor ? COL_HIGHLIGHT : COL_LOWLIGHT;
1088         assert(!jumping); /* can't jump from a hole! */
1089         draw_circle(dr, x+TILESIZE/2, y+TILESIZE/2, TILESIZE/4,
1090                     bg, bg);
1091     } else if (v == GRID_PEG) {
1092         bg = (cursor || jumping) ? COL_CURSOR : COL_PEG;
1093         draw_circle(dr, x+TILESIZE/2, y+TILESIZE/2, TILESIZE/3,
1094                     bg, bg);
1095         bg = (!cursor || jumping) ? COL_PEG : COL_CURSOR;
1096         draw_circle(dr, x+TILESIZE/2, y+TILESIZE/2, TILESIZE/4,
1097                     bg, bg);
1098     }
1099
1100     draw_update(dr, x, y, TILESIZE, TILESIZE);
1101 }
1102
1103 static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate,
1104                         game_state *state, int dir, game_ui *ui,
1105                         float animtime, float flashtime)
1106 {
1107     int w = state->w, h = state->h;
1108     int x, y;
1109     int bgcolour;
1110
1111     if (flashtime > 0) {
1112         int frame = (int)(flashtime / FLASH_FRAME);
1113         bgcolour = (frame % 2 ? COL_LOWLIGHT : COL_HIGHLIGHT);
1114     } else
1115         bgcolour = COL_BACKGROUND;
1116
1117     /*
1118      * Erase the sprite currently being dragged, if any.
1119      */
1120     if (ds->dragging) {
1121         assert(ds->drag_background);
1122         blitter_load(dr, ds->drag_background, ds->dragx, ds->dragy);
1123         draw_update(dr, ds->dragx, ds->dragy, TILESIZE, TILESIZE);
1124         ds->dragging = FALSE;
1125     }
1126
1127     if (!ds->started) {
1128         draw_rect(dr, 0, 0,
1129                   TILESIZE * state->w + 2 * BORDER,
1130                   TILESIZE * state->h + 2 * BORDER, COL_BACKGROUND);
1131
1132         /*
1133          * Draw relief marks around all the squares that aren't
1134          * GRID_OBST.
1135          */
1136         for (y = 0; y < h; y++)
1137             for (x = 0; x < w; x++)
1138                 if (state->grid[y*w+x] != GRID_OBST) {
1139                     /*
1140                      * First pass: draw the full relief square.
1141                      */
1142                     int coords[6];
1143                     coords[0] = COORD(x+1) + HIGHLIGHT_WIDTH - 1;
1144                     coords[1] = COORD(y) - HIGHLIGHT_WIDTH;
1145                     coords[2] = COORD(x) - HIGHLIGHT_WIDTH;
1146                     coords[3] = COORD(y+1) + HIGHLIGHT_WIDTH - 1;
1147                     coords[4] = COORD(x) - HIGHLIGHT_WIDTH;
1148                     coords[5] = COORD(y) - HIGHLIGHT_WIDTH;
1149                     draw_polygon(dr, coords, 3, COL_HIGHLIGHT, COL_HIGHLIGHT);
1150                     coords[4] = COORD(x+1) + HIGHLIGHT_WIDTH - 1;
1151                     coords[5] = COORD(y+1) + HIGHLIGHT_WIDTH - 1;
1152                     draw_polygon(dr, coords, 3, COL_LOWLIGHT, COL_LOWLIGHT);
1153                 }
1154         for (y = 0; y < h; y++)
1155             for (x = 0; x < w; x++)
1156                 if (state->grid[y*w+x] != GRID_OBST) {
1157                     /*
1158                      * Second pass: draw everything but the two
1159                      * diagonal corners.
1160                      */
1161                     draw_rect(dr, COORD(x) - HIGHLIGHT_WIDTH,
1162                               COORD(y) - HIGHLIGHT_WIDTH,
1163                               TILESIZE + HIGHLIGHT_WIDTH,
1164                               TILESIZE + HIGHLIGHT_WIDTH, COL_HIGHLIGHT);
1165                     draw_rect(dr, COORD(x),
1166                               COORD(y),
1167                               TILESIZE + HIGHLIGHT_WIDTH,
1168                               TILESIZE + HIGHLIGHT_WIDTH, COL_LOWLIGHT);
1169                 }
1170         for (y = 0; y < h; y++)
1171             for (x = 0; x < w; x++)
1172                 if (state->grid[y*w+x] != GRID_OBST) {
1173                     /*
1174                      * Third pass: draw a trapezium on each edge.
1175                      */
1176                     int coords[8];
1177                     int dx, dy, s, sn, c;
1178
1179                     for (dx = 0; dx < 2; dx++) {
1180                         dy = 1 - dx;
1181                         for (s = 0; s < 2; s++) {
1182                             sn = 2*s - 1;
1183                             c = s ? COL_LOWLIGHT : COL_HIGHLIGHT;
1184
1185                             coords[0] = COORD(x) + (s*dx)*(TILESIZE-1);
1186                             coords[1] = COORD(y) + (s*dy)*(TILESIZE-1);
1187                             coords[2] = COORD(x) + (s*dx+dy)*(TILESIZE-1);
1188                             coords[3] = COORD(y) + (s*dy+dx)*(TILESIZE-1);
1189                             coords[4] = coords[2] - HIGHLIGHT_WIDTH * (dy-sn*dx);
1190                             coords[5] = coords[3] - HIGHLIGHT_WIDTH * (dx-sn*dy);
1191                             coords[6] = coords[0] + HIGHLIGHT_WIDTH * (dy+sn*dx);
1192                             coords[7] = coords[1] + HIGHLIGHT_WIDTH * (dx+sn*dy);
1193                             draw_polygon(dr, coords, 4, c, c);
1194                         }
1195                     }
1196                 }
1197         for (y = 0; y < h; y++)
1198             for (x = 0; x < w; x++)
1199                 if (state->grid[y*w+x] != GRID_OBST) {
1200                     /*
1201                      * Second pass: draw everything but the two
1202                      * diagonal corners.
1203                      */
1204                     draw_rect(dr, COORD(x),
1205                               COORD(y),
1206                               TILESIZE,
1207                               TILESIZE, COL_BACKGROUND);
1208                 }
1209
1210         ds->started = TRUE;
1211
1212         draw_update(dr, 0, 0,
1213                     TILESIZE * state->w + 2 * BORDER,
1214                     TILESIZE * state->h + 2 * BORDER);
1215     }
1216
1217     /*
1218      * Loop over the grid redrawing anything that looks as if it
1219      * needs it.
1220      */
1221     for (y = 0; y < h; y++)
1222         for (x = 0; x < w; x++) {
1223             int v;
1224
1225             v = state->grid[y*w+x];
1226             /*
1227              * Blank the source of a drag so it looks as if the
1228              * user picked the peg up physically.
1229              */
1230             if (ui->dragging && ui->sx == x && ui->sy == y && v == GRID_PEG)
1231                 v = GRID_HOLE;
1232
1233             if (ui->cur_visible && ui->cur_x == x && ui->cur_y == y)
1234                 v += ui->cur_jumping ? GRID_JUMPING : GRID_CURSOR;
1235
1236             if (v != GRID_OBST &&
1237                 (bgcolour != ds->bgcolour || /* always redraw when flashing */
1238                  v != ds->grid[y*w+x])) {
1239                 draw_tile(dr, ds, COORD(x), COORD(y), v, bgcolour);
1240                 ds->grid[y*w+x] = v;
1241             }
1242         }
1243
1244     /*
1245      * Draw the dragging sprite if any.
1246      */
1247     if (ui->dragging) {
1248         ds->dragging = TRUE;
1249         ds->dragx = ui->dx - TILESIZE/2;
1250         ds->dragy = ui->dy - TILESIZE/2;
1251         blitter_save(dr, ds->drag_background, ds->dragx, ds->dragy);
1252         draw_tile(dr, ds, ds->dragx, ds->dragy, GRID_PEG, -1);
1253     }
1254
1255     ds->bgcolour = bgcolour;
1256 }
1257
1258 static float game_anim_length(game_state *oldstate, game_state *newstate,
1259                               int dir, game_ui *ui)
1260 {
1261     return 0.0F;
1262 }
1263
1264 static float game_flash_length(game_state *oldstate, game_state *newstate,
1265                                int dir, game_ui *ui)
1266 {
1267     if (!oldstate->completed && newstate->completed)
1268         return 2 * FLASH_FRAME;
1269     else
1270         return 0.0F;
1271 }
1272
1273 static int game_status(game_state *state)
1274 {
1275     /*
1276      * Dead-end situations are assumed to be rescuable by Undo, so we
1277      * don't bother to identify them and return -1.
1278      */
1279     return state->completed ? +1 : 0;
1280 }
1281
1282 static int game_timing_state(game_state *state, game_ui *ui)
1283 {
1284     return TRUE;
1285 }
1286
1287 static void game_print_size(game_params *params, float *x, float *y)
1288 {
1289 }
1290
1291 static void game_print(drawing *dr, game_state *state, int tilesize)
1292 {
1293 }
1294
1295 #ifdef COMBINED
1296 #define thegame pegs
1297 #endif
1298
1299 const struct game thegame = {
1300     "Pegs", "games.pegs", "pegs",
1301     default_params,
1302     game_fetch_preset,
1303     decode_params,
1304     encode_params,
1305     free_params,
1306     dup_params,
1307     TRUE, game_configure, custom_params,
1308     validate_params,
1309     new_game_desc,
1310     validate_desc,
1311     new_game,
1312     dup_game,
1313     free_game,
1314     FALSE, solve_game,
1315     TRUE, game_can_format_as_text_now, game_text_format,
1316     new_ui,
1317     free_ui,
1318     encode_ui,
1319     decode_ui,
1320     game_changed_state,
1321     interpret_move,
1322     execute_move,
1323     PREFERRED_TILE_SIZE, game_compute_size, game_set_size,
1324     game_colours,
1325     game_new_drawstate,
1326     game_free_drawstate,
1327     game_redraw,
1328     game_anim_length,
1329     game_flash_length,
1330     game_status,
1331     FALSE, FALSE, game_print_size, game_print,
1332     FALSE,                             /* wants_statusbar */
1333     FALSE, game_timing_state,
1334     0,                                 /* flags */
1335 };
1336
1337 /* vim: set shiftwidth=4 tabstop=8: */