Midpoint Displacement (#197)

Ruby
1

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

The three rules of Ruby Q.:

  1. Please do not post any solutions or spoiler discussion for this
    quiz until 48 hours have elapsed from the time this message was
    sent.

  2. Support Ruby Q. by submitting ideas and responses
    as often as you can! Visit: http://rubyquiz.strd6.com

  3. Enjoy!

Suggestion: A [QUIZ] in the subject of emails about the problem
helps everyone on Ruby T. follow the discussion. Please reply to
the original quiz message, if you can.

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

Midpoint Displacement (#197)

Haileo Rubyists,

The midpoint displacement algorithm is used to generate random
terrain in one dimension. The idea behind the algorithm is to start
with a line segment and adjust the middle by a random amount. This is
repeated for each new segment, with a decreasing random threshold. In
the end you will end up with an interesting looking ridge line.

This week’s quiz is to develop a Ruby implementation of the algorithm.
The details of the implementation are up to you, but the output should
be an array containing the heights. This can be displayed visually for
extra credit. Golfers are welcome, but easily explainable solutions
are cool too.

2

Ok, 48 hours has been passed by so here’s my solution:

=== BEGIN
require ‘enumerator’

segments = [0.0,0.0]; midpoints = []
max_randomness = 40
times = 5
app = {:width=>600, :height=>200}
boundary = 10

while times > 0 do
segments.each_with_index do |b,i|
next if i == 0; a = segments[i-1]
midpoints << ((a + b / 2.0) + (rand(max_randomness) -
(max_randomness /
2.0)))
end
segments = segments.zip(midpoints).flatten.compact
max_randomness -= 5; times -=1;
end

segment_width = (app[:width] - boundary*2) / segments.size.to_f

Shoes.app (:title=>‘Dreaming mountains’, :resizable=>false,
:width=>app[:width], :height=>app[:height]) do
stroke white
strokewidth 2
background black

segments.each_with_index do |b,i|
next if i == 0; a = segments[i-1]
line (f = (segment_width*(i-1) + boundary)), a + app[:height]/2.0,
(f +
segment_width), b + app[:height]/2.0
end
end
=== END

I used Shoes to display the result of the algorithm, It was my first
attempt
with this
framework, so if someone can help me to improve the style pleas suggest
:smiley:

Sandro

(attached a screenshot of the program’s output)

3

On Fri, Mar 20, 2009 at 10:30 AM, Daniel M. [email protected]
wrote:

Midpoint Displacement (#197)

Here’s my version. Starts with a flat line and displaces the
midpoint(s) iteratively. Iteration method takes a block so that
calling code can decide what to do with the information. In this
implementation I dump iteration info to the console and create some
pictures.

The bulk of the code is specific to RMagick and does per frame GIFs as
an animated one of the whole sequence.

Sample image at: http://www.above-average-software.com/img/line_anim.gif

#!/usr/bin/ruby -w

require ‘RMagick’

def get_displaced_midpoint(left, right, range)
mid = (left + right) / 2.0
adj = (rand * range) * (0 == rand(2) ? -1 : 1)
return mid + adj
end

def displace_line(line, range)
offset = 1
0.upto(line.length - 2) do |x|
line.insert(x + offset, get_displaced_midpoint(line[x + offset -
1], line[x + offset], range))
offset += 1
end
return line
end

def draw_line(iter, line, range, width, height, anim_list)
drawing = Magick::Draw.new
x_factor = width / (line.count - 1)
0.upto(line.count - 2) do |x|
drawing.line x_factor * x, (height/2) - (height * line[x] / 2),
x_factor * (x + 1), (height / 2) - (height * line[x + 1] / 2)
end
drawing.stroke(“transparent”)
drawing.fill(“black”)
drawing.text(4, 16, “Iteration #{iter}, Range +/- #{range}”)

img = Magick::Image.new(width, height,
Magick::HatchFill.new(‘white’, ‘lightcyan2’))
drawing.draw(img)
img.write(“line_img_#{‘%03d’ % iter}.gif”)
anim_list << img.copy
end

def print_line(iter, line, range)
puts “iteration #{iter} (range=#{range}): #{line.inspect}”
end

def perform_iterations(line, iterations, range, roughness)
1.upto(iterations) do |i|
line = displace_line(line, range)
yield(i, line, range)
range *= 2 ** (0 - roughness)
end
end

anim = Magick::ImageList.new

TODO: parse command line for options

width = 512
height = 512
roughness = 1.0

set iterations to be enough to get “full resolution” for image but no

higher
iterations = (Math.log(width) / Math.log(2)).to_i

perform_iterations([0.0, 0.0], iterations, 0.5, roughness){|iter, line,
range|
draw_line(iter, line, range, width, height, anim)
print_line(iter, line, range)
}

anim.delay = 100
anim.cur_image.delay = 300
anim.iterations = 0
anim.write(“line_anim.gif”)

4

Di Mo wrote:

Midpoint Displacement (#197)

My solution utilizes Builder to print a SVG representation to stdout.
Note that the enum_for(:each_cons, 2) construct could be replaced by a
simple each_cons(2) when running Ruby 1.8.7 or 1.9.x.

#!/usr/bin/env ruby

require ‘rubygems’
require ‘builder’
require ‘enumerator’

Options

max_offset = 0.5
roughness = 0.5
iterations = 12
width = height = 100
style = “fill: black; stroke: none”

Midpoint displacement

heights = [0.0, 0.0]
iterations.times do
heights = heights.enum_for(:each_cons, 2).map do |left, right|
mid = (left + right) / 2
mid += (rand * 2 - 1) * max_offset
[left, mid]
end.flatten << heights[-1]
max_offset *= roughness
end

SVG output

builder = Builder::XmlMarkup.new(:target => STDOUT)
builder.instruct!
builder.svg(:version => “1.1”, :width => width, :height => height) do
|svg|
xs = (0…heights.size).map {|x| x.to_f / (heights.size - 1) *
width}
ys = heights.map {|y| (1 - y) * height * 0.5}
points = [0, height] + xs.zip(ys) + [width, height]
svg.polyline(:style => style, :points => points.join(" "))
end

-Matthias

5

This week’s quiz received several interesting solutions. Summary also
available at http://rubyquiz.strd6.com/quizzes/197/#summary

Sandro’s solution uses the Shoes graphical toolkit. I hadn’t
played around with Shoes before, but it is basically awesome. It is
very simple to get going and well worth exploring.

Here is the entire display logic for Sandro’s App:

Shoes.app(:title=>'Dreaming mountains', :resizable=>false,

:width=>app[:width], :height=>app[:height]) do
stroke white
strokewidth 2
background black

  segments.each_with_index do |b,i|
    next if i == 0; a = segments[i-1]
    line (f = (segment_width*(i-1) + boundary)), a +

app[:height]/2.0, (f + segment_width), b + app[:height]/2.0
end
end

After setting up a few application parameters and creating the height
values it is super easy to display the segments, and makes a cool
looking screenshot:

Dreaming Mountains

Michael L. provided a solution using RMagick that generates an
animated gif of the whole process as well as each step. This clearly
illustrates the algorithm in action; it’s neat to see how it
progresses at each step.

Midpoint Displacement Animation

Michael uses some clever techniques to pack a thorough solution into a
small amount of code. The perform_iterations method accepts a block
which it uses to pass the current state of the simulation back, to
make it easy to capture the output on every step. Another cool
technique is using the width of the image to determine how many
iterations to run, with the idea being that once we get to sub-pixel
midpoints it is ok to stop.

# set iterations to be enough to get "full resolution" for image

but no higher
iterations = (Math.log(width) / Math.log(2)).to_i

Matthias’s solution has some useful techniques as well, such as using
of the :each_cons enumerator. This yields consecutive elements in
the array, for example:

>> [1, 2, 3].enum_for(:each_cons, 2).to_a
=> [[1, 2], [2, 3]]

This makes mapping inserting the midpoints a little easier, observe:

# Midpoint displacement
heights = [0.0, 0.0]
iterations.times do
  heights = heights.enum_for(:each_cons, 2).map do |left, right|
    mid = (left + right) / 2
    mid += (rand * 2 - 1) * max_offset
    [left, mid]
  end.flatten << heights[-1]
  max_offset *= roughness
end

The last height is appended to the end because it would otherwise be
lost and replaced by a midpoint.

Matthias’ solutions output is in SVG format using builder to create
the xml.

Matthias Mountains

There are useful bits that can be learned from each solution. So
please check them all out on the mailing list. Additionally the output
strategies of Shoe’s, RMagick, and SVG demonstrate what great options
we have in Ruby.

Thank you Sandro, Michael, and Matthias for your solutions this week!
Keep 'em coming!

– Daniel
http://rubyquiz.strd6.com