Wednesday, 31 October 2012

Evolution Explained

A lot of what you see in BeatEvolve has been done before but the unique addition here is that you are able to "evolve" your melody into something completely new. So I thought I'd devote this blog post to explaining how this evolution works behind the scenes, so to speak.

The evolution going on here is actually a technique known as cellular automata. It's something I first learned about while studying AI at university and has fascinated me ever since. There has been a lot of hype recently about emergence in video games and cellular automata represent about the purest form of emergence I can think of. Simple rules lead to a complex outcome.

So, where to begin? It's much easier to explain with an example.

Game Of Life

The Game Of Life ruleset was discovered by a mathematician called John Conway in 1970 and is the best known of all cellular automata because of it's similarity to life captured in a few simple rules.

You start with a 2D grid of cells. Some cells are "alive" (filled in) and others are "dead" (left blank). The starting pattern can be anything you like and the fun lies in trying out different ones. The pattern evolves by applying the same rules to every cell in the grid.

These are the rules for Conway's Game Of Life:
  • For each cell, count up the number of "alive" neighbouring cells. A neighbouring cell is any of the 8 cells that surround it.
  • Any "alive" cell with fewer than two "alive" neighbours dies, as if caused by under-population.
  • Any "alive" cell with two or three "alive" neighbours lives on to the next generation.
  • Any "alive" cell with more than three "alive" neighbours dies, as if by overcrowding.
  • Any "dead" cell with exactly three "alive" neighbours becomes an "alive" cell, as if by reproduction.  
Don't worry if this sounds confusing. It will all make sense with an example.

How To Calculate The Next Generation

First, let's take this starting pattern

Now we count up the number of living neighbours that each cell has.

Using the numbers in the image above along with the Game Of Life rules, we can generate the next step in the evolution.


Naturally, it takes a lot of time and effort to work out each step by hand but, of course, computers can do it so much faster! As it happens, the example above is particularly interesting in that it gradually drifts along the grid while keeping its original shape. This is known as a glider.

BeatEvolve Custom Rules

The Game Of Life ruleset is just one of almost countless possibilities in the world of cellular automata. If you'd like to read more about the subject, Mirek Wojtowicz has provided a very comprehensive website explaining all the most common types of rules and descriptions of popular rulesets for you to try out.

BeatEvolve lets you explore the whole range of Life and Generations style rulesets by allowing for customized rules. There are also six presets, including Game Of Life if you don't fancy creating your own.

The Generations style rules are very interesting an a perfect fit for music because they include decay states. This is when a cell is dying but not yet completely dead. A dying cell takes up space in the matrix and cannot be converted into a living cell. In BeatEvolve, a decaying note (cell) is played at a lower volume so you can get some subtle nuances into your music using decay states.

Finally, there is the option to use wrap around. If wrap around is selected then those cells on the edge count cells on the opposite edge as neighbours. Using wrap around means that patterns won't peter out as they get to the edge of the screen and is on by default for the six presets.

I hope I've managed to explained the evolution sufficiently in this post. Not sure if anyone will bother to read this but if someone out there now has a better understanding of cellular automata then this post has done its job.

Bye for now :).

No comments:

Post a Comment