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

   1 /* anemotaxis, Copyright (c) 2004 Eugene Balkovski
   2  *
   3  * Permission to use, copy, modify, distribute, and sell this software
   4  * and its documentation for any purpose is hereby granted without
   5  * fee, provided that the above copyright notice appear in all copies
   6  * and that both that copyright notice and this permission notice
   7  * appear in supporting documentation.  No representations are made
   8  * about the suitability of this software for any purpose. It is
   9  * provided "as is" without express or implied warranty.
  10  */
  11
  12 /*------------------------------------------------------------------------
  13   |
  14   |  FILE            anemotaxis.c
  15   |
  16   |  DESCRIPTION     Anemotaxis
  17   |
  18   |                  This code illustrates an optimal algorithm designed
  19   |                  for searching a source of particles on a plane.
  20   |                  The particles drift in one direction and walk randomly
  21   |                  in the other. The only information available to the
  22   |                  searcher is the presence of a particle at its location
  23   |                  and the local direction from where particle arrived.
  24   |                  The algorithm "explains" the behavior
  25   |                  of some animals and insects
  26   |                  who use olfactory and directional cues to find
  27   |                  sources of odor (mates, food, home etc) in
  28   |                  turbulent atmosphere (odor-modulated anemotaxis),
  29   |                  e.g. male moths locating females who release
  30   |                  pheromones to attract males. The search trajectories
  31   |                  resemble the trajectories that the animals follow.
  32   |
  33   |
  34   |  WRITTEN BY      Eugene Balkovski
  35   |
  36   |  MODIFICATIONS   june 2004 started
  37   |
  38   +----------------------------------------------------------------------*/
  39
  40 /*
  41    Options:
  42
  43    -distance <arg> size of the lattice
  44    -sources <arg>  number of sources
  45    -searhers <arg> number of searcher        */
  46
  47 #include <stdio.h>
  48 #include <stdlib.h>
  49 #include <string.h>
  50
  51 #include "screenhack.h"
  52
  53 #ifdef HAVE_DOUBLE_BUFFER_EXTENSION
  54 #include "xdbe.h"
  55 #endif
  56
  57
  58 /*-----------------------------------------------------------------------+
  59   |  PRIVATE DATA                                                          |
  60   +-----------------------------------------------------------------------*/
  61
  62 #define MAX_DIST 250
  63 #define MIN_DIST 10
  64 #define LINE_WIDTH 4
  65 #define MAX_INV_RATE 5
  66
  67 #define RND(x)     (random() % (x))
  68 #define X(x) ((int) (ax * (x) + bx))
  69 #define Y(x) ((int) (ay * (x) + by))
  70
  71 typedef struct {
  72   short x;
  73   short y;
  74 } Point;
  75
  76 typedef struct {
  77
  78   short y;    /* y-coordinate of the particle (relative to the source) */
  79
  80   short v;    /* velocity of the particle. Allowed values are -1, 0, 1.
  81                  2 means the particle is not valid */
  82 } YV;
  83
  84 typedef struct {
  85
  86   int n;             /* size of array xv */
  87
  88   YV *yv;            /* yv[i] keeps velocity and y-coordinate of the
  89                         particle at (i + 1, yv[i].y) relative to the
  90                         source */
  91
  92   int inv_rate;      /* Inverse rate of particle emission (if 0 then
  93                         source doesn't emit new particles (although
  94                         old ones can still exist )*/
  95
  96   Point r;           /* Position of the source */
  97
  98   long color;
  99
 100 } Source;
 101
 102
 103 typedef struct PList {
 104   Point r;
 105   struct PList *next;
 106 } PList;
 107
 108 typedef enum {UP_LEFT, UP_RIGHT, LEFT, RIGHT, DONE} State_t;
 109
 110 typedef enum {FALSE = 0, TRUE = 1} bool;
 111
 112 typedef struct {
 113
 114   Point r;              /* Current position */
 115
 116   Point vertex;         /* Position of the vertex of the most recent
 117                            cone, which is the region where the source
 118                            is located. We do exhaustive search in the
 119                            cone until we encounter a new particle,
 120                            which gives us a new cone. */
 121
 122   State_t state;        /* Internal state variable */
 123
 124   unsigned char c;      /* Concentration at r */
 125
 126   short v;              /* Velocity at r (good only when c != 0) */
 127
 128   PList *hist;          /* Trajectory */
 129
 130   int rs;               /* small shift of x-coordinate to avoid
 131                            painting over the same x */
 132
 133   long color;
 134
 135 } Searcher;
 136
 137 static Source **source;
 138 static Searcher **searcher;
 139
 140 static int max_dist, max_src, max_searcher;
 141
 142 static double ax, ay, bx, by;
 143 static int dx, dy;
 144
 145 static Display *dpy;
 146 static Window window;
 147
 148 static Pixmap b, ba, bb;
 149
 150 #ifdef HAVE_DOUBLE_BUFFER_EXTENSION
 151 static  XdbeBackBuffer backb;
 152 #endif
 153
 154 static long delay;              /* usecs to wait between updates. */
 155
 156 static int scrWidth, scrHeight;
 157 static GC gcDraw, gcClear;
 158
 159 static bool dbuf;
 160
 161 static XGCValues gcv;
 162 static Colormap cmap;
 163
 164
 165 /*-----------------------------------------------------------------------+
 166   |  PUBLIC DATA                                                           |
 167   +-----------------------------------------------------------------------*/
 168
 169 char *progclass = "Anemotaxis";
 170
 171 char *defaults [] = {
 172   ".background: black",
 173   "*distance: 40",
 174   "*sources: 25",
 175   "*searchers: 25",
 176   "*delay: 20000",
 177 #ifdef HAVE_DOUBLE_BUFFER_EXTENSION
 178   "*useDBE:             True",
 179 #endif
 180   0
 181 };
 182
 183
 184 XrmOptionDescRec options [] = {
 185   { "-delay",       ".delay",       XrmoptionSepArg, 0 },
 186   { "-distance",    ".distance",    XrmoptionSepArg, 0 },
 187   { "-sources",     ".sources",     XrmoptionSepArg, 0 },
 188   { "-searchers",   ".searchers",   XrmoptionSepArg, 0 },
 189   { 0, 0, 0, 0 }
 190 };
 191
 192
 193
 194 /*-----------------------------------------------------------------------+
 195   |  PRIVATE FUNCTIONS                                                     |
 196   +-----------------------------------------------------------------------*/
 197
 198 static void *emalloc(size_t size)
 199 {
 200   void *ret = malloc(size);
 201
 202   if (ret == NULL) {
 203     fprintf(stderr, "out of memory\n");
 204     exit(1);
 205   }
 206   return ret;
 207 }
 208
 209 static Searcher *new_searcher(void)
 210 {
 211   Searcher *m = (Searcher *) emalloc(sizeof(Searcher));
 212
 213   m->r.x = m->vertex.x = max_dist;
 214
 215   do {
 216     m->r.y = RND(2 * max_dist);
 217   } while(m->r.y < MIN_DIST || m->r.y > 2 * max_dist - MIN_DIST);
 218
 219   m->vertex.y = m->r.y;
 220
 221   m->state = (RND(2) == 0 ? UP_RIGHT : UP_LEFT);
 222   m->hist = NULL;
 223   m->color = random();
 224
 225   m->rs = RND(dx);
 226
 227   return m;
 228 }
 229
 230 static void destroy_searcher(Searcher *m)
 231 {
 232   PList *p = m->hist, *q;
 233
 234   while(p != NULL) {
 235     q = p->next;
 236     free(p);
 237     p = q;
 238   }
 239
 240   free(m);
 241 }
 242
 243 static void write_hist(Searcher *m)
 244 {
 245   PList *l;
 246
 247   l = m->hist;
 248   m->hist = (PList *) emalloc(sizeof(PList));
 249   m->hist->next = l;
 250   m->hist->r = m->r;
 251
 252 }
 253
 254 static void move_searcher(Searcher *m)
 255 {
 256
 257   if(m->c == TRUE) {
 258     write_hist(m);
 259     m->r.x -= 1;
 260     m->r.y -= m->v;
 261     write_hist(m);
 262     m->state = (RND(2) == 0 ? UP_LEFT : UP_RIGHT);
 263     m->vertex = m->r;
 264     return;
 265
 266   }
 267
 268   switch(m->state) {
 269   case UP_LEFT:
 270
 271     m->r.x -= 1;
 272     m->r.y += 1;
 273     m->state = RIGHT;
 274     write_hist(m);
 275     return;
 276
 277   case RIGHT:
 278
 279     m->r.y -= 1;
 280     if(m->vertex.x - m->r.x == m->vertex.y - m->r.y) {
 281       write_hist(m);
 282       m->state = UP_RIGHT;
 283     }
 284     return;
 285
 286   case UP_RIGHT:
 287
 288     m->r.x -= 1;
 289     m->r.y -= 1;
 290
 291     m->state = LEFT;
 292     write_hist(m);
 293     return;
 294
 295   case LEFT:
 296
 297     m->r.y += 1;
 298
 299     if(m->vertex.x - m->r.x == m->r.y - m->vertex.y) {
 300       write_hist(m);
 301       m->state = UP_LEFT;
 302     }
 303     return;
 304
 305   default:
 306     break;
 307   }
 308
 309 }
 310
 311 static void evolve_source(Source *s)
 312 {
 313
 314   int i;
 315
 316   /* propagate existing particles */
 317
 318   for(i = s->n - 1; i > 0; i--) {
 319
 320     if(s->yv[i - 1].v == 2)
 321       s->yv[i].v = 2;
 322     else {
 323       s->yv[i].v = RND(3) - 1;
 324       s->yv[i].y = s->yv[i - 1].y + s->yv[i].v;
 325     }
 326
 327   }
 328
 329
 330   if(s->inv_rate > 0 && (RND(s->inv_rate) == 0)) /* emit a particle */
 331     s->yv[0].y = s->yv[0].v = RND(3) - 1;
 332   else
 333     s->yv[0].v = 2;
 334
 335 }
 336
 337 static Source *new_source(void)
 338 {
 339   int i;
 340
 341   Source *s = (Source *) emalloc(sizeof(Source));
 342   if(max_searcher == 0) {
 343     s->r.x = 0;
 344     s->r.y = RND(2 * max_dist);
 345   }
 346   else {
 347     s->r.x = RND(max_dist / 3);
 348     do {
 349       s->r.y = RND(2 * max_dist);
 350     } while(s->r.y < MIN_DIST || s->r.y > 2 * max_dist - MIN_DIST);
 351   }
 352
 353   s->n = max_dist - s->r.x;
 354   s->yv = emalloc(sizeof(YV) * s->n);
 355
 356   for(i = 0; i < s->n; i++)
 357     s->yv[i].v = 2;
 358
 359   s->inv_rate = RND(MAX_INV_RATE);
 360
 361   if(s->inv_rate == 0)
 362     s->inv_rate = 1;
 363
 364   s->color = random();
 365
 366   return s;
 367 }
 368
 369 static void destroy_source(Source *s)
 370 {
 371   free(s->yv);
 372   free(s);
 373 }
 374
 375 static void get_v(const Source *s, Searcher *m)
 376 {
 377   int x = m->r.x - s->r.x - 1;
 378
 379   m->c = 0;
 380
 381   if(x < 0 || x >= s->n)
 382     return;
 383
 384   if((s->yv[x].v == 2) || (s->yv[x].y != m->r.y - s->r.y))
 385     return;
 386
 387   m->c = 1;
 388   m->v = s->yv[x].v;
 389   m->color = s->color;
 390 }
 391
 392
 393 static void init_anemotaxis(void)
 394 {
 395   XWindowAttributes wa;
 396
 397   delay = get_integer_resource("delay", "Integer");
 398   max_dist = get_integer_resource("distance", "Integer");
 399
 400   if(max_dist < MIN_DIST)
 401     max_dist = MIN_DIST + 1;
 402   if(max_dist > MAX_DIST)
 403     max_dist = MAX_DIST;
 404
 405   max_src = get_integer_resource("sources", "Integer");
 406
 407   if(max_src <= 0)
 408     max_src = 1;
 409
 410   max_searcher = get_integer_resource("searchers", "Integer");
 411
 412   if(max_searcher < 0)
 413     max_searcher = 0;
 414
 415   dbuf = TRUE;
 416
 417   source = (Source **) emalloc(sizeof(Source *) * max_src);
 418   memset(source, 0, max_src * sizeof(Source *));
 419
 420   source[0] = new_source();
 421
 422   searcher = (Searcher **) emalloc(max_searcher * sizeof(Searcher *));
 423
 424   memset(searcher, 0, max_searcher * sizeof(Searcher *));
 425
 426   b = ba = bb = 0;      /* double-buffer to reduce flicker */
 427
 428 #ifdef HAVE_DOUBLE_BUFFER_EXTENSION
 429   b = backb = xdbe_get_backbuffer (dpy, window, XdbeUndefined);
 430 #endif
 431
 432   XGetWindowAttributes(dpy, window, &wa);
 433   scrWidth = wa.width;
 434   scrHeight = wa.height;
 435   cmap = wa.colormap;
 436   gcDraw = XCreateGC(dpy, window, GCForeground, &gcv);
 437   gcv.foreground = get_pixel_resource("background", "Background", dpy, cmap);
 438   gcClear = XCreateGC(dpy, window, GCForeground, &gcv);
 439
 440   if (dbuf) {
 441     if (!b) {
 442         ba = XCreatePixmap (dpy, window, scrWidth, scrHeight, wa.depth);
 443         bb = XCreatePixmap (dpy, window, scrWidth, scrHeight, wa.depth);
 444         b = ba;
 445       }
 446   }
 447   else
 448     b = window;
 449
 450
 451   if (ba) XFillRectangle (dpy, ba, gcClear, 0, 0, scrWidth, scrHeight);
 452   if (bb) XFillRectangle (dpy, bb, gcClear, 0, 0, scrWidth, scrHeight);
 453
 454   ax = scrWidth / (double) max_dist;
 455   ay = scrHeight / (2. * max_dist);
 456   bx = 0.;
 457   by = 0.;
 458
 459   if((dx = scrWidth / (2 * max_dist)) == 0)
 460     dx = 1;
 461   if((dy = scrHeight / (4 * max_dist)) == 0)
 462     dy = 1;
 463   XSetLineAttributes(dpy, gcDraw, dx / 3 + 1, LineSolid, CapRound, JoinRound);
 464   XClearWindow(dpy, window);
 465 }
 466
 467 static void draw_searcher(Drawable curr_window, int i)
 468 {
 469   Point r1, r2;
 470   PList *l;
 471
 472   if(searcher[i] == NULL)
 473     return;
 474
 475   XSetForeground(dpy, gcDraw, searcher[i]->color);
 476
 477   r1.x = X(searcher[i]->r.x) + searcher[i]->rs;
 478   r1.y = Y(searcher[i]->r.y);
 479
 480   XFillRectangle(dpy, curr_window, gcDraw, r1.x - 2, r1.y - 2, 4, 4);
 481
 482   for(l = searcher[i]->hist; l != NULL; l = l->next) {
 483
 484     r2.x = X(l->r.x) + searcher[i]->rs;
 485     r2.y = Y(l->r.y);
 486
 487     XDrawLine(dpy, curr_window, gcDraw, r1.x, r1.y, r2.x, r2.y);
 488
 489     r1 = r2;
 490   }
 491
 492 }
 493
 494 static void draw_image(Drawable curr_window)
 495 {
 496   int i, j;
 497   int x, y;
 498
 499   for(i = 0; i < max_src; i++) {
 500
 501     if(source[i] == NULL)
 502       continue;
 503
 504     XSetForeground(dpy, gcDraw, source[i]->color);
 505
 506     if(source[i]->inv_rate > 0) {
 507
 508       if(max_searcher > 0) {
 509       x = (int) X(source[i]->r.x);
 510       y = (int) Y(source[i]->r.y);
 511       j = dx * (MAX_INV_RATE + 1 - source[i]->inv_rate) / (2 * MAX_INV_RATE);
 512       if(j == 0)
 513         j = 1;
 514       XFillArc(dpy, curr_window, gcDraw, x - j, y - j, 2 * j, 2 * j, 0, 360 * 64);
 515       }}
 516
 517     for(j = 0; j < source[i]->n; j++) {
 518
 519       if(source[i]->yv[j].v == 2)
 520         continue;
 521
 522       /* Move the particles slightly off lattice */
 523       x =  X(source[i]->r.x + 1 + j) + RND(dx);
 524       y = Y(source[i]->r.y + source[i]->yv[j].y) + RND(dy);
 525       XFillArc(dpy, curr_window, gcDraw, x - 2, y - 2, 4, 4, 0, 360 * 64);
 526     }
 527
 528   }
 529
 530   for(i = 0; i < max_searcher; i++)
 531     draw_searcher(curr_window, i);
 532
 533 }
 534
 535 static void animate_anemotaxis(Drawable curr_window)
 536 {
 537   int i, j;
 538   bool dead;
 539
 540   for(i = 0; i < max_src; i++) {
 541
 542     if(source[i] == NULL)
 543       continue;
 544
 545     evolve_source(source[i]);
 546
 547     /* reap dead sources for which all particles are gone */
 548     if(source[i]->inv_rate == 0) {
 549
 550       dead = TRUE;
 551
 552       for(j = 0; j < source[i]->n; j++) {
 553         if(source[i]->yv[j].v != 2) {
 554           dead = FALSE;
 555           break;
 556         }
 557       }
 558
 559       if(dead == TRUE) {
 560         destroy_source(source[i]);
 561         source[i] = NULL;
 562       }
 563     }
 564   }
 565
 566   /* Decide if we want to add new  sources */
 567
 568   for(i = 0; i < max_src; i++) {
 569     if(source[i] == NULL && RND(max_dist * max_src) == 0)
 570       source[i] = new_source();
 571   }
 572
 573   if(max_searcher == 0) { /* kill some sources when searchers don't do that */
 574     for(i = 0; i < max_src; i++) {
 575       if(source[i] != NULL && RND(max_dist * max_src) == 0) {
 576         destroy_source(source[i]);
 577         source[i] = 0;
 578       }
 579     }
 580   }
 581
 582   /* Now deal with searchers */
 583
 584   for(i = 0; i < max_searcher; i++) {
 585
 586     if((searcher[i] != NULL) && (searcher[i]->state == DONE)) {
 587       destroy_searcher(searcher[i]);
 588       searcher[i] = NULL;
 589     }
 590
 591     if(searcher[i] == NULL) {
 592
 593       if(RND(max_dist * max_searcher) == 0) {
 594
 595         searcher[i] = new_searcher();
 596
 597       }
 598     }
 599
 600     if(searcher[i] == NULL)
 601       continue;
 602
 603     /* Check if searcher found a source or missed all of them */
 604     for(j = 0; j < max_src; j++) {
 605
 606       if(source[j] == NULL || source[j]->inv_rate == 0)
 607         continue;
 608
 609       if(searcher[i]->r.x < 0) {
 610         searcher[i]->state = DONE;
 611         break;
 612       }
 613
 614       if((source[j]->r.y == searcher[i]->r.y) &&
 615          (source[j]->r.x == searcher[i]->r.x)) {
 616         searcher[i]->state = DONE;
 617         source[j]->inv_rate = 0;  /* source disappears */
 618
 619         /* Make it flash */
 620         searcher[i]->color = WhitePixel(dpy, DefaultScreen(dpy));
 621
 622         break;
 623       }
 624     }
 625
 626     searcher[i]->c = 0; /* set it here in case we don't get to get_v() */
 627
 628     /* Find the concentration at searcher's location */
 629
 630     if(searcher[i]->state != DONE) {
 631       for(j = 0; j < max_src; j++) {
 632
 633         if(source[j] == NULL)
 634           continue;
 635
 636         get_v(source[j], searcher[i]);
 637
 638         if(searcher[i]->c == 1)
 639           break;
 640       }
 641     }
 642
 643     move_searcher(searcher[i]);
 644
 645   }
 646
 647   draw_image(curr_window);
 648   usleep(delay);
 649 }
 650
 651 /*-----------------------------------------------------------------------+
 652   |  PUBLIC FUNCTIONS                                                      |
 653   +-----------------------------------------------------------------------*/
 654
 655 void screenhack(Display *disp, Window win)
 656 {
 657
 658   XWindowAttributes wa;
 659   int w, h;
 660
 661
 662   dpy = disp;
 663   window = win;
 664
 665   init_anemotaxis();
 666
 667   for(;;) {
 668
 669     XGetWindowAttributes(dpy, window, &wa);
 670
 671     w = wa.width;
 672     h = wa.height;
 673
 674     if(w != scrWidth || h != scrHeight) {
 675       scrWidth = w;
 676       scrHeight = h;
 677       ax = scrWidth / (double) max_dist;
 678       ay = scrHeight / (2. * max_dist);
 679       bx = 0.;
 680       by = 0.;
 681
 682       if((dx = scrWidth / (2 * max_dist)) == 0)
 683         dx = 1;
 684       if((dy = scrHeight / (4 * max_dist)) == 0)
 685         dy = 1;
 686       XSetLineAttributes(dpy, gcDraw, dx / 3 + 1, LineSolid, CapRound, JoinRound);
 687     }
 688
 689     XFillRectangle (dpy, b, gcClear, 0, 0, scrWidth, scrHeight);
 690     animate_anemotaxis(b);
 691
 692 #ifdef HAVE_DOUBLE_BUFFER_EXTENSION
 693     if (backb) {
 694         XdbeSwapInfo info[1];
 695         info[0].swap_window = window;
 696         info[0].swap_action = XdbeUndefined;
 697         XdbeSwapBuffers (dpy, info, 1);
 698       }
 699     else
 700 #endif
 701       if (dbuf) {
 702           XCopyArea (dpy, b, window, gcClear, 0, 0,
 703                      scrWidth, scrHeight, 0, 0);
 704           b = (b == ba ? bb : ba);
 705         }
 706
 707     screenhack_handle_events (dpy);
 708   }
 709
 710 }