Return to “Dev Logs”

Post

[Josh] Friday, July 13, 2018

#1
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:

Image

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:

Image

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:

Image

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:

Image

And, just for show, 50 regions with 2000 systems (back to exponential distribution):

Image

(Yes, I too wish the colors were prettier...but remember...no getting distracted by...graphics...... :monkey:)

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:

Image

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:

Image

Hey! Look at that! Two of the three shortcuts the computer chose made appearances in my annotations :D (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:

Image

I really like these choices :thumbup:

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.

Image

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 :nerd:

(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:

Image

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 :geek:

Hope you all have a great Friday! :wave:
“Whether you think you can, or you think you can't--you're right.” ~ Henry Ford
Post

Re: [Josh] Friday, July 13, 2018

#2
Ooh, Purdy!

Also, it's about damn time we saw some multisystem work, I don't think there's been any of that since LTP :ghost: and as usual, your work is impressive.

In regards to the shortcuts, I'm not sure I like that method, especially if it's as computationally expensive as you suggest. Might it not be better to select a random assortment of systems, with at least 1 in each region and then give this selection their own parallel tree?

Also, I'm wondering what your feelings on artificial wormholes are. Do we just have these natural networks or can we make our own? If we can make our own, then perhaps the shortcuts would be entirely artificial, where you have to send 2 beacons to the systems you want to connect through the natural network, activate the wormhole generator and boom, worm...bridge? Wormpanamacanal?
Image
The conquest of Nature is to be achieved through Number and Measure.
It's better to have questions you can't answer than answers you can't question.

Imagination Fertilizer
Post

Re: [Josh] Friday, July 13, 2018

#3
Nice update, with shineys :)
Hyperion wrote:
Fri Jul 13, 2018 8:57 pm
In regards to the shortcuts, I'm not sure I like that method, especially if it's as computationally expensive as you suggest. Might it not be better to select a random assortment of systems, with at least 1 in each region and then give this selection their own parallel tree?
It's a one time cost per tile, and is relative to the number of stars (likely the square or higher power). So the trick would be to have an upper bound on the number of stars in a tile, beyond which the tile generation time becomes too boring.

Other tricks could include generating tiles in a lower priority thread, starting when the traveler is, say, 4 systems away, rather than at high priority in the main thread when the traveler is 2 systems away.

regards,
Charles
Post

Re: [Josh] Friday, July 13, 2018

#5
Hyperion wrote:
Fri Jul 13, 2018 8:57 pm
In regards to the shortcuts, I'm not sure I like that method, especially if it's as computationally expensive as you suggest. Might it not be better to select a random assortment of systems, with at least 1 in each region and then give this selection their own parallel tree?
I'm not positive that it's the same as what you're suggesting, but I played with several (cheaper) variations, including generating the tree in two stages, first at the regional level and then the system level. For the most part something like that is fine, although it doesn't look quite as visually appealing. I found it surprising how strict my own sense of aesthetics turned out to be with respect to these shortcuts. Of course, my sense of aesthetics isn't necessarily what's important.

At any rate, I'm certain that there's a better solution out there somewhere that isn't as expensive. I think doing something in a hierarchical way will give good enough results (I believe this is effectively what you're getting at with your '1 in each region' tree).
Hyperion wrote:
Fri Jul 13, 2018 8:57 pm
Also, I'm wondering what your feelings on artificial wormholes are. Do we just have these natural networks or can we make our own? If we can make our own, then perhaps the shortcuts would be entirely artificial, where you have to send 2 beacons to the systems you want to connect through the natural network, activate the wormhole generator and boom, worm...bridge? Wormpanamacanal?
I have mixed feelings about on-demand bridging and am not ready to make a statement on the subject :ghost: I find it very likely that some form of controllable wormhole tech will exist, but this is a really delicate matter of balance to me, and I don't have the right set of limitations nailed down for those mechanics.
“Whether you think you can, or you think you can't--you're right.” ~ Henry Ford
Post

Re: [Josh] Friday, July 13, 2018

#6
Very cool, I forget now how I was doing mine, but one of the considerations was that ANY star could randomly be connected to any other, but was FAR less likely to be attached to one outside it's region, and would attempt to draw the lines in such a way that the stars wouldn't draw lines that would intersect any other line, or cross too close to another star, to help keep the map readable. There was also code that made the first two links very common, and any further links much less likely. Stellaris, for instance, has found that fewer links allow regions to form better, and regions make space empire building more fun.

