Tiny Voronoi-diagram-based map generator in CoffeeScript and ClojureScript
Dec 26, 2014
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"))
))