Design Q&A



Nervous System



Putting it All Together




















Intro This section aims to break the project down into its nitty gritty. It is written in documentary style, occaisionally going in and out of technical aspects. I've tried to write it as accessible and readable as possible, avoiding extremely detailed technical jargon when possible.

The work here is known as "computer based model building", and the analogy here is multicellular biology. It's just like making a map on the ground, letting twigs and rocks represent landmarks, paths, and places of interests. Here I'm allowing equally crude forms and behaviors represent highly complex things, such as the laws of physics, chemistry, and systems of biology.


Concept Background on "Cellular Morphogenesis"
The idea came to me reading while The Emergence of Everything by Harold J. Morowitz on a chapter about the emergence of multicellularity and its implications. The interest for me here is the emergence of this phenomenon, that individual and autonomous cells could group together to cooperate and even specialize, eventually forming functional living animals. Specifically, the move up from a lower level of complexity (cell structure, organelles, cell walls, etc) to a higher level of complexity (cells specializing into skin cells, nerve cells, bone, tissue, etc). I want to be able to not only express this idea in a programmed and algorithmic environment on the computer, but also have people understand and learn about this concept, and at the same create visually appealing work with both stills and animation. In other words, there needs to be pretty pictures by the end of all this. :þ

A Quote from The Emergence of Everything on Multicellularity "Among single celled organisms, it often happens that cells divide and do not split apart, but show a stickiness that leads to colonies. When this is followed by variable differentiation of the cells of a cluster into different forms, we refer to the phenomenon as morphogenesis"

Multicellular life forms come three particular kingdoms: animals, plants, and fungus. This project focuses on the animal kingdom because of my interest in animation, movement, and locomotion. However this does that mean that the other kingdoms less interesting in their own right.

Inspiration also came from Karl Sims' Evolved Virtual Creatures. This work heavily references his SIGGRAPH 1994 paper documenting his exploration of techniques to successfully evolve virtual creatures. No doubt there are many other research projects since Karl Sims, however I chose to reference him the most for familiarity.

Another inspiration is SodaPlay and SodaRace, and its implications of designed virtual creatures.


evolving virtual creatures

Emergence highlights from Wikipedia
Emergence is the process of deriving
some new and coherent structures, patterns and properties in a complex system. Emergent phenomena occur due to the pattern of interactions between the elements of a system over time. Emergent phenomena are often unexpected, nontrivial results of relatively simple interactions of relatively simple components. What distinguishes a complex system from a merely complicated one is that in a complex system, some behaviours and patterns emerge as a result of the patterns of relationship between the elements.

An emergent behaviour or emergent property is shown when a number of simple entities (agents) operate in an environment, forming more complex behaviours as a collective.

The complex behaviour or properties are not a property of any single such entity, nor can they easily be predicted or deduced from behaviour in the lower-level entities.

Emergent structures are patterns not created by a single event or rule. There is nothing that commands the system to form a pattern, but instead the interactions of each part to its immediate surroundings causes a complex process which leads to order. One might conclude that emergent structures are more than the sum of their parts because the emergent order will not arise if the various parts are simply coexisting; the interaction of these parts is central.

Emergent processes or behaviours can be seen in many places, from any multicellular biological organism to traffic patterns or organizational phenomena to computer simulations and cellular automata.

Summary from this Wikipedia article
Important things pertaining to this project about emergence: agents operating in an environment and forming complex behavior or structures, of which could accomplish what the agents themselves could not have before. It is important to show how this system could create new and unexpected results, not predicted by the lower-order forms (the agents themselves). Another important thing is to have these agents "form order despite the lack of command". back to top


Design Q&A These questions were posed during the research phase and were answered as the design phase was executed.

1. What determines success of a creature? Meaning, what quality are the creatures being selected for? Survival? Competition for speed? Competition to accomplish a task? (this assumes creatures automatically evolve motility).

Any competition involving animation is interesting. Swimming will be first priority.

2. What are the ways in which breeding and offspring of successful designs processed? Random mutations? Mix gene pools?

Mixing gene pools of successors seems to be ideal, though initially there will be only evolution through random mutation.

3. What do individual cells do, on their own? What's the level of interactivity between cells, and should this be represented? If so, how?

Little. The cells interact with each other through connections, but as an individual they will only react to physics (forces, friction, kinetic energy, etc).

4. What will the environment be? Will there be immediate competition against other creatures in a live environment? Will there be physical terrain to traverse? How important is this to the study of emergence and evolution?

No initial environment, especially selecting for creatures with the fastest motion through a fluid.

back to top


Form My "agents" in this case are individual cells. The emergent properties will come from the interactions between these cells. The first interaction is form, or how the cells arrange themselves in two dimensional space in relation to each other. In addition, all cells are acted upon by my particular flavor of the laws of physics.

