07 Jul 2015
Part I - The Big Bang
Back in my day, before new-fangled AOL and Prodigy, before broadband and 56kbps modems, there was the wonderful, wild-west world of the BBS (Bulletin Board System). Anyone with a computer and a phone line could set one up. Others could dial in, post on message forums and play games. Oh, games. The games.
L.O.R.D., Barren Realms Elite, and Tradewars. Tradewars was by far my favorite.
The premise was rather simple: you're a trader in a spaceship. The goal was to traverse the universe, buying and selling goods to accumulate money, or credits. With more credits, you could upgrade your ship, buy more holds (to carry more goods) or more weapons (to blow up other traders or aliens), and even buy your own planet and build a citadel!
It is with great nostalgia that I think back upon that game. It was text-only, with a sprinkle of ASCII color, but it captured my imagination.
Recently, I got to thinking about that game again. I had also gotten a hankering to learn Go and this seemed like a great opportunity.
The Big Bang
The first thing that happens when you set up a new Tradewars universe is The Big Bang. It's a quick program that instantiates the entire universe -- every sector, every cluster, every trading post, alien outpost, and planet.
You can think of each sector as a linked list. It contains its own data, plus the neighboring sectors. It might look something like this:
Each sector has a Name, Number, and list of Neighbors. Once we load a particular Sector, it's trivial to get to the next -- just select a neighbor and load it up!
Now, the hard part is generating this. Let's try a naive algorithm and see what happens.
First Pass Big Bang
# Define some constants define NUM_SECTORS = 1000 define MIN_NEIGHBORS = 1 define MAX_NEIGHBORS = 4 # Begin Big Bang create empty Universe fill Universe with NUM_SECTORS Sectors for each Sector as S: for 0..K (where K = rng(MIN_NEIGHBORS, MAX_NEIGHBORS)) pick random Sector as N (where N != S) add to S.Neighbors list
OK! So with this basic algorithm we've populated the entire universe, randomly connecting sectors with each other! Great!
Except... (you knew there was a "but", right?) This presents a handful of problems.
There Goes the Neighborhood
First, let's imagine the real universe. In our solar system, Earth is between Mars and Venus. On the other hand, Uranus is over 2.5 billion kilometers away from Earth. That's not even close. Would it make sense to say Venus and Earth are neighbors? Maybe they belong in the same community (we'll get to this later), but they are certainly not neighbors.
With our naive algorithm above, we're randomly selecting from W sectors. Imagine a 1000 Sectors. Earth could be paired with a "neighbor" from Alpha Centauri, which is light-years away.
The solution Tradewars came up with was to have a Cluster that contains nearby Sectors. You can think of a cluster as a solar system or a nebula or some other celestial body.
We can update the algorithm to look something like this:
# 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
There! Now we have a selection of Clusters that each contain Sectors.
But wait, now we have a bunch of Clusters with Sectors, but how does one get from Sector 1611 to Sector 258, if they're in different clusters? The clusters have to connect somehow.
Clearly, once we populate the Clusters, we have to link them together.
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
There's a minor flaw with this approach, which we can address in the next section
In the above algorithm, you'll notice that S2 is added to S1's Neighbors list, but S1 is not added to S2's neighbor list. In other words, S1 -> S2 is a one-way ticket!
This also raises another possibility: are there any sectors that have been orphaned? Imagine the following scenario:
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. Tune in next time for the answer in Part II.