Monday, November 5, 2018

Continent Maps (Part 3): Land Shapes

With the various changes from the last posting implemented, I'm now able to generate worlds that are considerably bigger than previously -- up to at least 8x the size of the original worlds -- and save them as big image files:
(You can click through to see the full-sized 4800x2400 version on Flickr.)

I'm generating these maps using the same procedural generation for the region sized maps.  The map above has a pretty reasonable continent shape, and some interesting outlying islands. However, that's mostly luck.  Here's another map:
This map is just a mess of islands and a Swiss cheese landmass.

Here's another example, that's somewhere between the other two maps.  It's not entirely realistic, but it might be interesting for a fantasy setting:
This has a large continent land mass, but there are some pretty odd land shapes and overall doesn't look completely “real."  (Although that might be something some people want in a fantasy map.)  So what shape(s) should a “world" map have?

The majority of fantasy world maps I see depict either a large, island continent (with small islands around it), such as this map of Andelen:

Or an “arm" of a continent, as in this map of Angorun:
Occasionally there is a map that is all land, or several island continents, but these are rather the exception to the rule.

First, let me see about generating “island" continents.  As it turns out, DA already has a function that generates a large central island on a map, and it's aware of the map size as well, so it should work to create the main continent shape.  Some noise and secondary islands should take care of the rest.
(Sorry, no full-size versions of these examples.)  I wasn't expecting the big central sea on this map, but it's a fine surprise.  Here's another example:
One problem with the central island function is that it starts with a circle, which works fine on the square maps I've been showing, but not so well on maps that are rectangular.  (Following examples with low amounts of perturbation to show the basic shapes more clearly.)
That's easily corrected by masking the land with a (perturbed) ellipse taken from the map's dimensions instead of a circle:
These central islands are scaled to fill the map, but in many cases for continent-sized maps we'll want to leave some “border" around the continent.  Two parameters control how much the island fills the map in the X and Y directions.

Here's the same border control with more reasonable perturbation:
You can see that the east and west ends of the map remain ocean.  (This map has a larger view to click through.)  This means the map could show an entire world (and wrap from right to left) or if a portion of a world, could be connected to another map that also has ocean along the appropriate edge.

The keen-eyed who clicked through on the previous map will notice that the ocean and land patterns stop halfway across the map.  Previously I've only had 1x1 maps, and the ocean and land patterns were sized to fit on those maps.  With bigger maps I have to manually tile the patterns across the map, so I added that.  (SVG has a way to tile a pattern, but it has a bug in Chrome so I can't use it.)  This is a nice feature, because I can now use smaller land and ocean patterns and they'll tile automatically.  Not sure why I didn't think to implement this previously!

Now that island continents are working okay, let me move on to implementing “arm" continents -- maps where the continent comes into the map from the edge.
In this case, the continent wraps off on three of the edges.  But the primary feature of these sorts of maps is that there is a substantial land connection between the continent depicted on the map and land off the edges of the map.

The easiest way to ensure this sort of off-map connection is to set the sea level low during generation.  This increases the land area depicted on the map, which increases the chance that there will be a large land mass, and increases the chance that there will be land (and not sea) on the edges of the map.
Of course, that's not a guarantee that the land mass will be very interesting or even a single mass:
One way to create the semblance of a single continent is to use the same island continent generation I used above, but offset the island toward an edge of the map.  That gives us something like this:
You can see how the main continent is (primarily) a central island that has been shifted up and right.  Since this is a continent and doesn't need to retain a strict island shape, I can allow more perturbation of the shape as well.
Obviously there are (many!) other approaches to generating terrain but these two will at least give me the ability to generate the most common continent-sized land shapes.

The keen-eyed reader might have noticed the odd, stripey forest shapes on many of the continent-sized maps.  Next time I'll start tackling some problems in the wind and biome models that cause that problem.

Tuesday, October 30, 2018

Continent Maps (Part 2): Getting Consistent Views

In the last posting, I explored the coordinate systems and learned how to slide the SVG viewport around to show only part of a larger world.  However, there were some problems with that, because up until now I've assumed that anything not visible is irrelevant.  In this posting, I'm going to go through and fix those assumptions so that I can consistently generate and view different portions of a larger map.

The problem with place names that I pointed out in the last posting is evident in these two views of the same map:
 Here's the same world, with the view slid to the left:
You can see the geography is the same, but many of the names have changed.  That's because Dragons Abound doesn't bother to name anything that isn't visible.  Since different things are visible in the two views, and the naming process is driven by random numbers, different names result.

