4946aeefde273ff2a7beb79a45eff9f87db9ed79
[xscreensaver] / hacks / bubbles.c
1 /* bubbles.c - frying pan / soft drink in a glass simulation */
2
3 /*$Id: bubbles.c,v 1.14 1998/06/04 22:55:09 jwz Exp $*/
4
5 /*
6  *  Copyright (C) 1995-1996 James Macnicol
7  *
8  * Permission to use, copy, modify, distribute, and sell this software and its
9  * documentation for any purpose is hereby granted without fee, provided that
10  * the above copyright notice appear in all copies and that both that
11  * copyright notice and this permission notice appear in supporting
12  * documentation.  No representations are made about the suitability of this
13  * software for any purpose.  It is provided "as is" without express or 
14  * implied warranty.
15  */
16
17 /*
18  * I got my original inspiration for this by looking at the bottom of a 
19  * frying pan while something was cooking and watching the little bubbles
20  * coming off the bottom of the pan as the oil was boiling joining together
21  * to form bigger bubbles and finally to *pop* and disappear.  I had some
22  * time on my hands so I wrote this little xscreensaver module to imitate
23  * it.  Now that it's done it reminds me more of the bubbles you get in
24  * a glass of fizzy soft drink.....
25  *
26  * The problem seemed to be that the position/size etc. of all the bubbles
27  * on the screen had to be remembered and searched through to find when
28  * bubbles hit each other and combined.  To do this more efficiently, the
29  * window/screen is divided up into a square mesh of side length mesh_length
30  * and separate lists of bubbles contained in each cell of the mesh are
31  * kept.  Only the cells in the immediate vicinity of the bubble in question
32  * are searched.  This should make things more efficient although the whole
33  * thing seems to use up too much CPU, but then I'm using an ancient PC so
34  * perhaps it's not surprising .
35  * (Six months after I wrote the above I now have a Pentium with PCI graphics 
36  * and things are _much_ nicer.)
37  *
38  * Author:           James Macnicol 
39  * Internet E-mail : J.Macnicol@student.anu.edu.au
40  */
41
42 #include <math.h>
43 #include "screenhack.h"
44 #include "bubbles.h"
45
46 #include <limits.h>
47
48 #include <stdio.h>
49 #include <string.h>
50
51 #ifndef VMS
52 # include <sys/wait.h>
53 #else /* VMS */
54 # if __DECC_VER >= 50200000
55 #  include <sys/wait.h>
56 # endif
57 #endif /* VMS */
58
59 #ifdef HAVE_UNISTD_H
60 # include <unistd.h>
61 #endif
62 #include "yarandom.h"
63
64 #ifdef HAVE_XPM
65 # include <X11/xpm.h>
66 #endif
67
68 /* 
69  * Public variables 
70  */
71
72 extern void init_default_bubbles(void);
73 extern int num_default_bubbles;
74 extern char **default_bubbles[];
75
76 char *progclass = "Bubbles";
77
78 char *defaults [] = {
79   ".background:         black",
80   ".foreground:         white",
81   "*simple:             false",
82   "*broken:             false",
83   "*delay:              800",
84   "*quiet:              false", 
85   "*nodelay:            false",
86   "*3D:                 false",
87   0
88 };
89
90 XrmOptionDescRec options [] = {
91   { "-simple",          ".simple",      XrmoptionNoArg, "true" },
92 #ifdef HAVE_XPM
93   { "-broken",          ".broken",      XrmoptionNoArg, "true" },
94 #endif /* HAVE_XPM */
95   { "-quiet",           ".quiet",       XrmoptionNoArg, "true" },
96   { "-nodelay",         ".nodelay",     XrmoptionNoArg, "true" },
97   { "-3D",          ".3D",      XrmoptionNoArg, "true" },
98   { "-delay",           ".delay",       XrmoptionSepArg, 0 },
99   { 0, 0, 0, 0 }
100 };
101
102 /* 
103  * Private variables 
104  */
105
106 static Bubble **mesh;
107 static int mesh_length;
108 static int mesh_width;
109 static int mesh_height;
110 static int mesh_cells;
111
112 static int **adjacent_list;
113
114 static int screen_width;
115 static int screen_height;
116 static int screen_depth;
117 static unsigned int default_fg_pixel, default_bg_pixel;
118 /* 
119  * I know it's not elegant to save this stuff in global variables
120  * but we need it for the signal handler.
121  */
122 static Display *defdsp;
123 static Window defwin;
124 static Colormap defcmap;
125 static Visual *defvisual;
126
127 /* For simple mode only */
128 static int bubble_min_radius;
129 static int bubble_max_radius;
130 static long *bubble_areas;
131 static GC draw_gc, erase_gc;
132
133 #ifdef HAVE_XPM
134 static int num_bubble_pixmaps;
135 static Bubble_Step **step_pixmaps;
136 #endif /* HAVE_XPM */
137
138 /* Options stuff */
139 #ifdef HAVE_XPM
140 static Bool simple = False;
141 #else
142 static Bool simple = True;
143 #endif
144 static Bool broken = False;
145 static Bool quiet = False;
146 static Bool threed = False;
147 static int delay;
148
149 /* 
150  * To prevent forward references, some stuff is up here 
151  */
152
153 static long
154 calc_bubble_area(int r)
155 /* Calculate the area of a bubble of radius r */
156 {
157 #ifdef DEBUG
158   printf("%d %g\n", r,
159          10.0 * PI * (double)r * (double)r * (double)r);
160 #endif /* DEBUG */
161   if (threed)
162     return (long)(10.0 * PI * (double)r * (double)r * (double)r);
163   else
164     return (long)(10.0 * PI * (double)r * (double)r);
165 }
166
167 static void *
168 xmalloc(size_t size)
169 /* Safe malloc */
170 {
171   void *ret;
172
173   if ((ret = malloc(size)) == NULL) {
174     fprintf(stderr, "%s: out of memory\n", progname);
175     exit(1);
176   }
177   return ret;
178 }
179
180 #ifdef DEBUG
181 static void 
182 die_bad_bubble(Bubble *bb)
183 /* This is for use with GDB */
184 {
185   fprintf(stderr, "Bad bubble detected at 0x%x!\n", (int)bb);
186   exit(1);
187 }
188 #endif
189
190 static int
191 null_bubble(Bubble *bb)
192 /* Returns true if the pointer passed is NULL.  If not then this checks to
193 see if the bubble is valid (i.e. the (x,y) position is valid and the magic
194 number is set correctly.  This only a sanity check for debugging and is
195 turned off if DEBUG isn't set. */
196 {
197   if (bb == (Bubble *)NULL)
198     return 1;
199 #ifdef DEBUG
200   if ((bb->cell_index < 0) || (bb->cell_index > mesh_cells)) {
201     fprintf(stderr, "cell_index = %d\n", bb->cell_index);
202     die_bad_bubble(bb);
203   }
204   if (bb->magic != BUBBLE_MAGIC)  {
205     fprintf(stderr, "Magic = %d\n", bb->magic);
206     die_bad_bubble(bb);
207   }
208   if (simple) {
209     if ((bb->x < 0) || (bb->x > screen_width) ||
210         (bb->y < 0) || (bb->y > screen_height) ||
211         (bb->radius < bubble_min_radius) || (bb->radius >
212                                              bubble_max_radius)) {
213       fprintf(stderr,
214               "radius = %d, x = %d, y = %d, magic = %d, cell index = %d\n",
215               bb->radius, bb->x, bb->y, bb->magic, bb->cell_index);
216       die_bad_bubble(bb);  
217     }
218 #ifdef HAVE_XPM
219   } else {
220     if ((bb->x < 0) || (bb->x > screen_width) ||
221         (bb->y < 0) || (bb->y > screen_height) ||
222         (bb->radius < step_pixmaps[0]->radius) || 
223         (bb->radius > step_pixmaps[num_bubble_pixmaps-1]->radius)) {
224       fprintf(stderr,
225               "radius = %d, x = %d, y = %d, magic = %d, cell index = %d\n",
226               bb->radius, bb->x, bb->y, bb->magic, bb->cell_index);
227       die_bad_bubble(bb);  
228     }
229 #endif /* HAVE_XPM */
230   }
231 #endif /* DEBUG */
232   return 0;
233 }
234
235 #ifdef DEBUG
236 static void 
237 print_bubble_list(Bubble *bb)
238 /* Print list of where all the bubbles are.  For debugging purposes only. */
239 {
240   if (! null_bubble(bb)) {
241     printf("  (%d, %d) %d\n", bb->x, bb->y, bb->radius);
242     print_bubble_list(bb->next);
243   }
244 }
245 #endif /* DEBUG */
246
247 static void 
248 add_bubble_to_list(Bubble **list, Bubble *bb)
249 /* Take a pointer to a list of bubbles and stick bb at the head of the
250  list. */
251 {
252   Bubble *head = *list;
253
254   if (null_bubble(head)) {
255     bb->prev = (Bubble *)NULL;
256     bb->next = (Bubble *)NULL;
257   } else {
258     bb->next = head;
259     bb->prev = (Bubble *)NULL;
260     head->prev = bb;
261   }
262   *list = bb;
263 }
264
265
266 /* 
267  * Mesh stuff 
268  */
269
270
271 static void 
272 init_mesh (void)
273 /* Setup the mesh of bubbles */
274 {
275   int i;
276
277   mesh = (Bubble **)xmalloc(mesh_cells * sizeof(Bubble *));
278   for (i = 0; i < mesh_cells; i++)
279     mesh[i] = (Bubble *)NULL;
280 }
281
282 static int
283 cell_to_mesh(int x, int y)
284 /* convert cell coordinates to mesh index */
285 {
286 #ifdef DEBUG
287   if ((x < 0) || (y < 0)) {
288     fprintf(stderr, "cell_to_mesh: x = %d, y = %d\n", x, y);
289     exit(1);
290   }
291 #endif
292   return ((mesh_width * y) + x);
293 }
294
295 static void 
296 mesh_to_cell(int mi, int *cx, int *cy)
297 /* convert mesh index into cell coordinates */
298 {
299   *cx = mi % mesh_width;
300   *cy = mi / mesh_width;
301 }
302
303 static int
304 pixel_to_mesh(int x, int y)
305 /* convert screen coordinates into mesh index */
306 {
307   return cell_to_mesh((x / mesh_length), (y / mesh_length));
308 }
309
310 static int
311 verify_mesh_index(int x, int y)
312 /* check to see if (x,y) is in the mesh */
313 {
314   if ((x < 0) || (y < 0) || (x >= mesh_width) || (y >= mesh_height))
315     return (-1);
316   return (cell_to_mesh(x, y));
317 }
318
319 #ifdef DEBUG
320 static void 
321 print_adjacents(int *adj)
322 /* Print a list of the cells calculated above.  For debugging only. */
323 {
324   int i;
325
326   printf("(");
327   for (i = 0; i < 8; i++)
328     printf("%d ", adj[i]);
329   printf(")\n");
330 }
331 #endif /* DEBUG */
332
333 static void 
334 add_to_mesh(Bubble *bb)
335 /* Add the given bubble to the mesh by sticking it on the front of the
336 list.  bb is already allocated so no need to malloc() anything, just
337 adjust pointers. */
338 {
339 #ifdef DEBUG
340   if (null_bubble(bb)) {
341     fprintf(stderr, "Bad bubble passed to add_to_mesh()!\n");
342     exit(1);
343   }
344 #endif /* DEBUG */
345
346   add_bubble_to_list(&mesh[bb->cell_index], bb);
347 }
348
349 #ifdef DEBUG
350 static void 
351 print_mesh (void)
352 /* Print the contents of the mesh */
353 {
354   int i;
355
356   for (i = 0; i < mesh_cells; i++) {
357     if (! null_bubble(mesh[i])) {
358       printf("Mesh cell %d\n", i);
359       print_bubble_list(mesh[i]);
360     }
361   }
362 }
363
364 static void 
365 valid_mesh (void)
366 /* Check to see if the mesh is Okay.  For debugging only. */
367 {
368   int i;
369   Bubble *b;
370
371   for (i = 0; i < mesh_cells; i++) {
372     b = mesh[i];
373     while (! null_bubble(b))
374       b = b->next;
375   }
376 }
377
378 static int
379 total_bubbles (void)
380 /* Count how many bubbles there are in total.  For debugging only. */
381 {
382   int rv = 0;
383   int i;
384   Bubble *b;
385
386   for (i = 0; i < mesh_cells; i++) {
387     b = mesh[i];
388     while (! null_bubble(b)) {
389       rv++;
390       b = b->next;
391     } 
392   }
393
394   return rv;
395 }
396 #endif /* DEBUG */
397
398 static void 
399 calculate_adjacent_list (void)
400 /* Calculate the list of cells adjacent to a particular cell for use
401    later. */
402 {
403   int i; 
404   int ix, iy;
405
406   adjacent_list = (int **)xmalloc(mesh_cells * sizeof(int *));
407   for (i = 0; i < mesh_cells; i++) {
408     adjacent_list[i] = (int *)xmalloc(9 * sizeof(int));
409     mesh_to_cell(i, &ix, &iy);
410     adjacent_list[i][0] = verify_mesh_index(--ix, --iy);
411     adjacent_list[i][1] = verify_mesh_index(++ix, iy);
412     adjacent_list[i][2] = verify_mesh_index(++ix, iy);
413     adjacent_list[i][3] = verify_mesh_index(ix, ++iy);
414     adjacent_list[i][4] = verify_mesh_index(ix, ++iy);
415     adjacent_list[i][5] = verify_mesh_index(--ix, iy);
416     adjacent_list[i][6] = verify_mesh_index(--ix, iy);
417     adjacent_list[i][7] = verify_mesh_index(ix, --iy);
418     adjacent_list[i][8] = i;
419   }
420 }
421
422 static void
423 adjust_areas (void)
424 /* Adjust areas of bubbles so we don't get overflow in weighted_mean() */
425 {
426   double maxvalue;
427   long maxarea;
428   long factor;
429   int i;
430
431 #ifdef HAVE_XPM
432   if (simple)
433     maxarea = bubble_areas[bubble_max_radius+1];
434   else
435     maxarea = step_pixmaps[num_bubble_pixmaps]->area;
436 #else
437   maxarea = bubble_areas[bubble_max_radius+1];
438 #endif /* HAVE_XPM */
439   maxvalue = (double)screen_width * 2.0 * (double)maxarea;
440   factor = (long)ceil(maxvalue / (double)LONG_MAX);
441   if (factor > 1) {
442     /* Overflow will occur in weighted_mean().  We must divide areas
443        each by factor so it will never do so. */
444 #ifdef HAVE_XPM
445     if (simple) {
446       for (i = bubble_min_radius; i <= bubble_max_radius+1; i++) {
447         bubble_areas[i] /= factor;
448         if (bubble_areas[i] == 0)
449           bubble_areas[i] = 1;
450       }
451     } else {
452       for (i = 0; i <= num_bubble_pixmaps; i++) {
453 #ifdef DEBUG
454         printf("area = %ld", step_pixmaps[i]->area);
455 #endif /* DEBUG */
456         step_pixmaps[i]->area /= factor;
457         if (step_pixmaps[i]->area == 0)
458           step_pixmaps[i]->area = 1;
459 #ifdef DEBUG
460         printf("-> %ld\n", step_pixmaps[i]->area);
461 #endif /* DEBUG */
462       }
463     }
464 #else
465     for (i = bubble_min_radius; i <= bubble_max_radius+1; i++) {
466       bubble_areas[i] /= factor;
467       if (bubble_areas[i] == 0)
468         bubble_areas[i] = 1;
469     }
470 #endif /* HAVE_XPM */
471   }
472 #ifdef DEBUG
473   printf("maxarea = %ld\n", maxarea);
474   printf("maxvalue = %g\n", maxvalue);
475   printf("LONG_MAX = %ld\n", LONG_MAX);
476   printf("factor = %ld\n", factor);
477 #endif /* DEBUG */
478 }
479
480 /* 
481  * Bubbles stuff 
482  */
483
484 static Bubble *
485 new_bubble (void)
486 /* Add a new bubble at some random position on the screen of the smallest
487 size. */
488 {
489   Bubble *rv = (Bubble *)xmalloc(sizeof(Bubble));
490
491   /* Can't use null_bubble() here since magic number hasn't been set */
492   if (rv == (Bubble *)NULL) {
493     fprintf(stderr, "Ran out of memory!\n");
494     exit(1);
495   }
496
497   if (simple) {
498     rv->radius = bubble_min_radius;
499     rv->area = bubble_areas[bubble_min_radius];
500 #ifdef HAVE_XPM
501   } else {
502     rv->step = 0;
503     rv->radius = step_pixmaps[0]->radius;
504     rv->area = step_pixmaps[0]->area;
505 #endif /* HAVE_XPM */
506   }
507   rv->visible = 0;
508   rv->magic = BUBBLE_MAGIC;
509   rv->x = random() % screen_width;
510   rv->y = random() % screen_height;
511   rv->cell_index = pixel_to_mesh(rv->x, rv->y);
512
513   return rv;
514 }
515
516 static void 
517 show_bubble(Bubble *bb)
518 /* paint the bubble on the screen */
519 {
520   if (null_bubble(bb)) {
521     fprintf(stderr, "NULL bubble passed to show_bubble\n");
522     exit(1);
523   }
524
525   if (! bb->visible) {
526     bb->visible = 1;
527
528     if (simple) {
529       XDrawArc(defdsp, defwin, draw_gc, (bb->x - bb->radius),
530                (bb->y - bb->radius), bb->radius*2, bb->radius*2, 0,
531                360*64);  
532     } else {
533 #ifdef HAVE_XPM
534       XSetClipOrigin(defdsp, step_pixmaps[bb->step]->draw_gc, 
535                      (bb->x - bb->radius),
536                      (bb->y - bb->radius));
537       
538       XCopyArea(defdsp, step_pixmaps[bb->step]->ball, defwin, 
539                 step_pixmaps[bb->step]->draw_gc,
540                 0, 0, (bb->radius * 2), 
541                 (bb->radius * 2),  
542                 (bb->x - bb->radius),
543                 (bb->y - bb->radius));
544 #endif /* HAVE_XPM */
545     }
546   }
547 }
548
549 static void 
550 hide_bubble(Bubble *bb)
551 /* erase the bubble */
552 {
553   if (null_bubble(bb)) {
554     fprintf(stderr, "NULL bubble passed to hide_bubble\n");
555     exit(1);
556   }
557
558   if (bb->visible) {
559     bb->visible = 0;
560
561     if (simple) {
562       XDrawArc(defdsp, defwin, erase_gc, (bb->x - bb->radius),
563                (bb->y - bb->radius), bb->radius*2, bb->radius*2, 0,
564                360*64);
565     } else {
566 #ifdef HAVE_XPM
567       if (! broken) {
568         XSetClipOrigin(defdsp, step_pixmaps[bb->step]->erase_gc, 
569                        (bb->x - bb->radius), (bb->y - bb->radius));
570         
571         XFillRectangle(defdsp, defwin, step_pixmaps[bb->step]->erase_gc,
572                        (bb->x - bb->radius),
573                        (bb->y - bb->radius),
574                        (bb->radius * 2),
575                        (bb->radius * 2));
576       }
577 #endif /* HAVE_XPM */
578     }
579   }
580 }
581
582 static void 
583 delete_bubble_in_mesh(Bubble *bb, int keep_bubble)
584 /* Delete an individual bubble, adjusting list of bubbles around it.
585    If keep_bubble is true then the bubble isn't actually deleted.  We
586    use this to allow bubbles to change mesh cells without reallocating,
587    (it needs this when two bubbles collide and the centre position is
588    recalculated, and this may stray over a mesh boundary). */
589 {
590   if ((!null_bubble(bb->prev)) && (!null_bubble(bb->next))) {
591     bb->prev->next = bb->next;
592     bb->next->prev = bb->prev;
593   } else if ((!null_bubble(bb->prev)) &&
594              (null_bubble(bb->next))) {
595     bb->prev->next = (Bubble *)NULL;
596     bb->next = mesh[bb->cell_index];
597   } else if ((null_bubble(bb->prev)) &&
598              (!null_bubble(bb->next))) {
599     bb->next->prev = (Bubble *)NULL;
600     mesh[bb->cell_index] = bb->next;
601     bb->next = mesh[bb->cell_index];
602   } else {
603     /* Only item on list */
604     mesh[bb->cell_index] = (Bubble *)NULL;
605   }              
606   if (! keep_bubble)
607     free(bb);
608 }
609
610 static unsigned long 
611 ulongsqrint(int x)
612 /* Saves ugly inline code */
613 {
614   return ((unsigned long)x * (unsigned long)x);
615 }
616
617 static Bubble *
618 get_closest_bubble(Bubble *bb)
619 /* Find the closest bubble touching the this bubble, NULL if none are
620    touching. */
621 {
622   Bubble *rv = (Bubble *)NULL;
623   Bubble *tmp;
624   unsigned long separation2, touchdist2;
625   int dx, dy;
626   unsigned long closest2 = ULONG_MAX;
627   int i;
628
629 #ifdef DEBUG 
630   if (null_bubble(bb)) {
631     fprintf(stderr, "NULL pointer 0x%x passed to get_closest_bubble()!", 
632             (int)bb);
633     exit(1);
634   }
635 #endif /* DEBUG */
636
637   for (i = 0; i < 9; i++) {
638     /* There is a bug here where bb->cell_index is negaitve.. */
639 #ifdef DEBUG
640     if ((bb->cell_index < 0) || (bb->cell_index >= mesh_cells)) {
641       fprintf(stderr, "bb->cell_index = %d\n", bb->cell_index);
642       exit(1);
643     }
644 #endif /* DEBUG */
645 /*    printf("%d,", bb->cell_index); */
646     if (adjacent_list[bb->cell_index][i] != -1) {
647       tmp = mesh[adjacent_list[bb->cell_index][i]];
648       while (! null_bubble(tmp)) {
649         if (tmp != bb) {
650           dx = tmp->x - bb->x;
651           dy = tmp->y - bb->y;
652           separation2 = ulongsqrint(dx) + ulongsqrint(dy);
653           /* Add extra leeway so circles _never_ overlap */
654           touchdist2 = ulongsqrint(tmp->radius + bb->radius + 2);
655           if ((separation2 <= touchdist2) && (separation2 <
656                                               closest2)) {
657             rv = tmp;
658             closest2 = separation2;
659           }
660         }
661         tmp = tmp->next;
662       }
663     }
664   }
665
666   return rv;
667 }
668
669 #ifdef DEBUG
670 static void
671 ldr_barf (void)
672 {
673 }
674 #endif /* DEBUG */
675
676 static long
677 long_div_round(long num, long dem)
678 {
679   long divvie, moddo;
680
681 #ifdef DEBUG
682   if ((num < 0) || (dem < 0)) {
683     fprintf(stderr, "long_div_round: %ld, %ld\n", num, dem);
684     ldr_barf();
685     exit(1);
686   }
687 #endif /* DEBUG */
688
689   divvie = num / dem;
690   moddo = num % dem;
691   if (moddo > (dem / 2))
692     ++divvie;
693
694 #ifdef DEBUG
695   if ((divvie < 0) || (moddo < 0)) {
696     fprintf(stderr, "long_div_round: %ld, %ld\n", divvie, moddo);
697     ldr_barf();
698     exit(1);
699   }
700 #endif /* DEBUG */
701
702   return divvie;
703 }
704
705 static int
706 weighted_mean(int n1, int n2, long w1, long w2)
707 /* Mean of n1 and n2 respectively weighted by weights w1 and w2. */
708 {
709 #ifdef DEBUG
710   if ((w1 <= 0) || (w2 <= 0)) {
711     fprintf(stderr,
712             "Bad weights passed to weighted_mean() - (%d, %d, %ld, %ld)!\n",
713             n1, n2, w1, w2);
714     exit(1);
715   }
716 #endif /* DEBUG */
717   return ((int)long_div_round((long)n1 * w1 + (long)n2 * w2,
718                            w1 + w2));
719 }
720
721 static int
722 bubble_eat(Bubble *diner, Bubble *food)
723 /* The diner eats the food.  Returns true (1) if the diner still exists */
724
725   int i;
726   int newmi;
727
728 #ifdef DEBUG
729   if ((null_bubble(diner)) || (null_bubble(food))) {
730     fprintf(stderr, "Bad bubbles passed to bubble_eat()!\n");
731     exit(1);
732   }
733 #endif /* DEBUG */
734
735   /* We hide the diner even in the case that it doesn't grow so that
736      if the food overlaps its boundary it is replaced. This could
737      probably be solved by letting bubbles eat others which are close
738      but not quite touching.  It's probably worth it, too, since we
739      would then not have to redraw bubbles which don't change in
740      size. */
741
742   hide_bubble(diner);
743   hide_bubble(food);
744   diner->x = weighted_mean(diner->x, food->x, diner->area, food->area);
745   diner->y = weighted_mean(diner->y, food->y, diner->area, food->area);
746   newmi = pixel_to_mesh(diner->x, diner->y);
747   diner->area += food->area;
748   delete_bubble_in_mesh(food, DELETE_BUBBLE);
749
750   if ((simple) && (diner->area > bubble_areas[bubble_max_radius])) {
751     delete_bubble_in_mesh(diner, DELETE_BUBBLE);
752     return 0;
753   }
754 #ifdef HAVE_XPM
755   if ((! simple) && (diner->area > 
756                      step_pixmaps[num_bubble_pixmaps]->area)) {
757     delete_bubble_in_mesh(diner, DELETE_BUBBLE);
758     return 0;
759   }
760 #endif /* HAVE_XPM */
761
762   if (simple) {
763     if (diner->area > bubble_areas[diner->radius + 1]) {
764       /* Move the bubble to a new radius */
765       i = diner->radius;
766       while (diner->area > bubble_areas[i+1])
767         ++i;
768       diner->radius = i;
769     }
770     show_bubble(diner);
771 #ifdef HAVE_XPM
772   } else {
773     if (diner->area > step_pixmaps[diner->step+1]->area) {
774       i = diner->step;
775       while (diner->area > step_pixmaps[i+1]->area)
776         ++i;
777       diner->step = i;
778       diner->radius = step_pixmaps[diner->step]->radius;
779     }
780     show_bubble(diner);
781 #endif /* HAVE_XPM */
782   }
783
784   /* Now adjust locations and cells if need be */
785   if (newmi != diner->cell_index) {
786     delete_bubble_in_mesh(diner, KEEP_BUBBLE);
787     diner->cell_index = newmi;
788     add_to_mesh(diner);
789   }
790
791   return 1;
792 }
793
794 static int
795 merge_bubbles(Bubble *b1, Bubble *b2)
796 /* These two bubbles merge into one.  If the first one wins out return
797 1 else return 2.  If there is no winner (it explodes) then return 0 */
798 {
799   int b1size, b2size;
800
801   b1size = b1->area;
802   b2size = b2->area;
803
804 #ifdef DEBUG
805   if ((null_bubble(b1) || null_bubble(b2))) {
806     fprintf(stderr, "NULL bubble passed to merge_bubbles()!\n");
807     exit(1);
808   }
809 #endif /* DEBUG */
810
811   if (b1 == b2) {
812     hide_bubble(b1);
813     delete_bubble_in_mesh(b1, DELETE_BUBBLE);
814     return 0;
815   }
816
817   if (b1size > b2size) {
818     switch (bubble_eat(b1, b2)) {
819     case 0:
820       return 0;
821       break;
822     case 1:
823       return 1;
824       break;
825     default:
826       break;
827     }
828   } else if (b1size < b2size) {
829     switch (bubble_eat(b2, b1)) {
830     case 0:
831       return 0;
832       break;
833     case 1:
834       return 2;
835       break;
836     default:
837       break;
838     }
839   } else {
840     if ((random() % 2) == 0) {
841       switch (bubble_eat(b1, b2)) {
842       case 0:
843         return 0;
844         break;
845       case 1:
846         return 1;
847         break;
848       default:
849         break;
850       }
851     } else {
852       switch (bubble_eat(b2, b1)) {
853       case 0:
854         return 0;
855         break;
856       case 1:
857         return 2;
858         break;
859       default:
860         break;
861       }
862     }
863   }
864   fprintf(stderr, "An error occurred in merge_bubbles()\n");
865   exit(1);
866 }
867
868 static void 
869 insert_new_bubble(Bubble *tmp)
870 /* Calculates which bubbles are eaten when a new bubble tmp is
871    inserted.  This is called recursively in case when a bubble grows
872    it eats others.  Careful to pick out disappearing bubbles. */
873 {
874   Bubble *nextbub;
875   Bubble *touch;
876
877 #ifdef DEBUG
878   if (null_bubble(tmp)) {
879     fprintf(stderr, "Bad bubble passed to insert_new_bubble()!\n");
880     exit(1);
881   }
882 #endif /* DEBUG */
883   
884   nextbub = tmp;
885   touch = get_closest_bubble(nextbub);
886   while (! null_bubble(touch)) {
887     switch (merge_bubbles(nextbub, touch)) {
888     case 2:
889       /* touch ate nextbub and survived */
890       nextbub = touch;
891       break;
892     case 1:
893       /* nextbub ate touch and survived */
894       break;
895     case 0:
896       /* somebody ate someone else but they exploded */
897       nextbub = (Bubble *)NULL;
898       break;
899     default:
900       /* something went wrong */
901       fprintf(stderr, "Error occurred in insert_new_bubble()\n");
902       exit(1);
903     }
904     /* Check to see if there are any other bubbles still in the area
905        and if we need to do this all over again for them. */
906     if (! null_bubble(nextbub))
907       touch = get_closest_bubble(nextbub);
908     else
909       touch = (Bubble *)NULL;
910   }
911 }
912
913 #ifdef DEBUG
914 static int
915 get_length_of_bubble_list(Bubble *bb)
916 {
917   Bubble *tmp = bb;
918   int rv = 0;
919
920   while (! null_bubble(tmp)) {
921     rv++;
922     tmp = tmp->next;
923   }
924
925   return rv;
926 }
927 #endif /* DEBUG */
928
929 /*
930  * Pixmap stuff used regardless of whether file I/O is available.  Must
931  * still check for XPM, though!
932  */
933
934 #ifdef HAVE_XPM
935
936 /*
937  * Pixmaps without file I/O (but do have XPM)
938  */
939
940 static void 
941 pixmap_sort(Bubble_Step **head, int numelems)
942 /* Couldn't get qsort to work right with this so I wrote my own.  This puts
943 the numelems length array with first element at head into order of radius.
944 */
945 {
946   Bubble_Step tmp;
947   Bubble_Step *least = 0;
948   int minradius = INT_MAX;
949   int i;
950
951   for (i = 0; i < numelems; i++) {
952     if (head[i]->radius < minradius) {
953       least = head[i];
954       minradius = head[i]->radius;
955     }
956   }
957   if (*head != least) {
958     memcpy(&tmp, least, sizeof(Bubble_Step));
959     memcpy(least, *head, sizeof(Bubble_Step));
960     memcpy(*head, &tmp, sizeof(Bubble_Step));
961   }
962
963   if (numelems > 2)
964     pixmap_sort(&head[1], numelems-1);
965 }
966
967 static int
968 extrapolate(int i1, int i2)
969 {
970   return (i2 + (i2 - i1));
971 }
972
973 static void 
974 make_pixmap_array(Bubble_Step *list)
975 /* From a linked list of bubbles construct the array step_pixmaps */
976 {
977   Bubble_Step *tmp = list;
978   int ind;
979 #ifdef DEBUG
980   int prevrad = -1;
981 #endif
982   
983   if (list == (Bubble_Step *)NULL) {
984     fprintf(stderr, "NULL list passed to make_pixmap_array\n");
985     exit(1);
986   }
987
988   num_bubble_pixmaps = 1;
989   while(tmp->next != (Bubble_Step *)NULL) {
990     tmp = tmp->next;
991     ++num_bubble_pixmaps;
992   }
993
994   if (num_bubble_pixmaps < 2) {
995     fprintf(stderr, "Must be at least two bubbles in file\n");
996     exit(1);
997   }
998
999   step_pixmaps = (Bubble_Step **)xmalloc((num_bubble_pixmaps + 1) * 
1000                                          sizeof(Bubble_Step *));
1001
1002   /* Copy them blindly into the array for sorting. */
1003   ind = 0;
1004   tmp = list;
1005   do {
1006     step_pixmaps[ind++] = tmp;
1007     tmp = tmp->next;
1008   } while(tmp != (Bubble_Step *)NULL);
1009
1010   /* We make another bubble beyond the ones with pixmaps so that the final
1011      bubble hangs around and doesn't pop immediately.  It's radius and area
1012      are found by extrapolating from the largest two bubbles with pixmaps. */
1013
1014   step_pixmaps[num_bubble_pixmaps] = 
1015     (Bubble_Step *)xmalloc(sizeof(Bubble_Step));
1016   step_pixmaps[num_bubble_pixmaps]->radius = INT_MAX;
1017
1018   pixmap_sort(step_pixmaps, (num_bubble_pixmaps + 1));
1019
1020 #ifdef DEBUG
1021   if (step_pixmaps[num_bubble_pixmaps]->radius != INT_MAX) {
1022     fprintf(stderr, "pixmap_sort() screwed up make_pixmap_array\n");
1023   }
1024 #endif /* DEBUG */
1025
1026   step_pixmaps[num_bubble_pixmaps]->radius = 
1027     extrapolate(step_pixmaps[num_bubble_pixmaps-2]->radius,
1028                 step_pixmaps[num_bubble_pixmaps-1]->radius);
1029   step_pixmaps[num_bubble_pixmaps]->area = 
1030     calc_bubble_area(step_pixmaps[num_bubble_pixmaps]->radius);
1031   
1032
1033 #ifdef DEBUG
1034   /* Now check for correct order */
1035   for (ind = 0; ind < num_bubble_pixmaps; ind++) {
1036     if (prevrad > 0) {
1037       if (step_pixmaps[ind]->radius < prevrad) {
1038         fprintf(stderr, "Pixmaps not in ascending order of radius\n");
1039         exit(1);
1040       }
1041     }
1042     prevrad = step_pixmaps[ind]->radius;
1043   }
1044 #endif /* DEBUG */
1045 }
1046
1047 static void
1048 make_pixmap_from_default(char **pixmap_data, Bubble_Step *bl)
1049 /* Read pixmap data which has been compiled into the program and a pointer
1050  to which has been passed. 
1051
1052  This is virtually copied verbatim from make_pixmap_from_file() above and
1053 changes made to either should be propagated onwards! */
1054 {
1055   int result;
1056   XGCValues gcv;
1057
1058 #ifdef DEBUG
1059   if (pixmap_data == (char **)0) {
1060     fprintf(stderr, "make_pixmap_from_default(): NULL passed\n");
1061     exit(1);
1062   }
1063 #endif
1064
1065   if (bl == (Bubble_Step *)NULL) {
1066     fprintf(stderr, "NULL pointer passed to make_pixmap()\n");
1067     exit(1);
1068   }
1069
1070   bl->xpmattrs.valuemask = 0;
1071
1072 #ifdef XpmCloseness
1073   bl->xpmattrs.valuemask |= XpmCloseness;
1074   bl->xpmattrs.closeness = 40000;
1075 #endif
1076 #ifdef XpmVisual
1077   bl->xpmattrs.valuemask |= XpmVisual;
1078   bl->xpmattrs.visual = defvisual;
1079 #endif
1080 #ifdef XpmDepth
1081   bl->xpmattrs.valuemask |= XpmDepth;
1082   bl->xpmattrs.depth = screen_depth;
1083 #endif
1084 #ifdef XpmColormap
1085   bl->xpmattrs.valuemask |= XpmColormap;
1086   bl->xpmattrs.colormap = defcmap;
1087 #endif
1088
1089
1090   /* This is the only line which is different from make_pixmap_from_file() */
1091   result = XpmCreatePixmapFromData(defdsp, defwin, pixmap_data, &bl->ball, 
1092                                    &bl->shape_mask, &bl->xpmattrs);
1093
1094   switch(result) {
1095   case XpmColorError:
1096     fprintf(stderr, "xpm: color substitution performed\n");
1097     /* fall through */
1098   case XpmSuccess:
1099     bl->radius = MAX(bl->xpmattrs.width, bl->xpmattrs.height) / 2;
1100     bl->area = calc_bubble_area(bl->radius);
1101     break;
1102   case XpmColorFailed:
1103     fprintf(stderr, "xpm: color allocation failed\n");
1104     exit(1);
1105   case XpmNoMemory:
1106     fprintf(stderr, "xpm: out of memory\n");
1107     exit(1);
1108   default:
1109     fprintf(stderr, "xpm: unknown error code %d\n", result);
1110     exit(1);
1111   }
1112   
1113   gcv.plane_mask = AllPlanes;
1114   gcv.foreground = default_fg_pixel;
1115   gcv.function = GXcopy;
1116   bl->draw_gc = XCreateGC (defdsp, defwin, GCForeground, &gcv);
1117   XSetClipMask(defdsp, bl->draw_gc, bl->shape_mask);
1118   
1119   gcv.foreground = default_bg_pixel;
1120   gcv.function = GXcopy;
1121   bl->erase_gc = XCreateGC (defdsp, defwin, GCForeground, &gcv);
1122   XSetClipMask(defdsp, bl->erase_gc, bl->shape_mask);  
1123 }
1124
1125 static void 
1126 default_to_pixmaps (void)
1127 /* Make pixmaps out of default ball data stored in bubbles_default.c */
1128 {
1129   int i;
1130   Bubble_Step *pixmap_list = (Bubble_Step *)NULL;
1131   Bubble_Step *newpix, *tmppix;
1132   char **pixpt;
1133
1134   init_default_bubbles();
1135
1136   for (i = 0; i < num_default_bubbles; i++) {
1137     pixpt = default_bubbles[i];
1138     newpix = (Bubble_Step *)xmalloc(sizeof(Bubble_Step));
1139     make_pixmap_from_default(pixpt, newpix);
1140     /* Now add to list */
1141     if (pixmap_list == (Bubble_Step *)NULL) {
1142       pixmap_list = newpix;
1143     } else {
1144       tmppix = pixmap_list;
1145       while (tmppix->next != (Bubble_Step *)NULL)
1146         tmppix = tmppix->next;
1147       tmppix->next = newpix;
1148     }
1149     newpix->next = (Bubble_Step *)NULL;
1150   }
1151   
1152   /* Finally construct step_pixmaps[] */
1153   make_pixmap_array(pixmap_list);
1154 }
1155
1156 #endif /* HAVE_XPM */
1157
1158
1159 /* 
1160  * Main stuff 
1161  */
1162
1163
1164 static void 
1165 get_resources(Display *dpy, Window window)
1166 /* Get the appropriate X resources and warn about any inconsistencies. */
1167 {
1168   Bool nodelay;
1169   XWindowAttributes xgwa;
1170   Colormap cmap;
1171   XGetWindowAttributes (dpy, window, &xgwa);
1172   cmap = xgwa.colormap;
1173
1174   threed = get_boolean_resource("3D", "Boolean");
1175   quiet = get_boolean_resource("quiet", "Boolean");
1176   simple = get_boolean_resource("simple", "Boolean");
1177   /* Forbid rendered bubbles on monochrome displays */
1178   if ((mono_p) && (! simple)) {
1179     if (! quiet)
1180       fprintf(stderr,
1181               "Rendered bubbles not supported on monochrome displays\n");
1182     simple = True;
1183   }
1184   delay = get_integer_resource("delay", "Integer");
1185   nodelay = get_boolean_resource("nodelay", "Boolean");
1186   if (nodelay)
1187     delay = 0;
1188   if (delay < 0)
1189     delay = 0;
1190
1191   default_fg_pixel = get_pixel_resource ("foreground", "Foreground", dpy,
1192                                          cmap);
1193   default_bg_pixel = get_pixel_resource ("background", "Background", dpy,
1194                                          cmap);
1195
1196   if (simple) {
1197     /* This is easy */
1198     broken = get_boolean_resource("broken", "Boolean");
1199     if (broken)
1200       if (! quiet)
1201         fprintf(stderr, "-broken not available in simple mode\n");
1202   } else {
1203 #ifndef HAVE_XPM
1204     simple = 1;
1205 #else
1206     broken = get_boolean_resource("broken", "Boolean");
1207 #endif /* HAVE_XPM */
1208   }
1209 }
1210
1211 static void
1212 init_bubbles (Display *dpy, Window window)
1213 {
1214   XGCValues gcv;
1215   XWindowAttributes xgwa;
1216   int i;
1217
1218   defdsp = dpy;
1219   defwin = window;
1220
1221   get_resources(dpy, window);
1222
1223   XGetWindowAttributes (dpy, window, &xgwa);
1224
1225 #ifdef DEBUG
1226   printf("sizof(int) on this platform is %d\n", sizeof(int));
1227   printf("sizof(long) on this platform is %d\n", sizeof(long));
1228 #endif /* DEBUG */
1229
1230   screen_width = xgwa.width;
1231   screen_height = xgwa.height;
1232   screen_depth = xgwa.depth;
1233   defcmap = xgwa.colormap;
1234   defvisual = xgwa.visual;
1235
1236   if (simple) {
1237     /* These are pretty much plucked out of the air */
1238     bubble_min_radius = (int)(0.006*(double)(MIN(screen_width, 
1239                                                  screen_height)));
1240     bubble_max_radius = (int)(0.045*(double)(MIN(screen_width,
1241                                                  screen_height)));
1242     /* Some trivial values */
1243     if (bubble_min_radius < 1)
1244       bubble_min_radius = 1;
1245     if (bubble_max_radius <= bubble_min_radius)
1246       bubble_max_radius = bubble_min_radius + 1;
1247
1248     mesh_length = (2 * bubble_max_radius) + 3;
1249
1250     /* store area of each bubble of certain radius as number of 1/10s of
1251        a pixel area.  PI is defined in <math.h> */
1252     bubble_areas = (long *)xmalloc((bubble_max_radius + 2) * sizeof(int));
1253     for (i = 0; i < bubble_min_radius; i++)
1254       bubble_areas[i] = 0;
1255     for (i = bubble_min_radius; i <= (bubble_max_radius+1); i++)
1256       bubble_areas[i] = calc_bubble_area(i);
1257
1258     mesh_length = (2 * bubble_max_radius) + 3;
1259   } else {
1260 #ifndef HAVE_XPM
1261     fprintf(stderr,
1262             "Bug: simple mode code not set but HAVE_XPM not defined\n");
1263     exit(1);
1264 #else
1265     /* Make sure all #ifdef sort of things have been taken care of in
1266        get_resources(). */
1267     default_to_pixmaps();
1268
1269     /* Set mesh length */
1270     mesh_length = (2 * step_pixmaps[num_bubble_pixmaps-1]->radius) + 3;
1271 #endif /* HAVE_XPM */
1272
1273     /* Am I missing something in here??? */
1274   }
1275
1276   mesh_width = (screen_width / mesh_length) + 1;
1277   mesh_height = (screen_height / mesh_length) + 1;
1278   mesh_cells = mesh_width * mesh_height;
1279   init_mesh();
1280
1281   calculate_adjacent_list();
1282
1283   adjust_areas();
1284
1285   /* Graphics contexts for simple mode */
1286   if (simple) {
1287     gcv.foreground = default_fg_pixel;
1288     draw_gc = XCreateGC (dpy, window, GCForeground, &gcv);
1289     gcv.foreground = default_bg_pixel;
1290     erase_gc = XCreateGC (dpy, window, GCForeground, &gcv);
1291   }
1292
1293   XClearWindow (dpy, window);
1294 }
1295
1296 static void 
1297 bubbles (Display *dpy, Window window)
1298 {
1299   Bubble *tmp;
1300
1301   tmp = new_bubble();
1302   add_to_mesh(tmp);
1303   insert_new_bubble(tmp);
1304
1305   XSync (dpy, True);
1306 }
1307
1308
1309 void 
1310 screenhack (Display *dpy, Window window)
1311 {
1312   init_bubbles (dpy, window);
1313   while (1) {
1314     bubbles (dpy, window);
1315     if (delay)
1316       usleep(delay);
1317   }
1318 }
1319