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