12 February 2019

Procedural Chunk-Based Universe part 1 - It's full of stars!

As a long-time fan of Space Engine, even before the infamous No Man's Sky was announced, I've been big on humongous procedural game worlds. The universe is a big place, after all, and someday I dream of exploring it, so in the meantime it's fun to pretend by immersing myself in exploration games like this.
Now SpaceEngine is being built by a sorcerer with years of experience in graphics programming. SpaceEngineer has created the entire engine in C++ and GLSL, taking advantage of shiny concepts like GPU terrain generation, raymarching, etc. It's all an inspiration to me, but much of it is too hard to chew if I bite it off in the advanced state in which it is. Like any noob, I learn by starting with the simple parts - WASD to move, click another player's head to shoot it, write and compile a few easily understood lines of code at a time to see if I'm doing it right.
So where professionals like SpaceEngineer use an octree to discretize 3D space, I, being mediocre at data structures, have instead gone the way of constant-sized chunks. I don't think it's a bad approach anyway - a number of games use chunks for their worlds and it serves them very well. There's that one about punching trees that I hear a few hundred or so people played...


Now Minecraft's chunk architecture is based on a 2D square grid. Each chunk measures 16 one-meter blocks on a side horizontally and extends the full 256-block depth of the game world (some evolution has occurred in the data storage format, but this basic formula still presents itself in the game logic). This works great for a game about people living on the surface of a large world and using mainly hand tools to make changes to the landscape. They are only able to tunnel a few dozen meters at most into the ground before encountering indestructible bedrock, and they are only able to build pillars a few dozen meters high, which is more than reasonable for a medieval house or even a respectable castle.
But I don't want to spend my life confined to within a short elevator ride from a 2D surface, and that goes for game worlds too. Minecraft's ability to feed the player gratuitous amounts of chunks must for me extend to the vertical axis, not merely so I can build stupidly tall towers or carve Aperture Laboratories into the land, but so I can take off into the great beyond and visit new worlds without end.
So that's my two-paragraph sermon about why I went with cubes.
Now, chunk-based game worlds naturally don't need to be limited to voxel-based landscapes. Those cubes can be as big as I want and contain whatever I want - I could make a cube with a galaxy in it, or even a whole cluster of galaxies.
Okay those are just dots, but they could be anything. The cube doesn't care what they are, only that they belong to it (and in most use cases, are inside it... I didn't have that hammered down by this point).
One cube obviously doesn't constitute a chunk system for the world. I also needed ways to make and control a number of chunks, for them to do useful things to the things inside them, and so on.
So first up was finding a way to put a whole mess of chunks in the world. Actually, even before that was thinking up overall logic for when and in what fashion chunks were placed in the world. My decision ended up being that the "universe" would attach to a game object, thereby having a world-space position. This game object could be the player, the main camera, or a special "Universe" object that follows the player or main camera or even remains stationary. For my earliest tests it remained stationary, but once work was solidly underway I made it follow the player - or at least move around by key presses as if following a player. At all times, the player or universe object would be contained within one chunk, and if it wandered too far (in the beginning this was a distance check, but later evolved into a different and more appropriate sort of check), new chunks would get generated around its new position so that it remained inside the universe (leaving the universe would be bad after all).
Since I was working in 3D, I had to account for the "center" chunk occupied by the player, the eight chunks forming a square around it, and the two other square layers of nine chunks each above and below it for a total of 27 chunks at minimum. This was the smallest I could go while ensuring that at all times the player remained inside the universe and had a new chunk in front no matter which way the player happened to move, including diagonally. Technically I could get away with only six chunks forming a sort of 3D plus sign, but that would have allowed the player to come very close to the edges of the universe before actually leaving the center chunk, and the visible consequence would be seeing a big wall of nothingness a short distance away only for a wad of stars to suddenly pop in right in front of the camera.
I don't have an illustration of exactly how the system looked at this point, but I do have an illustration from a later edition that highlights the basic 27-chunk cuboid idea:
The player and universe object are represented by a white circle and square (I forgot which is which) and currently, since the universe follows the player, they occupy the same location, which is at the center of the center chunk, which has a faint blue highlight. It and the other 26 chunks all have a blue outline drawn around them and a little blue line pointing at their centers. In the early phases I hadn't engineered a shiny system for drawing cube gizmos to outline chunks, so I only had the blue lines given by the Debug.DrawRay function.
The idea here was that if the player left that center chunk, whatever new chunk it occupied would become the center chunk and a new cuboid would be formed around it.

No comments:

Post a Comment

Sorry this isn't a real post :C

I've entered graduate school and, as I expected, suddenly become far busier than I had been before, leaving no time to maintain my blog,...