git.hungrycats.org Git - xscreensaver/blob - 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