space 4x....all systems connected?
Members - Reputation: 355
Posted 24 October 2010 - 05:21 PM
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.
Crossbones+ - Reputation: 1535
Posted 24 October 2010 - 05:35 PM
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.
Moderators - Reputation: 2653
Posted 24 October 2010 - 06:35 PM
Josh Petrie | Core Tools Engineer, 343i | Microsoft C++ MVP