modules/swarm: implement a particles swarm module

Just a fun little swarm based loosely on 80s-era boids

It would be interesting to make stuff like the # of particles
and the weights runtime configurable, or exposed as knobs.

Using a Z-buffer for occlusions and perhaps shading by depth might
make a significant improvement on the visual quality.  It might also
be interesting to draw the particles as lines connecting their current
position with their previous, instead as pixels.  Or fat pixels like
stars...

7 files changed, 287 insertions, 2 deletions

diff --git a/README b/README
index eae01c5..5f4c952 100644
--- a/README
+++ b/README
@@ -16,6 +16,7 @@ rototiller is, rendered entirely in software:
 	stars: a starfield simulator
 	submit: a 2D cellular automata game sim
 	swab: a colorful perlin-noise visualization
+	swarm: "Boids"-inspired particle swarm in 3D
 
 ---
 
diff --git a/configure.ac b/configure.ac
index f7dcd7c..3121644 100644
--- a/configure.ac
+++ b/configure.ac
@@ -61,5 +61,6 @@ AC_CONFIG_FILES([
  src/modules/stars/Makefile
  src/modules/submit/Makefile
  src/modules/swab/Makefile
+ src/modules/swarm/Makefile
 ])
 AC_OUTPUT
diff --git a/src/Makefile.am b/src/Makefile.am
index a21cb6f..d65eb5c 100644
--- a/src/Makefile.am
+++ b/src/Makefile.am
@@ -4,4 +4,4 @@ rototiller_SOURCES = fb.c fb.h fps.c fps.h knobs.h rototiller.c rototiller.h sdl
 if ENABLE_DRM
 rototiller_SOURCES += drm_fb.c
 endif
