Advertisement Jump to content
  • Advertisement
  • entries
    19
  • comments
    27
  • views
    11375

Planet Generation Plans

nukomod

1795 views

 

Hey all!

This time I'm going to write a little about my plans for generating planets. This entry won’t go into any specific details of the terrain generation but will be just a very high level overview of the basic framework. I don't think any of the ideas in here are new.. the procedural generation community are a very clever bunch indeed! I'm always amazed how when an idea pops into my head I'm able to find an existing article about it that goes into fine detail on the subject. Anyway let's crack on!

Heightmaps & Voxels

When it comes to generating terrain an easy first choice is to generate height maps and build the terrain mesh from that. You can get some good looking results quickly by overlaying some noise generation and tweaking things here and there.

image3.jpg.d0643950ffdd9f86dd0f6e1020922ba8.jpg

Though these can give some nice results they have limitations. For example tunnels and overhanging terrain can’t be represented in a simple height map. You also have to choose a projection scheme to map a 2D height map onto a sphere.

image2.jpg.4f5a2e118dcbb0837f584cfc2e21d34d.jpg

There’s another approach to terrain generation using voxels and that’s what I’m aiming to use. With voxels you can define all sorts of complex terrain and you can define what’s hiding under the ground too - whether it's seams of coal, ore or underground rivers. Many games use voxel terrains to great effect such as the infamous Minecraft. Sign me up!

In Minecraft the voxels are arranged in a grid, keeping everything nice and simple.. until you want to model a whole planet. Then you’d get something like this:

image4.jpg.06803f5afaa2b9138cb96c5e1150a331.jpg

Though that does look really cool, I don’t want my worlds to be great big cubes floating in space, so what do I do? There are all sorts of solutions to building a spherical world from a voxel grid, but they seem to be full of difficult space warping, caveats and rendering complications. I’d rather not deal with these kinds of complications, so I’m going to try a different approach.

Instead of arranging the voxels in a grid I’m planning to arrange them as points on a geodesic sphere like this (imagine the vertices are voxel points):

image9.jpg.0446fca9ecb9619023c5af59509a80be.jpg

It’s like taking the space warping issues you’d need to do at the cubes edges and spreading it evenly across the entire surface of the sphere. Instead of it becoming a difficult edge case it becomes a constant low level annoyance and keeps things consistent at all times. It will make the mesh generation a little more fun later too ;)

Voxel Planet Generation

The plan is to use an icosahedron as a starting point. Each vertex here is a voxel. This can be considered the lowest possible Level Of Detail (LOD) of a planet.


image1.jpg.a202d4363bdf2de698a27ea7eebeadd1.jpg

The space is chopped up into tetrahedrons from the planet surface into its core. There is an extra vertex at the centre of the planet for this.

image7.jpg.8681f66211b5b6385177bcae6a15e424.jpgimage8.gif.257e47a37cb70829e3a746f664e40150.gif

These tetrahedrons can be subdivided through to the core of the planet as required.

image5.png.87fe7726c2411700a7f6d0545558fae7.png

These illustrations are somewhat misleading though as this isn’t just generating a spherical mesh, but a bunch of voxels that could be empty space. The voxel points (vertices) hold information about what's actually in the space they occupy, whether it’s atmosphere, rock, magma etc. It is the job of the terrain generator to define what a voxel contains. I'm going to keep a clear divide between the planet voxel generation code and the terrain generation code this way.

I have some uncertainties on how to best manage the subdivisions of the planets voxels as required, but I’ll bash it out in a prototype.

Dynamic Changes

The game also needs to be able to make permanent changes to the terrain during play. Large explosions should create craters and I want them to persist. To do this I will need to be address the voxels and save state changes about them. I'm not 100% sure on the approach for this yet either. One train of thought is to basically create an algorithm for the voxel generation that that is able to assign each possibly generated vertex a unique 64bit number. That would have no waste and allow the maximum number of voxels, and some napkin math makes me believe it would have good detail on earth sized planets. Another approach could be some kind of hash of their XYZ or polar coordinates, though that will be more wasteful so it’d bring the total addressable voxels way below what a 64bit unique id could theoretically hold.

Ok that’s enough for now!
 

 

 

 



19 Comments


Recommended Comments

I've had some success applying the usual cube-> sphere transformations to a cube where each face is a voxel shell with some pre-determined thickness. It's not terribly elegant, but it's easy to get up and running. Your tetrahedral approach might avoid some of the distortion and apparent grid - interested to see how it turns out.

Share this comment


Link to comment

Very interesting.  I'll be curious to see how you realise the plan.

Share this comment


Link to comment

