Eric Weeks - personal pages - computer-generated pictures Cellular Automata on a QuasiCrystal

weeks/physics.emory.edu

Description

This picture was generated on a quasi-periodic tiling of the plane possessing 5-fold symmetry.

I ran a simple cellular automata called the "voter" CA. Each tile is a voter, voting either for the Democrats (blue) or Republicans (purple). If you implement this sort of algorithm in black & white, it's up to you which is which. Initially, all tile have a random state.

To start, choose a tile at random. Examine all of it's close neighbors (details below). If more than half of them are one color, the chosen tile switches to that color. Repeat this for a while; the final state is a bunch of clusters of voters of like mind. If only politics in real life were this simple.

Normally, you do this sort of thing on a rectangular grid, and it's easy to define what you mean by neighbors. Here, each tile has four neighbors that share edges with it. If you want to consider wider neighborhoods, you have to decide what you mean. Do you consider neighbor tiles if they only touch at corners, rather than edges? Well, I didn't want to program this in, so I didn't. What I did instead was to define a neighborhood of depth N: I first find the tiles that touch the original tile with a common edge. That's the depth-1 neighborhood. I then find the depth-1 neighborhood of all of those tiles; those tiles are the depth-2 neighborhood of the original tile. I do this recursively to find a depth-N neighborhood.

My final rule for deciding if a tile should switch is based on how many neighbors are in it's depth-N neighborhood.

If N is odd, there must be more than (N+1)/2 neighbors of a certain color to switch; if there are exactly (N+1)/2 neighbors it won't switch.
If N is even, there must be more than N/2 neighbors of a certain color to switch; if exactly N/2 neighbors, no switching.

I added a slight twist; if the depth-N neighborhood includes the boundary of the picture, the cell can't change. Thus, the boundaries of the picture are stubborn voters, and never change their minds, thus setting boundary conditions for the fickle tiles in the middle.

The picture at the top of this page was generated with a depth-3 neighborhood, and the tile-updating procedure was done 100,000 times. There are 5324 cells in the picture.

You may be wondering how the typical neighborhoods look -- I hinted above that some cells have odd numbers of neighbors, and some have even numbers. For the 100,000 iteration run, I made a histogram of the number of randomly chosen cells that had a given depth-3 neighborhood size. In the graph below, "dat00" is fat tiles (solid line, diamond symbol) and "dat11" is skinny tiles (dashed line, plus symbol).

Two examples of depth-5 neighborhoods are shown below (around the green tiles):

Click here to see the same algorithm as above, run on 86,036 tiles, 200,000 iterations, and a depth-5 neighborhood. (40k picture)

Curious what the Earth would look like from space if we had a 3-party system world government? Click here for more information. Or, perhaps it's just a 3-party majority rule CA run on a quasi crystal ...

Click here to see two CAs with different rules for skinny and fat tiles. (47k)

Links...

• CLICK HERE FOR INFORMATION ABOUT SOFTWARE USED TO MAKE QUASICRYSTALS
• Software I've written -- some functional, some fun
• Research I do
• Various simple algorithms for making simple pictures
• Graphics techniques (some used to make these pictures)
• Questions? Comments? Send me email; email address below.