Voronoi Revisited (Part 1)

As chronicled in recent blog posts, I've been struggling with modifying Dragons Abound to get the kind of coastline detail I'd like.  My dissatisfaction initially arose when I was implementing barrier islands.  To make the narrowest possible island I could, I made them one location wide -- each location being a Delauney triangle in the underlying representation:

This was pretty unsatisfying -- both because the island was very jagged and because the size of the details was too big.  Greatly increasing the number of Delauney triangles (and hence making each triangle much smaller) would seem to address this problem -- but at the density of triangles I would require the browser crashes.

I addressed this by divorcing the land outlines from the underlying location representation.  This allowed me to draw islands any shape or size I wanted, regardless of the underlying grid of locations:

So, problem solved!  This allows me to draw barrier islands, and since the coastline no longer has to follow the underlying grid, if I want a more detailed coastline I can create a coastline as normal and then add detail to it.

Except...  How do you add detail to a coastline?  That isn't as easy as you might think.  Since I want a fractal coastline, I looked at using actual fractals to add detail to the coastline:

And with some tuning, this can add a lot of detail and interest to coastlines.  However, it cannot produce something like this map:

with a broken shoreline, a variety of different shaped islands, etc.

Perlin noise can produce this sort of terrain with a sufficiently detailed underlying grid, but can it be done *without* storing the terrain height values in an underlying grid with the required resolution  (since I know that breaks my code)? So far, I haven't figured out how to do that.  The coastline is essentially the path through all the points where the Perlin noise function has a value of zero.  Although you can find out directly from the Perlin noise function a value at a particular (X,Y) location, you cannot find (say) “all the locations where the function has a value of zero."  So it's difficult to see how you can trace out the height contour without an underlying grid.  

Even worse, I asked Amit how to do this, and he didn't have an answer either.  It's one thing when I can't figure it out, but when the smart guy can't figure it out I begin to think it can't be done.  Frustrating.  I have the capability to shape the coastline however I want, but I can't get the shapes I want without a very detailed underlying grid.

So how can I get a high-resolution grid without breaking my code?

One approach I've thought about is something Azgaar did in his map generator -- variable size Voronoi cells.  The basic idea is to increase the density (and reduce the size) of the underlying grid along the coastlines, and make it less dense in the oceans and other areas that do not need the detail.  With this option, you will have many grid cells only in the areas where you need the detail.  This would be a pretty challenging change to implement in Dragons Abound, but it's something I want to think about.  On the other hand, Azgaar himself wasn't too happy with this approach, so that's also something to keep in mind.

In the meantime, I want to investigate exactly what is causing the browser to crash when I had lots and lots of triangles.  The Chrome developer tools can provide a lot of insight into performance.  I'm by no means an expert in how to use the tools, but many of the features are simple enough for anyone to figure out.  Case in point, if you want to know the overall memory use in a program, the Memory tab shows the current usage:

In this case, I'm displaying Azgaar's web page and it is using a modest 20 MB of memory.  I can use this to give me some basic insight into the memory usage of Dragons Abound and determine the point at which I crash the tab.

The basic parameter that controls the resolution of the underlying grid in Dragons Abound is cleverly called “npts" for Number of Points.  For every unit area of the map (the regional maps I normally use as examples are 1 unit in area), Dragons Abound creates this many locations in the underlying grid.  Typically I use a value of 16K (16384) for npts, which roughly means that each location in the grid corresponds to about a 70 square pixels on the screen at the default magnification.

Exact memory usage will obviously vary from map to map, but for the above map with 16K points, the memory usage was about 92 MB:

Which was lower than I expected and overall seems pretty modest.

If I double the number of points in the underlying grid, the memory usage goes up to 138 MB:

The memory usage doesn't double because some of that memory is overhead and other data structures that didn't change in size.  The 16K additional points amount to about 50 MB of memory, so each point ends up using about 3K bytes of memory.  That's more than I expected, but the overall usage is still very modest.  On a computer with 64GB of memory, 150 MB is hardly noticeable.

Skipping ahead a few doublings, I find that the tab that Dragons Abound is running in usually crashes around 128K points.  If I catch it before it crashes and check the memory:

which is ... not much.  Certainly not enough to crash the tab.

I've been operating under the assumption that memory usage was crashing the tab, but apparently memory is not the problem.  So why is the tab crashing on me?  The only other clue I have is that the tab doesn't crash until the map is complete, so perhaps that's an indication that it is crashing during rendering.  

The obvious guess is that the SVG I'm producing is overwhelming the browser renderer, either because it is too big or too complex.  As a first step, I can investigate how many SVG elements I'm creating.  In D3, I can get the total number of SVG elements I've created with svg.selectAll('*').size().

Running with 16K points and checking the number of SVG elements shows me this:

In turn, 32K points has 65457 elements and 128K points has 258823.  Each point added to the underlying grid adds two elements to the map.  I think I've found my culprit.

Each point in the underlying grid adds SVG elements because of the way Dragons Abound renders the land (and the sea).  The land is rendered by drawing each underlying location as a filled polygon and then blurring them all together.  This enables Dragons Abound to mottle the land in pleasing ways, or use the height of the land to render the land in 3D shading, as you can see in the land here:

I can investigate by turning off the land and ocean visualizations and checking to see how many SVG elements are created.  With 256K points:

Wow, that's a huge reduction in the number of SVG elements. And as hoped, the map now renders without crashing!  So as long as I avoid using the grid to render the land and sea, I can use a much denser grid than I've ever been able to before.

Now that I can use a much denser Voronoi grid, I want to check to see whether that enables generation of the sort of land features I want, such as coastal islands.  The dense Voronoi grid creates other problems (especially with rivers) so I'll turn off everything except the coastlines to speed up testing and focus on that.  Here's an initial render of some coastline using 256K points and some default noise:

The good news is that this renders fine, and in fact already produces a much better coastline.
Even without tuning it's a big improvement.  The noise is producing the kinds of fractal coastlines and coastal islands that I noted above in the reference map.

Here's a 300% zoom on the islands:

At this magnification, you can see some of the triangle artifacts from the underlying grid, but even so the islands are able to form some interesting shapes.  I can use smoothing (as I do on the current maps) to remove some of the more obvious triangle artifacts.  At the default magnification this provides a less jagged coastline, but also removes some fine detail:

I'll probably have to tune that to find a good middle ground.  More on that next time!

Barrier Islands Revisited

One of my motivations for rewriting Dragons Abound so that land masses don't have to conform to the underlying Delauney triangulation of the world was the problems I encountered in implementing barrier islands.  Now that the rewrite is done, I want to revisit barrier islands and take advantage of the new capabilities.

Recall that barrier islands are flat or lumpy areas of sand that form by wave and tidal action parallel to the mainland coast.  That often occur in long chains that may go on for many tens of miles.  The barrier islands are often separated by small tidal inlets, and may form lagoons between the islands and the mainland.  North Carolina's Outer Banks are a typical example:

When I implemented barrier islands for Dragons Abound, I was forced to make the islands at least a couple of locations thick.  If I tried to make islands that were just one location thick, the underlying triangles become very obvious in the outline of the island:

Now that I can draw a land mass without regard to the underlying locations, I can make a thin, smooth barrier island.

My original implementation of barrier islands worked by creating an outline where I wanted the island to be, and then turned any of the underlying Delauney triangles within the outline to land.  Now that I can define land as polygons, I don't need the second step of turning on the underlying triangles.  I can just use that outline directly as the barrier island:

But as you can see, the outline I create isn't quite perfect -- it folds back on itself near the bottom end.  When you project a line in a direction as I do here to create the polygon, it can create some weird shapes.  When I was just using this as a way to locate land locations, this was irrelevant.  But now that I'm using this directly, I'm going to have to clean it up and make it look more like an island.

I do a couple of things to improve the island outline.  First of all, instead of projecting from the actual coast, I project from a smooth version of the coast that removes most of the small folds and bumps.  Second, I scan through the outline and clip away any self-intersections where the island coastline crosses itself.  Finally, I cap the ends of the islands with arcs rather than just a straight line connecting the inside to the outside.

Here is a (zoomed in) example of a cleaned up, narrow barrier island:

If you look at natural barrier islands you'll see that the outward facing sides of the islands tend to be smooth while the insides are more irregular.  Presumably these islands are mostly sand, and the wave action on the outside tends to smooth them out, while the protected insides can be more irregular.  I can simulate that by adding some noise to the inside of the barrier island profile:

Here's an example of a possible problem:

Because it was created in a narrow inlet, the barrier island is overlapping the coast.  When land is tied to the underlying locations, it isn't possible for two land masses to overlap.  (They just end up merged.)  But now that the shape of the island isn't tied to the underlying locations, I need to add some smarts to keep from getting implausible results.

The first step in improving the placement is to identify all the bays on the coastline and keep barrier islands out of the bays.  Detecting the bays uses the method I described in this post; the basic idea is to measure the sinuosity of the coastline where I'm going to place the island and avoid any spots where the sinuosity is high.  This will cause the barrier islands to largely end up on flat spots on the coastline.  There are a few other rules that help with placement.  I avoid any coastlines that are too short -- this avoids creating barrier islands off of small islands.  I also avoid overlapping any existing barrier islands.  Finally, I check to see if the barrier island overlaps with any of the existing coastlines.  If it does, I reject it.  (Alternatively, I could try merging it with the coastline.)

The one improvement I'd still like to make is to add some small breaks into the islands, similar to what happens at the south end of the North Carolina Outer Banks.  That's on the TODO list for now.

A (Not So) Minor Rewrite

I've written recently about shortcomings in my map generation caused by using Voronoi cells/Delauney triangles to define land masses.  One problem I noted when implementing barrier islands -- because land must be at least one Delauney triangle in size, barrier islands could only be made so thin.  And even with a high density of triangles, the resulting islands would be very jagged because the coastline followed the triangle edges:

Another problem was that I couldn't generate a coastline with the kind of fractal detail that you often see in maps drawn by people.  And if I did add a lot of jagged detail to the coastline, it no longer followed the land exactly, resulting in the land or the sea showing through where it shouldn't:

Here you can see spots where the land sticks out a bit past the border.

The solution to this problem is to define land (at least when drawing the map) by the space enclosed by the coastline.  This is a pretty significant change -- I rely quite heavily on the underlying grid of Delauney triangles to draw the map.  For example, I consult locations to determine the biomes, colors, and other features that should be displayed there on the map.  But using actual polygons to define land masses (even if I continue to use the underlying grid for other purposes) would bring significant benefits, so I decided to at least explore the feasibility.

