1 /* anemotaxis, Copyright (c) 2004 Eugene Balkovski
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.
12 /*------------------------------------------------------------------------
16 | DESCRIPTION Anemotaxis
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.
34 | WRITTEN BY Eugene Balkovski
36 | MODIFICATIONS june 2004 started
38 +----------------------------------------------------------------------*/
43 -distance <arg> size of the lattice
44 -sources <arg> number of sources
45 -searhers <arg> number of searcher */
51 #include "screenhack.h"
53 #ifdef HAVE_DOUBLE_BUFFER_EXTENSION
58 /*-----------------------------------------------------------------------+
60 +-----------------------------------------------------------------------*/
65 #define MAX_INV_RATE 5
67 #define RND(x) (random() % (x))
68 #define X(x) ((int) (ax * (x) + bx))
69 #define Y(x) ((int) (ay * (x) + by))
78 short y; /* y-coordinate of the particle (relative to the source) */
80 short v; /* velocity of the particle. Allowed values are -1, 0, 1.
81 2 means the particle is not valid */
86 int n; /* size of array xv */
88 YV *yv; /* yv[i] keeps velocity and y-coordinate of the
89 particle at (i + 1, yv[i].y) relative to the
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 )*/
96 Point r; /* Position of the source */
103 typedef struct PList {
108 typedef enum {UP_LEFT, UP_RIGHT, LEFT, RIGHT, DONE} State_t;
110 typedef enum {FALSE = 0, TRUE = 1} bool;
114 Point r; /* Current position */
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. */
122 State_t state; /* Internal state variable */
124 unsigned char c; /* Concentration at r */
126 short v; /* Velocity at r (good only when c != 0) */
128 PList *hist; /* Trajectory */
130 int rs; /* small shift of x-coordinate to avoid
131 painting over the same x */
137 static Source **source;
138 static Searcher **searcher;
140 static int max_dist, max_src, max_searcher;
142 static double ax, ay, bx, by;
146 static Window window;
148 static Pixmap b, ba, bb;
150 #ifdef HAVE_DOUBLE_BUFFER_EXTENSION
151 static XdbeBackBuffer backb;
154 static long delay; /* usecs to wait between updates. */
156 static int scrWidth, scrHeight;
157 static GC gcDraw, gcClear;
161 static XGCValues gcv;
162 static Colormap cmap;
165 /*-----------------------------------------------------------------------+
167 +-----------------------------------------------------------------------*/
169 char *progclass = "Anemotaxis";
171 char *defaults [] = {
172 ".background: black",
177 #ifdef HAVE_DOUBLE_BUFFER_EXTENSION
184 XrmOptionDescRec options [] = {
185 { "-delay", ".delay", XrmoptionSepArg, 0 },
186 { "-distance", ".distance", XrmoptionSepArg, 0 },
187 { "-sources", ".sources", XrmoptionSepArg, 0 },
188 { "-searchers", ".searchers", XrmoptionSepArg, 0 },
194 /*-----------------------------------------------------------------------+
195 | PRIVATE FUNCTIONS |
196 +-----------------------------------------------------------------------*/
198 static void *emalloc(size_t size)
200 void *ret = malloc(size);
203 fprintf(stderr, "out of memory\n");
209 static Searcher *new_searcher(void)
211 Searcher *m = (Searcher *) emalloc(sizeof(Searcher));
213 m->r.x = m->vertex.x = max_dist;
216 m->r.y = RND(2 * max_dist);
217 } while(m->r.y < MIN_DIST || m->r.y > 2 * max_dist - MIN_DIST);
219 m->vertex.y = m->r.y;
221 m->state = (RND(2) == 0 ? UP_RIGHT : UP_LEFT);
230 static void destroy_searcher(Searcher *m)
232 PList *p = m->hist, *q;
243 static void write_hist(Searcher *m)
248 m->hist = (PList *) emalloc(sizeof(PList));
254 static void move_searcher(Searcher *m)
262 m->state = (RND(2) == 0 ? UP_LEFT : UP_RIGHT);
280 if(m->vertex.x - m->r.x == m->vertex.y - m->r.y) {
299 if(m->vertex.x - m->r.x == m->r.y - m->vertex.y) {
311 static void evolve_source(Source *s)
316 /* propagate existing particles */
318 for(i = s->n - 1; i > 0; i--) {
320 if(s->yv[i - 1].v == 2)
323 s->yv[i].v = RND(3) - 1;
324 s->yv[i].y = s->yv[i - 1].y + s->yv[i].v;
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;
337 static Source *new_source(void)
341 Source *s = (Source *) emalloc(sizeof(Source));
342 if(max_searcher == 0) {
344 s->r.y = RND(2 * max_dist);
347 s->r.x = RND(max_dist / 3);
349 s->r.y = RND(2 * max_dist);
350 } while(s->r.y < MIN_DIST || s->r.y > 2 * max_dist - MIN_DIST);
353 s->n = max_dist - s->r.x;
354 s->yv = emalloc(sizeof(YV) * s->n);
356 for(i = 0; i < s->n; i++)
359 s->inv_rate = RND(MAX_INV_RATE);
369 static void destroy_source(Source *s)
375 static void get_v(const Source *s, Searcher *m)
377 int x = m->r.x - s->r.x - 1;
381 if(x < 0 || x >= s->n)
384 if((s->yv[x].v == 2) || (s->yv[x].y != m->r.y - s->r.y))
393 static void init_anemotaxis(void)
395 XWindowAttributes wa;
397 delay = get_integer_resource("delay", "Integer");
398 max_dist = get_integer_resource("distance", "Integer");
400 if(max_dist < MIN_DIST)
401 max_dist = MIN_DIST + 1;
402 if(max_dist > MAX_DIST)
405 max_src = get_integer_resource("sources", "Integer");
410 max_searcher = get_integer_resource("searchers", "Integer");
417 source = (Source **) emalloc(sizeof(Source *) * max_src);
418 memset(source, 0, max_src * sizeof(Source *));
420 source[0] = new_source();
422 searcher = (Searcher **) emalloc(max_searcher * sizeof(Searcher *));
424 memset(searcher, 0, max_searcher * sizeof(Searcher *));
426 b = ba = bb = 0; /* double-buffer to reduce flicker */
428 #ifdef HAVE_DOUBLE_BUFFER_EXTENSION
429 b = backb = xdbe_get_backbuffer (dpy, window, XdbeUndefined);
432 XGetWindowAttributes(dpy, window, &wa);
434 scrHeight = wa.height;
436 gcDraw = XCreateGC(dpy, window, GCForeground, &gcv);
437 gcv.foreground = get_pixel_resource("background", "Background", dpy, cmap);
438 gcClear = XCreateGC(dpy, window, GCForeground, &gcv);
442 ba = XCreatePixmap (dpy, window, scrWidth, scrHeight, wa.depth);
443 bb = XCreatePixmap (dpy, window, scrWidth, scrHeight, wa.depth);
451 if (ba) XFillRectangle (dpy, ba, gcClear, 0, 0, scrWidth, scrHeight);
452 if (bb) XFillRectangle (dpy, bb, gcClear, 0, 0, scrWidth, scrHeight);
454 ax = scrWidth / (double) max_dist;
455 ay = scrHeight / (2. * max_dist);
459 if((dx = scrWidth / (2 * max_dist)) == 0)
461 if((dy = scrHeight / (4 * max_dist)) == 0)
463 XSetLineAttributes(dpy, gcDraw, dx / 3 + 1, LineSolid, CapRound, JoinRound);
464 XClearWindow(dpy, window);
467 static void draw_searcher(Drawable curr_window, int i)
472 if(searcher[i] == NULL)
475 XSetForeground(dpy, gcDraw, searcher[i]->color);
477 r1.x = X(searcher[i]->r.x) + searcher[i]->rs;
478 r1.y = Y(searcher[i]->r.y);
480 XFillRectangle(dpy, curr_window, gcDraw, r1.x - 2, r1.y - 2, 4, 4);
482 for(l = searcher[i]->hist; l != NULL; l = l->next) {
484 r2.x = X(l->r.x) + searcher[i]->rs;
487 XDrawLine(dpy, curr_window, gcDraw, r1.x, r1.y, r2.x, r2.y);
494 static void draw_image(Drawable curr_window)
499 for(i = 0; i < max_src; i++) {
501 if(source[i] == NULL)
504 XSetForeground(dpy, gcDraw, source[i]->color);
506 if(source[i]->inv_rate > 0) {
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);
514 XFillArc(dpy, curr_window, gcDraw, x - j, y - j, 2 * j, 2 * j, 0, 360 * 64);
517 for(j = 0; j < source[i]->n; j++) {
519 if(source[i]->yv[j].v == 2)
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);
530 for(i = 0; i < max_searcher; i++)
531 draw_searcher(curr_window, i);
535 static void animate_anemotaxis(Drawable curr_window)
540 for(i = 0; i < max_src; i++) {
542 if(source[i] == NULL)
545 evolve_source(source[i]);
547 /* reap dead sources for which all particles are gone */
548 if(source[i]->inv_rate == 0) {
552 for(j = 0; j < source[i]->n; j++) {
553 if(source[i]->yv[j].v != 2) {
560 destroy_source(source[i]);
566 /* Decide if we want to add new sources */
568 for(i = 0; i < max_src; i++) {
569 if(source[i] == NULL && RND(max_dist * max_src) == 0)
570 source[i] = new_source();
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]);
582 /* Now deal with searchers */
584 for(i = 0; i < max_searcher; i++) {
586 if((searcher[i] != NULL) && (searcher[i]->state == DONE)) {
587 destroy_searcher(searcher[i]);
591 if(searcher[i] == NULL) {
593 if(RND(max_dist * max_searcher) == 0) {
595 searcher[i] = new_searcher();
600 if(searcher[i] == NULL)
603 /* Check if searcher found a source or missed all of them */
604 for(j = 0; j < max_src; j++) {
606 if(source[j] == NULL || source[j]->inv_rate == 0)
609 if(searcher[i]->r.x < 0) {
610 searcher[i]->state = DONE;
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 */
620 searcher[i]->color = WhitePixel(dpy, DefaultScreen(dpy));
626 searcher[i]->c = 0; /* set it here in case we don't get to get_v() */
628 /* Find the concentration at searcher's location */
630 if(searcher[i]->state != DONE) {
631 for(j = 0; j < max_src; j++) {
633 if(source[j] == NULL)
636 get_v(source[j], searcher[i]);
638 if(searcher[i]->c == 1)
643 move_searcher(searcher[i]);
647 draw_image(curr_window);
651 /*-----------------------------------------------------------------------+
653 +-----------------------------------------------------------------------*/
655 void screenhack(Display *disp, Window win)
658 XWindowAttributes wa;
669 XGetWindowAttributes(dpy, window, &wa);
674 if(w != scrWidth || h != scrHeight) {
677 ax = scrWidth / (double) max_dist;
678 ay = scrHeight / (2. * max_dist);
682 if((dx = scrWidth / (2 * max_dist)) == 0)
684 if((dy = scrHeight / (4 * max_dist)) == 0)
686 XSetLineAttributes(dpy, gcDraw, dx / 3 + 1, LineSolid, CapRound, JoinRound);
689 XFillRectangle (dpy, b, gcClear, 0, 0, scrWidth, scrHeight);
690 animate_anemotaxis(b);
692 #ifdef HAVE_DOUBLE_BUFFER_EXTENSION
694 XdbeSwapInfo info[1];
695 info[0].swap_window = window;
696 info[0].swap_action = XdbeUndefined;
697 XdbeSwapBuffers (dpy, info, 1);
702 XCopyArea (dpy, b, window, gcClear, 0, 0,
703 scrWidth, scrHeight, 0, 0);
704 b = (b == ba ? bb : ba);
707 screenhack_handle_events (dpy);