Godot Map Generator
I have often thought about how one could implement zone based maps for video games, different territories with common borders. This project experiments with voronoi cell generation but is quite possibly not how you would implement such a thing.
But I am sure this has it's own usecases.
Overview
This map generator roughly follows this article. I like to handle the voronoi cells as selectable regions, that is where this project is a bit different.
Progress
I try to follow the article, so heres what has been done so far.
Currently Implemented
- Polygons
- Map representation (more or less)
- Islands
- Elevation
- Rivers
- Moisture
- Biomes
Todo
- Noisy edges
- More noise
- Smooth biome transitions
- Distorted biome transitions
GDExtension
It uses a custom GDExtension addon that provides a faster C++ implementation of Poisson-Disc-Sampling and a Delaunator. Originally used other implementations, this GDScript script for the Delaunator and a custom one for the PDS algorithm. The move to C++ improved the speed of the generator roughly by 50%-60%.
The custom addon is located in this GitHub repository.
Localization Exercise
I definitely used this project as an exercise in localization. Every text you see is fully localized in german and english.
A bit deeper in-depth look
To generate the voronoi cells I mostly oriented myself by how the Delaunator works. This is a really cool
piece of software - it triangulates points but keeps a lot of interesting data easy to access. Every triangle
is made up of counter-clockwise half-edges - one directional edges from one corner to the next. Two adjacent
triangles share an edge, every edge is made up of two half-edges, one from point A to point B and one in the
other direction, these half-edges are opposite of each other. The Delaunator has two arrays, triangles and
halfedges. When you give a list of points to triangulate, triangles and halfedges both have an entry for each
half-edge, triangles has returns the point id where a given half-edge in a triangle starts while halfedges
returns the opposite half-edge. Additionally, those half-edge ids a related to the triangle ids in the
following manner: a triangle t has the half-edges 3\*t, 3\*t+1 and 3\*t+2.
Once you get the hang of it, using such simple data structures is a blast.
You might know that voronoi cells and triangulation a related. Find the center of each triangle and connect it with the centers of adjacent triangles, surrounding a corner of the triangle to get voronoi cells. This way, you get a voronoi cell for every point of the original triangulation. To handle this information I created my own thing: the Voronator. The Voronator keeps a reference to an underlying Delaunator triangulation, as well as a list of vertices (all corners of a cell), one after the other and lists to see how many vertices each cell has (it keeps track of the start indices of each cell). Based on common techniques, voronoi cells are generated and easily kept track off.
The last layer on top is the Terrainator that ties all of it together. It samples points given certain parameters, triangulates them, generates voronoi cells based on other parameters. After this, based on its current configuration elevation, rivers, moisture and biomes are applied to the voronoi cells (or vertices).
Closing words
I have no idea if such a technical talk is any interesting, I have the habit to just ramble on, even if the person I am talking to doesn't understand a word I say.
All in all this project has taught me quite a bit, I am more or less happy with the current result, although I haven't checked all points of the bullet list.