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.