Conversion-diffusion algorithm
Making Realistic Giraffe Patterns With a Cellular Automaton
Backstory & abstract.
If TL;DR scroll down
I was walking through the Milwaukee zoo one day and looking at the giraffes, I wondered how their pattern is formed. Here are the giraffes.
The first thing that one would probably notice about a giraffe pattern is that it's made up of a bunch of dark kinda-hexagonal splotches, separated by thin borders. (The technical term is voronoi polygons.) How could these form? It seems like a stupid question, but start out with the fact that all of a giraffe's skin cells are the result of a single cell that divided into all of these cells, and somewhere along the process of dividing and growing, some of these cells decided to be dark and some light. And not only that, but they did so in such a way that forms the same patterns over and over; the patterns we recognize as that of a giraffe. And all of this happens without the cells having had a map of where they are on the body, or having any idea of the 'big picture' of the rest of the giraffe's skin.
So a better way to phrase the question is, "how does each individual giraffe's skin cell (even though they're all the same) know which color to be, in order to produce an overall large-scale pattern on the skin?"
Some things that we know about cells is that they can produce proteins and they can also detect proteins inside or outside the cell. A cell can also have a process which is switched on or off when a certain level of concentration is reached. In other words, they can send and receive signals to each other and act on those signals.
Interestingly, similar patterns show up on very unrelated species. For example there are moray eels with the same pattern as a giraffe. There are leopard sharks with a pattern very similar to that on corn snakes, which is also similar to that on boa constrictors. It is reasonable to suppose that all of these patterns keep appearing because the patterns on all of these species (which seems to include at least all vertebrates) are produced by homologous genes and processes. For example, humans and fish both have eyeballs, and skin, and a heart, and a liver, etc, because the development process is controlled by genes that both humans and fish have inherited from a common ancestor.
Now it would be easy to speculate that these blotches start out as a few small random cells that got switched on, which then expand out (switch on all of their neighboring cells) until they almost meet, leaving those borders. This sounds easy enough... in English. To a human... who can see the big picture. But how would a cell know when to not try and switch on its neighbors? I mean, if their method is, "if a cell 3 cells away is on, don't turn on," then there are also plenty of cells switched on that are 3 cells away within the same blotch.
The type of program used to simulate this type of situation, of skin cells sending and receiving signals and changing states, is called a cellular automaton, or CA for short. In a CA, each cell follows the same set of rules of how to behave, but since each cell can find itself in different circumstances, they can end up being in different states, and thus forming patterns. This is what you'll find directly below, and feel free to try it out at any time, play with the settings, and see what happens.
More details:
The above javascript uses a modified reaction-diffusion type of cellular automaton to generate patterns like those found on the skin of giraffes. I've called this a conversion-diffusion model instead because all of the reaction-diffusion models I've seen are the same, and I didn't want this one to be mistaken for the same thing. Here are some examples of results it produced, as well as real giraffes for comparison. Notice not just the larger concept of regions, but the more subtle imperfections as well, which are very telling, IMO.
Real giraffes, for comparison.
And as I mentioned, here's the pattern on some 'honeycomb' moray eels:
 |