Now, suggestion:

Build your 3D map with considerations for 2D viewing. Don't pull a Elite Dangerous, or an EVE: Online, make the map CLEARLY readable when you are showing it in 2D, and have that the default format for the map.
Most people find it hard to navigate in 3D, so this will help keep the user experience comfortable, with the lack of links crossing each other it will also make it easy to do a visual route calculation, not just a system generated one. This is important so players can quickly check a map and see how they should navigate around the systems.
°˖◝(ಠ‸ಠ)◜˖°
Toba - A Development Dump
Post

Re: [Josh] Friday, July 13, 2018

#7
For the shortcut system wouldnt a two-step process help?

The position of a star can be approximated with the position of its cluster and topological distance will be equivalent as well.
So wouldnt a first pass be to just check which clusters need a shortcut and afterwards find out which exact stars? (And in the cluster some spatial octant/quadrant sorting to weed out stars that are on the opposite side)

Would strongly reduce the N for what seems to be some O(N!) complexity problem.

(I also only just woke up after a whole day of partying, so my thoughts may not be as coherent as they feel to me...)
Post

Re: [Josh] Friday, July 13, 2018

#8
Cornflakes_91 wrote:
Sat Jul 14, 2018 12:31 am
For the shortcut system wouldnt a two-step process help?

The position of a star can be approximated with the position of its cluster and topological distance will be equivalent as well.
So wouldnt a first pass be to just check which clusters need a shortcut and afterwards find out which exact stars? (And in the cluster some spatial octant/quadrant sorting to weed out stars that are on the opposite side)

Would strongly reduce the N for what seems to be some O(N!) complexity problem.

(I also only just woke up after a whole day of partying, so my thoughts may not be as coherent as they feel to me...)
Clusters can have an z,x,y for their mass center, and a list of all the clusters they are linked too, you can then sort by inverse physical distance and link distance.
Then you check stars on the edge of the clusters in question that dont have too many links, and find possible links that wont make the map look bad.
°˖◝(ಠ‸ಠ)◜˖°
Toba - A Development Dump
Post

Re: [Josh] Friday, July 13, 2018

#9
Nice update!

Personally, I detest the one-link-per-star results: especially since tile border stars get two links anyway.
It's just very immersion breaking for me - the only reason you'd implement it is for an artificial limitation.

One reason I don't play EVE Online is for this problem: although they have multiple links per system, they very frequently miss out links to systems that are closer than the existing links, forcing us to travel long paths out of the way, frequently into or through danger, just because CCP don't want to make it too easy.
But it's worse than that with one link per star: you can blockade entire regions or trap NPCs artificially by simple point defence.

Mostly though, I don't like it because logically it wouldn't happen, for the same reason we have the trade routes not being forced to have one route per asteroid. If you have a close-by system, you would have a gate to it.

Also, on the idea of simpler link/shortcut generation; could you treat the regions the same way you do the larger tiles, and have four/six fixed links out of the region to hook up to other regions? Makes a slightly fractal link generator that might be considerably quicker and easier.
--
Mind The Gap
Post

Re: [Josh] Friday, July 13, 2018

#11
I agree that the connectivity factor is generally too low in these maps. While I like the idea of being able to hide in a dead-end, hard-to-get-to corner of space, there's too much of that going on here. I will improve the connectivity.
“Whether you think you can, or you think you can't--you're right.” ~ Henry Ford
Post

Re: [Josh] Friday, July 13, 2018

#12
Niiiiiice. Thanks, Josh!

I can't resist noting (as Ringu intimates) that the only reason we're even looking at algorithms for generating plausible-and-fun connections between certain star systems is because the game universe isn't continuous. If there were just "space" all over, you could simply fly from anywhere to anywhere.

