Life in a shade of ruby
Conway's Game of Life is a great way to practice your craft. I recently created my own rendition in Ruby, and have plans to implement it in Javascript and Erlang. If you haven't heard of Conway's Game of life (CGOL), it is a cellular automaton [1], essentially a mathematical model, consisting of a two dimensional grid where each x and y coordinate are either alive or dead. Whether a cell is alive or dead is governed by a simple set of rules, and the game advances/evolves by applying the rules to each cell based on the previous generation's configuration and then repeating. Wow, that was seriously a mouthful. I would go into why this game has kept programmers interested in it despite being ~forty years old, but as soon as you start with CGOL you'll see how fascinating it is to see an entire world of complexity arise from low level constructs. Let's go through the rules and then meet back up to discuss the code.
Rules
Each cell has eight neighbors, three above, one on either side, and three below. The rules of CGOL simply govern the state of the cell in question as it relates to the state of its neighbor cells.
That's it. For real. The entire list of rules can be summarized in Ruby like so.
# If cell is alive then it continues to stay alive if it has
# 2 or 3 alive neighbors. If the cell is dead then it comes
# back to life only if it has exactly 3 alive neighbors.
@alive ? [2,3].include?(alive_neighbors) : alive_neighbors == 3
After seeing that, you get an idea of why this CGOL is so interesting. Its set of rules create extreme complexity from little input. Take a look at the pattern, acorn. It is a methuselah that takes 5206 generations to generate 633 cells including 13 escaped gliders [2]). (It won't mature fully in the video because it's on a 50x50 grid)
The Code
Now that you understand Conway's Game of Life, we can start talking about how to implement it. The examples found here are from my first attempt at creating CGOL. It's not perfect, but it'll serve to illustrate why this is such a fun problem. Ryan Bigg did a screencast in which he creates CGOL through a test driven approach [3]. It's well worth your time and probably a better implementation. For now, we'll just go off my version.
The Cell
class Cell
attr_accessor :y, :x, :alive, :future_alive
def initialize(x,y,alive=false)
@x = x
@y = y
@alive = alive
end
def is_alive?(sum)
self.future_alive = if @alive
[2,3].include?(sum)
else
sum == 3
end
end
def set_next_generation
self.alive = self.future_alive
self.future_alive = nil
end
def to_s; @alive ? ' O ' : " " end
end
This is your basic cell. It stores its own coordinates and whether it is alive or not. The Cell#isalive? sets a variable called futurealive which dictates its state in the next generation. The reason we need to store its future state in its own variable is because if we change its alive status (while iterating over each celll) it will alter its neighbors calculations. Each new generation must be computed using the previous generation's information. To avoid violating this principle, we need to store the calculated value while operating on the original state.
It might be better not to save the coordinates within the cell itself, but it makes working with the object much, much easier. Basically, with the Cell class we have a mini state machine.
After that, creating the grid of cells is as easy as:
# Array#new accepts a block....radical!
@cells = Array.new(@height) { |y| Array.new(@width) { |x| Cell.new(x,y) }}
The Game
To tie all the cells together, I created the Game class. It creates the playing board and processes each generation. We initialize it with the dimensions of the board and how many generations we'd like to process, and tell it to #play.
class Game
def initialize(w,h,steps)
@width,@height,@steps = w,h,steps
@cells = Array.new(@height) { |y| Array.new(@width) { |x| Cell.new(x,y) }}
@neighbors = [[-1, 0],[1, 0],[-1, 1],[0, 1],[1, 1],[-1, -1],[0, -1], [1, -1]]
end
def play
(1..@steps).each_with_index do |i|
system('clear')
puts self.to_s
step
sleep 0.1
end
end
def step
@cells.reverse.each do |row|
row.each do |cell|
cell.is_alive? alive_neighbors(cell.x, cell.y)
end
end
@cells.each {|r| r.each {|c| c.set_next_generation }}
end
def alive_neighbors(x,y)
@neighbors.inject(0) do |sum, (neighbor_x, neighbor_y)|
sum += 1 if @cells[y + neighbor_y][x + neighbor_x].alive; sum
end
end
def to_s
@cells.reverse.map { |row| row.join }.join("\n")
end
end
The cool part is Game#alive_neighbors it's here where we determine how many neighbors are alive. I've said before that when you have Ennumerable#inject everything looks like a nail. It's definitely my favorite ennumerable method, and here I use it to get a count of neighboring cells with their internal state set to alive. We just take the point we are testing and add the points from the @neighbors array and add to sum if that cell is alive. Super simple.
The Pattern
Alright, that's all well and good, but we don't actually have any cells alive in the initial state so our entire program (though perfectly functional) does exactly nothing. So I created a pattern Class:
class Pattern
def initialize(x, y, pattern=nil)
@origin_x, @origin_y = origin_x, origin_y
@default_patterns = {:acorn => [[-3,0],[-2,0],[-2,2],[0,1],[1,0],[2,0],[3,0]]}
@pattern = @default_patterns[pattern].nil? ? @default_patterns[:acorn] : @default_patterns[pattern]
end
def set_cells(cells)
@pattern.each do |(x,y)|
unless cells[@origin_x + x].nil? || cells[@origin_x + x][@origin_y + y].nil?
cells[@origin_y + y][@origin_x + x].alive = true;
end
end
end
end
You'll notice that the Pattern#setcells method looks a lot like the aliveneighbors method and it is. This allows you to trigger certain cells alive by calculating their points relative to an origin point. It sounds complicated, but it's actually quite simple, assuming you have a pattern you just call:
Pattern.new(somepoint_x, somepoint_y, :acorn).set_cells(@cells)
Call that directly before you begin iterating over @steps in Game#Play and you'll create your origin points. Once you've gotten familiar with that, you can create any pattern you like (there are many great patterns online). Here is the famous gospers-glider-gun:
Defined like so:
:glider_gun => [[0,0],[-1,0],[-1,1],[-1,-1],[-2,2],[-2,-2],[-3,0],
[-4,3],[-5,3],[-4,-3],[-5,-3],[-6, 2],[-6,-2],
[-7,1],[-7,0],[-7,-1],[-16,0],[-17,0],[-16,1],
[-17,1],[3,3],[3,2],[3,1],[4,3],[4,2],[4,1],[5,4],
[5,0],[7,4],[7,5],[7,0],[7,-1],[17,2],[17,3],[18,2],
[18,3]]
Conclusions
In Ruby, I completed my first working prototype CGOL in an hour or two. It was a lot of fun. It's a great problem and has probably been written in every language ever created. The reasons for that are clear; it's a fun problem that forces you to use many different aspects of the language. In Ruby, this was pretty simple, but I've been writing in Ruby for years. I'm going to try writing this in a language I don't know well and use it for what it is: a fun learning tool. Some of the patterns I've seen around the web have truly impressed me. While rules of the game are simple, the resulting complexity is truly amazing. Take some time and try coding this in your language of choice, or improve this one. Either way, have fun with it. ^_^
References
1.) Wiki Entry on Cellular Automaton
2.) Methuselah Definition
3.) Ryan Bigg's Solution TDD
Additional References
Awesome Life News Site
Game of Life Demo on YouTube
