One thing I’ve been working on is a graph-based, goal-oriented dialog system (in TADS3).
Normally, most dialog system are predicated on the idea that the player makes active choices (picking a option from a list, typing >ASK ABOUT some subject, or whatever) and different options might get added or removed from specific dialog nodes and things like that but otherwise it’s mostly static. The thing I’m working on is that at any given point in a conversation there’s an “active” dialog node (a vertex in a graph), but just as the player is choosing a “move” by selecting a dialog option, so is the NPC. So instead of being a simple tree the player can lawnmower through, conversations are an isomorphism of a two-player (or more!) board game, in which both players are trying to move things in a direction of their choosing.
It’s worth pointing out that this doesn’t work well for expository dialog, which is what a lot of game dialog often is. This can be kludged together by designing the graph appropriately (making a bunch of “dialog corridors” that have to be traversed to reach any “goals”), but it’s a lot more messy that just handling things using a more conventional dialog system.
It also dovetails well if you have other NPC goal-seeking behaviors, like the specific situation you’re talking about here (having an NPC comment on a change in the game world).
Very interesting approach, never considered that as an option. What technique do you use to liberate the tree from its static nature? Stochastic walk, like Markov or non-Markov chain?
I can see that hand-designing a tree like that can become a puzzle in itself.
NPC decisionmaking is handled by a simple regret minimization algorithm adapted from decision logic that I was putting together for an in-game poker-playing AI. One of the provably optimal approaches to poker AI (in the sense that it’ll approach the Nash equilibrium in a finite number of steps) is called “counterfactual regret minimization”. I was already thinking of the story vaguely in terms of a bunch of characters trying to deal with their regrets and the phrase seemed oddly compelling, so I’ve tentatively made “A story of counterfactual regret” the subtitle of the game and really leaned into regret minimization as a gameplay element.
Decision process aside, the dialog “map” (the set of all currently reachable dialog states) is a graph into which vertices and edges can be added and removed by in-game events.
Currently the way I’m handling static/bookeeping/whatever stuff (like having an explicit option to end the conversation, special topics that the player should always be able to ask about, and so on) is by having the dialog-handling logic look up the available options in the dialog graph (usually just the player-available edges of the current vertex) and then append/prepend additional stuff onto the results before formatting everything for output.
What I think I’m going to end up doing is having two dialog “maps”: a “this conversation” map and a “overall interactions with this NPC” map, if that makes sense. So building the dialog output/available inputs based on “conversational process” bits from the state of the current conversation (so adding greeting messages, increasing or decreasing NPC “interest”/“attentiveness” based on how long the conversation has been going on, and so on) and the “global” state of the interaction between the player and the NPC…the position of the ongoing board game they’re playing.
The individual vertices in the graph work more or less the way they do in most dialog systems: they’re a list of options and the next state they lead to. The gimmick or whatever is that the next state isn’t a single, deterministic state but instead a decision node for the NPC to evaluate themselves. You could do this by, for example, just implementing a bunch of conditional spaghetti in the individual “PC” dialog results, but I think the graph-based idiom (or whatever you want to call it) makes it easier to work with.
I’m a bit curious as I did at some point make a strict VERB-NOUN parser in a game for the very first TALP Jam (had stricter rules than now) but later changed the game (for another comp instead) to accept slightly more advanced input, but it would then tell the player it wasn’t necessary if they typed more than two words. The main problem was that sometimes a noun contains a space such as “car key” and the parser regarded “car key” as two words. Another example could be if you had e.g. a blue and a red pill. If you don’t allow adjectives, the game cannot tell the difference. You can of course avoid such situations but I ended up feeling that it limited that game quite a lot.
I don’t know how dialog is handled internally in In Glassand I haven’t played it so I can’t comment on that. But yeah, it’s definitely to make conversations more goal-oriented. That fell more or less naturally out of trying to make everything more dynamic and goal/narrative focused.
Basically the “hook” for the game design, for me, was thinking about how when you’re playing a game with someone you can tell a lot about how they’re feeling by how they’re playing. My spouse and I played a lot of Gloomhaven early in the pandemic, and it was obvious that when she was angry about something she’d play more impulsively, when worried more cautiously and slowly, and so on. This isn’t exactly a revolutionary observation (and she communicates her emotions in less subtle ways as well!). But it occurred to me that this isn’t something that I’ve really seen used in gameplay design. When you want to have the NPC convey an emotion, it’s usually just scripted. And frequently (in higher-budget games) performed by an actor and then played back, so the emotional component (or whatever you want to call it) is literally just a recorded human emotion being kinda cut and pasted into the gameplay…instead of being something you get from the gameplay. If that distinction makes sense.
That started a chain of thinking that got me, several internal conversations later…mostly about how feasible various designs would be and how likely they’d be to get literally any players…to playing poker in an IF game. And then that got me to applying (or at least trying to apply) the same sorts of “tricks” to other kinds of NPC behavior.
It absolutely remains to be seen how well it works in general. Like one of the things I specifically wanted to model was that befriending someone and gaining their trust isn’t just monotonically accumulating musical notes or hearts or whatever…or to have it be a simple boolean flag that’s toggled by a specific event or item. Which seem to be the predominant ways of handling this sort of thing in games. But I don’t know how much it’ll turn out to be just annoying if things don’t work “deterministically” that way.
See, this is exactly what I am doing (though not every TALK leads to options). Because I personally gripe to be made to type things I don’t need to type when they could be one-keyed. So when dialogue options appear, I don’t ask for a 1 and RETURN, you just press 1. When I ask a yes or no question, you just press Y or N, not Y and return. To repeat a command, you just hit RETURN, not type G and return.
In one dimension, this is very small stuff, but it’s an element of the game I make in my own excess-keying averse image. And in years when my game comes out, you won’t remember I told you it would be pretty smooth, but I’m going to say now that I think it’s pretty smooth.
I do understand the basic inclination to not mix modes at all. But where we are now is we have all these choice trees appearing in parser games and you still have to type numbers or whole words that are already presented completely discretely and hit RETURN. It always felt clunky to me, rather than holding me in the same UI for a really good reason.
This is sort of off-topic, but since we’re all here: what are some games making good use of vanilla Threaded Conversation? I’m not looking for brilliant mechanical enhancements. Just a game using the extension straight from the can?
I’d like to get a feel for what a strong implementation of it looks like.
My game Flattened London had a topic-based system - the player could first TALK TO an NPC to get something like “I last saw him in the salt mine”, and then ASK THEM ABOUT SALT MINE (or A SALT MINE for short) to be told “The salt mine is five hundred feet to the west, near the old well.” It was not very narratively complex, but worked well for exposition and clues, which was what my game was about.
I’ve been messing around with something similar, for similar reasons. My game is all about navigating your relationship with the NPCs, and having an element of goal seeking / decision making in their responses seems critical to making them feel more independent. I’d be interested in how you are getting on. I’d set up a target topic and had the NPC select the next best quip to get them closer to the topic. But the problem I was running into was ballooning size of the graph, and consequent computation time.
Which is frustrating, because my problem with “talk NPC” parsers is there lack of control in what and how the PC speaks. Works in some games, of course, but as mine is nearly all about talking that’s just not going to work for me.
I asked a question and then disappeared for a week… So apologies for that - I know I haven’t responded to all of your comments, but I have found them really valuable and intend to resurrect this thread with some follow-ups .
Firstly, I’m conscious that dialogue is a relatively small part of my game, so I wasn’t planning to invest too heavily in anything too heavyweight w.r.t. a dialogue (e.g., new engine, extensive vocabulary, etc.). At least not in the game’s first iteration.
The return key issue - even if I go with an options list, I’d still want a return keypress afterwards. It’s too easy, especially on a mobile phone, to hit the wrong number accidentally. And becauase my dialogue options may be non-recurring (i.e., you make your choice and you live with the consequences), that might not be satisfying for the player.
Adjectives are something about which I’m thinking separately. Currently, of the chapters of the game I’ve designed, adjectives aren’t required, but I do have a method to deal with that, should I need it (but I’m hoping I won’t because I’m a purist at heart ). And I sort-of agree with the points made around PUT, etc. However, I think on balance, increasing the complexity of the parser increases the likelihood of a player needing to “guess the sentence” or get put off by getting a misleading response when typing something that’s not quite right.
I agree with the comments that if you’re playing an all-text game, you don’t want to be brought out of that to then have to click options, so having thought about this a little bit, I’m going to make sure that the two verbs TALK and ASK can be used to drive dialogue in a way that gives the player some agency.
There will be two verbs - TALK and ASK. TALK will just be a general greeting to get the conversation started and may include clues based on your inventory or appearance (as someone suggested). Just as room descriptions have nouns with which you can interact (and EXAMINE), converastions will include nouns about which you can ASK. So these nouns will crop up as part of the conversation and you may also learn about an NPCs specialist subject from other NPCs and be able to ask them about that, too. I’m hoping that this will dispense with the guess-the-topic problem in that all the nouns about which that NPC may be asked should appear in their conversation or someone else’s - I don’t want it that the player has to cycle through every noun in the game every time they encounter an NPC just to get some clues.
The parser already drops prepositions, so if a player types ASK or ASK ABOUT , the parser will know to process it as ASK (same with TALK and TALK TO ).
I guess the proof will be in the pudding, and I might get stuck when the NPC interactions need to get more complex (I’m already thinking about an ANSWER verb…), but that’s all part of the fun!
Thanks to everyone that’s contributed (and may yet continue to contribute) - it’s been really useful to hear people’s opinions.
How does the player KNOW they don’t need to ask about every noun in the game? Or what things can be asked about. I’ve played some games (thinking of the original Fallout) where I didn’t feel sure the “ask about” feature was fully implemented, because I couldn’t make it do anything.
Honestly if it’s not that big a part of your game, why don’t NPCs make useful conversation unprompted? If TALK is the obvious action when crossing paths with anybody, save the player some trouble? You can still have the player make choices when they come to an actual choice, by prompting them at that time, and can still have the NPC respond to TALK and ASK.
Any reason you don’t mention TELL? I think it’s useful even if it’s just a synonym for ASK.
Good question. Firstly, I’m hoping this won’t be the only game I write in which there are NPCs with which the player can interact, so I’d like to create a foundation on which I can build in the future. Secondly, I am looking for something a little bit more than NPCs-as-clue-machines, even in this adventure. Theme, tone, and immersion are important to me when playing a game, so I’d like to add a dash of sparkle to my NPCs even if they are only there to remind you that the fishing rod is used for fishing.
Another excellent question. As the developer, I know I’ll only code responses when the NPC is asked about things that have been signposted in the game, but the player won’t necessarily know that. Unless I write it explicitly in the instructions, of course (which I probably will). Within my engine, players can optionally activate a ‘help mode’ which highlights scenery nouns with which they can interact in the location descriptions, which I would extend to include conversational nouns. The in-game CLUE option could also be used to share some topics about which the player could ask the NPC at that location (this will need work for the free-roaming NPCs in a later chapter, but I’ll cross that bridge when I get to it).
There’s also the ‘common knowledge’ response, so if the player asks any NPC about the fishing rod, they’ll get the same information - only that which is signposted inside the NPC conversation would be specific to that NPC. Not everything is common knowledge, of course!
Interesting. I hadn’t considered that the player might want to tell the NPC something rather than ask them about something. I don’t think of TELL and ASK as synonymous (unless it’s shorthand for TELL ME ABOUT). I had planned to use the ANSWER command if the NPC asks a question, but that’s moot at the moment (as there are currently no NPCs that ask anything of the player).
I’m not sure how much technical detail you want, but the high-level view of how I’m approaching it is probably easiest to explain in a couple of stages. First, the “naive” dialog logic:
Each NPC has a data store recording their current “feelings” on different subjects. It’s basically a big hash table where the keys are subject IDs and the values are integers, where 1000 represents a neutral reaction, 0 is the worst possible reaction, and 2000 is the best possible reaction.
Decisions work by constructing an ordered tuple of the alternatives and using the values as weights to pick a result. E.g., summing the values, and then picking a integer between 1 and the sum. There are other methods (tending to prefer the “worst” result or the “best” result or using a linear combination of values as the weight, and so on) but the simple random-1-to-sum is the easiest to understand.
In conversation, the NPC is given a “board position” (usually) dictated by whatever dialog option the player most recently chose. That is a vertex in the dialog graph, and it has edges connecting to different “NPC” dialog nodes, each of which has one or more IDs associated with it, where the IDs are subjects in their decision table. The dialog decision is resolved as described above, where the decision tuple consists of all of the edge IDs for the current vertex in the dialog graph.
Having selected an edge, the current vertex is updated, and the edges of that vertex are the topics (or whatever you want to call them) available (and/or available by default) to the player, the the process repeats.
This is basically goal-free, in the sense that all the NPC “cares about” is their favorite option at the current moment.
In addition to this, they may have one or more goals as defined as part of their state. I’m doing this in TADS3 and the state in question is an AgendaItem (or rather a subclass of AgendaItem), but all you need to know about that is that every AgendaItem instance has a numeric priority and a isReady() method, and the game automagically makes active the (one) AgendaItem on the NPC with the highest priority says it’s ready that turn.
Agendas have been extended so that they can be associated with instances of a “goal” class. The goal class defines, in game terms, specific objectives (like obtaining some object or learning some information) and different behaviors for each stage of the “quest”. So if the objective is to obtain a pebble, then the initial stage might be “look for the pebble”, directing the NPC to engage in, for example, a random walk. If the NPC learns where the pebble is (by seeing it or by having a knowledge flag twiddled by a conversation or whatever) it might then go into a “fetch” stage, where they attempt to move to the location where the pebble is. Once in the same location as the pebble, they then move into a “take” stage, attempting to take the pebble directly if it’s on the ground or talking to whoever has it if it’s in someone’s inventory.
At each stage of the process described above, the NPCs reactions on certain subjects can be tweaked to either replace or modify their “basic” reaction on one or more subjects in their decision logic (so making them interested in the “pebble” subject even if they wouldn’t normally be, but only for the duration of the “quest”). The goal can also specify “external” goals as well, which will affect dialog choices not by directly changing the weights for the edges on the current dialog vertex, but instead directing the NPC to try to “path to” a specific node (e.g. to make the conversation about pebbles even if pebbles aren’t part of any of the adjacent dialog nodes).
To improve the performance of the pathing stuff I precompute everything and then update subgraphs as edges are added or removed. The process is the same as the one I discuss for room pathfinding in this thread.
That’s basically it. There are a bunch of special cases and tweaks (like special topics that get added to the available dialog options independent of the “local conversational context” or whatever you want to call it) but it’s mostly some elaborate (but conceptually simple) random weighted choice decision logic coupled to mostly-separate mostly-deterministic large-scale goal-seeking decision logic that either modifies or overrides the probabilistic stuff.
That was a lot of words, but I think this is one of those things that sounds a lot more complicated than it really is. Feel free to ask for clarification if I haven’t explained things well enough.
Thanks! That was very clear. So every node is linked to a subject in the NPC decision table. How big is that table? I guess one subject could be linked to many vertexes!
How do the resulting conversations feel? Do they have the mechanical feel that fits puzzle solving (say X to unlock Y), or do they feel a little more like a negotiation?
One of the themes of my game is how emotion and mood shapes our reactions to things, so I could see the system you described giving me some flexibility to do that through modifying the weights; but I wouldn’t want it to feel too directly “make him sad to get him to tell you about the graveyard” - more that a sad conversation means that the graveyard is more likely to come up.
I’d also want the NPC up actively direct the conversation - so if they are sad, trying to talk about graveyards, or in your example, pebbles… but it’s not clear how that fits with the “just choose the next vertex” logic that you laid out. How do the two systems interact?
I’m not done with either the game or with implementing the decision model, so I don’t know how large the final tables will end up being. But I’m not too worried about them as a scalability issue, because individual entries are small—they’re just integers, because I’m intentionally avoiding using any floating point in the decision logic, for performance reasons.
And while the underlying data store is a hash table with subject IDs as keys and integer weights as values, the tuples used to make decisions are generated by methods that query the data store. Right now there’s a one-to-one relationship between query keys and values, and “fancier” queries are baked into separate methods on the decision engine object.
So, for example, if you’re talking to Alice and the question is “Bob and I are going to go get a pizza, you want to come?”, that might query Alice’s data store for her general reaction to the ID “bob”. But if the question is “Bob and I are going to investigate the cultist temple and attempt to stop the dark ritual, do you want to come?” that wouldn’t just query “bob” in the abstract, but specific qualities like “bob:trust”.
Right now I’m handling this by just treating them as independent IDs, but I already have different query methods for “general” reaction queries and “specific feelings” queries, where the “general” queries just look up a single ID and return the value, while the fancier query methods do more elaborate things, for example returning a normalized average of the “general” value (how does Alice feel about “bob”) and the specific “sense” (how does Alice feel about “bob:trust”). The idea being that this allows “skill rolls” (or however you want to think about them) against the specific thing (“bob:trust”) while still modelling (in a rudimentary fashion) more complex “feelings” (Alice might 100% trust Bob but just not like him…so she might run to him if she’s already in a crisis but wouldn’t willingly walk into a dangerous situation with him if she can avoid it).
But…instead of doing this sort of thing the way I just described, I think I’m going to refactor things so that the underlying hash table contains values other than integers…for example methods that return integer values (so instead of calling different methods for different kinds of queries, the decision engine API will always use the same query semantics, and any “fancy” stuff will be baked into how the data is handled in the table. Also, I think instead of handling different “aspects” of a general concept as individual keys, concepts that have “aspects” will be stored as a hash table within the main hash table. So in TADS3 hash tables are instances of the LookupTable class, so I think I’m going to have something like a NPCLookupTable class derived from LookupTable that implements all of the “emotional tuning” logic (starting out with a basic “how do I feel about this person” and then inflecting it with “how much to I trust them” or “how angry am I at them” or “how much do I owe them” and so on).
So I really don’t know how big all of that is going to end up being.
Well, I’m not done so I don’t know how well it will work in a full-scale game. But the way I’m approaching it, I think it’s no more or less “believable” or whatever than the writing makes it. The mechanics are mostly to open up design possibilities, but I think the flow or whatever of conversations still has to be managed the same way you would in implementing a more conventional dialog tree…there’s just somewhat more options you have to fill in.
From the player’s point of view, most dialog trees consist of one or more “menu” nodes, one of which is usually the main entry point of conversations: a list of subjects that can start/resume the conversation with. Some of these lead to leaf nodes, which are the end of a conversational branch, and usually just return the conversation to the “menu” node. Some are little cycles or branching paths that have several steps to a leaf node, and some might lead to other “menu” nodes.
Within that conceptual model, the player usually tolerates large conversational shifts due to their choices in “menu” nodes. They expect to be able to suddenly steer the conversation in a new direction with little or no segue. I do think that NPCs trying to “steer” conversations requires more finesse. Players are used to lawnmowering through conversations themselves and I don’t think anyone particularly notices “tonal” problems with this when they’re the one doing it. But if an NPC starts exhibiting the same behavior, I think most players would notice. So I think that usually requires planning transitions as multiple conversational “hops” (option selections and dialog “results”)…even if selecting a particular option puts the conversation on rails through the next couple choices…that is the NPC decides they want to change the subject but instead of just blankly asking about the new subject (like the player might do from a “menu” node) the NPC will talk about something tangentially related to the current subject, giving the player three (or whatever) options, but unless the player just bails completely on the subject (via a global “goodbye” option or something like that), the NPC will take that as an opportunity to segue into the subject they want to talk about. If that makes sense.
In other words, I think that’s mostly just implementation finesse instead of a technical problem.
A couple ways.
For very “high priority” subjects…so not “I want to talk about graveyards” but more “I discovered who the killer is”…that would probably be an NPC agenda, which means that if the NPC is elsewhere when the conditions are met to initiate the agenda, they might path to the player and then initiate conversation (instead of waiting for the player to interact with them). In which case they’ll just open the conversation on the appropriate topic, probably explicitly stated in the agenda: start the conversation at vertex “killerFound”. But maybe selecting from multiple possible conversational entry points based on multiple criteria…picking between multiple “killerFound” nodes by rolling for ['killerFound', 'player:trusted'] vs ['killerFound', 'self:paranoia'] or something like that.
Alternately, important subjects that aren’t important enough for the NPC to initiate a conversation to bring them up might be added to the NPC’s “default” options…basically their equivalent to the starting “menu” node that the player gets when starting a conversation, making them available whenever the NPC can make a “free” choice, which usually happens either when the conversation is in a “menu” node, or at the end of some kinds of leaf nodes.
So when the player starts a conversation the initial choice might send the conversation into a specific branch/subgraph…>ASK ABOUT LUNCH or whatever and Alice starts taking your sandwich order, and when she’s asking if you want white or wheat or if they should hold the mayo, they’re not going to suddenly start talking about the graveyard and musing about the transience of all material things. Unless it’s that kind of game I guess. But at the end of that branch, whichever leaf node is reached, it’ll have some sort of indication of what the next thing is. Maybe it’s a “goodbye” node, which means the conversation is halted and Alice runs off to get sandwiches. In that case she might then return with the sandwiches, and when that task is flagged complete, then they’re at a “free” node (basically like they’re the PC and just initiated a conversation, and so can choose the “first move”). Or if the leaf node doesn’t end the conversation but instead is a “return to menu” action, then here the NPC can pick an option from their “menu”.
For the specific kind of thing you’re talking about you’d probably want the decision criteria for “graveyard talk” to be some mood property that you’re tracking internally…sadness or depression or whatever.
One of the approaches to this kind of thing I’m experimenting with is having a number of general conversational subjects that the player discusses with either specific NPCs (Alice always wants to talk about the news, Bob is into gardening, everyone wants to talk about the strange carnival that’s come into town) with the idea that the player will be discussing these things over and over again as the game progresses and the plot and relationships evolve, and that specific points in these conversations can be used as the hooks for “specific mood” or whatever branches.
That is, gardening is something that keeps turning up in conversations with Bob, and just talking about gardening is always in the “menu” when talking with Bob…so if Bob wants to muse on the impermanence of all life, you craft your dialog options involving that as coming from Bob talking about his eggplants failing, and then have Bob steer the conversation toward that option…which goes through gardening…so the big transition is between whatever else the player and Bob have been talking about and gardening, but that transition isn’t jarring because the player is always talking about gardening with Bob. If that all makes sense.
(though not every TALK leads to options). Because I personally gripe to be made to type things I don’t need to type when they could be one-keyed. So when dialogue options appear, I don’t ask for a 1 and RETURN, you just press 1. When I ask a yes or no question, you just press Y or N, not Y and return. To repeat a command, you just hit RETURN, not type G and return.