2017-03-13

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

No comments:

Post a Comment