(Much of the initial work for this I did on an Amtrak train ride to New Jersey, and I wasn't able to capture screenshots, so this first part will be somewhat dry.)

To begin with, I kept world generation unchanged, but as a final step I captured all the coastlines as polygons and saved them.  Initially, some of these coastlines did not form closed loops since I have avoided creating coastlines around the very edge of the map.  In the past, coastlines at the very edge of the map caused some difficulties, so I simply did not generate coastlines in those areas.  However, my work setting DA up to generate continent-sized maps removed those issues, so I was now able to modify the generation of coastlines to only create closed loops.  So now the map generates all land masses as closed-loop polygons without any holes.

Here's an example of my current approach.  The coastline follows the edges of the triangles, so each triangle falls either completely in the land or completely in the sea.  A red dot marks the center of every location that has a height greater than zero, and blue dots mark locations less than zero:

Since the coastline runs along the edges between greater than zero and less than zero, every red dot is inside the land polygon and every blue dot is outside.

When I perturb the coastline it no longer runs on the edges of the triangles.  This may result in a red dot being outside the coastline, or a blue dot inside the coastline:

Many parts of DA rely on knowing where the land and sea are, and they start to break down when the coast doesn't correspond to that split:

Here you can see how the river ends awkwardly on a non-existent coastline.

To rectify this, I want to switch over to identifying a location as “land" if it falls inside one of the land polygons.  Since the coast no longer necessarily follows the edges of the Delauney triangle, a triangle might only be partially in the land.  Rather than rely on the height in a location to decide if it is “land" or “sea" I'm now going to determine that by checking whether any part of a triangle is inside any land polygon.  In combination with this, I will mask all the land to the actual land polygons.  So even though I will paint some land locations that are outside of the actual land mass, they'll be clipped and won't show.  The trick is to include every location that has any part inside the polygon so that I get complete coverage inside.  In the following illustration, every red dot indicates a location that is at least partially within the land polygon, and every blue dot a location that is entirely outside the polygon:

Here you can see how the centers of some land locations are actually outside of the land polygon.  But crucially, none of the sea locations are inside the polygon.

However, this doesn't fix the river problem in all cases.  The river needs to be drawn past the edge of the land, so that it is clipped to the land polygon and the mouth of the river aligns with the coast.  To force the river to be drawn past the coast, I identify all the sea locations that are immediate neighbors to land locations -- I call these “coastal" locations -- and then I make sure the river extends out to a coastal region.  The result is that the river crosses the coastline and is clipped properly.  In this illustration, I've marked the coastal locations with green:

You can see the river is now clipped correctly.

With that in place, I can now experiment with making the coastline more interesting.  Here's how the coastline changes if I add a sizable amount of jitter:

This doesn't do much beyond change the shape of the coastline a little.  That's because I'm using the same line segments and just moving the endpoints around a bit.  That doesn't add any detail.  If I break the original line segments up into pieces and jitter the pieces:

The jitter adds some complexity to the coastline and oddly enough also softens it.  This is because breaking the line segments down into smaller pieces and jittering the pieces effectively creates curves.  This is a somewhat more interesting coastline, but doesn't produce the kind of fractal look I'm seeking.

Jitter moves each point randomly and independently.  It might be better to use noise to move the points around, so that nearby points move roughly together.  Octaves of noise might also help create fractal detail, as it does when creating a fractal landscape.

This certainly has a greater level of detail, but it reminds me more of a Dr. Seuss illustration than a real coastline.  There are also numerous artifacts where perturbing the coast has caused it to cross itself.

If I want a fractal coastline, perhaps I should try using a fractal generator.  There are a few articles on using fractals to generate coastlines, but nothing I can really use out of the box, so I'll have to implement it myself.

One of the simplest fractals is the Koch curve, which you've probably seen before.  The basic idea is to divide a line segment into three parts and then add a triangle to the center part.  Doing this repeatedly creates an increasingly complex shape:

Of course, this produces a perfectly regular structure, which is not what I want for a coastline, but that can probably be fixed.  So let me implement a Koch curve and apply it to a simple line segment like a bit of flat coastline:

Let's see how this looks if I vary how the line segment is split into three pieces, so that the pieces can be different sizes:

Varying the height of the bumps changes the character of the line.  With low values, the triangle becomes lower and more smooth:

Which starts to look like a coastline.  With high values a problem becomes apparent:

The line starts to overlap on itself and self-intersect.  It makes an interesting pattern but would be a problem in a coastline.

Using a negative value for the height inverts the line:

Which viewed this way looks like the silhouette of a cartoon cloud.

For my purposes, one of the most useful settings is to mix negative and positive height values, so that the fractal sometimes goes one direction and sometimes the other:

And with a lower height value:

Even this relatively unsophisticated approach looks pretty good.

Before going on, let me fix the problems that arise when the coastline self-intersects.  Trying to prevent this from happening is pretty difficult, but fixing it afterwards is straightforward.  Beginning at one end of the line, I scan ahead a segment at a time.  If the current segment intersects with a later segment in the line, I keep the intersection point and clip out everything else.

Even large height values are now okay:

Although you can see there are many spots where the line comes very close to touching itself.

At the high values, the triangle nature of the fractal is fairly evident but that can be eliminated by going deeper into the fractal (and using a thinner line to show the detail):

Before I go any further, let me try this on the coastline and see how it looks:

Well, that's disappointing.  Why did that happen?  The problem is that I'm fractalizing each segment of the coast line.  But those segments are not very long -- basically just long enough to get one triangle stuck into them -- which turns the coastline into a series of spikes/anti-spikes.  As a quick first attempt to improve this, I can use line simplification to create longer line segments on the coast:

Still rough and not quite where I want it to be, but showing enough promise to continue experimenting.

To return to the original problem of fractalizing a line, so far I've been using the Koch curve, where a part of the line is recursively replaced with a triangle (or 2/3 of a triangle).  I can change that to be a three-sided figure pretty easily:

Not unsurprisingly, this gives a more rounded fractal.  It doesn't look too bad on the map:

Increasing the number of sides quickly breaks down, because the resulting segments are too small for the next level of recursion.  The Koch triangle produces four segments of length/4.  The three-sided figure produces five segments of length/5, and so on.  With higher numbers of sides the segments quickly too small to be fractalized themselves.

Choosing a random number of sides from 2 to 4 so that each fractal varies makes the character of the curve less predictable:

So far, every recursive level of fractalization uses the same ratios of sizes.  To change that, I can borrow the notion of persistence from noise generation. With persistence, as the scale of the noise grows finer and finer, the amplitude of the noise is reduced.  If I apply that same idea here, I get a fractal line that gets smoother as the scale gets smaller:

If you compare this line to the previous one, you can see that there is similar large scale changes, but at the finer scale the line is smoother.

I can also reverse the persistence, so that at a large scale the line doesn't change as much, but there is added detail at a lower level:

Here the line is closer to the original straight line, but with strong fine detail.  This seems like it might be useful for coastlines, so that the fractalization doesn't wander too far from the original line, but still adds detail.

A limiting factor in my implementation so far is that the fractalization part only works on line segments, so when I apply it to the coastline I have to essentially throw out the existing detail and just treat that section of coastline as a straight line.  If I set the fractalization low, it's obvious that the coastline is being reduced to low resolution segments:

I call this the Picasso map.

So how can I avoid turning everything into straight lines?  In the Koch curve, the fractalization is caused by adding (two sides of) a triangle to a straight line.  I need a way to add a triangle to an arbitrary polyline.

You can think of adding the triangle to the straight line as offsetting a point in the middle of the line perpendicular to the line:

So if I want to do this to an arbitrary polyline, I need to offset perpendicular to the polyline.  In the case of a polyline, I don't have just a single line for the whole offset area, so I need to be able to offset by the perpendicular all along the polyline -- the perpendicular will keep changing.  I also need to know how far to offset along the perpendicular at any point:

So this triangle offset can be looked at as a pattern of offsets to the perpendicular by different amounts.  I'll turn the triangle offset into a pattern for the fractalization that tells me how far to offset given how far along the line I'm at -- then when I want to offset a point that is (say) 37% along the length of an arbitrary polyline I can look at a point that is 37% along the length of my fractalization pattern, find the Y value at that point, and then use that to control how far I offset the point in my polyline.

So what does it look like to apply this to a polyline rather than a line segment?  Here's a curved polyline:

And here's the same polyline after adding a triangle to it:

As you might expect, it is taller and more pointed.  That's perhaps not too interesting, but here's what it looks like if the fractalization is recursively applied (and allowed to randomly switch between negative and positive):

Since I didn't have to turn the line into a straight line, it has retained much of it's original shape.  So now I can apply fractalization to an arbitrary polyline.  Here's an example of this applied to a coastline:

The red line shows the original coastline before fractalization was applied.  You can see that unlike the Picasso Map, the original coastline did not need to be reduced to long straight lines before fractalization.   You can also see that the fractalization has made significant changes in the coastline -- eliminating big sections of land in some areas and adding some in other areas.

Now that fractalization of arbitrary coastlines is working, I want to add the capability to vary the roughness of the fractalization across the map, so that I can have smooth coastlines in some places and rough coastlines in other places.  This is evident in many real world places.  A good example is Ireland, which has a rough Western coast and a smooth Eastern coast:
Ireland's Western coast is probably rougher because it faces into the North Atlantic.  I could link this effect to ocean currents or something similar on my maps, but for a first approximation I'll just use a noise function to smoothly control the roughness of the coastline.  This view shows the original coastline in red and then the “fractalized" coastline in black underneath:

In this example, you can see that the fractalized shore follows the original coastline closely around 9 o'clock on the island, but up around 1 o'clock the shore is much rougher and deviates from the original shore quite a bit. Here's what the fractalized coasts look like on a map:

This isn't quite the look I'm aiming for, so I'm probably going to revisit this with a different approach, but it's not entirely bad.  I like very much that the coast is smooth in some places and rough in others; that's a feature I will try to maintain.