# Midpoint Displacement (#197)

**URL:** <https://www.ruby-forum.com/t/midpoint-displacement-197/163461>\
**Category:** Ruby\
**Created:** [March 20, 2009, 4:34pm UTC](https://www.ruby-forum.com/t/midpoint-displacement-197/163461 "2009-03-20T16:34:25Z")\
**Posts on this page:** 5\
**Page:** 1

<div class="post-metadata">

**Author:** ![danmcb](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/d/13edae/32.png) [@danmcb](https://www.ruby-forum.com/u/danmcb)\
**Post date:** [March 20, 2009, 4:34pm UTC](https://www.ruby-forum.com/t/midpoint-displacement-197/163461/1 "2009-03-20T16:34:25Z")

</div>

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

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](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](http://gameprogrammer.com/fractal.html#midpoint) 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.

---

<div class="post-metadata">

**Author:** ![danmcb](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/d/13edae/32.png) [@danmcb](https://www.ruby-forum.com/u/danmcb)\
**Post date:** [March 22, 2009, 8:00pm UTC](https://www.ruby-forum.com/t/midpoint-displacement-197/163461/2 "2009-03-22T20:00:02Z")

</div>

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  
😃

Sandro

(attached a screenshot of the program’s output)

---

<div class="post-metadata">

**Author:** ![danmcb](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/d/13edae/32.png) [@danmcb](https://www.ruby-forum.com/u/danmcb)\
**Post date:** [March 24, 2009, 5:24pm UTC](https://www.ruby-forum.com/t/midpoint-displacement-197/163461/3 "2009-03-24T17:24:18Z")

</div>

On Fri, Mar 20, 2009 at 10:30 AM, Daniel M. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid)  
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](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”)

---

<div class="post-metadata">

**Author:** ![danmcb](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/d/13edae/32.png) [@danmcb](https://www.ruby-forum.com/u/danmcb)\
**Post date:** [March 24, 2009, 11:07pm UTC](https://www.ruby-forum.com/t/midpoint-displacement-197/163461/4 "2009-03-24T23:07:44Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![danmcb](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/d/13edae/32.png) [@danmcb](https://www.ruby-forum.com/u/danmcb)\
**Post date:** [March 30, 2009, 12:06am UTC](https://www.ruby-forum.com/t/midpoint-displacement-197/163461/5 "2009-03-30T00:06:11Z")

</div>

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

Sandro’s solution uses the [Shoes](http://shoooes.net/about/) 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](http://rubyquiz.strd6.com/quizzes/197/dreaming_mountains.png)

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](http://rubyquiz.strd6.com/quizzes/197/line_anim.gif)

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](http://rubyquiz.strd6.com/quizzes/197/matthias_mountains.png)

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](http://rubyquiz.strd6.com)