After looking through the code, I discovered that almost everything is being named whether it is visible or not.  But it only takes one exception to throw off the naming of everything that follows.  In this case, the exception is that Dragons Abound is only generating the coastlines that are visible.  The reason for this is convoluted.  There's actually a “coastline" along the entire edge of the world, which -- since it encloses the entire world -- breaks some of the program logic if I actually create that coastline.  To avoid that from happening I've just generated the visible coastlines.  Now that the map can extend far beyond the edge of the viewport, that's not a good solution.  Instead, I need to stop generating coastlines when I get near the real edge of the map.  (Which I still keep off-screen to avoid showing edge-effect problems.)

With that fixed, the names are now consistent across the two maps:
One thing to note for the future:  If I use the interaction capability to change the name of a map feature, that change won't be recreated on a different view, and probably won't even be reproducible.  Something to think about.

If you look closely at the previous map, you'll see that an ocean area near the bottom center of the map has a label “Meb Island" floating in it.  That happened because Dragons Abound thinks the ocean area is actually an island.  Without going into all the technical details, it's surprisingly tricky to distinguish between islands and lakes when they run off the edge of the map.  At any rate, the algorithm is getting confused by the change I made above in generating the non-visible coastlines and needs a little fixing to avoid this sort of problem.

Now let me try quadrupling the size of the world and show 1/4 of it in a map view:
In general this looks okay (and has a big interesting river system, and a big lake, but you might notice that the cities seem very sparse.  That's because Dragons Abound generates a range of 10-20 cities.  That range works well for the original size world, but not so well when the world size is quadrupled.  So the range needs to be adjusted for the relative size of the world.  There are probably a number of areas where this needs to be done.

Here is the same map with that problem fixed:
Now there are a more reasonable number of towns and cities, but this reveals another problem.  You can note a number of orphaned names around the edge of the map, like Nanmrummombrook, Marwynnley and Noyewood in the lower left.  This happens because label placement tries to place labels where they are visible.  Previously, that routine has never had to worry about a label for a feature being off-screen, because in the regional maps almost the whole world is visible.  But now there can be cities and other features just off-screen.  So I need to add some logic to the labeling routine so that it doesn't try to create labels for map features that aren't visible.
That's more reasonable.  On the right edge, Cumden is just barely on the map but the label is still placed where it is visible.

One thing that might not be immediately obvious in the bigger maps is that the number of locations in the world hasn't changed.  Although the map is (in some sense) 4 times as big, the underlying area is still chopped up into the same number of locations.  The initial step in map generation is to cover the world with a Voronoi diagram with a fixed number of locations.  So as the map gets bigger, each Voronoi cell gets bigger as well.

It makes sense to scale the number of locations with the map size, but unfortunately, the performance of Dragons Abound is somewhat worse than linear with the number of locations in the world, so generating maps with a large number of locations can take a long time.  Here's an example of a map with 4x the resolution (number of locations) as the map above:
The added locations change the generation process, so the terrain isn't the same as the above maps, but you may notice the added detail in the coastlines and the land shadows.

Fortunately, when profiling the performance in generating bigger maps, I noticed some obvious problems that were using a lot of processor time.  Some debugging time later, I've fixed the worst offenders, and that allows me to make some bigger maps.  Here's an entire 4x map:
This is effectively zoomed out to 25% size.  This seems to be about the maximum size map that Chrome can display.  The world generation can handle larger maps but the browser crashes when trying to display them.  Firefox seems more capable in this regard; it can display maps up to 9 times the size of my original maps.  Here's a portion of such a map -- I've left it full size, so you can click through to get a better notion of the size and detail of the map.
Firefox can generate a map this big, but I can only screen capture a picture at the maximum browser window size.  I've got a function to save the map as a PNG file, but it can also only save the portion of the map that is being displayed.  I suppose I could scroll the map, capture multiple screens and stitch them all together, but that's a pain.

A better solution would be to save the underlying SVG and then open it in a program like Inkscape.
In the past I've been able to cut & paste the SVG for a map into Inkscape, but the SVG for the world maps is so big that trying to cut & paste it crashes the browser!  Fortunately, I found FileSaver.js and I can use that to save the SVG directly to a file, and then open it in Inkscape and create a very big image that way.

Or at least in theory.  There are a couple of challenges in getting these maps working in Inkscape.

The first problem is that Inkscape makes a few different assumptions from Chrome & Firefox about how to display SVG.  Specifically, if a path doesn't have a fill color specified, the browsers assume that it has no fill; Inkscape assumes that it is filled with black.  So when I open a saved SVG in Inkscape it is mostly black because the top-most layer in the map doesn't have a fill color.  This can be fixed by specifying “fill: none" where needed so that paths display the same in the browser and Inkscape.

The second problem is that Inkscape has some bugs in how it handles masks.  Apparently Inkscape itself only creates masks with a single element, and doesn't handle masks with multiple elements very well.  Dragons Abound creates a number of masks with multiple elements.  The workaround for that problem is to group all the elements in each Dragons Abound mask into a single (unnecessary) “group" element.

The third problem has to do with images and other loaded resources.  These are referenced in the original SVG by a relative path, e.g., “images/background0.png."  My sources are then organized so that the little standalone webserver I use can find those resources in the specified places.  When I take that same SVG and open it in Inkscape, those relative paths are now treated as “file:" URLs and Inkscape looks for the resources relative to the folder where the SVG was saved.  The easy workaround here is to save SVGs into a folder that has the resources in the correct places; this could be the same root folder used by the webserver or a different location that has copies of the resources in the same (relative) locations.

The fourth problem is fonts.  Dragons Abound uses both web fonts and locally stored fonts, all in WOFF2 format.  In the browser, these are applied to text by using a CSS “font-family" style, and before the map is generated, all the possible fonts are loaded into the Web page to be ready to use.  When the same file is opened in Dragons Abound, it looks for fonts in the system font directory, and there doesn't seem to be any way to specify another font directory.  The easy solution (at least for my development machine) is to install the fonts Dragons Abound uses into the system font directory, although this isn't as trivial as it sounds, because the font names much match and there isn't any easy way to change the name of a font in Windows.  But of course, this won't work on any computer that doesn't have the proper fonts installed.  A more portable solution is to embed the SVG fonts into the maps.  This goes onto the TODO list.

After all this, I end up with this interface to the map generation:
The Extent input boxes set the overall size of the world, where 1x1 is (arbitrarily) the size of the original maps.  The vbx (viewbox) size defines how big a piece of the world to show in the map; in this case it is also set to 1x1 so the map will portray the entire world.  The vbx center defines where in the world to center the map; 0, 0 is the center of the world.  Finally, the SVG size parameter controls how many screen pixels to use for 1 unit of viewbox size; set to 775 this makes the displayed 1x1 map on the screen take up 775x775 pixels.  This is handy when I create a very large map.  By setting this parameter to a low value (say 150 pixels) I can make a large map fit entirely on the screen.

By varying these six parameters I have control over the size of the world and the portion of the world to display in the map.  The Generate button does what you'd think; the Display button below it does just the displaying the world part, so that I can generate a world and then display different parts of it by changing the viewbox parameters without having to regenerate the world.  (A better programmer would probably implement this all as pan & zoom.)  The Save PNG button saves the visible map as a PNG file; the Save SVG button saves the SVG for the entire map.  The Test It button is set up to run test code that varies as I develop different features.

Now that I can generate and display all or part of a bigger world, next time I will look at adapting the land shapes to bigger maps.

Tuesday, October 23, 2018

Continent Maps (Part 1): SVG and Coordinate Systems

Up until now, the size of maps in Dragons Abound have been fixed and somewhat indeterminate.  They are what I think of as “regional" scale maps -- not a whole world map, but a significant chunk, like the west coast of the United States, or a part of Europe.  I like this scale quite a bit, but I want to do some experimenting with Dragons Abound to see if I can generate world-sized maps (or at least bigger than the regional maps I currently generate).  But before I start into that, a little digression on fantasy world maps.

When you stop to think about it, the world is a big place.  Most fantasy “world" maps are nowhere near the proper size.  Consider, for example, Middle-Earth, the setting of Lord of the Rings:

While seemingly depicting a huge world, in fact Middle Earth is based upon Europe:
which means a real “world" map of Tolkien's world would be about 50x the size of the Middle Earth map (!).  In fact, most fantasy world maps I see depict what seems to be about a continent or so of the world:
That seems to be about the biggest area that depicts well in fantasy map style.

So generating a real “world map" is probably too ambitious.  A better target would be a continent (or partial continent) sized map.  (Although it's convenient to still think of this as “world" sized.)  So how big a map would that be? If the current Dragons Abound maps are “sub-continent" size, this suggests that I might want to be generating maps that are 8-10x as large.

