scribble

Oasis

About     Blog     LinkedIn     GitHub    

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)
                add to S.Neighbors list
            add S to C.Sectors list
            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
            add S2 to S1.Neighbors list

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:

  • Add more sectors!
  • 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

scribble

About     Blog     LinkedIn     GitHub