m@munday

Updates…

Things have been pretty quiet over the last few months. I’ve relocated to California and started a new job. During the transition I fell a bit behind on my personal coding projects, but I’ve been trying to devote more time as I’ve adjusted more. Recently I released an update to my sliding menu library that enabled dragging the menu open and closed and revamped how the shadow worked. I also did some minor updates to swarm, including using the updated sliding menu library and some graphical updates including a new icon. That’s it for now. I’ll try to start posting more often again now.

Evolving automata

I wanted to present a cellular automation music generator written in javascript  and discuss the methods I used this time, but my attempts thus far have not yielded  audio nearly as nice as that which I ended my last CA article with. In lieu of that here is a bit more info how cells evolve in an elementary cellular automation.

A neighborhood

In this post I’ll describe how a cell in a new generation of an elementary cellular automation is created. I stated before that a rule is applied to a neighborhood of cells of a generation, in the case of elementart cellular automation this is any given cell and it’s neighbor to the left and its neighbor to the right (Fig 1).

neighborhood

Fig. 1 The neighborhood of the filled cell

These three cells determine what the state of the new cell at the came position as the shaded cell in the next generation will be. Each cell in a generation has three parents.

If we look at all the possible combinations of the values of the three cells, we find that there are 2^3 or 8. As proof, here is a printed representation of all possibilities [000, 001, 010, 011,100,101,110,111]. The concept of all cells in a neighborhood creating the next generation is true of all cellular automata, though the neighborhoods themselves can be much more complicated.

A rule

[000, 001, 010, 011, 100, 101, 110, 111]
[ 0 ,  0 ,  0 ,  0 ,  0 ,  0 ,  0 ,  0 ]

Since there must be a child cell in each position of a new generation, there must be an outcome for each of the 8 possible states of the parent cells. The list of all possible outcomes is called a rule. Each rule is named by taking the 8 outcomes (either 1 or 0) as binary and then converting it to an integer representation. For example, the simplest and most boring rule is rule 0. Rule 0′s binary is 00000000 and since a rule’s binary representation is the outcome of a new generation, rule 0 does nothing, it just repeats 0′s forever. If you were wondering, yes, since there are 8 bits in each rule there are a total of 2^8 or 256 rules.

Sharing parents

As you may have noticed, each generation of a cellular automation has the same number of cells as the previous generation. How, you ask? Well it’s simple really cells in the new generation share parents. Each Cell shares 2 of it’s parents with each of the cells on either side of it. The illustration (fig. 2) below shows the shared parents of the two shaded cells on the bottom row by shading the shared parents in a darker blue. Obviously, all cells in the lower generation share parents as well, the illustration is just to show how 2 adjacent cells cells share the majority of parents.

sharedparents

fig. 2 Shared parents

There you have it, a base understanding of how cells are evolved from their 3 parents to rules and rule spaces, and parent sharing. The evolution of cells IS cellular automation and from these simple concepts we get some pretty interesting stuff.

Visualized Cellular Automation

161The more study and write about elementary cellular automation, the more I see that visualization isn’t  just a nice decoration, it is the easiest way to convey the interesting parts of certain automata. No matter how much I talk about the fractal shapes of rules like 18, 126 or 161, or how rule 126 and 129 are related, without a visual frame of reference they are just numbers. To combat that fact and to continue my exploration, I’ve made a html visualizer. Click on the numbers of the rules in the previous sentence and you can view and execute the cellular automation that corresponds to the rule. The visualizer itself also has another option that I’ve been working on: a button titled “Randomize!”. The button works the same as the run button except it randomly adds more base seeds then runs the animation, the results of random seeded automata have been visually interesting so far and I hope will aid in future uses of the tool. The UI isn’t too user friendly at the moment but you can mess with it here, or use a url to automatically render an automation like so: http://munday.ws/?r=[number of rule]&g=[number of generations] ex:  http://munday.ws/ca/?r=30&g=100, which will draw 100 generations of rule 30.

Visualization is not the only reason that I have extended my cellular automation code, I’ve decided to also tackle music generation from automata as well. The basic concept for turning automata into music is to:

  1. Pick a rule.
  2. Execute the rule for some number of generations.
  3. Select a 2d [notes,generation] array that is a subset of the output.
  4. Iterate over the each generation at some time interval, playing the note assigned to all cells in the “on” state.
  5. Listen.

