Thomas Schneider    Archive    Feed    Github

Tiny Voronoi-diagram-based map generator in CoffeeScript and ClojureScript

This actually was my Recurse Center pair programming interview project.

Like this polished generator, it generates a Voronoi diagram, applies Lyoid’s relaxation then generates a map based on cells except:

  • it uses the naive bitmap approach instead of using a Fortune algorithm implementation
  • thus it doesn’t have features based on Delaunay-relaxation!
  • it’s written from scratch in Coffee and Clojure script instead of Flash

Number of cells:

Original CoffeeScript:

rand_int = (upper_bound) -> Math.floor(Math.random() * upper_bound)


euclidian_distance = (p1, p2) ->
    Math.sqrt (p2.x - p1.x) ** 2 + (p2.y - p1.y) ** 2


voronoi_bitmap = (sites, height, width) ->
    [1..height].map (row) ->
        [1..width].map (column) ->
            pixel = {x: row, y: column}
            distances = (euclidian_distance(pixel, site) for site in sites)

            distances.indexOf(Math.min.apply(@, distances))


centroids = (bitmap) ->
    counts = []
    for row in [0..bitmap.length - 1]
        for column in [0..bitmap[row].length - 1]
            current_cell = bitmap[row][column]
            counts[current_cell] ||= {sumx: 0, sumy: 0, n: 0}
            counts[current_cell].sumx += row
            counts[current_cell].sumy += column
            counts[current_cell].n += 1

    counts.map (cell_count) -> {
        x: cell_count.sumx / cell_count.n,
        y: cell_count.sumy / cell_count.n
    }

lyoid_relaxation = (bitmap, iterations=1) ->
    heigth = bitmap.length
    width = bitmap[0].length

    for i in [1..iterations]
        bitmap = voronoi_bitmap(centroids(bitmap), width, heigth)

    bitmap


neighbors = (bitmap, ncells) ->
    graph = ([] for i in [1..ncells])

    for row in [0..bitmap.length - 2]
        for column in [0..bitmap[row].length - 2]
            current_cell = bitmap[row][column]

            for neighbor_cell in [bitmap[row+1][column], bitmap[row][column+1]]
                if current_cell isnt neighbor_cell and neighbor_cell not in graph[current_cell]
                    graph[current_cell].push(neighbor_cell)
                    graph[neighbor_cell].push(current_cell)

    graph


cell_distances_from = (peak, graph) ->
    distances = []
    distance_from_peak = 0
    current_level = [peak]

    while current_level.length > 0
        for cell in current_level
            distances[cell] = distance_from_peak

        next_level = []
        for cell in current_level
            for neighbor in graph[cell] when distances[neighbor] is undefined and neighbor not in next_level
                next_level.push(neighbor)

        current_level = next_level
        distance_from_peak += 1

    distances
        
        
draw_bitmap = (bitmap, colors, canvas_id) ->
    heigth = bitmap.length
    width = bitmap[0].length
    canvas = document.getElementById(canvas_id)
    canvas.width = width
    canvas.heigth = heigth
    ctx = canvas.getContext("2d")
    image_data = ctx.createImageData(width, heigth)

    for row in [0..heigth-1]
        for column in [0..width-1]
            pixel_number = row * width + column
            color = colors[bitmap[row][column]]
            #image_data.data[pixel_number*4..pixel_number*4 + 3] = color
            for i in [0..3]
                image_data.data[pixel_number*4+i] = color[i]
    
    ctx.putImageData(image_data, 0, 0)


HEIGHT = WIDTH = 500

document.getElementById('go').onclick = ->
    ncells = parseInt(document.getElementById('ncells').value)
    #draw a random voronoi diagram on #random_voronoi_diagram
    random_points = ({x: rand_int(HEIGHT), y:rand_int(WIDTH)} for i in [1..ncells])
    random_bitmap = voronoi_bitmap(random_points, HEIGHT, WIDTH)

    random_colors = ([rand_int(255), rand_int(255), rand_int(255), 255] for i in [1..ncells])
    draw_bitmap(random_bitmap, random_colors, 'random_voronoi_diagram')


    relaxed_bitmap = lyoid_relaxation(random_bitmap, 3)

    graph = neighbors(relaxed_bitmap, ncells)

    distances = cell_distances_from(relaxed_bitmap[HEIGHT/2][WIDTH/2], graph)

    altitude_gradient = ([0, i * 51, 0, 255] for i in [0..5])
    colors = distances.map (distance) ->
        altitude_gradient[distance] or [0,0,255,255] #sea if distance > 5

    draw_bitmap(relaxed_bitmap, colors, 'round_island')

Less advanced ClojureScript:

(defrecord Point [x y])
(def elem (.-getElementById js/document))
(defn rand-int [max] (js/parseInt (rand max)))
(defn double-map [double-array function]
(map (fn [simple-array] (map function simple-array))))

(defn euclidian-distance [p1 p2]
  (let [[dx (- (:x p2) (:x p1))]
        [dy (- (:y p2) (:y p1))]]
    (Math/sqrt (+ (* dx dx) (* dy dy)))))


(defn voronoi-bitmap [sites height width]
  (for [row (range 0 (- height 1))
        height (range 0 (- width 1))]
     (let [[current-pixel (Point. row height)]
           [distances (vector (map sites #(euclidian-distance current-pixel %)))]]
       (.indexOf distances (min distances)))))

(defn draw-bitmap [bitmap colors width height canvas-id]
    (.putImageData
      (.getContext (elem canvas-id) "2d")
      (js/Uint8Array. (flatten
        (double-map
          (fn [cell-number] (nth colors cell-number))
          bitmap)))))

(set! (.-onclick (elem "go")) #(
  (let [[ncells (.value (elem "ncells-input"))]
        [random-points (for [i (range 1 ncells)] (Point. (rand-int height) (rand-int width)))]
        [random-colors (for [i (range 1 ncells)] [(rand-int 255) (rand-int 255) (rand-int 255) 255])]]
    (draw-bitmap
      (voronoi-bitmap random-points random-colors 500 500 "random_voronoi_diagram")
      "random_voronoi_diagram"))
))