Cooking Up Gumbo

written by Kevin Maloney and Sheridan Thirsk of Harebrained Schemes

Our most recent release, Shadowrun: Dragonfall - Director’s Cut (DFDC), features an in-house AI system that we developed called “Gumbo.” In this article, we will detail how Gumbo came about, what our goals for the system were, and how, in the end, it largely accomplished them. We hope that our takeaways from this project will be helpful towards your own turn-based (or real-time) AI endeavors.

First, a little background. After a Kickstarter campaign that ended successfully in April, 2012 with $1.8 million in funding, Shadowrun Returns shipped on July 25, 2013. Seven months later we released a major DLC expansion entitled Shadowrun: Dragonfall, and on September 18, 2014 we released Shadowrun: Dragonfall - Director’s Cut.

The Dragonfall DLC began as a stretch goal in our Kickstarter campaign. However, by the time it went out the door, it had grown into a full expansion that improved on many aspects of the core game.

Both the team and the community responded positively to the improvements in Dragonfall. Still, the team felt that a stronger version of Dragonfall was possible. Thus, we embarked on creating Dragonfall - Director’s Cut. Free to all owners of the DLC, DF-DC was not only an improved version of Dragonfall, it was also now standalone, so new fans could jump right in to our latest and greatest.

When we came up with a list of areas that we wanted to invest in for DF-DC, smarter AI was high up on the list (especially given that combat was also being overhauled). Both Shadowrun Returns and Shadowrun: Dragonfall used AI derived from a branching tree of xml edited in Unity. They also used custom code to read data and perform actions in the game. While this system succeeded in giving a variety of enemies’ basic behaviors, we felt that there was room for improvement on several fronts. With the existing system, any tuning or unique behaviors that designers wanted to make required engineering support, followed by the lengthy process of rebuilding our assets and code. This made iteration very slow and hid the AI agent’s decision-making process from the designers.

Goals

In game theory and economics, the term utility describes the ability to satisfy an AI agent’s needs and wants. In our games, we want to maximize agent’s utility in three ways, to reduce amount of damage taken, to assist allies, and to maximize amount of damage to the enemies. Often these goals require a sequence of actions, each with potential random elements and failure points. In an intelligent dynamic world, the AI agents should still make decisions which have high utility.

These were our primary development goals.

Easy

Designers should be able to set up characters, items, and maps in line with their vision of what combat should look like. The AI should act as the final piece to realize their design goals. Each decision made by the AI agents should be visible and editable by the designer if desired.

Safe

Recursion or failure in a turn-based game can be quite bad. In our first game, we implemented “brain freeze timeouts” if we detected that the AI tree was stuck or looping. This was a practical solution, but not an ideal one. A new AI solution would need to make all possible problem areas fail gracefully without being obvious to the end user.  

Expandable

The point where an AI has a basic set of actions and operations is just the first stage of development. Because of this, additional features in any potential area would need to be easy to plug into the AI. Common patterns would be condensed into a single feature to create consistent designs, reducing the potential for error.

Fast

While a turn-based game may seem slow, the AI’s decision-making process needs to happen very quickly. When an AI agent arrives at a tile and decides to perform an attack, a pause between those two actions is detrimental because it occurs frequently. Similarly, all NPCs on the whole map get a slice of time to think even if they are “non-combatants”, because their combat status could change at any time. Our new AI would need to be fast to account for all of this.
 

Our Solution

We decided to create a lightweight new script language called GumboScript.  

One member from our Kickstarter community asked why we didn’t use LUA, or another script that is established and documented. While the extra capabilities provided by full-featured scripts have their advantages, some features did not meet our goals and some added unnecessary complexity so we were better off writing our own script language.

To reduce string parsing, our GumboScript is read once and stored in C# classes like the rest of our code. There is also a fixed small bank of memory with a few registers for a few data types which is allocated once in a block. These data types are also restricted to a basic set which avoids discrepancies. We also wanted to avoid script bindings, or connections, as much as possible. Finally, because we ship on multiple platforms, it was safer not to use external libraries or runtimes with limited memory access and file reads.
 

Core Objectives

Readable