Springs In order to achieve fluid, organic-like animation, I had to learn all about springs. A spring connects two masses together. A rest-state length is defined. When the two masses are pulled from each other, the spring forces the two masses closer toegether. When the two masses are pushed too close, the spring pulls them apart. In essence, a spring is always trying to maintain that length of its rest-state. Springs are used in SodaPlay's creatures. See Applet.

I performed several tests with springs until I achieved the results that I wanted.
On a technical note, I've used a hacky version of fourth order Runge-Kutta. I'm not even sure if I've implemented it properly, but it does seem to help creatures from exploding in most cases.

Masses Each cell is considered one point mass. Each cell has inertia, so that when thrown, a cell will keep going until something has stopped it (hitting a wall, or hitting another cell, or pulled back by a spring). The primary force that slows down a cell is the friction of the fluid that it's floating in. In this work, my virtual cells are sitting in an imaginary pitri dish. The fluid is invisible, but the effects of the fluid are visible through these cells. back to top See Applet.


Structure The next step is to provide some kind of "blueprint" that allows these cells to be placed and connected by springs in a predictable and consistent manner.

Genome This blueprint is simply a set of numbers, interpreted as instructions on how to build a cell. The philosophy behind this project is to see how emergent behavior and form could arise from morphology alone, therefore I minimized the amount of information is given by the genome. Let me stress that the genome does not hold information for "each and every cell".

The genome contains a list of "genes". Each gene holds information like angles, distances, the type of cell (more on this later), how many times to replicate, and its following child gene. The embryo cell (or "root" cell) is placed at a predefined location. All consecutive cells are grown from this initial cell. The embryo cell always uses the first gene in the strand. See Applet.

example of a genotype graph

Phenome The blueprint is then read through as data instructions, specifications on how to build a creature. All construction starts from the embryo cell and uses information contained in the genome. So for example, the embryo cell contains the first gene in the strain, and is told to make a new cell at 30° absolute angle, 25 pixels away from itself. It is also told how many times to do this, and in our example the cell is told to divide three times. Now we have a form that looks like a column of cells lined up at 30 degrees. The cell is also told what the consecutive "child" cell each of these new cells will make. So if the embryo's child is told to use gene 13 (which contains information like angle, distance, which child gene, etc etc), the new cells that it makes will divide again with those specifications. This process continues until all cells divide to a cell that contains a gene telling it to stop. These termination genes are important because it prevents infinite loops of cell growth.

To cut corners and save time, I assumed that creatures are to be built bisymmetrically down a center axis as are most animals. Thus, the genome defines exactly one half of a creature and every cell division is mirrored across its center axis.

The springs that connect these cells together are not defined directly in the genome. Rather, a routine runs through all cells checking their distances. If a cell is within a certain distance threshold (say, 20 pixels), connect the two cells with a spring. This distance is called "cohesion distance", and it plays an important part in creature evolution. One tiny angle shift would greatly change the behavior and mechanics of a creature.

This is why there isn't a one-to-one relationship between genes and cells, and that in general a string of 10 genes can produce a complex pattern of over 300 cells. This is the relationship between genotypes and phenotypes. The advantage is to have relatively little information produce large quantities of patterns and to have evolution recycle these useful patterns. See Applet.

Finally, the genome also instructs what that particular type of cell is to be grown. The following three sections describe the nerve cell, the muscle cell, and the sensor cell in detail. back to top


Nervous System While this work goes in depth with simulating neural networks, the depth did not serve to be an advantage to the final result. Nonetheless, I referenced John Holland's description of artificial neural networks for this project (John Holland, Emergence from Chaos to Order, chapter 5 on Neural Nets). As a side note, even though this simulation of neurons is very detailed, it is but an extremely crude simplification of true neural networks running within your skull. I'm also ignoring Hebb's Rule, which I now think is a grave mistake. See Applet.

Neuron Each cell in this work is a simulated neuron, and the creature as a whole can be thought of as a neural network in itself. Every neuron cell contains a charge that is accumulated. This accumulation is the sum of charges from other neurons firing to it (except sensor cells). When the accumulated charge surpasses a certain threshold, the neuron itself will fire to all cells it's connected to.

Variable Threshold The threshold at which a neuron fires is variable. When a neuron hasn't fired for a very long time, the neuron is more sensitive to firing (the threshold is low). When a neuron has just fired, the threshold is high. It will take a much higher accumulation of charge in order to make the neuron fire again.

Synapse Neural cells are connected to one another through a synapse connection. In proper biological terms, these are your dendrites and axons. The genome does not give information on which cell is connected to which cell, and therefore springs are used as bridges of synaptic action.

Fatigue After a neuron has fired, there is a certain amount of time where it simply cannot fire anymore. A neuron recovers over a certain number of time-steps and then is ready to fire again once the fatigue is gone. This allows special behaviors like lock-step firing when neural loops are involved.

