This article is part of my series of projects around Map Generation. Click here to see the list of projects of this series.
Welp... Here I am, restarting my map engine for the sixth time now ! After regular hexagons, pixelated hexagons, pixel grid, blobmap, and interpolation map, I am now using Voronoi polygons !
Every map engine I made over the years. For left to right and top to bottom in chronological order.
Motivation
The goal, as always, is to make maps that look realistic, are divisible in tiles to be used by the game logic, and with enough details and interesting features. Square grids are boring, look unrealistic with right angles, and movement on a square grid are ugly due to each region having edge-neighbors and corner-neighbors. Hexagonal grids are better since they only have edge neighbors and the angles are less brutal, however we can still see the pattern if the resolution is too low.
In this project, I attempted to use a polygonal grid based on a Voronoi diagram. This method creates regions around seed points such that each point on the plane is attributed to the region corresponding to the closest seed point. That way, we get the benefits of hexagonal grids without the repeating pattern.
However, polygons with straight edges are ugly and unrealistic. One way to make the edges look more like geographical features (rivers, coasts, cliffs, etc) is to keep the vertices of the polygons fixed, but draw noisy edges between them. And one method to achieve this is to subdivide each edge into a broken line.
The additional difficulty is that I also want my maps to support wrapping, either horizontally or vertically or both. This means each polygon and edge must match exactly on one side and the other.
Region generation
The first step to generate the grid is generating the seed points for the Voronoi diagram. Using two uniform distribution, a number of points are generated over the whole map to match a given density. Points might generate close to each other but this is not an issue because of the relaxation steps.
If wrapping is enabled, we duplicate points in a certain margin from one side to extend the other.
Then using Fortune's algorithm, we create the Voronoi diagram.
If wrapping is enabled, we remove the points and extraneous edges outside the map.
Then we crop the regions to dimensions of the map.
Some points are too close to each other and this results in thin regions and sharp angles. To mitigate this issue, we perform relaxation using Lloyd's algorithm which consists in first moving each point to the geometric average of the corners of their respective region.
Second, we remove the edges and keep only the points.
If wrapping is enabled, once again we duplicate points at the margin from one side to extend the other.
And we can recalculate the Voronoi diagram.
If wrapping is enabled, once again remove the points and regions outside the map.
Cropping the regions to the dimensions of the map completes a full iteration of Voronoi relaxation. We can repeat this process multiple times to make the regions more rounded.
Finally, we can make the regions look even more natural and smooth out the sharp corners by performing what I call corner relaxation : we simply move each corner to the geometric average of their three corresponding region center.
Here is an animated GIF of the whole process.