Looks neat. In fact I'm working on almost the exact same thing :)  However I'm not sure you can divide tetrahedrons evenly. You can get four new ones on the corners and then you get this sort of odd center space.  In your picture it looks to me like you divided up the faces of the original tetrahedrons which you can do easily, however chopping up the insides might be tricky, however if you figure out a good way to do it, it would be way cool.

I decided to use prisms, just because you can make an octree out of them like you can a cube.  The down side is you can't go all the way to the center of your sphere and also the inner ones are a bit smaller than the outer ones. But if you build your geometry around some reasonable band of the world it shouldn't be a huge problem, and also it gets rid of the problem of geometry looking different in different corners of the world like you would get if you generated your world in a simple subdivided cube.

I had an old version working a few years back but it just used height-maps applied to a subdivided icosahedron based simplex-noise. However it did let you walk around a huge planet without generating any data in advance.

Share this comment


Link to comment
19 minutes ago, Gnollrunner said:

However I'm not sure you can divide tetrahedrons evenly. You can get four new ones on the corners and then you get this sort of odd center space.

That odd sort of space in the centre is an octahedron. Decomposing the octahedorn is tricky, but not impossible

Share this comment


Link to comment

You guys are spot on about dividing up the space. I didn't realise at first that tetrahedrons don't tessellate in 3D space, it would have been great if they did. The picture of the sphere where you can see inside is quite misleading isn't it! Gnollrunner I'm playing with some options now, which includes some with prisms, seems I may be going down the same route you did :) Do you have any links related to what you did?

Share this comment


Link to comment
1 hour ago, nukomod said:

You guys are spot on about dividing up the space. I didn't realise at first that tetrahedrons don't tessellate in 3D space, it would have been great if they did. The picture of the sphere where you can see inside is quite misleading isn't it! Gnollrunner I'm playing with some options now, which includes some with prisms, seems I may be going down the same route you did :) Do you have any links related to what you did?

I really don't, I'm just kind of winging it.  I'm basically doing the same thing as marching cubes except with prisms. The hard part is really the LOD transitions.  I think surface nets or dual contouring does that better but then you get other issues you need to deal with. I haven't found any magic bullets. I'm using octrees with chunking such that all cells in a chunk that have any geometry must be at the same level AND neighboring chunks can at most have one level difference. Even with that, the edge conditions are a pain. I worked out an algorithm that seems to work but I'm still debugging all the cases. I have table look ups with pointers to little subroutines that handle various cases. It's a lot of code, but I'm tying to avoid a lot of ifs.

Share this comment


Link to comment
On 6/19/2018 at 6:03 PM, nukomod said:

You guys are spot on about dividing up the space. I didn't realise at first that tetrahedrons don't tessellate in 3D space, it would have been great if they did. The picture of the sphere where you can see inside is quite misleading isn't it! Gnollrunner I'm playing with some options now, which includes some with prisms, seems I may be going down the same route you did :) Do you have any links related to what you did?

Yeah, I was doing the same kind of problem (I started with an octohedron, but...) and found the same problem. I don't have my notes at the moment, but I seem to remember splitting lengths into three (or maybe four?) rather than two and thus getting a vertex in the center, which IIRC solved it. Maybe you can experiment along those lines, I'd love to know what you end up with in either case!

Share this comment


Link to comment

You could consider an more complex cube->sphere thingy, similar to the results a hexahedral meshing algorithm would produce, see this image on the left. The only advancement is that the interior does not tesselate to infinity, if you want destruction of whole planets for example. Increasing scale issue on the surface remains the same.

 1-s2.0-S0378475414000871-gr14.jpg

Share this comment


Link to comment
5 hours ago, JoeJ said:

You could consider an more complex cube->sphere thingy, similar to the results a hexahedral meshing algorithm would produce, see this image on the left. The only advancement is that the interior does not tesselate to infinity, if you want destruction of whole planets for example. Increasing scale issue on the surface remains the same.

 1-s2.0-S0378475414000871-gr14.jpg

The first one looks similar to what I'm doing, except you start out with a cube so you end up with hexahedrons instead of prisms. In my case I won't have destruction of whole planets (no Death Star in my game :P) so I don't worry about the middle. You can easily use marching cubs, surface nets etc with this, but you sill have the same issues of LOD transition, chunking and so forth which in my experience is the hardest part.

I think if I wanted to support full destruction I might be tempted to just forget about tying the make voxel orientation uniform around the world and just build everything with regular matrix.

Share this comment


Link to comment

Thinking of it my proposal is pretty stupid - using a simple subdividing cube grid projected to sphere has the same advantages at the core and the same number of singularities at the surface. (Ooops :) )

 

Edit: But there may be advantages to support Minecraft alike building eventually? Not sure - my world looks flat if i look outside the window and i'm happy with that :)

