Voronoi Revisited (Part 3)

In the two previous blog posts, I gave up on trying to generate an interesting fractal coastline without using a very dense Voronoi (Delauney) grid and instead modified Dragons Abound to work with a very dense grid.  Or at least got it to the point where it could generate interesting coastlines.

However, the rest of the program doesn't work well with so many Delauney triangles (256K at my current settings).  One problem is that Dragons Abound draws the land and sea by drawing all the individual triangles, and that many SVG elements crashes the browser.  So I have to turn off land rendering completely.  There's probably a way to work around that issue, but having so many triangles creates other issues.  For example, there are various parts of the program that have to process the entire map.  Each of those becomes sixteen times slower when there are 256K locations rather than 16K locations.  There are also some parts of the code (the new precipitation model being an example) that break in various ways when dealing with so many triangles.  And there's nothing to be gained by having the location grid be so detailed -- after creating the coastline, nothing is improved by the additional complexity.  So while I probably could go through the program and fix the areas where a large number of locations slows down the code unacceptably, or breaks the code, it seems easier to reduce the resolution of the map grid after coastlines have been created.

Azgaar has previously done some work on changing the resolution of the the Voronoi grid underlying the map.  He implemented the capability to change the resolution of the grid on the fly as he was generating, so that he could (for example) increase the density of locations along the coast. However, changing the density locally has some drawbacks -- specifically, it creates some odd shaped triangles along the boundary.  And Azgaar later opined that it was too complicated and not worth the effort.  Azgaar usually knows what he's talking about, so I'll take his word for it and avoid any kind of repacking of the existing grid.

What I'll do instead is created a second grid at the desired (lower) resolution and then copy the heightmap over to the new grid.  (Recall that Dragons Abound now keeps coastlines separate from the grid so that once they're created they're no longer dependent upon matching up precisely with the grid.)  This is a little bit tricky.  Since the original grid is at a much higher resolution than the new grid, there will be many locations in the original grid that map to a single location in the new grid.  Since each of those original locations has a different height in the heightmap, how should I copy that over?  Should I use the average?  Or perhaps the highest (or lowest)?

To start with, I'll just pick one random location to copy over, just to see if the new grid will work with the rest of the program:

It works surprisingly well.  One minor bug where the new locations were not getting properly marked as land, coast or sea but once that was fixed, map generation worked fine.  There are a few minor things to clean up (such as the Palmanor icon out to sea) but overall it looks good.  Even the tiny islands look fine.

In the end, I settled on making each location be the average of the underlying locations when reducing the resolution of the Voronoi grid.  This seems like a reasonable approach, and I can always adjust it later if necessary.  This image shows how the coastlines end up separate from the final grid:

So to recap:  Dragons Abound uses a very high resolution grid of Delauney triangles during the generation of the map heightmap.  When that is complete, Dragons Abound captures the coastlines by tracing where the heightmap transitions from less than zero to greater then zero.  Dragons Abound then copies the high resolution grid into a much lower resolution grid by averaging overlapping locations.  The high resolution grid is then discarded and the rest of the procedural generation and display continues on using the low resolution grid.  An interesting question is whether using a Delauney grid at this point adds any value; perhaps I should just copy into a hex grid or something similar.