git.hungrycats.org Git - xscreensaver/blob - hacks/jigsaw.c

   1 /* xscreensaver, Copyright (c) 1997-2006 Jamie Zawinski <jwz@jwz.org>
   2  *
   3  * Permission to use, copy, modify, distribute, and sell this software and its
   4  * documentation for any purpose is hereby granted without fee, provided that
   5  * the above copyright notice appear in all copies and that both that
   6  * copyright notice and this permission notice appear in supporting
   7  * documentation.  No representations are made about the suitability of this
   8  * software for any purpose.  It is provided "as is" without express or
   9  * implied warranty.
  10  */
  11
  12 /*
  13   TODO:
  14
  15     =  Rather than just flickering the pieces before swapping them,
  16        show them lifting up and moving to their new positions.
  17        The path on which they move shouldn't be a straight line;
  18        try to avoid having them cross each other by moving them in
  19        oppositely-positioned arcs.
  20
  21     =  Rotate the pieces as well, so that we can swap the corner
  22        and edge pieces with each other.
  23
  24     =  Have it drop all pieces to the "floor" then pick them up to
  25        reassemble the picture.
  26
  27     =  As a joke, maybe sometimes have one piece that doesn't fit?
  28        Or lose a piece?
  29  */
  30
  31 #include "screenhack.h"
  32 #include "spline.h"
  33
  34 #undef countof
  35 #define countof(x) (sizeof((x))/sizeof((*x)))
  36
  37 #define CENTER    0
  38 #define NORTH     1
  39 #define NORTHEAST 2
  40 #define EAST      3
  41 #define SOUTHEAST 4
  42 #define SOUTH     5
  43 #define SOUTHWEST 6
  44 #define WEST      7
  45 #define NORTHWEST 8
  46
  47 struct piece {
  48   int width, height;
  49   int x, y;
  50   Pixmap pixmap;
  51 };
  52
  53 struct set {
  54   struct piece pieces[9];
  55 };
  56
  57 #define PIECE_A_HOLLOW 0
  58 #define PIECE_A_FILLED 1
  59 #define PIECE_B_HOLLOW 2
  60 #define PIECE_B_FILLED 3
  61
  62 struct swap_state {
  63   int flashing;
  64   int x1, y1, x2, y2;
  65   Bool draw_p;
  66 };
  67
  68 struct state {
  69   Display *dpy;
  70   Window window;
  71
  72   struct set all_pieces[4];
  73
  74   int piece_width, piece_height;
  75   int width, height;
  76   int x_border, y_border;
  77   Pixmap source;
  78   GC gc;
  79   int fg, bg;
  80   int border_width;
  81   XPoint *state;
  82   int delay, delay2;
  83
  84   int jigstate;
  85
  86   struct swap_state swap;
  87   int clearing;
  88
  89   async_load_state *img_loader;
  90 };
  91
  92
  93 /* Returns a spline describing one edge of a puzzle piece of the given length.
  94  */
  95 static spline *
  96 make_puzzle_curve (int pixels)
  97 {
  98   double x0 = 0.0000, y0 =  0.0000;
  99   double x1 = 0.3333, y1 =  0.1000;
 100   double x2 = 0.4333, y2 =  0.0333;
 101   double x3 = 0.4666, y3 = -0.0666;
 102   double x4 = 0.3333, y4 = -0.1666;
 103   double x5 = 0.3666, y5 = -0.2900;
 104   double x6 = 0.5000, y6 = -0.3333;
 105
 106   spline *s = make_spline(20);
 107   s->n_controls = 0;
 108
 109 # define PT(x,y) \
 110     s->control_x[s->n_controls] = pixels * (x); \
 111     s->control_y[s->n_controls] = pixels * (y); \
 112     s->n_controls++
 113   PT (  x0, y0);
 114   PT (  x1, y1);
 115   PT (  x2, y2);
 116   PT (  x3, y3);
 117   PT (  x4, y4);
 118   PT (  x5, y5);
 119   PT (  x6, y6);
 120   PT (1-x5, y5);
 121   PT (1-x4, y4);
 122   PT (1-x3, y3);
 123   PT (1-x2, y2);
 124   PT (1-x1, y1);
 125   PT (1-x0, y0);
 126 # undef PT
 127
 128   compute_spline (s);
 129   return s;
 130 }
 131
 132
 133 /* Draws a puzzle piece.  The top/right/bottom/left_type args
 134    indicate the direction the tabs point: 1 for out, -1 for in, 0 for flat.
 135  */
 136 static void
 137 draw_puzzle_shape (Display *dpy, Drawable d, GC gc,
 138                    int x, int y, int size, int bw,
 139                    int top_type, int right_type,
 140                    int bottom_type, int left_type,
 141                    Bool fill_p)
 142 {
 143   spline *s = make_puzzle_curve (size);
 144   XPoint *pts = (XPoint *) malloc (s->n_points * 4 * sizeof(*pts));
 145   int i, o;
 146
 147   /* The border is twice as wide for "flat" edges, otherwise it looks funny. */
 148   if (fill_p)
 149     bw = 0;
 150   else
 151     bw /= 2;
 152
 153   o = 0;
 154   if (top_type == 0) {
 155     pts[o].x = x;        pts[o].y = y + bw; o++;
 156     pts[o].x = x + size; pts[o].y = y + bw; o++;
 157   } else {
 158     for (i = 0; i < s->n_points; i++) {
 159       pts[o].x = x + s->points[i].x;
 160       pts[o].y = y + s->points[i].y * top_type;
 161       o++;
 162     }
 163   }
 164
 165   if (right_type == 0) {
 166     pts[o-1].x -= bw;
 167     pts[o].x = x + size - bw; pts[o].y = y + size; o++;
 168   } else {
 169     for (i = 1; i < s->n_points; i++) {
 170       pts[o].x = x + size + s->points[i].y * (-right_type);
 171       pts[o].y = y        + s->points[i].x;
 172       o++;
 173     }
 174   }
 175
 176   if (bottom_type == 0) {
 177     pts[o-1].y -= bw;
 178     pts[o].x = x; pts[o].y = y + size - bw; o++;
 179   } else {
 180     for (i = 1; i < s->n_points; i++) {
 181       pts[o].x = x        + s->points[s->n_points-i-1].x;
 182       pts[o].y = y + size + s->points[s->n_points-i-1].y * (-bottom_type);
 183       o++;
 184     }
 185   }
 186
 187   if (left_type == 0) {
 188     pts[o-1].x += bw;
 189     pts[o].x = x + bw; pts[o].y = y; o++;
 190   } else {
 191     for (i = 1; i < s->n_points; i++) {
 192       pts[o].x = x + s->points[s->n_points-i-1].y * left_type;
 193       pts[o].y = y + s->points[s->n_points-i-1].x;
 194       o++;
 195     }
 196   }
 197
 198   free_spline (s);
 199
 200   if (fill_p)
 201     XFillPolygon (dpy, d, gc, pts, o, Complex, CoordModeOrigin);
 202   else
 203     XDrawLines (dpy, d, gc, pts, o, CoordModeOrigin);
 204
 205   free (pts);
 206 }
 207
 208
 209 /* Creates two pixmaps for a puzzle piece:
 210    - The first is a solid bit-mask with 1 for each pixel inside the piece;
 211    - The second is an outline of the piece, where all drawn pixels are
 212      contained within the mask.
 213
 214    The top/right/bottom/left_type args indicate the direction the
 215    tabs point: 1 for out, -1 for in, 0 for flat.
 216
 217    Size is how big the piece should be, from origin to origin.
 218
 219    Returned x/y is the origin within the pixmaps.
 220  */
 221 static void
 222 make_puzzle_pixmap_pair (Display *dpy, Drawable d, int size, int bw,
 223                          int top_type, int right_type,
 224                          int bottom_type, int left_type,
 225                          int *x_ret, int *y_ret,
 226                          Pixmap *mask_ret, Pixmap *outline_ret)
 227 {
 228   int w = size * 3;
 229   int h = w;
 230   int x = size;
 231   int y = size;
 232   Pixmap p0 = XCreatePixmap (dpy, d, w, h, 1);
 233   Pixmap p1 = XCreatePixmap (dpy, d, w, h, 1);
 234   XGCValues gcv;
 235   GC gc;
 236   gcv.foreground = 0;
 237   gcv.background = 0;
 238   gc = XCreateGC (dpy, p0, GCForeground|GCBackground, &gcv);
 239   XFillRectangle (dpy, p0, gc, 0, 0, w, h);
 240   XFillRectangle (dpy, p1, gc, 0, 0, w, h);
 241   XSetForeground (dpy, gc, 0);
 242
 243 # ifdef HAVE_COCOA
 244   jwxyz_XSetAlphaAllowed (dpy, gc, False);
 245 # endif
 246
 247   /* To ensure that each pixel is drawn only once, we render the piece
 248      such that it "owns" the left and top edges, but not the right and
 249      bottom edges.
 250
 251          - - +      "#" is this piece.
 252          - # +      It overlaps "-" and is overlapped by "+".
 253          - + +
 254
 255      To accomplish this, we clear to black, draw "#" in white,
 256      then draw "+" in black.
 257    */
 258
 259   /* Center square */
 260   XSetForeground (dpy, gc, 1);
 261   draw_puzzle_shape (dpy, p0, gc, x, y, size, bw,
 262                      top_type, right_type, bottom_type, left_type,
 263                      True);
 264
 265   /* Top right square */
 266   XSetForeground (dpy, gc, 0);
 267   draw_puzzle_shape (dpy, p0, gc, x + size, y - size, size, bw,
 268                      0, 0, -top_type, -left_type,
 269                      True);
 270
 271   /* Center right square */
 272   draw_puzzle_shape (dpy, p0, gc, x + size, y, size, bw,
 273                      0, 0, 0, -right_type,
 274                      True);
 275
 276   /* Bottom center square */
 277   draw_puzzle_shape (dpy, p0, gc, x, y + size, size, bw,
 278                      -bottom_type, 0, 0, 0,
 279                      True);
 280
 281   /* And Charles Nelson Reilly in the bottom right square */
 282   draw_puzzle_shape (dpy, p0, gc, x + size, y + size, size, bw,
 283                      -bottom_type, -right_type, 0, 0,
 284                      True);
 285
 286   /* Done with p0 (the mask).
 287      To make p1 (the outline) draw an outlined piece through the mask.
 288    */
 289   if (bw < 0)
 290     {
 291       bw = size / 30;
 292       if (bw < 1) bw = 1;
 293     }
 294
 295   if (bw > 0)
 296     {
 297       XSetForeground (dpy, gc, 1);
 298       XSetClipMask (dpy, gc, p0);
 299       XSetLineAttributes (dpy, gc, bw, LineSolid, CapButt, JoinRound);
 300       draw_puzzle_shape (dpy, p1, gc, x, y, size, bw,
 301                          top_type, right_type, bottom_type, left_type,
 302                          False);
 303     }
 304
 305   XFreeGC (dpy, gc);
 306   *x_ret = x;
 307   *y_ret = x;
 308   *mask_ret = p0;
 309   *outline_ret = p1;
 310 }
 311
 312
 313 static void
 314 make_puzzle_pixmaps (struct state *st)
 315 {
 316   int i, j;
 317
 318   int edges[9][4] = {
 319     { -1,  1, -1, 1 },  /* CENTER    */
 320     {  0,  1, -1, 1 },  /* NORTH     */
 321     {  0,  0, -1, 1 },  /* NORTHEAST */
 322     { -1,  0, -1, 1 },  /* EAST      */
 323     { -1,  0,  0, 1 },  /* SOUTHEAST */
 324     { -1,  1,  0, 1 },  /* SOUTH     */
 325     { -1,  1,  0, 0 },  /* SOUTHWEST */
 326     { -1,  1, -1, 0 },  /* WEST      */
 327     {  0,  1, -1, 0 },  /* NORTHWEST */
 328   };
 329
 330   /* sometimes swap direction of horizontal edges */
 331   if (random() & 1)
 332     for (j = 0; j < countof(edges); j++) {
 333       edges[j][0] = -edges[j][0];
 334       edges[j][2] = -edges[j][2];
 335     }
 336
 337   /* sometimes swap direction of vertical edges */
 338   if (random() & 1)
 339     for (j = 0; j < countof(edges); j++) {
 340       edges[j][1] = -edges[j][1];
 341       edges[j][3] = -edges[j][3];
 342     }
 343
 344   for (j = 0; j < 9; j++) {
 345     for (i = 0; i < 2; i++) {
 346       int x, y;
 347       int top, right, bottom, left;
 348       Pixmap mask, outline;
 349       top    = edges[j][0];
 350       right  = edges[j][1];
 351       bottom = edges[j][2];
 352       left   = edges[j][3];
 353       if (i) {
 354         top    = -top;
 355         right  = -right;
 356         bottom = -bottom;
 357         left   = -left;
 358       }
 359       make_puzzle_pixmap_pair (st->dpy, st->window, st->piece_width,
 360                                st->border_width,
 361                                top, right, bottom, left,
 362                                &x, &y, &mask, &outline);
 363
 364       st->all_pieces[i*2].pieces[j].x = x;
 365       st->all_pieces[i*2].pieces[j].y = y;
 366       st->all_pieces[i*2].pieces[j].pixmap = outline;
 367
 368       st->all_pieces[i*2+1].pieces[j].x = x;
 369       st->all_pieces[i*2+1].pieces[j].y = y;
 370       st->all_pieces[i*2+1].pieces[j].pixmap = mask;
 371     }
 372   }
 373 }
 374
 375 static void
 376 free_puzzle_pixmaps (struct state *st)
 377 {
 378   int i, j;
 379   for (i = 0; i < countof(st->all_pieces); i++)
 380     for (j = 0; j < countof (st->all_pieces[i].pieces); j++)
 381       if (st->all_pieces[i].pieces[j].pixmap) {
 382         XFreePixmap (st->dpy, st->all_pieces[i].pieces[j].pixmap);
 383         st->all_pieces[i].pieces[j].pixmap = 0;
 384       }
 385 }
 386
 387
 388 static void
 389 jigsaw_init_1 (struct state *st)
 390 {
 391   XWindowAttributes xgwa;
 392   int x, y;
 393   XGCValues gcv;
 394   Colormap cmap;
 395
 396   XGetWindowAttributes (st->dpy, st->window, &xgwa);
 397
 398   st->piece_width = 40 + (random() % 100);
 399   if (xgwa.width / st->piece_width < 4)
 400     st->piece_width = xgwa.width / 4;
 401   st->piece_height = st->piece_width;
 402
 403   free_puzzle_pixmaps (st);
 404   make_puzzle_pixmaps (st);
 405
 406   cmap = xgwa.colormap;
 407   st->width  = xgwa.width  / st->piece_width;
 408   st->height = xgwa.height / st->piece_height;
 409   st->x_border = (xgwa.width  - (st->width  * st->piece_width)) / 2;
 410   st->y_border = (xgwa.height - (st->height * st->piece_width)) / 2;
 411
 412   if (st->width  < 4) st->width  = 4, st->x_border = 0;
 413   if (st->height < 4) st->height = 4, st->y_border = 0;
 414
 415   if (st->state) free (st->state);
 416   st->state = (XPoint *) malloc (st->width * st->height * sizeof(*st->state));
 417
 418   if (!st->gc)
 419     {
 420       XColor fgc, bgc;
 421       char *fgs = get_string_resource(st->dpy, "foreground", "Foreground");
 422       char *bgs = get_string_resource(st->dpy, "background", "Background");
 423       Bool fg_ok, bg_ok;
 424
 425       st->gc = XCreateGC (st->dpy, st->window, 0, &gcv);
 426
 427 # ifdef HAVE_COCOA
 428       jwxyz_XSetAlphaAllowed (st->dpy, st->gc, False);
 429 # endif
 430
 431       if (!XParseColor (st->dpy, cmap, fgs, &fgc))
 432         XParseColor (st->dpy, cmap, "gray", &fgc);
 433       if (!XParseColor (st->dpy, cmap, bgs, &bgc))
 434         XParseColor (st->dpy, cmap, "black", &bgc);
 435
 436       free (fgs);
 437       free (bgs);
 438       fgs = bgs = 0;
 439
 440       fg_ok = XAllocColor (st->dpy, cmap, &fgc);
 441       bg_ok = XAllocColor (st->dpy, cmap, &bgc);
 442
 443       /* If we weren't able to allocate the two colors we want from the
 444          colormap (which is likely if the screen has been grabbed on an
 445          8-bit SGI visual -- don't ask) then just go through the map
 446          and find the closest color to the ones we wanted, and use those
 447          pixels without actually allocating them.
 448       */
 449       if (fg_ok)
 450         st->fg = fgc.pixel;
 451       else
 452         st->fg = 0;
 453
 454       if (bg_ok)
 455         st->bg = bgc.pixel;
 456       else
 457         st->bg = 1;
 458
 459 #ifndef HAVE_COCOA
 460       if (!fg_ok || bg_ok)
 461         {
 462           int i;
 463           unsigned long fgd = ~0;
 464           unsigned long bgd = ~0;
 465           int max = visual_cells (xgwa.screen, xgwa.visual);
 466           XColor *all = (XColor *) calloc(sizeof (*all), max);
 467           for (i = 0; i < max; i++)
 468             {
 469               all[i].flags = DoRed|DoGreen|DoBlue;
 470               all[i].pixel = i;
 471             }
 472           XQueryColors (st->dpy, cmap, all, max);
 473           for(i = 0; i < max; i++)
 474             {
 475               long rd, gd, bd;
 476               unsigned long d;
 477               if (!fg_ok)
 478                 {
 479                   rd = (all[i].red   >> 8) - (fgc.red   >> 8);
 480                   gd = (all[i].green >> 8) - (fgc.green >> 8);
 481                   bd = (all[i].blue  >> 8) - (fgc.blue  >> 8);
 482                   if (rd < 0) rd = -rd;
 483                   if (gd < 0) gd = -gd;
 484                   if (bd < 0) bd = -bd;
 485                   d = (rd << 1) + (gd << 2) + bd;
 486                   if (d < fgd)
 487                     {
 488                       fgd = d;
 489                       st->fg = all[i].pixel;
 490                       if (d == 0)
 491                         fg_ok = True;
 492                     }
 493                 }
 494
 495               if (!bg_ok)
 496                 {
 497                   rd = (all[i].red   >> 8) - (bgc.red   >> 8);
 498                   gd = (all[i].green >> 8) - (bgc.green >> 8);
 499                   bd = (all[i].blue  >> 8) - (bgc.blue  >> 8);
 500                   if (rd < 0) rd = -rd;
 501                   if (gd < 0) gd = -gd;
 502                   if (bd < 0) bd = -bd;
 503                   d = (rd << 1) + (gd << 2) + bd;
 504                   if (d < bgd)
 505                     {
 506                       bgd = d;
 507                       st->bg = all[i].pixel;
 508                       if (d == 0)
 509                         bg_ok = True;
 510                     }
 511                 }
 512
 513               if (fg_ok && bg_ok)
 514                 break;
 515             }
 516           XFree(all);
 517         }
 518 #endif /* HAVE_COCOA */
 519     }
 520
 521   /* Reset the window's background color... */
 522   XSetWindowBackground (st->dpy, st->window, st->bg);
 523   XClearWindow(st->dpy, st->window);
 524
 525   for (y = 0; y < st->height; y++)
 526     for (x = 0; x < st->width; x++)
 527       {
 528         st->state[y * st->width + x].x = x;
 529         st->state[y * st->width + x].y = y;
 530       }
 531
 532   if (st->source)
 533     XFreePixmap (st->dpy, st->source);
 534   st->source = XCreatePixmap (st->dpy, st->window, xgwa.width, xgwa.height,
 535                               xgwa.depth);
 536
 537   st->img_loader = load_image_async_simple (0, xgwa.screen, st->window,
 538                                             st->source, 0, 0);
 539 }
 540
 541
 542 static void
 543 get_piece (struct state *st,
 544            int x, int y, struct piece **hollow, struct piece **filled)
 545 {
 546   int p;
 547   Bool which = (x & 1) == (y & 1);
 548
 549   if      (x == 0           && y == 0)            p = NORTHWEST;
 550   else if (x == st->width-1 && y == 0)            p = NORTHEAST;
 551   else if (x == st->width-1 && y == st->height-1) p = SOUTHEAST;
 552   else if (x == 0           && y == st->height-1) p = SOUTHWEST;
 553   else if (y == 0)                                p = NORTH;
 554   else if (x == st->width-1)                      p = EAST;
 555   else if (y == st->height-1)                     p = SOUTH;
 556   else if (x == 0)                                p = WEST;
 557   else                                            p = CENTER;
 558
 559   if (hollow)
 560     *hollow = (which
 561                ? &st->all_pieces[PIECE_A_HOLLOW].pieces[p]
 562                : &st->all_pieces[PIECE_B_HOLLOW].pieces[p]);
 563   if (filled)
 564     *filled = (which
 565                ? &st->all_pieces[PIECE_A_FILLED].pieces[p]
 566                : &st->all_pieces[PIECE_B_FILLED].pieces[p]);
 567 }
 568
 569
 570 static void
 571 draw_piece (struct state *st, int x, int y, int clear_p)
 572 {
 573   struct piece *hollow, *filled;
 574   int from_x = st->state[y * st->width + x].x;
 575   int from_y = st->state[y * st->width + x].y;
 576
 577   get_piece(st, x, y, &hollow, &filled);
 578
 579   XSetClipMask(st->dpy, st->gc, filled->pixmap);
 580   XSetClipOrigin(st->dpy, st->gc,
 581                  st->x_border + (x * st->piece_width) - filled->x - 1,
 582                  st->y_border + (y * st->piece_width) - filled->y - 1);
 583
 584   if (clear_p)
 585     {
 586       XSetForeground(st->dpy, st->gc, st->bg);
 587       XFillRectangle(st->dpy, st->window, st->gc,
 588                      st->x_border + (x * st->piece_width)  -st->piece_width/2,
 589                      st->y_border + (y * st->piece_height) -st->piece_height/2,
 590                      st->piece_width*2, st->piece_height*2);
 591     }
 592   else
 593     XCopyArea(st->dpy, st->source, st->window, st->gc,
 594               st->x_border + (from_x * st->piece_width)  - st->piece_width/2,
 595               st->y_border + (from_y * st->piece_height) - st->piece_height/2,
 596               st->piece_width*2, st->piece_height*2,
 597               st->x_border + (x * st->piece_width)  - st->piece_width/2,
 598               st->y_border + (y * st->piece_height) - st->piece_height/2);
 599
 600   if (clear_p > 1)
 601     return;
 602
 603   XSetForeground(st->dpy, st->gc, st->fg);
 604   XSetClipMask(st->dpy, st->gc, hollow->pixmap);
 605   XSetClipOrigin(st->dpy, st->gc,
 606                  st->x_border + (x * st->piece_width) - hollow->x - 1,
 607                  st->y_border + (y * st->piece_width) - hollow->y - 1);
 608   XFillRectangle(st->dpy, st->window, st->gc,
 609                  st->x_border + (x * st->piece_width)  - st->piece_width/2,
 610                  st->y_border + (y * st->piece_height) - st->piece_height/2,
 611                  st->piece_width*2, st->piece_height*2);
 612 }
 613
 614
 615 static int
 616 animate_swap (struct state *st, struct swap_state *sw)
 617 {
 618   XPoint swap;
 619
 620   if (sw->flashing > 1)
 621     {
 622       draw_piece(st, sw->x1, sw->y1, sw->flashing & 1);
 623       draw_piece(st, sw->x2, sw->y2, sw->flashing & 1);
 624       sw->flashing--;
 625       return st->delay;
 626     }
 627
 628   swap = st->state[sw->y1 * st->width + sw->x1];
 629   st->state[sw->y1 * st->width + sw->x1] =
 630     st->state[sw->y2 * st->width + sw->x2];
 631   st->state[sw->y2 * st->width + sw->x2] = swap;
 632
 633   if (sw->draw_p)
 634     {
 635       draw_piece(st, sw->x1, sw->y1, 0);
 636       draw_piece(st, sw->x2, sw->y2, 0);
 637       sw->flashing = 0;
 638     }
 639
 640   return 0;
 641 }
 642
 643
 644 static int
 645 swap_pieces (struct state *st,
 646              int src_x, int src_y, int dst_x, int dst_y,
 647              Bool draw_p)
 648 {
 649   struct swap_state *sw = &st->swap;
 650
 651   sw->x1 = src_x;
 652   sw->y1 = src_y;
 653   sw->x2 = dst_x;
 654   sw->y2 = dst_y;
 655   sw->draw_p = draw_p;
 656
 657   /* if animating, plan to flash the pieces on and off a few times */
 658   sw->flashing = sw->draw_p ? 7 : 0;
 659
 660   return animate_swap(st, sw);
 661 }
 662
 663
 664 static Bool
 665 done (struct state *st)
 666 {
 667   int x, y;
 668   for (y = 0; y < st->height; y++)
 669     for (x = 0; x < st->width; x++)
 670       {
 671         int x2 = st->state[y * st->width + x].x;
 672         int y2 = st->state[y * st->width + x].y;
 673         if (x != x2 || y != y2)
 674           return False;
 675       }
 676   return True;
 677 }
 678
 679
 680 static int
 681 shuffle (struct state *st, Bool draw_p)
 682 {
 683   struct piece *p1, *p2;
 684   int src_x, src_y, dst_x = -1, dst_y = -1;
 685
 686  AGAIN:
 687   p1 = p2 = 0;
 688   src_x = random() % st->width;
 689   src_y = random() % st->height;
 690
 691   get_piece(st, src_x, src_y, &p1, 0);
 692
 693   /* Pick random coordinates until we find one that has the same kind of
 694      piece as the first one we picked.  Note that it's possible for there
 695      to be only one piece of a particular shape on the board (this always
 696      happens with the four corner pieces.)
 697    */
 698   while (p1 != p2)
 699     {
 700       dst_x = random() % st->width;
 701       dst_y = random() % st->height;
 702       get_piece(st, dst_x, dst_y, &p2, 0);
 703     }
 704
 705   if (src_x == dst_x && src_y == dst_y)
 706     goto AGAIN;
 707
 708   return swap_pieces(st, src_x, src_y, dst_x, dst_y, draw_p);
 709 }
 710
 711
 712 static void
 713 shuffle_all (struct state *st)
 714 {
 715   int j;
 716   for (j = 0; j < 5; j++) {
 717     /* swap each piece with another 5x */
 718     int i = (st->width * st->height * 5);
 719     while (--i > 0)
 720       shuffle (st, False);
 721
 722     /* and do that whole process up to 5x if we ended up with a solved
 723        board (this often happens with 4x4 boards.) */
 724     if (!done(st))
 725       break;
 726   }
 727 }
 728
 729
 730 static int
 731 unshuffle (struct state *st)
 732 {
 733   int i;
 734   for (i = 0; i < st->width * st->height * 4; i++)
 735     {
 736       int x = random() % st->width;
 737       int y = random() % st->height;
 738       int x2 = st->state[y * st->width + x].x;
 739       int y2 = st->state[y * st->width + x].y;
 740       if (x != x2 || y != y2)
 741         {
 742           return swap_pieces(st, x, y, x2, y2, True);
 743         }
 744     }
 745   return 0;
 746 }
 747
 748
 749 static int
 750 animate_clear (struct state *st)
 751 {
 752   while (st->clearing > 0)
 753     {
 754       int x = random() % st->width;
 755       int y = random() % st->height;
 756       XPoint *p = &st->state[y * st->width + x];
 757       if (p->x == -1)
 758         continue;
 759       draw_piece(st, p->x, p->y, 2);
 760       p->x = p->y = -1;
 761       st->clearing--;
 762       return st->delay;
 763     }
 764   return 0;
 765 }
 766
 767
 768 static int
 769 clear_all (struct state *st)
 770 {
 771   st->clearing = st->width * st->height;
 772   return animate_clear(st);
 773 }
 774
 775
 776 static void *
 777 jigsaw_init (Display *dpy, Window window)
 778 {
 779   struct state *st = (struct state *) calloc (1, sizeof(*st));
 780   st->dpy = dpy;
 781   st->window = window;
 782   st->delay = get_integer_resource (st->dpy, "delay", "Integer");
 783   st->delay2 = get_integer_resource (st->dpy, "delay2", "Integer") * 1000000;
 784   st->border_width = get_integer_resource (st->dpy, "pieceBorderWidth",
 785                                            "Integer");
 786   if (st->delay == 0) st->delay = 1; /* kludge */
 787   return st;
 788 }
 789
 790
 791 static unsigned long
 792 jigsaw_draw (Display *dpy, Window window, void *closure)
 793 {
 794   struct state *st = (struct state *) closure;
 795   int x, y;
 796   int delay = 0;
 797
 798   if (st->img_loader)   /* still loading */
 799     {
 800       st->img_loader = load_image_async_simple (st->img_loader, 0, 0, 0, 0, 0);
 801       if (! st->img_loader) {  /* just finished */
 802         shuffle_all (st);
 803         for (y = 0; y < st->height; y++)
 804           for (x = 0; x < st->width; x++)
 805             draw_piece(st, x, y, 0);
 806       }
 807       return st->delay;
 808     }
 809
 810   if (st->swap.flashing)
 811     delay = animate_swap (st, &st->swap);
 812   else if (st->clearing)
 813     delay = animate_clear (st);
 814
 815   if (!delay) {
 816     if (st->jigstate == 0)
 817       {
 818         jigsaw_init_1 (st);
 819         st->jigstate = 1;
 820       }
 821     else if (st->jigstate == 1)
 822       {
 823         if (done(st))
 824           {
 825             st->jigstate = 2;
 826             delay = st->delay2;
 827           }
 828         else
 829           {
 830             delay = unshuffle(st);
 831           }
 832       }
 833     else if (st->jigstate == 2)
 834       {
 835         st->jigstate = 0;
 836         delay = clear_all(st);
 837       }
 838     else
 839       abort();
 840   }
 841
 842   if (delay == 1) delay = 0; /* kludge */
 843   return (delay ? delay : st->delay * 10);
 844 }
 845
 846 static void
 847 jigsaw_reshape (Display *dpy, Window window, void *closure,
 848                  unsigned int w, unsigned int h)
 849 {
 850   /* window size is checked each time a new puzzle begins */
 851 }
 852
 853 static Bool
 854 jigsaw_event (Display *dpy, Window window, void *closure, XEvent *event)
 855 {
 856   return False;
 857 }
 858
 859 static void
 860 jigsaw_free (Display *dpy, Window window, void *closure)
 861 {
 862   struct state *st = (struct state *) closure;
 863   free_puzzle_pixmaps (st);
 864   if (st->state) free (st->state);
 865   if (st->gc) XFreeGC (dpy, st->gc);
 866   if (st->source) XFreePixmap (dpy, st->source);
 867   free (st);
 868 }
 869
 870 \f
 871
 872 static const char *jigsaw_defaults [] = {
 873   ".background:         Black",
 874   ".foreground:         #AAAAAA",
 875   "*delay:              70000",
 876   "*delay2:             5",
 877   "*pieceBorderWidth:   -1",
 878 #ifdef __sgi    /* really, HAVE_READ_DISPLAY_EXTENSION */
 879   "*visualID:           Best",
 880 #endif
 881   0
 882 };
 883
 884 static XrmOptionDescRec jigsaw_options [] = {
 885   { "-delay",           ".delay",               XrmoptionSepArg, 0 },
 886   { "-delay2",          ".delay2",              XrmoptionSepArg, 0 },
 887   { "-bw",              ".pieceBorderWidth",    XrmoptionSepArg, 0 },
 888   { "-border-width",    ".pieceBorderWidth",    XrmoptionSepArg, 0 },
 889   { 0, 0, 0, 0 }
 890 };
 891
 892
 893 XSCREENSAVER_MODULE ("Jigsaw", jigsaw)