The process is simple enough, and I have some ideas on how to make music by combining several automata by changing rules at fixed rates over the automation. I’m currently searching for javascript based audio tools to help me create the audio portion of the project.  Hopefully my next post on cellular automation will have audio and visuals of automata, but until then I leave you with a little atuomata music from Softology:

Pascal’s triangle PSA

Instead of thinking about pascal’s triangle like this:

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1

I think about it like this:

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1

It makes more sense.

That is all.

The_More_You_Know

Exploring Cellular Automation

Rule 30

Rule 30 (00011110)

Background TL;DR: For a long time I’ve had a passive interest in cellular automation. As someone who’s been obsessed with software and for years, it seems like a natural fit, but I haven’t had the motivation to dive in, until I returned to school to get a computer science degree. Now, it’s not exactly for research or some comp-sci project, I decided to use cellular automation as a subject for my Communications for Engineers class. To help make my way through all the writing, learning something that’s been somewhat of an interest of mine accomplishes two things.

Cellular Automation

In general, Cellular automation is a discrete model that consists of a grid of cells with a finite number of states that change over time based on a set of rules and the states of adjacent cells. Variations of automata can get complicated rather quickly, which is why I chose to start with elementary cellular automation, a one dimensional automata.

Elementary Cellular Automation

As I stated before, elementary cellular automation is about as simple an automation as they come. Each cell has a binary state (on or off) and the neighborhood of cells that affect subsequent generations of the automation are a cell and the cells to its left and right. Two states and three cells in the neighborhood provides for 2^3 or 8 possible configurations. The rule space for the automation covers all of the configurations is 2^8 or 256 possible rules. Such a small space should be boring right? Wrong. These simple contents house such things as turing completeness and chaos! The small nature and interesting output makes it ideal for me to implement for fun and profit! (or credits :D)

The first generation of the automation is generally seeded with a single cell in the middle, then for some number of times t, the rule is applied to the previous generation, resulting in newer changing generations for each iteration.

The rules themselves have a name, they’re called Wolfram codes after Stephen Wolfram who devised the scheme of using integer representations for each of the 256 eight bit binary rules. The scheme makes the rules easy to discuss and is quite logical.

Implementing the automation

Ok, enough background explanation, lets get to the fun stuff. I chose to make a simple implementation in javascript to run in the browser, initially rendering output to a html table and hopefully using html canvas and/or processing.js for a nicer output.

I broke the concept into two parts, the cell: an element with references to the cells to its left and right, a boolean state, and a function to apply a rule to the cell; and a world: the grid that visualizes the cells. The world holds the rule, a width, the collection of cells and functions to initialize the first generation of cells, one to evolve new generations and one to spit out the visualization.

That’s about it for this post. I’ve posted the javascript code here and will add the demo and post it to Github after I finish making the forms to apply the various rules and options. Note: the image used for this post is a screenshot of the output of a simple implementation of the javascript code posted here.

New sliding menu feature: Parallax

I added a new option in my sliding menu library: MENU_TYPE_PARALLAX.
It basically makes the menu slide out at twice the speed that the content slides away, giving an interesting effect.
To use it call

setType(MENU_TYPE_PARALLAX);.

I also added manifest option

android:hardwareAccellerated="true"

to the test app so that older devices that take advantage of the feature for animation.

Once again, Here’s the project on github

Sliding menu rework

Last night I noticed that the sliding style menu option of my dead simple sliding menu was wonky on my nexus 4 (the slide over style was fine). This led me down a rabbit hole to a new version at about 4:30am, then another update at 8:30 to fix some fixes :)

I also documented the crap out of it.

Net result is a new Dead simple sliding menu on github. Go get you some.

Torrent-fu beta

I just posted a beta for a new version of torrent-fu on torrent-fu.com. The new version has a revamped ui and some new features. Try it out and send me your input/suggestions/etc…

Click here to Get: Torrent-fu concept 2 beta

Optimizing Android Performance

I’ve recently pushed a few minor updates to my android dead simple sliding menu that fixed some bugs and limited overdraw issues after being inspired by the following post on curious-creature.org about optimizing android performance:

http://www.curious-creature.org/2012/12/01/android-performance-case-study/.

Not only did reading the article inspire me to optimize Swarm last night, it taught me a more about some of the tools I had never used or known about in the Android Developer toolkit.

The article was very helpful and will hopefully  get more developers thinking about user experience in general on Android since it can be a bit lacking, especially on single developer projects.

Android Scala base update

I recently updated my Android Scala base project (https://github.com/munday/Android-Scala-Base) to support ubuntu as well as mac. The master branch is for mac and the ubuntu branch is for ubuntu.