Before I jump into the challenge of generating bigger maps, I need to have a better understanding of the different coordinate systems Dragons Abound uses.  I inherited multiple coordinate systems from Martin O'Leary's original code, and their interactions can be confusing, even after working with them for two years.  Mostly I've gotten away with not fiddling with them, but obviously I'm going to have to do that to generate bigger maps.

To start with, the “world" behind the regional map is currently generated within a unit square.  Each regional map has locations from (-0.5, -0.5) to (0.5, 0.5) with the origin (0,0) in the middle of the region.
The one oddity here is that the Y axis is reversed from what you saw in high school geometry.  -0.5 is at the top of the map and 0.5 at the bottom.  The Y axis is often reversed in computer graphics.  I've heard this explained as an artifact of how early monitors (TVs) scanned from top to bottom, so the first scan line was at the top, the next just below it and so on, so the Y index of the scan lines went from zero at the top to some positive number at the bottom.  Whatever the reason, SVG (Scalable Vector Graphics) uses this coordinate scheme, so Dragons Abound does as well.

This coordinate system is independent of how the map will be displayed.  It's just a unitless system for constructing the world -- a city is located at (0.12875, -0.223), a border runs from (0.337, 0.010) to (0.333, 0.017), etc.  And while the current regional maps are limited to 0.5 to -0.5, that's not a limit on this coordinate system.  I can create world outside of these limits.

