197 Midpoint Displacement


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.


This week’s quiz received several interesting solutions.

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

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 Libby 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

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!

Wednesday, March 25, 2009