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