The next coordinate system is what SVG calls the viewbox.  This establishes the actual coordinates that will be used to draw the graphics.  For example, Dragons Abound sets the viewbox to start at (-500, -500) and have a width of 1000 and a height of 1000:
(Upon review, the number at the top of the Y axis should be -500.  Sorry for the typo.)

You'll note that with this choice, converting between the first coordinate system and the second system just involves multiplying everything by 1000.  So to draw something, Dragons Abound finds its location coordinates, multiplies by 1000, and draws to those SVG coordinates.

So I can use the viewbox coordinates to draw a line from (say) (0, 0) to (250, 250).  But I don't really want that to draw a line from (0, 0) to (250, 250) on the computer screen.  For one thing, that would mean that if I wanted to display the map at a different point on the screen, I'd have to change all the coordinates of everything on the map and redraw it.  That would be painful.

To handle where the graphics show up on the screen, there's a third coordinate system which SVG calls the viewport.  The viewport is the actual part of the page where the graphics will be drawn (on a web page, it's an <svg> element).  It has a width and a height and a location.  The location is the coordinates of the upper-left corner of the viewport.  So if I was displaying a map in a viewport at (30, 100) that had a height and width of 800, the viewport coordinate system would look like this:
In SVG, the viewbox and viewport coordinate systems are connected to each other, and SVG takes care of translating between them.  You just draw into the viewbox coordinate system, and what you draw shows up in the corresponding place in the viewport.  (There are some problems when you create a viewbox and viewport that don't have the same aspect ratio.  Then things either get clipped or stretched to fit, depending upon your choice of the preserveAspectRatio attribute.  I just recommend not doing that in the first place.) 

So to recap:  A city located in the world at (0.10, 0.33) is drawn at (100, 330) and shows up on the screen at (110, 764).

You can see why keeping track of this can be confusing!

What happens if I change each of these coordinate systems?  In the first coordinate system, suppose I generate a world that only goes from -0.25 to 0.25 in each axis.  Then the resulting world is only a quarter the size of my usual world and only fills up the middle part of the entire viewport:
(You can also see a few weird edge artifacts that are normally hidden.)  Likewise, if I double the size of the first coordinate system, there's a lot of map that isn't seen because it is outside the edge of the viewport.

What happens if I double the size of the viewbox?  Well, if I also double the ratio between first coordinate system and the viewbox (from 1000 to 2000), then nothing much happens.  If I keep the ratio at 1000, then once again the map is reduced to half size.
However, this time the map has the original area 1x1.  Again you can see edge artifacts that are normally hidden (like the bulbous sides of the forests).  You can also see that the ocean pattern is not correct -- it must have hard-coded some assumptions about the viewbox size.  Likewise, the compass seems to be finding the corner of the viewbox, rather than the corner of the map.

Conversely, if I halve the viewbox size, it has the effect of zooming in on the map:
Here we see only the middle quarter of the map.  This isn't a very useful way to zoom, because you can see that having only half the map visible creates some problems -- the marker for the city “South Owenson" is off screen, for example.  It also effectively doubles the size of fonts, etc., which I probably don't want.

A more useful aspect of viewbox is to change the origin.  So far, I have kept the viewbox centered on the map, but that's not required.  For example, I can shift the map to the right by centering the viewbox on a point on the left side of the map:
Again, you can see edge effects and some other problems, but effectively the map has been slid over to the right.  The usefulness of this may not be obvious, but suppose I generate a map that is twice the width of the normal map.  By default it looks like this:
This looks like any other map, but it's actually only the center part of a bigger map.  So I can now adjust the viewbox to bring other parts of the map into view:
Here I've slid the viewpoint to the left, so we see more of the world to the west of the original view.  Some names have changed on the map, because Dragons Abound currently does some things (like naming features) based upon whether they're visible.  I'll need to change that to keep the map consistent when sliding the viewbox around.  Eventually, though, I'll be able to slide the viewbox around a bigger map and generate regional maps of any desired area.  So I can generate and display a large continent-sized map, but I can also generate regional maps of areas within the larger map.

To summarize, then.  There are three coordinate systems in use.  The first is an abstract coordinate system for the world features.  The second is the viewbox, and it defines the portion of the world that is visible.  The third is the viewport, and that controls where on the screen the map is drawn.  To draw a bigger world, I need to expand the first coordinate system.  To show more on the screen, I need to expand the viewbox.  I can also slide the viewbox around to show different parts of a larger world.

Next time I'll work on fixing some of the inconsistencies that arise when I use the viewport to show only part of a larger map.

Tuesday, October 16, 2018

Sprucing up the Rivers

There are a few problems with the way Dragons Abound draws rivers, and in this posting I'm going to try to fix up some of them.

First of all, I realized recently that I'm still drawing rivers using SVG lines, and changing the width of the river by adjusting the width of the line.  In extreme cases this can result in some odd effects:

And in fact, I've had to add code to avoid these kinds of situations.  But some time ago, I implemented a different way of drawing lines that lets me smoothly vary the width of the line any way I'd like.  But for some reason I'd never switched over rivers to using the new line routines, so let me do that and see whether it improves the river visualization.
Here's a side-by-side comparison with the old version on the left and the new version on the right.  If you look carefully you can see that the transitions are smoother and more natural in the new version.  This is most noticeable in places like the fork where there are some sharp changes of direction.  With the new version, I also have better control over the quality of the path drawing, so I can vary it between smooth and rough as I desire.

That's a small improvement, but the real reason to switch to the new lines is to address the starts (and ends) of rivers:
Rivers start in the mountains and flow downhill to end at the coast.  As you can see in this screenshot, the start of the river is pretty abrupt.  It just starts at a minimum width, and if the river has an outline (as in this example), the outline is missing across the start of the river.  (Rivers have a minimum width to avoid having rivers that are nearly-invisible thin lines.)  This is largely an artifact of the old way of drawing the river, and would have been annoying to fix.  With the new river code, though, I can just set the initial width of the river to zero, so that the river starts with a point:
That works, but looks a little pinched off.  Let me try phasing in the river over the first part of the river:
Now the river starts at a point and then gradually increases to the minimum width.  That looks much nicer.

Another problem area is at the mouth of a river where it joins the sea.  If the land has an outline then it cuts off the river, as you can see in the map above.  I don't think that looks very good, but it's a problem I also see on a lot of my reference maps:
If you look at the river right below the city of Avinnor at the top of the map, you'll see the land outline goes right across the mouth of the river.  So this is something people struggle with too.

The obvious fix would be to draw the river on top of the land outline.  The problem with doing this is that it is hard to end the river exactly where the ocean starts without leaving a gap or an overlap.  So to avoid this, I have been drawing the river a little long and then drawing the ocean on top of the river.  This eliminates any potential gaps.  For similar reasons, the land outline needs to be on top of both the ocean and the land.  So I cannot put the river on top of the land outline without causing a problem where the river meets the ocean.

One solution is to mask out the land outline where the river crosses it.  This is fairly straightforward -- I just need to draw the river a second time in black into a mask, and then apply that mask to the land outline.  If the river has a black outline like the land outline, this works pretty well:
The transition is more abrupt than I'd like, though.  I can address that by broadening out the river where it joins the ocean.
That looks pretty good.  It looks even better when the weight of the coastline is closer to the weight of the river border:
I see a similar treatment on a lot of my reference maps:
Unfortunately, it doesn't look as good when the outline color of the river doesn't match the outline color of the land:
What I'd like to do in this situation is start the river outline as the same color as the land outline and then use a gradient to transition to the river outline color.  Unfortunately, that's not easily done as SVG doesn't provide gradients that follow a path.  There some ugly workarounds, but I'll leave that for another day.

As I discovered while working on the Tolkien-style map, this approach to drawing the river mouth turns out to be exactly backwards for a style which uses a solid black river:
Masking out the coastline at a river mouth with a black river ends up creating an unnatural gap.  In this case I want to turn the mask off and leave a solid coastline.
Dragons Abound has many ways to style every part of the map, and that creates lots of edge cases to make things look good!

There's at least one more improvement I'd like to make to rivers, but I'll leave that for another time.