Random Island Generation Improvements
A long time ago a blogged about random island generation. Here are some of my old blog entries about the topic:
Random Terrain Generator
Terrain Generator Continued
Rivers
More About Rivers
Voronoi Powered Rivers, Bezier

I used a complex Voronoi/Delauny library for this and then rasterized the data using a polygon fill algorithm because I need a 2D pixel array for the heightmap.
After doing some more research however I realized that generating a Voronoi diagram directly as a 2D array is quite easy. I even found a site with minimalist Delauny diagram implementations for various programming languages.
No C# implementation there but the approach is so simple that it only took a few minutes to write a working version for Unity in C#. The only problem with the approach presented there (I only looked at the Java version) is that the algorithm is not optmized at all and gets a lot slower with increasing numbers of Voronoi sites.

What it does is extremely simple:
for each pixel in the array:
      find the closest Voronoi site by iterating over all sites and saving the shortest one with distance
      tint the pixel in the color of the site with the shortest distance

There are two problems with the implementation:
Checking the distance to ALL voronoi sites for each pixel: This makes the algorithm super slow with increasing numbers of sites. The solution for this is to only check the distance of adjacent sites. I'm creating the site points in a grid pattern so I know all the neighbors. This makes it easy to implement this optimization.
Square root calculation in distance calculation: Calculating a square root is a relatively expensive operation. This operation can simply be removed because we only compare distances and don't need the actual distance. This has no huge impact but still makes a difference.

I solved both of these problems and achieved a fair performance that way.
The best thing however is that this approach is so much easier and requires just like 1% of the amount of code that I had before.

To test my new implementation more easily I made a little separate Unity project which you can try in the browser:
Try the Web Map Generator
Note that this is just a very basic version which only creates a basic island shape and assigns some random colors. Also it doesn't work perfectly well with non-square map sizes.

Further Optimizations
Another thing I'll change is the resolution I'm using for the random map generation.
I was insane enough to work with a 1x1 m precision for all operations. Now I plan to reduced the base resolution to 4x4 m or maybe even 8x8 m.
Imagine a 256x256 m island. With the current calculation this leads to 256x256 "pixels" which is 65.536 pieces of data (each representing 1x1 m).
With 4x4 m precison the values change a bit: 256 / 4 is 64. 64x64 results in only 4.096 pieces of data. That's only 6.25% of the original data and therefore allows a much faster world generation. With 8x8 m it would be only 1.024 pieces of data.

Of course simply doing just that would make the generated maps blocky and ugly. That's why I will switch back to the 1x1 m precision after generating the basic map layout. I'll then apply simple smoothing algorithms and perlin noise to get more detailed and non-blocky results.


Red Cross
Someone in the comments pointed out that the red cross can be problematic in video games and he's totally right about it.
Therefore I replaced the red cross with a heart - which is a better logo anyway

blog comments powered by Disqus