terrain.js

'use strict';

function runif(lo, hi) {
  return lo + Math.random() * (hi - lo);
}

var rnorm = (function() {
  var z2 = null;
  function rnorm() {
    if (z2 != null) {
      var tmp = z2;
      z2 = null;
      return tmp;
    }
    var x1 = 0;
    var x2 = 0;
    var w = 2.0;
    while (w >= 1) {
      x1 = runif(-1, 1);
      x2 = runif(-1, 1);
      w = x1 * x1 + x2 * x2;
    }
    w = Math.sqrt((-2 * Math.log(w)) / w);
    z2 = x2 * w;
    return x1 * w;
  }
  return rnorm;
})();

function randomVector(scale) {
  return [scale * rnorm(), scale * rnorm()];
}

var defaultExtent = {
  width: 1,
  height: 1,
};

function generatePoints(n, extent) {
  extent = extent || defaultExtent;
  var pts = [];
  for (var i = 0; i < n; i++) {
    pts.push([
      (Math.random() - 0.5) * extent.width,
      (Math.random() - 0.5) * extent.height,
    ]);
  }
  return pts;
}

function centroid(pts) {
  var x = 0;
  var y = 0;
  for (var i = 0; i < pts.length; i++) {
    x += pts[i][0];
    y += pts[i][1];
  }
  return [x / pts.length, y / pts.length];
}

function improvePoints(pts, n, extent) {
  n = n || 1;
  extent = extent || defaultExtent;
  for (var i = 0; i < n; i++) {
    pts = voronoi(pts, extent)
      .polygons(pts)
      .map(centroid);
  }
  return pts;
}

function generateGoodPoints(n, extent) {
  extent = extent || defaultExtent;
  var pts = generatePoints(n, extent);
  pts = pts.sort(function(a, b) {
    return a[0] - b[0];
  });
  return improvePoints(pts, 1, extent);
}

function voronoi(pts, extent) {
  extent = extent || defaultExtent;
  var w = extent.width / 2;
  var h = extent.height / 2;
  return d3.voronoi().extent([
    [-w, -h],
    [w, h],
  ])(pts);
}

function makeMesh(pts, extent) {
  extent = extent || defaultExtent;
  var vor = voronoi(pts, extent);
  var vxs = [];
  var vxids = {};
  var adj = [];
  var edges = [];
  var tris = [];
  for (var i = 0; i < vor.edges.length; i++) {
    var e = vor.edges[i];
    if (e == undefined) continue;
    var e0 = vxids[e[0]];
    var e1 = vxids[e[1]];
    if (e0 == undefined) {
      e0 = vxs.length;
      vxids[e[0]] = e0;
      vxs.push(e[0]);
    }
    if (e1 == undefined) {
      e1 = vxs.length;
      vxids[e[1]] = e1;
      vxs.push(e[1]);
    }
    adj[e0] = adj[e0] || [];
    adj[e0].push(e1);
    adj[e1] = adj[e1] || [];
    adj[e1].push(e0);
    edges.push([e0, e1, e.left, e.right]);
    tris[e0] = tris[e0] || [];
    if (!tris[e0].includes(e.left)) tris[e0].push(e.left);
    if (e.right && !tris[e0].includes(e.right)) tris[e0].push(e.right);
    tris[e1] = tris[e1] || [];
    if (!tris[e1].includes(e.left)) tris[e1].push(e.left);
    if (e.right && !tris[e1].includes(e.right)) tris[e1].push(e.right);
  }

  var mesh = {
    pts: pts,
    vor: vor,
    vxs: vxs,
    adj: adj,
    tris: tris,
    edges: edges,
    extent: extent,
  };
  mesh.map = function(f) {
    var mapped = vxs.map(f);
    mapped.mesh = mesh;
    return mapped;
  };
  return mesh;
}

function generateGoodMesh(n, extent) {
  extent = extent || defaultExtent;
  var pts = generateGoodPoints(n, extent);
  return makeMesh(pts, extent);
}
function isedge(mesh, i) {
  return mesh.adj[i].length < 3;
}

function isnearedge(mesh, i) {
  var x = mesh.vxs[i][0];
  var y = mesh.vxs[i][1];
  var w = mesh.extent.width;
  var h = mesh.extent.height;
  return x < -0.45 * w || x > 0.45 * w || y < -0.45 * h || y > 0.45 * h;
}

