Growing lichen

It was supposed to be a quick effect, and a trip to the past. It was one of the first things I ever coded in C, years ago. I found a description of it (was it a course?) in some old gaming magazine and decided to give it a try.

And now I've found the chapter about it in an old book I ordered for a couple of bucks from an American second-hand bookshop. The book is "The Magic Machine - A Handbook of Computer Sorcery" by A. K. Dewdney (see Fig. 1).

Fig. 1. "The Magic Machine" - can you feel the 90s?

Slo-Gro (slow growth) is a model of a particulate growth process, which happens for example during the aggregation of zinc particles in a two-dimensional film. The ions wander around until they meet the previously settled particles and thus form tree-like structures. DLA stands for diffusion-limited aggregation. The particles settle to form complex, fractal tree-like structures, which remind me of moss, or the Tree of Life - with branches that thrive and branches that wither out (see Fig. 2).

The analogy (well, one of the analogies) for the DLA process presented in the book is simply too precious to pass [1]:

The most colorful (albeit the least realistic) model for a DLA process involves a succesion of drunks wandering about in the dark until they stumble on a crowd of insensate comrades; lulled by the sounds of peaceful snoring, they instantly lie down to sleep. An aerial view of the slumbering crowd by morning light might well reveal the same fractal shape found in a zinc cluster or a soot patch.

On more serious note, the process can be described as follows. The particles (pixels, ions, ...) are initially placed randomly on the circumference of the circle. Each of the particles then wanders randomly (up, left, right, down) until it finds itself in the neighbourhood of some other particle, which is now stationary. The wandering particle then settles down and a now one is launched. The wandering process is stopped when the particles wanders out too far (outside the circle), or if it made too many steps (10 000) without any contact. New particle is generated to replace the strayed one. The process is repeated in a loop. At some point the arena will fill completely, and no new particles will find any more place to join.

In order to make the process quicker, you can influence the Brownian motion of the particles a little. I added a small displacement for the particles at each step, that slowly drags them towards the center, regardless of their random motion. This is controlled by the attraction parameter.

I made a small interactive simulator of the SLO-GRO effect: SLO-GRO Simulator

The code is available here: https://github.com/dagothar/slo-gro (beware: at some points it's one hack upon another!).

In the simulator you can launch your own slow growth process. You can draw on the board to create your own seeds, even during the simulation. You can tweak and mix the colors on the go. The process produces quite interesting graphical results (see figs. 3-9). Make sure to try different values of parameters, as well as different colors.

Fig. 3. The field overgrown.

Fig. 4. Dappled grass.

Fig. 5. Waves of grass.

Fig. 6. Creative palette.

Fig. 7. Delta step overgrown!

Fig. 8. Moon grass.

Fig. 9. Acid eye.

The moss grows quite quickly in the beginning, but it loses its pace abruptly: at some point the growing tree seems almost static. Even though the particles now have smaller distance to travel, more of them is necessary to fill the rings of increasing area (which grows as the square of the distance!). It will take several minutes to fill our Petri dish.

It is interesting to see what is the dimension of the structure generated by the slow growth process. For such a fractal, we can expect its fractal dimension to be somewhere between 1 and 2. Isn't it exciting that there are figures that dwell somewhere between being linear and planar? If you want to learn more about fractals and fractals dimension, I recommend watching an excellent video by 2Blue1Brown.

The fractal dimensions is basically the exponent by which the area of the object increases in response to scaling. For example, the "area" (length) of the line is linearly dependent on its scaling and thus the line is 1-dimensional. The area of a planar figure (e.g. a triangle) raises with the second power of the scaling, and thus the triangle is 2-dimensional. Similarly, a cube is 3-dimensional. The notion of dimension gets complicated with fractals. They tend to have fractional dimensions.

There's an easy way of calculating the fractal dimension of our structure. Simply measure the area (the number of settled points) for several different values of the radius. I did it by letting the moss grow, pausing at certain intervals, and measuring what the radius of the circle containing the sediment is. The data is presented in the plot below (fig. 10).

Fig. 10. Area of the structure vs. the total area.

The fractal dimension is calculated as the slope of the line of the structure area vs the scale plot.  My result is ~1.9. The fractal dimensions cited for Slo-Gro in [1] is 1.58. The discrepancy here is probably due to the attraction parameter; without it the tendrils of the tree tend to be considerably less dense (but then it takes massive amounts of time to generate the data! - see fig. 12). Feel free to experiment.

Fig. 11. Structure area (blue) and the total area (red) in log-log scale. The blue line has slightly smaller slope.

Fig. 12. Sparser structure with the attraction parameter set to 0.1 instead of 0.5.

Literature

[1] A. K. Dewdney, "The Magic Machine. A Handbook of Computer Sorcery", W. H. Freeman and Company, New York, 1990, ISBN: 0-7167-2149-2.

Langton's Ant

Langton's ant is a small bug that crawls tirelessly on a floor tiled with rectangular plates, which are black on one side and white on the other. Whenever the ant first steps on the plate, it checks its color and changes direction:

• if the plate is black - it turns to the right,
• if the plate is white - it turns to the left.

It then proceeds - a nasty little vandal - to turn over the plate it is now standing on: white to black or black to white. And then it moves forward (in the new direction) again.

Could the rules be any simpler? Of course, with such simple rules we do not expect the ant to exhibit any interesting behaviour. It will probably just run around in a circle, and maybe flip some tiles randomly. Nothing interesting can come out of such a system. Or can it?

