Pixel details
Up until now, land has been land, and water has been water. To create more believable maps, with further customization possibilities, that sadly does not suffice. The filters that are being applied need more details about the geography to make smart decisions. I've added a few "Scanning" filters that basically tags each pixel in the map with additional information. Now each pixel knows the following:
- What is my altitude? Am I above or below sealevel?
- Am I in a river?
- Am I on land, but next to a river? (A riverbank)
- Am I along a coastline?
- Am I in a lake?
- Am I in an ocean?
Smarter Cities
Previously, when I generated city names, I had no way of making sure that the city names were fitting for their location. Now I can make sure that City 1 should be along the coast. Since I know this, the city name generator can now delegate its work to the specialized coastal-city name generator. No longer will the super-secret city of the pirates "Skullport" be located way up in the mountains :)
I would recommend (if you're not already doing it) that all of your "how am I positioned relative to water" questions could be answered with one or a few metrics: distance from the sea and (possibly) distance from potable water and distance from navigable water. All of the others can be based on these simple metrics and they are straightforward to compute ("Distance Transform of Sampled Functions" by Felzenszwalb and Huttenlocher is an excellent paper for this purpose).
ReplyDeleteThe pirate city of Skullport really could be in the mountains if there's a navigable waterway...
Very interesting article. I'll have to read it more thoroughly to make an informed comment, but my initial reaction is that this is something that would come in addition to what I already have. I am striving to keep the data array holding the pixel information as small as possible, but a few values indicating values that hold distance to sea/lakes/rivers is definitely something very interesting, and worth looking into. So thanks for this feedback :)
ReplyDeleteFor heightfield-based mapmaking, I have found that it's really hard to overstate how useful the distance transform is. Nearly as useful is a pit-filler like that of "A fast, simple and versatile algorithm to fill the depressions of digital elevation models." by Planchon, O. and Darboux, F., 2001. Next on the list that I use is a per-pixel gradient map: summing the upstream gradients at each pixel gives the potential flow at each point and following the largest potential flows gives "rivers". For reasonably-sized surfaces, that's only a few more maps and they can often be calculated once, used, and the discarded.
ReplyDeleteHi,
ReplyDeleteI tried using both some DEM algorithms (not exactly the one you mention though), and the exact approach to creating rivers that you suggest here. What I learned is that they work very well with small maps, but I had problems managing RAM usage, Stack overflows (in the recursive algorithms), and poor performance when the maps grow large. When I work with 8192*8192 maps (That's 67108864 "cells"), I had to come up with a quicker approach, especially for river-generation. Of course, I can not get optimal rivers with my approach, when thinking of where a river would naturally flow. But I made a compromise that I'm happy with.
Performance is a tough one for optimal river finding because the brute force version is O(n*n*n). Most folks don't really care about "correct" rivers, but only care about whether they are plausible.
ReplyDeleteI believe most of my rivers have started to look plausible, although there's still the freak artifact now and then. So I don't consider it 100% done, but the first 80% is definitely there. And that will have to suffice until the rest of the software is in a satisfactory state :)
ReplyDelete