Procedural Map Generation

For some time I've wanted to create an application that could generate believable maps, such as those that can be found in an atlas. For this application I would want to simulate plate tectonics, weather for climate zones, ideal city placement, and much more. I'd want the user to be able to choose what elements to display, the visual style of the map, and to be able to stop at any stage of the process to make changes by hand. While this was mainly out of personal interest, I imagine that it could be used as a tool in games for either assisting artists to build a more believable landscapes, or to generate entire worlds on the fly for games with that requirement. That's why I decided that this would be the project for my specialization.

This would however be too broad of a scope for the time given. So for this project I decided to make a base for that application that could be further built upon in the future. I was greatly inspired by a generator made by Martin O'Leary and decided to follow the steps that he had laid out for the base of this application. My goal for this project was to create a generator that had the same features as his, save for the name generation. This included generating a base landscape, eroding it, rendering the coasts and rivers, and placing cities in ideal spots and marking borders between them. Below is how I spent my time and my results.

Week 1

At the start of our specialization we were concurrently having a course on Network Programming, so for this first week I focused on that class but I also made up a plan for how to approach this project and set up this website.

Week 2 & 3

For the next two weeks I followed my plan and implemented Fortune's Algorithm in order to generate Voronoi Diagrams. This algorithm takes a number of points (sites) and pulls a "sweepline" across them. As it sweeps over them it creates a "beachline" of parabolas who's intersections defines the edges of the Voronoi Diagram. When a parabola is compressed by two other parabolas a vertex is created.

It was fairly easy to find overviews of the algorithm, but most sources glanced over more specific parts of the process. I eventually found an article by Paul Reed that provided me with the parts that I found difficult to understand.

Most sources also recommended using a Doubly Connected Edge List (DCEL) for storing the diagram, but I couldn't find anyone describing how this is done, so I had to come up with my own implementation.

I wasn't able to make it work completely, having some edge cases where the algorithm would fail, and I still have to restrict the algorithm to some bounds, but with this I was able to move on to the next step.

Week 4

During week four I integrated Perlin noise from an external library and I implemented a way to generate a mesh from the Voronoi diagram. The mesh generation was fairly simple. I only had to traverse all the faces (sites) of the diagram and iterate through its edges, treating the sites as vertices and their shared edges as edges, essentially creating a Delaunay Triangulation.

Week 5 & 6

The next step in the plan was to erode the terrain. I started by implemeting a flow map to store how the water would travel over the map and cause hydraulic erosion. After this I found it difficult to reason about how to continue, so I instead worked on the website and finished documenting most projects.

Week 7

For week seven I decided to finally make an attempt at erosion. I tried out a technique I saw in a video by Sebastian Lague where you simulate rainfall across the map and trace the path that the water would take. The water carries sediment and drops it after it exceeds the droplet's capacity. The implementation was based on a grid map, which made it difficult to recreate, and the result wasn't great.

Week 8

For the final week I decided to focus on the documentation that was necessary for the course. However, on the first day I wanted to try out another method for erosion. This technique involves creating a network of water flow, calculating how much water would reach each vertex, and then lowering the terrain based on the amount of water and the slope in the water's path. This was less realistic than the previous technique, but gave much better results in my opinion.

Conclusion

While I didn't get all the way there, missing the intended visual representation and the city placement, I was still happy with how it turned out. The final result is rendered as a 3D heightmap, which I initially only intended to be a helpful visualization tool during development but that I now plan to incorporate into the future application. If I hadn't gotten stuck on the erosion during weeks 5 & 6 I think that I would've reached all of my goals, but in spite of these shortcomings I believe that this is a good basis for the application that I'm imagining and I plan to continue working on it in the future.