Note that a continuous universe still has structure because stars still exist at some distance from each other. As long as you impose some limitation on long-distance travel speed, such as by capping the maximum distance that FTL engines can jump a ship, and perhaps imposing a small fuel cost proportional to distance traveled, trade routes and other networks will still emerge naturally. This happens without any need to predetermine allowable routes (vertices between nodes)... and with the benefit that interesting things can exist outside the "physical" areas of star system nodes. (Note that this also makes the universe a little more amenable to rendering some multi-star-system effects as area fields. Of course you can still do fields in a node-and-vertices arrangement, but my impression is that this is a little simpler in a world that's already continuous.)

You might still want to do a tile-based approach to dynamically generating new clusters of star systems. (Preferably a hex grid!) The point is, a continuous universe eliminates the need to figure out which stars are connected to which during universe generation: they're all connected.

I'm going to go ahead and assume "continuous universe" is off the table at this point. :D Just considering an alternative -- maybe there's some utility to temporarily setting aside the nodes-and-vertices assumption.

Mostly, I'm just glad to see some thinking time going into universe generation and how emergent dynamics will span multiple star systems. That's a big milestone to hit!
Post

Re: [Josh] Friday, July 13, 2018

#13
Flatfingers wrote:
Sat Jul 14, 2018 1:54 pm
Niiiiiice. Thanks, Josh!

I can't resist noting (as Ringu intimates) that the only reason we're even looking at algorithms for generating plausible-and-fun connections between certain star systems is because the game universe isn't continuous. If there were just "space" all over, you could simply fly from anywhere to anywhere.

Note that a continuous universe still has structure because stars still exist at some distance from each other. As long as you impose some limitation on long-distance travel speed, such as by capping the maximum distance that FTL engines can jump a ship, and perhaps imposing a small fuel cost proportional to distance traveled, trade routes and other networks will still emerge naturally. This happens without any need to predetermine allowable routes (vertices between nodes)... and with the benefit that interesting things can exist outside the "physical" areas of star system nodes. (Note that this also makes the universe a little more amenable to rendering some multi-star-system effects as area fields. Of course you can still do fields in a node-and-vertices arrangement, but my impression is that this is a little simpler in a world that's already continuous.)

You might still want to do a tile-based approach to dynamically generating new clusters of star systems. (Preferably a hex grid!) The point is, a continuous universe eliminates the need to figure out which stars are connected to which during universe generation: they're all connected.

I'm going to go ahead and assume "continuous universe" is off the table at this point. :D Just considering an alternative -- maybe there's some utility to temporarily setting aside the nodes-and-vertices assumption.

Mostly, I'm just glad to see some thinking time going into universe generation and how emergent dynamics will span multiple star systems. That's a big milestone to hit!
Flat, continuous universe maybe, but as a hyperspace cell? If you have a Hyper drive, you don't need wormholes, you can hop out of your dot into the local hyperspace cell, and then zoom over to another dot in the cell, and pop back into a different system. This may make hyperspace travel feasible within dense clusters, but far less so in trying to travel between clusters. This sort of mitigates the problem of one wormhole link per system while still making wormholes, especially ones that go to another cluster their own soft bottleneck for travel. The wormhole network would be like a highway, especially if warp rails connected the wormholes.

Also, if it's hyperspace, you can combine effect zones that affect systems with space-terrain in hyperspace.
Image
The conquest of Nature is to be achieved through Number and Measure.
It's better to have questions you can't answer than answers you can't question.

Imagination Fertilizer
Post

Re: [Josh] Friday, July 13, 2018

#14
Have you ever played stellaris? The have a lane system for their systems in galaxies that is pretty good.

https://goo.gl/images/juof1R

https://goo.gl/images/TtA8uy

https://steamuserimages-a.akamaihd.net/ ... 80028F218/

From what i can see they just use more connections between their stars than what you are using in your tests.
Build a man a fire, and he'll be warm for a day. Set a man on fire, and he'll be warm for the rest of his life.
Post

Re: [Josh] Friday, July 13, 2018

#15
The fact that space is so chock-full of nothing makes it difficult to develop terrain that actually means something for travel. What's a few million kilometers' detour if you're already traveling lightyears? It's also difficult to credibly "blockade" space, in no small part because you have to block an entire extra degree of freedom. How do you protect the borders of your empire from incursion? Patrol routes would have to cover an entire surface of obscene area, since your empire presumably extends over multiple star systems, and they would have to cover it densely enough to repel invaders from any part of the surface. Otherwise every system in your empire would be a frontier system, and it would have no "heart" of safe systems. Graph-based space resolves problems like this by reducing the area you need to patrol to just the link endpoints, and only those on the topological border of your empire.

Online Now

Users browsing this forum: No registered users and 1 guest

cron