Programmers have become accustomed to seeing brackets of all kinds [ , { , (, < and words like “void” or putting an “f” or “0x” next to a number. However, this is not very natural, and is an easy point of failure for a new user writing a line of code. In GumboScript, we use some basic nouns and verbs, some algebra, and a little shorthand to cover the rest of the math operations.  

In this case, a bitwise match is written as the word MATCH, and the list of attributes are separated with commas instead of a “bitwise or.” Nesting is done with whitespace. Verbs are always written before nouns, and adjectives and math operators combine to create formulas. We hope that it reads closer to an English sentence than to what some may call gobbledygook.

Our inspiration for a very approachable script comes from the modern scripts LUA and Python, but also from a 70KB game made in 1990, “Warbots” by Chris Busch. The objective of Warbots is to script a combat robot using a basic knowledge of logic, minimal formatting, and simple commands like move, shoot and scan.

Comparison between Warbots' pascal and Shadowrun's GumboScript.  Warbots:  
https://archive.org/details/Warbots
 

Failable

Sometimes failure is intended, and sometimes it is unexpected. In all cases, the AI agent should respond gracefully. In GumboScript, every action can pass, fail or become busy.  Using the debug tools, we can see where the flow failed on an action, and the designer can choose to write fallback behavior at that point if desired. For example, if a gun fails to fire, it may fall back to a reload action or switch to a punch attack.

Perpetual

When an AI agent starts thinking, it should remember information about its own actions and scans, and sometimes its allies’ information as well. We populate the AI agents’ memory with a few common entries like the latest attacker or longest ranged weapon. Additionally, designers can define their own variables to be stored. One script may keep track of their most useful item or a specific enemy who flanked them. Later in the game, they can use these to factor in the decisions. This is not a new concept to AI, but it was an important addition to our script and allowed the designer to decide which things are remembered.

Event driven

For real-time AI, there are many different events that can cause an AI agent to rethink their actions. Turn-based AI can be limited to the turn start being the sole event, but we wanted some more control and timely reactions. Currently we can have the script respond to a handful of events including a friend being attacked, or a stranger walking into sight range. The designer can then start a sequence of events to fit their design instead of waiting until the next turn.  

Restrictive

While we wanted the most flexible system possible, we also wanted speed and safety. This is why some operations are not possible in script. Currently, our methods have a default loop maximum of three loops. The distance and visibility to all threats is evaluated internally only when the positions have changed. External scans to the world and internal scans to one's own abilities or attributes are cached at turn start and only re-evaluated when necessary. This allows the AI script to use complicated combinations of selections or evaluations multiple times without having to redo potentially slow work.
 

With these concepts established and the code in place, we set about designing profiles for our various enemy types. We established that our primary design goal for the AI was that it “not look dumb”. Although that may sound glib, it’s a pretty practical way to look at AI; more than anything, what’s important is how the AI appears to the player.

Below is the diagram we made to start creating the main combat loop (method) for our most common type of AI agent, the Soldier.

The loop evaluates on the start of every AP (Action Point, the currency used to take actions) spend. The reason for this is that AP is variable. Typical enemies start with two AP, but any number of things could be happening on the battlefield to deduct AP. Thus, there is no guarantee that the AI will still have AP to spend during evaluation.

We expanded on this model as we progressed, but the central principles of the combat loop remained until DF-DC shipped.

Reactive overrides (red) happen when the AI needs to react but it is not their turn - such as "Hit in the Open" as shown in the diagram

Special conditions (yellow) are secondary priorities. They aren’t matters of life and death, but they’re still pretty important. These fire one after the other in a priority sequence. This allows the AI do things that are really important, but not at the expense of risking lives. Having a degree of self-preservation was key to our goal of AI was to “not look dumb”.

In the standard combat part of the loop (light blue), you will notice that cover is very important. This was high on our list of ways to make the AI agent appear “not dumb.” Standing in the open while a team of feisty Shadowrunners have various forms of hurt (both technological and arcane) pointed your way certainly qualifies as dumb.

We took advantage of the human tendency to see and infer a meaningful pattern where there isn’t one. In the diagram, CTD stands for “Chance To Do,” and the decimal value is converted to a percent chance. In the diagram, the AI has 50-50 chance of either seeking cover and attacking, or looking for a flanking shot. For our Mage AI agent we used CTD in even more places, and we were happy with the result. For example, most of the time Mage AI will wait for enemies to be grouped to fire their AoE, but every now and then they will fire on a single target just to keep it interesting.

The overrides, special cases in priority order, and somewhat random primary combat loops together create the impression of intelligence that appears to be doing sensible things.
 

Objectives vs. Execution

The goal when creating the profiles was to make a systemic type of logic that would “not look dumb” in all situations, but this was not how things worked out in practice. We found a major issue in the form of the AI taking cover twice and not taking an action. There were various flavors of this, from the "sort-of-odd-looking" to the "really silly looking." For example, the AI agent might

In the spirit of both speed and safety, a brute force approach was taken in the script. Once cover is entered, it’s more-or-less guaranteed that AI agents will either take an action or end their turns. Whenever the script could be at a point where the AI wanted to take cover, it either did so, took an action, or ended its turn. The reason we did this at every possible branch, rather than handling it systemically, was due to the number of behavior permutations that could occur.

Now that we know where the landmines are, a more systemic approach to the cover behavior would be possible, but as our shipping date approached, we chose to play it safe with a limited design.  It’s plenty exciting to bolt things onto a moving train, but it’s a little bit too thrilling to change how the engine works while its running at full speed.

Fortunately, our cover issue was our only significant speed bump. Giving the designers the ability to iterate on AI behavior by themselves allowed for updates to be made on an order of magnitude faster than our previous system. If changes needed to be made in GumboScript, it could usually be done quickly, which allowed the design team more time to correct and construct new behaviors. The end result was a higher-quality AI experience with less engineering time. Even on the tight timeline of DF-DC, investing in tools paid off.

The Future with GumboScript

GumboScript for DF-DC is only the beginning; a first version designed to support basic turn- based actions. We hope to advance the system features by focusing on utility, adding more prediction, goal-based decisions, and the ability to learn from past results. We hope that these systems can work in both turn-based and real-time environments for more responsive AI in all future Harebrained Schemes games.

For more information on games that do implement a goal-based system, we suggest Jeff Orkin’s work in Goal Oriented Action Planning, which is a practical application of some advanced AI concepts implemented in the first person game F.E.A.R. (among others).
http://alumni.media.mit.edu/~jorkin/goap.html

To try out Gumbo script for yourself, you can create custom content in our online UGC workshop for Shadowrun: Dragonfall - Director’s Cut. You can see our community page on steam http://steamcommunity.com/app/300550. Internally we have used Sublime Text as the editor with our own syntax coloring.  Further documentation and the sublime text package file are available on our wiki http://shadowrun-returns.wikispaces.com/GumboScript. 
 

See you in the Shadows.