Mapgen4: elevation painting

Last week I described the plan for elevation in mapgen4. The goal was to allow painting mountains, valleys, and oceans on the map. I used a jittered grid to pick positions for mountain peaks, and then implemented three distance fields:

1. Distance from closest mountain peak. I use this to create distinct mountains instead of noise-based continuous mountains.


2. Distance from coastline. On the ocean side, I use this to make shallow water near the coast. On the land side, I use this to keep mountains away from coasts. (not sure I should)


3. Distance from mountain ranges. I use this to make a gradual drop from mountains to valleys.

I continued optimizing. The main map regeneration is now around 400ms for the one-time initialization and 120ms to regenerate the map while painting. I implemented a simple paint interface, with small/medium/large brushes and ocean/valley/mountain tools. It works on touch devices too, and it feels pretty good on a tablet.

Map painting

Notes:

1. UI: One part of the interface feels unintuitive: erasing mountains. The way the mountain constraints work, a tiny mountain constraint creates a distance field around it, full of mountains. When you erase, you're looking all those mountains, trying to erase them, but since most of them didn't create the distance field, your erasing does nothing. I'll have to tweak or rethink this UI before release.


2. Consistent output: For performance and also for increased procedural variation I was using a hybrid of Breadth First Search and Dijkstra's Algorithm. It used an O(N) queue like Breadth First Search, but it also peeked at 4 elements ahead in the queue, and swapped with one of them if it had a higher priority (lower elevation). Dijkstra's Algorithm always picks the highest priority element; my hybrid would favor them but it didn't look at the entire queue. The results were pretty good, and it ran in only 5ms. I was happy with this. Unfortunately, as you paint, the variation from this algorithm caused it to "flicker", even in areas you weren't painting in. I switched to Dijkstra's Algorithm, using flatqueue, and it now runs in 20ms and doesn't flicker. I think there are opportunities for further optimization but I'll revisit this later.


3. Regl.js framebuffers: Clearing the framebuffers was taking a surprising amount of time, often 5–7ms. I was using regl({framebuffer: fbo_z})(() => { regl.clear({color: [0, 0, 0, 1], depth: 1}); }). I found that fbo_z.use(() => { regl.clear({color: [0, 0, 0, 1], depth: 1}); }) runs much faster, often in under 0.1ms. I don't know why. And I don't see use in the documentation and I admit I don't really understand what's going on here. But it's now faster, so I'm happy.


4. Profiling: I admit I find Chrome's profiler kind of confusing. I liked their older profiler better. I learned about a new tool, SpeedScope, that presented information in a way that "clicked" for me. I made use of the "Left Heavy" and "Sandwich" views to figure out what I needed to optimize next.


5. WebAssembly: I wondered how much faster my map generation algorithms would run if I wrote them in C and then compiled them using Emscripten. I tried this with one of my functions. To my great surprise, it ran 10–20% slower! I suspect the biggest win from Emscriptened code is that instead of allocating lots of Javascript objects, your C++ objects get stored in contiguous memory in TypedArrays. My code already uses TypedArrays for almost everything, and there evidently wasn't much else to be gained from this. It's possible another one of my algorithms would benefit from WebAssembly, but I decided not to pursue this for now.

I told myself I'd work on rivers this week. Last time I worked on rivers I was able to make them fast, but not pretty. I'm going to see if I can make them prettier. First I need to figure out why they're so jagged. Another thing I want to do with rivers is make them depend on rainfall. But that means I need to actually implement rainfall. And to implement varying rainfall, I want to make rain that depends on oceans and mountains. I'll start with simple algorithms for this, like west-to-east wind and rain shadows, but I'd like to experiment with more complex flow algorithms. Or maybe what I should do is let the user paint the rainfall levels. That'd be easier and more expressive. Hm.

When I get back to optimization in a week or two, I plan to split the tasks up to run on WebWorkers. I think that'll be the biggest win for responsiveness, and some of the algorithms can also run in parallel across several WebWorkers, so that'll speed things up even more. It's already usable but laggy. I think another factor of 2 or 3 will make it feel good.