Last time I mentioned that I made some changes to my dual-mesh helper library. I use it for my Delaunay/Voronoi map and art projects. Part of the motivation was that I want to work on some new map projects, and wanted to fix some of the issues with the library. I then realized I need to test out the changes in mapgen4.
I made a list of mapgen4 bugs I wanted to fix. The main one I'm going to talk about here is that the edges of the map are jagged. Why didn't anyone notice? Because I set the default zoom level to be slightly zoomed in, so that you don't see the edges!
To investigate, I first started a separate project where I could isolate and experiment with the module I was trying to understand. I built visualizations to look at the boundary points.
After fixing the boundary point function, I imported it back into mapgen4 and tried it.
Guess what? It didn't help at all! (In fact, it was worse, as I would later discover)
I had assumed that the problem was the boundary points, and I spent a lot of time fixing boundary points. But I hadn't verified that the problem was the boundary points first. So I fixed a problem that wasn't there.
So I came back to mapgen4 and I added a debug visualization to show the boundary points and the Delaunay triangulation. It looked ok! It didn't explain what I'm seeing. And it also tells me that I was looking in the wrong place. Debug visualizations can be very useful! After further debugging, I discovered that the jaggedness was a result of the quad rendering I'm using. I'm neither drawing the Voronoi regions nor the Delaunay triangles. Instead, I'm drawing quads that combine both, and I'm turning those quads into two triangles.
The fix was to exclude boundary triangles, which weren't even something I considered as part of the dual-mesh library. I don't know why I didn't think of this when I was originally writing the code, but I suspect it's because all my debug visualizations were either the Voronoi regions or Delaunay triangles, but never these quads.
But … there's still something weird going on. The bottom and right sides have a black region. The top and left sides do not. That's weird…
So I investigated that bug and found that I had an off-by-one error in an unexpected place. Wow. How many more bugs am I going to find?
The answer was… several!
If I want the map to fill the entire 1000✕1000 square, I need the boundary points to be on the outside of the square. But the Poisson Disc algorithm can only stay away from points inside the square. That made me realize I should have a double boundary, one layer inside to push the Poisson Disc points away, and one layer outside to ensure that I fill the map square.
But … in changing the way boundary points were generated, I introduced a bug. I need the Poisson Disc points to ignore the interior layer of boundary points. They were often too close to the existing points, creating some narrow triangles. That bug had to be fixed twice, since there are two Poisson Disc stages in mapgen4. One is for the terrain and one is for mountain peaks. Fixing this bug exposed another bug in the new algorithm: a few boundary points were missing, but only on the bottom and right side of the map:
This was caused by those points being exactly on the edge of the square, sometimes getting classified as being outside. To fix the bug, I pushed them inside slightly.
Once I got the underlying structure correct, I worked on the rendering. I returned to the sawtooth border problem:
I had tried fixing this by moving the points on the CPU, but then I realized I could just as easily do this on the GPU. Either way, I clamp()-ed the points to the map square. That was much easier than I expected, but only worked because I had fixed the other bugs first.
I was pretty happy that I fixed all these bugs. I wasn't happy that I had them in the first place, but I'm also not surprised, given how this evolved out of an experimental project.
In the next post I'll talk about a new feature I added, one that was only possible after these bugs were fixed.
Post a Comment