What does the pigment threshold do?
Here is how the pattern changes as the pigment threshold is changed. This is simply "how sensitive is a cell's receptor to a certain molecule" which could be controlled by even a single gene. The result can either be expressed in an on/off fashion (like this pic) where there is zero pigment until the threshold is passed, and then there is full pigmentation. An alternative is a smoother fade-in/out look, which can also be seen in some examples. Another alternative would be multiple thresholds, with a different color being associated with different amounts. (These images were generated by an earlier verison of the script with a bug that produced a tendency toward diagonals, so please ignore that aspect.) |
How does this different from other computer-generated giraffe patterns?
I'm glad you asked because this is my favorite part. The results show several details which exist in real giraffe patterns, but do not appear in generated patterns:
- Edges of the borders can be smooth or jagged.
- When two blotches meet early on, they leave an 'inlet' of border between them.
- When the threshold is changed, the same underlying results can produce patterns of different subspecies, with full blotches, or 'eroded' looking blotches. This shows that what appear to be very different patterns are actually the same with only one small difference.
What's so special about this program?
There are many ways a computer can generate this general type of pattern. What's interesting about this method is that it's biologically possible. That is, the patterns on real giraffes might actually be generated in this way. In the skin cells of a developing embryo, none of them have knowledge of their position on the body, or a road map telling them "if you are located over here, be this color." The pattern has to be generated by a process where each skin cell interacts only with nearby cells and without access to any information about the 'big picture.'
The reaction-diffusion system has been used to demonstrate a possible mechanism for skin patterns on other animals, and is a great way to show how certain types of patterns could be formed by a developing embryo, and not just skin patterns but also the distribution of hairs, scales, and feathers on animals. But what it cannot do (at least as far as I have been able to determine) is produce a giraffe pattern. (Or the patterns on many other species.)
The other point of interest is that this program produces the various sub-types of patterns seen on real giraffe subspecies, all with the same mechanism, by changing one or two values such as how much of the substrate molecule is present at the beginning, or how much product must be present in order for a cell to produce pigment. The difference between Reticulated and Masai giraffes (and all the others) is not the result of any extra or missing processes. It even produces the fuzzy edging and little "failed border" inlets found on real giraffe patterns, not because of a special addition to the program but because that's a natural consequence of this algorithm. (Those inlets, as you will find, are a result of two blotches that merged early on.)
Why?
After several years of occasionally working with cellular automata and various pattern-making algorithms, I had a 'eureka' moment one day and realized this specific set of rules should make giraffe spots. Part of the nature of cellular automata is that the patterns they generate are emergent (not directly written into the rules, but rather emerge/coalesce, much like weather) so it can be extremely difficult to predict a result just by knowing all of the components of the algorithm. Imagining it isn't enough, so I had to program it and make sure it actually worked. My efforts to find such a program already on the internet were always unsuccessful, so I put this on the web in case someone else might someday find it interesting, whether they are into giraffes, or programming, or whatever else.
What is the simulation actually doing, in English?
- It's easier to see if you uncheck the giraffe colors and cell states, to get the blue/yellow view.
- Each virtual cell is represented by one pixel of the image.
- There are two molecules. The amount of A is shown in yellow, and the amount of B is shown in blue. Where neither is present it will be black.
- The A and B molecules each diffuse out through the tissue at their own (user defined) rates.
- A cell can either be "off" or "on." When a cell is off, it does nothing. When a cell is on, it converts molecule A into molecule B (at a rate defined by the user) and also attempts to switch all of its neighbors to "on." A cell will only turn on if there is enough (also user defined) of molecule A present. A cell will turn off after a certain (user defined) length of time, or if the concentration of A falls (user defined) too low, or if the concentration of B goes (user defined) too high.
- At the start a (user defined) handful of cells are randomly switched "on."
Why does it work where others fail?
This method is different from other diffusion-reaction systems in a few key ways. First, the substrate (normally called U) does not replenish. The amount at the start is all that is ever used to complete the process. The spots are able to run right up to each others' edges without overlapping, because the substrate (via diffusion) gets sucked up into the expanding blotches before they arrive. In the blue/yellow display (uncheck the giraffe colors and cell states boxes) you can see this as the dark regions around the expanding blotches that look like shadows. Second, the product (normally called V) stays in the cell where it is made and does not diffuse. Although there is an option to allow it, so that you can see the consequence, it is off by default. This also allows the edges of the blotches to stay separated. Third, at the start only a few cells start out in the "on" state, which makes them capable of performing the chemical reaction. All other cells are switched "off" at the beginning. The "on" cells then slowly activate their neighbors, switching them to the "on" state after a while. This also allows the substrate to be sucked up into the blotches as they expand, again helping to create the border regions between blotches. Finally, the threshold can be used by cells to determine whether they do or do not produce pigment. Increasing the threshold will "erode" the pattern and widen the borders.
One final note on producing patterns, the borders stay rather slim if thresholds are not used. Setting a high threshold will widen the borders, but will also erode the weaker parts of the blotches. To solve this problem, after the process has covered the whole image and you've paused it, run a few cycles of "smooth" and observe the changes until the pattern looks correct for the type you are trying to produce. (This would correspond to the product molecule being released from cells and allowed to diffuse through the tissues after the process has completed.) The other way to do this is by setting the B Diffusion Rate to a very low number like 0.01, but this has a side-effect: the edges that meet early are smoother than the edges that are filled out at the very end. Either way is biologically possible. I do not have detailed enough pictures of giraffe skins to know for certain which of the two above results would be a better match to real giraffes, but it appears the latter may be more realistic.
How would this correspond to actual processes taking place in the skin of a giraffe embryo?
This simulation requires each virtual cell to be able to produce, convert, and detect the levels of a few molecules, and for these molecules to be able to diffuse throughout the surrounding tissue. Real cells are little chemical factories, they can make enzymes to catalyze a reaction, and detect the presence or concentration levels of specific proteins, and processes can be switched on/off depending on conditions. And of course real molecules that leave the real cells can diffuse throughout the real tissues. Putting all of this together, a cell can 'communicate' and 'interact' with other nearby cells via these processes, thus making this simulation a real possibility.
About the author
I enjoy creating and toying with cellular automata as a hobby. One of the challenges I've taken on is trying to produce realistic animal patterns with them, because obviously the skin is an actual CA and these have to be produced by a similar process. I'm working on a more universal model, in an attempt to find a (ha ha) Grand Unified Theory of vertebrate skin patterns, so keep an eye out for that, too.
If you've found this model or this page useful or interesting (especially if it is in any way involved in any real research, biology or computers or math) I'd love to hear about it, so feel free to drop me a note at serpwidgets@hotmail.com with any comments, ideas, etc.
Other interesting observations about animal patterns
 |
