Mapgen4: bug fixes

From Red Blob Games's Blog

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:

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!

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:

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:

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:

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: mapgen4 , maps , project