<commit_before>---
layout: post
title: Remaking Tradewars - The Big Bang
date: 2015-07-07 23:01:33
disqus: n
---

### The Story

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](http://golang.org) 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

<table class="table table-condensed" style="border: 1px solid #CCC;width: 40%;margin: 0 60px;">
    <thead>
        <th>Name</th>
        <th>Neighbors</th>
    </thead>
    <tbody>
        <td>
            Terra IV
        </td>
        <td>
            <ul>
                <li>153</li>
                <li>6699</li>
                <li>981</li>
            </ul>
        </td>
    </tbody>
</table>

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

```
    create empty Universe
    fill Universe with W Sectors
    for each Sector as S:
        for between 1 and 4 (random number of 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 *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:

```
    create empty Universe
    fill Universe with K Sectors
    create empty Clusters
    pick random number K (where 10 > K > 0)
        add Cluster C to Clusters list
        for 0..K (where 5 > K > 0, a random number of Sectors)
            for 1..J (where 5 > J > 0, a random number of 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<commit_msg>Clarify some points.<commit_after>---
layout: post
title: Remaking Tradewars - The Big Bang
date: 2015-07-07 23:01:33
disqus: n
---

### The Story

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](http://golang.org) 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

<table class="table table-condensed" style="border: 1px solid #CCC;width: 40%;margin: 0 60px;">
    <thead>
        <th>Name</th>
        <th>Neighbors</th>
    </thead>
    <tbody>
        <td>
            Terra IV
        </td>
        <td>
            <ul>
                <li>153</li>
                <li>6699</li>
                <li>981</li>
            </ul>
        </td>
    </tbody>
</table>

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 *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
    pick random number K (where NUM_SECTORS / MIN_CLUSTERS > K > 0)
        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
{'fraction_non_alphanumeric': 0.06815772736909052, 'fraction_numerical': 0.013779944880220479, 'mean_word_length': 2.954316848281643, 'pattern_counts': {'":': 0, '<': 47, '<?xml version=': 0, '>': 55, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '6330618', 'n_tokens_mistral': 2815, 'n_tokens_neox': 2535, 'n_words': 1412}