rubyでライフゲームを実装してみた

きのうと今日は趣味のプログラミング。
高校一年の時にライフゲームの存在を知った。その頃使っていたコンピュータはNECのTK-80BS。早速NEC LEVEL1 BASICを使って実装にチャレンジした。このBASICは整数演算のみで配列変数も１次元のものが１つ(@)しか使えず、すごく不自由なプログラミング。それでもなんとか完成させ実行してみると、32文字x16行で１世代進めるのに一分以上かかってしまう。描画も非常に遅く、ちょっとパターンを試してみるだけでも日が暮れてしまう。そこで8080マシン語でプログラムを組み直し実行してみた。すると１秒間に３世代程度更新するようになって、何とか遊べるようになった。（本題からそれるけど、TK-80BSではハードウェアの問題からVRAMにデータを書き込むとノイズが発生する。機械語で高速に書き込むと吹雪が降っているような画面になってしまう）
その後PC-8001を入手したのでZ80マシン語で実装し直し、78文字x23行で１秒に３世代程度のスピードが確保できた。このプログラムは、当時所属していたFORESIGHTの会報に載せて頂いた。（「開発言語」が「BASIC」となっているけど、DATA文のマシン語プログラムをPOKEでメモリに書き込む形だった...と思う）
その後FM-7やPC-9801などを所有するようになったけど、ライフゲームを実装することは無かった。
久しぶりにライフゲームを実装する気になったのは、当時と比べてハードウェアが格段に進歩して比較にならないような速度となっており、ソフトウェア面でもプログラマにとって優しい（== ハードウェア性能が要求される）rubyなどの動的言語が台頭してきているという状況で、当時ハンドアセンブルで苦労して実装してやっと実現できた性能が、今時のハードウェア・ソフトウェアで作るとどうなのよ....を実感してみたかったということ。
プログラム本体(lifegame.rb)のソースは、このエントリの最後に載せた。このソースだけではダメで、画面サイズや初期パターンを定義するファイルが別途必要となる。
最初にTK-80BSの画面環境で試してみた。画面サイズは32x16だけど、上下左右に枠を1文字確保していたので、30x14となる。初期パターン定義は以下の通り。

require 'lifegame.rb'

LifeGame.setup :size_h => 30,   # 水平方向サイズ
               :size_v => 14,   # 垂直方向サイズ
               :count => 1000   # 実行回数
#
# 初期パターン
#
LifeGame.set_pattern(<<EOS)
    ooooooooo
 o       ooooo
EOS

LifeGame.start

Macbook（Core2Duo 2.4GHz 4GB OSX 10.5.6）のターミナルで実行してみた結果は以下の通り。

速い!! fpsを表示出来るようにしているのだけど、最大120fps程度出ている模様。TK-80BSマシン語の40倍の性能が出ている。

次にPC-8001での画面サイズで試してみた。

require 'lifegame.rb'

LifeGame.setup :size_h => 78,   # 水平方向サイズ
               :size_v => 23,   # 垂直方向サイズ
               :count => 1000   # 実行回数
#
# 初期パターン
#
LifeGame.set_pattern(<<EOS)
    ooooooooo
 o       ooooo
EOS

LifeGame.start

25fps程度の性能。PC-8001よりも10倍ほど速い。

調子に乗ってターミナルを最大化して試してみた。

require 'lifegame.rb'

LifeGame.setup :size_h => 300,   # 水平方向サイズ
               :size_v => 80,   # 垂直方向サイズ
               :count => 1000   # 実行回数
#
# 初期パターン
#
LifeGame.set_pattern(<<EOS)
    ooooooooo
 o       ooooo
EOS

LifeGame.start

さすがに遅い．最大1.8fps程度。プログラムを見直せば改善できると思う。

最後に、速すぎる場合、最大fpsを制限する指定を追加してみた。5fpsで表示させてみる。

require 'lifegame.rb'

