The Experiment
Dendrites have a disgusting alien appearance.
When a charged cathode is placed into a solution of some copper salts, it grows
these weird dendrites. Look at them, aren't they weird and alien? Let's all get together
to point and mock them for their strange appearance.
Once we are done mocking the strange creepy alien tentacles, we can try and understand
something about their formation. Entirely through intuition, I believe that these funny patterns
emerge through the following processing:
- Particles bounce around a beaker of whatever salt.
- A particle bumps into the cathode, the difference in charges makes him stick
- Copper is a good conductor, so that particle now conducts the charge from the cathode.
- Other particles are now more likely to bump into an attached particle.
- This repeats, the likelyhood of a particle on a random walk of hitting the cathode increasing with
every iteration.
Unfortunately I made all of that up and so I have no idea if it is true. However, if it were to be true
I would assume the following things to also be true:
- The longer a chain of attached particles are, that's to say the more it's broad side is broader than its narrow side, the more
likely it becomes to split. This I think is the primary reason the dendrites develop that disgusting coral shape that we were
mocking it for.
- The growth of the dendrites should be exponential, or something non-linear anyway.
- The growth of the dendrites is a function of the surface area of the existing dendrites.
So today let's try and verify that mechanism, by simulating only that mechanism and seeing if it makes weird disgusting
coral things.
2D Simulation
This simulation is nice and simple, that's because we're intentionally trying to use the model as a way to isolate
a specific mechanism- meaning we only have to make that one mechanism. Actually, the tricky part about this sort of
verification is you have to make sure you don't accidentally add in extra mechanisms.
In reality, computers are so complicated that it's almost impossible to not add in extra mechanisms. For example
if you use floating point numbers at all, you immediately add in all sorts of strange rounding errors and comparison faults- and
not trivial ones, ones that really matter! In my experience about half the hard mistakes made in modeling something complicated come
from floating points. It can be argued that the whole reason physics simulators are more than 500 lines, is because floating points
are bad.
Basic Setup
For our basic setup, we'll say particles exist in 2D space. They store their position and their velocity in F32 vectors.
Every frame, we'll look at how long its been since the last frame, multiply the velocity by that amount, and add it to our position.
Particles will start with a random position and a random velocity. If they go out of the frame, we'll randomize it again.
Spatial Partitioning
If you have ever worked in computer graphics, simulations, game development, or really any serious aspect of computer science,
you have had this problem before. We have some group of particles, or birds, or bounded volumes, or whatever, and we would like to run
some code when they bump into eachother.
The naive approach is to write some function testForCollision(a, b) then loop through all our particles
twice, and see if any particles collide. That's dumb though, don't do that, because it runs in O(n^2). The better way
to do it is to use some kind of spatial partitioning algorithm. We're going to implement a really easy one, that bounds the particles
by rounding down their positions, and seeing if they overlap.
This technique is equivalent to drawing a grid accross the whole canvas, pushing every particle around so it neatly aligns with the grid,
and then saying that any two particles in the same cell on the grid have collided. It is an imperfect method, sometimes particles can touch
and it won't trigger a collision, other times particles will just get a bit close to eachother, but trigger a coliision none-the-less. What
is certain using this method, is that if two particles are inside exactly the same space, they will trigger a collision.
Despite its flaws, it is very quick! It takes O(n) to separate the particles into the cells of the grids (called bins in the code),
and then all further checks take O(1). For that reason we will make use of it, since to be honest we don't really care about the quality
of our collisions too much, and I was considering modeling them with a poisson distribution off the surface area of the structure.
final float SCALE = 2.0;
final int NUMBER_PARTICLES = 2000;
ArrayList particles = new ArrayList();
ArrayList stuckParticles = new ArrayList(); // just used for efficient rendering
ParticleBin bins;
int numParticlesToAdd = 0;
void setup() {
size(400, 400);
startSimulation();
}
void draw() {
// We will draw a dark black endless void background. This is like a regular background
// but dark and evil. This is only a glimpse at the real evil darkness I can imagine.
// Probably most people would go insane.
//background(0);
// Draw the pretty dots, but only if they're not moving
//for (Particle p : stuckParticles) p.draw();
// Use integer casting to fake the hitboxes on the pretty dots
bins = new ParticleBin(stuckParticles);
// Move those pretty dots
for (Particle p : particles) p.updateMovement(1.0, bins);
// Add more particles to make up for the ones that got stuck
for (int i = 0; i < numParticlesToAdd; i++)
particles.add(new Particle());
numParticlesToAdd = 0;
// If the simulation gets too full reset it
if (stuckParticles.size() > (width*height)/3) {
startSimulation();
}
}
void startSimulation() {
particles = new ArrayList();
stuckParticles = new ArrayList();
System.gc();
for (int i = 0; i < NUMBER_PARTICLES; i++) particles.add(new Particle());
particles.get(0).becomeImmobile();
particles.get(0).pos = new PVector(width/2, height - 20);
bins = new ParticleBin(stuckParticles);
background(0);
frameRate(60);
}
class Particle {
PVector pos;
PVector vel;
boolean immobile = false;
Particle linkedTo = null;
public Particle() {
this.pos = new PVector(random(0, width), random(0, height));
this.vel = new PVector(random(-1, 1), random(-1, 1));
}
public void updateMovement(float dt, ParticleBin bins) {
// Immobile particles need not bother moving.
if (immobile) return;
// Compute the next position
PVector newPos = PVector.add(this.pos, PVector.mult(this.vel, dt));
// If they go out of bounds in any way
if (newPos.x > width || newPos.y > height || newPos.x < 0 || newPos.y < 0) {
// Fix it by looping around
if (newPos.x > width) newPos.x -= width;
if (newPos.y > height) newPos.y -= height;
if (newPos.x < 0) newPos.x += width;
if (newPos.y < 0) newPos.y += height;
// Then skip their turn
newPos = new PVector(random(0, width), random(0, height));
pos = newPos;
return;
}
// Look for other particles at the bin we're about to move into
ArrayList myNeighbors = bins.getParticlesAt(newPos.x, newPos.y);
// If no one is there then we can go there, otherwise we'll have to look at the particle
// where we're going and see if any are sticky. If one of them is, then we'll become
// sticky too...
for (Particle p : myNeighbors) {
if (p.immobile) {
linkedTo = p;
becomeImmobile();
this.draw();
return;
}
}
// otherwise we'll carry along our merry way.
this.pos = newPos;
}
public void becomeImmobile() {
stuckParticles.add(this);
numParticlesToAdd++;
this.immobile = true;
}
public void draw() {
fill(0, 255, 0);
stroke(0, 255, 0);
strokeWeight(SCALE/2);
line(pos.x, pos.y, linkedTo.pos.x, linkedTo.pos.y);
//circle(pos.x, pos.y, SCALE);
noFill();
}
}
class ParticleBin {
ArrayList[][] bins;
public ParticleBin(Iterable particles) {
this.bins = buildParticleBin(particles);
}
public ParticleBin(Particle[] particles) {
this.bins = buildParticleBin(particles);
}
private ArrayList[][] buildParticleBin(Particle[] particles) {
// Go through and create a map of all the particles in positional space
// A 2D matrix of [particle] where the dimensions in 2D are the integer
// positional coordinates of the particles. So arr[x][y] would return all
// the particles at pos (x, y).
int bx = floor(width/SCALE);
int by = floor(height/SCALE);
ArrayList[][] mappy = new ArrayList[bx][by];
// Initialize all the array lists (not needed, very inefficient, remove later)
for (int i =0; i < bx; i++) {
for (int j = 0; j < by; j++) {
mappy[i][j] = new ArrayList();
}
}
// Then go bin all the particles
for (Particle p : particles) {
// If he's out of bounds fuck him
int tx = floor(p.pos.x / SCALE);
int ty = floor(p.pos.y / SCALE);
if (tx < 0 || ty < 0 || tx >= mappy.length || ty >= mappy[0].length) continue;
// Otherwise add him to our weird map thing
mappy[tx][ty].add(p);
}
return mappy;
}
private ArrayList[][] buildParticleBin(Iterable particles) {
// Go through and create a map of all the particles in positional space
// A 2D matrix of [particle] where the dimensions in 2D are the integer
// positional coordinates of the particles. So arr[x][y] would return all
// the particles at pos (x, y).
int bx = floor(width/SCALE);
int by = floor(height/SCALE);
ArrayList[][] mappy = new ArrayList[bx][by];
// Initialize all the array lists (not needed, very inefficient, remove later)
for (int i =0; i < bx; i++) {
for (int j = 0; j < by; j++) {
mappy[i][j] = new ArrayList();
}
}
// Then go bin all the particles
for (Particle p : particles) {
// If he's out of bounds fuck him
int tx = floor(p.pos.x / SCALE);
int ty = floor(p.pos.y / SCALE);
if (tx < 0 || ty < 0 || tx >= mappy.length || ty >= mappy[0].length) continue;
// Otherwise add him to our weird map thing
mappy[tx][ty].add(p);
}
return mappy;
}
public ArrayList getParticlesAt(float x, float y) {
int bx = floor(x / SCALE);
int by = floor(y / SCALE);
// If we're out of bounds return no particles
if (bx >= this.bins.length || by >= this.bins[0].length || bx < 0 || by < 0)
return new ArrayList();
// Otherwise return the guys in the same bin
if (this.bins[bx][by] == null) return new ArrayList();
else return this.bins[bx][by];
}
}
After running it I realized I had done the inevitable, I had added in an extra mechanism. Because I replace
particles that go out of bounds randomly, they often respawn in the middle of the dendrite- sticking immediately.
This causes the inside to get "clumped up" and messes with the branch like structure. This is easily fixed by
spawning the particles outside the bounds, and giving them a random velocity facing towards the center.
Making It Look Like Seaweed
If you put the first seed at the bottom of the screen, and make the particles rain down on it, it grows up in an algae like way- which looks neet!
Of course at this point we have completley left the "scientific playground" version of computer science, and entered the
"hey look I made something nifty" version. I don't mean that as a bad thing, I think there's a lot of value to just playing around
trying to make something cool. But once we stop worrying about recreating a specific mechanisms, we can't be sure where any of the
results come from.
