For several years, I’ve wanted to build a space-opera roguelike, where players can take on interstellar adventures, meet exotic aliens, and explore uncharted systems. Think No Man’s Sky meets Dwarf Fortress. As the game grows and evolves, I’ll talk more about the actual mechanics, but in this post I’m going to introduce the galaxy generation system, which was the area I started working on.

World Generation Overview

World generation is the first stage of game play. Players generate a world file, which their characters can live in and explore. Players of Dwarf Fortress will be familiar with this pattern. Procedural generation is my preferred form of art, so I wanted to tackle this system early.

At a high level, the game world is stored in a hierarchical tree, the top level of which is the Galaxy object. For the purposes of this post, the Galaxy’s only child is a Starmap, which we will see later.

Creating Some Stars

The Galaxy object has four methods of interest:

We’ll see bake_starmap in the next post. Let’s take a look at how we lay out the galaxy.

class Galaxy:

    # ...

    def add_disc(self, n, x=0, y=0, x_std=1.0, y_std=1.0):
        """Add eliptically distributed systems to the galaxy"""
        for _ in range(n):
            x_coord = random.normalvariate(x, x_std)
            y_coord = random.normalvariate(y, y_std)
            
            position = (x_coord, y_coord)

            # Use your imagination for this part.
            system = System()
            system.set_position(position)

            self.add_star(system)

This method lets us add a randomly distributed disc to the galaxy’s star list. Its inputs are a count of stars and the distribution parameters. In Voidstar’s actual code, this method takes additional parameters that let the worldbuilder customize what types of stars show up. That way, we can have different star type distributions on the spiral arms than in the core (and other possible configurations).

Tall and skinny disc Tall and skinny disc

Circular disc Circular disc

By combining two skinny discs, two wide discs, and one small circular disc, we get a large cross that will form the arms of our galaxy:

Cross galaxy Swirled galaxy

Giving It Some Style

The next method is swirl, which requires a couple helper methods. These are mathematically fairly simple.

where a is the configurable swirl factor. The 20th root of the distance may raise eyebrows, but in testing I found this to produce the best output. However, this changes drastically with different standard deviations in the star distributions, so it may warrant some inspection.

class Galaxy:

    # ...
    
    def swirl(self, factor=1.0, about=(0, 0)):
        """Swirl the galaxy"""
        for star in self.stars:
            dA = factor * (1/_distance(star.position)**0.1)
            position = star.position
            star.position = _rotate(position, dA, about) 

    # ...

def _distance(point):
    x, y = point
    x = float(x)
    y = float(x)
    return math.sqrt(x**2 + y**2)


def _rotate(point, angle, about):
    x, y = point
    about_x, about_y = about
    x -= about_x
    y -= about_y
    x_new = x * math.cos(angle) - y * math.sin(angle)
    y_new = x * math.sin(angle) + y * math.cos(angle)
    return (x_new + about_x, y_new + about_y)

The swirl function took a few interations to get right. It turns out that factor needs to be closer to 100 to produce realistic looking output.

Swirled galaxy Swirled galaxy

Ease Up!

The last function we need to make a pretty galaxy is a jitter function, which quickly eases up any hard lines we may have picked up when adding and swirling the discs:

class Galaxy:

    # ...

    def jitter(self, factor=1.0):
        """Randomize the positions of systems"""
        for star in self.stars:
            x, y = star.position
            x += random.uniform(-0.1, 0.1) * factor
            y += random.uniform(-0.1, 0.1) * factor
            star.position = (x, y)

The jitter and swirl factors can be used to create more evenly distributed systems within the Galaxy. They will likely be configurable parameters at worldgen.

Swirled galaxy Swirled galaxy

Tying It All Together

We need to get all of this into a harness so we can see what it does:

# Change this one for more or less dense galaxies
STARS = 10000

# Calculated values, but feel from to experiment
ARM_STARS = 99 * STARS // 100
WIDE_ARM = 4 * ARM_STARS // 10
THIN_ARM = ARM_STARS // 10
CORE = STARS // 10

BASE_SDEV = 1.0
WIDE_ARM_SDEV = 0.2
THIN_ARM_SDEV = 0.04
CORE_SDEV = 0.1

def make_galaxy():
    galaxy = Galaxy()
    galaxy.add_disc(WIDE_ARM, x_std=WIDE_ARM_SDEV, types=COOL)
    galaxy.add_disc(THIN_ARM, x_std=THIN_ARM_SDEV, types=MEDIUM)
    galaxy.add_disc(WIDE_ARM, y_std=WIDE_ARM_SDEV, types=COOL)
    galaxy.add_disc(THIN_ARM, y_std=THIN_ARM_SDEV, types=MEDIUM)
    galaxy.add_disc(CORE, x_std=CORE_SDEV, y_std=CORE_SDEV, types=HOT)
    galaxy.swirl(factor=SWIRL)
    galaxy.jitter()
    return galaxy

We’ll want a way to look at the map. For that, I’m using matplotlib:

def plot(galaxy):
    import matplotlib.pyplot as plt
    data = map(lambda star: (
        star.position[0],
        star.position[1]
    ), galaxy.stars)
    x, y = zip(*data)
    plt.scatter(x, y, alpha=0.5, marker=".")
    axes = plt.gca()
    x_min = min(x)
    x_max = max(x)
    axes.set_ylim([x_min, x_max])
    plt.show()}

Here, we’re pulling the data from the stars and unzipping it into two lists, using the special operator *, which tells zip to perform the inverse operation.

Then, we’re generating a scatterplot with a nicely fit window.

Now, kick the whole process off:

if __name__ == "__main__":
    import matplotlib.pyplot as plt
    import random

    t1 = time.time()
    galaxy = make_galaxy()
    t2 = time.time()
    print("Generated world in {0}s".format(t2-t1))
    plot(galaxy)