LifeGame.setup :size_h => 30,   # 水平方向サイズ
               :size_v => 14,   # 垂直方向サイズ
               :count => 1000,  # 実行回数
               :max_fps  => 5     # 最大FPS
# 
# 初期パターン
#
LifeGame.set_pattern(<<EOS)
    ooooooooo
 o       ooooo
EOS

LifeGame.start

かなり見やすくなった。

本体のプログラムは、以下の通り。

class Field
  attr_reader :data

  def initialize(h_size,v_size)
    @h_size,@v_size = h_size,v_size
    @data = Array.new(@v_size,0)
  end

  def [](h,v) ; @data[v][h] end

  def []=(h,v,value)
    case value
    when 0 then @data[v] &= ~(1 << h)
    when 1 then @data[v] |= 1 << h
    else raise
    end
  end

  def size ; [ @h_size,@v_size ] end

  def clear ; @data.fill(0) end

  def advance(target_field)
    population = 0
    (0...@v_size).each do |v_pos|
      (0...@h_size).each do |h_pos|

        surround_count = 0
        (-1).upto(1) do |v_def|
          (-1).upto(1) do |h_def|
            next if v_def == 0 && h_def == 0
            v_point = v_pos + v_def
            h_point = h_pos + h_def
            if (v_point >= 0 && v_point < @v_size) then
              surround_count += @data[v_point][h_point]
            end
          end
        end

        population += 
          target_field[h_pos,v_pos] = apply_rule(surround_count,@data[v_pos][h_pos])
      end
    end
    return population
  end

  def apply_rule(surround_count,source_status)
    case surround_count
    when 2 then source_status
    when 3 then 1
    else 0
    end
  end
end


class Deployer
  attr_reader :field

  def initialize(h_size,v_size) 
    @field = Field.new(h_size,v_size)
  end

  class Array
    def each_with_index(&block)
      index = 0
      self.each do |value|
        yield value,index
        index += 1
      end
      self
    end
  end 

  def set_pattern(pattern)
    fieldsize_h,fieldsize_v = *@field.size

    pattern_data = pattern.split "\n"
    h_base = (fieldsize_h - pattern_data.map { |data| data.size}.max) / 2
    v_base = (fieldsize_v - pattern_data.size) / 2
    pattern_data.each_with_index do |row_data,row_index|
      (row_data.split '').each_with_index do |ch,ch_index|
        @field[h_base+ch_index,v_base+row_index] = 1 if ch != ' '
      end 
    end
  end
end

class Life
  def initialize(field,count,fps)
    @field,@count,@fps = field,count,fps
    @h_size,@v_size = *@field.size
    @field2 = Field.new(*@field.size)
  end

  def start
    population = 0
    message = ''
    now_time = (previous_time = Time.now.to_f) + 1
    1.upto(@count) do |generation|
      display(' ','o',generation,population,message)
      effective_fps = 1.0/(now_time - previous_time);
      if effective_fps > @fps then
        sleep 1.0/@fps - (now_time - previous_time)
        now_time = Time.now.to_f
      end
      message = "fps=#{'%5.2f' % (1/(now_time - previous_time))}"
      population = @field.advance(@field2)    
      previous_time,now_time = now_time,Time.now.to_f

      @field,@field2 = @field2,@field
    end
  end

  def display(dead_char,live_char,generation,population,message)
    cls
    locate 1,1
    print "Generation=#{generation}  Population=#{population} #{message}"
    (0...@v_size).each do |v_index|
      contents = ' '*@h_size
      (0...@h_size).each do |h_index|
        contents[h_index] = [dead_char,live_char][@field[h_index,v_index]]
      end
      locate(1,v_index+3)
      print(contents)
    end
    $stdout.flush
  end

  private
  def locate(h,v) ; print "\033[#{v};#{h}H"; end
  def cls ; print "\033[2J" ; end

end

# for game definition

class LifeGame
  def LifeGame.setup(info)
      @@dep = Deployer.new(info[:size_h],info[:size_v])
      @@count = info[:count]
      @@fps = info[:max_fps] || 300
  end
  def LifeGame.set_pattern(pattern) ; @@dep.set_pattern(pattern) ; end
  def LifeGame.start ; Life.new(@@dep.field,@@count,@@fps).start ; end
