16 Jul 2015
Remaking Tradewars - Part II
EDIT: I've actually come up with a better algorithm to ensure 100% connectivity. Please check Part III to see how I did it! The below search algorithms are still necessary, but for different reasons, so feel free to keep reading. Check Part III for the new algorithm, though!
The Orphaned Sector Problem
In the previous 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!
How do we solve this? Well, that's the $64,000 question.
The way to ensure that we have no orphaned sectors is to travel from each sector to every other sector. If we can make it from A -> B, A -> C, ..., A -> N, and then from B -> A, B -> C, ..., B -> N, and so on, then we have ensured that every Sector is reachable from every other Sector.
Right off the bat, though, you can tell that this is a very inefficient algorithm. For N sectors, we're going to check every other sector N times, for O( n2 ) complexity.
Here's a basic algorithm:
function dfs(graph, v): let S be a stack S.push(v) while S is not empty v = S.pop() if v is not labeled as discovered: label v as discovered for all sectors from v to w in graph.adjacentEdges(v) do S.push(w)
In plain English, it works like this: Imagine you walk into a house. In the foyer, there are three neighboring rooms: the living room, the kitchen, and the office. You mentally mark the Foyer as "discovered." You pick one (the living room) and go there first. The living room has two neighboring rooms: the foyer and a closet. You mentally mark the living room as "discovered" and you enter the closet. There are no neighbors, so you back out to the living room. There are no undiscovered rooms, so you back up to the foyer. Now you've already visited the living room, so you move to the next neighboring room -- the kitchen. This process repeats itself.
By skipping rooms you've already discovered, you can prevent getting stuck into an infinite loop (foyer -> living room -> foyer -> living room -> foyer...).
The downside to this process is that the stack
S can get very, very large. Depth-first search algorithms often suffer from non-termination -- that is, the universe can be so big that it just never finishes because it's almost impossible to traverse them all in good time.
Now let's look at Breadth-First Search.
Here's a basic algorithm from Wikipedia:
function bfs(graph,v): let Q be a queue Q.enqueue(v) label v as discovered while Q is not empty v ← Q.dequeue() process(v) for all edges from v to w in G.adjacentEdges(v) do if w is not labeled as discovered Q.enqueue(w) label w as discovered
The first major difference is that we're using a queue instead of a stack. The difference is minor but important. A stack is like a stack of plates. In order to get to the bottom plate, you have to remove the top plates (pop them off). This is a last-in-first-out (LIFO) approach. A queue is more like a line at the bank. In order to get to the teller, you have to wait for all of the previously added people to finish. This is a first-in-first-out (FIFO) approach.
It turns out that the complexity of this is basically the same as DFS, but depending on the topography of the graph, the best case scenarios might be faster.
Here's a visual example of what it looks like:
See how it evaluates each level before it goes on to the next? Contrast that with Depth-first search, which traverses all the way down the tree before going to the next branch.
Putting it all together
Now all we have to do is pick one of these algorithms, start the graph at Sector 1, conduct the search, and return a list of orphaned sectors. For each of these orphaned sectors, we connect them to another sector in the cluster, then continue on. It might look something like this:
for C in Clusters for S in C.Sectors while (orphans = DFS(S)) for O in orphans N = RNG(C.Sectors) // Pick a random sector in this cluster add O to N.Neighbors list
Be warned: this might take a LONG time for large numbers of sectors! However, once it's done, we should have a fully connected universe!
In the next post, we'll actually start writing some code.