function neighbours(mesh, i) {
  var onbs = mesh.adj[i];
  var nbs = [];
  for (var i = 0; i < onbs.length; i++) {
    nbs.push(onbs[i]);
  }
  return nbs;
}

function distance(mesh, i, j) {
  var p = mesh.vxs[i];
  var q = mesh.vxs[j];
  return Math.sqrt(
    (p[0] - q[0]) * (p[0] - q[0]) + (p[1] - q[1]) * (p[1] - q[1])
  );
}

function quantile(h, q) {
  var sortedh = [];
  for (var i = 0; i < h.length; i++) {
    sortedh[i] = h[i];
  }
  sortedh.sort(d3.ascending);
  return d3.quantile(sortedh, q);
}

function zero(mesh) {
  var z = [];
  for (var i = 0; i < mesh.vxs.length; i++) {
    z[i] = 0;
  }
  z.mesh = mesh;
  return z;
}

function slope(mesh, direction) {
  return mesh.map(function(x) {
    return x[0] * direction[0] + x[1] * direction[1];
  });
}

function cone(mesh, slope) {
  return mesh.map(function(x) {
    return Math.pow(x[0] * x[0] + x[1] * x[1], 0.5) * slope;
  });
}

function map(h, f) {
  var newh = h.map(f);
  newh.mesh = h.mesh;
  return newh;
}

function normalize(h) {
  var lo = d3.min(h);
  var hi = d3.max(h);
  return map(h, function(x) {
    return (x - lo) / (hi - lo);
  });
}

function peaky(h) {
  return map(normalize(h), Math.sqrt);
}

function add() {
  var n = arguments[0].length;
  var newvals = zero(arguments[0].mesh);
  for (var i = 0; i < n; i++) {
    for (var j = 0; j < arguments.length; j++) {
      newvals[i] += arguments[j][i];
    }
  }
  return newvals;
}

function mountains(mesh, n, r) {
  r = r || 0.05;
  var mounts = [];
  for (var i = 0; i < n; i++) {
    mounts.push([
      mesh.extent.width * (Math.random() - 0.5),
      mesh.extent.height * (Math.random() - 0.5),
    ]);
  }
  var newvals = zero(mesh);
  for (var i = 0; i < mesh.vxs.length; i++) {
    var p = mesh.vxs[i];
    for (var j = 0; j < n; j++) {
      var m = mounts[j];
      newvals[i] += Math.pow(
        Math.exp(
          -((p[0] - m[0]) * (p[0] - m[0]) + (p[1] - m[1]) * (p[1] - m[1])) /
            (2 * r * r)
        ),
        2
      );
    }
  }
  return newvals;
}

function relax(h) {
  var newh = zero(h.mesh);
  for (var i = 0; i < h.length; i++) {
    var nbs = neighbours(h.mesh, i);
    if (nbs.length < 3) {
      newh[i] = 0;
      continue;
    }
    newh[i] = d3.mean(
      nbs.map(function(j) {
        return h[j];
      })
    );
  }
  return newh;
}

function downhill(h) {
  if (h.downhill) return h.downhill;
  function downfrom(i) {
    if (isedge(h.mesh, i)) return -2;
    var best = -1;
    var besth = h[i];
    var nbs = neighbours(h.mesh, i);
    for (var j = 0; j < nbs.length; j++) {
      if (h[nbs[j]] < besth) {
        besth = h[nbs[j]];
        best = nbs[j];
      }
    }
    return best;
  }
  var downs = [];
  for (var i = 0; i < h.length; i++) {
    downs[i] = downfrom(i);
  }
  h.downhill = downs;
  return downs;
}

function findSinks(h) {
  var dh = downhill(h);
  var sinks = [];
  for (var i = 0; i < dh.length; i++) {
    var node = i;
    while (true) {
      if (isedge(h.mesh, node)) {
        sinks[i] = -2;
        break;
      }
      if (dh[node] == -1) {
        sinks[i] = node;
        break;
      }
      node = dh[node];
    }
  }
}

