cylinder_height_map.coffee

# Original code: https://github.com/baxter/csterrain/blob/master/src/generate_terrain.coffee
#
#
# Generate realistic looking terrain using the [diamond square algorithm](http://en.wikipedia.org/wiki/Diamond-square_algorithm).
#
#### Generating a height map

# The height map is basically an array of numbers, each element represents
# a point on a map and each number represents the height of that grid.
class @HeightMap

  # Initialise the height map with a `size` whose upper bound is inclusive (32 means an array of 33 items).
  # Call the `reset` function to put the height_map into a state that is ready
  # for terrain generation.
  constructor: (size, options = {}) ->
    @low_value   = options.low_value ? 0
    @high_value  = options.high_value ? 255
    @variability = options.variability ? 0.75
    @mid_value   = Math.floor((@low_value + @high_value) / 2)
    @size        = { width: size.width, height: size.height }
    @reset()
    @at = @get_cell

  # Pop any remaining objects from the operation queue and discard them.
  # Create an empty 2D array, size × size,
  # Set all the corner points to the mid value.
  # Push a new object to the queue for the first diamond square step.
  reset: =>
    @map = for y in [0..@size.height]
      null for x in [0...@size.width]

    @set_cell 0, 0, @mid_value
    @set_cell 0, @size.height, @mid_value

  # Get the value of the point at [x, y].
  get_cell: (x, y) ->
    x = 0 if x is @size.width
    @map[y][x]

  # Set the value of the point at [x, y] to be v.
  set_cell: (x, y, v) ->
    x = 0 if x is @size.width
    @map[y][x] = v

  # Set the value of the cell at [x, y] to be v, but only if it isn't already set.
  # This is useful when we recurse, since some adjacent points might already
  # have a value set and I'd rather preserve them.
  soft_set_cell: (x, y, v) ->
    x = 0 if x is @size.width
    @map[y][x] ||= v

  # Keep calling step() until there's nothing left in the queue.
  run: ->
    @diamond_square 0, 0, @size.width, @size.height, @mid_value

  # The diamond square algorithm works on a particular region in 2 steps:
  diamond_square: (left, top, right, bottom, base_height) ->
    x_centre = Math.floor (left + right) / 2
    y_centre = Math.floor (top + bottom) / 2

    # * The **diamond** step populates the centre point by averaging the
    # values at the four corners and adding or subtracting a random amount
    # of noise.

    centre_point_value = Math.floor (
      (
        @get_cell(left, top) +
        @get_cell(right, top) +
        @get_cell(left, bottom) +
        @get_cell(right, bottom)
      ) / 4
    ) - (Math.floor (Math.random() - 0.5) * base_height * 2)

    @soft_set_cell(x_centre, y_centre, centre_point_value)

    # * The **square** step populates the North, South, East and West points
    # by averaging the North West and North East values, the South East and
    # South East values, etc.

    @soft_set_cell(x_centre, top,      Math.floor (@get_cell(left,  top)    + @get_cell(right, top)   ) / 2 + ((Math.random() - 0.5) * base_height))
    @soft_set_cell(x_centre, bottom,   Math.floor (@get_cell(left,  bottom) + @get_cell(right, bottom)) / 2 + ((Math.random() - 0.5) * base_height))
    @soft_set_cell(left,     y_centre, Math.floor (@get_cell(left,  top)    + @get_cell(left,  bottom)) / 2 + ((Math.random() - 0.5) * base_height))
    @soft_set_cell(right,    y_centre, Math.floor (@get_cell(right, top)    + @get_cell(right, bottom)) / 2 + ((Math.random() - 0.5) * base_height))

    # Once the centre point and the four side points are populated then,
    # provided there are no smaller regions left, split the current region
    # into four smaller regions and perform the diamond square algorithm
    # on them.
    if (right - left) > 2
      base_height = Math.floor base_height * Math.pow 2.0, -@variability

      @diamond_square left,     top,      x_centre, y_centre, base_height
      @diamond_square x_centre, top,      right,    y_centre, base_height
      @diamond_square left,     y_centre, x_centre, bottom,   base_height
      @diamond_square x_centre, y_centre, right,    bottom,   base_height