Improving Mapgen4's boundaries, part 2 #
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!
Improving Mapgen4's boundaries, part 1 #
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.
Curved region rendering #
Around a month ago I had an idea in my head: a voronoi grid modified to have rounded cells that change in size. I made an attempt here for single cells changing size. The next step was to merge cells together, as I had done on this project. I decided that the way to demo this would be to simulate some kind of belief/cultural systems that spread over time across a map. I tried this here.
Labels: triangles
Map generation on a sphere, part 1 #
I ran into a showstopper with mapgen4. It unpredictably "freezes" in the sense that inputs have no effect, even though both the map generation and rendering are running. I'm taking a break from that for ProcGen 2018 - 9 days to work on a procedural generation project.
I decided to play with procedural map generation on a sphere. I've long wanted to try generating entire planets instead of flat maps. See this project and this project to get an idea of what I'm wanting to learn how to do.
Mapgen4: river appearance #
Earlier this week I moved all the heavy computation into its own thread. The rest of the week I wanted to work on rivers. The last time I worked on rivers, I replaced the slow CPU-based renderer with a fast GPU-based renderer. However, the output was ugly:
Delaunator guide #
I decided that I should work on a new tutorial this summer. What better than to take all the map experiments I worked on last summer, and turn them into a procedural voronoi-map generation tutorial? As I worked on the outline and some of the initial diagrams I realized this was going to be big: poisson disc, delaunay, voronoi, elevation, climate, biomes, oceans, rivers, towns, roads, natural resourcess, and so much more. And starting with something big often leads to failure. So I needed something smaller.
I decided that I should start with just the structural part: Delaunay and Voronoi, and how they can be used for game maps: poisson disc, jitted grid, delaunay, voronoi, graph properties, neighbors, traversal, lookups, iterators, ghost elements, centroid vs incenter vs circumcenter, rounded regions, subdivision, and more. While working on the outline for this I realized again that it was going to be big. And starting with something big often leads to failure. So I needed something even smaller.
Alternatives to Voronoi for procedural map generation #
When I think back on my polygon map generator project from 2010, the word I associate most with it is voronoi. I used Voronoi diagrams for spacing the points and also for constructing polygons around those points. Seven years later, I'm revisiting this, looking at the ways in which Voronoi wasn't a perfect match for my needs, and looking for alternatives.
Hexagon tiling of a sphere #
Recently two people asked me about making a tile-based game that uses a sphere topology. Some games have tile maps that wrap around. Civilization for example lets you go off the left side of the map and you warp to the right side. You can’t go off the top or bottom of the map. In 3D space, this would be a cylinder. Some games also let you go off the top side and warp to the bottom, and vice versa. In 3D space, this would be a torus. But most tile map games don’t use a sphere. Why? The sphere doesn't tile. I thought … can we almost tile it? The answer is yes!
I wrote up my notes here including a small interactive demo. This is a quick & dirty investigation and not one of my longer polished articles; see this post about my wanting to write pages more quickly.
Distances on a triangular grid #
As part of my article on grids, I'd like to provide basic algorithms for grids. I already know how to compute distances on square and hexagon grids, but I didn't know how to compute them on a triangle grid. I initially tried changing coordinate systems, inspired by Charles Fu's coordinate system. I normally use the coordinate system from my article on grids:
The first coordinate (which I will call u) is the
position along the horizontal axis; the second (which I
call v) is the position along the southwest/northeast
diagonal. The Left/Right parity introduces some compliation; I
let R be 1 and L be 0. This coordinate
system is nice for storing maps in an array, but it's not as clean,
because triangle grids have three axes but only two of them are
expressed in the coordinates. For the horizontal axis I
used 2u+R as the position; for the second axis I
used 2v+R. I guessed that the position along the third
axis would u-v. I drew some grids on paper, wrote down
the u,v values, and then computed the three positional
values. They behave properly for computing distances along the
third axis, but the system falls apart when computing distances not
on the three axes.
Frustrated, I decided to step back and approach this problem in a more principled manner. In Charles Fu's three-axis coordinate system, taking one step in the grid changes two of the coordinates and leaves the third alone. For a triangle grid, the dominating feature is the straight lines in three directions. I looked on the web for any articles describing distances on triangular grids, but didn't find any that satisfied me. This paper was promising but unfortunately gives an iterative algorithm and not a clean formula. However, it uses an interesting coordinate system, which is useful for computing distances. If you take one step in the grid, you will cross exactly one line. The distance between two locations will be the number of lines you have to cross. I wanted to use a coordinate system in which crossing a line changes a coordinate:
I want to map
the u,v,R coordinates I normally use into the alternate coordinate system a,b,c, where
exactly one of a,b,c changes when you cross a
line. Here's where I decided to use algebra. In u,v,R space, the black triangle has
coordinates 0,0,0; the triangle to the east of it has
coordinates 0,0,1; to the west, -1,0,1; to
the south, 0,-1,1. In a,b,c space, the
black triangle is 0,0,0; the east triangle
is 0,0,1; the west triangle is 0,-1,0; and
the south triangle is -1,0,0.
I want a formula that computes a, and I expect it to be
linear, so I write a = au*u + av*v +
aR*R + constant. That's four unknowns, but we know the
constant will be 0, so it's really three unknowns. To get three
equations, I plug in the values for the east, west, and south
triangles, then solve for the coefficients. Let's see what happens:
For each s in (a, b, c), and each triangle i: si = su*u + sv*v + sR*R East triangle: u,v,R = 0,0,1 s1 = su*0 + sv*0 + sR*1 therefore: sR = s1 West triangle: u,v,R = -1,0,1 s2 = su*-1 + sv*0 + sR*1 therefore: su = sR - s2 South triangle: u,v,R = 0,-1,1 s3 = su*0 + sv*-1 + sR*1 therefore: sv = sR - s3
When s is axis a, we look
at a for triangles 1 (east), 2 (west), and 3 (south),
so a1 is 0, a2 is 0,
and a3 is -1. The algebra tells us
that aR = 0, au = 0,
and av = 1. That means the formula
is a = v. Pretty simple. Doing the same
for b and c, I get b = u
and c = u + v + R.
These results are simple enough that if I played with the grid
enough, I would have come up with them. However the algebraic
approach works for other constraints, not only the simple ones. I
also used it to create a coordinate system with 2u+v+R,
u+2v+R, v-u (this is 30 degrees rotated from the one above),
which may be useful for other algorithms. Algebra and calculus also
come in handy for defining movements (e.g., splines), growth rates,
equilibria in interacting systems, and other types of interesting
behaviors in games.
What is the distance between two locations in a triangular grid?
Each step involves a line crossing, and we want to count steps, so
we add up the line crossings along each axis (a, b,
c): distance = abs(Δu) + abs(Δv) +
abs(Δ(u+v+R)). This looks just like the Manhattan distance formula, but for triangles instead of squares.