15 February 2019

Procedural Chunk-Based Universe part 2 - the Universe Within the Universe

In Part 1 I explained how I set out to make a chunk system for representing huge game worlds and detailed how I started to tackle the problem.
So far I had planned out what I wanted to do in a vague sense and created a minimal implementation using only a fixed-size cuboid of 3x3x3=27 chunks. I went on to spend a while making these ever fancier and prettier, but a major constraint was making itself known: I couldn't render enough objects within my 27 chunks to represent anything like a fair imitation of a whole visible universe.

The real universe contains some objects that are very bright and visible at great distances, and other objects that are dimmer and only visible up close. In order to handle this practically, I realized that I would benefit greatly from my universe generator being able to be stacked, with "small universes" with small visible radii inside "large universes" with large visible radii. The small ones could handle nearby galaxies (currently represented by "star" sprites) and the large ones could handle distant, bright galaxies and galaxy clusters, rendering fewer of these.
The universe has a structure, however. It is believed to be "homogeneous" on the largest of scales, meaning any given huge volume of it looks roughly like any other given huge volume of it - galaxies aren't aligned to a grid and don't follow a gradient toward somewhere they all bunch up at the center of the universe (you may have heard of the Great Attractor, but while that is huge by our standards, cosmologists believe that other large gravity wells exist far away throughout the universe and that the universe as a whole isn't being pulled into any one place). On smaller (but still huge) scales, though, there is a distinct pattern called the "cosmic web":
Naturally I wanted to replicate this (and already had by implementing Worley noise, a.k.a. Voronoi noise or cell noise in my "star" placement code, as I mean to detail in a separate post), meaning I couldn't just spam stars at random locations in chunks of random scales. My noise function had to not only have a structure , but that structure had to be independent of whatever size I set for the visible universe. This would be far easier to accomplish if the chunks were a consistent size and stacked universes with variable visible radii could simply have variable numbers of chunks.
In conclusion, chunks had to be responsible for sampling 3D noise in a way that's consistent and deterministic regardless of how many of them have been spawned, what the visible radius of their parent universe is, where and in what order they have spawned, and whatever history the player may have of being in other places. Adapting my existing noise to this idea was fairly straightforward, but a paradigm shift had occurred in my progress on this project from this point forward.
As I've mentioned a redundant number of times, I had a 3x3x3 block of chunks, but if I wanted to make a universe of a different size whilst maintaining the same chunk size (and I could go no smaller), I had to develop a procedural tactic for generating a variable number of chunks around the player and arranging them in a ball. A cuboid would work, but its boundaries would be at highly varied distances from the player with some too close, causing "pop in", or some too far, causing redundant stuff to be spawned despite being excessively far away.
What I ended up producing was this.
The universe has a visible radius (indicated by the brown wireframe sphere) and a chunk size each set by the developer and which can have any value independent of one another. The program calculates how many chunks it takes on each axis to meet or exceed the visible radius, with a bit of padding so that it includes all chunks that would touch the visible universe in addition to those whose centers are inside it, and a minimum of 3 chunks on each axis, and uses this information to iterate through points in space that together form a large cuboid. In the screenshot here, each of these has been indicated with a small red line. The cuboid itself measures 5x5x5 chunks.
Chunks outside the visible radius, i.e. in the corners, won't be necessary, so while iterating through these points, the algorithm validates whether they fall within the (padded) visible radius and if so marks them with a small green line. The checks for the visible radius produce the faint green lines, and the padding added to the visible radius is shown by the faint blue lines.
I had the algorithm spit out some chunks on each of these validated points and got this:
Okay not this exactly - I'm using an anachronistic screenshot from a later version again, but it looks the same as what I had at this point.
By this point my derping around with 3D noise functions had given rise to a "Debug Noise" script that didn't bother with the actual Voronoi cells and instead just put some stars in a cube and game them all one color based on the current chunk's random seed (which was based on its world-space position). That cube could be scaled down a bit to more clearly display the boundaries between chunks as I still hadn't built the fancy outlining feature I showed earlier.
Note the blue line indicating each chunk that actually got spawned, the player icon in the center, and the blocky sphere measuring 5 chunks in diameter.
I was now able to make visible universes with arbitrary numbers of chunks, although unsurprisingly huge numbers of chunks led to huge performance drops. This was especially the case while my system didn't fully respect the persistent nature of chunks and would refresh every single chunk in the universe every time the player moved too far and a refresh was called. In the event of a player teleporting 80 billion light years into a completely new visible universe, this would be necessary anyway, but in more mundane cases like flying from one chunk into the next, most of the universe would remain unchanged and only a few chunks would fall out of visibility or come into view. That meant that I could instead have most of the actual chunks remain untouched and only refresh a few. I made sure to retain the option of refreshing all of them in case I wanted (note the buttons to force a full refresh and to "re-seed" the universe with a new random seed and rebuild all of the chunks based on that), but my next task would clearly be to create a mechanism for keeping track of which chunks existed and whether they really needed to be changed.
In Part 3 I plan to explain how I managed this and how it made my algorithm much more sophisticated.

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,...