The Flying Castle can Mass Teleport as it flees from the Manastorm. I want the player to be able to choose where to teleport, maintain resources for it, and have some knowledge about what they are going to find.

I also want quests to go between different maps, providing extended requests for more valuable items and spells.

I love the idea of clouds disappearing to reveal the worldmap as the player explores or receives information about particular locations. Cities, quest targets, or special bosses might provide the player difficult choices between what to choose or if it is worth risking the Manastorm catching up to them.

So, my worldmap requirements:

• Randomly generated with some controls
• Various regions with different settings that can be seamlessly teleported to
• Water and land
• Cloud / Fog-of-War that can be revealed over time
• Nodes with a map / adventure
• Nodes with another enemy castle to battle

I could just use simple hexagons to generate landmasses (ala Civilization), but I preferred the natural look of voronoi polygons (plus they provide ample opportunity for rivers). These polygons would also give me variation to show cloud bunching along the edges:

Time to write Voronoi

It didn’t take too long to get an initial attempt. I created a WorldGenerator module that created a random set of 100 sites on a canvas. I used a library to generate Voronoi graph from these sites.

And then I took the voronoi graph, assigned polygons / centers to maps, and it mostly worked!

The edges are definitely too large, and many of them are thin / different sizes. There’s something called LLoyd’s Relaxation Algorithm I can use to get more regular polygons.

LLoyd’s Relaxation Algorithm finds the centroid of each polygon (which is different from the center I used for creating the polygon) and then rebuilds the voronoi using the centroid rather than the center.

Effectively, this gradually migrates all of the centers and polygons to more averaged shapes and uniform distributions from the original random noise.

The downside is that it does require running voronoi multiple times. I wrote a static function for performing it.

public static VoronoiResults Relax(VoronoiResults graph) {
    PointD[] sitesRelaxed = new PointD[graph.generatorSites.length];
    PointD[][] regions = graph.voronoiRegions();
    // find the centroid (avg of points) of the region and make that the new site
    for (int i = 0; i < regions.length; i++) {
        double sumX = 0;
        double sumY = 0;

        for (PointD p : regions[i]) {
            sumX += p.x;
            sumY += p.y;
        }

        sitesRelaxed[i] = new PointD(sumX / regions[i].length, sumY / regions[i].length);
    }
    // rebuild a voronoi diagram using these new relaxed points
    return Voronoi.findAll(sitesRelaxed, graph.clippingBounds);
}

I found ~2 relaxations gave me the uniformity I was looking for.

The blue dots show the centroid, while the red are the current center. Additional relaxations have a huge diminishing returns for distance as they asymptotically approach the centroid, you can see they are already pretty close after 2.

If I want a higher density of voronoi, I can just up how many sites I create:

Paths between nodes

Voronoi has all of the polygons and centers, but I don’t have connections between nodes. I’ll need to know which nodes you can travel between so the castle can navigate between them.

Turns out, a graph where all the center points of a Voronoi Diagram are connected is called a Delaunay Triangulation! It is a well understood phenomenon in its own right.

private static void GenMapRoutes(MapNode[] maps, VoronoiResults mapGraph) {
    // create a map route for neighbor (map index) -> (map indices)
    // currently just use delauney triangulation
    for (VoronoiEdge edge : mapGraph.voronoiEdges) {
        MapNode map1 = maps[edge.site1];
        MapNode map2 = maps[edge.site2];
        // connect the two as neighbors
        map1.neighborIds.add(map2.mapId);
        map2.neighborIds.add(map1.mapId);
    }
}

I’ll eventually want to filter some of these polygons out and focus on just nodes players can travel to, but I can save that for later.

Coloring time

To start simple, I want interior land, beaches, and ocean. I decided that simply generating a height map with some perlin noise would be good start.

I wasn’t sure how I would add multiple regions, but decided that having them connected by oceans was a good idea.

I can use my generator to make a particular region, and then stitch them together at particular nodes/waygates. That way I didn’t have to figure out how to make good islands and continents, and could focus on making a single continent with a few small islands for each region.

Also, this means I could configure my generator to look distinct for different regions.

I chose to use Perlin noise for the height map. It did a relatively good job at creating islands, but not as much a main continent:

It looks rough, so I added some color gradients based on height to make it easier on the eyes:

Out of pure curiosity, I decided to write a quick script that would increase the noise resolution of the height map every few seconds to visualize how Perlin Noise is shaped:

We need oceans

Regardless, this has too many landforms, so to isolate the region I added a quadratic fall-off based on radial distance.

This strategy worked okay, but the edges fell off hard, and on higher resolution generations it was abundandtly clear. Obviously I could just change colors, but I wanted something a little more natural looking for showing deep oceans.

I chose to blend a radial and square gradient to tug the edges and get more playable space on a particular map.

This is roughly the final algorithm I chose to use:

// Runs for each site
// calculate unit coordinates that scale by resolution (normalized 0 to 1)
float perlin = Noise.GetNoise(ux * resolution, uy * resolution);
// ensure island based on distance to edges
// use a square gradient (normalized)
float dist = Math.max(Math.abs(ux - 0.5f), Math.abs(uy - 0.5f)) / 0.5f;
// use a radial gradient (normalized)
float radDist = MathUtilsExtra.Distance(ux, uy, 0.5f, 0.5f) / NormalMaxDist;
// linearly interpolate the square and radiant gradients based on how close to center it is
// this will allow for corners to populate land (square dominant) and gradually radially shift in,
// which avoids the "streaking" corners that square gradients typically have
dist = MathUtils.lerp(dist, radDist, 1 - radDist);

// produces an island slope based on x^4 fall-off with a slight linear incline to the center
siteHeights[i] = siteHeights[i] - siteHeights[i] * dist * dist * dist * dist + 0.1f * (1 - dist);

And the results look pretty good. I can control the height map baseline to control how much water is in the region (important for Dragon Isles).

I can actually visualize exactly what is going on using my map generator. I create a baseline map with Perlin noise…

And then I create a falloff curve, you can see the mix of radial and square gradients, creating a rounded square shape.

Here’s a bunch of different islands generated with different settings and seeds!