198 Diamond-Square

Description

Guten Tag Rubyists,

Following in the same vein as last week’s quiz I present to you the diamond-square algorithm. Instead of one dimensional terrain as last week, the random terrain generated by this algorithm is in two dimensions. Visual displays are again encouraged.

The secret to this algorithm is that there are two phases for generating the new random values: from the diagonals (diamond) and from the adjacents (square). This makes the generated terrain smoother and prevents artifacts from generating solely by the adjacents.

Once equipped with these terrain generation algorithms, making ruby based Elf/Goblin/Tanks simulations will be a breeze!

There is now a suggestion form! I’m looking forward to all of your great suggestions!

Summary

Since there were no solutions submitted on the mailing list this week I’ve included a solution of my own.

class DiamondSquare
  def self.rando
    rand() - 0.5
  end
  
  def self.go(times)
    arrays = [[0.5]]
    
    ratio = 2
    
    times.times do
      arrays.map! do |array|
        insert_nils(array)
      end
      arrays = insert_arrays(arrays)
      compute_from_diagonals(arrays) {|a, b, c, d| (a + b + c + d)/4 + rando*ratio} 
      compute_from_adjacents(arrays) {|a, b, c, d| (a + b + c + d)/4 + rando*ratio}
      ratio *= 0.5
    end
    
    return arrays
  end
  
  def self.insert_arrays(arrays)
    new_arrays = []
    arrays.size.times do |i|
      array = arrays[i]
      new_arrays.push array, Array.new(array.size, 0.0)
    end
    return new_arrays
  end
  
  def self.insert_nils(array)
    new_array = []
    array.size.times do |i|
      new_array.push(array[i], 0.0)
    end
    return new_array
  end
  
  def self.compute_from_adjacents(arrays)
    n = arrays.size
    n.times do |row|
      n.times do |col|
        next if (row + col) % 2 == 0
        arrays[row][col] = 
          yield(arrays[(row-1)%n][col], arrays[row][(col-1)%n],
                arrays[row][(col+1)%n], arrays[(row+1)%n][col])
      end
    end
  end
  
  def self.compute_from_diagonals(arrays)
    n = arrays.size
    n.times do |row|
      next if row % 2 == 0
      n.times do |col|
        next if col % 2 == 0
        arrays[row][col] = 
          yield(arrays[(row-1)%n][(col-1)%n], arrays[(row-1)%n][(col+1)%n],
                arrays[(row+1)%n][(col-1)%n], arrays[(row+1)%n][(col+1)%n])
      end
    end
  end
  
  def self.print_arrays(arrays)
    i = 0
    arrays.each do |array|
      print "%4d: " % i
      array.each do |ele|
        print '%1.3f ' % ele
      end
      i += 1
      puts
    end
    puts '---------------------------------------'
  end
end

I actually wrote it almost a year ago to generate the terrain for Dungeon Farmer. It’s kind of clunky, but it has its merits. Some of the interesting things about this solution are that rather than start with a full sized array it starts with a small array (very small actually, 1x1) and inserts empty elements to be filled in before each step. This causes the array to double in width and height at each iteration.

The compute_from_diagonals and compute_from_adjacents methods yield the four adjacent or diagonal cells so that you can easily change the nature of the computation. The cells wrap around in a toroidal manner to make it easy to compute the values on the edges.

It was fun to make and I hope you find it interesting!

Sunday, March 29, 2009