Edited by JoeJ

Share this comment


Link to comment

Just got a look at my old handwritten notes (dear lord in heaven....). I completely forgot that I started experimenting on something you miiiight have a use for. Basically, treating existing objects as point clouds and converting anything near the player to visible graphics via a standard marching cubes algorithm. If there are a lot of gold points in a section, that section is depicted as a gold thingie, and so on.

Just a thought. I'll go into my padded cell now and count the silence.....

Share this comment


Link to comment

as far as topology goes one method I've found that looks sort of neat is as follows:

1. create a random line (for sphere, hemisphere), random side of the line raise +1, other side of line -1.
2. repeat procecess until desired shape is achieved. (100-1000+)

 Problem with this though is that sometimes it leads to really unround, lopsided planets sometimes. Other than that it can look pretty dynamic. I did not come up with this idea, though, and I don't remember where I got it. Also may need to smooth or scale.

Edited by h8CplusplusGuru

Share this comment


Link to comment
4 hours ago, h8CplusplusGuru said:

that looks like it exactly 😃

I implemented this years ago. The main problem I have with it is, it doesn't easily let you just generate local terrain at one point on the planet.  While it's procedural, you end up having to store everything rather than just keeping the stuff you need that's around the camera.  For me simplex noise works a lot better since you can easily throw away and regenerate local data as needed to whatever level you want, and also you can customize your functions locally in infinite ways. 

I suppose you could use it as a base function for which you store your terrain at a predetermined level and then apply simplex-nose stuff on top of it to fill in the details.

Share this comment


Link to comment

@Embassy of Time, You had brought the idea of creating procedural tessellated planetary generation to my attention years ago.  I didn't really understand then, and perhaps now, the criteria of the obstacle.  However, I've got an observation to make regarding attempts to create a procedural-tessellate-able sponge-world without the use of voxels and why it may not be possible.  The reason being the conflict between what a GPU can process and what the CPU can process.  I'm going to kinda make shit up here because I don't have my info 100% but from the bits I do know about CPU's and GPU's I gonna make the following claim.  I'm going to claim that in order to compute a procedural-tessellate-able non-voxel sponge-planet you'd require GPU's that are designed to process information in higher dimensions, mayvbe 4 but maybe only 3.  Problem is modern GPU's, as I see it, are designed to provide quick processing of individual screen pixels.  So what ever higher dimension processing the CPU is doing the GPU is squishing it all into 2D and spitting out the results; therefore, you couldn't utilise the GPU for any higher dimensional computations for the intended goal.  You'd need to rely entirely on the CPU and that would result in a quick noticeable bottleneck that would prevent the result from looking real.

Share this comment


Link to comment
2 hours ago, Awoken said:

@Embassy of Time, You had brought the idea of creating procedural tessellated planetary generation to my attention years ago.  I didn't really understand then, and perhaps now, the criteria of the obstacle.  However, I've got an observation to make regarding attempts to create a procedural-tessellate-able sponge-world without the use of voxels and why it may not be possible.  The reason being the conflict between what a GPU can process and what the CPU can process.  I'm going to kinda make shit up here because I don't have my info 100% but from the bits I do know about CPU's and GPU's I gonna make the following claim.  I'm going to claim that in order to compute a procedural-tessellate-able non-voxel sponge-planet you'd require GPU's that are designed to process information in higher dimensions, mayvbe 4 but maybe only 3.  Problem is modern GPU's, as I see it, are designed to provide quick processing of individual screen pixels.  So what ever higher dimension processing the CPU is doing the GPU is squishing it all into 2D and spitting out the results; therefore, you couldn't utilise the GPU for any higher dimensional computations for the intended goal.  You'd need to rely entirely on the CPU and that would result in a quick noticeable bottleneck that would prevent the result from looking real.

Not sure I get your chain of logic here, but I am trying. I think the issue you worry about is, in essence, CPU capacity. The core information about a landscape needs perhaps to be made in CPU, since it has a more flexible math (I don't know how GPUs differ from CPUs in this regard, so I'm going from what you described as best as I can). The issue becomes how to translate raw landscape information into actual graphics. But I think that's less of a bottleneck than you suggest. The CPU would end up with a polygon landscape with some added data to enhance details, just like using graphics shaders to build upon basic graphics data. While it requires some careful math, I doubt it would make or break the process. But I have no definitive evidence for that.

Share this comment


