Map Generation: Introduction

I always loved procedural generation, and was really impressed by mewo2’s fantasy maps. I decided to give it a try using Unity and the Burst Compiler, an amazing piece of tech developed at Unity. It was also the opportunity to dig into SVG and implement a few algorithms and white papers: Delaunay’s triangulation, a depression filling algorithm, a cartographic labeling algorithm based on simulated annealing, water network computation and a few others. I’ll write a (probably long) series of articles detailing the interesting parts and algorithms of the project and my general process to approach this kind of topic.

I could have used Unity’s ECS, but it seemed a bit overkill. However I’ll use the job system directly with Burst, and render just enough 3d to visualize the generated terrain. The map itself will be an SVG file written on disk.

The steps will be

• Generate random points
• Write a custom Burst-compatible data structure to store polygons and generate a Delaunay triangulation using Bowyer-Watson
• Assign a height to each polygon
• Fill the depressions using Planchon-Darboux
• Clean the coastlines
• Compute the water flow over the map by following down slopes
• Create water sources and follow the water network until it reaches the sea
• Render all of that to SVG (which itself will require many more steps)

Burst-compatible code must satisfy multiple constraints:

• No reference types or classes
• which means no boxing of a struct to an interface type
• struct instance methods and static methods only
• no managed collections, only Native Containers

So Burst strongly favors data-oriented design/programming. I’ll refer you to this list of resources about DOD and Mike Acton’s talks if you want to know more about it.

So let’s start by a bit of boilerplate and generating points.