• Create Account

We're offering banner ads on our site from just \$5!

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

Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

3 replies to this topic

### #1ncsu121978  Members   -  Reputation: 508

Like
0Likes
Like

Posted 24 October 2010 - 05:21 PM

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.

### #2Sirisian  Crossbones+   -  Reputation: 1774

Like
0Likes
Like

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.

### #3Josh Petrie  Moderators   -  Reputation: 3191

Like
0Likes
Like

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 | Game Developer, Undead Labs

### #4ncsu121978  Members   -  Reputation: 508

Like
0Likes
Like

Posted 24 October 2010 - 06:39 PM

@jpetrie - bingo. sounds like an excellent idea. im gonna give it a try first

Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

PARTNERS