Weights In addition to a signal strength, a signal also contains a special "signal weight". This value is specified by the genome, so that each cell has a predetermined weight that it will fire. The value can be positive or negative, depending on specifications of the genome. When a neuron cell is ready to fire, it will sum up all the weights recieved from other neuron cells that fired to it. If the combined weight is "not zero", the cell will fire. If the combined weight is zero (the event that a cell fired to it with -1, and another cell fired to it with +1), the cell will refuse to fire. This property allows for highly complex neural networks to emerge, explained below.

XOR A network with two inputs, one with a positive weight and the other negative, both fire to a recieving neuron cell. This network is able to accomplish a simple computational task called XOR. The recieving cell will only fire if one of the inputs are triggered, but not both at the same time. See Applet.

Indefinite Memory A XOR network with a loop from the recieving cell firing to one of the inputs causes the network to have what John Holland calls "indefinite memory". That is, the network "remembers" that its free input has been triggered. It can also actively delete that memory by triggering the same input at the same time, canceling out signal travelling in the loop. See Applet.

example of an XOR network

The goal for simulating these processes is to have intelligent "feed-forward" neural networks emerge. A feed-forward is best understood when compared to a feed-back network. A feed-back network is a network that makes a direction connection between the inputs (sensors) and the effectors (muscles). Think of a venus fly-trap: once its sensors are triggered, it automatically causes a chemical reaction to make its jaws close. On the other hand, a feed-forward network hooks up the inputs to a hidden layer, and the hidden layer is then connected to the effectors. The hidden layer is a neural network that will not only behave reactively, but proactively. A hunter in the ocean will actively seek out prey, as opposed to acting only when prey comes its way.

back to top


Muscles The nervous system of a creature will pass information onto muscle cells. These specialized cells are also nerve cells that can recieve charge and have variable threshold and fatigue like described in the previous section. I experimented with turning on and off the muscle cell's capability of transmiting its own charge with varying results.

