Welcome to the blog of

Josh Deprez

⬅️ Previous post Permalink link

Published 23 October 2021

Making a Game in Go, part 7

And now, something completely different. A dialogue system!

Please don’t tell me you are going to implement your own dialogue system too! Aren’t you friends with the Yarn Spinner people?

Exactly. Why reimplement something that already exists and does a good job?

Ok, so… Yarn Spinner. A dialogue system for games, “the friendly tool for writing game dialogue”. Why put dialogue in a game? I dunno, but narrative seems to be an element of many popular games, and I would like to have some in mine too.

Yarn Spinner is not written in Go, which would make it easy to interoperate with directly, nor is it written in C/C++, which would be slightly awkward yet feasible (via CGo).

Yarn Spinner is written in C#. This makes sense because Yarn Spinner is (so far) intended to run as a Unity package, and Unity uses C#.

I wonder what the state of .NET-Go interop is? Some things I found:

  • go-dotnet - “PoC” (proof of concept)
  • go-clr - another PoC, “definitely not production ready”
  • Embeddinator-4000 - no Go output? seems like overkill anyway?

Wait, that’s it?

Reimplementing, like, half of Yarn Spinner

tl;dr: the code’s up on GitHub.

Yarn Spinner consists of a few high-level parts:

  • The Yarn Spinner language itself - concretely this can be thought of as the combination of a lexer grammar and a parser grammar that can be converted into whatever other language is needed (that ANTLR supports).
  • The Yarn Spinner compiler (containing the generated parser in C# from above). Given a .yarn file, the compiler produces a protobuf containing the compiled program, and a string table in CSV format containing all the lines of dialogue.
  • The dialogue runner. Given the output from the compiler, the dialogue runner runs the program and delivers the dialogue to the game.

High level diagram showing key Yarn Spinner components

Since the dialogue runner is the closest part to the game, and the language grammar and compiler can be used stand-alone (they don’t have to be shipped with the game), if I have to reimplement anything it would be the dialogue runner.

Tailwinds for writing a reimplementation of the Yarn Spinner VM in Go:

  • IRL access to key members of the Yarn Spinner team if I have any questions. 😄
  • Yarn Spinner is open source with a permissive license (MIT). Not only can I read the original implementation to understand how it works, my implementation is free to outright copy pieces of it or be a derivative work without worry (provided the license conditions are satisfied).
  • The bytecode is a protobuf format. Generating proto stubs in Go is about as easy as any other language supported by protocol buffers. This takes care of program decoding.
  • The number of opcodes (17) is small, especially compared with ISAs of non- virtual CPUs like x86. Between the opcodes, the variations on opcodes, and the standard library of functions, there is not a burdensome amount of work.
  • The string table format is CSV. The encoding/csv standard library package can do the heavy lifting there.
  • Implementing the Yarn Spinner format functions (these appear in the string table), particularly plural and ordinal, might not be straightforward, but there are probably a few Go packages floating around that provide the Unicode CLDR data, such as golang.org/x/text.

Oh, also I began implementing it in like 2016 (but had other things to do than complete it).

The virtual machine

The Yarn Spinner virtual machine is the core of the dialogue system at game run time. Its primary responsibilities are:

  • Run the compiled Yarn Spinner program.
  • Tell the game to show a line (of dialogue). The program itself doesn’t know the contents of a line, merely the ID of the line in the string table and the values of any text substitutions.
  • Tell the game to show a set of options (themselves lines in the string table).
  • Accept the player’s choice of option (an integer).
  • Tell the game to run game-defined commands (strings).
  • Notify the game of any other possibly interesting events, like the beginning and end of nodes, that certain lines might be delivered soon so that the game can load associated assets in the background, or the end of the dialogue.

This suggests an interface for the game to implement that the VM can talk to. Yarn Spinner’s dialogue runner needs a similar sort of interface. The idiom in Yarn Spinner’s C# implementation is to use various separate properties of delegate type as callbacks for each event. While it would be simple in Go to either have 7 different interfaces with 1 method each, or have 7 fields of func type, neither approach makes a ton of sense. Responsibility for handling game dialogue is likely to be concentrated in one location, so making that thing handle all the different events produced by the virtual machine, whether or not they are needed by the game, is reasonable. For implementations that ignore most of the methods, there’s also a FakeDialogueHandler that can be embedded to provide no-op implementations.

1
2
3
4
5
6
7
8
9
type DialogueHandler interface {
    Line(line Line) error
    Options(options []Option) (int, error)
    Command(command string) error
    PrepareForLines(lineIDs []string) error
    NodeStart(nodeName string) error
    NodeComplete(nodeName string) error
    DialogueComplete() error
}

Imitating the original Yarn Spinner API is desirable for two reasons:

  • Providing a similar API leverages the design work that has gone into the existing API.
  • Providing a similar API makes using it easier for anyone who has used the original.

But there are a few deliberate API differences that I want to touch on.

Yarn Spinner’s implementation pauses execution after delivering lines, options, and commands. When the game is ready for more content from the dialogue system, it must call Continue to make the VM continue executing. This makes a lot of sense when you consider that a game only rarely needs more content from the dialogue system. Most of the time is spent waiting for player inputs, or otherwise allowing the player to enjoy the content. So suspending execution and requiring an explicit Continue allows the dialogue system to get out of the way.

Sequence diagram showing non-blocking Yarn Spinner dialogue runner operation

However, it is unnecessary to do this in Go - there is a more *Go*thic way. The VM can run concurrently in a separate goroutine, and deliver the content as fast as it likes. When the game needs to spend more time between bits of content, it can block.

Blocking the VM goroutine (with, say, a channel operation or a mutex lock) isn’t as expensive as it sounds (it doesn’t “waste a thread”). In fact concurrency is very useful even where operations don’t need to happen in parallel. The goroutine scheduler is aware of channel operations and mutexes and so on, and while a goroutine is waiting on these, the scheduler won’t schedule that goroutine. When the game is ready to receive more dialogue, it can unblock its handling of the current Line, Options, Command (etc), and return.

“Sequence diagram”-esque diagram showing blocking concurrent operation

Aside from simplifying away execution state tracking and the Continue method, doing it this way enables Options to return the chosen option directly, rather than requiring another VM method for telling the VM about it (SetSelectedOption). The API is clearer.

Because goroutines and channels are so useful for adapting between blocking and non-blocking needs in this way, well-designed Go APIs usually block. If non-blocking is needed, the caller can wrap the API call in a goroutine, with results passed later on via a channels entirely managed by the user of the API. Blocking APIs tend to be easier to understand than either non-blocking APIs or APIs that try to do both by taking channel arguments or returns.

Another key difference between my implementation and the Yarn Spinner API is a Go practical necessity: C# has the concept of exceptions, but the Go way is to return errors like any other value. So each method in the DialogueHandler returns error, and the VM checks the error value before continuing, providing the dialogue handler the opportunity to halt the VM in much the same way as raising an unhandled exception in C# land.

The virtual machine implementation is also inspired by Yarn Spinner’s. Having the source code and a suite of ready-made test cases has been a massive time-saver when trying to debug or understand differences in behaviour. Given that virtual machine is essentially a loop that considers program instructions one at a time, many similarities between implementations will happen naturally.

Choosing what to do based on the current instruction sounds a lot like a switch statement (and that is how Yarn Spinner does it) but for the sake of reducing code indentation (and “cyclomatic complexity”) I ended up with a slightly different device:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
var dispatchTable = []func(*VirtualMachine, []*yarnpb.Operand) error{
    yarnpb.Instruction_JUMP_TO:        (*VirtualMachine).execJumpTo,
    yarnpb.Instruction_JUMP:           (*VirtualMachine).execJump,
    yarnpb.Instruction_RUN_LINE:       (*VirtualMachine).execRunLine,
    yarnpb.Instruction_RUN_COMMAND:    (*VirtualMachine).execRunCommand,
    yarnpb.Instruction_ADD_OPTION:     (*VirtualMachine).execAddOption,
    yarnpb.Instruction_SHOW_OPTIONS:   (*VirtualMachine).execShowOptions,
    yarnpb.Instruction_PUSH_STRING:    (*VirtualMachine).execPushString,
    yarnpb.Instruction_PUSH_FLOAT:     (*VirtualMachine).execPushFloat,
    yarnpb.Instruction_PUSH_BOOL:      (*VirtualMachine).execPushBool,
    yarnpb.Instruction_PUSH_NULL:      (*VirtualMachine).execPushNull,
    yarnpb.Instruction_JUMP_IF_FALSE:  (*VirtualMachine).execJumpIfFalse,
    yarnpb.Instruction_POP:            (*VirtualMachine).execPop,
    yarnpb.Instruction_CALL_FUNC:      (*VirtualMachine).execCallFunc,
    yarnpb.Instruction_PUSH_VARIABLE:  (*VirtualMachine).execPushVariable,
    yarnpb.Instruction_STORE_VARIABLE: (*VirtualMachine).execStoreVariable,
    yarnpb.Instruction_STOP:           (*VirtualMachine).execStop,
    yarnpb.Instruction_RUN_NODE:       (*VirtualMachine).execRunNode,
}

func (vm *VirtualMachine) execute(inst *yarnpb.Instruction) error {
    if inst.Opcode < 0 || int(inst.Opcode) >= len(dispatchTable) {
        return fmt.Errorf("invalid opcode %v", inst.Opcode)
    }
    exec := dispatchTable[inst.Opcode]
    if exec == nil {
        return fmt.Errorf("invalid opcode %v", inst.Opcode)
    }
    return exec(vm, inst.Operands)
}

This demonstrates two things.

First, array and slice literals in Go can be written similarly to map and struct literals (with keyed elements), so long as the “keys” are integer indexes (and protobuf enums are int32 values in Go). What happens if you leave a gap (or start after index 0)? Any uninitialised elements between 0 and the maximum index key take the zero value for the type. In the case of Yarn Spinner, there are no unused instructions between JUMP_TO and RUN_NODE, so the nil check is strictly unnecessary.

Each instruction is implemented as its own method, with a common signature:

1
func (vm *VirtualMachine) execSomething(operands []*yarnpb.Operand) error

Given any method, there are two short ways to get a func value that calls the method, using method expressions. Of course one could write a closure that calls the method, but method expressions are shorter and make a lot of sense when you see them at work.

The more common method expression style is to write a method call but without the parentheses or arguments:

1
2
var vm *VirtualMachine
vm.execSomething   // is a func([]*yarnpb.Operand) error

The less common, but still very useful syntax, is to use the type itself instead of a value.

1
2
(*VirtualMachine).execSomething
// is a func(*VirtualMachine, []*yarnpb.Operand) error

Since the *VirtualMachine isn’t known when taking the method expression, the func has to take a value of that type as an arg.

Why use the second kind of method expression here, when the first has fewer args and the value of vm is known? e.g. why not something like

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
func (vm *VirtualMachine) execute(inst *yarnpb.Instruction) error {
    dispatchTable := []func([]*yarnpb.Operand) error {
        yarnpb.Instruction_JUMP_TO:  vm.execJumpTo,
        yarnpb.Instruction_JUMP:     vm.execJump,
        // ... snip ...
        yarnpb.Instruction_RUN_NODE: vm.execRunNode,
    }
    // ...snip...
    exec := dispatchTable[inst.Opcode]
    // ...snip...
    return exec(inst.Operands)
}

Well, unless the compiler is clever, it is likely dispatchTable would be recreated on every execute call (i.e. every VM instruction), which seems wasteful.

The standard functions

One VM opcode stands out from the others - CALL_FUNC. It is noteworthy because all arithmetic operations, Boolean expressions, numeric comparisons, and string concatenation in Yarn Spinner programs happens using CALL_FUNC, rather than with dedicated instructions for those purposes.

As an example, the expression 2+3 is compiled into:

1
2
3
4
5
PUSH_FLOAT 2     ; first argument
PUSH_FLOAT 3     ; second argument
PUSH_FLOAT 2     ; number of args being passed
CALL_FUNC "Add"  ; invoke the function
; top of stack now contains the result (5)

Yarn Spinner defines 17 standard functions that implement the basic operations. (Making the functions into their own opcodes would double the opcode count!) Some functions are shared across different types, for example, the Boolean expression functions (Or, And, Xor, Not) clearly work with Boolean args, but also floats (0 is false) and strings (empty is false, non-empty is true). Add is shared between floats (arithmetic addition) and strings (concatenation). This is required because (as of this writing) the Yarn Spinner compiler makes “truthiness” and other implicit type conversions the responsibility of the functions, rather than inserting comparisons or explicit conversions.

CALL_FUNC isn’t limited to the standard Yarn Spinner functions, either. Custom functions, with any number of arguments of any type, including variadic functions, can be registered to be called. This flexibility makes the implementation of CALL_FUNC the most complicated instruction. Supporting variadic functions implies that the program has to communicate how many values on the stack are function args - this is why the arg count is always pushed before CALL_FUNC. Yarn Spinner could adopt two different calling conventions to avoid the unnecessary push for non-variadic functions, but that shuffles the responsibility back from the runtime to the compiler.

Both C# and Go have reflection. In Go reflection is done via the reflect package, which I mentioned in the previous post. reflect.Type has a number of methods relevant to interrogating the args of a function. After checking that the custom function’s Kind is indeed reflect.Func, the reflect.Type supports NumIn, NumOut, and IsVariadic methods to find how many args the function has, and In and Out methods to inspect the type of each.

The logic of matching the types of items on the VM stack with args of each function is a bit tedious, especially to support both non-variadic functions (where the number of args must match exactly) and variadic functions (where the last In arg is the implicit slice type, and the number of args provided by the program can be one fewer than NumIn!).

The cool part is actually calling a function via reflection. After wrapping all the input args with reflect.Value (no special logic is needed for variadic functions - that is taken care of by reflect!) the call can be made on a reflect.Value wrapping the function:

1
2
3
4
5
6
7
// Params built from stack values
params := []reflect.Value{ ... }

// function is the function we wish to call
result := reflect.ValueOf(function).Call(params)
// result is now another []reflect.Value with
// the return values.

The string table

Reading a CSV file with encoding/csv and then putting all the rows into a map keyed by line ID isn’t particularly thrilling code. What is a bit more interesting is what happens with lines when they need to be presented, because Yarn Spinner lines can be more complex than plain strings.

Firstly, there are string substitutions. A substitution happens in lines, options, and commands, when the author writes an inline expression. For example, the line Hello, {$name}! would be compiled into two parts: bytecode to load the value of $name to be used as a substitution, and a corresponding line in the string table of the form Hello, {0}!. When the VM runs a line, it not only passes the ID of the string in the table, but also all the values that need to replace curly-braced numbers.

Yarn Spinner, and an earlier version of my Go package, implement substitutions with repeated string replacement:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
type Line struct {
    ID string
    Substitutions []string
}

func (t *StringTable) Render(line Line) (string, error) {
    row, found := t.table[line.ID]
    if !found {
        return "", fmt.Errorf("line ID %q not in string table", line.ID)
    }
    text := row.Text
    for i, subst := range line.Substitutions {
        token := "{" + strconv.Itoa(i) + "}"
        // alternatively token := fmt.Sprintf("{%d}", i)
        text = strings.ReplaceAll(text, token, subst)
    }
    return text, nil
}

This hardly needs to be optimised, because dialogue content only needs to be delivered as fast as the player can consume it - string replacements won’t be the bottleneck in that process. But, just for fun, here’s how the substitutions could be processed in a single pass over the line text using a strings.Builder for minimising allocations:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
func (t *StringTable) Render(line Line) (string, error) {
    row, found := t.table[line.ID]
    if !found {
        return "", fmt.Errorf("line ID %q not in string table", line.ID)
    }
    text := row.Text
    
    var sb strings.Builder
    token := false
    tokenStart := 0

    for i, r := range text {
        switch {
        case !token && r == '{':
            // Entering token mode -
            // record the start position of the token
            token = true
            tokenStart = i
        case token && r == '}':
            // Exiting token mode -
            // token should have a substitution index n
            n, err := strconv.Atoi(text[tokenStart+1:i])
            if err != nil || n < 0 || n >= len(line.Substitutions) {
                // Either the token was malformed
                // or the index requested wasn't
                // provided by the program.
                // Oh well, output the token-like thing
                sb.WriteString(text[tokenStart:i+1])
                continue
            }
            token = false
            // write the substitution
            sb.WriteString(line.Substitutions[n])
        case token:
            // not a closing brace, hopefully a digit - skip
        default:
            // not-token mode
            sb.WriteRune(r)
        }
    }
    if token {
        // ended in token mode
        // output the partial token
        sb.WriteString(text[tokenStart:])
    }
    return sb.String(), nil
}

The other language feature that is the responsibility of the dialogue runner is format functions. The idea with format functions is to defer some expressions that produce text, where the text would vary both by game state and potentially by language. Different string tables for different languages can be translated in a way that produces more natural dialogue across languages.

Format functions are written with square brackets [, ] and have a more sophisticated syntax than substitutions. Thankfully there are only 3 supported format functions: select, plural, and ordinal (and the latter two are fairly similar). Examples:

1
2
3
Hey [select "{0}" m="bro" f="sis" nb="doc"]
That'll be [plural "{0}" one="% dollar" other="% dollars"]
You are currently [ordinal "{0}" one="%st" two="%nd" few="%rd" other="%th"] in the queue

Note these examples have one main difference with the syntax described in the Yarn Spinner docs. Yarn Spinner compiles the inline expressions used as input to the function into a substitution token. The examples above would be what appears in the compiled string table.

Format functions would be, uh, challenging to implement with a repeated-replacement algorithm. While {0}, {69}, {420}, ... tokens can be easily search’n’replaced for each substitution provided by the program, there are no limits on what strings each format function could contain, nor how many key/value pairs appear after the selector input.

At this writing the Yarn Spinner develop branch implements format functions with a big loop. I wanted to try something a bit different - between substitutions, format functions, and the necessary escape sequences, there’s practically a whole (small) language, and across my career I have barely dipped my toes into the waters of lexers and parsers.

After some quick looking around for text parsing packages for Go, I settled on participle, because it looks nice and one of the examples shown in the README looks kind of like what format functions need (if you squint a bit): let a = "hello ${name + ", ${last + "!"}"}" can be lexed with participle’s stateful lexer. Yarn Spinner format functions similarly require nested evaluation - the tokens % and {0} are substituted into strings, which are inside format functions (which are inside lines of text, which are kind of like strings).

The lexer and parser details are in strings.go, and while it does not match what Yarn Spinner does exactly… the tests pass 🤷

One final word on participle: using participle to parse a grammar that uses double-quoted strings, together with a Go linter that complains that participle’s easy struct tags violate the convention for field tags, led to a few escaping dramas, particularly parser:"\"\\\"\" @@ \"\\\"\"" 🤪

For the pluarl and ordinal format functions, Yarn Spinner uses the wonderful Unicode CLDR to pick the value. Having spotted the golang.org/x/text package, in particular feature/plural, I figured it would be easier than generating the information from LDML myself. And it was! It just has two minor problems.

That’s more of a bridge I can pester someone to build when I need to cross it. In the meantime, maybe someone has something better? A search for “cldr” among Go packages reveals a variety of other efforts to load and make useful the CLDR. I tried using razor-1’s localizer package, but despite cardinal data working fine, ordinal data wasn’t present, leading to a nil pointer panic. Or maybe I was holding it wrong. Still, the NewOperands function was useful for figuring out what to pass to golang.org/x/text’s MatchPlural:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
import (
    //...snip...
	cldr "github.com/razor-1/localizer-cldr"
	"golang.org/x/text/feature/plural"
)

//...snip...

case "plural":
    ops, _ := cldr.NewOperands(in)
    form := plural.Cardinal.MatchPlural(lang, int(ops.I), 
        int(ops.V), int(ops.W), int(ops.F), int(ops.T))
    //...snip...

case "ordinal":
    ops, _ := cldr.NewOperands(in)
    form := plural.Ordinal.MatchPlural(lang, int(ops.I),
        int(ops.V), int(ops.W), int(ops.F), int(ops.T))
    //...snip...