/* 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);
}
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)