6c28205f508f841229a2b300704179e4a42b1adc
[xscreensaver] / hacks / jigsaw.c
1 /* xscreensaver, Copyright (c) 1997, 1998, 2001, 2003
2  *  Jamie Zawinski <jwz@jwz.org>
3  *
4  * Permission to use, copy, modify, distribute, and sell this software and its
5  * documentation for any purpose is hereby granted without fee, provided that
6  * the above copyright notice appear in all copies and that both that
7  * copyright notice and this permission notice appear in supporting
8  * documentation.  No representations are made about the suitability of this
9  * software for any purpose.  It is provided "as is" without express or 
10  * implied warranty.
11  */
12
13 /*
14   TODO:
15
16     =  Rather than just flickering the pieces before swapping them,
17        show them lifting up and moving to their new positions.
18        The path on which they move shouldn't be a straight line;
19        try to avoid having them cross each other by moving them in
20        oppositely-positioned arcs.
21
22     =  Rotate the pieces as well, so that we can swap the corner
23        and edge pieces with each other.
24
25     =  The shapes of the piece bitmaps still aren't quite right.
26        They should line up with no overlap.  They don't...
27     
28     =  Have it drop all pieces to the "floor" then pick them up to
29        reassemble the picture.
30
31     =  As a joke, maybe sometimes have one piece that doesn't fit?
32        Or lose a piece?
33  */
34
35 #include "screenhack.h"
36
37 #define DEBUG
38
39 #include "images/jigsaw/jigsaw_a_h.xbm"
40 #include "images/jigsaw/jigsaw_a_n_h.xbm"
41 #include "images/jigsaw/jigsaw_a_ne_h.xbm"
42 #include "images/jigsaw/jigsaw_a_e_h.xbm"
43 #include "images/jigsaw/jigsaw_a_se_h.xbm"
44 #include "images/jigsaw/jigsaw_a_s_h.xbm"
45 #include "images/jigsaw/jigsaw_a_sw_h.xbm"
46 #include "images/jigsaw/jigsaw_a_w_h.xbm"
47 #include "images/jigsaw/jigsaw_a_nw_h.xbm"
48
49 #include "images/jigsaw/jigsaw_b_h.xbm"
50 #include "images/jigsaw/jigsaw_b_n_h.xbm"
51 #include "images/jigsaw/jigsaw_b_ne_h.xbm"
52 #include "images/jigsaw/jigsaw_b_e_h.xbm"
53 #include "images/jigsaw/jigsaw_b_se_h.xbm"
54 #include "images/jigsaw/jigsaw_b_s_h.xbm"
55 #include "images/jigsaw/jigsaw_b_sw_h.xbm"
56 #include "images/jigsaw/jigsaw_b_w_h.xbm"
57 #include "images/jigsaw/jigsaw_b_nw_h.xbm"
58
59 #include "images/jigsaw/jigsaw_a_f.xbm"
60 #include "images/jigsaw/jigsaw_a_n_f.xbm"
61 #include "images/jigsaw/jigsaw_a_ne_f.xbm"
62 #include "images/jigsaw/jigsaw_a_e_f.xbm"
63 #include "images/jigsaw/jigsaw_a_se_f.xbm"
64 #include "images/jigsaw/jigsaw_a_s_f.xbm"
65 #include "images/jigsaw/jigsaw_a_sw_f.xbm"
66 #include "images/jigsaw/jigsaw_a_w_f.xbm"
67 #include "images/jigsaw/jigsaw_a_nw_f.xbm"
68
69 #include "images/jigsaw/jigsaw_b_f.xbm"
70 #include "images/jigsaw/jigsaw_b_n_f.xbm"
71 #include "images/jigsaw/jigsaw_b_ne_f.xbm"
72 #include "images/jigsaw/jigsaw_b_e_f.xbm"
73 #include "images/jigsaw/jigsaw_b_se_f.xbm"
74 #include "images/jigsaw/jigsaw_b_s_f.xbm"
75 #include "images/jigsaw/jigsaw_b_sw_f.xbm"
76 #include "images/jigsaw/jigsaw_b_w_f.xbm"
77 #include "images/jigsaw/jigsaw_b_nw_f.xbm"
78
79 #define GRID_WIDTH  66
80 #define GRID_HEIGHT 66
81
82 #define CENTER    0
83 #define NORTH     1
84 #define NORTHEAST 2
85 #define EAST      3
86 #define SOUTHEAST 4
87 #define SOUTH     5
88 #define SOUTHWEST 6
89 #define WEST      7
90 #define NORTHWEST 8
91
92 struct piece {
93   int width, height;
94   int x, y;
95   Pixmap pixmap;
96 };
97
98 struct set {
99   struct piece pieces[9];
100 };
101
102 #define PIECE_A_HOLLOW 0
103 #define PIECE_A_FILLED 1
104 #define PIECE_B_HOLLOW 2
105 #define PIECE_B_FILLED 3
106
107 static struct set all_pieces[4];
108
109 static void
110 init_images(Display *dpy, Window window)
111 {
112 # define LOAD_PIECE(PIECE,NAME)                                 \
113     PIECE.x = jigsaw_##NAME##_x_hot;                            \
114     PIECE.y = jigsaw_##NAME##_y_hot;                            \
115     PIECE.pixmap =                                              \
116     XCreatePixmapFromBitmapData(dpy, window,                    \
117                                 (char *) jigsaw_##NAME##_bits,  \
118                                 jigsaw_##NAME##_width,          \
119                                 jigsaw_##NAME##_height,         \
120                                 1, 0, 1)
121
122 # define LOAD_PIECES(SET,PREFIX,SUFFIX)                         \
123     LOAD_PIECE(SET.pieces[CENTER],    PREFIX##_##SUFFIX);       \
124     LOAD_PIECE(SET.pieces[NORTH],     PREFIX##_n_##SUFFIX);     \
125     LOAD_PIECE(SET.pieces[NORTHEAST], PREFIX##_ne_##SUFFIX);    \
126     LOAD_PIECE(SET.pieces[EAST],      PREFIX##_e_##SUFFIX);     \
127     LOAD_PIECE(SET.pieces[SOUTHEAST], PREFIX##_se_##SUFFIX);    \
128     LOAD_PIECE(SET.pieces[SOUTH],     PREFIX##_s_##SUFFIX);     \
129     LOAD_PIECE(SET.pieces[SOUTHWEST], PREFIX##_sw_##SUFFIX);    \
130     LOAD_PIECE(SET.pieces[WEST],      PREFIX##_w_##SUFFIX);     \
131     LOAD_PIECE(SET.pieces[NORTHWEST], PREFIX##_nw_##SUFFIX)
132
133   LOAD_PIECES(all_pieces[PIECE_A_HOLLOW],a,h);
134   LOAD_PIECES(all_pieces[PIECE_A_FILLED],a,f);
135   LOAD_PIECES(all_pieces[PIECE_B_HOLLOW],b,h);
136   LOAD_PIECES(all_pieces[PIECE_B_FILLED],b,f);
137
138 # undef LOAD_PIECE
139 # undef LOAD_PIECES
140 }
141
142 static Pixmap
143 read_screen (Display *dpy, Window window, int *widthP, int *heightP)
144 {
145   Pixmap p;
146   XWindowAttributes xgwa;
147   XGetWindowAttributes (dpy, window, &xgwa);
148   *widthP = xgwa.width;
149   *heightP = xgwa.height;
150
151   p = XCreatePixmap(dpy, window, *widthP, *heightP, xgwa.depth);
152   XClearWindow(dpy, window);
153   load_random_image (xgwa.screen, window, p, NULL);
154   XClearWindow(dpy, window);
155
156   return p;
157 }
158
159
160 static int width, height;
161 static int x_border, y_border;
162 static Pixmap source;
163 static GC gc;
164 static Bool tweak;
165 static int fg, bg;
166 static XPoint *state = 0;
167
168 static void
169 jigsaw_init(Display *dpy, Window window)
170 {
171   XWindowAttributes xgwa;
172   int x, y;
173   XGCValues gcv;
174   Colormap cmap;
175   int source_w, source_h;
176
177   tweak = random()&1;
178
179   source = read_screen (dpy, window, &source_w, &source_h);
180
181   XGetWindowAttributes (dpy, window, &xgwa);
182   cmap = xgwa.colormap;
183   width  = xgwa.width  / GRID_WIDTH;
184   height = xgwa.height / GRID_HEIGHT;
185   x_border = (xgwa.width  - (width  * GRID_WIDTH)) / 2;
186   y_border = (xgwa.height - (height * GRID_WIDTH)) / 2;
187
188   if (width < 4 || height < 4)
189     {
190       fprintf (stderr, "%s: window too small: %dx%d (need at least %dx%d)\n",
191                progname, xgwa.width, xgwa.height,
192                GRID_WIDTH * 4, GRID_HEIGHT * 4);
193       exit (1);
194     }
195
196   if (!state)
197     state = (XPoint *) malloc(width * height * sizeof(XPoint));
198   gc = XCreateGC (dpy, window, 0, &gcv);
199
200   {
201     XColor fgc, bgc;
202     char *fgs = get_string_resource("foreground", "Foreground");
203     char *bgs = get_string_resource("background", "Background");
204     Bool fg_ok, bg_ok;
205     if (!XParseColor (dpy, cmap, fgs, &fgc))
206       XParseColor (dpy, cmap, "gray", &fgc);
207     if (!XParseColor (dpy, cmap, bgs, &bgc))
208       XParseColor (dpy, cmap, "black", &bgc);
209
210     fg_ok = XAllocColor (dpy, cmap, &fgc);
211     bg_ok = XAllocColor (dpy, cmap, &bgc);
212
213     /* If we weren't able to allocate the two colors we want from the
214        colormap (which is likely if the screen has been grabbed on an
215        8-bit SGI visual -- don't ask) then just go through the map
216        and find the closest color to the ones we wanted, and use those
217        pixels without actually allocating them.
218      */
219     if (fg_ok)
220       fg = fgc.pixel;
221     else
222       fg = 0;
223
224     if (bg_ok)
225       bg = bgc.pixel;
226     else
227       bg = 1;
228
229     if (!fg_ok || bg_ok)
230       {
231         int i;
232         unsigned long fgd = ~0;
233         unsigned long bgd = ~0;
234         int max = visual_cells (xgwa.screen, xgwa.visual);
235         XColor *all = (XColor *) calloc(sizeof (*all), max);
236         for (i = 0; i < max; i++)
237           {
238             all[i].flags = DoRed|DoGreen|DoBlue;
239             all[i].pixel = i;
240           }
241         XQueryColors (dpy, cmap, all, max);
242         for(i = 0; i < max; i++)
243           {
244             long rd, gd, bd;
245             unsigned long d;
246             if (!fg_ok)
247               {
248                 rd = (all[i].red   >> 8) - (fgc.red   >> 8);
249                 gd = (all[i].green >> 8) - (fgc.green >> 8);
250                 bd = (all[i].blue  >> 8) - (fgc.blue  >> 8);
251                 if (rd < 0) rd = -rd;
252                 if (gd < 0) gd = -gd;
253                 if (bd < 0) bd = -bd;
254                 d = (rd << 1) + (gd << 2) + bd;
255                 if (d < fgd)
256                   {
257                     fgd = d;
258                     fg = all[i].pixel;
259                     if (d == 0)
260                       fg_ok = True;
261                   }
262               }
263
264             if (!bg_ok)
265               {
266                 rd = (all[i].red   >> 8) - (bgc.red   >> 8);
267                 gd = (all[i].green >> 8) - (bgc.green >> 8);
268                 bd = (all[i].blue  >> 8) - (bgc.blue  >> 8);
269                 if (rd < 0) rd = -rd;
270                 if (gd < 0) gd = -gd;
271                 if (bd < 0) bd = -bd;
272                 d = (rd << 1) + (gd << 2) + bd;
273                 if (d < bgd)
274                   {
275                     bgd = d;
276                     bg = all[i].pixel;
277                     if (d == 0)
278                       bg_ok = True;
279                   }
280               }
281
282             if (fg_ok && bg_ok)
283               break;
284           }
285         XFree(all);
286       }
287   }
288
289   /* Reset the window's background color... */
290   XSetWindowBackground (dpy, window, bg);
291   XClearWindow(dpy, window);
292
293   for (y = 0; y < height; y++)
294     for (x = 0; x < width; x++)
295       {
296         state[y * width + x].x = x;
297         state[y * width + x].y = y;
298       }
299 }
300
301
302 static void
303 get_piece(int x, int y, struct piece **hollow, struct piece **filled)
304 {
305   int p;
306   Bool which = (x & 1) == (y & 1);
307
308   if      (x == 0       && y == 0)        p = NORTHWEST;
309   else if (x == width-1 && y == 0)        p = NORTHEAST;
310   else if (x == width-1 && y == height-1) p = SOUTHEAST;
311   else if (x == 0       && y == height-1) p = SOUTHWEST;
312   else if (y == 0)                        p = NORTH;
313   else if (x == width-1)                  p = EAST;
314   else if (y == height-1)                 p = SOUTH;
315   else if (x == 0)                        p = WEST;
316   else                                    p = CENTER;
317
318   if (tweak) which = !which;
319   if (hollow)
320     *hollow = (which
321                ? &all_pieces[PIECE_A_HOLLOW].pieces[p]
322                : &all_pieces[PIECE_B_HOLLOW].pieces[p]);
323   if (filled)
324     *filled = (which
325                ? &all_pieces[PIECE_A_FILLED].pieces[p]
326                : &all_pieces[PIECE_B_FILLED].pieces[p]);
327 }
328
329
330 static void
331 draw_piece(Display *dpy, Window window, int x, int y, int clear_p)
332 {
333   struct piece *hollow, *filled;
334   int from_x = state[y * width + x].x;
335   int from_y = state[y * width + x].y;
336
337   get_piece(x, y, &hollow, &filled);
338           
339   XSetClipMask(dpy, gc, filled->pixmap);
340   XSetClipOrigin(dpy, gc,
341                  x_border + (x * GRID_WIDTH) - filled->x - 1,
342                  y_border + (y * GRID_WIDTH) - filled->y - 1);
343
344   if (clear_p)
345     {
346       XSetForeground(dpy, gc, bg);
347       XFillRectangle(dpy, window, gc,
348                      x_border + (x * GRID_WIDTH)  - GRID_WIDTH/2,
349                      y_border + (y * GRID_HEIGHT) - GRID_HEIGHT/2,
350                      GRID_WIDTH*2, GRID_HEIGHT*2);
351     }
352   else
353     XCopyArea(dpy, source, window, gc,
354               x_border + (from_x * GRID_WIDTH)  - GRID_WIDTH/2,
355               y_border + (from_y * GRID_HEIGHT) - GRID_HEIGHT/2,
356               GRID_WIDTH*2, GRID_HEIGHT*2,
357               x_border + (x * GRID_WIDTH)  - GRID_WIDTH/2,
358               y_border + (y * GRID_HEIGHT) - GRID_HEIGHT/2);
359
360   if (clear_p > 1)
361     return;
362
363   XSetForeground(dpy, gc, fg);
364   XSetClipMask(dpy, gc, hollow->pixmap);
365   XSetClipOrigin(dpy, gc,
366                  x_border + (x * GRID_WIDTH) - hollow->x - 1,
367                  y_border + (y * GRID_WIDTH) - hollow->y - 1);
368   XFillRectangle(dpy, window, gc,
369                  x_border + (x * GRID_WIDTH)  - GRID_WIDTH/2,
370                  y_border + (y * GRID_HEIGHT) - GRID_HEIGHT/2,
371                  GRID_WIDTH*2, GRID_HEIGHT*2);
372
373   if (clear_p)
374     {
375       /* If the pieces lined up right, we could do this by just not drawing
376          the outline -- but that doesn't look right, since it eats the outlines
377          of the adjascent pieces.  So draw the outline, then chop off the outer
378          edge if this is a border piece.
379        */
380       XSetForeground(dpy, gc, bg);
381       if (x == 0)
382         XFillRectangle(dpy, window, gc,
383                        x_border - 2,
384                        y_border + (y * GRID_HEIGHT),
385                        3, GRID_HEIGHT);
386       else if (x == width-1)
387         XFillRectangle(dpy, window, gc,
388                        x_border + ((x+1) * GRID_WIDTH) - 2,
389                        y_border + (y * GRID_HEIGHT),
390                        3, GRID_HEIGHT);
391
392       if (y == 0)
393         XFillRectangle(dpy, window, gc,
394                        x_border + (x * GRID_WIDTH),
395                        y_border - 2,
396                        GRID_WIDTH, 3);
397       else if (y == height-1)
398         XFillRectangle(dpy, window, gc,
399                        x_border + (x * GRID_WIDTH),
400                        y_border + ((y+1) * GRID_HEIGHT) - 2,
401                        GRID_WIDTH, 3);
402     }
403 }
404
405
406 static void
407 swap_pieces(Display *dpy, Window window,
408             int src_x, int src_y, int dst_x, int dst_y,
409             Bool draw_p)
410 {
411   XPoint swap;
412   int i;
413   if (draw_p)
414     for (i = 0; i < 3; i++)
415       {
416         draw_piece(dpy, window, src_x, src_y, 1);
417         draw_piece(dpy, window, dst_x, dst_y, 1);
418         XSync(dpy, False);
419         usleep(50000);
420         draw_piece(dpy, window, src_x, src_y, 0);
421         draw_piece(dpy, window, dst_x, dst_y, 0);
422         XSync(dpy, False);
423         usleep(50000);
424       }
425
426   swap = state[src_y * width + src_x];
427   state[src_y * width + src_x] = state[dst_y * width + dst_x];
428   state[dst_y * width + dst_x] = swap;
429
430   if (draw_p)
431     {
432       draw_piece(dpy, window, src_x, src_y, 0);
433       draw_piece(dpy, window, dst_x, dst_y, 0);
434       XSync(dpy, False);
435     }
436 }
437
438
439 static void
440 shuffle(Display *dpy, Window window, Bool draw_p)
441 {
442   struct piece *p1, *p2;
443   int src_x, src_y, dst_x = -1, dst_y = -1;
444
445  AGAIN:
446   p1 = p2 = 0;
447   src_x = random() % width;
448   src_y = random() % height;
449
450   get_piece(src_x, src_y, &p1, 0);
451
452   /* Pick random coordinates until we find one that has the same kind of
453      piece as the first one we picked.  Note that it's possible for there
454      to be only one piece of a particular shape on the board (this commonly
455      happens with the corner pieces.)
456    */
457   while (p1 != p2)
458     {
459       dst_x = random() % width;
460       dst_y = random() % height;
461       get_piece(dst_x, dst_y, &p2, 0);
462     }
463
464   if (src_x == dst_x && src_y == dst_y)
465     goto AGAIN;
466
467   swap_pieces(dpy, window, src_x, src_y, dst_x, dst_y, draw_p);
468 }
469
470
471 static void
472 shuffle_all(Display *dpy, Window window)
473 {
474   int i = (width * height * 10);
475   while (i > 0)
476     {
477       shuffle(dpy, window, False);
478       i--;
479     }
480 }
481
482 static void
483 unshuffle(Display *dpy, Window window)
484 {
485   int i;
486   for (i = 0; i < width * height * 4; i++)
487     {
488       int x = random() % width;
489       int y = random() % height;
490       int x2 = state[y * width + x].x;
491       int y2 = state[y * width + x].y;
492       if (x != x2 || y != y2)
493         {
494           swap_pieces(dpy, window, x, y, x2, y2, True);
495           break;
496         }
497     }
498 }
499
500 static void
501 clear_all(Display *dpy, Window window)
502 {
503   int n = width * height;
504   while (n > 0)
505     {
506       int x = random() % width;
507       int y = random() % height;
508       XPoint *p = &state[y * width + x];
509       if (p->x == -1)
510         continue;
511       draw_piece(dpy, window, p->x, p->y, 2);
512       XSync(dpy, False);
513       usleep(1000);
514       p->x = p->y = -1;
515       n--;
516     }
517 }
518
519 static Bool
520 done(void)
521 {
522   int x, y;
523   for (y = 0; y < height; y++)
524     for (x = 0; x < width; x++)
525       {
526         int x2 = state[y * width + x].x;
527         int y2 = state[y * width + x].y;
528         if (x != x2 || y != y2)
529           return False;
530       }
531   return True;
532 }
533
534
535 \f
536 char *progclass = "Jigsaw";
537
538 char *defaults [] = {
539   ".background:         Black",
540   ".foreground:         Gray40",
541   "*delay:              70000",
542   "*delay2:             5",
543 #ifdef __sgi    /* really, HAVE_READ_DISPLAY_EXTENSION */
544   "*visualID:           Best",
545 #endif
546   0
547 };
548
549 XrmOptionDescRec options [] = {
550   { "-delay",           ".delay",               XrmoptionSepArg, 0 },
551   { "-delay2",          ".delay2",              XrmoptionSepArg, 0 },
552   { 0, 0, 0, 0 }
553 };
554
555 void
556 screenhack (Display *dpy, Window window)
557 {
558   int delay = get_integer_resource("delay", "Integer");
559   int delay2 = get_integer_resource("delay2", "Integer");
560
561   init_images(dpy, window);
562
563   while (1)
564     {
565       int x, y;
566       jigsaw_init (dpy, window);
567       shuffle_all(dpy, window);
568
569       for (y = 0; y < height; y++)
570         for (x = 0; x < width; x++)
571           draw_piece(dpy, window, x, y, 0);
572
573       while (!done())
574         {
575           unshuffle(dpy, window);
576           XSync (dpy, False);
577           screenhack_handle_events (dpy);
578           if (delay) usleep (delay);
579         }
580
581       screenhack_handle_events (dpy);
582       if (delay2)
583         usleep (delay2 * 1000000);
584
585       clear_all(dpy, window);
586     }
587 }