The past week has been troubleshooting. The biggest problem was water pouring out of my house's electrical panel, but that's not what this blog post is about. I've been working on bugs in the map generator. There are some bugs I've been putting off because I didn't understand them.

The first problem was that rivers haven't been reaching the ocean. This has been a problem for a while, but I didn't want to fix it until I stopped changing the algorithm. I'm mostly happy with the river algorithm now so I decided to investigate. One thing that the Game AI Summit at GDC emphasizes is building debug visualizations; I'm a fan of that technique and tried it here:

Debugging coastal and river triangles

This uncovered several bugs.

The algorithm uses Dijkstra's Algorithm to search the land for places to put rivers. I had originally started the algorithm on the boundaries of the map. It explored the oceans and then crawled up onto land until it reached the mountain peaks. The problem with this is that if there are disconnected oceans, it would force a path between them. I changed this to start from the coastal triangles. That fixed the spurious ocean connections, but it introduced a new problem: the rivers didn't reach the ocean. This is because the way the rivers are rendered, I draw rivers on each Delaunay triangle. Each triangle connects the inflows to the outflows. By starting at the coastal triangles, there was no outflow, so there was no river rendered.

I need to special case the coastal triangle river rendering. However, for now, I put in a workaround: I start the algorithm on all ocean triangles. That way they will climb through the coastal triangles, and set an outflow direction.

While investigating this I also found that my graphics buffers for river triangles weren't big enough to handle every case. Oops! I was also drawing the entire buffer instead of only the triangles I needed to draw. Oops again!

I also found occasional coastal triangles where they shouldn't have been. The painted input elevations are on a grid. To map this to a Delaunay triangle mesh, I use bilinear interpolation on the grid's pixels. Occasionally the interpolated value would be zero, and there would be a coastal triangle that wasn't generated by my coastal triangle algorithm. I fixed this by forcing all painted elevations to be either land (>0) or ocean (<0), never exactly 0.

Rivers look much better when they reach the ocean!

Rivers coming from mountains

After fixing several bugs I decided I should continue working on bugs. I decided to work on a mountain painting mystery. There are places where no mountains would show up. You could paint repeatedly in that area and there would still be gaps:

Mountain peak locations: random

It didn't take long to understand why. I choose mountain peaks at program startup. The paint operation doesn't create the mountain peaks; it activates the ones already there by mixing them into the elevation. The problem is that the initial peak locations aren't evenly distributed. I picked points on the mesh randomly, which inevitably leads to clumps and gaps. It would be better to pick evenly distributed points, but I didn't have a nice way to do that on a mesh.

I often find that I can solve problems better by approaching them from a different angle. In this case, the problem was that I didn't have a good way to pick evenly distributed points after I had a mesh. So I worked backwards. I picked evenly distributed points and then built a mesh that included those points. That way, I was sure that the mountain peak locations were actually on the mesh!

This was great in theory. When I sat down to implement it, I realized it was slightly more complicated. I actually have a dual mesh. There's a Voronoi polygon mesh and a Delaunay triangle mesh. The mountain peaks need to be on the Delaunay mesh, and the rest of the points need to be on the Voronoi mesh. I ended up picking all the points on the Voronoi mesh, then picking an arbitrary nearby point on the Delaunay mesh when I needed a mountain point. It's good enough for now.

While reworking this part of the code, I also found another bug: there are triangles with zero area. That should never happen! It turns out I had messed up the calculation of the lengths of the sides of triangles, which I then used to calculate the areas using Heron's Formula. I had needed the edge lengths for another part of the code, and ended up reusing them for the triangles. The problem is that every edge in the dual mesh actually corresponds to two line segments in the geometry. One is the sides of the Voronoi polygons; the other is the sides of the Delaunay triangles. I had been calculated the Voronoi side lengths, and then ended up using them in a place where I needed the Delaunay side lengths. This caused the rivers to vary in width more than I expected. I hadn't understood that bug, and I had planned to work on it next, so I was happy to have found and fixed it while trying to fix mountains.

With the new mountain peak locations, no matter where you paint mountains, you'll get some:

Mountain peak locations: blue noise

Great! But there are some larger consequences to this. First, the blue noise calculation is expensive. I decided to precompute these and save them to a file. Then I load the file on the page and use it to build the mesh. This would've worked better if I had cleaner code, but I have tons of global variables and many of them depended on the mesh to already be there. To keep the code working I embedded the data in a giant string. However that string was way too big so I spent some time refactoring the code to make it not depend on the mesh at startup, and now the code can wait until the file has been read in before it constructs all the global data.

The other big consequence of switching from a jittered grid to a blue noise mesh is that the mesh is far more "regular". The polygon sizes are fairly uniform, which means the river meandering and the mountain appearance is nowhere near as random looking as before. You can see it in the above screenshot but it's much more obvious with a higher mesh resolution:

Mountain peaks are too regular

This is a problem to fix another day. I plan to allocate a week for improving visuals, and will work on this then.

I didn't get a lot of work last week, but it was much needed work. I normally like to fix bugs as I work on the features, but sometimes there's something deeper going on that requires stepping back and looking at the bigger picture.

Note about this blog post: I've been using the original full resolution PNG screenshots, but by reducing their palette to 8 bits, shrinking them to one quarter size, switching from PNG to JPG, and optimizing them, these screenshots are around 6% the original size, from 13.2MB to 0.8MB. Click on them to see the full sized image. I should do this to all my blog posts in the future.

Labels: , ,

6 comments:

Alan wrote at September 26, 2018 10:54 PM

If I understand correctly, you’re taking a PNG, reducing it 8 bit palletized, resizing to quarter size, then converting to JPEG? Given how JPEG works, I suspect that reducing to an 8 bit palette isn’t helping. And resizing after palettizing will either take you back to 24 bit color or will harm the accuracy, as resamoling into an existing palette can lead to undesirable compromises. Dropping that step might cost you nothing and slightly improve the resulting quality.

I’ve been enjoying your blog and look forward to your future posts.

Zellyn wrote at September 27, 2018 6:58 AM

Despite the holes, the original mountains look better, partly because they seem to go in runs, like real mountains do. Good luck!

Amit wrote at September 27, 2018 7:05 AM

@Alan: good point! I had started with the 8 bit palette and then tried JPEG, and I should take out the 8 bit step now. Thanks!

@Zellyn: I agree, the original mountains look better. The new mountains solved the UI problem but made things look worse. I need to go back and figure out how to make them look good while also keeping the UI working properly.

Scott Turner wrote at September 27, 2018 7:57 AM

A lot of terrific material in this post. I'll save a detailed response for Reddit :-)

Tyr wrote at September 28, 2018 11:51 AM

Oh, oh, you've started in to run into the Nabraska problem!
https://caseymuratori.com/blog_0011

I'm pretty excited to see how you solve this. I actually used Casey's approach in my final year graphics program.

Amit wrote at October 02, 2018 6:53 AM

@Scott Turner: thanks! For other readers: here's the reddit link https://www.reddit.com/r/proceduralgeneration/comments/9jdz80/mapgen4_bug_fixes_rivers_havent_been_reaching_the/

@Tyr: yes! However since my camera angle is different and the Voronoi/Delaunay mesh provides additional randomness (which I'm still tuning) I'm hopeful that I won't have to spend as much time on it as Casey did.