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:
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:
And with this correction, the final map also looks different. No more canyon into the mountains!
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!
#RPG #Hex #Maps #Text Mapper
(Please contact me if you want to remove your comment.)
⁂
Algorithm changed to be totally breadth first. I’m not sure it is better. 😄
– Alex Schroeder 2016-08-17 13:24 UTC
