Friday, July 13, 2018
Hail, spacefarers!
In today's log, I'm going to afford myself a mental break from talking about the economy again and instead walk you through how to build a universe with interesting structure, which is something that I have been doing recently to take a breather from pricing, economy, credits...it was all starting to drive me a little mad. I spent roughly another two weeks on it all, then decided that I really needed to dip my toes into something else before I started having nightmares about market orders. That being said, I was still thirsting to do something with a 'big picture' feel to it, since I have spent so much time on little pictures, hence this excursion into universe generation! It was a fun process, so I will share it in enough detail that you should be able to build your own universes if you so desire
Starting with Star Soup
Let's jump right in. For our purposes, building a universe consists, essentially, of building a graph (a collection of vertices and edges linking those vertices). Vertices represent systems, edges represent wormhole or jump gate connections between systems.
The most basic starting point is a random collection of vertices, distributed uniformly over a space. This is as boring as boring can get:
Still, we have to start somewhere...
Getting Connected with Kruskal's
If a uniformly-random distribution of points is the most basic way to generate vertices, then the most basic (sensible) way to generate edges is via a technique called the minimum spanning tree. For our purposes, what it means is that we want to 'connect the dots' in such a way that we are using as little 'distance' as possible. In other words, we want to make it possible to navigate from any system to any other system, but we also want to make the connectivity such that nearby systems are the most likely candidates for being connected. When you see it, you'll understand why we want to connect our systems like this
Luckily it's easy to write the algorithm for doing this! There are two great, easy choices: Kruskal's and Prim's. Since the former is slightly more general and I have written it many times before, I will use Kruskal's. They produce the same results when building a single MST.
Here is our soup of stars, this time connected with the MST:
Already looking better!
Notice how the connections are made in a very 'orderly' way. That's because of the MST. Connecting random stars will yield a far less attractive map.
Hierarchical Detail: Regions & Regional Substructure
Clearly, this universe is too boring. We would like to see more structure: stars within clusters within regions, etc. 'Real' physics aside, structure will make for far more interesting gameplay, and a better feeling of getting to explore an interesting universe.
Here's an idea: what if, instead of generating a bunch of uniform stars in a soup, we were to generate a few regions in a soup, then start 'attaching' stars to those regions? Let's try it. We'll generate 20 regions, then 1000 stars, each randomly attached to a region and with a 5% random exponential deviation from the regional center. Then we'll connect it all just like before.
The results are much more encouraging:
Note that I have given each region a random color here, and stars inherit their region's color, purely for the sake of being able to see the regions on this map. We will obviously draw this whole thing in a prettier way for the in-game UI
There are lots of ways we can tune the generating parameters to change the structure. For example, while I like the rather chaotic nature of these regions, you can change the system position-within-region distribution to gaussian instead of exponential to 'tighten up' the regional clustering. Here is what gaussian with 0.7% deviation looks like, using the same seed as above:
And, just for show, 50 regions with 2000 systems (back to exponential distribution):
(Yes, I too wish the colors were prettier...but remember...no getting distracted by...graphics...... )
Generating Shortcuts
At this point, things are looking quite nice. However, if you look carefully at the map and think about navigating around these systems, you may find that it seems quite tedious! Indeed, getting out of a distant 'corner' of space can take a lot of jumps. This is, in fact, by design! The minimum spanning tree is exactly that: it uses the least amount of 'connective line' that we could possibly use to make a connected universe. In particular, there is zero redundancy. Since it's a tree, there is also exactly one (non-overlapping) path from any point A to any other point B, never more. It's an efficient universe in terms of wormhole usage, but it's not very kind to the weary inter-regional merchant!
Looking at these maps, you can probably see 'obvious' places where you could draw an extra connection or two and really cut down on the amount of travel required to get around. For example, here's an annotated map where I've drawn in some obvious choices for extra connections that'd make things easier:
We'd like to generate such 'shortcuts' automatically. But how? Teaching the computer to identify good shortcuts is actually not so easy. We need a way to mathematically define good shortcuts. Intuitively, we want to choose two systems that are topologically far apart (that is, the path between them is very long), but are physically close. You will indeed note that this is a characteristic of all the sample shortcuts I drew above: they bridge systems that are physically close to one-another, but very very far apart in terms of the 'path length' between them.
So, all we have to do, for each shortcut we want to make, is: find the pair of systems whose ratio of travel distance to physical distance is the highest, and connect them. Turns out, this algorithm works really well for the most part. (Note: in reality, I use travel distance divided by the square root of physical distance, which encourages the algorithm to think more globally rather than making intra-regional shortcuts). Here are the first three shortcuts that the algorithm selects on the above map:
Hey! Look at that! Two of the three shortcuts the computer chose made appearances in my annotations (I swear I did not check before I annotated!) Sadly the algorithm did not come up with a space whale option, but it would be difficult to teach the computer to be as silly as me. We'll check out one more example, this time with 5 shortcuts:
I really like these choices
The shortcutting algorithm serves to make the map's structure even more interesting, since we now have more options for getting around, but we have introduced those options in a very specific way based on our goal of providing the most 'bang for our buck' with each shortcut.
Unfortunately, this shortcut algorithm is also computationally expensive. Computing all path lengths on a graph is expensive, and doing so in an efficient way is a significantly harder algorithmic challenge than computing the MST. I've played with a few cheaper ways of computing shortcuts, but none have come up with as good of results. I'm sure that, with a bit more thought and cleverness we could solve this much more quickly. For now, I'm pleased with the results, and will optimize more as I am able.
(Bonus) 3D
It should come as no surprise that all of the algorithms I've discussed extend effortlessly into 3D. In fact, while building the generator, I used 3D math the whole time, but kept a configurable constant that let me collapse the third dimension at will.
For Limit Theory, I have expressed that I will likely default to 2D universe maps; I prefer the simplicity. However, as demonstrated, it's effortless to enable 3D generation, so we can include that as a configuration option in the universe generator
(Bonus) Making it Infinite with Boundary Stitching
But wait! Limit Theory advertises an 'infinite' universe! So far we have only seen finite ones. What's the deal? The deal is quite simple, in fact. To make a universe infinite, all you need to do is 'tile' a finite one -- that is, use your 'finite universe' generator to generate content for each 'cell' of the universe, then find a way to stitch them together. Think of these screenshots we have seen so far as single 'pixels' in the infinite picture of the universe. The only interesting problem with this approach is how to connect the cells. In particular, if we want to make sure that the universe actually does go on forever (and that we can actually get to new systems forever), then we must make sure that the entire grid is connected.
The way to do this is very easy: choose a star system to represent each border of your tile (in our case, for a 2D grid tiling, we could call them N, E, S, W, for example), then connect the borders of adjacent tiles appropriately (the N border-system of a tile will be connected to the S border-system of the tile above it, etc.) To choose which systems should be border systems, there's an obvious answer: the system that is closest to the border (duh?) In other words, the northmost system in a tile will be our N border. To make all this clear visually, we can draw our border systems on the map and extend lines outward to indicate where our universe tile will be stitched to neighboring tiles:
So, when the player is getting to within topological proximity of one of those four border systems, we need to ensure that the appropriate adjacent tile in the universe is generated (and receives enough historical simulation to 'smooth out' border effects). The generator automatically identifies the border systems and flags them as such so that the engine will be able to handle preloading accordingly.
I have actually decided, over the course of LT development, that I don't want to play in an infinite universe, but would rather have a large, finite one (so that I am forced to get to 'know' it, rather than endlessly skipping town to the next cell). That being said, infinite universe generation is clearly one of the promises of LT, so I fully intend to support this tiling / stitching system despite my own preference to play without it (finite/infinite will be yet another universe configuration option).
By the way, in case it isn't clear, one very important property of the border stitching mechanism is that you don't have to generate the neighboring cell to know how it is connected to your current cell. This is in stark contrast to how we generated the finite universes above (we can't find the MST of an infinite graph, for obvious reasons!) This is the fundamental trade-off of infinite generation: you must have some topological regularity at some level. But, you see, we can play this clever trick of making each 'tile' of our regular grid a rather complex structure in its own right, which ensures that we get a much more interesting universe than if each cell in the grid corresponded to only one system.
(Update) Improving Local Connectivity
See this post for a simple technique to improve the local connectivity, which, as some have pointed out, is really too low with just the MST.
---
Alrighty, that took me a little too long to write, no surprises there, but you guys were patient to wait for it...so thank you
I will be getting back to my global economy work soon, but this multi-system work is also quite exciting, so I'm going to keep at it for a bit longer. I wanted to have a few more features like region names & system properties done for today, but I spent my time on the shortcut algorithm and the spatial faulting algorithm (which I cut from this devlog due to results not being that interesting) instead. Ah well! Perhaps next time
Hope you all have a great Friday!
Post
Fri Jul 13, 2018 8:11 pm
#1
[Josh] Friday, July 13, 2018
“Whether you think you can, or you think you can't--you're right.” ~ Henry Ford