Evening, folks!

We’re aware of a crash bug effecting OS X users since v1.0.3 and we’re working on a fix – we’ll let you know more as soon as we can! In general, at the moment we are working on another patch containing some fixes and small adjustments, and we’ve started working on our first post-1.0 content update. :)

It’s been a while since we had a real technical dev blog, though, so for tonight Tccoxon’s written up a post about how he built Starbound’s procedural quest system!

~Mollygos

Since Starbound hit 1.0, I’ve found myself looking back over my contributions over the last couple of years. I feel incredibly lucky to have had the chance to work on Starbound, and be a part of the community. I know the rest of the team here in the office does too.

One of my favorite features in Starbound is procedural generation – the way it produces endless distinct planets to explore, the way every weapon you find is different, and every NPC has a unique appearance. I know that from a design perspective, procedural generation is often inferior to hand-designed content… but designing a procedural system that produces pleasing results is still an interesting puzzle that fascinates me. (And has been central to the concept of one of my other projects, Lenna’s Inception.)

So I jumped at the chance to build a procedural quest system for Starbound!

We had three main goals for a procedural quest generation system. The first goal was encouraging the player to explore more, playing to Starbound’s strengths. Exploring in Starbound is fun. Walking across the surface of a new planet, you’ll encounter monster fights, treasure, new building and crafting materials, dungeons to clear out, friendly NPCs with something to say, and occasionally hostile NPCs to engage in combat with. So to make the best use of Starbound’s other features, the quest system should encourage you to explore the planet you’re on.

Second to that, distant parts of a planet in Starbound often don’t have anything to connect them. For example, a planet can have a floran village and an avian temple on it. You might wonder about how these two groups interact and relate, but the chances are they’re distant enough that the NPCs that live in them never see each other. A good procedural quest system that involves both of these places can provide more context and story. If you rescue a floran that has been kidnapped by avian fanatics from the temple, you can read into that and determine that there is some tension between these two groups.

Many games have repeatable quests that quickly become dull. One of the reasons for this (in my opinion) is that the quests often have no meaningful cause or effect. If an NPC has asked me to kill the rats in her basement ten times in a row, I begin to wonder why the rats are entering her basement, why the NPC is not doing anything to keep them out, and what effect my actions are having on the local rat population. I feel dissatisfied knowing that there is no cause or effect for this quest. IMO, good quest generation systems should at least try to give their quests some semblance of meaning, so I made that the final, aspirational goal.

Starbound isn’t the first game with a procedural quest system. Skyrim has probably the best known quest generator, Radiant. Most quests produced by Radiant consist of a randomly chosen location, enemy type and reward. The locations can be things like homes, businesses and dungeons. The type of quest you get, whether an assassination or theft, depends on who gives you the quest.

The stated goal of Radiant was to get the player to explore locations they haven’t been to before. It achieves this, I believe, and it also happens to do reasonably well at producing meaning. I think it’s because of that that I didn’t realise I was playing procedural quests until I was half a dozen quests in. :D

Radiant quests generally have some sort of cause — you receive theft quests from the thieves’ guild because you’re a thief — and sometimes an effect — someone you’ve stolen from can seek revenge. What I think reduces the meaningfulness of Radiant quests is that the same causes and effects are used repeatedly. There just isn’t much variety. With Starbound, we experimented with an idea to produce a wider variety of causes and effects.

Earlier in development, Starbound had a series of placeholder quests to make a cup of coffee for an NPC. The sequence was something like:

1. Find coffee beans and use a machine them into coffee liquid
2. Find sand and craft it into glass to make mug
3. Find silver, craft it into a spoon and use it to stir the coffee in the glass

It’s not a great story line, but each quest in the sequence does exhibit purpose, cause and effect. That’s partly because the result of each quest is used in the next. That’s a pattern that’s easy to formalise and use in a generator:

1. Get A.
2. Use A to get B.
3. Use B to get C.

The quest generator in Starbound doesn’t generate just individual quests, it plans entire sequences of quests (like the above) that achieve an NPC’s goal. Surprisingly, this isn’t really anything new. At its core, the quest generator is something known as a regression planner — an algorithm that has been known about for at least 40 years. This may simply be its first use for generating quests in a commercial video game.

What a regression planner does is find a sequence of actions that will take it from the way things currently are, to a world where its goal has been achieved. A futuristic household robot might use a regression planner when you ask it for a cup of coffee. It would work backwards from its goal (a cup of coffee in your hand) to determine that it needs a cup of coffee in its own appendage, and in order to get there it needs a clean cup, some fresh coffee and a spoon to stir it with. The fresh coffee would need brewing. And in order to brew the coffee it needs some beans…

In the case of the quest generator, the goal is randomly chosen from a pool. It can be anything from finding the NPC a new friend, improving the state of the village, broadening a merchant’s stock, gaining influence over another NPC, or finding a stylish new hat.

I didn’t have the heart to tell him!

These goals are especially designed to produce permanent effects on the world, and many of them can affect the generation of later quest sequences. For example, when you’ve completed a quest to help an NPC assert dominance over another NPC, he/she can later use that influence in another quest to extort the victim for a needed item.

By giving each goal a permanent effect, and having each quest serving the next quest, I think we’ve done a decent job of making sure Starbound’s procedural quests are meaningful. Some quests and goals work better than others, but overall I’m pleased with how it works, and I hope our players enjoy them. :)

One of the things I learned while building this system is that, depending on the context, even bad or stupid procedural generation can be positive. The first sequence I remember Starbound generating was one where an NPC wanted to make friends with his neighbour… so he asked me to steal his neighbour’s torch off the wall, and then give back to the neighbour as a gift from him. The neighbour was so delighted to have a torch again, they became instant friends!

The reason this is funny instead of jarring is that the NPCs in Starbound always look dumb, thanks to their cartoony emotes and exaggerated behaviours. So if you know you’re going to be using procedural generation in a project, you can design the context around it to turn its mistakes into (in the legendary words of Bob Ross) happy accidents.

Starbound was pretty much the perfect environment in which to experiment with procedural quest generation, thanks to its cartoony NPCs and wide variety of mechanics and activities.

I’ve also learned how to make a better quest generation system.

Starbound generates multiplayer quests. Multiple players can accept a quest, and what happens — whether they can all complete it together or whether they must compete for the reward — depends on which quest it is. I think this was a mistake because it complicates the system and prevents the generator from reasoning about the player’s progress. Quests individually tailored to each player would be much better. The generator would know what the player’s been doing on other planets, it could involve their other colonies, and tailor the difficulty of enemies more precisely. Right now, it can’t make any such assumptions about the player.

Quests with branching paths and multiple actors would allow the player more freedom to complete quests the way they want. Right now, quest sequences have only one ending, but theoretically multiple endings could be generated with a more advanced iterative planning algorithm. If you receive a quest to steal an NPC’s item, an alternative quest could be provided that allows you to report that NPC to a guard instead. Branching quests probably wouldn’t fit Starbound very well, but would be interesting to see in other games!