function fillSinks(h, epsilon) {
  epsilon = epsilon || 1e-5;
  var infinity = 999999;
  var newh = zero(h.mesh);
  for (var i = 0; i < h.length; i++) {
    if (isnearedge(h.mesh, i)) {
      newh[i] = h[i];
    } else {
      newh[i] = infinity;
    }
  }
  while (true) {
    var changed = false;
    for (var i = 0; i < h.length; i++) {
      if (newh[i] == h[i]) continue;
      var nbs = neighbours(h.mesh, i);
      for (var j = 0; j < nbs.length; j++) {
        if (h[i] >= newh[nbs[j]] + epsilon) {
          newh[i] = h[i];
          changed = true;
          break;
        }
        var oh = newh[nbs[j]] + epsilon;
        if (newh[i] > oh && oh > h[i]) {
          newh[i] = oh;
          changed = true;
        }
      }
    }
    if (!changed) return newh;
  }
}

function getFlux(h) {
  var dh = downhill(h);
  var idxs = [];
  var flux = zero(h.mesh);
  for (var i = 0; i < h.length; i++) {
    idxs[i] = i;
    flux[i] = 1 / h.length;
  }
  idxs.sort(function(a, b) {
    return h[b] - h[a];
  });
  for (var i = 0; i < h.length; i++) {
    var j = idxs[i];
    if (dh[j] >= 0) {
      flux[dh[j]] += flux[j];
    }
  }
  return flux;
}

function getSlope(h) {
  var dh = downhill(h);
  var slope = zero(h.mesh);
  for (var i = 0; i < h.length; i++) {
    var s = trislope(h, i);
    slope[i] = Math.sqrt(s[0] * s[0] + s[1] * s[1]);
    continue;
    if (dh[i] < 0) {
      slope[i] = 0;
    } else {
      slope[i] = (h[i] - h[dh[i]]) / distance(h.mesh, i, dh[i]);
    }
  }
  return slope;
}

function erosionRate(h) {
  var flux = getFlux(h);
  var slope = getSlope(h);
  var newh = zero(h.mesh);
  for (var i = 0; i < h.length; i++) {
    var river = Math.sqrt(flux[i]) * slope[i];
    var creep = slope[i] * slope[i];
    var total = 1000 * river + creep;
    total = total > 200 ? 200 : total;
    newh[i] = total;
  }
  return newh;
}

function erode(h, amount) {
  var er = erosionRate(h);
  var newh = zero(h.mesh);
  var maxr = d3.max(er);
  for (var i = 0; i < h.length; i++) {
    newh[i] = h[i] - amount * (er[i] / maxr);
  }
  return newh;
}

function doErosion(h, amount, n) {
  n = n || 1;
  h = fillSinks(h);
  for (var i = 0; i < n; i++) {
    h = erode(h, amount);
    h = fillSinks(h);
  }
  return h;
}

function setSeaLevel(h, q) {
  var newh = zero(h.mesh);
  var delta = quantile(h, q);
  for (var i = 0; i < h.length; i++) {
    newh[i] = h[i] - delta;
  }
  return newh;
}

function cleanCoast(h, iters) {
  for (var iter = 0; iter < iters; iter++) {
    var changed = 0;
    var newh = zero(h.mesh);
    for (var i = 0; i < h.length; i++) {
      newh[i] = h[i];
      var nbs = neighbours(h.mesh, i);
      if (h[i] <= 0 || nbs.length != 3) continue;
      var count = 0;
      var best = -999999;
      for (var j = 0; j < nbs.length; j++) {
        if (h[nbs[j]] > 0) {
          count++;
        } else if (h[nbs[j]] > best) {
          best = h[nbs[j]];
        }
      }
      if (count > 1) continue;
      newh[i] = best / 2;
      changed++;
    }
    h = newh;
    newh = zero(h.mesh);
    for (var i = 0; i < h.length; i++) {
      newh[i] = h[i];
      var nbs = neighbours(h.mesh, i);
      if (h[i] > 0 || nbs.length != 3) continue;
      var count = 0;
      var best = 999999;
      for (var j = 0; j < nbs.length; j++) {
        if (h[nbs[j]] <= 0) {
          count++;
        } else if (h[nbs[j]] < best) {
          best = h[nbs[j]];
        }
      }
      if (count > 1) continue;
      newh[i] = best / 2;
      changed++;
    }
    h = newh;
  }
  return h;
}

