Improving Mapgen4's boundaries, part 1

From Red Blob Games's Blog

I've been wanting to refamiliarize myself with the mapgen4 code because I'd like to do some new map projects and will want to reuse some of the code from my existing projects.

The first thing I decided to work on was my dual-mesh library. I had originally written it to be a generally useful wrapper around Delaunator. Since then, I wrote the Delaunator Guide, which has all the same functions, but in a way that you can adapt to your own needs. I also realized that by making this library public, I was making it harder for my own needs. So version 3 of this library is going to be primarily for my own needs.

The major changes I made so far:

1. I switched from require() to es6 modules.
2. I switched from JavaScript to TypeScript. I have mixed feelings about this, as so far it's gotten in the way more often than it has helped. I was already using typescript for type checking with jsdoc types, but typescript for compiling hasn't been a great experience.
3. I changed the naming convention, from a_to_b meaning a was the input and b was the output to b_from_a. Why? Because when chaining calls, writing c = b_to_c(a_to_b(a)) is much harder to parse and spot errors in than writing c = c_from_b(b_from_a(a)). A big thanks to Tom Forsyth for making the argument for this convention. So far, it's been quite a good change for this project.
4. I made a visualization of the boundary points, primarily to figure out the bugs, but also to serve as a reminder to myself of how the ghost and boundary points are arranged.
5. I found and fixed some bugs in the boundary point function. Look at the diagram above. The spacing of the blue points doesn't match the spacing of the red points, especially at the corners. This leads to some narrow triangles at the corners.
6. I removed the 1000x1000 limitation and made the boundary point code work for any rectangle.
7. I removed the depedency on the poisson-disk-sampling library, because I use different different point selection approaches in each project.

I haven't finished the dual-mesh changes, but wanted to put some of them to the test by trying them out in mapgen4. So that's what I did next. Although it went well, I had two thoughts after this:

1. The dual-mesh library does a bunch of things I don't need in mapgen4.
2. The dual-mesh library does some things that aren't done the way mapgen4 needs it.

This reinforced my belief that a lot of what I need is a starting point or a recipe that I can adapt to each project's needs, instead of a reusable library that tries to do everything. I'm using less than half the code from dual-mesh, and am reimplementing parts of it because it doesn't quite fit my needs.

So what works and what doesn't?

1. The core functions work really well. These are primarily traversal functions, which I wrote about in the Delaunator Guide. The code in that guide was meant to be generic, and use common naming conventions. For some of my projects I use a different naming convention, and for mapgen4 I needed to minimize callbacks and allocations for performance reasons. I think this should remain in the library.
2. The creation functions use Poisson Disc, create boundary points, and create a ghost structure. For mapgen4, I want to use a different boundary point function, I need two different sets of Poisson Disc points, and I want to precalculate all of these and save them to a file. I do use the ghost structure code from the dual-mesh library, but the rest I had to reimplement. These might be best turned into recipes to be adapted to each project's needs.
3. The test functions are nice but I only used them while developing the dual-mesh code. I don't need them in mapgen4. They should remain in the library, but not the distribution bundle of the library.

I also spent some time just exploring different boundary point algorithms. Along the way I found this one:

I didn't plan to use this. I just made it for fun, because it looked like it might be interesting. And it turned to be exactly what I needed for mapgen4. It's a reminder that it's useful to explore possibilities because they add to the set of possible solutions I can pick from.

Despite fixing bugs in the boundary point function, mapgen4 still had major bugs in the boundary points. That's because when I'm working on dual-mesh, I address imagined problems, whereas when I'm working on mapgen4, I address real problems. This is yet another reminder to myself to start with the real problems, not the imagined problems.

In the next post I'll show some of the issues I ran into and how I fixed them.

Labels: geometry , mapgen4 , maps , triangles , voronoi