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 (st->dpy, wa.visual, wa.colormap, st->colors, &st->ncolors,
 383                         True, True, 0, True);
 384
 385   st->delay = get_integer_resource(st->dpy, "delay", "Integer");
 386   st->max_dist = get_integer_resource(st->dpy, "distance", "Integer");
 387
 388   if(st->max_dist < MIN_DIST)
 389     st->max_dist = MIN_DIST + 1;
 390   if(st->max_dist > MAX_DIST)
 391     st->max_dist = MAX_DIST;
 392
 393   st->max_src = get_integer_resource(st->dpy, "sources", "Integer");
 394
 395   if(st->max_src <= 0)
 396     st->max_src = 1;
 397
 398   st->max_searcher = get_integer_resource(st->dpy, "searchers", "Integer");
 399
 400   if(st->max_searcher < 0)
 401     st->max_searcher = 0;
 402
 403   st->dbuf = True;
 404
 405 # ifdef HAVE_COCOA      /* Don't second-guess Quartz's double-buffering */
 406     st->dbuf = False;
 407 # endif
 408
 409   st->source = (Source **) emalloc(sizeof(Source *) * st->max_src);
 410   memset(st->source, 0, st->max_src * sizeof(Source *));
 411
 412   st->source[0] = new_source(st);
 413
 414   st->searcher = (Searcher **) emalloc(st->max_searcher * sizeof(Searcher *));
 415
 416   memset(st->searcher, 0, st->max_searcher * sizeof(Searcher *));
 417
 418   st->b = st->ba = st->bb = 0;  /* double-buffer to reduce flicker */
 419
 420 #ifdef HAVE_DOUBLE_BUFFER_EXTENSION
 421   st->b = st->backb = xdbe_get_backbuffer (st->dpy, st->window, XdbeUndefined);
 422 #endif
 423
 424   st->scrWidth = wa.width;
 425   st->scrHeight = wa.height;
 426   st->cmap = wa.colormap;
 427   st->gcDraw = XCreateGC(st->dpy, st->window, 0, &st->gcv);
 428   st->gcv.foreground = get_pixel_resource(st->dpy, st->cmap,
 429                                           "background", "Background");
 430   st->gcClear = XCreateGC(st->dpy, st->window, GCForeground, &st->gcv);
 431
 432   if (st->dbuf) {
 433     if (!st->b) {
 434         st->ba = XCreatePixmap (st->dpy, st->window, st->scrWidth, st->scrHeight, wa.depth);
 435         st->bb = XCreatePixmap (st->dpy, st->window, st->scrWidth, st->scrHeight, wa.depth);
 436         st->b = st->ba;
 437       }
 438   }
 439   else
 440     st->b = st->window;
 441
 442
 443   if (st->ba) XFillRectangle (st->dpy, st->ba, st->gcClear, 0, 0, st->scrWidth, st->scrHeight);
 444   if (st->bb) XFillRectangle (st->dpy, st->bb, st->gcClear, 0, 0, st->scrWidth, st->scrHeight);
 445
 446   st->ax = st->scrWidth / (double) st->max_dist;
 447   st->ay = st->scrHeight / (2. * st->max_dist);
 448   st->bx = 0.;
 449   st->by = 0.;
 450
 451   if((st->dx = st->scrWidth / (2 * st->max_dist)) == 0)
 452     st->dx = 1;
 453   if((st->dy = st->scrHeight / (4 * st->max_dist)) == 0)
 454     st->dy = 1;
 455   XSetLineAttributes(st->dpy, st->gcDraw, st->dx / 3 + 1, LineSolid, CapRound, JoinRound);
 456   XClearWindow(st->dpy, st->window);
 457
 458   return st;
 459 }
 460
 461 static void draw_searcher(struct state *st, Drawable curr_window, int i)
 462 {
 463   Point r1, r2;
 464   PList *l;
 465
 466   if(st->searcher[i] == NULL)
 467     return;
 468
 469   XSetForeground(st->dpy, st->gcDraw, st->searcher[i]->color);
 470
 471   r1.x = X(st->searcher[i]->r.x) + st->searcher[i]->rs;
 472   r1.y = Y(st->searcher[i]->r.y);
 473
 474   XFillRectangle(st->dpy, curr_window, st->gcDraw, r1.x - 2, r1.y - 2, 4, 4);
 475
 476   for(l = st->searcher[i]->hist; l != NULL; l = l->next) {
 477
 478     r2.x = X(l->r.x) + st->searcher[i]->rs;
 479     r2.y = Y(l->r.y);
 480
 481     XDrawLine(st->dpy, curr_window, st->gcDraw, r1.x, r1.y, r2.x, r2.y);
 482
 483     r1 = r2;
 484   }
 485
 486 }
 487
 488 static void draw_image(struct state *st, Drawable curr_window)
 489 {
 490   int i, j;
 491   int x, y;
 492
 493   for(i = 0; i < st->max_src; i++) {
 494
 495     if(st->source[i] == NULL)
 496       continue;
 497
 498     XSetForeground(st->dpy, st->gcDraw, st->source[i]->color);
 499
 500     if(st->source[i]->inv_rate > 0) {
 501
 502       if(st->max_searcher > 0) {
 503       x = (int) X(st->source[i]->r.x);
 504       y = (int) Y(st->source[i]->r.y);
 505       j = st->dx * (MAX_INV_RATE + 1 - st->source[i]->inv_rate) / (2 * MAX_INV_RATE);
 506       if(j == 0)
 507         j = 1;
 508       XFillArc(st->dpy, curr_window, st->gcDraw, x - j, y - j, 2 * j, 2 * j, 0, 360 * 64);
 509       }}
 510
 511     for(j = 0; j < st->source[i]->n; j++) {
 512
 513       if(st->source[i]->yv[j].v == 2)
 514         continue;
 515
 516       /* Move the particles slightly off lattice */
 517       x =  X(st->source[i]->r.x + 1 + j) + RND(st->dx);
 518       y = Y(st->source[i]->r.y + st->source[i]->yv[j].y) + RND(st->dy);
 519       XFillArc(st->dpy, curr_window, st->gcDraw, x - 2, y - 2, 4, 4, 0, 360 * 64);
 520     }
 521
 522   }
 523
 524   for(i = 0; i < st->max_searcher; i++)
 525     draw_searcher(st, curr_window, i);
 526
 527 }
 528
 529 static void animate_anemotaxis(struct state *st, Drawable curr_window)
 530 {
 531   int i, j;
 532   Bool dead;
 533
 534   for(i = 0; i < st->max_src; i++) {
 535
 536     if(st->source[i] == NULL)
 537       continue;
 538
 539     evolve_source(st->source[i]);
 540
 541     /* reap dead sources for which all particles are gone */
 542     if(st->source[i]->inv_rate == 0) {
 543
 544       dead = True;
 545
 546       for(j = 0; j < st->source[i]->n; j++) {
 547         if(st->source[i]->yv[j].v != 2) {
 548           dead = False;
 549           break;
 550         }
 551       }
 552
 553       if(dead == True) {
 554         destroy_source(st->source[i]);
 555         st->source[i] = NULL;
 556       }
 557     }
 558   }
 559
 560   /* Decide if we want to add new  sources */
 561
 562   for(i = 0; i < st->max_src; i++) {
 563     if(st->source[i] == NULL && RND(st->max_dist * st->max_src) == 0)
 564       st->source[i] = new_source(st);
 565   }
 566
 567   if(st->max_searcher == 0) { /* kill some sources when searchers don't do that */
 568     for(i = 0; i < st->max_src; i++) {
 569       if(st->source[i] != NULL && RND(st->max_dist * st->max_src) == 0) {
 570         destroy_source(st->source[i]);
 571         st->source[i] = 0;
 572       }
 573     }
 574   }
 575
 576   /* Now deal with searchers */
 577
 578   for(i = 0; i < st->max_searcher; i++) {
 579
 580     if((st->searcher[i] != NULL) && (st->searcher[i]->state == DONE)) {
 581       destroy_searcher(st->searcher[i]);
 582       st->searcher[i] = NULL;
 583     }
 584
 585     if(st->searcher[i] == NULL) {
 586
 587       if(RND(st->max_dist * st->max_searcher) == 0) {
 588
 589         st->searcher[i] = new_searcher(st);
 590
 591       }
 592     }
 593
 594     if(st->searcher[i] == NULL)
 595       continue;
 596
 597     /* Check if searcher found a source or missed all of them */
 598     for(j = 0; j < st->max_src; j++) {
 599
 600       if(st->source[j] == NULL || st->source[j]->inv_rate == 0)
 601         continue;
 602
 603       if(st->searcher[i]->r.x < 0) {
 604         st->searcher[i]->state = DONE;
 605         break;
 606       }
 607
 608       if((st->source[j]->r.y == st->searcher[i]->r.y) &&
 609          (st->source[j]->r.x == st->searcher[i]->r.x)) {
 610         st->searcher[i]->state = DONE;
 611         st->source[j]->inv_rate = 0;  /* source disappears */
 612
 613         /* Make it flash */
 614         st->searcher[i]->color = WhitePixel(st->dpy, DefaultScreen(st->dpy));
 615
 616         break;
 617       }
 618     }
 619
 620     st->searcher[i]->c = 0; /* set it here in case we don't get to get_v() */
 621
 622     /* Find the concentration at searcher's location */
 623
 624     if(st->searcher[i]->state != DONE) {
 625       for(j = 0; j < st->max_src; j++) {
 626
 627         if(st->source[j] == NULL)
 628           continue;
 629
 630         get_v(st->source[j], st->searcher[i]);
 631
 632         if(st->searcher[i]->c == 1)
 633           break;
 634       }
 635     }
 636
 637     move_searcher(st->searcher[i]);
 638
 639   }
 640
 641   draw_image(st, curr_window);
 642 }
 643
 644 static unsigned long
 645 anemotaxis_draw (Display *disp, Window window, void *closure)
 646 {
 647   struct state *st = (struct state *) closure;
 648   XWindowAttributes wa;
 649   int w, h;
 650
 651
 652   XGetWindowAttributes(st->dpy, st->window, &wa);
 653
 654   w = wa.width;
 655   h = wa.height;
 656
 657   if(w != st->scrWidth || h != st->scrHeight) {
 658     st->scrWidth = w;
 659     st->scrHeight = h;
 660     st->ax = st->scrWidth / (double) st->max_dist;
 661     st->ay = st->scrHeight / (2. * st->max_dist);
 662     st->bx = 0.;
 663     st->by = 0.;
 664
 665     if((st->dx = st->scrWidth / (2 * st->max_dist)) == 0)
 666       st->dx = 1;
 667     if((st->dy = st->scrHeight / (4 * st->max_dist)) == 0)
 668       st->dy = 1;
 669     XSetLineAttributes(st->dpy, st->gcDraw, st->dx / 3 + 1, LineSolid, CapRound, JoinRound);
 670   }
 671
 672   XFillRectangle (st->dpy, st->b, st->gcClear, 0, 0, st->scrWidth, st->scrHeight);
 673   animate_anemotaxis(st, st->b);
 674
 675 #ifdef HAVE_DOUBLE_BUFFER_EXTENSION
 676   if (st->backb) {
 677     XdbeSwapInfo info[1];
 678     info[0].swap_window = st->window;
 679     info[0].swap_action = XdbeUndefined;
 680     XdbeSwapBuffers (st->dpy, info, 1);
 681   }
 682   else
 683 #endif
 684     if (st->dbuf)       {
 685       XCopyArea (st->dpy, st->b, st->window, st->gcClear, 0, 0,
 686                  st->scrWidth, st->scrHeight, 0, 0);
 687       st->b = (st->b == st->ba ? st->bb : st->ba);
 688     }
 689
 690   return st->delay;
 691 }
 692
 693
 694
 695 static void
 696 anemotaxis_reshape (Display *dpy, Window window, void *closure,
 697                  unsigned int w, unsigned int h)
 698 {
 699 }
 700
 701 static Bool
 702 anemotaxis_event (Display *dpy, Window window, void *closure, XEvent *event)
 703 {
 704   return False;
 705 }
 706
 707 static void
 708 anemotaxis_free (Display *dpy, Window window, void *closure)
 709 {
 710   struct state *st = (struct state *) closure;
 711   int i;
 712   if (st->source) {
 713     for (i = 0; i < st->max_src; i++)
 714       if (st->source[i]) destroy_source (st->source[i]);
 715     free (st->source);
 716   }
 717   if (st->searcher) {
 718     for (i = 0; i < st->max_searcher; i++)
 719       if (st->searcher[i]) destroy_searcher (st->searcher[i]);
 720     free (st->searcher);
 721   }
 722   free (st);
 723 }
 724
 725
 726
 727
 728 static const char *anemotaxis_defaults [] = {
 729   ".background: black",
 730   "*distance: 40",
 731   "*sources: 25",
 732   "*searchers: 25",
 733   "*delay: 20000",
 734   "*colors: 20",
 735 #ifdef HAVE_DOUBLE_BUFFER_EXTENSION
 736   "*useDBE:             True",
 737 #endif
 738   0
 739 };
 740
 741
 742 static XrmOptionDescRec anemotaxis_options [] = {
 743   { "-delay",       ".delay",       XrmoptionSepArg, 0 },
 744   { "-distance",    ".distance",    XrmoptionSepArg, 0 },
 745   { "-sources",     ".sources",     XrmoptionSepArg, 0 },
 746   { "-searchers",   ".searchers",   XrmoptionSepArg, 0 },
 747   { "-colors",      ".colors",      XrmoptionSepArg, 0 },
 748   { 0, 0, 0, 0 }
 749 };
 750
 751
 752 XSCREENSAVER_MODULE ("Anemotaxis", anemotaxis)