function trislope(h, i) {
  var nbs = neighbours(h.mesh, i);
  if (nbs.length != 3) return [0, 0];
  var p0 = h.mesh.vxs[nbs[0]];
  var p1 = h.mesh.vxs[nbs[1]];
  var p2 = h.mesh.vxs[nbs[2]];

  var x1 = p1[0] - p0[0];
  var x2 = p2[0] - p0[0];
  var y1 = p1[1] - p0[1];
  var y2 = p2[1] - p0[1];

  var det = x1 * y2 - x2 * y1;
  var h1 = h[nbs[1]] - h[nbs[0]];
  var h2 = h[nbs[2]] - h[nbs[0]];

  return [(y2 * h1 - y1 * h2) / det, (-x2 * h1 + x1 * h2) / det];
}

function cityScore(h, cities) {
  var score = map(getFlux(h), Math.sqrt);
  for (var i = 0; i < h.length; i++) {
    if (h[i] <= 0 || isnearedge(h.mesh, i)) {
      score[i] = -999999;
      continue;
    }
    score[i] +=
      0.01 / (1e-9 + Math.abs(h.mesh.vxs[i][0]) - h.mesh.extent.width / 2);
    score[i] +=
      0.01 / (1e-9 + Math.abs(h.mesh.vxs[i][1]) - h.mesh.extent.height / 2);
    for (var j = 0; j < cities.length; j++) {
      score[i] -= 0.02 / (distance(h.mesh, cities[j], i) + 1e-9);
    }
  }
  return score;
}
function placeCity(render) {
  render.cities = render.cities || [];
  var score = cityScore(render.h, render.cities);
  var newcity = d3.scan(score, d3.descending);
  render.cities.push(newcity);
}

function placeCities(render) {
  var params = render.params;
  var h = render.h;
  var n = params.ncities;
  for (var i = 0; i < n; i++) {
    placeCity(render);
  }
}

function contour(h, level) {
  level = level || 0;
  var edges = [];
  for (var i = 0; i < h.mesh.edges.length; i++) {
    var e = h.mesh.edges[i];
    if (e[3] == undefined) continue;
    if (isnearedge(h.mesh, e[0]) || isnearedge(h.mesh, e[1])) continue;
    if (
      (h[e[0]] > level && h[e[1]] <= level) ||
      (h[e[1]] > level && h[e[0]] <= level)
    ) {
      edges.push([e[2], e[3]]);
    }
  }
  return mergeSegments(edges);
}

function getRivers(h, limit) {
  var dh = downhill(h);
  var flux = getFlux(h);
  var links = [];
  var above = 0;
  for (var i = 0; i < h.length; i++) {
    if (h[i] > 0) above++;
  }
  limit *= above / h.length;
  for (var i = 0; i < dh.length; i++) {
    if (isnearedge(h.mesh, i)) continue;
    if (flux[i] > limit && h[i] > 0 && dh[i] >= 0) {
      var up = h.mesh.vxs[i];
      var down = h.mesh.vxs[dh[i]];
      if (h[dh[i]] > 0) {
        links.push([up, down]);
      } else {
        links.push([up, [(up[0] + down[0]) / 2, (up[1] + down[1]) / 2]]);
      }
    }
  }
  return mergeSegments(links).map(relaxPath);
}

function getTerritories(render) {
  var h = render.h;
  var cities = render.cities;
  var n = render.params.nterrs;
  if (n > render.cities.length) n = render.cities.length;
  var flux = getFlux(h);
  var terr = [];
  var queue = new PriorityQueue({
    comparator: function(a, b) {
      return a.score - b.score;
    },
  });
  function weight(u, v) {
    var horiz = distance(h.mesh, u, v);
    var vert = h[v] - h[u];
    if (vert > 0) vert /= 10;
    var diff = 1 + 0.25 * Math.pow(vert / horiz, 2);
    diff += 100 * Math.sqrt(flux[u]);
    if (h[u] <= 0) diff = 100;
    if (h[u] > 0 != h[v] > 0) return 1000;
    return horiz * diff;
  }
  for (var i = 0; i < n; i++) {
    terr[cities[i]] = cities[i];
    var nbs = neighbours(h.mesh, cities[i]);
    for (var j = 0; j < nbs.length; j++) {
      queue.queue({
        score: weight(cities[i], nbs[j]),
        city: cities[i],
        vx: nbs[j],
      });
    }
  }
  while (queue.length) {
    var u = queue.dequeue();
    if (terr[u.vx] != undefined) continue;
    terr[u.vx] = u.city;
    var nbs = neighbours(h.mesh, u.vx);
    for (var i = 0; i < nbs.length; i++) {
      var v = nbs[i];
      if (terr[v] != undefined) continue;
      var newdist = weight(u.vx, v);
      queue.queue({
        score: u.score + newdist,
        city: u.city,
        vx: v,
      });
    }
  }
  terr.mesh = h.mesh;
  return terr;
}

