Skip to content

NPC ~ Dialogue

Jump to bottom
sglenn-uchi edited this page May 31, 2022 · 21 revisions

Introduction

This document will outline how NPC dialogue, together with its various features, have been implemented. (See: dialogue.h, dialogue.c)

Content:

Basics

Directed Graphs

NPC dialogue is implemented using directed graphs. That is, a combination of nodes and edges:

Directed Graph

Starting from node A, a player can traverse to different nodes using "edges" (i.e. dialogue options), until they arrive at node F, where the conversation ends. In our implementation, this graph was achieved with the following structs:

typedef struct edge {
    char *quip;
    node_t *from, *to;
} edge_t;

typedef struct edge_list {
    edge_t *edge;
    struct edge_list *next, *prev;
} edge_list_t;

typedef struct node {
    char *node_id;
    char *npc_dialogue;
    edge_list_t *edges;
} node_t;

Note: the actual implementation contains a few more fields, to facilitate more complex dialogue functionalities, but the basic idea is the same.

Numeric Options

Ideally, we want to display dialogue to the player in the following manner:

Pick an item: a sword or a shield?
1. Sword
2. Shield

To achieve this, we need to implement some kind of "numeric labeling" for the dialogue options. This task is made more complex when, later, we introduce the concept of conditional dialogue. To be brief, here is an outline for how these numeric labels are generated:

  1. Upon reaching a new node, each dialogue option is checked for their "availability" (conditional dialogue).
  2. Once we know which dialogue options are available, we assign numeric labels to those dialogue options.
  3. These (numeric labels & dialogue options) are all stored in a string, when is sent to the CLI for printing. (See: create_return_string() in dialogue.c)

A Conversation

To store all the nodes and edges of a conversation, we have a convo struct:

typedef struct convo {
    int num_nodes;
    node_list_t *all_nodes;
    edge_list_t *all_edges;
    node_t *cur_node;
} convo_t;

Each NPC holds a convo struct, representing the conversation they have.

Building a Conversation

To build a conversation, use the following steps.

Step 1: Create the conversation

convo_t *c = convo_new()

Step 2: Build the nodes

add_node(c, "Node 1", "Pick an item: a sword or a shield?");
add_node(c, "Node 2a", "The path of offence. Good choice.");
add_node(c, "Node 2b", "The path of defence. Smart choice.");

Step 3: Build the edges

add_edge(c, "Sword", "Node 1", "Node 2a");
add_edge(c, "Shield", "Node 1", "Node 2b");

The convo struct can then be assigned to an NPC.

Running a Conversation

A conversation is run in the following manner:

  1. The player types talk to <NPC>. Behind the scenes, start_conversation() is called.
  2. A dialogue string (NPC's speech + dialogue options) is printed to the terminal.
  3. The player chooses his response. Behind the scenes, run_conversation_step() is called.
  4. We traverse to the selected node.
  5. Steps 2-4 are repeated, until the conversation is done.

As mentioned above, the relevant functions are:

char *start_conversation(convo_t *c, int *rc, game_t *game);

char *run_conversation_step(convo_t *c, int input, int *rc, game_t *game);

CLI Integration

To run dialogue from the CLI, we need a way to parse numbers, as opposed to words. To facilitate that, we use a mode functionality. (See: mode.h)

In short, when the player types the command talk to <NPC>, the game switches into "conversation mode." In conversation mode, we parse the user's input as numbers rather than words. We then call the associated dialogue function to carry out the conversation. Once the conversation is over, the game switches back to "normal mode."

Conditional Dialogue

To install conditional dialogue, we introduce a conditions field into the edge struct. condition_t is defined in condition.h. (See: condition.h)

typedef struct edge {
    char *quip;
    node_t *from, *to;
    condition_t *conditions;
} edge_t;

Using functions from condition.h, we can create item/attribute conditions, as well as test whether these conditions are met. If the conditions are met, then the edge is available.

Availability

Edge availability is reflected in edge linked lists:

typedef enum {
    EDGE_DISABLED = -1,
    EDGE_UNAVAILABLE,
    EDGE_AVAILABLE
} edge_avail_status;

typedef struct edge_list {
    edge_avail_status availability;
    edge_t *edge;
    struct edge_list *next, *prev;
} edge_list_t;

Availabilities are important when it comes to creating the dialogue strings. Note: EDGE_DISABLED is a special status that disables an edge permanently. This may be useful in the context of quests, for instance, where you may only want to be able to start a quest once.

Dialogue Actions

To install dialogue actions, we introduce a node_action struct:

typedef enum {
    GIVE_ITEM,
    TAKE_ITEM,
    START_QUEST,
    START_BATTLE
} node_action_type;

typedef struct node_action {
    node_action_type action;
    char *action_id;
    struct node_action *next, *prev;
} node_action_t;

Which we place in the node struct:

typedef struct node {
    char *node_id;
    char *npc_dialogue;
    int num_edges;
    int num_available_edges;
    edge_list_t *edges;
    node_action_t *actions;
} node_t;

Essentially, when the player arrives at a node, actions is checked. If it is not empty, then we execute each action. Note: Currently, only two actions are available: GIVE_ITEM and TAKE_ITEM.

Future Work

Integrate More Actions (2020-2022)

Once Quest and Battle have been fully integrated into the game, we should explore allowing players to start quests and battles through dialogue. This would make for a more interesting gameplay experience. Additionally, other, unique actions could be added such as recruiting NPCs as player companions or performing certain behavioral actions (e.g. hugging, laughing, frowning, etc.).

(2021-2022) Update: The functions that execute a variety of KINDs of actions are defined in the actionmanagement module. There is a function in NPC dialogue called do_node_actions which is intended to execute the action, but it is not currently linked with actionmanagement. Before, this was intended to be done with an additional npc_actions module. Right now, actions have only been possible in dialogue via monkeypatching.

Create More Complex Edge Disabling Logic (2020-2021)

Currently, after the player traverses an edge, the edge is permanently disabled if the node it leads to contains actions. This is to prevent issues like receiving multiple copies of the same item, starting the same quest twice, etc. However, this is not an optimal solution, as we can surely imagine scenarios where despite having an action, we want to continue giving players access to the node in the future. For example, if a player forgets what an NPC told them about a quest, they should be able to go back and ask him. To that end, the edge disabling logic could be made more complex.

Clone this wiki locally