07 Jul 2015
Remaking Tradewars
Part I  The Big Bang
The Story
Back in my day, before newfangled AOL and Prodigy, before broadband and 56kbps modems, there was the wonderful, wildwest 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 textonly, 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:
Sector 100
Name  Neighbors 

Terra IV 

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.
The 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 lightyears 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
Forever Alone
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 oneway 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.
B