function getBorders(render) {
  var terr = render.terr;
  var h = render.h;
  var edges = [];
  for (var i = 0; i < terr.mesh.edges.length; i++) {
    var e = terr.mesh.edges[i];
    if (e[3] == undefined) continue;
    if (isnearedge(terr.mesh, e[0]) || isnearedge(terr.mesh, e[1])) continue;
    if (h[e[0]] < 0 || h[e[1]] < 0) continue;
    if (terr[e[0]] != terr[e[1]]) {
      edges.push([e[2], e[3]]);
    }
  }
  return mergeSegments(edges).map(relaxPath);
}

function mergeSegments(segs) {
  var adj = {};
  for (var i = 0; i < segs.length; i++) {
    var seg = segs[i];
    var a0 = adj[seg[0]] || [];
    var a1 = adj[seg[1]] || [];
    a0.push(seg[1]);
    a1.push(seg[0]);
    adj[seg[0]] = a0;
    adj[seg[1]] = a1;
  }
  var done = [];
  var paths = [];
  var path = null;
  while (true) {
    if (path == null) {
      for (var i = 0; i < segs.length; i++) {
        if (done[i]) continue;
        done[i] = true;
        path = [segs[i][0], segs[i][1]];
        break;
      }
      if (path == null) break;
    }
    var changed = false;
    for (var i = 0; i < segs.length; i++) {
      if (done[i]) continue;
      if (adj[path[0]].length == 2 && segs[i][0] == path[0]) {
        path.unshift(segs[i][1]);
      } else if (adj[path[0]].length == 2 && segs[i][1] == path[0]) {
        path.unshift(segs[i][0]);
      } else if (
        adj[path[path.length - 1]].length == 2 &&
        segs[i][0] == path[path.length - 1]
      ) {
        path.push(segs[i][1]);
      } else if (
        adj[path[path.length - 1]].length == 2 &&
        segs[i][1] == path[path.length - 1]
      ) {
        path.push(segs[i][0]);
      } else {
        continue;
      }
      done[i] = true;
      changed = true;
      break;
    }
    if (!changed) {
      paths.push(path);
      path = null;
    }
  }
  return paths;
}

function relaxPath(path) {
  var newpath = [path[0]];
  for (var i = 1; i < path.length - 1; i++) {
    var newpt = [
      0.25 * path[i - 1][0] + 0.5 * path[i][0] + 0.25 * path[i + 1][0],
      0.25 * path[i - 1][1] + 0.5 * path[i][1] + 0.25 * path[i + 1][1],
    ];
    newpath.push(newpt);
  }
  newpath.push(path[path.length - 1]);
  return newpath;
}
function visualizePoints(svg, pts) {
  var circle = svg.selectAll('circle').data(pts);
  circle.enter().append('circle');
  circle.exit().remove();
  d3.selectAll('circle')
    .attr('cx', function(d) {
      return 1000 * d[0];
    })
    .attr('cy', function(d) {
      return 1000 * d[1];
    })
    .attr('r', 100 / Math.sqrt(pts.length));
}

function makeD3Path(path) {
  var p = d3.path();
  p.moveTo(1000 * path[0][0], 1000 * path[0][1]);
  for (var i = 1; i < path.length; i++) {
    p.lineTo(1000 * path[i][0], 1000 * path[i][1]);
  }
  return p.toString();
}

function visualizeVoronoi(svg, field, lo, hi) {
  if (hi == undefined) hi = d3.max(field) + 1e-9;
  if (lo == undefined) lo = d3.min(field) - 1e-9;
  var mappedvals = field.map(function(x) {
    return x > hi ? 1 : x < lo ? 0 : (x - lo) / (hi - lo);
  });
  var tris = svg.selectAll('path.field').data(field.mesh.tris);
  tris
    .enter()
    .append('path')
    .classed('field', true);

  tris.exit().remove();

  svg
    .selectAll('path.field')
    .attr('d', makeD3Path)
    .style('fill', function(d, i) {
      return d3.interpolateViridis(mappedvals[i]);
    });
}

function visualizeDownhill(h) {
  var links = getRivers(h, 0.01);
  drawPaths('river', links);
}

