#+title: Elevation Control
#+date: <2017-07-17 Mon>

#+begin_export html
<x:head>
  <meta name="twitter:card" content="summary" />
  <meta name="twitter:site" content="@redblobgames" />
  <meta property="og:url" content="https://www.redblobgames.com/x/1728-elevation-control/" />
  <meta property="og:title" content="Red Blob Games: sketching mountains and coastlines to guide procedural map generation" />
  <meta property="og:description" content="Experiment with drawing coastlines and mountains to generate island terrain" />
  <meta property="og:image" content="https://www.redblobgames.com/x/1728-elevation-control/blog/draw-blob.png"/>
</x:head>

<style>
canvas#layer-drawing { cursor: crosshair; }
div.layers { clear: both; display: grid; grid-template-columns: 1fr; }
div.layers > canvas { grid-column: 1; grid-row: 1; width: 100%; }
#distance-field-panels { display: grid; grid-template-columns: repeat(3, 1fr); grid-column-gap: 10px; }
#distance-field-panels figure canvas { width: 100%; }
svg path { fill: hsl(120,20%,80%); stroke: hsl(120,50%,50%); stroke-width: 2px; }
svg line { fill: none; stroke: hsl(0,0%,80%); stroke-width: 2px; }
button { width: 200px; margin: 0 4px; }
button.a { background-color: hsl(30,20%,80%); }
button.e { width: 100px; background-color: hsl(120,20%,80%); }
button.c { background-color: hsl(240,20%,80%); }
#buttoncontainer.altitude  button.a,
#buttoncontainer.erase     button.e,
#buttoncontainer.coastline button.c 
{ outline: 2px solid black; font-weight: bold; }
</style>

<p style="font-size:small">
   <em>Note:</em> the /x/ series of posts on my site are mostly unpolished mini posts. I'm trying out a few different ideas for procedural map generation; this is one of them.
</p>
#+end_export

In my [[../1725-procedural-elevation/][previous blog post]] I experimented with elevation based on river drainage basins. It was cool, but it didn't match what we needed for our game, so I stepped back a bit and decided to work on something else. We want the game/level designer to have some control over mountains, coastlines, and rivers. The designer should be able to draw a rough sketch, and then the procedural generator will fill in the rest. We're intentionally making /unrealistic terrain/ (likely something low-poly and cartoony), but that's something for a future blog post. This week's experiment is about designer control of mountains and coastlines. 

Draw @@html:<span style="color:hsl(30,50%,30%)">⯀</span>@@mountain ridges or @@html:<span style="color:hsl(240,100%,30%)">⯀</span>@@coastlines: @@html: <button style="margin-left:100px;width:75px" onclick="sketcher.reset_sketch()">erase all</button>@@

#+begin_export html
<div class="layers">
  <canvas id="layer-output" width="600" height="600"/>
  <canvas id="layer-preview" width="600" height="600"/>
  <canvas id="layer-drawing" width="600" height="600"/>
</div>
<div id="buttoncontainer" style="text-align:center">
  <button class="a" onclick="set_mode('altitude')">Mountain ridges</button>
  <button class="e" onclick="set_mode('erase')">Erase</button>
  <button class="c" onclick="set_mode('coastline')">Coastlines</button>
</div>
<div style="text-align:center">
  Noise: <input type="range" min="0.0" max="1.0" value="0.0" step="0.1" oninput="set_noise(this.valueAsNumber)" style="width:400px"/>
</div>
#+end_export

Things to try:

- Draw the mountain ridges, and the system figures out the coastline. Adjust the coastline by drawing your own.
- Draw the coastline, and the system figures out the mountain ridges once you completely enclose an area. Draw your own mountain ranges to replace the default.
- Draw a partial coastline and also some mountain ridges to see how the water/land "spills" in/out of the partially enclosed area.

#+begin_export html
<figure>
<img width="600" height="120" src="blog/examples.png"/>
</figure>
#+end_export

The implementation is surprisingly simple.

** Distance fields
:PROPERTIES:
:CUSTOM_ID: distance-fields
:END:

