So when I actually had power and internet this month, I was working on a terrain generator for Trading Company. There were plenty of tutorials with varied degrees of difficulty, but a lot of them really didn’t fit the game. For one thing, I wanted the terrain to not be grid or hex based, if it was all made of hexes it would look like Civilization, if it was a grid it would look too much like Minecraft. I wanted a way to make it look more natural.

Another problem was that the world needed to be divided into sections, these would act as different areas where cities and locations would go. But just having this be sections of the world split into a grid I thought would be boring. So ultimately after doing some research I found the Voronoi algorithm.

This is the Voronoi algorithm, or at least it was made using it. The idea is you create a certain amount of random points on the screen (the origin points), then you go through a grid and for each cell or point, find out which origin point it’s closest to, and that determined which chunk it belonged to. This was ideal for sectioning off the world for the different locations, along with creating biomes.

One issue with Voronoi however, which you can see in the picture above, is that the sections it creates can be very small or very large. This is due to the randomness of the origin point placement, if two points are very close together, the resulting polygon will be smaller. This wasn’t the best when I was going to be using these polygons as sections the player can discover in the world.

To fix this issue I used a method known as Lloyd Relaxation, essentially I created the initial Voronoi diagram, found the center point of the polygon, and moved the origin point to that center and redid the Voronoi algorithm. I did this about 3 – 5 times to smooth it out enough so that it looked natural, some polygons were still a bit smaller or larger, but it wasn’t enough of a difference to be concerned.

So I prototyped this using Winforms before I actually tried to create a mesh and such inside of Unity. I added a few biomes, made some adjustable values and these were the results. The black dots represent the origin points. Next I’m going to be writing about the actual implementation of this in Unity, you can read about that here!