function drawPaths(svg, cls, paths) {
  var paths = svg.selectAll('path.' + cls).data(paths);
  paths
    .enter()
    .append('path')
    .classed(cls, true);
  paths.exit().remove();
  svg.selectAll('path.' + cls).attr('d', makeD3Path);
}

function visualizeSlopes(svg, render) {
  var h = render.h;
  var strokes = [];
  var r = 0.25 / Math.sqrt(h.length);
  for (var i = 0; i < h.length; i++) {
    if (h[i] <= 0 || isnearedge(h.mesh, i)) continue;
    var nbs = neighbours(h.mesh, i);
    nbs.push(i);
    var s = 0;
    var s2 = 0;
    for (var j = 0; j < nbs.length; j++) {
      var slopes = trislope(h, nbs[j]);
      s += slopes[0] / 10;
      s2 += slopes[1];
    }
    s /= nbs.length;
    s2 /= nbs.length;
    if (Math.abs(s) < runif(0.1, 0.4)) continue;
    var l =
      r *
      runif(1, 2) *
      (1 - 0.2 * Math.pow(Math.atan(s), 2)) *
      Math.exp(s2 / 100);
    var x = h.mesh.vxs[i][0];
    var y = h.mesh.vxs[i][1];
    if (Math.abs(l * s) > 2 * r) {
      var n = Math.floor(Math.abs((l * s) / r));
      l /= n;
      if (n > 4) n = 4;
      for (var j = 0; j < n; j++) {
        var u = rnorm() * r;
        var v = rnorm() * r;
        strokes.push([
          [x + u - l, y + v + l * s],
          [x + u + l, y + v - l * s],
        ]);
      }
    } else {
      strokes.push([
        [x - l, y + l * s],
        [x + l, y - l * s],
      ]);
    }
  }
  var lines = svg.selectAll('line.slope').data(strokes);
  lines
    .enter()
    .append('line')
    .classed('slope', true);
  lines.exit().remove();
  svg
    .selectAll('line.slope')
    .attr('x1', function(d) {
      return 1000 * d[0][0];
    })
    .attr('y1', function(d) {
      return 1000 * d[0][1];
    })
    .attr('x2', function(d) {
      return 1000 * d[1][0];
    })
    .attr('y2', function(d) {
      return 1000 * d[1][1];
    });
}

function visualizeContour(h, level) {
  level = level || 0;
  var links = contour(h, level);
  drawPaths('coast', links);
}

function visualizeBorders(h, cities, n) {
  var links = getBorders(h, getTerritories(h, cities, n));
  drawPaths('border', links);
}

function visualizeCities(svg, render) {
  var cities = render.cities;
  var h = render.h;
  var n = render.params.nterrs;

  var circs = svg.selectAll('circle.city').data(cities);
  circs
    .enter()
    .append('circle')
    .classed('city', true);
  circs.exit().remove();
  svg
    .selectAll('circle.city')
    .attr('cx', function(d) {
      return 1000 * h.mesh.vxs[d][0];
    })
    .attr('cy', function(d) {
      return 1000 * h.mesh.vxs[d][1];
    })
    .attr('r', function(d, i) {
      return i >= n ? 4 : 10;
    })
    .style('fill', 'white')
    .style('stroke-width', 5)
    .style('stroke-linecap', 'round')
    .style('stroke', 'black')
    .raise();
}

function dropEdge(h, p) {
  p = p || 4;
  var newh = zero(h.mesh);
  for (var i = 0; i < h.length; i++) {
    var v = h.mesh.vxs[i];
    var x = (2.4 * v[0]) / h.mesh.extent.width;
    var y = (2.4 * v[1]) / h.mesh.extent.height;
    newh[i] =
      h[i] -
      Math.exp(10 * (Math.pow(Math.pow(x, p) + Math.pow(y, p), 1 / p) - 1));
  }
  return newh;
}

function generateCoast(params) {
  var mesh = generateGoodMesh(params.npts, params.extent);
  var h = add(
    slope(mesh, randomVector(4)),
    cone(mesh, runif(-1, -1)),
    mountains(mesh, 50)
  );
  for (var i = 0; i < 10; i++) {
    h = relax(h);
  }
  h = peaky(h);
  h = doErosion(h, runif(0, 0.1), 5);
  h = setSeaLevel(h, runif(0.2, 0.6));
  h = fillSinks(h);
  h = cleanCoast(h, 3);
  return h;
}