I had tried several approaches, including medial axis, before I found something I like quite a lot. The idea is to use /distance fields/. For each point on the mesh, calculate the (graph) distance from a set of /seed points/. Here are the three distance fields for the map you drew above:

#+begin_export html
<div id="distance-field-panels">
  <figure><canvas id="distance-altitude" width="200" height="200"/><figcaption>A = Mountains</figcaption></figure>
  <figure><canvas id="distance-boundary" width="200" height="200"/><figcaption>B = Boundary</figcaption></figure>
  <figure><canvas id="distance-coastline" width="200" height="200"/><figcaption>C = Coastline</figcaption></figure>
</div>
#+end_export

The land and water were spilling over the coastlines. To fix that, I made the distance fields for the boundary and mountains /not cross the coastline/.

Distance fields are easy to calculate on a graph, using breadth first search (around 20 lines of code).

** Combining distance fields
:PROPERTIES:
:CUSTOM_ID: combining-distance-fields
:END:

Given ~A~ = distance-from-mountain and ~B~ = distance-from-boundary, how should I combine them? My first thought was to interpolate the nearest constraint points. Between +1 and 0 I would interpolate linearly. But I draw an enclosed "O" shape for mountains, the interpolation would be between 1 and 1, and it'd end up as a plateau. I'd prefer it to be a crater. So I searched for some useful interpolation functions.

I discovered that ~B/(A+B)~ works really well! Near the mountain ridges, ~A~ is small, so ~B/(A+B)~ is close to ~B/B~ = 1. Near the boundary, ~B~ is small, so ~B/(A+B)~ is close to ~0/A~ = 0. In between, it interpolates.

It's scale-free: if I replace distances by ten times the distance, I get the same answer. This is an important property. Without it, I have much lower confidence in the results.

*** Pairwise combination
:PROPERTIES:
:CUSTOM_ID: pairwise-combination
:END:

The mountains and boundary aren't enough. I wanted to be able to draw a coastline ~C~ as well. I extended the two-point interpolation:

- If ~C~ is furthest away, use the previous interpolation with only ~A~ and ~B~ but modify it for -1 (boundary) to +1 (mountains): ~2*B/(A+B)-1~
- If ~B~ is furthest away, interpolate between coastline (0) and mountains (+1): ~C/(A+C)~
- If ~A~ is furthest away, interpolate between coastline (0) and boundary (-1): ~B/(B+C)-1~

There are sometimes weird effects with partially drawn coastlines. The boundary–mountain interpolation doesn't always match up with the boundary–coastline + coastline–mountain interpolations. The problem is that any time I introduce /if-then/ into the equation, there's a potential for discontinuity. Are there other functions that don't lead to discontinuities?

*** Harmonic mean
:PROPERTIES:
:CUSTOM_ID: harmonic-mean
:END:

I looked at the [[https://en.wikipedia.org/wiki/Weighted_geometric_mean][weighted geometric mean]] and the [[https://en.wikipedia.org/wiki/Harmonic_mean#Weighted_harmonic_mean][weighted harmonic mean]].  The weighted geometric mean would return positive elevations only, so it's not useful here. The weighted harmonic mean though looks nice. For two values with elevation 0.0 and 1.0, it becomes ~B/(A+B)~, which is exactly what I had started with. For three values:

~(+1 * 1/A + 0 * 1/C + -1 * 1/B) / (1/A + 1/C + 1/B)~

- If there's no coastline, ~C~ is infinity, so ~1/C~ is 0, and this becomes ~(1/A-1/B)/(1/A+1/B)~ which turns out to be equivalent to the previous rule of ~2*B/(A+B)-1~.
- If the land is surrounded by coastline, in the interior ~B~ is infinity, so ~1/B~ is 0, and this becomes ~(1/A)/(1/A+1/C)~ which turns out to be equivalent to the previous rule of ~C/(A+C)~.
- If the land is surrounded by coastline, in the exterior ~A~ is infinity, so ~1/A~ is 0, and this becomes ~(-1/B)/(1/C+1/B)~ which turns out to be equivalent to the previous rule of ~B/(B+C)-1~.

Hey, that's pretty cool — when there's no coastline or a complete coastline, it is the same as my previous set of rules! Where it differs is when there's a partial coastline. I had discontinuities with partial coastlines, but the harmonic mean eliminates all the discontinuities. It's less code too. Nice!

*** Weighting functions
:PROPERTIES:
:CUSTOM_ID: weighting-functions
:END:

With harmonic means, there's also the potential to use different weighting other than linear: ~(+1 * 1/Aⁿ + 0 * 1/Cⁿ + -1 * 1/Bⁿ) / (1/Aⁿ + 1/Cⁿ + 1/Bⁿ)~. 

#+begin_src python :exports results :results output :wrap export html
#!/usr/bin/env python3

import math

def interpolation_line(f):
    points = []
    points2 = []
    epsilon = 1e-3
    for i in range(101):
        a = max(epsilon, i/100.0)
        b = max(epsilon, 1-i/100.0)

        e = (1/f(b)) / (1/f(a) + 1/f(b))
        x = round(250 * a, 2)
        y = 90 - round(90 * e, 2)
        points.append((x,y))
        points2.append((500-x,y))
    return points + list(reversed(points2))

def diagram(label, points):
    d = 'M' + 'L'.join(map(lambda p: "{:.2f},{:.2f}".format(*p), points))
    print("""
    <figure>
    <svg viewBox="0 0 600 100">
    <g transform="translate(50,5)">
    <rect x="0" y="45" width="500" height="45" style="fill:hsl(240,50%,70%)"/>
    <path d="{} L 500,90 L 0,90 Z"/>
    <line x1="0" y1="91" x2="500" y2="91"/>
    <line x1="250" y1="91" x2="250" y2="0"/>
    </g>
    <text text-anchor="middle" x="300" y="90">{}</text>
    </svg>
    </figure>
""".format(d, label))
    
diagram("Linear: n=1", interpolation_line(lambda x: x))
diagram("Square: n=2", interpolation_line(lambda x: x*x))
diagram("Square root: n=sqrt(2)", interpolation_line(lambda x: math.sqrt(x)))
#+end_src

#+results:
#+begin_export html

    <figure>
    <svg viewBox="0 0 600 100">
    <g transform="translate(50,5)">
    <rect x="0" y="45" width="500" height="45" style="fill:hsl(240,50%,70%)"/>
    <path d="M0.25,89.91L2.50,89.10L5.00,88.20L7.50,87.30L10.00,86.40L12.50,85.50L15.00,84.60L17.50,83.70L20.00,82.80L22.50,81.90L25.00,81.00L27.50,80.10L30.00,79.20L32.50,78.30L35.00,77.40L37.50,76.50L40.00,75.60L42.50,74.70L45.00,73.80L47.50,72.90L50.00,72.00L52.50,71.10L55.00,70.20L57.50,69.30L60.00,68.40L62.50,67.50L65.00,66.60L67.50,65.70L70.00,64.80L72.50,63.90L75.00,63.00L77.50,62.10L80.00,61.20L82.50,60.30L85.00,59.40L87.50,58.50L90.00,57.60L92.50,56.70L95.00,55.80L97.50,54.90L100.00,54.00L102.50,53.10L105.00,52.20L107.50,51.30L110.00,50.40L112.50,49.50L115.00,48.60L117.50,47.70L120.00,46.80L122.50,45.90L125.00,45.00L127.50,44.10L130.00,43.20L132.50,42.30L135.00,41.40L137.50,40.50L140.00,39.60L142.50,38.70L145.00,37.80L147.50,36.90L150.00,36.00L152.50,35.10L155.00,34.20L157.50,33.30L160.00,32.40L162.50,31.50L165.00,30.60L167.50,29.70L170.00,28.80L172.50,27.90L175.00,27.00L177.50,26.10L180.00,25.20L182.50,24.30L185.00,23.40L187.50,22.50L190.00,21.60L192.50,20.70L195.00,19.80L197.50,18.90L200.00,18.00L202.50,17.10L205.00,16.20L207.50,15.30L210.00,14.40L212.50,13.50L215.00,12.60L217.50,11.70L220.00,10.80L222.50,9.90L225.00,9.00L227.50,8.10L230.00,7.20L232.50,6.30L235.00,5.40L237.50,4.50L240.00,3.60L242.50,2.70L245.00,1.80L247.50,0.90L250.00,0.09L250.00,0.09L252.50,0.90L255.00,1.80L257.50,2.70L260.00,3.60L262.50,4.50L265.00,5.40L267.50,6.30L270.00,7.20L272.50,8.10L275.00,9.00L277.50,9.90L280.00,10.80L282.50,11.70L285.00,12.60L287.50,13.50L290.00,14.40L292.50,15.30L295.00,16.20L297.50,17.10L300.00,18.00L302.50,18.90L305.00,19.80L307.50,20.70L310.00,21.60L312.50,22.50L315.00,23.40L317.50,24.30L320.00,25.20L322.50,26.10L325.00,27.00L327.50,27.90L330.00,28.80L332.50,29.70L335.00,30.60L337.50,31.50L340.00,32.40L342.50,33.30L345.00,34.20L347.50,35.10L350.00,36.00L352.50,36.90L355.00,37.80L357.50,38.70L360.00,39.60L362.50,40.50L365.00,41.40L367.50,42.30L370.00,43.20L372.50,44.10L375.00,45.00L377.50,45.90L380.00,46.80L382.50,47.70L385.00,48.60L387.50,49.50L390.00,50.40L392.50,51.30L395.00,52.20L397.50,53.10L400.00,54.00L402.50,54.90L405.00,55.80L407.50,56.70L410.00,57.60L412.50,58.50L415.00,59.40L417.50,60.30L420.00,61.20L422.50,62.10L425.00,63.00L427.50,63.90L430.00,64.80L432.50,65.70L435.00,66.60L437.50,67.50L440.00,68.40L442.50,69.30L445.00,70.20L447.50,71.10L450.00,72.00L452.50,72.90L455.00,73.80L457.50,74.70L460.00,75.60L462.50,76.50L465.00,77.40L467.50,78.30L470.00,79.20L472.50,80.10L475.00,81.00L477.50,81.90L480.00,82.80L482.50,83.70L485.00,84.60L487.50,85.50L490.00,86.40L492.50,87.30L495.00,88.20L497.50,89.10L499.75,89.91 L 500,90 L 0,90 Z"/>
    <line x1="0" y1="91" x2="500" y2="91"/>
    <line x1="250" y1="91" x2="250" y2="0"/>
    </g>
    <text text-anchor="middle" x="300" y="90">Linear: n=1</text>
    </svg>
    </figure>


    <figure>
    <svg viewBox="0 0 600 100">
    <g transform="translate(50,5)">
    <rect x="0" y="45" width="500" height="45" style="fill:hsl(240,50%,70%)"/>
    <path d="M0.25,90.00L2.50,89.99L5.00,89.96L7.50,89.91L10.00,89.84L12.50,89.75L15.00,89.63L17.50,89.49L20.00,89.32L22.50,89.13L25.00,88.90L27.50,88.65L30.00,88.36L32.50,88.03L35.00,87.68L37.50,87.28L40.00,86.85L42.50,86.38L45.00,85.86L47.50,85.31L50.00,84.71L52.50,84.06L55.00,83.37L57.50,82.63L60.00,81.84L62.50,81.00L65.00,80.11L67.50,79.17L70.00,78.18L72.50,77.13L75.00,76.03L77.50,74.88L80.00,73.68L82.50,72.43L85.00,71.12L87.50,69.77L90.00,68.37L92.50,66.92L95.00,65.42L97.50,63.89L100.00,62.31L102.50,60.69L105.00,59.04L107.50,57.36L110.00,55.65L112.50,53.91L115.00,52.15L117.50,50.38L120.00,48.59L122.50,46.80L125.00,45.00L127.50,43.20L130.00,41.41L132.50,39.62L135.00,37.85L137.50,36.09L140.00,34.35L142.50,32.64L145.00,30.96L147.50,29.31L150.00,27.69L152.50,26.11L155.00,24.58L157.50,23.08L160.00,21.63L162.50,20.23L165.00,18.88L167.50,17.57L170.00,16.32L172.50,15.12L175.00,13.97L177.50,12.87L180.00,11.82L182.50,10.83L185.00,9.89L187.50,9.00L190.00,8.16L192.50,7.37L195.00,6.63L197.50,5.94L200.00,5.29L202.50,4.69L205.00,4.14L207.50,3.62L210.00,3.15L212.50,2.72L215.00,2.32L217.50,1.97L220.00,1.64L222.50,1.35L225.00,1.10L227.50,0.87L230.00,0.68L232.50,0.51L235.00,0.37L237.50,0.25L240.00,0.16L242.50,0.09L245.00,0.04L247.50,0.01L250.00,0.00L250.00,0.00L252.50,0.01L255.00,0.04L257.50,0.09L260.00,0.16L262.50,0.25L265.00,0.37L267.50,0.51L270.00,0.68L272.50,0.87L275.00,1.10L277.50,1.35L280.00,1.64L282.50,1.97L285.00,2.32L287.50,2.72L290.00,3.15L292.50,3.62L295.00,4.14L297.50,4.69L300.00,5.29L302.50,5.94L305.00,6.63L307.50,7.37L310.00,8.16L312.50,9.00L315.00,9.89L317.50,10.83L320.00,11.82L322.50,12.87L325.00,13.97L327.50,15.12L330.00,16.32L332.50,17.57L335.00,18.88L337.50,20.23L340.00,21.63L342.50,23.08L345.00,24.58L347.50,26.11L350.00,27.69L352.50,29.31L355.00,30.96L357.50,32.64L360.00,34.35L362.50,36.09L365.00,37.85L367.50,39.62L370.00,41.41L372.50,43.20L375.00,45.00L377.50,46.80L380.00,48.59L382.50,50.38L385.00,52.15L387.50,53.91L390.00,55.65L392.50,57.36L395.00,59.04L397.50,60.69L400.00,62.31L402.50,63.89L405.00,65.42L407.50,66.92L410.00,68.37L412.50,69.77L415.00,71.12L417.50,72.43L420.00,73.68L422.50,74.88L425.00,76.03L427.50,77.13L430.00,78.18L432.50,79.17L435.00,80.11L437.50,81.00L440.00,81.84L442.50,82.63L445.00,83.37L447.50,84.06L450.00,84.71L452.50,85.31L455.00,85.86L457.50,86.38L460.00,86.85L462.50,87.28L465.00,87.68L467.50,88.03L470.00,88.36L472.50,88.65L475.00,88.90L477.50,89.13L480.00,89.32L482.50,89.49L485.00,89.63L487.50,89.75L490.00,89.84L492.50,89.91L495.00,89.96L497.50,89.99L499.75,90.00 L 500,90 L 0,90 Z"/>
    <line x1="0" y1="91" x2="500" y2="91"/>
    <line x1="250" y1="91" x2="250" y2="0"/>
    </g>
    <text text-anchor="middle" x="300" y="90">Square: n=2</text>
    </svg>
    </figure>


    <figure>
    <svg viewBox="0 0 600 100">
    <g transform="translate(50,5)">
    <rect x="0" y="45" width="500" height="45" style="fill:hsl(240,50%,70%)"/>
    <path d="M0.25,87.24L2.50,81.78L5.00,78.75L7.50,76.54L10.00,74.74L12.50,73.21L15.00,71.85L17.50,70.62L20.00,69.50L22.50,68.47L25.00,67.50L27.50,66.59L30.00,65.73L32.50,64.91L35.00,64.13L37.50,63.38L40.00,62.66L42.50,61.96L45.00,61.29L47.50,60.63L50.00,60.00L52.50,59.38L55.00,58.78L57.50,58.19L60.00,57.62L62.50,57.06L65.00,56.51L67.50,55.96L70.00,55.43L72.50,54.91L75.00,54.39L77.50,53.88L80.00,53.38L82.50,52.88L85.00,52.39L87.50,51.91L90.00,51.43L92.50,50.95L95.00,50.48L97.50,50.01L100.00,49.55L102.50,49.08L105.00,48.62L107.50,48.17L110.00,47.71L112.50,47.26L115.00,46.80L117.50,46.35L120.00,45.90L122.50,45.45L125.00,45.00L127.50,44.55L130.00,44.10L132.50,43.65L135.00,43.20L137.50,42.74L140.00,42.29L142.50,41.83L145.00,41.38L147.50,40.92L150.00,40.45L152.50,39.99L155.00,39.52L157.50,39.05L160.00,38.57L162.50,38.09L165.00,37.61L167.50,37.12L170.00,36.62L172.50,36.12L175.00,35.61L177.50,35.09L180.00,34.57L182.50,34.04L185.00,33.49L187.50,32.94L190.00,32.38L192.50,31.81L195.00,31.22L197.50,30.62L200.00,30.00L202.50,29.37L205.00,28.71L207.50,28.04L210.00,27.34L212.50,26.62L215.00,25.87L217.50,25.09L220.00,24.27L222.50,23.41L225.00,22.50L227.50,21.53L230.00,20.50L232.50,19.38L235.00,18.15L237.50,16.79L240.00,15.26L242.50,13.46L245.00,11.25L247.50,8.22L250.00,2.76L250.00,2.76L252.50,8.22L255.00,11.25L257.50,13.46L260.00,15.26L262.50,16.79L265.00,18.15L267.50,19.38L270.00,20.50L272.50,21.53L275.00,22.50L277.50,23.41L280.00,24.27L282.50,25.09L285.00,25.87L287.50,26.62L290.00,27.34L292.50,28.04L295.00,28.71L297.50,29.37L300.00,30.00L302.50,30.62L305.00,31.22L307.50,31.81L310.00,32.38L312.50,32.94L315.00,33.49L317.50,34.04L320.00,34.57L322.50,35.09L325.00,35.61L327.50,36.12L330.00,36.62L332.50,37.12L335.00,37.61L337.50,38.09L340.00,38.57L342.50,39.05L345.00,39.52L347.50,39.99L350.00,40.45L352.50,40.92L355.00,41.38L357.50,41.83L360.00,42.29L362.50,42.74L365.00,43.20L367.50,43.65L370.00,44.10L372.50,44.55L375.00,45.00L377.50,45.45L380.00,45.90L382.50,46.35L385.00,46.80L387.50,47.26L390.00,47.71L392.50,48.17L395.00,48.62L397.50,49.08L400.00,49.55L402.50,50.01L405.00,50.48L407.50,50.95L410.00,51.43L412.50,51.91L415.00,52.39L417.50,52.88L420.00,53.38L422.50,53.88L425.00,54.39L427.50,54.91L430.00,55.43L432.50,55.96L435.00,56.51L437.50,57.06L440.00,57.62L442.50,58.19L445.00,58.78L447.50,59.38L450.00,60.00L452.50,60.63L455.00,61.29L457.50,61.96L460.00,62.66L462.50,63.38L465.00,64.13L467.50,64.91L470.00,65.73L472.50,66.59L475.00,67.50L477.50,68.47L480.00,69.50L482.50,70.62L485.00,71.85L487.50,73.21L490.00,74.74L492.50,76.54L495.00,78.75L497.50,81.78L499.75,87.24 L 500,90 L 0,90 Z"/>
    <line x1="0" y1="91" x2="500" y2="91"/>
    <line x1="250" y1="91" x2="250" y2="0"/>
    </g>
    <text text-anchor="middle" x="300" y="90">Square root: n=sqrt(2)</text>
    </svg>
    </figure>

#+end_export

For the demo on this page I chose harmonic means with sqrt weighting. On land, it should produce more valleys and sharper mountain peaks. In the water, it should produce more shallow water and occasional deep water trenches.

*However* it doesn't actually produce that effect for the three-valued harmonic mean. :-( The sqrt weighting puts a lot more of the values in the middle, which is 0 for the -1:+1 range. That's what I want — a lot of values near 0. But for the three-valued harmonic mean, it's separately putting a lot of values in the middle of the -1:0 range (lots of -0.5) and the 0:+1 range (lots of +0.5). So it's a cute trick but it has issues.

** Features
:PROPERTIES:
:CUSTOM_ID: features
:END:

*** Noise 
:PROPERTIES:
:CUSTOM_ID: noise
:END:

One of our goals is to let the designer specify constraints, but then fill in the unconstrained areas procedurally. I tried a little bit of here with elevation. I mixed in simplex noise for unconstrained areas. Try going to the demo at the top and changing the noise slider.

I'm not happy with the results though. It may need higher resolution maps to make it work well.

*** Resolution
:PROPERTIES:
:CUSTOM_ID: resolution
:END:

The lines drawn by the designer are stored as vectors, so it should be possible to apply those same vectors to a more detailed mesh to get similar landscapes. The idea would be to use the low resolution mesh to give interactive speeds for the designer to explore possibilities, then apply a high resolution mesh for the final terrain. However I haven't implemented this yet.

*** Non-islands
:PROPERTIES:
:CUSTOM_ID: non-islands
:END:

In this demo I've constrained map boundaries to be deep water (field ~B~), but the algorithm isn't limited to island shapes. I can generate other types of maps by setting the boundary conditions to include both land and water. Try drawing mountains over the edges of the map.

*** Different elevation constraints
:PROPERTIES:
:CUSTOM_ID: different-elevation-constraints
:END:

Right now the algorithm only works with mountain, boundary, coastline constraints. It would be useful to be able to set /any/ elevation instead of only +1. The algorithm does *not* support that, and I'm not sure what to do about it.

There are papers listed at the end that do support more complex constraints, not only arbitrary elevations, but also constraints on slopes and second derivatives. There are some pretty cool effects from these types of constraints, but the algorithms to set elevations is much more complicated than what I wanted to implement.

** More
:PROPERTIES:
:CUSTOM_ID: more
:END:

There are other projects that have done far more advanced things than what I'm doing here. Take a look at these:

- [[https://www.semanticscholar.org/paper/Feature-based-terrain-generation-using-diffusion-Hnaidi-Gu%C3%A9rin/6dce9a47c78331a4abc1fd591731d08b236f0e3a?p2df][Feature based terrain generation using diffusion equation]] [PDF]
- [[https://hal.archives-ouvertes.fr/hal-01517343][Sculpting Mountains: Interactive Terrain Modeling Based on Subsurface Geology]]
- [[https://hal.archives-ouvertes.fr/hal-01519852][EcoBrush: Interactive Control of Visually Consistent Large-Scale Ecosystems]]
- [[https://pubs.cs.uct.ac.za/id/eprint/516/1/terrsketch.pdf][Terrain Sketching]] [PDF]
- [[http://hpcg.purdue.edu/pubs/2013/Genevaux2013sigg.pdf][Terrain Generation Using Procedural Models Based on Hydrology]] [PDF]

I'm looking for the /simplest/ thing that could work for our project's needs. Our maps will be low-poly cartoonish, so realism is not the goal. Previous blog posts in this series:

- [[../1721-voronoi-alternative/][Triangle dual meshes]]
- [[../1722-b-rep-triangle-meshes/][Triangle mesh representation]]
- [[../1722-delaunay-map-import/][Importing map data from an image]] (designer control)
- [[../1723-procedural-river-growing/][Generating river drainage basins]]
- [[../1724-elevation-from-rivers/][Generating elevation from rivers]] part 1
- [[../1725-procedural-elevation/][Generating elevation from rivers]] part 2

My current plan is to use the method on this page to generate /coarse/ elevation. I'll then use the algorithms I developed in the previous blog posts: coarse elevation to generate rivers, then both coarse elevation and rivers to generate detailed elevation. The level designer will sketch out some ideas and the system will procedurally generate a landscape that matches the designer's input.

#+begin_export html
<x:footer>
  <script>
    let module = {};
  </script>
  <script src="../1725-procedural-elevation/triangle-mesh.js"/>
  <script src="/js/draggable.v1.js"/>
  <script src="/js/prng.js"/>
  <script src="/js/simplex-noise.js"/>
  <script src="delay-draw.js"/>
  <script src="elevation-control.js"/>

  Created 11 Jul 2017 with Emacs org-mode (<a href="index.org">source of this page</a>); &#160;
<!-- hhmts start -->Last modified: 26 Aug 2022<!-- hhmts end -->
</x:footer>
#+end_export