Link to comment

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
  • Advertisement
  • Advertisement
  • What is your GameDev Story?

    In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

    (You must login to your GameDev.net account.)

  • Blog Entries

  • Similar Content

    • By tromtrom
      Hi there,
      I've been absolutely fascinated by Noita trailers, and gameplay videos.
      https://noitagame.com/
      Their pitch is that every single pixel is simulated. How does it work exactly?
      I'm trying to take another game as example, let's say Oxygen Not Included, tiles have properties such as material, temperature, quality of air, pressure, etc...
      It's actually very easy to understand how to model these kind of data. It can just be a massive grid, each element of that grid is a tile, tiles are regrouped by chunks. A chunk getting a change would be set to dirty, then get reupdated, etc... Of course it's not easy to make, but it's easy to understand,
      Now what about Noita? Could it be the same way to model the environment, but at the level of a pixel instead of a tile? Would that not be way too costly?
      Just trying to wrap my head around the concept...
       
       
    • By Marat Gazizulin
      Hello everyone! I'm writing research on topic - "The best game engine for a small team to create 2D indie games". I need a research consultant or any feedback in this topic because I can't do it on my own - I'm not a scientist or someone else in game engines and other things. I've chosen criteria and game engines for research. They are in image "table.png" below. As we can see, it contains 6 game engines and 10 criteria. I want to know - are this criteria and game engines suitable for my research? In "Notes" section I put quiestion to help respondents answering.
      In the last line - Value of criteria(in different words, multiplier), I wrote my own estimation of each criterion. This method let us to get different order of engines for every game development team. For example, if I value "Learning Curve" and "Ease of use" I will get one order, but if I value "Genre" and "Extra Benefits" I will get another order. Thank you for your attention. I hope you will leave feedback. Have a nice day :3.
    • By Lauren Tuccy
      So my only coding experience is with writing Interactive Fiction games with Inform, so I get the logic and stuff, but, I'm so used to starting with a program with libraries and assets already built in, that I have no idea how to build something from scratch. 
      I'm would like to make this simulation game where the player is a student in a [magic] school, and I've got stats for the students, their personality types, and ideas on how that should effect their performance in class, and experience rates, and all this data in a google spreadsheet, but I have NO idea how to start creating this game on a code level. So, I'm just struggling on finding out how to get started. Can anybody give me some advice?
    • By MiniDarkOF
      Hello Again,
      I'm trying to create a "sound expansion"

      The Example:
      a nuclear explosion sound has 1000ft of audible sound area
      players who is next to the explosion hear it first
      players who is far to the explosion will hear after some seconds
      when the sound reaches its area limit, it ends with a "fade-out"

      The Point:
      i already know how to create fade-out sound effect in Unity
      know i want to know how i can create this "sound expansion" effect
    • By Alikberov
      In classic sound adjustment of games we having control over volume of music or sound-FX. For lots of table games or puzzles this is enough for all user preferences.
      But in more difficult games with complex sound environment such of adjustments is not enough and gamer must to use the headphones, because sounds of game environment can disturb surrounding public. But headphones can destroy the health of gamer.
      I'm not present any code at here, but I trying to build a draft of sound FX spectre of emotional perceptibility of gamer to giving more wide control over sounds in game with complex choice for favor gamma in playing sounds.
      0. Angels level Mood music, that playing in the brain at this moment Sounds of thinking like the trying for inspected prediction for action Speech synthesis of player thinking process; Player-self dialogue Inside sounds of body functions, like heart-beat, breath or beat in temples Outside sounds of body, like knuckles squeak, belly rumbling or cough Nearest subjective environment, like mosquito cheep, buddy whisper, phone speech or headphone of equipping Subjective environment, like fly hum, sleepers shore, somebody cough or slurp, speech Active subjective environment, like doors squeak, floor squeak under foots, sneakers shuffling, tick of switch Objective environment accompaniment, like leaves rustle or curtains swaying, branches rap in window, winds drone, water purl Passive objective environment, like spontaneus floor or furniture squeak, alone drop fall, wallpapers crackle Operated active technical environment, like phone ringtone, TV set or radio, claxone or gun shot Interactive technical environment, like watch tick-tick, elevator sound Active technical environment, like frigy sound or autos engine Technical environment accompaniment, like generators sound Passive environment, like waterfall noise or river purl, twitters, public hubbubs Operated environment, like battle noise or cannons shots, explosions Interactive environment, like thunder or lighting, volcano or earthquake Active environment, like hurricane or tsuname Evironment accompaniment, like public or animals screaming, animals rave, people rave or crying It's not HDR. No dynamics.
      Static normalize all sounds of game for session.
      Just, like in graphical equalizer, we can have a 20 sliders band of levels any sounds.
      If user shut down to zero all 20 adjusts, except #6, then no any sounds user can listen and hearing #6 (mosquito, whisper and equipping) only.
      (No monsters, no disasters, no cannons. The commander only!)

×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!