In space based 4x type games, you generally draw all the systems with lines linking the systems together denoting that you can travel directly between those systems.

In a randomly generated universe, how do you ensure that all systems are connected? i.e. there exists a path from every systems to every other systems, not direct links mind you, but a path through multiple systems.

I was thinking something like:

generate all systems, loop through all systems and make a link between it and the closest two systems.

But this could still result in systems that just connected to each other in a triangle fashion, and not to all the other systems.

**0**

# space 4x....all systems connected?

Started by ncsu121978, Oct 24 2010 05:21 PM

3 replies to this topic

Sponsor:

###
#2
Crossbones+ - Reputation: **1651**

Posted 24 October 2010 - 05:35 PM

Ideally you'd start with a complete graph and then remove edges. You probably don't want a minimum spanning tree? If you do then you could just generate a MST. If you don't want a MST then deciding when to stop removing edges would be a problem. I have an idea but it's probably expensive.

I'd create a complete graph with the weights between each system equal to the distance between the systems. Then divide all the distance by X and convert to integers where X is large enough to remove most of the edges. Then using the every pair path data from a floyd-warshall calculation remove all the unnecessary edges (edges that aren't part of a path). If you haven't removed enough edges (say you're targeting for 5% of a complete graph) then make X bigger. Kind of an odd way to solve it though and not a real-time solution for a large number of systems.

I'd create a complete graph with the weights between each system equal to the distance between the systems. Then divide all the distance by X and convert to integers where X is large enough to remove most of the edges. Then using the every pair path data from a floyd-warshall calculation remove all the unnecessary edges (edges that aren't part of a path). If you haven't removed enough edges (say you're targeting for 5% of a complete graph) then make X bigger. Kind of an odd way to solve it though and not a real-time solution for a large number of systems.

###
#3
Moderators - Reputation: **2956**

Posted 24 October 2010 - 06:35 PM

Rather than start with a bunch of systems which you must connect, start with one system and grow the rest from it. Put the first system in the queue. While the queue is non-empty and you don't hit a threshold, dequeue a system, generate a random number representing the number of lanes out of the system, randomly plot new systems within a desired range, check if existing systems exist in that range and randomly connect them or not, et cetera. Enqueue each new system. This can be tweaked in several ways, and should guarantee that there are no disconnected loops, and also provide you something you can re-run if you want a seemingly endless universe.

**Josh Petrie** | Core Tools Engineer, 343i | Microsoft C++ MVP