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