Let's see what happens anyway. At first, it seems our predictions were correct. The ant produces simple and symmetric patterns (see Fig. 1).

Fig. 1. At first nothing interesting happens.

After a couple hundred of iterations, the patterns seem still quite symmetric and predictable (see Fig. 2).

Fig. 2. Making nice patterns.

After 2000 iterations chaos emerges (see Fig. 3):

Fig.3. The beginning of chaos.

We now change our prediction. The ant is going to fool around and paint the whole floor with no regard to symmetry or aesthetics - it is going to be a pure chaos.

Let's watch a little more...

This is what happens after ~11,000 iterations (Fig. 4):

Fig. 4. The ant escapes, leaving a "rose" behind.

After tumultous youth, the ant has abandoned its chaotic ways and started behaving orderly. The structure left behind reminds me vaguely of a rose. The ant now constructs a "highway", taking 104 steps to make yet another turn in the coil of the stalk.

How did this happen? Why did such simple rules result in so many different kinds of behaviours? From order, to chaos, to order again. How did the number 104 come up from the rules we have defined in the beginning?

There was certainly no way to predict the final result from those.

You can play with the Langton's ant using the simulator I made: https://rawgit.com/dagothar/langton-ant-js/master/index.html

As usual, the source files are provided: https://github.com/dagothar/langton-ant-js

 

Simply click Start. You can also try to make the ant go step-by-step with the aptly named Step button.

You can also draw on the board with the mouse! What do you think will happen when the ant encounters your drawings? Can you trap it? Will the ant draw a different shape?

 You can read more about the Langton's ant here: https://en.wikipedia.org/wiki/Langton's_ant

World of wires

Or Wirewold for short.

In good old days I spent an inordinate amount of time doing weird things, such as drawing and simulating spaceships and battles using humble MS Paint (that itself is worth making a post on its own - if for nothing else but to explain myself). What would I give to see my painstakingly hand-crafted animations to come to life all on their own! I wish I knew of Wireworld back then.

Wireworld is a cellular automaton designed by Brian Silverman in 1987 (yay, I was born the same year) to simulate the behaviour of digital circuits. Its Wiki page explains the rules briefly, but to the point: https://en.wikipedia.org/wiki/Wireworld.

Basically, you have a grid of 'pixels', each of which can be in four different states: empty, wire, head of the electron or tail of the electron.
Each turn the pixels change their state according to the following rules:
1. empty remains empty,
2. tail of the electron becomes the wire,
3. head becomes tail,
4. wire becomes a head if, and only if 1 or two adjacent cells (4-connectivity!) are heads.

These rules make it possible to construct all sorts of circuits (logic gates, clocks, flip-flops, frequency multipliers etc.). You can see several examples on the Wiki page.

Isn't it hypnotizing to watch the electrons zooming around on beautiful copper wires? I can watch them all day. Especially in this picture:

Fig.1. A computer calculating primes implemented in Wireworld (by http://www.quinapalus.com).

The circuit presented in Fig. 1 is a complete (and working) computer implemented in Wireworld (made by http://www.quinapalus.com). What's more, it is programmed to calculate and display primes! I remember running the simulation for many, many hours before I managed to witness it jump to next prime in line.
(Here you can watch the recording of the Wireworld computer: https://youtu.be/jnIs7n9-LKs - I still have to figure out how to encode the videos to be clearer though).

The inner workings of the simulated device are presented in great detail on its webpage. It describes the philosophy behind the clocks, logic gates, ALU and the memory of the machine (it's the long skewed bank of horizontal parallel lines on the right side of the image). It's interesting to read how it operates.

And they do have the assembly code of the CPU described there. You could program the computer to do something else altogether!

I made some implementations of Wireworld (long ago) to play with the concept. These were the days when my complete lack of knowledge about good programming practices didn't stop me to try and to write all sorts of things. You can only imagine how I feel looking back at the code. Nevertheless, here it is (you have been warned!): https://github.com/dagothar/wireworld

The programs were made to run on Ubuntu, but should work on Windows as well, if you manage to configure the environment. They use the allegro graphic libraries (http://allegro.cc), which you can install on Ubuntu easily:

$ sudo apt-get install liballegro4-dev

Then it's only a matter of makeing the projects. Sorry, there's not much support that I can give if things do not work out! I myself cannot make heads and tails out of the scramble.

Let me explain the programs briefly.

1.  wireworld program
 This one is more of a sandbox. The board is quite small, and the data is represented as a char array and stored in text files. You can paint on the board with the mouse; scroll wheel changes the type of the pixel that you paint (empty, wire, head, tail). Spacebar starts/stops the simulation. Escape closes the window. The default diagram loaded is that of a binary adder module and Gray to Binary decoder (see Fig. 2.). You can save your work (to save.wir file) by pressing the S key. L loads the file.

Fig. 2. Wireworld program. Gray2Bin decoder presented.

2.  wire program
This one is more versatile and powerful. The program accepts a .bmp file as input, e.g.:

$ ./wire circuit.bmp

 The colors of wires, heads and tails (in that order) are taken from the pixels in the upper left corner of the picture (top row). Spacebar pauses and starts the simulation. You can use S/L to store and load the diagram. The BMP file for the computer is attached (see Fig. 3.). If you wish to make your own design, simply draw one in any Paint-like program!

Fig.3. Wire program. Quinaplus computer loaded and running.

I should make a new implementation of the simulator one of these days!