Implementing Quests and Dialogs

I've been wanting to write up something about how quests and data work in Dawn -- a slice through the engine from top to bottom -- but I haven't had a good hook to do so yet.  I think, though, since I'm in the process of porting Dawn's dialogs over to Moai, its conversation system could provide a good example.

I'm motivated to write about quests because there seems to be little to none in the way of books, articles, and blog posts on the subject -- and yet quests -- or quest like systems -- are an essential component of many games. Finding a way to talk about them, and finding ways to compare and contrast solutions, would be valuable (and interesting!). Dawn's implementation is just one possible way. Other games I've worked on have done radically different things. Ultimately, I'd love to learn more about what others have done.

First, a quick update to provide context. I finally have the first piece of the dialog GUI working the way I want. It's not graphically pretty, but the point really for me is the underlying UI framework supporting it. It means it's possible to build (some small, pre-measured) nested ui components using an html/flex+css like syntax. For town menus, which can have variable numbers of elements, I'll need to finish measurement and sizing - but from there I'll have a good foundation for much more complex UI like combat and shops.

Mori, not to be confused with Moai.
They get angry about that.

From the game's perspective, all dialogs are launched from quests, so let's start at the top....

A Quest by any other name.

Quests are scripted in Python, but rather than interpreting Python at runtime ( the only complete version of Dawn is in Flash, so that's a no go ) the scripts (ultimately) generate binary data, and its the binary data which drives the quests. All data in game -- including conversations -- are actually represented this way.

This is the quest code for the second quest quest in the game ( the tutorial is painfully complicated; this one is short and to the point. )

from questcode import *
from quest_towns import *
import guests

def create( quest ):
  # look up the path defined by the route from the capital to glade
  path_to_glade= PATHS( capital_city, south_ford, glade )

  # add a pending quest at the capital, when you select it:
  # Hu tells you he wants you to find a person named Bataar, 
  # he shows you the route to glade: the last place bataar was. 
  main= quest.offer_quest_dialog( capital_city, "Hu needs your help" ).\
        reveal( path_to_glade )

  # half-way there, you'll encounter some combat
  # you'll also see a one off welcome message when you arrive at glade
  main.path_combat( south_ford, glade, percent=50 ).\
       use_path( path= PATH( south_ford, glade ), percent=100, chain=True ).\
       show_message( "arrival" ).\
       resume_movement()
  
  # you can click on the town to search for 'Bataar'.
  # he'll talk to you, which completes your quest, then he'll join your party.
  # you'll also get two new quests now that this one is done.
  main.use_town( glade, "Search for Bataar", chain=True ).\
       #
       # this action purely exists to show dialog,
       # the structures related to it are shown in the post below
       #
       show_dialog( "batty" ).\
       #
       # the last bits of this quest:
       #
       complete_quest().\
       give_guest( guests.bataar ).\
       run_quest( "c1_xfal" ).\
       run_quest( 'c1_bat2' )  

Rather than inventing a custom format for the binary data,  Dawn uses something called Protocol buffers: a structured binary data format developed by Google.

Optional Properties
The protocol buffer "has_property()" works similar to a tri-bool, and turns out to be really useful. 

Magic spells, for instance, have a field for "duration" controlling how many combat rounds they last.

"Has", therefore, can distinguish between instantaneous effects ( has duration=true, duration=0 ), and infinite effects ( has duration = false ).

Key values ( ex. -1 ) would work, but "has" code reads much better, and compresses well.

If you've been in games for a while, you've  probably seen a dozen comparable systems. So what's so nice about PBs? 1) it's well documented and liberally licensed, 2) there are a plethora of language bindings, and the Python, C++, and Java code are all maintained by Google, 3) it supports type reflection ( handy for tool work ), and -- perhaps uniquely -- 4) it supports optional properties.

Now, when I say *all* data in Dawn is represented this way, I really mean it. With the exception of images, sounds, and animations ( stored variously as pngs, jpgs, and swfs ), all player and monster archetypes, spells, quests, towns, you name it are protocol buffers. To keep things consistent, even text and conversations gets stored this way. 

Here's a look at the core protocol buffers ( Google calls the main data type a "message" ) used for quest dialogs:

// X data are quest actions
message XShowDialogs {
  repeated XShowDialog contents;
}
// This is the exact data structure 
// used by the quest snippet shown above
message XShowDialog { 
  optional int32 action;
  optional int32 display_set;
}
// a display set is a dialog
message DisplaySets {
  repeated DisplaySet contents;
}
message DisplaySet {
  // optional background image ( ex. cityscape, open field, etc. ) 
  optional int32 bkgrnd;
  // optional audio file to play during conversation
  optional int32 audio; 
  // optional title on the first dialog
  optional string title;
  // reference to first piece of text
  optional int32 starting_text;
}
message DisplayTexts {
  repeated DisplayText contents;
}
message DisplayText { 
  // each line can be said by a different person
  optional int32 dialog_npc;
  // the actual text displayed
  optional string text;
  // a link to the next line of dialog
  optional int32 next_text;
}

As you can see in the above, each of the root types  (XShowDialog, ShowDialog, DisplayText) are bound into an AOS ( array of structures ) -- for instance, an individual conversation is represented as a DisplaySet, and all the conversations in the game are kept in a single array called DisplaySets.

When the game starts, Dawn loads each AOS into memory. ( To help a bit with security, they are all bit twiddled and hmac'd in the process. But, for some unknown reason, I load each blob of structures separately, rather than having one top level SOAs. Next game, I guess. :} )

Even for as small as Dawn is, there are a total of 58 "root" data types, 20 which are devoted to quests(!).

Cross references. 

Protocol buffers don't natively provide a concept of cross-references between data types.  And you can spot the deficiency right off in the above sample.  All those references between data types are indices. The XShowDialog references the dialog it wants to display by a single "int32 display_set", the DisplaySet references its first line of dialog with an "int32 starting_text", the text references the person speaking with "int32 dialog_npc", and so on.

132 conversations, and more than 500 lines of dialog, journal entries, and quest descriptions does not the next Final Fantasy make but, that's more than enough potential bugs. ( Especially for one programmer, and one designer! ) Every index in every structure represents a place where a reference could go wrong.

What this means is that, for Dawn, protobuffers are not a complete solution. Instead, they are just the "language" the tools and the game share in common. The tools, on the other hand, all speak to each other via a separate, much safer structure: a sqlite database.

Sqlite.

In sqlite, we're not limited to indices, we can reference data however we want -- name of the speaker, or name of a conversation script, for instance -- and we can validate that data.

Since a picture saves a thousands words, here's sqlite playing the role of a central hub for all Dawn's data:

Beyond just validating the data, and storing human readable references, an additional benefit of using sqlite to store all Dawn's data is that multiple sources of data can coexist peacefully.  The heads.py file script scans the directory of speaker's headshot images, the speakers.xls spreadsheet holds a list of speaker names and notes about them, and so on.

The conversations themselves all live in doc files ( google docs actually, downloaded on demand: thanks Python! ), and using a word processing program means it's easy to verify everything's spelled corectly ( <- Humor, not irony. Really. )

Rather than duplicating the database and the protocol buffer definitions, there's actually even a little python script that walks the pb fields and generates the majority of the .proto message files automatically. ( Thanks again, Python! )

Quest Actions.

So, that's the bird's eye view of the data. How's a quest actually work? As I said there are 20 data types for quests. Each piece of data represents an action. Actions are chained together in a series of stages representing a particular quest.

[ Add a quest offer to a town ] ->
[ On accept: show dialog ] ->
[ Add a combat action to a path ] 

A Quest Action is an activity that either completes instantly, in which case we move immediately onto the next action, or an activity that takes some interminable amount of time. XShowDialog is an example of the latter. We trigger the display of the dialog, but we don't know how long it will take for the player to read the dialogs. Heck, maybe they want to go get lunch!

For the curious, here's a complete list of all the quest actions in Dawn:

• Accept/Decline: Offers a quest and branches to either: a chain of events for acceptance, or a chain of actions for decline. Decline usually just loops, pointing back to the Accept/Decline action.
• Change Chapter: Show's a congratulations on transition to a new section of the game.
• Change Items: Give or take items from the player.
• Check Items: Only moves on when the player has the specified items.
• Give Ability: Alter the player's record to enable a new spell or other ability.
• Give Guest: Alter the player's record to add a party member.
• Lock Town: Bar the player from moving to a given town, or the inverse: only allow them to move to given town. Record the lock into the player record.
• Reveal Path: Show a new path between towns, and sure the towns on either end are visible as well. Record the path into the player's list of known paths.
• Show Dialog: This is the core of this post, it's an action which spawns dialog. When the player finishes reading, then the action completes and the quest moves on to the next action.
• Show Log: Alter the player's record to give them a new journal entry.
• Spawn Combat: Send the player into combat.
• Use Path: Add a "path trigger" to the player's record. The triggers are evaluated as the player moves so that when the the player passes the specified location ( represented as a percentage b/t two towns ) a new chain of actions gets run.
• Use Town: Adds a "town trigger" to the player's record. The triggers are evaluated when the player clicks on a town, in order to add a menu option when they click on the specified town. Once the player selects the menu item, a new chain of actions gets run.

The two odd ball actions in all this are related to save. Neither action actually saves the game, but they are at the start and end of every chain of actions, and they are the only things that alter the player's list of active quests.

• Completed: only exists after combat or at the end of a quest. This usually gives the player some items or experience, and then -- once the player has accepted those -- removes all traces of the quest's actions from the player's record.
• Request Action: used by "use path" and "use town". Like completed, it alters the player's save data to remove the "use" action, and add a new chain of actions.

The behavior of "Completed" and "Request Action" ensures the player can never trigger the same chain twice. This means they can't receive multiple copies of the same item drop, nor can they have duplicate spawn combat events ( or use town menu items ) active at once.

All of Dawn's other actions were carefully chosen so that the entire dynamic state of the game can be referenced solely in terms of the player. This took lots of talking, and initially, a couple of wrong turns -- but it makes saving easy, and means that game can safely ( and automatically ) save any time the player reaches a town. ( And, really, whenever they come back to the world view at a town: for instance from a shop, or from a dialog. )

Each data type links to a specific code handler, this requires some (autogenerated) boilerplate code to create the right runtime class for each action type. The runtime class for spawn dialog looks like this:

class ShowDialog: public QuestAction
{
  typedef QuestAction parent_;
public:
  ShowDialog(ActionIndex)   
   : QuestAction(action)
   , _xshow( XShowDialog::Find( action ) )
  {
  }
protected:
  virtual bool action_started();  
  XShowDialog _xshow;
};

bool ShowDialog::action_started() 
{
  bool okay= false;
  if (_xshow && parent_::action_started()) {
    const DisplaySet ds= DisplaySet::FromDialog( _xshow );
    if (!ds->has_starting_text()) {
      LOG_INFO("skipping empty dialog %x", ds->display_crc() );
      action_completed();
    }
    else {
      // wait until dialog is done, 
      // then move to the next action in the chain
      complete_after_task( new OverlayDialog( ds ) );
    }
    okay= true;
  }    
  return okay;
}

Pretty simple at its core, just like most of the quest actions. They really only exist to spawn activities or run other kinds of shared code before moving to the next action in the chain.

The Moai connection

Now, you'll notice that the above code is written in C++. Before I settled on Moai, I had tried out both Cocos2d, and raw iOS dialogs. But, before I started working with any of them, the first thing I did was to port the code from Flash to C++. ( It's actually possible to play the entire game from the command line, but let me say: it's definitely not as fun! ) And, ideally, UI would just be "fluff"; somewhat in the spirit of the GoF decorator pattern.

I looked first at having C++ call specific lua code for each piece of UI -- as indicated by the new OverlayDialog() call in the sample -- but decided instead to use an event based system. The event queue then becomes the single shared connection point between the lua code and C++. The queue is accessible from Lua via a global, registered by the C++ code at startup.

Rather than "new OverlayDialog", as in the sample code above, instead the code queues an event. Each event sent to Lua is essentially just a name, and.... a protocol buffer.

core.game.queue_event( "ShowDialog", xshow.pb(), this, &oncomplete );

To handle the indeterminate duration of ShowDialog, the C++ code actually sends along a completion callback ( and user data for that callback ). Moai shows the dialog, the user clicks through everything, and when the complete dialog has been exhausted, the Lua code calls back to C++, and the dialog moves on.

One really nice thing about using named events is that, should I ever choose to port the state machine over to Lua, it'll fit perfectly with the Lua version of hsm-statechart.

All's well, that end's well.

Alrighty, I think that's a pretty good look at what's going on under the hood, and probably more than plenty to digest. If you have any questions just ask. If you have any links on how you, or others, manage quests: be sure to let me know!