SimFrost (#117)

Ruby
1

Isn’t this one a fun problem? Three cheers to Mark Jason Dominus for
introducing it to me.

The solutions were fantastic as well. In particular, people found many
interesting ways to render the output: using some Unixisms in the
terminal,
using curses, rendering trivial image formats like PPM and XPM, building
images
programmatically with RMagick, and even 3D rendering with OpenGL. All
of those
were very cool.

I’m going to show my own code below, but I will take a few diversions as
we go.
Here’s the start of my simulator class:

#!/usr/bin/env ruby -w

class SimFrost
def initialize(width, height, vapor)
@ticks = 0
@grid = Array.new(height) do
Array.new(width) { rand(100) < vapor ? “.” : " " }
end
@grid[height / 2][width / 2] = “*”
end

attr_reader :ticks

def width
  @grid.first.size
end

def height
  @grid.size
end

# ...

This setup code creates the grid object, filled with the particles
described in
the quiz using the quiz example notation. Several other solvers used
Symbols or
constants for these element which reads a lot better.

My grid is just Arrays of columns inside an Array of rows. This is
called “row
major” order. It’s a little backwards to the way we normally think,
because you
index with a Y coordinate and then the X, but that’s easy enough to fix
with a
helper method. It’s also great for showing results, because you can
process
them row by row.

The other three methods are just accessors for attributes of the
simulation.

One interesting point of discussion raised on the mailing list by
Christoffer
Lerno was that populating the grid as I do above, by testing a
percentage for
every cell, doesn’t necessarily fill the grid with that exact percent of
elements. The smaller the grid, the more likely you are to be off. For
example:

percent = 30
=> 30

grid = Array.new(100) { rand(100) < 30 ? “.” : " " }
=> [" ", “.”, “.”, " ", " ", " ", …, " "]

grid.grep(/./).size
=> 37

Notice how the actual percentage is off from my requested percentage by
seven
percent. This is less of an issue the bigger the grid gets and small
grids
don’t tend to be too interesting anyway, but there will usually be some
level of
error with this approach.

To solve this, you really need to calculate the percentage against the
full grid
size and ensure that you fill exactly that many cells. Christoffer’s
code for
that was:

require ‘enumerator’

percentage = 30
width = 30
height = 20
vapour = width * height * percentage / 100
vacuum = width * height - vapour
grid = []

(Array.new(vacuum, ’ ') + Array.new(vapour, ‘.’)).
sort_by { rand }.
each_slice(width) { |s| grid << s }

Laziness won out though and most of us used the trivial cell by cell
fill
strategy.

Getting back to my code, here are two more methods on the simulator:

# ...

def complete?
  not @grid.flatten.include? "."
end

def to_s
  @grid.map { |row| row.join }.join("\n")
end

# ...

These are pretty easy. First, complete?() just tells us if we are done
by
checking for any remaining vapor particles. The other method, to_s(),
is just a
nested join() on the grid object used to output results.

Now we’re ready for the heart of the simulation:

# ...

def tick
  (tick_start...height).step(2) do |y|
    (tick_start...width).step(2) do |x|
      cells = [ [x,             y            ],
                [wrap_x(x + 1), y            ],
                [wrap_x(x + 1), wrap_y(y + 1)],
                [x,             wrap_y(y + 1)] ]
      if cells.any? { |xy| cell(xy) == "*" }
        cells.select { |xy| cell(xy) == "." }.
              each { |xy| cell(xy, "*") }
      else
        rotated = cells.dup
        if rand(2).zero?
          rotated.push(rotated.shift)
        else
          rotated.unshift(rotated.pop)
        end
        new_cells = rotated.map { |xy| cell(xy) }
        cells.zip(new_cells) { |xy, value| cell(xy, value) }
      end
    end
  end
  @ticks += 1
end

private

def tick_start; (@ticks % 2).zero? ? 0 : 1 end

def wrap_x(x) x % width  end
def wrap_y(y) y % height end

def cell(xy, value = nil)
  if value
    @grid[xy.last][xy.first] = value
  else
    @grid[xy.last][xy.first]
  end
end

end

…

The tick() method is where the action is. It walks the grid
neighborhood by
neighborhood making changes. Note that cells are managed as just two
element
Arrays and I use the human-friendly X-before-Y notation. I also build
the
neighborhood by putting the cells in clockwise order. This means a
rotation is
just a shift() and push(), or pop() and unshift() to go the other way.

Cell access is all handled through the cell() helper method, which
switches the
order for row major access. Christoffer Lerno had an interesting
approach to
this cell access problem where he defined a handful of methods with some
metaprogramming:

class Neighbourhood

2.times do |y|
  2.times do |x|
    class_eval %Q{
      def xy#{x}#{y}; @grid[@x + #{x}, @y + #{y}]; end
      def xy#{x}#{y}=(v); @grid[@x + #{x}, @y + #{y}] = v; end
    }
  end
end

# ...

This allowed him to define rotations as:

# ...

def ccw90
  self.xy00, self.xy10, self.xy01, self.xy11 = xy10, xy11, xy00,

xy01
end

def cw90
  self.xy00, self.xy10, self.xy01, self.xy11 = xy01, xy00, xy11,

xy10
end

# ...

Getting back to my code, I also have wrappers for X and Y coordinates so
I can
properly handle the grid edges with modulo arithmetic. This code only
ever runs
off the right and bottom edges of the grid and only by one cell, so we
don’t
need to worry about negative numbers.

Finally, tick_start() toggles the neighborhood offset for me, though
Dave B.
did it with some cool bitwise XOR operations that looked like this:

offset = 0
=> 0

offset ^= 1
=> 1

offset ^= 1
=> 0

offset ^= 1
=> 1

Now that we have a simulator, we’re ready for some display code. The
first
display model I built was based on the Unix terminal because it was so
easy to
do:

…

class UnixTerminalDisplay
BLUE = “\e[34m”
WHITE = “\e[37m”
ON_BLACK = “\e[40m”
CLEAR = “\e[0m”

def initialize(simulator)
  @simulator = simulator
end

def clear
  @clear ||= `clear`
end

def display
  print clear
  puts @simulator.to_s.gsub(/\.+/, "#{BLUE  +

ON_BLACK}\&#{CLEAR}").
gsub(/*+/, “#{WHITE +
ON_BLACK}\&#{CLEAR}”).
gsub(/ +/, “#{ ON_BLACK}\&#{CLEAR}”)
end
end

…

Here we just wrap a simulator with some search and replace logic. The
regexen
are used to wrap the icons in terminal escape codes to color them. The
code
also shells out to clear, or uses the cached result, to erase the
terminal
before each round of drawing.

While that’s easy to code, it’s not portable or flashy. Simulations
look so
much better in graphical representations and as I mentioned before,
solvers
produced those in a variety of ways.

My own solution to the graphics problem is another trick I learned from
Mark
Jason Dominus. Believe it or not, there are a few super trivial image
formats
that you can hand roll in no time. It pays to learn one of them, for
situations
like this, when you just need some quick and dirty image output. You
can always
use a converter to get them into more popular image formats. That’s
exactly how
I built the quiz movie.

There are a few versions of the PPM image format, but the one I used
goes by the
following rules:

  1. Start the image file with P6 on its own line.
  2. The second line is the width in pixels, followed by the height in
    pixels, followed by the color range (just use 255 for this) as a
    space delimited list of integers. For example, a 640 by 480 image
    has a second line of: 640 480 255.
  3. From that point on, the rest of data is binary. Each pixel is
    represented by three characters which represent the amount of red,
    green, and blue coloring in that pixel. The numeric byte value of
    the character is the amount for the color it represents.

Watch how easy that is to code up:

…

class PPMImageDisplay
BLUE = [0, 0, 255].pack(“C*”)
WHITE = [255, 255, 255].pack(“C*”)
BLACK = [0, 0, 0 ].pack(“C*”)

def initialize(simulator, directory)
  @simulator = simulator
  @directory = directory

  Dir.mkdir directory unless File.exist? directory
end

def display
  File.open(file_name, "w") do |image|
    image.puts "P6"
    image.puts "#{@simulator.width} #{@simulator.height} 255"
    @simulator.to_s.each_byte do |cell|
      case cell.chr
      when "." then image.print BLUE
      when "*" then image.print WHITE
      when " " then image.print BLACK
      else          next
      end
    end
  end
end

private

def file_name
  File.join(@directory, "%04d.ppm" % @simulator.ticks)
end

end

…

The image implementation I just described in encapsulated in the
display()
method. The binary values are handled by constants at the top of the
class.
Note how easy it is to build PPM’s RGB colors using pack(). The rest of
the
class just creates a directory to hold the frame images and builds file
names
based on the current tick count.

Finally, we come to the application code of my solution:

if FILE == $PROGRAM_NAME
require “optparse”

options = { :width     => 80,
            :height    => 22,
            :vapor     => 30,
            :output    => UnixTerminalDisplay,
            :directory => "frost_images" }

ARGV.options do |opts|
  opts.banner = "Usage:  #{File.basename($PROGRAM_NAME)} [OPTIONS]"

  opts.separator ""
  opts.separator "Specific Options:"

  opts.on( "-w", "--width EVEN_INT", Integer,
           "Sets the width for the simulation." ) do |width|
    options[:width] = width
  end
  opts.on( "-h", "--height EVEN_INT", Integer,
           "Sets the height for the simulation." ) do |height|
    options[:height] = height
  end
  opts.on( "-v", "--vapor PERCENT_INT", Integer,
           "The percent of the grid filled with vapor." ) do |vapor|
    options[:vapor] = vapor
  end
  opts.on( "-t", "--terminal",
           "Unix terminal display (default)." ) do
    options[:output] = UnixTerminalDisplay
  end
  opts.on( "-i", "--image",
           "PPM image series display." ) do
    options[:output] = PPMImageDisplay
  end
  opts.on( "-d", "--directory DIR", String,
           "Where to place PPM image files.  ",
           %Q{Defaults to "frost_images".} ) do |directory|
    options[:directory] = directory
  end

  opts.separator "Common Options:"

  opts.on( "-?", "--help",
           "Show this message." ) do
    puts opts
    exit
  end

  begin
    opts.parse!
  rescue
    puts opts
    exit
  end
end

simulator = SimFrost.new( options[:width],
                          options[:height],
                          options[:vapor] )
setup     = options[:output] == PPMImageDisplay ?
            [simulator, options[:directory]]    :
            [simulator]
terminal  = options[:output].new(*setup)

terminal.display
until simulator.complete?
  sleep 0.5 if options[:output] == UnixTerminalDisplay
  simulator.tick
  terminal.display
end

end

While that looks like a lot of code, most of it is just option parsing
where I
fill an options Hash. The last twelve lines are where the interesting
stuff
happens. A simulator is constructed and then wrapped in a display
class. From
there we go into the main event loop which is just sleep (terminal
display
only), tick(), and draw until the simulation is complete?().

My thanks to all the super cool Ruby programmers who can literally
create ice
with the movements of their fingers.

Ruby Q. will now take a two week vacation so I can get out of town and
have a
little fun. Send me some great quiz ideas while I’m gone and we will
get them
into play when I return.