2016-08-16 Alpine Map Generator

I’ve been working on the Alpine map generator some more. It uses Text Mapper to render the output into an SVG image and it uses the Gnomeyland icons by Greg MacKenzie so it looks nice. Sadly, I’ve developed a pathetic obsession about getting it “right”. To illustrate my obsession and to help me fight it, let me document what I’m talking about. This is a “bug” I just fixed.

Here’s the old map:

The old map

What’s wrong you ask? I was confused by the canyon carved into the mountains from lake 17.04. I expected it to flow into 18.05. Let’s check the height map before lakes start flooding, looking for an outlet:

The initial setup with arrows pointing where the water wants to flow

Why would the river flow from 16.03 (height 7) to 15.04 (height 9)? This makes no sense.

So I studied my debug logs:

Lake started with 1704
Candidates: 1704
Looking at candidate 1704
River now: 1704
A neighbor of 1704 is 1804 with target 1704
Adding 1804 to our lake because it empties into our lake; the river leading here: 1704 1804
A neighbor of 1704 is 1603 with target 1704
Adding 1603 to our lake because it empties into our lake; the river leading here: 1704 1603
A neighbor of 1704 is 1803 with target 1704
Adding 1803 to our lake because it empties into our lake; the river leading here: 1704 1803
A neighbor of 1704 is 1703 with target 1704
Adding 1703 to our lake because it empties into our lake; the river leading here: 1704 1703
A neighbor of 1704 is 1705 with target 1704
Adding 1705 to our lake because it empties into our lake; the river leading here: 1704 1705
A neighbor of 1704 is 1604 with target 1704
Adding 1604 to our lake because it empties into our lake; the river leading here: 1704 1604
Candidates: 1804 1603 1803 1703 1705 1604
Looking at candidate 1804
River now: 1704 1804
Adding lake 1805 to our candidates: 1603 1803 1703 1705 1604 1805
A neighbor of 1804 is 1905 with target 1805
Adding 1905 to our lake because it empties into our lake; the river leading here: 1704 1804 1905
A neighbor of 1804 is 1904 with target 1803
Adding 1904 to our lake because it empties into our lake; the river leading here: 1704 1804 1904
Candidates: 1805 1603 1803 1703 1705 1905 1604 1904
Looking at candidate 1603
River now: 1704 1603
A neighbor of 1603 is 1602 with target 1702
Adding 1602 and 1702 to our lake, but need to explore
We flowed back into the lake via 1704 1603 1602 1702 1703
... 1702 is a new candidate with river: 1704 1603 1602 1702
... 1602 is a new candidate with river: 1704 1603 1602
Back at 1603 with river 1704 1603
A neighbor of 1603 is 1504 with target 1505
Adding 1504 and 1505 to our lake, but need to explore
Adding 1506 to our lake and keep exploring
Adding 1606 to our lake and keep exploring
Adding 1707 to our lake and keep exploring
Adding 1807 to our lake and keep exploring
Adding 1808 to our lake and keep exploring
Adding 1909 to our lake and keep exploring
Adding 2009 to our lake and keep exploring
Adding 2010 to our lake and keep exploring
Adding 2110 to our lake and keep exploring
Adding 2210 to our lake and keep exploring
Adding 2211 to our lake and keep exploring
Adding 2212 to our lake and keep exploring
Adding 2313 to our lake and keep exploring
Adding 2413 to our lake and keep exploring
Adding 2514 to our lake and keep exploring
Adding 2614 to our lake and keep exploring
Adding 2715 to our lake and keep exploring
Adding 2716 to our lake and keep exploring
Adding 2816 to our lake and keep exploring
Adding 2817 to our lake and keep exploring
Adding 2918 to our lake and keep exploring
Adding 2919 to our lake and keep exploring
Adding 3019 to our lake and keep exploring
Adding 3120 to our lake and keep exploring
Adding 3220 to our lake and keep exploring
We left the map via 1704 1603 1504 1505 1506 1606 1707 1807 1808 1909 2009 2010 2110 2210 2211 2212 2313 2413 2514 2614 2715 2716 2816 2817 2918 2919 3019 3120 3220
Arrows for 1704 should now point to 1603
Arrows for 1603 should now point to 1504

The key is the list of candidates after looking at the first round of neighbors: 1804 1603 1803 1703 1705 1604. These are sorted by height, 16.04 is last, which is great. But it also means that 16.03 (wrong direction: east into the mountains) is the equivalent of 17.05 and 18.04 (south east, towards lake 18.05).

Clearly, I needed a better sorting algorithm for the next candidates to look for: the candidates at the same level needed to be sorted by their lowest neighbor which had not already been looked at.

A bit later:

Lake started with 1704
Candidates: 1704
Looking at candidate 1704
River now: 1704
A neighbor of 1704 is 1803 with target 1704
Adding 1803 to our lake because it empties into our lake; the river leading here: 1704 1803
A neighbor of 1704 is 1804 with target 1704
Adding 1804 to our lake because it empties into our lake; the river leading here: 1704 1804
A neighbor of 1704 is 1705 with target 1704
Adding 1705 to our lake because it empties into our lake; the river leading here: 1704 1705
A neighbor of 1704 is 1703 with target 1704
Adding 1703 to our lake because it empties into our lake; the river leading here: 1704 1703
A neighbor of 1704 is 1603 with target 1704
Adding 1603 to our lake because it empties into our lake; the river leading here: 1704 1603
A neighbor of 1704 is 1604 with target 1704
Adding 1604 to our lake because it empties into our lake; the river leading here: 1704 1604
lowest neighbor of 1703 is 1702
lowest neighbor of 1703 is 1702
lowest neighbor of 1703 is 1702
Candidates: 1804 1705 1703 1803 1603 1604
Looking at candidate 1804
River now: 1704 1804
Adding lake 1805 to our candidates: 1705 1703 1803 1603 1604 1805
A neighbor of 1804 is 1905 with target 1805
Adding 1905 to our lake because it empties into our lake; the river leading here: 1704 1804 1905
A neighbor of 1804 is 1904 with target 1803
Adding 1904 to our lake because it empties into our lake; the river leading here: 1704 1804 1904
lowest neighbor of 1703 is 1702
lowest neighbor of 1703 is 1702
lowest neighbor of 1703 is 1702
Candidates: 1805 1705 1703 1905 1803 1603 1604 1904
Looking at candidate 1705
River now: 1704 1705
A neighbor of 1705 is 1706 with target 1707
Adding 1706 and 1707 to our lake, but need to explore
Adding 1807 to our lake and keep exploring
Adding 1808 to our lake and keep exploring
Adding 1909 to our lake and keep exploring
Adding 2009 to our lake and keep exploring
Adding 2010 to our lake and keep exploring
Adding 2110 to our lake and keep exploring
Adding 2210 to our lake and keep exploring
Adding 2211 to our lake and keep exploring
Adding 2212 to our lake and keep exploring
Adding 2313 to our lake and keep exploring
Adding 2413 to our lake and keep exploring
Adding 2514 to our lake and keep exploring
Adding 2614 to our lake and keep exploring
Adding 2715 to our lake and keep exploring
Adding 2815 to our lake and keep exploring
Adding 2816 to our lake and keep exploring
Adding 2917 to our lake and keep exploring
Adding 2918 to our lake and keep exploring
Adding 2919 to our lake and keep exploring
Adding 3019 to our lake and keep exploring
Adding 3120 to our lake and keep exploring
Adding 3220 to our lake and keep exploring
We left the map via 1704 1705 1706 1707 1807 1808 1909 2009 2010 2110 2210 2211 2212 2313 2413 2514 2614 2715 2815 2816 2917 2918 2919 3019 3120 3220
Arrows for 1704 should now point to 1705
Arrows for 1705 should now point to 1706

1804 1705 1703 1803 1603 1604 is the correct sorting order. 18.04 and 17.05 are at the front and the southern passage is discovered.

Notice my additional debug message I needed to check that for hex 17.03 the neighbor 17.04 is not checked. It would be the lowest neighbor indeed but we have already looked at it, so we need to ignore it. By the time we’re looking at 17.03, only the three northern hexes are options and 17.02 is indeed the lowest neighbor.

So now, since 18.04 and 17.05 are equally likely, the algorithm picked 17.05 and lake 17.04 doesn’t flow into lake 18.05 but their rivers meet in 17.06 and I think the map is much better, now. Here’s the corrected water flow map:

Correcting the flow of water

And with this correction, the final map also looks different. No more canyon into the mountains!

The new map

Now I get the urge to draw lines indicating the water divides. Noooo! :)

And just in case I make further changes to the algorithm, here’s what the application would generate right now for this width, height, and seed.

Time passes and I’ve spotted another problem in the map above. Take a look at lake 34.05 which drains through one of the highest peaks in the area, 35.07. How on earth did that happen?

We need to look at the earlier maps again. Before the flood processor kicks in we can already see that any water on the peak 35.07 will immediately drain into lake 37.09.

So, the algorithm goes:

  1. look at all the neighbors of 34.05. None look very exciting, they all drain back into 34.05.
  2. look at our neighbors’ neighbors; ignore the two white fields, focus on the light gray ones, e.g. 34.06.
  3. all its neighbors drain back into the lake with the exception of our peak, 35.07; and with that, we found our lake 37.09
  4. looking at all our candidates, lake 37.09 looks like the most promising, since it lies lower than any of the candidates

And that explains it. The problem seems to be that once we are looking at a candidate like 34.06, we’ll evaluate all its neighbors, even the very high ones like 37.09, even if a candidate of similar height like 35.05 has a much better neighbor like 36.05 which would drain off to the north west.

My algorithm is not enough breadth first like water would be.

More tinkering ahead, I can feel it!

Tags:

Comments

Algorithm changed to be totally breadth first. I’m not sure it is better. :)

– Alex Schroeder 2016-08-17 13:24 UTC


Please make sure you contribute only your own work, or work licensed under the GNU Free Documentation License. Note: in order to facilitate peer review and fight vandalism, we will store your IP number for a number of days. See Privacy Policy for more information. See Info for text formatting rules. You can edit the comment page if you need to fix typos. You can subscribe to new comments by email without leaving a comment.

To save this page you must answer this question:

Please say HELLO.