!!!PHOTOSENSITIVITY WARNING!!!

How I Started

When I was unemployed (by choice :D) three years ago, I decided to replicate Conway’s Game of Life in Python, with real-time display. At the time, I failed. I didn’t have a great grasp of array slicing, and that meant I introduced some very confusing bugs. My git fundamentals were bad, and I was a beginner at object-oriented programming. After some time at Bugcrowd, working as a web developer, I felt like my programming skills had sharpened, so I took another shot. This time I succeeded, using Python again. It felt really great to see the progress I’d made.

image

I initially used Pygame to achieve this. However, one day I saw an implementation of Conway’s on the Golang website, and it was much, much faster. I feared compiled languages, I only had minor experience in them, but I knew I had to make the jump. So I dove in. But first, an explanation of what’s different about my approach.

The Twist

The difference with my implementation of cellular automata, of which Conway’s is an example, was that I made an effort to allow random rulesets.

Consider the rules of Conway’s:

  • Any live cell with two or three neighbors survives.
  • Any dead cell with three live neighbors becomes a live cell.
  • All other live cells die in the next generation. Similarly, all other dead cells stay dead.

If we wanted, we could encode these like this, in a Go object:

type Rule struct {
  Alive       bool
  Transitions [9]uint8
}

var r0 = Rule{
  Alive:       false,
  Transitions: [9]uint8{0, 0, 0, 1, 0, 0, 0, 0, 0}}

var r1 = Rule{
  Alive:       true,
  Transitions: [9]uint8{0, 0, 1, 1, 0, 0, 0, 0, 0}}

In this case, there are 9 possible sums of the number of alive cells adjacent to a cell, from 0-8. In order to decide what to transition to each time the state changes - which in cellular automata lingo is called a “tick” - each cell looks up the rule relevant to its current state and changes to whatever state is in the array index that corresponds to the number of adjacent live cells.

But of course, these aren’t the only configurations of transitions possible:

var r0 = Rule{
  Alive:       false,
  Transitions: [9]uint8{1, 1, 0, 0, 1, 0, 0, 0, 1}}

var r1 = Rule{
  Alive:       true,
  Transitions: [9]uint8{0, 1, 1, 1, 1, 0, 1, 1, 1}}

This ruleset results in an interesting pattern:

image

A maze.

But hey, why stop at two rules:

var r0 = Rule{
  Alive:       true,
  Transitions: [9]uint8{0,3,0,1,2,2,2,1,0}}

var r1 = Rule{
  Alive:       true,
  Transitions: [9]uint8{1,0,1,0,3,1,1,3,3}}

var r2 = Rule{
  Alive:       false,
  Transitions: [9]uint8{3,1,1,2,1,3,1,2,3}}

var r3 = Rule{
  Alive:       true,
  Transitions: [9]uint8{3,3,0,1,1,3,0,0,0}}

Some even more interesting results!

image

Ants.

I Have No Idea What I Am Doing

All of these rule sets were randomized, since I have no idea what I am doing. In my Python pygame codebase, which is here, I made an effort to measure some heuristics to prune games that were boring. I stored each grid state for the game so I had a history of the game, and on each tick I would check to see if the current state totally matched a past state. Since the game proceeds deterministically, if this happened, I knew the game had entered a cycle. My assumption was that games that entered a short cycle, would be boring. This was not true. In the maze gif above, the grid eventually falls into a short cycle, but looks interesting, at least to me.

My next heuristic was based on the amount of ticks a game took to fall into a cycle. This also didn’t help, much. For sure, games that very quickly fell into a cycle (<10 ticks) were almost universally boring, but even some of those quickly fell into interesting states.

The next thing I noticed was that over about 5 rules, the games looked so random that they appeared like noise. Sometimes these games would become cyclical, but often these cycles would appear too noisy to see a pattern.

The interesting thing about these games is that they seems to have patterns that create structures. A smart friend of mine suggested feeding the grid state as inputs into a neural net. That’s left as an exercise for the reader.

image

Three rules finishing with a glider generator.

I ended up not worrying about heuristics in the golang version, because I rushed towards the graphical elements, and just select ones that look pretty. Its kind of calming to look at these random games, in my experience!

A fundamental part of this project for me was trying to get better at coding, and I chose to attempt this in golang.

My Golang Journey

I’m a Golang beginner. You can see the awful library that generated these games here. The implementation hasn’t been significantly changed for a while. I’ve mostly been working on using the visuals in interesting ways.

My initial thoughts about Go were that it was refreshing. Coming from Python and Ruby, it was kind of nice to have a language that had one way of doing things in a fair few cases. Then, I found out that I’d misconfigured GOPATH! Shit!

After a bit of playing around, I think I got it right. However, I think I still messed up the final layout of the project. Next time I’ll do better, but I think Go could have made it easier to understand.

One of the first things I didn’t #Get was the way Go uses capital letters to determine if a method/struct is public or not. A capitalized strut is a public strut:

// private
type grid struct {
  x,y int
}

// public
type Grid struct {
  x,y int
}

In a lot of my early code I was creating structs that I wanted to be public later, without that in mind.