Note that the pattern changes as it reaches the extremes of the animal. This shows the various amounts of progress of the pattern as it forms, so that you can see the intermediate parts of the process. Notice that also the 'most complete' parts of the pattern tend to be at about the shoulders and radiates out from there (or on some species, along the length of the spine more so than just the shoulders) so that the more 'distant' a point is on the (embryo-shaped) body the less developed the pattern is at that point, with the most distant points being the belly, fingers/toes, tail, and nose. The same can be observed on the rosette patterns of big cats, where the legs only have black spots and the rosettes become more 'complete' as you approach the 'origin' by the spine, such as the picture on the left.
This suggests that the process does not take place simultaneously, but instead begins first at or near the 'neural crest' area (the base of the neck) and then radiates outward from there. One can see this phenomenon in corn snakes known as 'bloodred' where the pattern fades out as one goes from dorsal toward ventral.
Also notice the fact that the left and right halves of the pattern will 'separate' on the tail end of many animals, such as the stripes on zebras. In this example you can see they are connected from right to left in the front half, and then they lose continuity as they approach the rear. This is presumably because the pattern is forming while the left and right halves of the skin are closed over the cranial end of the spine, but are still open on the caudal end of the spine.
This phenomenon also shows up in striped corn snakes, where the longitudinal stripes tend to break into shorter dashes toward the tail.
Also, back to the giraffes, notice the white space between polygons is larger on the neck, which shows that the pattern formed on the skin before it grew from a 'regular embryo' shape into a 'giraffe' (longer neck) shape. |
 |
Another type of model for pattern formation (such as the Clonal Mosaic) will use groups of cells which migrate over the skin and then grow, pushing other cells out of the way while doing so. I think this model fails to explain the following phenomenon. Here we see a typical zebra.
 |
Take a look at the yellow stripe(s) and the blue stripes which are highlighted on the left picture. These stripes are another anomaly which can provide clues to the process that produced them, and help us identify whether a model is accurate, because a reaslistic model should not only produce the 'pretty' aspects of a pattern, but also make the same 'mistakes' that the real process makes.
What happens here is that where the blue stripes die out, the yellow stripe expands to takes its place, and additionally, it even splits into two stripes. There's no reason for this to happen with three separate groups of cells that are each just expanding. However, this is precisely the type of thing that happens if you have a cellular automaton that starts at the spine and sweeps toward the belly, where the 'on' cells produce a signal that causes cells to turn off once a certain threshold is reached. (This anomaly occurs with a reaction-diffusion model, or a 'radius-threshold' model as well.) |
 |
The trick with the zebra pattern (and others such as the tiger) is the pointy tips on the stripes. A typical cellular automaton like reaction-diffusion produces smooth rounded edges on everything and is typically incapable of making pointy things. Some models offer a 'cheat' by making the cells biased along a certain axis, turning spots into elliptical spots that look stripe-like. But this still fails to produce splitting and merging of stripes, or pointy tips. This is where adding a 'sweep' element to the model can make a difference. Instead of having a simultaneous two-dimensional automaton with all cells being equal, the activity takes place in a line (or regtangle) parallel to the spine. The area of activity then sweeps toward the belly. As it finally tapers off, the activity would then be able to taper to sharp points.
This type of activity is also consistent with the slow fading out of patterns on the legs/belly of many animals. You can see this on the leg of the giraffe below. The picture is turned sideways to fit this page better, but you can see the torso on the left and the leg on the right. Notice the pattern does not just continue in a complete fashion and then stop. It fades in intensity and completeness.
