Dev Blog
Hi, this is the Stranded III development blog (see also Forum Thread, Comment Thread).
Entry 30 - Random Terrain Generator - September 13, 2015
Random Terrain Generator
Generating terrains is one of the main things I took care of the last days/weeks.
I found a pretty cool, big and detailed article about procedural map generation based on Voronoi polygons. This actually doesn't fit to the height maps in Stranded III because their data is based on arrays and not polygons with more or less arbitrary positions. Of course I can use polygons anyway but I have to rasterize them in some way so I can store their data in arrays.
Areas created from random points
So after seeing that article I wanted to go for a comparable approach. The first step is to somehow separate the map into areas which then can be used as a base for further transformations. It seemed to be way too much effort to use all that Voronoi stuff. So I came up with this simplified algorithm:
Create a 2D array for the map
Iterate over the array in x and y direction (nested loop) with a certain step size > 1
For each step spawn a point at the current position with a random offset (which is smaller than the step size)
In some (random) cases spawn an additional point with another small offset in the same area
The point(s) created per step will get a an ID
Iterate over the entire array (nested loop, now over EVERY array cell so the step size is 1)
For each cell iterate over all random points and find the closest one to the current position
Save the unique ID of the closest point in that array cell
This is very slow because you have to iterate over ALL points for ALL array cells and calculate the distance. In my case I had an array with the size of 512x512. I spawned a point (or 2) every 8 units. So at least (512/8)^2=4096 points and max 4096*2=8192 points.
By the way: The random secondary points are used to get a less uniform result.
In worst case there are 512*512*8192 distance calculations which equals the insane number of 2,147,483,648. I didn't bother to do exact measurements but I think it took over 30 seconds to run this.
Here's my first result after rendering it:
Click me to enlarge
Ooops. So something went wrong there. But no worries. It was just the rendering (classic stuff like like mixing up x and y):
Click me to enlarge
Still not exactly what I wanted to display. The third attempt gave me the desired result:
Click me to enlarge
So this is actually a pretty acceptable result. Sadly the (run-)time required to create it was totally unacceptable.
There would be a ton of ways to optimize my simple algorithm. It's totally stupid to check all points for all array cells for example. It would be way more efficient to store the points in a sorted data structure and to only check the closest points for example.
Back to Voronoi
I didn't try to optimize my poor algorithm. Instead I went back to the Voronoi stuff. There are even multiple C# Unity implementations linked on the article page. I took the first one which is available here, did some basic cleanup and added the demo to Stranded III:
Click me to enlarge
I noticed that the demo displayed a lot of stuff that I don't really need so I reduced it to the most important stuff:
Click me to enlarge
This is cool and fast - at least compared to my own algorithm. The next step was to somehow rasterize this into my array. I already implemented Bresenham's line agorithm in Stranded III so it wasn't very hard to do this:
Click me to enlarge
But what I actually need is the area enclosed by those lines, not the lines themselves. I needed something which allows me to rasterize polygons which are defined by vertices/edges. I knew that this can be done with a scan line algorithm but I didn't really find a good implementation of this for C# so I started to write my own one.
My first visual result with it was this:
Click me to enlarge
Well... this somehow worked a bit but there's clearly something wrong. I found out that I had - again - a problem in the rendering code. So I fixed that one:
Click me to enlarge
Still not correct. It took me some time to find out that I did a pretty stupid mistake. It's easy and convenient to store edges as lines which consist of a start point and an end point. This however is pure waste of resources when talking about polygons because the end point of one line is always equal to the start point of another line. So when storing polygon edges as lines you would have to store all points twice which is just a horrible idea.
Instead I wanted to store them as points/vertices which are just connected in order. So I converted the list of lines that the Voronoi stuff spit out to a list of vertices. The lines were not ordered the way I thought they would be which caused the funky problems you can see above. The colored and black areas are defined by invisible edges which span between the wrong edge points.
I fixed the order and this is my current result:
Click me to enlarge
Yay! This one still has some minor issues but it basically does what I want. The most visible problem is probably the missing/partial fill of polygons on the left and right border. That's because the edges are missing there but it shouldn't be very hard to solve this.
Keep in mind: This is all just about splitting the terrain into areas which can then be used for further operations. The colors are just for debugging. This is work in progress terrain generation.
I'll continue with this topic in my next dev blog.
Generating terrains is one of the main things I took care of the last days/weeks.
I found a pretty cool, big and detailed article about procedural map generation based on Voronoi polygons. This actually doesn't fit to the height maps in Stranded III because their data is based on arrays and not polygons with more or less arbitrary positions. Of course I can use polygons anyway but I have to rasterize them in some way so I can store their data in arrays.
Areas created from random points
So after seeing that article I wanted to go for a comparable approach. The first step is to somehow separate the map into areas which then can be used as a base for further transformations. It seemed to be way too much effort to use all that Voronoi stuff. So I came up with this simplified algorithm:
Create a 2D array for the map Iterate over the array in x and y direction (nested loop) with a certain step size > 1 For each step spawn a point at the current position with a random offset (which is smaller than the step size) In some (random) cases spawn an additional point with another small offset in the same area The point(s) created per step will get a an ID Iterate over the entire array (nested loop, now over EVERY array cell so the step size is 1) For each cell iterate over all random points and find the closest one to the current position Save the unique ID of the closest point in that array cellThis is very slow because you have to iterate over ALL points for ALL array cells and calculate the distance. In my case I had an array with the size of 512x512. I spawned a point (or 2) every 8 units. So at least (512/8)^2=4096 points and max 4096*2=8192 points.
By the way: The random secondary points are used to get a less uniform result.
In worst case there are 512*512*8192 distance calculations which equals the insane number of 2,147,483,648. I didn't bother to do exact measurements but I think it took over 30 seconds to run this.
Here's my first result after rendering it:
Click me to enlargeOoops. So something went wrong there. But no worries. It was just the rendering (classic stuff like like mixing up x and y):
Click me to enlargeStill not exactly what I wanted to display. The third attempt gave me the desired result:
Click me to enlargeSo this is actually a pretty acceptable result. Sadly the (run-)time required to create it was totally unacceptable.
There would be a ton of ways to optimize my simple algorithm. It's totally stupid to check all points for all array cells for example. It would be way more efficient to store the points in a sorted data structure and to only check the closest points for example.
Back to Voronoi
I didn't try to optimize my poor algorithm. Instead I went back to the Voronoi stuff. There are even multiple C# Unity implementations linked on the article page. I took the first one which is available here, did some basic cleanup and added the demo to Stranded III:
Click me to enlargeI noticed that the demo displayed a lot of stuff that I don't really need so I reduced it to the most important stuff:
Click me to enlargeThis is cool and fast - at least compared to my own algorithm. The next step was to somehow rasterize this into my array. I already implemented Bresenham's line agorithm in Stranded III so it wasn't very hard to do this:
Click me to enlargeBut what I actually need is the area enclosed by those lines, not the lines themselves. I needed something which allows me to rasterize polygons which are defined by vertices/edges. I knew that this can be done with a scan line algorithm but I didn't really find a good implementation of this for C# so I started to write my own one.
My first visual result with it was this:
Click me to enlargeWell... this somehow worked a bit but there's clearly something wrong. I found out that I had - again - a problem in the rendering code. So I fixed that one:
Click me to enlargeStill not correct. It took me some time to find out that I did a pretty stupid mistake. It's easy and convenient to store edges as lines which consist of a start point and an end point. This however is pure waste of resources when talking about polygons because the end point of one line is always equal to the start point of another line. So when storing polygon edges as lines you would have to store all points twice which is just a horrible idea.
Instead I wanted to store them as points/vertices which are just connected in order. So I converted the list of lines that the Voronoi stuff spit out to a list of vertices. The lines were not ordered the way I thought they would be which caused the funky problems you can see above. The colored and black areas are defined by invisible edges which span between the wrong edge points.
I fixed the order and this is my current result:
Click me to enlargeYay! This one still has some minor issues but it basically does what I want. The most visible problem is probably the missing/partial fill of polygons on the left and right border. That's because the edges are missing there but it shouldn't be very hard to solve this.
Keep in mind: This is all just about splitting the terrain into areas which can then be used for further operations. The colors are just for debugging. This is work in progress terrain generation.
I'll continue with this topic in my next dev blog.