Dev Blog

Hi, this is the Stranded III development blog (see also Forum Thread, Comment Thread).

Overview (115 Entries)

Entry 83 - Island Generation Improvements - January 13, 2019

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

Disqus

blog comments powered by Disqus