-rototiller_LDADD = modules/compose/libcompose.a modules/drizzle/libdrizzle.a modules/flui2d/libflui2d.a modules/julia/libjulia.a modules/meta2d/libmeta2d.a modules/montage/libmontage.a modules/pixbounce/libpixbounce.a modules/plasma/libplasma.a modules/plato/libplato.a modules/ray/libray.a modules/roto/libroto.a modules/rtv/librtv.a modules/snow/libsnow.a modules/sparkler/libsparkler.a modules/spiro/libspiro.a modules/stars/libstars.a modules/submit/libsubmit.a modules/swab/libswab.a libs/grid/libgrid.a libs/puddle/libpuddle.a libs/ray/libray.a libs/sig/libsig.a libs/txt/libtxt.a libs/ascii/libascii.a libs/din/libdin.a -lm
+rototiller_LDADD = modules/compose/libcompose.a modules/drizzle/libdrizzle.a modules/flui2d/libflui2d.a modules/julia/libjulia.a modules/meta2d/libmeta2d.a modules/montage/libmontage.a modules/pixbounce/libpixbounce.a modules/plasma/libplasma.a modules/plato/libplato.a modules/ray/libray.a modules/roto/libroto.a modules/rtv/librtv.a modules/snow/libsnow.a modules/sparkler/libsparkler.a modules/spiro/libspiro.a modules/stars/libstars.a modules/submit/libsubmit.a modules/swab/libswab.a modules/swarm/libswarm.a libs/grid/libgrid.a libs/puddle/libpuddle.a libs/ray/libray.a libs/sig/libsig.a libs/txt/libtxt.a libs/ascii/libascii.a libs/din/libdin.a -lm
diff --git a/src/modules/Makefile.am b/src/modules/Makefile.am
index d2c4636..28fc7fd 100644
--- a/src/modules/Makefile.am
+++ b/src/modules/Makefile.am
@@ -1 +1 @@
-SUBDIRS = compose drizzle flui2d julia meta2d montage pixbounce plasma plato ray roto rtv snow sparkler spiro stars submit swab
+SUBDIRS = compose drizzle flui2d julia meta2d montage pixbounce plasma plato ray roto rtv snow sparkler spiro stars submit swab swarm
diff --git a/src/modules/swarm/Makefile.am b/src/modules/swarm/Makefile.am
new file mode 100644
index 0000000..327aee8
--- /dev/null
+++ b/src/modules/swarm/Makefile.am
@@ -0,0 +1,3 @@
+noinst_LIBRARIES = libswarm.a
+libswarm_a_SOURCES = swarm.c
+libswarm_a_CPPFLAGS = -I@top_srcdir@/src -I@top_srcdir@/src/libs
diff --git a/src/modules/swarm/swarm.c b/src/modules/swarm/swarm.c
new file mode 100644
index 0000000..4ebd79e
--- /dev/null
+++ b/src/modules/swarm/swarm.c
@@ -0,0 +1,278 @@
+/*
+ *  Copyright (C) 2021 - Vito Caputo - <vcaputo@pengaru.com>
+ *
+ *  This program is free software: you can redistribute it and/or modify it
+ *  under the terms of the GNU General Public License version 3 as published
+ *  by the Free Software Foundation.
+ *
+ *  This program is distributed in the hope that it will be useful,
+ *  but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ *  GNU General Public License for more details.
+ *
+ *  You should have received a copy of the GNU General Public License
+ *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ */
+
+/* this implements a very simplified "boids" inspired particles swarm
+ * http://www.red3d.com/cwr/boids/
+ * https://en.wikipedia.org/wiki/Boids
+ * https://en.wikipedia.org/wiki/Swarm_intelligence
+ */
+
+#include <stdlib.h>
+#include <unistd.h>
+#include <math.h>
+
+#include "fb.h"
+#include "rototiller.h"
+
+#define SWARM_SIZE	(32 * 1024)
+#define SWARM_ZCONST	4.f
+
+typedef struct v3f_t {
+	float	x, y, z;
+} v3f_t;
+
+typedef struct v2f_t {
+	float	x, y;
+} v2f_t;
+
+typedef struct boid_t {
+	v3f_t	position;
+	v3f_t	direction;
+	float	velocity;
+} boid_t;
+
+typedef struct swarm_context_t {
+	v3f_t		color;
+	float		ztweak;
+	boid_t		boids[];
+} swarm_context_t;
+
+
+static inline float randf(float min, float max)
+{
+	return ((float)rand() / (float)RAND_MAX) * (max - min) + min;
+}
+
+
+static inline void v3f_rand(v3f_t *v, float min, float max)
+{
+	v->x = randf(min, max);
+	v->y = randf(min, max);
+	v->z = randf(min, max);
+}
+
+
+static inline v3f_t v3f_add(v3f_t a, v3f_t b)
+{
+	return (v3f_t){
+		.x = a.x + b.x,
+		.y = a.y + b.y,
+		.z = a.z + b.z,
+	};
+}
+
+
+static inline v3f_t v3f_sub(v3f_t a, v3f_t b)
+{
+	return (v3f_t){
+		.x = a.x - b.x,
+		.y = a.y - b.y,
+		.z = a.z - b.z,
+	};
+}
+
+
+static inline v3f_t v3f_mult_scalar(v3f_t v, float scalar)
+{
+	return (v3f_t){
+		.x = v.x * scalar,
+		.y = v.y * scalar,
+		.z = v.z * scalar,
+	};
+}
+
+
+static inline float v3f_len(v3f_t v)
+{
+	return sqrtf(v.x * v.x + v.y * v.y + v.z * v.z);
+}
+
+
+static inline void v3f_normalize(v3f_t *v)
+{
+	float	l = 1.f / v3f_len(*v);
+
+	v->x *= l;
+	v->y *= l;
+	v->z *= l;
+}
+
+
+static v3f_t v3f_lerp(v3f_t a, v3f_t b, float t)
+{
+	return (v3f_t){
+		.x = (b.x - a.x) * t + a.x,
+		.y = (b.y - a.y) * t + a.y,
+		.z = (b.z - a.z) * t + a.z,
+	};
+}
+
+
+static void boid_randomize(boid_t *boid)
+{
+	v3f_rand(&boid->position, -1.f, 1.f);
+	v3f_rand(&boid->direction, -1.f, 1.f);
+	v3f_normalize(&boid->direction);
+	boid->velocity = randf(.05f, .2f);
+}
+
+
+/* convert a color into a packed, 32-bit rgb pixel value (taken from libs/ray/ray_color.h) */
+static inline uint32_t color_to_uint32(v3f_t color) {
+	uint32_t	pixel;
+
+	if (color.x > 1.0f) color.x = 1.0f;
+	if (color.y > 1.0f) color.y = 1.0f;
+	if (color.z > 1.0f) color.z = 1.0f;
+
+	if (color.x < .0f) color.x = .0f;
+	if (color.y < .0f) color.y = .0f;
+	if (color.z < .0f) color.z = .0f;
+
+	pixel = (uint32_t)(color.x * 255.0f);
+	pixel <<= 8;
+	pixel |= (uint32_t)(color.y * 255.0f);
+	pixel <<= 8;
+	pixel |= (uint32_t)(color.z * 255.0f);
+
+	return pixel;
+}
+
+
+static void * swarm_create_context(unsigned ticks, unsigned num_cpus)
+{
+	swarm_context_t	*ctxt;
+
+	ctxt = calloc(1, sizeof(swarm_context_t) + sizeof(*(ctxt->boids)) * SWARM_SIZE);
+	if (!ctxt)
+		return NULL;
+
+	for (unsigned i = 0; i < SWARM_SIZE; i++)
+		boid_randomize(&ctxt->boids[i]);
+
+	return ctxt;
+}
+
+
+static void swarm_destroy_context(void *context)
+{
+	swarm_context_t	*ctxt = context;
+
+	free(ctxt);
+}
+
+
+static void swarm_update(swarm_context_t *ctxt, unsigned ticks)
+{
+	v3f_t	avg_direction = {};
+	float	avg_velocity = 0.f;
+	v3f_t	avg_center = {};
+	float	wleader, wcenter, wdirection;
+
+	{ /* [0] = leader */
+		float	r = (float)ticks * ((cosf((float)ticks * .0001f) * .5f + .5f) * .1f);
+
+		ctxt->boids[0].position.x = cosf(r);
+		ctxt->boids[0].position.y = sinf(r);
+		ctxt->boids[0].position.z = cosf(r * 2.f);
+	}
+
+	/* characterize the current swarm */
+	for (unsigned i = 0; i < SWARM_SIZE; i++) {
+		boid_t	*b = &ctxt->boids[i];
+
+		avg_center = v3f_add(avg_center, b->position);
+		avg_direction = v3f_add(avg_direction, b->direction);
+		avg_velocity += b->velocity;
+	}
+
+	avg_velocity *= (1.f / (float)SWARM_SIZE);
+	avg_center = v3f_mult_scalar(avg_center, (1.f / (float)SWARM_SIZE));
+	avg_direction = v3f_mult_scalar(avg_direction, (1.f / (float)SWARM_SIZE));
+	v3f_normalize(&avg_direction);
+
+	/* vary weights */
+	wleader = cosf((float)ticks * .001f) * .5f + .5f;
+	wcenter = cosf((float)ticks * .0005f) * .5f + .5f;
+	wdirection = sinf((float)ticks * .003f) * .5f + .5f;
+
+	/* update the followers in relation to leader and swarm itself */
+	for (unsigned i = 1; i < SWARM_SIZE; i++) {
+		boid_t	*b = &ctxt->boids[i];
+		v3f_t	to_leader = v3f_sub(ctxt->boids[0].position, b->position);
+		v3f_t	to_center = v3f_sub(avg_center, b->position);
+
+		v3f_normalize(&to_leader);
+		b->direction = v3f_lerp(b->direction, to_leader, wleader * .1f);
+		v3f_normalize(&b->direction);
+		b->direction = v3f_lerp(b->direction, to_center, wcenter * .1f);
+		v3f_normalize(&b->direction);
+		b->direction = v3f_lerp(b->direction, avg_direction, wdirection * .05f);
+		v3f_normalize(&b->direction);
+
+		b->position = v3f_add(b->position, v3f_mult_scalar(b->direction, b->velocity));
+	}
+
+	/* color the swarm according to the current weights */
+	ctxt->color.x = wleader;
+	ctxt->color.y = wcenter;
+	ctxt->color.z = wdirection;
+
+	/* this zooms out a bit when the swarm loosens up, gauged by low weights */
+	ctxt->ztweak = (1.8f - v3f_len(ctxt->color)) * 4.f;
+}
+
+
+static void swarm_render_fragment(void *context, unsigned ticks, unsigned cpu, fb_fragment_t *fragment)
+{
+	swarm_context_t	*ctxt = context;
+
+	swarm_update(ctxt, ticks);
+
+	fb_fragment_zero(fragment);
+
+	{
+		float		fw = fragment->frame_width, fh = fragment->frame_height;
+		uint32_t	color = color_to_uint32(ctxt->color);
+
+		fw *= .5f;
+		fh *= .5f;
+
+		for (unsigned i = 0; i < SWARM_SIZE; i++) {
+			boid_t	*b = &ctxt->boids[i];
+			v2f_t	nc;
+
+			nc.x = b->position.x / (b->position.z + SWARM_ZCONST + ctxt->ztweak);
+			nc.y = b->position.y / (b->position.z + SWARM_ZCONST + ctxt->ztweak);
+
+			nc.x = nc.x * fw + fw;
+			nc.y = nc.y * fh + fh;
+
+			fb_fragment_put_pixel_checked(fragment, nc.x, nc.y, color);
+		}
+	}
+}
+
+
+rototiller_module_t	swarm_module = {
+	.create_context = swarm_create_context,
+	.destroy_context = swarm_destroy_context,
+	.render_fragment = swarm_render_fragment,
+	.name = "swarm",
+	.description = "\"Boids\"-inspired particle swarm in 3D",
+	.author = "Vito Caputo <vcaputo@pengaru.com>",
+	.license = "GPLv3",
+};
diff --git a/src/rototiller.c b/src/rototiller.c
index 7e96545..6857e72 100644
--- a/src/rototiller.c
+++ b/src/rototiller.c
@@ -51,6 +51,7 @@ extern rototiller_module_t	spiro_module;
 extern rototiller_module_t	stars_module;
 extern rototiller_module_t	submit_module;
 extern rototiller_module_t	swab_module;
+extern rototiller_module_t	swarm_module;
 
 static const rototiller_module_t	*modules[] = {
 	&compose_module,
@@ -71,6 +72,7 @@ static const rototiller_module_t	*modules[] = {
 	&stars_module,
 	&submit_module,
 	&swab_module,
+	&swarm_module,
 };
 
 typedef struct rototiller_t {