function terrCenter(h, terr, city, landOnly) {
  var x = 0;
  var y = 0;
  var n = 0;
  for (var i = 0; i < terr.length; i++) {
    if (terr[i] != city) continue;
    if (landOnly && h[i] <= 0) continue;
    x += terr.mesh.vxs[i][0];
    y += terr.mesh.vxs[i][1];
    n++;
  }
  return [x / n, y / n];
}

function drawLabels(svg, render) {
  var params = render.params;
  var h = render.h;
  var terr = render.terr;
  var cities = render.cities;
  var nterrs = render.params.nterrs;
  var avoids = [render.rivers, render.coasts, render.borders];
  var lang = makeRandomLanguage();
  var citylabels = [];
  function penalty(label) {
    var pen = 0;
    if (label.x0 < -0.45 * h.mesh.extent.width) pen += 100;
    if (label.x1 > 0.45 * h.mesh.extent.width) pen += 100;
    if (label.y0 < -0.45 * h.mesh.extent.height) pen += 100;
    if (label.y1 > 0.45 * h.mesh.extent.height) pen += 100;
    for (var i = 0; i < citylabels.length; i++) {
      var olabel = citylabels[i];
      if (
        label.x0 < olabel.x1 &&
        label.x1 > olabel.x0 &&
        label.y0 < olabel.y1 &&
        label.y1 > olabel.y0
      ) {
        pen += 100;
      }
    }

    for (var i = 0; i < cities.length; i++) {
      var c = h.mesh.vxs[cities[i]];
      if (
        label.x0 < c[0] &&
        label.x1 > c[0] &&
        label.y0 < c[1] &&
        label.y1 > c[1]
      ) {
        pen += 100;
      }
    }
    for (var i = 0; i < avoids.length; i++) {
      var avoid = avoids[i];
      for (var j = 0; j < avoid.length; j++) {
        var avpath = avoid[j];
        for (var k = 0; k < avpath.length; k++) {
          var pt = avpath[k];
          if (
            pt[0] > label.x0 &&
            pt[0] < label.x1 &&
            pt[1] > label.y0 &&
            pt[1] < label.y1
          ) {
            pen++;
          }
        }
      }
    }
    return pen;
  }
  for (var i = 0; i < cities.length; i++) {
    var x = h.mesh.vxs[cities[i]][0];
    var y = h.mesh.vxs[cities[i]][1];
    var text = makeName(lang, 'city');
    var size = i < nterrs ? params.fontsizes.city : params.fontsizes.town;
    var sx = ((0.65 * size) / 1000) * text.length;
    var sy = size / 1000;
    var posslabels = [
      {
        x: x + 0.8 * sy,
        y: y + 0.3 * sy,
        align: 'start',
        x0: x + 0.7 * sy,
        y0: y - 0.6 * sy,
        x1: x + 0.7 * sy + sx,
        y1: y + 0.6 * sy,
      },
      {
        x: x - 0.8 * sy,
        y: y + 0.3 * sy,
        align: 'end',
        x0: x - 0.9 * sy - sx,
        y0: y - 0.7 * sy,
        x1: x - 0.9 * sy,
        y1: y + 0.7 * sy,
      },
      {
        x: x,
        y: y - 0.8 * sy,
        align: 'middle',
        x0: x - sx / 2,
        y0: y - 1.9 * sy,
        x1: x + sx / 2,
        y1: y - 0.7 * sy,
      },
      {
        x: x,
        y: y + 1.2 * sy,
        align: 'middle',
        x0: x - sx / 2,
        y0: y + 0.1 * sy,
        x1: x + sx / 2,
        y1: y + 1.3 * sy,
      },
    ];
    var label =
      posslabels[
        d3.scan(posslabels, function(a, b) {
          return penalty(a) - penalty(b);
        })
      ];
    label.text = text;
    label.size = size;
    citylabels.push(label);
  }
  var texts = svg.selectAll('text.city').data(citylabels);
  texts
    .enter()
    .append('text')
    .classed('city', true);
  texts.exit().remove();
  svg
    .selectAll('text.city')
    .attr('x', function(d) {
      return 1000 * d.x;
    })
    .attr('y', function(d) {
      return 1000 * d.y;
    })
    .style('font-size', function(d) {
      return d.size;
    })
    .style('text-anchor', function(d) {
      return d.align;
    })
    .text(function(d) {
      return d.text;
    })
    .raise();

  var reglabels = [];
  for (var i = 0; i < nterrs; i++) {
    var city = cities[i];
    var text = makeName(lang, 'region');
    var sy = params.fontsizes.region / 1000;
    var sx = 0.6 * text.length * sy;
    var lc = terrCenter(h, terr, city, true);
    var oc = terrCenter(h, terr, city, false);
    var best = 0;
    var bestscore = -999999;
    for (var j = 0; j < h.length; j++) {
      var score = 0;
      var v = h.mesh.vxs[j];
      score -=
        3000 *
        Math.sqrt(
          (v[0] - lc[0]) * (v[0] - lc[0]) + (v[1] - lc[1]) * (v[1] - lc[1])
        );
      score -=
        1000 *
        Math.sqrt(
          (v[0] - oc[0]) * (v[0] - oc[0]) + (v[1] - oc[1]) * (v[1] - oc[1])
        );
      if (terr[j] != city) score -= 3000;
      for (var k = 0; k < cities.length; k++) {
        var u = h.mesh.vxs[cities[k]];
        if (Math.abs(v[0] - u[0]) < sx && Math.abs(v[1] - sy / 2 - u[1]) < sy) {
          score -= k < nterrs ? 4000 : 500;
        }
        if (
          v[0] - sx / 2 < citylabels[k].x1 &&
          v[0] + sx / 2 > citylabels[k].x0 &&
          v[1] - sy < citylabels[k].y1 &&
          v[1] > citylabels[k].y0
        ) {
          score -= 5000;
        }
      }
      for (var k = 0; k < reglabels.length; k++) {
        var label = reglabels[k];
        if (
          v[0] - sx / 2 < label.x + label.width / 2 &&
          v[0] + sx / 2 > label.x - label.width / 2 &&
          v[1] - sy < label.y &&
          v[1] > label.y - label.size
        ) {
          score -= 20000;
        }
      }
      if (h[j] <= 0) score -= 500;
      if (v[0] + sx / 2 > 0.5 * h.mesh.extent.width) score -= 50000;
      if (v[0] - sx / 2 < -0.5 * h.mesh.extent.width) score -= 50000;
      if (v[1] > 0.5 * h.mesh.extent.height) score -= 50000;
      if (v[1] - sy < -0.5 * h.mesh.extent.height) score -= 50000;
      if (score > bestscore) {
        bestscore = score;
        best = j;
      }
    }
    reglabels.push({
      text: text,
      x: h.mesh.vxs[best][0],
      y: h.mesh.vxs[best][1],
      size: sy,
      width: sx,
    });
  }
  texts = svg.selectAll('text.region').data(reglabels);
  texts
    .enter()
    .append('text')
    .classed('region', true);
  texts.exit().remove();
  svg
    .selectAll('text.region')
    .attr('x', function(d) {
      return 1000 * d.x;
    })
    .attr('y', function(d) {
      return 1000 * d.y;
    })
    .style('font-size', function(d) {
      return 1000 * d.size;
    })
    .style('text-anchor', 'middle')
    .text(function(d) {
      return d.text;
    })
    .raise();
}
function drawMap(svg, render) {
  render.rivers = getRivers(render.h, 0.01);
  render.coasts = contour(render.h, 0);
  render.terr = getTerritories(render);
  render.borders = getBorders(render);
  drawPaths(svg, 'river', render.rivers);
  drawPaths(svg, 'coast', render.coasts);
  drawPaths(svg, 'border', render.borders);
  visualizeSlopes(svg, render);
  visualizeCities(svg, render);
  drawLabels(svg, render);
}

function doMap(svg, params) {
  var render = {
    params: params,
  };
  var width = svg.attr('width');
  svg.attr('height', (width * params.extent.height) / params.extent.width);
  svg.attr(
    'viewBox',
    (-1000 * params.extent.width) / 2 +
      ' ' +
      (-1000 * params.extent.height) / 2 +
      ' ' +
      1000 * params.extent.width +
      ' ' +
      1000 * params.extent.height
  );
  svg.selectAll().remove();
  render.h = params.generator(params);
  placeCities(render);
  drawMap(svg, render);
}

var defaultParams = {
  extent: defaultExtent,
  generator: generateCoast,
  npts: 16384,
  ncities: 15,
  nterrs: 5,
  fontsizes: {
    region: 40,
    city: 25,
    town: 20,
  },
};