Dialog Trees: Basic Design and Implementation

The basic mechanics of dialog trees amounts to describing a directed graph, with some bells and whistles. Specifically, the edges are possible player responses, the nodes are NPC statements, and we have them both be subjects of observers (so selecting the line "I accept this quest" in dialog will trigger the start of that quest). Arguably, dialog nodes and edges are also observers (different dialog options reflecting the player's progress through the story).

The basic structure of a directed graph, with some bells and whistles attached, occurs frequently in RPGs (though seldom in Rogue-likes). I'll be using vague names like "edge" and "node" (instead of "response" and "dialog-node").

Software Design

I'm not going to discuss, "How to write narrative dialog for your RPG". This is a very important topic, one I don't think I am skilled at, but it assumes we have a data structure for storing dialog. We first must introduce the data structures and algorithms for software to work with dialog, then some additional code to facilitate authoring dialog more easily.

The design varies depending on granularity. The basic elements require two classes, a node class which has the NPC's line and the player responses; and the edge class, which represents one possible player response to an NPC line.

(defclass edge ()
  ((text :initarg :text
         :type string)
   (next-node-id :initarg :next-node-id)))

(defclass node ()
  ((id :initarg :id)
   (npc-line :initarg :npc-line
             :type string)
   (speaker :initarg :speaker)
   (responses :initarg :responses)))

Arguably we could give an ID to each edge, but the schematic design should be clear.

We could go further, and introduce a subject class, a notify method for the subject, and have edge inherit the subject class. This design choice depends on whether the subject's notify method requires additional parameters (e.g., an event keyword or whatever).

Contingent Responses

We also need to consider the situation where some player responses are only displayed when events occur, or a skill check is passed. If we use Common Lisp, for example, we can consider something along the lines of:

(defclass edge ()
  ((show? :initarg :show?
          :initform t ;; default to true
          :type (or boolean (function (edge) *))
          :documentation "Either a check to show if this edge should be shown, or its result.")
   ;; other slots ("fields") as before, not shown
   ))
         
(defun edge/show? (edge)
  (declare (type edge edge))
  (let ((edge-show? (slot-value edge 'show?)))
    (if (typep edge-show? 'boolean)
      edge-show?
      (funcall edge-show? edge))))

This permits handling one-time checks by the second-order function along the lines of:

(defun one-time-check (check-callback)
  (declare (type (function (edge) *) check-callback))
  (lambda (edge)
    (declare (type edge edge))
    (let ((result (funcall check-callback edge)))
      ;; coerce the result to a boolean value
      (setf (slot-value edge 'show?) (if result t nil)))))

;; ostensibly used as (one-time-check (skill-check :strength :at-least 10))

The only requirement I would recommend: during a dialog, the show? should evaluate to the same value. So a skill-check that happens each dialog should store that check's result until dialog ends. Alternatively, it should only update the show? value upon success, and keep its function/callback version for future checks.

Hack: Scripts

We can take advantage of this to invoke a script when a response is selected. This amounts to making the observer notified (of the response selected) trigger the desired code instead. Common Lisp simplifies the observer pattern to a function call-back, the subject pattern is a class with a slot observers for a list of functions.

(defclass subject ()
  ((observers :initarg :observers
              :initform nil
              :type list)))

(defgeneric notify (self event-keyword &key &allow-other-keys))

(defmethod notify ((self subject) event-keyword &key &allow-other-keys)
  (loop for observer in (slot-value self 'observers)
        do (funcall observer self event-keyword)))

(defgeneric add-observer (self observer))

(defmethod add-observer ((self subject) observer)
  (setf (slot-value self 'observers)
        (cons observer (slot-value self 'observers))))

;; trigger a script by something along the lines of
;; (add-observer edge
;;               (lambda (self event)
;;                 (declare (ignore self event))
;;                 (script)))

(Note to Lispers: maybe the type of the observers slot should be (vector * (function (subject keyword &key &allow-other-keys) *)), or else the notify loop may require an additional line when observer to avoid null observers. But the intuition is to have a collection of callbacks, which we invoke with notify.)

Related Work

We haven't factored in the speakers yet, which could be done by proxy (using an entity component system). Instead of inserting the NPC's data structure directly, use the unique ID for that NPC. We store in a separate hash-table the NPCs (using their IDs as keys).

Also Emily Short's amazing work on conversation and Beyond Branching: Quality-Based, Salience-Based, and Waypoint Narrative Structures. More generally, the art of writing the actual dialog text itself has been discussed since Aristotle's Poetics.

Last, the authoring tools have not been discussed. We could look at interactive fiction for inspiration (e.g., Ink). The idea we should fix in our mind: create a DSL for authoring dialog, so it's more along the lines of markup instead of coding. For example:

(with-speaker doc-harris
  (node "Hello, how can I help you?"
    ;; a response is either a list (string optional-next-id &key observers ...)
    ;;               or terminal, i.e., just a string or lacks a next-id
    :responses (("Tell me about this town" :dialog.doc-harris/town-guide)
                "Nothing today, thank you")) ; terminal response
  
  ;; a "node" which circles back until terminated
  (circuit-node "Anything else you want to know?"
                :id :dialog.doc-harris/town-guide ; unless an :id is given, autogenerates a unique ID for dialog nodes
                :initial-npc-line "Sure, what do you want to know?"
                :responses (("Is there a place to rest?" "Sure, there's an inn down the street")
                            ("Where can I get supplies?" "There's a blacksmith on the East side of town, and a trader next to the inn.")
                            ("Where can I get patched up?" "Right here! Doc Harris, medical practitioner, at your service!")
                            "Eh, I think I'm good now. Thanks and good bye!")) ; terminal response

  ;; trigger a quest if accepted through dialog
  (node "You're here! I need your help! My daughter's been kidnapped!"
    :show? ...
    :responses ("Uh, sorry, we're *really* *busy* at the moment..."
                ("Of course! Who apprehended her?" :start-quest :doc-harris.quest/kidnapped-daughter)
                ("We need to know some more questions first..." :dialog.doc-harris/urgent-quest-circuit)))
  ;; etc.
  )

If combined with an entity component system, we can write some code to check the edges point to existing nodes, the speaker is a valid NPC, the quests started (and finished) through dialog all exist. I'm in the middle of writing a proof-of-concept of this validation toolkit, and will probably talk about it soon-ish.

Design Patterns and Architecture Patterns in Rogue-likes

Since the '90s, "patterns" have been stolen borrowed from Christopher Alexander's work on architecture. Alexander was curious about designing rooms, buildings, even entire cities, using a sort of "language" which addresses recurring problems like "What do we do with people waiting around?" In a house, this would be a drawing room; for a city, with a transit system, this would be benches (or whatever). Programmers realized they analogously face recurring problems which are solved with "very similar" solutions, and introduced design patterns to the world of software engineering.

For RPGs, we similarly divide it up into patterns: the players go on quests, which occur on levels, whose objectives are typically one of some half-dozen varieties ("fetch quests", "assemble parts for an artisan" quest, "kill quests", "defend quests", "follow quests", etc.). There are Non-Player Characters the user interacts with, Enemies to kill, etc. UC Santa Cruz has done some work on RPG patterns in this vein.

The goals of using patterns in programming include: speeding up development, decreasing the number of bugs, increasing stability, making it easier to extend the program's capabilities, aid testing, and so on.

Munificent Bob wrote a wonderful book, Game Programming Patterns. Design patterns address recurring problems which regularly crop up, and were the "hot new thing" in the '90s. What's an example of this in games? A recurring pattern in, e.g., Steam games are achievements, which are precisely the observer pattern.

Since design patterns have been well discussed by Munificent Bob, I'll focus on the less discussed architecture patterns for Rogue-likes. Specifically, MVC and its variations.

Architecture Patterns

"Architecture patterns" refers to particular ways to structure the code to cleanly separate concerns. For most rogue-likes, this is some variant of MVC: the rules to the game is coded up in the models, the UI rendering is handled by the views, and the translation of user input to game commands is handled in the controller.

If we wanted to have a "poor man's" Fallout-type Rogue-like, where there's a separate dialog interface showing possible responses to the NPC's statement, another interface for traversing the "world map", and a third for traversing the "local region" map, then we can handle this cleanly with an MVC-architecture. One controller for handling user inputs for the dialog, another for traversing the world, and a third controller for the local world map.

We can organize the code to reflect this architecture:

/game/

/game/models/actor.c
/game/models/dialog.c
/game/models/item.c
/game/models/quest.c

/game/controllers/dialog_controller.c
/game/controllers/world_map_controller.c
/game/controllers/combat_controller.c

/game/views/dialog_view.c
/game/views/world_map_view.c
/game/views/combat_view.c

All the logic of dialog is handled in /game/models/dialog.c, which can trigger quests, complete quests, or otherwise update the game state to reflect the choices made. In an object-oriented language, the model is the subject of a view observer. Schematically, in C++, a model would look like:

// make this a template class (parametrized by Model)?
class Model {
public:
    Model() : observers_() { };
    ~Model();
    // business logic methods not shown
    // subject methods, for observer pattern
    void addObserver(const Observer &observer);
    void removeObserver(const Observer &observer);
    void notify() {
        for (Observer o : observers_) {
            o.update(*this);
        }
    }
private:
    std::vector observers_;
};

The only place where UI occurs should be swept into the views. Ostensibly we could create subdirectories for the different libraries use (e.g., /game/views/ncurses/ for the code handling NCurses-rendering, /game/views/sdl/ for the analogous code using the SDL library, etc.). If we were implementing the game in an object-oriented language, the view would be an observer of the model, and be notified when the game state has changed. Schematically, in C++, a view class would look like:

// make this a template class (parametrized by Model)?
class Model;
class Observer {
public:
    virtual ~Observer() { };
    virtual update(const Model &model) = 0;
};

class View : public virtual Observer {
public:
    View(...);
    ~View();
    void render();
    // observer pattern method
    void update(const Model &model);
    // action patterns to dispatch events to the controller
    void addMouseClickListener(const MouseClickListener &listener);
    // etc.
};

Controllers come in pairs with views. We attach the view to the model within controllers, and the action listeners are populated within the controller, too, for handling events (like mouse clicking or keyboard events, possibly inspired by DOM events). The generic controller resembles:

class Controller {
public:
    Controller(View *view, Model *model) {
        view_ = view;
        model_ = model;
        model->addObserver(view);
        // attach action listeners here, too
    };
    ~Controller();
    // high level user interactions
private:
    View* view_;
    Model* model_;
};

A variation of this architecture, for the Fallout-type game with several interfaces (dialog, world map, local map) may take a hierarchical MVC: intuitively, a "maestro controller" which delegates the game-loop to the dialog controller from the start of dialog until dialog ends, whereupon the game-loop returns to the maestro controller.

Such an architecture permits unit-testing the models, which lets us catch bugs in the boring mechanics (e.g., "marking a quest complete works as expected, right?"), and make it easier to swap out the UI.

Following the Lisp philosophy, we want to create a DSL within which we implement the game. The models describe this DSL. We can store the game data in a separate directory (say, /game/data/) encoded in JSON or YAML or S-expressions. If we wanted to make sure there are multiple ways to solve a quest (through dialog, sneak, or violence as three alternatives, for example), we could setup a small helper program or routine to check each quest has this property...thereby checking a sneaky player could win the game, as could a violent player or a dialog-focused player.

This also permits several people to work on the game. If the DSL is minimally specified and worked on by everyone, there could even be a team working on the game script independent of the game engine. A small Lisp script could check that the game script is playable, an emacs mode could be written to make development faster (a simple C-k C-q to develop a new quest, or whatever, with a skeleton newly inserted at the cursor).

Thus is the goal for such an architecture: to make it easy to develop the game, separating the fun parts from the boring reptitive parts so that the boring repetitive parts are implemented only once. The fun parts could be extended by a team, independent of the boring parts.

References and Concluding Remarks

The Model-View-Controller architecture has evolved over time into something idiosynchratic to each language. Java's MVC in Swing is slightly different than the original MVC in Smalltalk (and when Ruby-on-rails hit the scene, MVC changed into a core component of web development). Admittedly, I am drawing upon the Java tradition (see also MVC Structure, Examples of Model-View-Controller Pattern, Java SE Application Design With MVC).

Java has the Controller class track View objects and Model objects; whereas a vanilla approach would have the View create and track an instance of a corresponding Controller class, and both the Controller and View would observe a Model object. Doubtless there are many other variations of this theme, I won't pretend to be comprehensive reviewing them here. And, in my experience, it's easy to transform an MVC architecture into a Presentation-Abstraction-Controller architecture (again, this is fine, but I just want to emphasize that following a plan should not deter us from doing what works).

• Model-View-Controller. In Pattern-Oriented Software Architecture, Volume 1 (Peter Sommerlad, Michael Stal, Frank Buschmann, Hans Rohnert, Regine Meunier), Wiley, 1996, pp. 125 et seq.