Next, I encountered some issues with copying slices (unfixed-length arrays). I don’t think this is a problem exclusive to Go, since I’ve encountered it a bunch in Python, too, but knowing when something is a deep versus a shallow copy is important. Have a look here on stackoverflow for some of the confusion.

As a result of these kind of obstacles with slices, it was important to me to make sure my slices were intialized with the right length for copying, so I found myself writing code like this a fair bit:

type alives struct {
  x, y  int
  array [][]bool
}

func makeAlives(x int, y int) alives {
  array := make([][]bool, y)
  for idx := range array {
    array[idx] = make([]bool, x)
  }
  return alives{x, y, array}
}

This type of code seemed frustrating, but also necessary so I allocated only the memory I needed, something I hadn’t really had to think about before.

I was keen to try out some parallelism, so I attempted to run many games in parallel. I hit an interesting problem. When I tried to access the Source I’d created to give me random integers, in order to make the Grid state randomized, it would fail. This meant I had to place a sync.Mutex on the random number generator.

// random generator
var randMutex sync.Mutex
var src = rand.NewSource(time.Now().UnixNano())
var r = rand.New(src)

func randInt(i int) int {
  randMutex.Lock()
  integer := r.Intn(i)
  randMutex.Unlock()
  return integer
}

With that out of the way, it was actually very easy to run the code in parallel by just kicking off the function I used to run the randomized games:

// RunMany games of life using the Options provided
func RunMany(Options GameOpts, gameAmount int) {
  var wg sync.WaitGroup
  wg.Add(gameAmount)
  for i := 0; i < gameAmount; i++ {
    go func(i int) {
      defer wg.Done()
      g := MakeGame(Options)
      g.Run()
      fmt.Println("Game ", i)
    }(i)
  }

  wg.Wait()
}

The magic here is in the go - a goroutine and the WaitGroup. These work in concert to ensure everything is executed (the go) and then the program Wait()s until everything is done. This lead to an embarassingly quick program, but individual games were only being executed at a speed that would allow only 10fps on a relatively small grid. More had to be done.

Implementation Specifics

At this point, I implemented an OpenGL renderer, using the Go bindings. I won’t touch on it much because I don’t feel like I understand OpenGL enough to. Passing colour data to the shader took me way longer than it should have - and you can see some of those struggles in the repository commit history. There’s a lot of room for improvement, as the colour is passed on each cell update, when it could be set once, much earlier, then looked up in the shader. I hope I’m good enough to do that one day.

The first optimization that really increased performance was related to counting the surrounding Alive cells. The intuitive way to tick the game seemed to be this:

  1. For every cell, count the surrounding alive cells.
  2. On a new cell grid, set the same cell location to the new cell type as per the rule transitions
  3. Start using the new cell grid.

You may already see the problem with this. This means that as we progress around the grid, most cells Alive/Dead state is accessed 8 different times as the nested for loops progress around the board.

The better tactic was to do this:

Init

Create a grid of integers that represent the adjacent alive counts. For every cell that is alive, increment the surrounding cells on the alive grid.

During the game

  1. Copy the alive count integer grid to a new grid.
  2. For every cell, use the old alive count grid to set the same cell location to the new cell type as per the rule transitions
  3. Increment/Decrement all surrounding cells on the new alive grid if the Alive/Dead status changes, or do nothing if it doesn’t
  4. Start using the new cell grid and alive count grid

The advantages may already be obvious, but they include:

  • Cells aren’t checked for their alive status multiple times
  • If the cell doesn’t change from alive to dead or vice versa, no action is taken for alive counts

Thanks for reading so far! Have a pretty gif!!!

image

How would I even describe this?

Since I’d implemented OpenGL, I’d read a little bit about front and back buffers. While this buffering has some other advantages in video, I was interested in it because they meant I didn’t have to reallocate memory. If I had two grids that I flipped between, I could always use the same two, and never reallocate memory for the cell states. This was true of both the cell rules, and the alive counts. This also lead to a significant speedup.

Future

The code isn’t great.

image

Strawberries?

I’m hoping to implement some heuristics again, to try and prune uninteresting games. Since I’ve parallelized and sped up running the games, it may be easier for me now to run experiments.

I was thinking I might use some graph theory and visualization with Graphviz to graphically show how transitions link together.

There’s a pretty significant community of people interested in Cellular Automata, and I hope they find this interesting! I can probably learn a lot from them, and know they’ve explored games with more than 2 rules a fair bit.

Maybe I’ll make this into some art project?

image

How I Generated This Post

Since I’m going outside even less at the moment, it seemed like a good opportunity to write some blog posts.

Interfacing with the library can be quite straightforward, and not require much code. It is possible to save and load games in a json format. For the purposes of this post I iterated through a list of pregenerated json games after intially loading conway’s game of life. I also included a method for capturing the screen as pngs when desired. You can see that code in a gist here.

I then used ffmpeg to convert the pngs into gifs with the following shell script:

rm out/output_*.gif
for d in */ ; do
  ffmpeg -i $d%4d_screenshot.png -f gif -vf "fps=10,scale=iw*.5:ih*.5,split[s0][s1];[s0]palettegen[p];[s1][p]paletteuse" -loop 0 out/output_${d%?}.gif
done

I was originally piping this to gifsicle but ffmpeg seemed faster!

Thanks for reading! Comments and questions welcomed.