/* anemotaxis, Copyright (c) 2004 Eugene Balkovski * * Permission to use, copy, modify, distribute, and sell this software * and its documentation for any purpose is hereby granted without * fee, provided that the above copyright notice appear in all copies * and that both that copyright notice and this permission notice * appear in supporting documentation. No representations are made * about the suitability of this software for any purpose. It is * provided "as is" without express or implied warranty. */ /*------------------------------------------------------------------------ | | FILE anemotaxis.c | | DESCRIPTION Anemotaxis | | This code illustrates an optimal algorithm designed | for searching a source of particles on a plane. | The particles drift in one direction and walk randomly | in the other. The only information available to the | searcher is the presence of a particle at its location | and the local direction from where particle arrived. | The algorithm "explains" the behavior | of some animals and insects | who use olfactory and directional cues to find | sources of odor (mates, food, home etc) in | turbulent atmosphere (odor-modulated anemotaxis), | e.g. male moths locating females who release | pheromones to attract males. The search trajectories | resemble the trajectories that the animals follow. | | | WRITTEN BY Eugene Balkovski | | MODIFICATIONS june 2004 started | +----------------------------------------------------------------------*/ /* Options: -distance size of the lattice -sources number of sources -searhers number of searcher */ #include "screenhack.h" #ifdef HAVE_DOUBLE_BUFFER_EXTENSION #include "xdbe.h" #endif /*-----------------------------------------------------------------------+ | PRIVATE DATA | +-----------------------------------------------------------------------*/ #define MAX_DIST 250 #define MIN_DIST 10 #define LINE_WIDTH 4 #define MAX_INV_RATE 5 #define RND(x) (random() % (x)) #define X(x) ((int) (st->ax * (x) + st->bx)) #define Y(x) ((int) (st->ay * (x) + st->by)) typedef struct { short x; short y; } Point; typedef struct { short y; /* y-coordinate of the particle (relative to the source) */ short v; /* velocity of the particle. Allowed values are -1, 0, 1. 2 means the particle is not valid */ } YV; typedef struct { int n; /* size of array xv */ YV *yv; /* yv[i] keeps velocity and y-coordinate of the particle at (i + 1, yv[i].y) relative to the source */ int inv_rate; /* Inverse rate of particle emission (if 0 then source doesn't emit new particles (although old ones can still exist )*/ Point r; /* Position of the source */ long color; } Source; typedef struct PList { Point r; struct PList *next; } PList; typedef enum {UP_LEFT, UP_RIGHT, LEFT, RIGHT, DONE} State_t; typedef struct { Point r; /* Current position */ Point vertex; /* Position of the vertex of the most recent cone, which is the region where the source is located. We do exhaustive search in the cone until we encounter a new particle, which gives us a new cone. */ State_t state; /* Internal state variable */ unsigned char c; /* Concentration at r */ short v; /* Velocity at r (good only when c != 0) */ PList *hist; /* Trajectory */ int rs; /* small shift of x-coordinate to avoid painting over the same x */ long color; } Searcher; struct state { Source **source; Searcher **searcher; int max_dist, max_src, max_searcher; double ax, ay, bx, by; int dx, dy; Display *dpy; Window window; Pixmap b, ba, bb; #ifdef HAVE_DOUBLE_BUFFER_EXTENSION XdbeBackBuffer backb; #endif long delay; /* usecs to wait between updates. */ int scrWidth, scrHeight; GC gcDraw, gcClear; Bool dbuf; XGCValues gcv; Colormap cmap; XColor *colors; int ncolors; }; /*-----------------------------------------------------------------------+ | PUBLIC DATA | +-----------------------------------------------------------------------*/ /*-----------------------------------------------------------------------+ | PRIVATE FUNCTIONS | +-----------------------------------------------------------------------*/ static void *emalloc(size_t size) { void *ret = malloc(size); if (ret == NULL) { fprintf(stderr, "out of memory\n"); exit(1); } return ret; } static Searcher *new_searcher(struct state *st) { Searcher *m = (Searcher *) emalloc(sizeof(Searcher)); m->r.x = m->vertex.x = st->max_dist; do { m->r.y = RND(2 * st->max_dist); } while(m->r.y < MIN_DIST || m->r.y > 2 * st->max_dist - MIN_DIST); m->vertex.y = m->r.y; m->state = (RND(2) == 0 ? UP_RIGHT : UP_LEFT); m->hist = NULL; m->color = st->colors[random() % st->ncolors].pixel; m->rs = RND(st->dx); return m; } static void destroy_searcher(Searcher *m) { PList *p = m->hist, *q; while(p != NULL) { q = p->next; free(p); p = q; } free(m); } static void write_hist(Searcher *m) { PList *l; l = m->hist; m->hist = (PList *) emalloc(sizeof(PList)); m->hist->next = l; m->hist->r = m->r; } static void move_searcher(Searcher *m) { if(m->c == True) { write_hist(m); m->r.x -= 1; m->r.y -= m->v; write_hist(m); m->state = (RND(2) == 0 ? UP_LEFT : UP_RIGHT); m->vertex = m->r; return; } switch(m->state) { case UP_LEFT: m->r.x -= 1; m->r.y += 1; m->state = RIGHT; write_hist(m); return; case RIGHT: m->r.y -= 1; if(m->vertex.x - m->r.x == m->vertex.y - m->r.y) { write_hist(m); m->state = UP_RIGHT; } return; case UP_RIGHT: m->r.x -= 1; m->r.y -= 1; m->state = LEFT; write_hist(m); return; case LEFT: m->r.y += 1; if(m->vertex.x - m->r.x == m->r.y - m->vertex.y) { write_hist(m); m->state = UP_LEFT; } return; default: break; } } static void evolve_source(Source *s) { int i; /* propagate existing particles */ for(i = s->n - 1; i > 0; i--) { if(s->yv[i - 1].v == 2) s->yv[i].v = 2; else { s->yv[i].v = RND(3) - 1; s->yv[i].y = s->yv[i - 1].y + s->yv[i].v; } } if(s->inv_rate > 0 && (RND(s->inv_rate) == 0)) /* emit a particle */ s->yv[0].y = s->yv[0].v = RND(3) - 1; else s->yv[0].v = 2; } static Source *new_source(struct state *st) { int i; Source *s = (Source *) emalloc(sizeof(Source)); if(st->max_searcher == 0) { s->r.x = 0; s->r.y = RND(2 * st->max_dist); } else { s->r.x = RND(st->max_dist / 3); do { s->r.y = RND(2 * st->max_dist); } while(s->r.y < MIN_DIST || s->r.y > 2 * st->max_dist - MIN_DIST); } s->n = st->max_dist - s->r.x; s->yv = emalloc(sizeof(YV) * s->n); for(i = 0; i < s->n; i++) s->yv[i].v = 2; s->inv_rate = RND(MAX_INV_RATE); if(s->inv_rate == 0) s->inv_rate = 1; s->color = st->colors[random() % st->ncolors].pixel; return s; } static void destroy_source(Source *s) { free(s->yv); free(s); } static void get_v(const Source *s, Searcher *m) { int x = m->r.x - s->r.x - 1; m->c = 0; if(x < 0 || x >= s->n) return; if((s->yv[x].v == 2) || (s->yv[x].y != m->r.y - s->r.y)) return; m->c = 1; m->v = s->yv[x].v; m->color = s->color; } static void * anemotaxis_init (Display *disp, Window win) { struct state *st = (struct state *) calloc (1, sizeof(*st)); XWindowAttributes wa; st->dpy = disp; st->window = win; XGetWindowAttributes(st->dpy, st->window, &wa); st->ncolors = get_integer_resource (st->dpy, "colors", "Colors"); st->ncolors++; st->colors = (XColor *) malloc(sizeof(*st->colors) * (st->ncolors+1)); make_random_colormap (wa.screen, wa.visual, wa.colormap, st->colors, &st->ncolors, True, True, 0, True); st->delay = get_integer_resource(st->dpy, "delay", "Integer"); st->max_dist = get_integer_resource(st->dpy, "distance", "Integer"); if(st->max_dist < MIN_DIST) st->max_dist = MIN_DIST + 1; if(st->max_dist > MAX_DIST) st->max_dist = MAX_DIST; st->max_src = get_integer_resource(st->dpy, "sources", "Integer"); if(st->max_src <= 0) st->max_src = 1; st->max_searcher = get_integer_resource(st->dpy, "searchers", "Integer"); if(st->max_searcher < 0) st->max_searcher = 0; st->dbuf = True; # ifdef HAVE_JWXYZ /* Don't second-guess Quartz's double-buffering */ st->dbuf = False; # endif st->source = (Source **) emalloc(sizeof(Source *) * st->max_src); memset(st->source, 0, st->max_src * sizeof(Source *)); st->source[0] = new_source(st); st->searcher = (Searcher **) emalloc(st->max_searcher * sizeof(Searcher *)); memset(st->searcher, 0, st->max_searcher * sizeof(Searcher *)); st->b = st->ba = st->bb = 0; /* double-buffer to reduce flicker */ #ifdef HAVE_DOUBLE_BUFFER_EXTENSION st->b = st->backb = xdbe_get_backbuffer (st->dpy, st->window, XdbeUndefined); #endif st->scrWidth = wa.width; st->scrHeight = wa.height; st->cmap = wa.colormap; st->gcDraw = XCreateGC(st->dpy, st->window, 0, &st->gcv); st->gcv.foreground = get_pixel_resource(st->dpy, st->cmap, "background", "Background"); st->gcClear = XCreateGC(st->dpy, st->window, GCForeground, &st->gcv); if (st->dbuf) { if (!st->b) { st->ba = XCreatePixmap (st->dpy, st->window, st->scrWidth, st->scrHeight, wa.depth); st->bb = XCreatePixmap (st->dpy, st->window, st->scrWidth, st->scrHeight, wa.depth); st->b = st->ba; } } else st->b = st->window; if (st->ba) XFillRectangle (st->dpy, st->ba, st->gcClear, 0, 0, st->scrWidth, st->scrHeight); if (st->bb) XFillRectangle (st->dpy, st->bb, st->gcClear, 0, 0, st->scrWidth, st->scrHeight); st->ax = st->scrWidth / (double) st->max_dist; st->ay = st->scrHeight / (2. * st->max_dist); st->bx = 0.; st->by = 0.; if((st->dx = st->scrWidth / (2 * st->max_dist)) == 0) st->dx = 1; if((st->dy = st->scrHeight / (4 * st->max_dist)) == 0) st->dy = 1; XSetLineAttributes(st->dpy, st->gcDraw, st->dx / 3 + 1, LineSolid, CapRound, JoinRound); XClearWindow(st->dpy, st->window); return st; } static void draw_searcher(struct state *st, Drawable curr_window, int i) { Point r1, r2; PList *l; if(st->searcher[i] == NULL) return; XSetForeground(st->dpy, st->gcDraw, st->searcher[i]->color); r1.x = X(st->searcher[i]->r.x) + st->searcher[i]->rs; r1.y = Y(st->searcher[i]->r.y); XFillRectangle(st->dpy, curr_window, st->gcDraw, r1.x - 2, r1.y - 2, 4, 4); for(l = st->searcher[i]->hist; l != NULL; l = l->next) { r2.x = X(l->r.x) + st->searcher[i]->rs; r2.y = Y(l->r.y); XDrawLine(st->dpy, curr_window, st->gcDraw, r1.x, r1.y, r2.x, r2.y); r1 = r2; } } static void draw_image(struct state *st, Drawable curr_window) { int i, j; int x, y; for(i = 0; i < st->max_src; i++) { if(st->source[i] == NULL) continue; XSetForeground(st->dpy, st->gcDraw, st->source[i]->color); if(st->source[i]->inv_rate > 0) { if(st->max_searcher > 0) { x = (int) X(st->source[i]->r.x); y = (int) Y(st->source[i]->r.y); j = st->dx * (MAX_INV_RATE + 1 - st->source[i]->inv_rate) / (2 * MAX_INV_RATE); if(j == 0) j = 1; XFillArc(st->dpy, curr_window, st->gcDraw, x - j, y - j, 2 * j, 2 * j, 0, 360 * 64); }} for(j = 0; j < st->source[i]->n; j++) { int size = (st->scrWidth > 2560 ? 8 : 4); /* Retina displays */ if(st->source[i]->yv[j].v == 2) continue; /* Move the particles slightly off lattice */ x = X(st->source[i]->r.x + 1 + j) + RND(st->dx); y = Y(st->source[i]->r.y + st->source[i]->yv[j].y) + RND(st->dy); XFillArc(st->dpy, curr_window, st->gcDraw, x - size/2, y - size/2, size, size, 0, 360 * 64); } } for(i = 0; i < st->max_searcher; i++) draw_searcher(st, curr_window, i); } static void animate_anemotaxis(struct state *st, Drawable curr_window) { int i, j; Bool dead; for(i = 0; i < st->max_src; i++) { if(st->source[i] == NULL) continue; evolve_source(st->source[i]); /* reap dead sources for which all particles are gone */ if(st->source[i]->inv_rate == 0) { dead = True; for(j = 0; j < st->source[i]->n; j++) { if(st->source[i]->yv[j].v != 2) { dead = False; break; } } if(dead == True) { destroy_source(st->source[i]); st->source[i] = NULL; } } } /* Decide if we want to add new sources */ for(i = 0; i < st->max_src; i++) { if(st->source[i] == NULL && RND(st->max_dist * st->max_src) == 0) st->source[i] = new_source(st); } if(st->max_searcher == 0) { /* kill some sources when searchers don't do that */ for(i = 0; i < st->max_src; i++) { if(st->source[i] != NULL && RND(st->max_dist * st->max_src) == 0) { destroy_source(st->source[i]); st->source[i] = 0; } } } /* Now deal with searchers */ for(i = 0; i < st->max_searcher; i++) { if((st->searcher[i] != NULL) && (st->searcher[i]->state == DONE)) { destroy_searcher(st->searcher[i]); st->searcher[i] = NULL; } if(st->searcher[i] == NULL) { if(RND(st->max_dist * st->max_searcher) == 0) { st->searcher[i] = new_searcher(st); } } if(st->searcher[i] == NULL) continue; /* Check if searcher found a source or missed all of them */ for(j = 0; j < st->max_src; j++) { if(st->source[j] == NULL || st->source[j]->inv_rate == 0) continue; if(st->searcher[i]->r.x < 0) { st->searcher[i]->state = DONE; break; } if((st->source[j]->r.y == st->searcher[i]->r.y) && (st->source[j]->r.x == st->searcher[i]->r.x)) { st->searcher[i]->state = DONE; st->source[j]->inv_rate = 0; /* source disappears */ /* Make it flash */ st->searcher[i]->color = WhitePixel(st->dpy, DefaultScreen(st->dpy)); break; } } st->searcher[i]->c = 0; /* set it here in case we don't get to get_v() */ /* Find the concentration at searcher's location */ if(st->searcher[i]->state != DONE) { for(j = 0; j < st->max_src; j++) { if(st->source[j] == NULL) continue; get_v(st->source[j], st->searcher[i]); if(st->searcher[i]->c == 1) break; } } move_searcher(st->searcher[i]); } draw_image(st, curr_window); } static unsigned long anemotaxis_draw (Display *disp, Window window, void *closure) { struct state *st = (struct state *) closure; XWindowAttributes wa; int w, h; XGetWindowAttributes(st->dpy, st->window, &wa); w = wa.width; h = wa.height; if(w != st->scrWidth || h != st->scrHeight) { st->scrWidth = w; st->scrHeight = h; st->ax = st->scrWidth / (double) st->max_dist; st->ay = st->scrHeight / (2. * st->max_dist); st->bx = 0.; st->by = 0.; if((st->dx = st->scrWidth / (2 * st->max_dist)) == 0) st->dx = 1; if((st->dy = st->scrHeight / (4 * st->max_dist)) == 0) st->dy = 1; XSetLineAttributes(st->dpy, st->gcDraw, st->dx / 3 + 1, LineSolid, CapRound, JoinRound); } XFillRectangle (st->dpy, st->b, st->gcClear, 0, 0, st->scrWidth, st->scrHeight); animate_anemotaxis(st, st->b); #ifdef HAVE_DOUBLE_BUFFER_EXTENSION if (st->backb) { XdbeSwapInfo info[1]; info[0].swap_window = st->window; info[0].swap_action = XdbeUndefined; XdbeSwapBuffers (st->dpy, info, 1); } else #endif if (st->dbuf) { XCopyArea (st->dpy, st->b, st->window, st->gcClear, 0, 0, st->scrWidth, st->scrHeight, 0, 0); st->b = (st->b == st->ba ? st->bb : st->ba); } return st->delay; } static void anemotaxis_reshape (Display *dpy, Window window, void *closure, unsigned int w, unsigned int h) { } static Bool anemotaxis_event (Display *dpy, Window window, void *closure, XEvent *event) { return False; } static void anemotaxis_free (Display *dpy, Window window, void *closure) { struct state *st = (struct state *) closure; int i; if (st->source) { for (i = 0; i < st->max_src; i++) if (st->source[i]) destroy_source (st->source[i]); free (st->source); } if (st->searcher) { for (i = 0; i < st->max_searcher; i++) if (st->searcher[i]) destroy_searcher (st->searcher[i]); free (st->searcher); } XFreeGC (dpy, st->gcDraw); XFreeGC (dpy, st->gcClear); free (st->colors); free (st); } static const char *anemotaxis_defaults [] = { ".background: black", "*distance: 40", "*sources: 25", "*searchers: 25", "*delay: 20000", "*colors: 20", #ifdef HAVE_DOUBLE_BUFFER_EXTENSION "*useDBE: True", #endif 0 }; static XrmOptionDescRec anemotaxis_options [] = { { "-delay", ".delay", XrmoptionSepArg, 0 }, { "-distance", ".distance", XrmoptionSepArg, 0 }, { "-sources", ".sources", XrmoptionSepArg, 0 }, { "-searchers", ".searchers", XrmoptionSepArg, 0 }, { "-colors", ".colors", XrmoptionSepArg, 0 }, { 0, 0, 0, 0 } }; XSCREENSAVER_MODULE ("Anemotaxis", anemotaxis)