# 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

dsquare = new HeightMap(width: 64, height: 64)
dsquare.run()
# return an height value
generateHeight = (x, y) ->
  dsquare.get_cell Math.round(x / 2), Math.round(y / 2)

# builds a tile map with the given width and height sizes
buildTileMap = (width, height) ->
  tileMap = new Array(width)
  for y in [0...width]
    tileMap[y] = new Array(height)
    for x in [0...height]
      tileMap[y][x] = generateHeight(x, y)
  tileMap
  
drawTile = (ctx, point, size) ->
  ctx.beginPath()
  [x1, y1] = [point.x * size.w, point.y * size.h]
  [x2, y2] = [x1 + size.w, y1 + size.h]
  ctx.moveTo x1, y1
  ctx.lineTo x2, y1
  ctx.lineTo x2, y2
  ctx.lineTo x1, y2
  ctx.lineTo x1, y1
  ctx.closePath()

$ ->
  scene = document.createElement 'canvas'
  scene.width = scene.height = 512
  # build a tile map.
  # Tilemap size is the half of the canvas size
  map = buildTileMap 128, 128
  ctx = scene.getContext '2d'
  
  tileSize = 
    w: scene.width / map.length
    h: scene.height / map[0].length

  # draw a 2px circle for each tilemap location
  for y in [0...map.length]
    for height, x in map[y]
      ctx.fillStyle = ctx.strokeStyle = "rgb(#{height},#{height},#{height})"
      drawTile(ctx, { x, y }, tileSize)
      ctx.stroke()
      ctx.fill()

  document.body.appendChild scene