From: Daniel Moore <yahivin@...>
Date: 2009-04-06T13:23:49+09:00
Subject: [QUIZ][SUMMARY] Diamond-Square (#198)

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][1]. 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!

[1]: http://code.google.com/p/strd6/wiki/DungeonFarmer

-- 
-Daniel
http://rubyquiz.strd6.com