#+title: Mapgen2, HTML5
#+date: <2017-08-03>
#+vue: true
#+draft: true

#+begin_export html
<style>
  input[type="range"] { cursor: ew-resize; }
  .hover-term { cursor: help; border-bottom: 2px dashed black; }
  #diagram-mesh-construction button { background-color: hsl(60,10%,90%); }
  #diagram-mesh-construction button.active { background-color: hsl(120,50%,80%); border-color: hsl(120,50%,50%); }
</style>
#+end_export

{WIP- recreating the diagrams and algorithms from http://www-cs-students.stanford.edu/~amitp/game-programming/polygon-map-generation/ in html5}

Back in 2010, I wrote an article about [[http://www-cs-students.stanford.edu/~amitp/game-programming/polygon-map-generation/][polygon map generation]]. I had wanted to make a map generator that did /not/ use Simplex/Perlin noise for elevation, but instead was built by assigning properties to polygons in a mesh. Although the map generator was made for [[https://en.wikipedia.org/wiki/Realm_of_the_Mad_God][Realm of the Mad God]], some of the algorithms are useful for other types of games too. In each section I'll describe the rationale and variants.

This page is an update of the original page. I'm using the same algorithms (with a few tweaks), but the explanations now include interactive diagrams.

{why polygons?}

#+begin_export html
<figure>
<!-- img src="blog/overview.png" / -->
</figure>
<div style="clear:both"/>
#+end_export


* Polygonal Regions
:PROPERTIES:
:CUSTOM_ID: polygonal-regions
:END:

There are four steps to constructing the polygon mesh:

#+begin_export html
<div id="diagram-mesh-construction">
  <figure>
    <figcaption>Dual mesh construction</figcaption>
    <canvas width="600" height="600"/>
  </figure>
  <ol>
    <li>Pick <span class="hover-term" data-show="points">evenly distributed points</span>.</li>
    <li>Construct a <span class="hover-term" data-show="delaunay">Delaunay triangulation</span>.</li>
    <li>Calculate the <span class="hover-term" data-show="centroids">centroids of the triangles</span>.</li>
    <li>Construct <span class="hover-term" data-show="regions">polygonal regions from those points</span>.</li>
  </ol>
  <p>
  Putting it all together, I have a <span class="hover-term" data-show="all">dual mesh</span>, which has both polygonal regions and
  triangles. Each red point corresponds to one region; each blue point corresponds to one triangle. The red points are the corners of the triangles; the blue points are the corners of the regions. I use centroid polygons here but the same steps work for Voronoi compare: Centroid&nbsp;<input name="centroidCircumcenterMix" type="range" min="0" max="1" step="0.01"/>&nbsp;Voronoi. I picked centroids because the blue points are more evenly spaced.
  </p>
</div>
#+end_export

For evenly distributed red points, I used [[http://devmag.org.za/2009/05/03/poisson-disk-sampling/][Poisson disc sampling]] in this project and [[https://en.wikipedia.org/wiki/Lloyd%27s_algorithm][Lloyd relaxation]] in the first version. Other options are to use points on a grid, or points on a grid randomly perturbed. I didn't use uniformly random points, because they aren't evenly distributed.

** TODO Variable density points

https://azgaar.wordpress.com/2017/10/05/templates/ - explores more points near coastlines, and fewer points in oceans

* Islands
:PROPERTIES:
:CUSTOM_ID: islands
:END:

For this game I'm generating islands, so the boundary of the map will always be water. In the interior, we can use noise to determine which areas are land and water. {this is the constraint+randomness theme}

#+begin_export html
<div id="diagram-water-assignment">
  <figure>
    <figcaption>Water, ocean, lake, coastlines</figcaption>
    <canvas width="600" height="600"/>
 </figure>
  <ol>
    <li>Use noise to determine <span class="hover-term" data-show="landwater">land vs. water</span>.</li>
    <li>Use <span class="hover-term" data-show="connectivity">connectivity</span> to determine which water regions are ocean.</li>
    <li><span class="hover-term" data-show="lakes">Lakes</span> are any water regions not connected to the boundary of the map.</li>
    <li><span class="hover-term" data-show="all">Coastlines</span> are the edges connected to an ocean region on one side and a land region on the other.</li>
  </ol>
</div>
#+end_export

I'm using Simplex noise minus a value that depends on the distance to the boundary of the map: =1 + noise(x, y) - sqrt(x^2 + y^2) < 0? 'water' : 'land'=.

https://en.wikipedia.org/wiki/High_island
 
** Alternatives
:PROPERTIES:
:CUSTOM_ID: islands-alternatives
:END:

There are many other ways to make coastlines. A mix of sine waves in polar coordinates works pretty well. Noise functions in polar coordinates work well too. A level designer might choose a specific shape for the coastline. For this project I chose to start with the coastline and then build a height map, but another approach is to start with a height map and set the coastline where the elevation crosses zero.

** TODO Noise map

- Display the noise values and the land/water map side by side
- Control noisy/deflate parameters here
- Control octaves/etc parameters here

** TODO Lakes

- Highlight some lakes on the map using my svg arrow-out-of-the-box; it doesn't have to be a separate diagram

* Elevation
:PROPERTIES:
:CUSTOM_ID: elevation
:END:

For this project I set elevation based on the /distance from the coast/. To calculate it, run Breadth First Search from the coastline. I tried distances on the polygon regions and distances on the corners, and found corners worked better for this map generator. 

#+begin_export html
<div id="diagram-elevation-assignment">
  <figure>
    <figcaption>Elevation</figcaption>
    <canvas width="600" height="600"/>
  </figure>
  <ol>
    <li>Find <span class="hover-term" data-show="coast_t">corners along coastline edges</span>. As above, coastline edges have an ocean on one side and land on the other side.</li>
    <li>Calculate corner <span class="hover-term" data-show="t_coastdistance">distance from the coastline</span> using Breadth First Search.</li>
    <li>Set <span class="hover-term" data-show="t_elevation">corner elevation</span> by rescaling ocean distances from -1 to 0 and land distances from 0 to +1.</li>
    <li>Set the <span class="hover-term" data-show="all">region elevation</span> to the average elevation of the polygon's corners.</li>
  </ol>
</div>
#+end_export

There is no randomness or noise in this step. 

** Alternatives
:PROPERTIES:
:CUSTOM_ID: elevation-alternatives
:END:

Elevation based on distance to coastline produces simplistic symmetric volcanic-style islands. It's what we wanted in our game. However it's not the most interesting terrain. There are lots of other ways to set elevation, such as [[https://www.redblobgames.com/maps/terrain-from-noise/][fractal noise]], using [[https://www.redblobgames.com/x/1724-elevation-from-rivers/][river basins to set elevation]], or [[https://www.redblobgames.com/x/1728-elevation-control/][drawing mountains and coastlines]], or [[https://azgaar.wordpress.com/2018/02/26/image-converter/][reading heightmaps from images]].

Both water → elevation (shown here) and elevation → water are possible.

** Lakes
:PROPERTIES:
:CUSTOM_ID: elevation-lakes
:END:

If there are no lakes, Breadth First Search works great, but with lakes, things get more complicated. I want the entire lake to have the same corner elevation, so I check if the edge has a lake on either side. If so, I don't increase the distance along that edge. Look at the distance visualization to see this around lakes. This turns breadth first search into a more complicated graph search. I'm not happy with this but it's good enough for now.

Alternatively, if you want lakes at elevation 0, you can treat them like oceans. Set elevation based on distance to ocean /or/ lake.

** TODO Controlling the distribution

{ show the distribution }

If we have a desired distribution of elevations, we can reshape the distribution. I'm using a linear mapping from distance to elevation but that mapping can be anything.

* Drainage
:PROPERTIES:
:CUSTOM_ID: drainage
:END:

At each corner, I point to the corner that has the lowest elevation. This forms a drainage map, sometimes called a watershed map.

1. Streams start on land and flow down to the coastline.
1. Streams join together (tributaries) but don't fork (distributaries).
1. There are no cycles.

#+begin_export html
<div id="diagram-drainage-assignment">
  <figure>
    <figcaption>Drainage patterns</figcaption>
    <canvas width="600" height="600"/>
  </figure>
  <p>
    Because elevations are based on distances, there are <em>many</em>
    possible drainage graphs for the same elevation map. Which one we
    calculate depends on the graph traversal order. This is an opportunity
    to use a random seed to choose which of the many drainage graphs
    we generate:
    <button name="changeDrainageSeed">Change random seed</button>
  </p>
</div>
#+end_export

** Lakes
:PROPERTIES:
:CUSTOM_ID: drainage-lakes
:END:

Along lakes, the elevation isn't increasing, so what should the drainage map do? I make the drainage map follow the graph search used for elevation, so any drainage leading into a lake will eventually lead out, but may take a convoluted path inside the lake. I'm not happy with this but it's good enough for now.

** TODO Watersheds

Drainage can also be used to define watersheds, which can be useful as political and cultural boundaries. Rivers are also useful as political (but not cultural) boundaries.

{ diagram or layer showing watershed boundaries }


* Rivers
:PROPERTIES:
:CUSTOM_ID: rivers
:END:

Rivers are a subset of the streams in the drainage map.

1. Choose a subset of points to be potential river sources. {constraint}
2. Choose a subset of those points to be rivers. {random}

#+begin_export html
<div id="diagram-rivers">
  <figure>
    <figcaption>River creation</figcaption>
    <canvas width="600" height="600"/>
  </figure>
  <button name="reset">Reset</button>
  <input name="numRivers" type="range" min="0" max="1"/> rivers
  <button name="addRivers">Add rivers</button>
  <button name="changeRiverSeed">Change random subset</button>
</div>
#+end_export


** TODO Parameters for selecting a subset of rivers

Not all locations produce equally good rivers. Some filters to consider:

1. Only "leaves" of the drainage tree. (implemented above)
2. Only above some elevation threshold.
3. Only on sloped land. (if you have variable slopes)
4. Only locations with plenty of rainfall. (if you have rainfall implemented)
5. Only locations with wind carrying moisture from bodies of water.
6. Only land that's on a peak not a valley.

{should this be an interactive diagram?}

* Moisture
:PROPERTIES:
:CUSTOM_ID: moisture
:END:

I use a “moisture” value to assign biomes in the next section. I set moisture on land to the /distance/ from a lakeshore or riverbank. The start points are polygonal regions adjacent to lakes or rivers. Similar to elevation, I use Breadth First Search to calculate the distances, then rescale them. Zero distance will have moisture 1.0 and high distance will have moisture 0.0. Water regions will have moisture 1.0.

#+begin_export html
<div id="diagram-moisture-assignment">
  <figure>
    <figcaption>Moisture</figcaption>
    <canvas width="600" height="600"/>
  </figure>
  <button name="reset">Reset</button>
  <input name="numRivers" type="range" min="0" max="0"/> rivers
  <button name="addRivers">Add rivers</button>
</div>
#+end_export

There are many other ways to assign moisture/humidity/rainfall. I used this one because it was simple and worked well for the game these maps were for. It's unable to produce effects like the Nile going through a desert. Other ways to assign moisture include noise (Simplex, Perlin, etc.) and wind simulation (rain shadows, evapotranspiration, etc.).

** TODO Controlling the distribution

{ show the distribution }

If we have a desired distribution of moisture, we can reshape the distribution. I'm using a sqrt mapping from distance to moisture but that mapping can be anything.

* Biomes
:PROPERTIES:
:CUSTOM_ID: biomes
:END:

(explanation about whittaker diagrams, indexed with temperature and rainfall -- temperature is based on elevation and latitude, but on a small island the latitude is constant; rainfall is based on evaporation and wind but I'm just using moisture=evaporation here)

#+begin_export html
<div id="diagram-biome-assignment">
  <figure>
    <figcaption>Biomes</figcaption>
    <canvas width="600" height="600"/>
  </figure>
  <button name="reset">Reset</button>
  <input name="numRivers" type="range" min="0" :max="spring_t.length"/> rivers
  <button name="addRivers">Add rivers</button>
  <button name="prevSeed">Prev seed</button>
  <button name="nextSeed">Next seed</button>
  <br/>
  temperature bias: <input name="temperatureBias" type="range" min="-1" max="1" step="0.01"/>
  moisture bias: <input name="moistureBias" type="range" min="-1" max="1" step="0.01"/>
</div>
#+end_export

** TODO Noisy boundaries

1. Add random number to elevation/moisture
2. Add random noise to elevation/moisture

** TODO Controlling the distribution

{ show the distribution }

See also https://worldengine-ecs.readthedocs.io/en/latest/biomes.html -- it seems useful to draw the scatter plot or a density plot, and then provide parameters for tuning that to make an ice world or a forest world etc.

* Noisy rendering
:PROPERTIES:
:CUSTOM_ID: noisy-rendering
:END:

** Noisy edges
:PROPERTIES:
:CUSTOM_ID: noisy-edges
:END:

Goal: replace the straight-line boundaries of polygonal regions (including biome borders, coastlines, and rivers) with "noisy" lines.

I am following the same general technique I used in 2010.

#+begin_export html
<div id="diagram-quadrilateral-tiling">
  <canvas width="600" height="600"/>
</div>
#+end_export

[[href:/maps/noisy-edges/][separate page]]

#+begin_export html
<div id="diagram-noisy-edges">
  <canvas width="600" height="600"/>
  levels = <input name="noisyEdgeLevels" type="range" min="0" max="3"/>
  amplitude = <input name="noisyEdgeAmplitude" type="range" min="0.0" max="1.0" step="0.05"/>
</div>
#+end_export

** TODO Noisy transitions

** TODO Noisy fills

* TODO Export

#+begin_export html
<div id="map-export">
  <textarea placeholder="JSON output here"
            style="width: 100%; height: 10em; border: 3px solid #ccc; padding: 5px; font-family: monospace; overflow: scroll" 
            onclick="this.setSelectionRange(0, this.value.length)"/>
  <button name="export">Export</button>
</div>
#+end_export


* Libraries
:PROPERTIES:
:CUSTOM_ID: libraries
:END:

Although it's sometimes fun to reimplement everything myself, I try not to do that. I used these libraries:

- poisson-disk-sampling
- delaunator
- simplex-noise
- int-hash

* Other algorithms
:PROPERTIES:
:CUSTOM_ID: other-algorithms
:END:

Coastline/lake: start with any edge a→b that has the left side water and right side land. Then from vertex b you need to find another edge b→c with left side water and right side land. Then continue, one by one, until you get back to a.

* References
:PROPERTIES:
:CUSTOM_ID: references
:END:


http://gmolines.github.io/pfe/oqp/al/ihm/2018/09/17/Y1819-S058/

https://heredragonsabound.blogspot.com/

https://azgaar.wordpress.com/

https://m.mythcreants.com/blog/crafting-plausible-maps/

https://blog.runevision.com/2015/08/procedural-world-potentials-simulation.html

https://blog.bruce-hill.com/meandering-triangles - if you assign an elevation to each region, you can use the triangles for rendering, and use a contour line to find the coastline

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

#+begin_export html
  <x:footer>
    <script src="/js/prng.js"/>
    <script src="_bundle.js"/>

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