end 

• 【2009/05/24追記】

Array#each_with_indexを再定義していた。取り除いたコードを再掲。

class Field
  attr_reader :data

  def initialize(h_size,v_size)
    @h_size,@v_size = h_size,v_size
    @data = Array.new(@v_size,0)
  end

  def [](h,v) ; @data[v][h] end

  def []=(h,v,value)
    case value
    when 0 then @data[v] &= ~(1 << h)
    when 1 then @data[v] |= 1 << h
    else raise
    end
  end

  def size ; [ @h_size,@v_size ] end

  def clear ; @data.fill(0) end

  def advance(target_field)
    population = 0
    (0...@v_size).each do |v_pos|
      (0...@h_size).each do |h_pos|

        surround_count = 0
        (-1).upto(1) do |v_def|
          (-1).upto(1) do |h_def|
            next if v_def == 0 && h_def == 0
            v_point = v_pos + v_def
            h_point = h_pos + h_def
            if (v_point >= 0 && v_point < @v_size) then
              surround_count += @data[v_point][h_point]
            end
          end
        end

        population += 
          target_field[h_pos,v_pos] = apply_rule(surround_count,@data[v_pos][h_pos])
      end
    end
    return population
  end

  def apply_rule(surround_count,source_status)
    case surround_count
    when 2 then source_status
    when 3 then 1
    else 0
    end
  end
end


class Deployer
  attr_reader :field

  def initialize(h_size,v_size) 
    @field = Field.new(h_size,v_size)
  end

  def set_pattern(pattern)
    fieldsize_h,fieldsize_v = *@field.size

    pattern_data = pattern.split "\n"
    h_base = (fieldsize_h - pattern_data.map { |data| data.size}.max) / 2
    v_base = (fieldsize_v - pattern_data.size) / 2
    pattern_data.each_with_index do |row_data,row_index|
      (row_data.split '').each_with_index do |ch,ch_index|
        @field[h_base+ch_index,v_base+row_index] = 1 if ch != ' '
      end 
    end
  end
end

class Life
  def initialize(field,count,fps)
    @field,@count,@fps = field,count,fps
    @h_size,@v_size = *@field.size
    @field2 = Field.new(*@field.size)
  end

  def start
    population = 0
    message = ''
    now_time = (previous_time = Time.now.to_f) + 1
    1.upto(@count) do |generation|
      display(' ','o',generation,population,message)
      effective_fps = 1.0/(now_time - previous_time);
      if effective_fps > @fps then
        sleep 1.0/@fps - (now_time - previous_time)
        now_time = Time.now.to_f
      end
      message = "fps=#{'%5.2f' % (1/(now_time - previous_time))}"
      population = @field.advance(@field2)    
      previous_time,now_time = now_time,Time.now.to_f

      @field,@field2 = @field2,@field
    end
  end

  def display(dead_char,live_char,generation,population,message)
    cls
    locate 1,1
    print "Generation=#{generation}  Population=#{population} #{message}"
    (0...@v_size).each do |v_index|
      contents = ' '*@h_size
      (0...@h_size).each do |h_index|
        contents[h_index] = [dead_char,live_char][@field[h_index,v_index]]
      end
      locate(1,v_index+3)
      print(contents)
    end
    $stdout.flush
  end

  private
  def locate(h,v) ; print "\033[#{v};#{h}H"; end
  def cls ; print "\033[2J" ; end

end

# for game definition

class LifeGame
  def LifeGame.setup(info)
      @@dep = Deployer.new(info[:size_h],info[:size_v])
      @@count = info[:count]
      @@fps = info[:max_fps] || 300
  end
  def LifeGame.set_pattern(pattern) ; @@dep.set_pattern(pattern) ; end
  def LifeGame.start ; Life.new(@@dep.field,@@count,@@fps).start ; end
end