From http://www.jwz.org/xscreensaver/xscreensaver-5.39.tar.gz
[xscreensaver] / 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       int size = (st->scrWidth > 2560 ? 8 : 4);  /* Retina displays */
515
516       if(st->source[i]->yv[j].v == 2)
517         continue;
518
519       /* Move the particles slightly off lattice */
520       x =  X(st->source[i]->r.x + 1 + j) + RND(st->dx);
521       y = Y(st->source[i]->r.y + st->source[i]->yv[j].y) + RND(st->dy);
522       XFillArc(st->dpy, curr_window, st->gcDraw, x - size/2, y - size/2, size, size, 0, 360 * 64);
523     }
524
525   }
526
527   for(i = 0; i < st->max_searcher; i++)
528     draw_searcher(st, curr_window, i);
529  
530 }
531
532 static void animate_anemotaxis(struct state *st, Drawable curr_window)
533 {
534   int i, j;
535   Bool dead;
536
537   for(i = 0; i < st->max_src; i++) {
538
539     if(st->source[i] == NULL)
540       continue;
541
542     evolve_source(st->source[i]);
543
544     /* reap dead sources for which all particles are gone */
545     if(st->source[i]->inv_rate == 0) {
546
547       dead = True;
548
549       for(j = 0; j < st->source[i]->n; j++) {
550         if(st->source[i]->yv[j].v != 2) {
551           dead = False;
552           break;
553         }
554       }
555
556       if(dead == True) {
557         destroy_source(st->source[i]);
558         st->source[i] = NULL;
559       }
560     }
561   }
562
563   /* Decide if we want to add new  sources */
564
565   for(i = 0; i < st->max_src; i++) {
566     if(st->source[i] == NULL && RND(st->max_dist * st->max_src) == 0)
567       st->source[i] = new_source(st);
568   }
569
570   if(st->max_searcher == 0) { /* kill some sources when searchers don't do that */
571     for(i = 0; i < st->max_src; i++) {
572       if(st->source[i] != NULL && RND(st->max_dist * st->max_src) == 0) {
573         destroy_source(st->source[i]);
574         st->source[i] = 0;
575       }
576     }
577   }
578
579   /* Now deal with searchers */
580
581   for(i = 0; i < st->max_searcher; i++) {
582
583     if((st->searcher[i] != NULL) && (st->searcher[i]->state == DONE)) {
584       destroy_searcher(st->searcher[i]);
585       st->searcher[i] = NULL;
586     }
587
588     if(st->searcher[i] == NULL) {
589
590       if(RND(st->max_dist * st->max_searcher) == 0) {
591
592         st->searcher[i] = new_searcher(st);
593
594       }
595     }
596
597     if(st->searcher[i] == NULL)
598       continue;
599
600     /* Check if searcher found a source or missed all of them */
601     for(j = 0; j < st->max_src; j++) {
602
603       if(st->source[j] == NULL || st->source[j]->inv_rate == 0)
604         continue;
605
606       if(st->searcher[i]->r.x < 0) {
607         st->searcher[i]->state = DONE;
608         break;
609       }
610
611       if((st->source[j]->r.y == st->searcher[i]->r.y) && 
612          (st->source[j]->r.x == st->searcher[i]->r.x)) {
613         st->searcher[i]->state = DONE;
614         st->source[j]->inv_rate = 0;  /* source disappears */
615
616         /* Make it flash */
617         st->searcher[i]->color = WhitePixel(st->dpy, DefaultScreen(st->dpy));
618
619         break;
620       }
621     }
622
623     st->searcher[i]->c = 0; /* set it here in case we don't get to get_v() */
624
625     /* Find the concentration at searcher's location */
626     
627     if(st->searcher[i]->state != DONE) {
628       for(j = 0; j < st->max_src; j++) {
629         
630         if(st->source[j] == NULL)
631           continue;
632
633         get_v(st->source[j], st->searcher[i]);
634       
635         if(st->searcher[i]->c == 1)
636           break;
637       }
638     }
639
640     move_searcher(st->searcher[i]);
641
642   }
643
644   draw_image(st, curr_window);
645 }
646
647 static unsigned long
648 anemotaxis_draw (Display *disp, Window window, void *closure)
649 {
650   struct state *st = (struct state *) closure;
651   XWindowAttributes wa;
652   int w, h;
653
654     
655   XGetWindowAttributes(st->dpy, st->window, &wa);
656
657   w = wa.width;
658   h = wa.height;
659
660   if(w != st->scrWidth || h != st->scrHeight) {
661     st->scrWidth = w;
662     st->scrHeight = h;
663     st->ax = st->scrWidth / (double) st->max_dist;
664     st->ay = st->scrHeight / (2. * st->max_dist);
665     st->bx = 0.;
666     st->by = 0.;
667       
668     if((st->dx = st->scrWidth / (2 * st->max_dist)) == 0)
669       st->dx = 1;
670     if((st->dy = st->scrHeight / (4 * st->max_dist)) == 0)
671       st->dy = 1;
672     XSetLineAttributes(st->dpy, st->gcDraw, st->dx / 3 + 1, LineSolid, CapRound, JoinRound);
673   } 
674
675   XFillRectangle (st->dpy, st->b, st->gcClear, 0, 0, st->scrWidth, st->scrHeight);
676   animate_anemotaxis(st, st->b);
677
678 #ifdef HAVE_DOUBLE_BUFFER_EXTENSION
679   if (st->backb) {
680     XdbeSwapInfo info[1];
681     info[0].swap_window = st->window;
682     info[0].swap_action = XdbeUndefined;
683     XdbeSwapBuffers (st->dpy, info, 1);
684   }
685   else
686 #endif
687     if (st->dbuf)       {
688       XCopyArea (st->dpy, st->b, st->window, st->gcClear, 0, 0,
689                  st->scrWidth, st->scrHeight, 0, 0);
690       st->b = (st->b == st->ba ? st->bb : st->ba);
691     }
692
693   return st->delay;
694 }
695
696
697
698 static void
699 anemotaxis_reshape (Display *dpy, Window window, void *closure, 
700                  unsigned int w, unsigned int h)
701 {
702 }
703
704 static Bool
705 anemotaxis_event (Display *dpy, Window window, void *closure, XEvent *event)
706 {
707   return False;
708 }
709
710 static void
711 anemotaxis_free (Display *dpy, Window window, void *closure)
712 {
713   struct state *st = (struct state *) closure;
714   int i;
715   if (st->source) {
716     for (i = 0; i < st->max_src; i++)
717       if (st->source[i]) destroy_source (st->source[i]);
718     free (st->source);
719   }
720   if (st->searcher) {
721     for (i = 0; i < st->max_searcher; i++)
722       if (st->searcher[i]) destroy_searcher (st->searcher[i]);
723     free (st->searcher);
724   }
725   free (st);
726 }
727
728
729
730
731 static const char *anemotaxis_defaults [] = {
732   ".background: black",
733   "*distance: 40",
734   "*sources: 25",
735   "*searchers: 25",
736   "*delay: 20000",
737   "*colors: 20",
738 #ifdef HAVE_DOUBLE_BUFFER_EXTENSION
739   "*useDBE:             True",
740 #endif
741   0
742 };
743
744
745 static XrmOptionDescRec anemotaxis_options [] = {
746   { "-delay",       ".delay",       XrmoptionSepArg, 0 },
747   { "-distance",    ".distance",    XrmoptionSepArg, 0 },
748   { "-sources",     ".sources",     XrmoptionSepArg, 0 },
749   { "-searchers",   ".searchers",   XrmoptionSepArg, 0 },
750   { "-colors",      ".colors",      XrmoptionSepArg, 0 },
751   { 0, 0, 0, 0 }
752 };
753
754
755 XSCREENSAVER_MODULE ("Anemotaxis", anemotaxis)