20 Jul 2015
Remaking Tradewars - Part III
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.
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) 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!