summaryrefslogtreecommitdiffstats
path: root/hacks/anemotaxis.c
diff options
context:
space:
mode:
Diffstat (limited to 'hacks/anemotaxis.c')
-rw-r--r--hacks/anemotaxis.c755
1 files changed, 755 insertions, 0 deletions
diff --git a/hacks/anemotaxis.c b/hacks/anemotaxis.c
new file mode 100644
index 0000000..9f240e8
--- /dev/null
+++ b/hacks/anemotaxis.c
@@ -0,0 +1,755 @@
+/* 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 <arg> size of the lattice
+ -sources <arg> number of sources
+ -searhers <arg> 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);
+ }
+ 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)
generated by cgit v1.2.3-55-g7522 (git 2.39.0) at 2024-05-18 05:40:07 +0200