Oasis

# 20 Jul 2015 Remaking Tradewars - Part III Ensuring Connectivity

### The Orphaned Sector Problem Revisited

In the first post, we initiated the Big Bang and made some iterations to create a Universe containing Clusters of Sectors. At the end of the post, we ran into an issue whereupon we might wind up with orphaned sectors.

Here's a recap of the algorithm itself:

``````    # Define some constants
define NUM_SECTORS = 1000
define MIN_NEIGHBORS = 1
define MAX_NEIGHBORS = 4
define MIN_CLUSTERS  = 10
define MIN_SECTORS_PER_CLUSTER = 2
define MAX_SECTORS_PER_CLUSTER = 20

# Begin Big Bang
create empty Universe
fill Universe with K Sectors
create empty Clusters

while still available Sectors
add Cluster C to Clusters list
for 0..K (where K = rng(MIN_SECTORS_PER_CLUSTER, MAX_CLUSTERS_PER_SECTOR)
for 1..J (where J = rng(MIN_NEIGHBORS, MAX_NEIGHBORS)
pick random available Sector as N (where N != S)
remove S from available Sector list

for each Cluster as C
pick random Cluster N (where N != C)
pick random Sector S1 in C
pick random Sector S2 in N
``````

For a simple Universe, you might wind up with Sectors in a Cluster like this:

See the problem? Once we go from from S1 -> S2, we can't get back to S1 -- ever! Big problem!

In Part II, I discussed a possible solution: using depth-first search (DFS) or breadth-first search (BFS) to detect orphan sectors, then attempt to connect them again.

It turns out, there's a better way.

### Tunnel Vision

This one took me awhile to figure out. As I was tinkering with the algorithms to get rid of the orphan sectors, I realized something: I was randomly connecting previously-randomized sectors. Why bother with the random connections if the sector numbers are already random? Just connect it to the next one in the list!

In other words, we have some clusters that look like this:

``````sectors = [1,2,3,4,5,6,7,8,9,10];
cluster1 = [6,3,1,7];
cluster2 = [2,9,4];
cluster3 = [10,5,8];
``````

Since each cluster is already randomized, let's just connect them in order!

``````cluster1: 6 -> 3 -> 1 -> 7
cluster2: 2 -> 9 -> 4
cluster3: 10 -> 5 -> 8
``````

Once each cluster's sectors are connected, connect the first and last sector of each cluster: ``` cluster1: 8 (cluster3) -> 6 -> 3 -> 1 -> 7 -> 2 (cluster2) cluster2: 7 (cluster1) -> 2 -> 9 -> 4 -> 10 (cluster3) cluster3: 4 (cluster2) -> 10 -> 5 -> 8 -> 6 (cluster1) ```

If you were to graph this, you'd get a circle, like this:

As you can see, it's possible to get from any sector to any other sector in the universe. Now that we know that's possible, all we have to do is add new connections at random within clusters. The algorithm looks something like this:

``````// First pass: Connect each sector sequentially
for C in Clusters
for S in C.Sectors
Neighbor = S + 1
if (Neighbor > number of sectors in C)
Neighbor = 0
endif

S.connect(Neighbor)
endfor

NeighborC = C + 1
if (NeighborC > number of clusters)
NeighborC = 0
endif

// Connect last sector of this cluster to
// first sector of next cluster
C.Sectors[last].connect(NeighborC.Sectors[0])
endfor

// Second pass: Randomly connect sectors
for C in Clusters
for S1 in C.Sectors
chance = Random(0, 100)
if (Random > CHANCE_OF_CONNECTION)
S2 = C.Sectors.Random
S1.connect(S2)
endif
endfor

// Select random cluster
C2 = Clusters.Random

// Connect random sector in C to random sector in C2
C.connect(C2);
endfor
``````

This might look something like this:

If you look at this carefully, you'll see that there are no orphaned nodes. The universe is 100% connected, but still looks pretty random!

If you're interested in exploring this a little more deeply, try modifying your algorithm to implement the following ideas:

• Use greuler or similar tool to generate a visual graph of your universe, like my examples above
• Introduce dead-ends (e.g., there's only one path to a node)
• Example: 2 <-> 6 <-> 8 (no other path to 8 but through 2 and 6)
• Introduce tunnels (e.g., only one path between A and B, but many paths to A and many paths from B)
• Example: 1,2,3 -> 4 -> 5 -> 6 -> 7,8,9 (no other path to 7 except through 4, 5, and 6)
• Write a test using DFS or BFS to ensure all nodes are reachable from every other node
• Write a function using Dijkstra's Algorithm to determine the shortest path from A to B, where A and B are different sectors. (Note: We will discuss this in a future post!)

Tune in next time for more Tradewars-esque fun!

Toodles!

-B