In reality, muscles are fibers made from hundreds of thousands of cells. Sir Charles Dawrin called it one of nature's most amazing inventions, noting how a soft piece of jelly could turn stiff and tough in a fraction of a second on command (electric pulse). Since I am simulating on the level of individual cells, I had to take the shortcut of modeling "muscle" cells. When it recieves a charge and fires, the muscle cell will temporarily decrease the spring length to all of its neighbors. The produced effect is a contraction. Unlike SodaPlay, these muscles do not act constantly on a Sine wave. They act only when their own internal neuron fires. Also, Soda's muscles are allowed to extend, whereas muscles in this work are only allowed to contract, reflecting real muscles a little closer (though you can argue that relaxing a muscle is the act of extension... but let's not go there...).

After a muscle has reached maximum contraction, the muscle will begin to relax. It cannot contract again until after it has been relaxed. The idea of controllable relax rates had been toyed around with during my evolution tests, but the evolved creatures were never smart enough to take advantage of such a mechanism.

Creatures that have efficient muscle systems can propell themselves through fluid. This is caused by springs losing energy to fluid friction. The physics here is more messy than I'm willing to expulge, and the implementation is equally as messy. back to top See Applet.


Sensors Some cells are tagged as sensor cells. In biology, specialized cells can pick up a variety of information about their environment, such as pressure, magnetic and electrical forces, sounds, chemicals, light from the visible spectrum, etc. In modeling these creatures, I wanted to evolve creatures that could not only swim quickly, but adapt to a changing environment such as a moving light-source. Pressure sensors were planned but due to time constraints were cut out of implementation.

Light Sensors All cells tagged as sensors are light sensors. These cells recieve charge if it is exposed to a light source. A ray-trace is performed and if the cell's line-of-sight is blocked by other cells, it will not recieve charge. Light sensors have a limited capability of telling distance to light. Future designs of this implementation should allow global comparisons of all light sensors, therefore giving the creature a sense of direction to light. This is not the case right now. A sensor is either exposed to light, or hidden.

This is done to encourage eyes to grow on the outside of the body, as opposed to the inside... However light sensors can "see" through other light sensors (other light sensor cells do not block line of sight), giving the possibility of compound eyes to emerge. back to top


Putting it All Together A complete creature is now constructed of springs, nerves, muscles, and sensors. The morphology is built from instructions contained in the genotype. The cells are color coded in the following format:

Stucture Cells that have no specialization. These cells are referred to structure because they only serve to anchor other cells together with springs. These cells are colored in gray.

Nerves The neuron cells that are allowed to pass information to other cells are colored in blue.

Muscle Cells that can pull other cells behaving like muscles are colored in red.

Sensors The light sensors of a creature. They are colore green.

Example of creature anatomy.

Several render views were written as well. Two important ones are noted here: The first viewing mode renders all the springs as they are located in space. The second mode shows the creature anatomy and all synaptic connections as well as cell types, neural activity, and so on. See Applet.


Evolution The process for evolution to occur are as follows:

Completely random genotypes are generated. They are built into phenotypes and dropped in a population. This population is usually around 150-200 randomized creatures.

The program then goes through and tests each creature for performance. Before that occurs, some simple logistical tests are done to prevent wasting simulation time. Creatures who explode due to physics bugs (spring integration errors) are immediately removed. Creatures who don't have all requisite parts (say, missing sensors or muscles completely) are also removed. Creatures who fail to respond in the first 50 frames are removed.

Once a creature is found to be capable of motion, that creature is placed in the Best Creature slot and given a fitness value. The fitness value is determined by what type of test is being done (more on this next).

After the program has exhausted testing the population, the best creature is picked for duplication. Its offspring will take up about 30% of the population and the rest will again be seeded by randomized creatures. The offspring of the last successful creature are all mutated slighly in some particular way (change in cell spacing, angle, cell type, children, neuron weight, etc). The program once again tests this population, finding a creature that has a higher fitness to replace the last creature.

As an aside, evoltuion could have benefitted from cross-breeding the genotypes to make mutant creatures however this feature had been cut out due to time restrictions.

This is a crude way of evolving virtual creatures but it was all I had time left for. Two types of tests were made to test creatures for fitness. They are:

Fast Swimmers Creatures from this test are selected for absolute speed only. A light is placed north of the creature, however the creature is allowed to swim in any direction so long as it goes fast. Speed is measured in pixels per frame (px/frm). See Applet.

Creatures that emerged come in a variety of shapes and sizes. Extremely fast creatures were capable swimming at about 5 pixels per frame. Some creatures use the entire forward contraction of their bodies to move forward like a slug. Others wag appendages to move themselves. There are also creatures that would curl themselves into an arc and use their entire bodies to move. A few creatures travel by mysteriously vibrating extremely short muscles back and forth and generate motion.

Follow the Light In this test creatures are given fitnes values based on how well they follow a light source. Three tests are performed. The first test is with the light directly north of the creature. Creatures going the wrong way are eliminated and thus only creatures with sensors facing the light survive (in nature, escaping a predator by going toward their jaws is a very bad idea). The second test is with the light starting directly north, but slowly moving towards the left. In the third test, the light moves to the right.

Creatures are scored on how close they get to the light. Creatures that can only go in a certain direction (say, they only go straight every single time and ignore the shift in light direction) are given a penalty. Creatures that can react to the changing light direction are thus selected for. See Applet.

The resulting creatures that emerged from these tests are surprisingly simple in construction. For the most part these creatures use the same strategy, that is, to place their sensors in a concavity or a convex surface. When the light source has moved, only one side of its body would respond, thus achieving a crude "light-following" behavior. None of the creatures exhibited any usage of complex neural networks...


Conclusion? In conclusion, evolving virtual creatures is much harder than it looks. "Design by brute-force" is what it really comes down to, and though it's a fantastic approach, it must be optimized in many ways in order for hundreds of thousands of generations to be done feasibly. The dream is to show the process to someone in real-time, and by recording time-lapse videos of this project I was able to achieve some of that.

There are many things that didn't work out, such as the physics engine, the neural network, evolving by mutation alone, and others. Future versions of this project should keep things simpler, and allow complexity to arise as opposed to the other way around. There are things that I did not foresee, such as physics problems (fluid dynamics, Runge-Kutta, etc). Other places that could be greatly improved is the technique in which evolution is selected. The code is both messy and obsfucated because of my lack of experience in writing such things. The neural network was also something I didn't imagine would be a problem. Future versions would allow neural networks to evolve seperately, thus evolving creatures that know how to use their bodies properly. The muscle system could use a lot of work, as well the sensors which could benefit from having various other types of sensors (internal pressure sensors). Finally, new tests should be performed for other creature designs, such as with gravity turned on (SodaRace style), and competition between multiple creatures.

All in all it was a worthwhile learning experience. From this research I had to delve into many different disciplines of science, such as biology, physics, chemistry, neural science, and computer science. Any future attempts at this project would demand that I learn a lot more math.


Bibliography Here are works both cited and referenced, listed in no particular order.

Emergence from Chaos to Order by John H. Holland, 1998.

Evolutionary Wars A Three Billion-Year Arms Race by Charles Kingsley Levy, 1999

Evolving Virtual Creatures by Karl Sims, 1994

The Emergence of Everything by Harold J. Morowitz

SodaPlay by Soda Creative Ltd.

Blur code by SEB & Modified/Rewritten by Toxi

Special thanks to Casey Reas, Ben Fry, Chaim Gingold, Quasimondo, Skloopy, V3ga, marcello, and Fish-face.


The work on this website is copyright © Michael Chang 2005