Swarms Rule

I've been thinking a bit about what rules make a swarm look like a swarm. The three rules that boids follow, cohesion, alignment, and separation, make a nice flock, but a swarm isn't really the same as a flock. A swarm's parts moves around even when it is still, if may change shape at any time, and it more dynamic and less structured then a flock. So what rules do we need to produce swarm behavior?

First off, there appear to be more then one type of swarm, or at least more then one thing a swarm may be doing. A bait ball is a circle of beings all circling in the same direction and staying close together but not converging to a point. A large, mostly stable swarm may appear to grow limbs or briefly split. A moving swarm may be more like a flock then a standing one. Perhaps there are other forms we may wish to create that are swarmlike?

So, the rules. A standing swarm that does not change shape seems to need only two rules- move randomly and stay inside a sphere. Luckily these are both O(n) time operations for a swarm of size n, so we can get away with an efficient little swarm if we allow individuals to move through each other. To get the shape changing effect I would guess we could create invisible attractive or repulsive forces and move them around, orbiting the center of the swarm and possibly reversing their effect occasionally. Another possibility is temporary leaders, either with new rules or with the same rules as others, that are followed by close by individuals. Another possibility is that individuals always sort of follow each other but the strength of that influence varies.

For a bait ball I would guess we would need separation from a central point, random movement, and a strong need for alignment. I'm not sure if this is enough, but I imagine the alignment would keep them in check and the random movement (possibly also a need to move forward) would keep them circling.

Finally the flocking behavior of a moving swarm may simply be the above standing swarm rules with a force pulling the individuals to a certain location. This may be enough to create a nice looking moving swarm.

Thats all I can think of for now. Any thoughts? Other types of swarms? Other rule sets that seem plausible?

A Very Cool Method for Computing Shortest Paths

I've been reading a very cool article A Very General Method of Computing Shortest Paths, which gives a nice general way to compute several things by solving an equation in a *-semiring or Kleene Algebra. It ties together shortest paths, regular expressions from automata, solving linear equations, and several other problems into one fairly simple algorithm. Definitely worth reading.

Sensor Controller Interpreter

I've started programming a prototype for MicroSwarmigism, and while things are going slowly, I've got a general notion in place that I want to record here. The idea is that changes to the game occur in three stages, consisting of a sensing stage where data is collected, a controlling stage where changes are calculated, and an interpreting or application stage where instructions are carried out. This is more general then what I'm describing here, and in fact it seems to be a nice way to decompose things like genetic operators or generally operations on a data structure. For now I'm focusing on how I'm planning on using it in Unity.

All three of Sensors, Controllers, and Interpreters are parametrized by their input and output, so they are really just unary functions. The difference is in how they are used, and in Unity, when they are called. Sensors are intended to be used to determine information about the state of the world such as mouse input or positions. Sensors run in Update, and I plan on only running Sensors when their data is asked for, so they are lazy. Controllers are intended to produce the data that is used to make changes. I call this data instructions, but really it can be anything. The Interpreters are intended to apply the instructions to some piece of data. This is done in LateUpate, so all sensors will have pulled their data and ordering of Controllers will not effect Sensors. The ordering on Interpreters is not controlled, so their effects should be commutative if possible.

An example of this that I'm working out right now is this: a Sensor collects mouse input information, a Controller reduces this information to a delta in mouse position, and an Interpreter merges the change in position with the position of a cursor. This would be how the mouse cursor works. Adding a collision sensor and left click sensor would allow a controller to determine is something is selected, and an interpreter to change the cursor's current selection.

Another example would be a swarm with a sensor telling it the position of each of its gisms, a controller averaging that position, and an interpreter on each gism using this information to effect its next move.

Yet another example would be mating- a sensor on a gism would determine close by gisms, another would determine energy level, a controller would determine if mating should occur. The given gisms should then have a sensor providing genetic material, and an interpreter applying crossover.

The one downside to this setup that I can think of is that since Update is used so collect data and produce instructions, and LateUpdate to apply them, there is no time that is used to enforce invariants the way LateUpdate is sometimes used. For example, if the mouse cursor goes off the edge of the screen, we could use LateUpdate to place it back on the screen after all other movements have been applied. I plan on simply being aware of this and programming carefully to mitigate the problem.

A Proof of Spirits

In addition to his electronics blog, To The Rails, my friend Chris now has a booze blog Proof of Spirits. Check it out.

Also check out my brother art blog Sculptor by Day for awesome drawings and computer graphics, as well as MicroSwarmigism updates.