Announcement

Collapse
No announcement yet.

Almost Hex Planet Procedural Generation

Collapse
X
 
  • Filter
  • Time
  • Show
Clear All
new posts

    Almost Hex Planet Procedural Generation

    Hey!

    The last few weeks I was busy working with the procedural generation of a planet (which consists mostly of hexagon tiles - more on that in a sec)!
    I have seen a lot of map generators that inspired me (for example Zeustiak's Map Generator). Nevertheless I wanted to work on a generator that created planets instead of 2D maps.
    Any comments, ideas or answers to my several problems would be vastly appreciated.

    Here is where I am now (this is biome view btw. I have a temperature, elevation and humidity view too - you can also view the wind in the form of arrows) :
    Click image for larger version

Name:	current.jpg
Views:	1
Size:	69.7 KB
ID:	1192306

    Another one with around 10k tiles: (Arrows are for winds)

    Click image for larger version

Name:	current2.jpg
Views:	1
Size:	128.7 KB
ID:	1192324

    Summary:
    A Planet Generation algorithm that begins by creating a procedural mesh, split into hundreds of tiles. Then elevation is calculated using tectonic plates - and continents are formed. Heat and humidity come next as well as some wind patterns. Finally using the previous calculations I assign biomes to titles.

    A quick tour:
    • Procedural mesh generation: Starting with a regular icosahedron, I subdivide it as much as I want to (for the above size it's 4 subdivisions - my PC can handle up to 5 or 6 but it is noticeably slower). Then I generate the dual polyhedron to create a sphere that consists of hexagons and some pentagons.
    • Tectonic Plates and Elevation: After creating my sphere, I create tectonic plates (around 50 of them) by selecting random (non-neighbor) tiles and using voronoi as well as just a tiny bit of randomness. Each tectonic plate is set as an oceanic or not and a velocity around the center of the planet. Then after calculating pressure in the borders (and depending on how the plates collide)I generate the elevation and spread it inwards.
    • Winds are for the moment randomly generated. I start by assigning huge winds around locations and then bluring and adding up those winds for nice patterns. I actually don't like the fact that the winds are before the heat mechanism (wind should actually go from warm to cold locations).
    • Temperature: Each tile receives heat from the sun. Locations near the equator receive more heat than ones further away. Then this heat is spread around using winds. If heat is concentrated too much in a tile then heat radiates back into space. Unfortunately due to the randomness of the winds I had to tweak stuff a lot to keep ice in the poles and tiles near the equator warm.
    • Humidity and precipitation: Humidity (as mass of water /cubic meter) is generated in the oceans then spread around using the wind. If relative humidity is very high in a tile (relative humidity is affected by absolute humidity and temperatures) then it becomes rain.
    • Biomes: Finally I generate a biome for each tile depending on their temperature, elevation and precipitation. No real difficulty here, I just google'd up biomes and using my understanding I assigned a range of values there.


    Future Plans
    • Rework heat and wind patterns - since those two should be connected
    • Add resources to my generat
    • Figure a solution for the pentagon tiles. I am thinking about adding several pentagons and heptagons to break the symmetry. Nevertheless I am a bit lazy to work on that now..
    • I am not happy about the precipitation. I feel that random tiles are getting a lot of rain while tiles right next to them are deserts.
    • Finally I want to add navigation & stuff like that to my planet so that simple units can move around. In a few words create a framework for my future strategy game.


    Let's get started:

    Procedural Mesh Generation
    This actually took most of my time. The first and simple idea was to start with a simple icosahedron and subdivide it as much as I had to, to create my initial sphere.
    While at that time it looked like a simple idea I had no idea how to start creating my mesh. I went ahead and made a simple icosahedron using the custom mesh component by hard coding the vertex coordinates and the edges (that's actually a valid way to create an icosahedron).
    Nevertheless when I went ahead to split the edges I hit a wall. There was no obvious to me way to keep track of which edge I was splitting - and even when I found a solution to this I was always losing track of neighbor faces. The way I was representing my mesh was too simple to support any complex operations like subdivision. This got me reading a lot of papers on mesh representation (I was totally clueless before this) until I decided I was going with the half edge data structure also known as double connected edge list.
    After coding the whole data structure and re-creating the icosahedron using it, I was able to proceed to subdividing it. By this time I had moved to using the Procedural Mesh Component.

    Click image for larger version

Name:	subdividedicosahedron.jpg
Views:	1
Size:	60.9 KB
ID:	1192303

    The second part of the problem now, was to create hexagon tiles from this subdivided icosahedron. The idea again was simple: Treat each vertex as a future face (or tile), and the centroid of each neighboring triangle as the corner of those future faces:

    Click image for larger version

Name:	dualpolyhedron.jpg
Views:	1
Size:	87.0 KB
ID:	1192304
    (excuse my painting skills - I did my best)

    As you can understand, the black triangles are the old faces of the subdivided icosahedron and the red ones are the generated hexagon tiles. By the way this is called a dual polyhedron
    Of course that wasn't so easy as I hoped it to be, because I was losing neighboring tiles all the time. It wasn't that hard either though.
    The problem that arose was that you can NOT have a sphere out of hexagons - more about this here.
    You always end up with pentagons in the places of the original icosahedron vertices. That was something I actually knew from the beginning - this irregularity is why I chose to start with a procedural mesh and not by slamming hexagons in an instanced mesh.
    Anyway, the results were not bad at all:
    Click image for larger version

Name:	tiledsphere.jpg
Views:	1
Size:	50.8 KB
ID:	1192305

    (The screenshot was from when I was experimenting with materials, that's why I had to paint it over with black lines, for you to see. The red are the pentagons)

    The first part, the mesh, was done. I had some ideas to break the symmetry created by the pentagons by adding more pentagons in random locations. (Actually that idea was from a similar generator I had seen somewhere but can't find anymore to link )

    I will follow right away with tectonics (elevation), temperatures, winds & more!
    Last edited by Semitable; 08-29-2016, 04:22 PM.
    Check my User Interface Kit here: https://forums.unrealengine.com/show...-Interface-Kit
    A WIP Hex Planet Generation: https://forums.unrealengine.com/show...ral-Generation

    #2
    Next job was to create elevations and continents. A good way to do that is by using tectonic plates.

    So I went ahead and created tectonic plates. I selected 50 random tiles (I called them tectonic roots) that were not too close to each other. Then I started assigning tiles to the closest tectonic roots.
    The result was great right away:
    Click image for larger version

Name:	tectonic.jpg
Views:	1
Size:	62.2 KB
ID:	1114244

    Now I just had to assign a random vector to each tectonic plate that represented the movement around the center of the planet.
    Click image for larger version

Name:	tectonicmovement.jpg
Views:	1
Size:	60.6 KB
ID:	1114247
    (The arrow is the vector around which the plate moves). This vector though should start in the CENTER of the planet, not in the center of the tile. (I did it that way to visualize how each plate moved)
    So take the arrow, move it to the center of the planet and then using the right hand rule you know how each plate moves.

    Then the hard part begun. I had to find all the tiles that are in the border of the tectonic plates and find the pressure they has from the neighbor tectonic plates.
    I had to work on my math for this one since you need to find the cross product of the vector of the plates movement with the vector pointing to the neighbor tile. Do this for all the border tiles and then add up the values you found for the final pressure. (I won't go into depth for now since I will have to refresh my memory on the math I did. If anyone is interested I can check it though)

    After calculating the pressure on the borders I knew if the plates were colliding, drifting apart or if they were quite stable.
    Then I created elevation in the borders: (~ref plate tectonics)
    • Convergent boundaries (Colliding)
      Oceanic vs Oceanic: Island Arc
      Oceanic vs Continental: Oceanic Trench and Mountain Range
      Continental vs Continental: Extensive Mountain Range
    • Divergent boundaries (Drifting Apart)
      Divergent boundaries usually create new crust in a lower elevation so that's what I did. I took the elevation of the tectonic plates and subtracted a small number from those.
    • Transform boundaries (Stable)
      Finally in the case of stable boundaries I averaged out the elevations in the area and added some randomness.


    Finally I just had to move the elevation from the borders inwards to the tectonic root (Scaling down mountains or trenches). That took a recursive function but wasn't that hard to do. I then blurred the elevations a bit to remove hard lines.
    Anything with elevation < 0 became an ocean and elevation > 0 became land.
    Click image for larger version

Name:	elevation1.jpg
Views:	1
Size:	67.3 KB
ID:	1114250
    Here you can see a mountain range and what I think are results of my "Oceanic Trench" and "Island Arc" interpretations.

    In any case I was happy with the morphology that was generated. Here's another planet:
    Click image for larger version

Name:	elevation2.jpg
Views:	1
Size:	57.0 KB
ID:	1114251

    Post any questions below! I will continue with the wind and heat patterns tomorrow if you guys are interested!
    Last edited by Semitable; 08-28-2016, 02:25 PM.
    Check my User Interface Kit here: https://forums.unrealengine.com/show...-Interface-Kit
    A WIP Hex Planet Generation: https://forums.unrealengine.com/show...ral-Generation

    Comment


      #3
      Good morning!

      I now had the elevation of my planets. It was time to create some kind of climate.
      The correct way for this would be to generate heat (from the sun) and then spread it around with winds (winds that go from warm places to colder)
      Unfortunately that wasn't the first idea I had. What I did (and I plan on reworking) was to generate random winds.
      • I selected random tiles (same procedure as the tectonic roots), and then assigned directions to winds starting from those locations. (Right hand rule again). This also gave a nice spin - making it quite natural.
      • Then for each tile that didn't yet have a wind attached I summed up all the wind vectors * distance from wind root. (For example if there were 3 wind roots in my map, each tile would have a wind: wind1*DistanceFrom1 + wind2*DistanceFrom2 + wind3*DistanceFrom3. (Distance was calculated using Great-Circle Distance)


      The result was great from the beginning (one of the reasons I kept it).

      Click image for larger version

Name:	winds.jpg
Views:	1
Size:	108.9 KB
ID:	1114284


      Then the temperature:
      Things have started to be easier. I was now comfortable using the tiles I had made and assigning attributes to them. The temperature was calculated as such:
      First of all I had two temperatures for each tile:
      • Ground temperature
      • Air Temperature


      And a loop that was:
      1. Each tile would receive a set amount of heat dependent from the distance to the equator.
      2. If there was a difference between ground and air Temp: heat was transferred from the hottest to the coldest.
      3. Air was then moving heat (Air temp only) to neighbor tiles (dependent on the wind direction obviously).
      4. If a tile was starting to become too hot (ground temp) it would progressively radiate more and more temperature back into space.


      I run the previous loop until things settled down (or reached a very high loop counter):
      Click image for larger version

Name:	heat.jpg
Views:	1
Size:	54.9 KB
ID:	1114285

      And another example:

      Click image for larger version

Name:	heat2.jpg
Views:	1
Size:	80.4 KB
ID:	1114286

      (blue zones are subzero temperatures; red-zones are > 0)

      The problem I had with this implementation is that winds could easily overcome the starting heat received from the sun and huge subzero zones were created (instead of having sub-zero temperatures only in the poles, I had icy regions that reached even the equator).
      For this reason I had to do a lot of tweaking and scale down a lot the heat transferred through winds.

      And finally the humidity/precipitation.

      Each tile has 3 variables:
      • Absolute Humidity - Quoting Wikipedia: "Absolute humidity is the total mass of water vapor present in a given volume of air. It does not take temperature into consideration.". It is measured in mass per cubic meter.
      • Relative Humidity. Relative humidity is the percentage we usually read in the weather reports. It is calculated using the absolute humidity and the temperature of the tile.
      • Precipitation: When relative humidity reaches a number close to 100%, then water falls in the form of rain/snow etc. and becomes precipitation.


      So my algorithm went as follows:
      • Absolute humidity is generated from ocean tiles.
      • Absolute humidity is moved around using winds.
      • Relative humidity is calculated for each tile.
      • If relative humidity > 95% it starts to "rain" removing mass from absolute humidity and adding it to the precipitation variable. This continues until relative humidity is < 60%-80% (random)


      I loop these steps 365 times to calculate the precipitation in every tile. Relative humidity is quite unstable as you can guess - but precipitation is a value I can use later for biomes!

      I hope you guys liked my post. Please comment, critique or ask questions! :-)
      Last edited by Semitable; 08-29-2016, 09:13 AM.
      Check my User Interface Kit here: https://forums.unrealengine.com/show...-Interface-Kit
      A WIP Hex Planet Generation: https://forums.unrealengine.com/show...ral-Generation

      Comment


        #4
        Post reserved for Biomes & Future Work.
        Check my User Interface Kit here: https://forums.unrealengine.com/show...-Interface-Kit
        A WIP Hex Planet Generation: https://forums.unrealengine.com/show...ral-Generation

        Comment


          #5
          Looks great!

          Good job getting the hexagonal subdivision going, I had a crack at that and it proved a bit too challenging for me

          Comment


            #6
            This is super interesting

            Comment


              #7
              Originally posted by ioFlow Studios View Post
              Looks great!
              Good job getting the hexagonal subdivision going, I had a crack at that and it proved a bit too challenging for me
              Thanks a lot! Yeah the subdivision was quite hard. I only managed to do it when I fully implemented the half-edge data structure.

              Originally posted by HeadClot View Post
              This is super interesting
              Thanks :-)
              I updated the post with winds, heat & humidity! Unfortunately I couldn't find a screenshot with humidity - when I do I'll post it!

              Hope you guys enjoy!
              Check my User Interface Kit here: https://forums.unrealengine.com/show...-Interface-Kit
              A WIP Hex Planet Generation: https://forums.unrealengine.com/show...ral-Generation

              Comment


                #8
                This looks awesome, I've always wanted to do this myself, but never really had the time. How far do you reckon you're going to take it?

                Comment


                  #9
                  Originally posted by ambershee View Post
                  This looks awesome, I've always wanted to do this myself, but never really had the time. How far do you reckon you're going to take it?
                  Not really sure, but at the moment I find it very interesting and I have some really nice ideas. At this moment I am experimenting with adding some 'real time' temperature and humidity changes. This way you can see temperatures change and ice melt in the duration of a year.

                  My main issue is that I don't want to create a realistic simulation - but I want things to be based on reality.

                  For this reason I find hard to balance things (like winds) by keeping them realistic but still feel like a game.
                  Check my User Interface Kit here: https://forums.unrealengine.com/show...-Interface-Kit
                  A WIP Hex Planet Generation: https://forums.unrealengine.com/show...ral-Generation

                  Comment


                    #10
                    Do you plan on selling this on the market place?

                    Comment


                      #11
                      Originally posted by HeadClot View Post
                      Do you plan on selling this on the market place?
                      My plans now are to make a game out of this. I have some great (imho) ideas on my mind. If that doesn't work out for me there's a good chance I'll package it up and sell it in the marketplace. You think there will be many interested?
                      Check my User Interface Kit here: https://forums.unrealengine.com/show...-Interface-Kit
                      A WIP Hex Planet Generation: https://forums.unrealengine.com/show...ral-Generation

                      Comment


                        #12
                        Originally posted by Semitable View Post
                        My plans now are to make a game out of this. I have some great (imho) ideas on my mind. If that doesn't work out for me there's a good chance I'll package it up and sell it in the marketplace. You think there will be many interested?
                        Personally Speaking I know I am

                        Comment


                          #13
                          Long delay but +1, has anything happened since?

                          Comment

                          Working...
                          X