• ### Remove ads and support GameDev.net for only $3. Learn more: The New GDNet+: No Ads! • # NPC Conversation Techniques Game Design and Theory NPC Conversation Techniques Courtesy of Amit Patel Did I hear a request to discuss conversation engine techniques? That means an opportunity to repost for discussion my 26 screen paper on the best way to talk in a game. Booo-ha-ha-ha-ha-ha... : ) Seriously, I'm quite interested in how to work a solid, intuitive conversation, and any suggestions would be welcome. # 1.0 Introduction I've noticed a preponderance of posts all looking for various graphics tricks and techniques to use in their games. While I have no problem with this (in fact, I've learned quite a few things), there's been another programming problem on my mind lately. I haven't really though too heavily about it, but I'd like to throw a few ideas out in this forum and see where it goes. Results of open-discussion will be incorporated into this paper over time. Source code will inevitably follow, and the resulting monolith (as it seems to be taking on a life of its own) will be donated to the Rec.Games.Programmer Programming Encyclopedia if it is deemed useful enough. ## 1.0.1 Statement of Purpose What I'm interested in creating is a conversation engine. I want to find a method of allowing communication between players and the computer characters (Non Player Characters or NPCs). Ideally it would allow the following: 1. Structured interaction between the player(s) and NPCs. This would allow conversations to take place, and would be the normal method of communication. It would allow player input, as well as the "standard greeting" given by an NPC from whom nothing else can be obtained. For example: it would allow players to negotiate with a shop owner, but also allow players to get information from a pedestrian ("Welcome to Port Nowhere". ). 2. Flexible dialogues based on external flags. This would allow NPCs to change conversations depending upon events in the storyline. For example: everyone in town will talk of nothing other than the slimy alien who ate the mayor. Once the alien is disposed of, they would be free to talk about other things. 3. It should be (fairly) easy for the players to determine how to ask certain questions, while not be merely a matter of walking through every branch of a conversation tree. For example: the venerable Sierra engine vs. Ultima Underworld (more detail on this later). 4. It should be fairly easy to program and maintain (including efficient storage) to allow many large conversations to be created, tested, and maintained without inordinate amounts of effort. 5. It should be flexible enough to provide better than 3rd grade levels of conversation, but extensible enough to handle modifications without undue difficulty. 6. It should be easy to use for novice players, but convenient for advanced players. This means it should also allow both keyboard and mouse input. If it can incorporate both seamlessly, then the player can decide what combination works best. One other item to keep in mind, is that the conversation engine should be flexible enough to be incorporated into the rest of the interface. It must function smoothly with the movement engine, and any other control routines the program may require. What this list of requirements does, is prove that this problem will be more difficult to solve effectively than the graphics portion of my program, because the approach is not terribly well defined. # 2.0 Common Approaches There are three main approaches I have seen. They are: 1. Text Parsing 2. Menu-Driven Conversations 3. Hybrid Conversations Each has distinct advantages and disadvantages: ## 2.1 Text Parsing Text Parsing Engine. A prompt is given to the player, nothing more. Input is typed in the following syntax: . This is a very old and refined method of input for a game, allowing all manner of action to be effected upon the environment. Generally, it has been used as the primary means of interacting with the game (as in the case of the old text adventure games), but has also been seen used as a primitive vehicle for interaction with NPCs. Examples of this sort of input would be: TADS (the Text ADventure game System), old Sierra games, Zork (really old people might remember this one : ) ), etc. Advantages: "Correct" actions are concealed from the player. Player needs to think about problems, rather than just walk though all the possibilities. Generally very good for puzzle creation, where the trick is to determine what to use X for to effect Y (for example: "put the key in the lock", "open the door"). The fact that it is the oldest form of input means that it has been resolved to a respectable level of complexity, and can simulate natural conversation fairly well. For example: ASK THE MAN ABOUT THE WHALE "Oh, the whale. He's a real killer alright. Nary a man sails the sea without keeping one eye out for the whale." ASK THE MAN ABOUT A BOAT "A boat? Surely you're not thinking of sailing? You're crazier than I thought!"  Disadvantages: "Correct" actions are often extremely difficult to determine, leading to frustration on the part of the user, especially if the puzzles are difficult, ill-conceived, or multi-part. This is especially difficult when a nice illustration or snazzy description does not match the name by which an object is referred to internally. Anyone who has ever played one of these games has seen the following: TAKE THE WINE "I don't know what a WINE is" TAKE THE FLASK "I don't know what a FLASK is" TAKE THE DAMN BOTTLE "I don't know what a DAMN is" TAKE THE BOTTLE "You have taken the bottle."  This can quickly lead to frustration, as the player has difficulty in manipulating the interface. The largest problem is that user though patterns are always a mystery, as we have all seen (especially from beta testers: "What? You mean you tried to put the bathtub in your backpack and the game crashed? Gee... I never thought of that one...") Players, especially good ones, are notorious for trying the bizarre just to see what happens. (In fact, I 've always found that in these types of games, finding the little bizarre cases that they actually put into the game just to see if anyone tries it are the most interesting parts of these games.) Regardless, this form of communication is user un-friendly, despite the fact that it's relatively straightforward to program. ## 2.2 Menu-Driven Conversations Menu Driven Conversations: These are conversations where the NPC says something and the player is presented with a multiple choice answer. Ultima Underworld II used this form of communication: Angry Orc: "Hey! Nobody gets in here without the password." A. "Yes. The password. I know it." B. "The password? Oh, I forgot it. It's downstairs. I'll be right back." C. "Password? I don't need no stinkin' password!"  Advantages: The choices are obvious, allowing the player to concentrate on their course of action, not "guess the right question". An interface should intrude upon the game as little as possible, allowing the player to invlove themselves with your game, not entangle themsleves in their hardware. The conversation is a little more colorful (I've always loved choice "C".) and allows you to texture the conversation and use consistent slang to keep the player in character: B. "Yea, the scourge of the east approaches."  Disadvantages: The choices are a little too obvious. A player can merely save their game, and then try all the different branches of the conversation tree until they find the desired path. One possible solution is to allow save games only in certain locations, making it more trouble than it's worth to try all the options at will. On the other hand, this inconveniences the player and complicates the interface. (Personally. I don't mind the limited saves concept. It has the extra advantage of making combat a little more stressful than infinite save points does.) Large numbers of choices are difficult to implement. If your game is a detective-type game, where you have large numbers of questions to ask large numbers of people, than the engine becomes unwieldy. It can also take a long time to traverse enough branches to get the desired result. This also detracts from the feel of the game. ## 2.3 Hybrid Engine The hybrid engine is a combination of both previous systems. On the one hand, it presents the player with a list of actions that may be tried, allowing them to decide which is appropriate. It also obscures the painful obviousness of multiple-choice answers. From this basis, there are two major variations: the full-keyword version, and the basic choices plus optional keyword version. Both systems traverse conversations in the same way. Typical conversation: (Approach Fred, initiate conversation by selecting GREETING from list) you: "Greetings friend." response: "Greetings yourself, traveler. Nice day today." (select TRADE) you: "I have traveled many lands and have acquired many curiosities. Perhaps you might have as well. Would you care to barter a bit?" response: "Ho there! Is my profession so obvious that you can spot me as a trader a mile off? Of course! Let us see what we have..."  ### 2.3.1 The All-Keyword System This engine presents the player with a list of keywords. The player picks a keyword, and the appropriate conversation proceeds from there. As the game progresses, more keywords are added to the list, allowing the player to revisit certain NPCs to see if they know anything new. An example of this type of game would be Bad Blood, a post-apocalyptic game. As you progressed in the game, new keywords would be added to your list of options. You would know which parts of conversations were important, and could then revisit key characters and try the new keywords. Disadvantages: The all-keyword system. This allows the player to talk to everyone about everything, and wait for the important keywords to show up. (Similar to the way you'd get points in the old Sierra games for doing correct things.) This could take some of the thought out of the game, as a player can simply run through conversations only looking for the 'beep' that indicates a new keyword. On the other hand, it allows some feedback to the player on their progress. Another disadvantage, is that all intonation is predetermined. If you wish to ask a character about a certain item. Like a bottle, you choose bottle and the computer phrases your question for you. It takes away a player's ability to decide how they wish to phrase their question. Phrasing is especially useful when giving NPCs their own motivations. For example, you might want to lean on a weak-willed Orc to get information, but you would probably affect a more fawning tone in the presence of royalty, lest you find yourself shorter by a head. Intonation and interpretation is a vital part of communication (as seen by the net usage of : ) and similar icons to ensure that the intended meaning is not misinterpreted by the reader) and eliminating that aspect of conversation can detract from the player's association with their character. ### 2.3.2 The Standard Choices With Optional Keyword This is similar to the first option, only this time, there are only basic choices presented to the player. There is also a blank space, where the player may try any other keywords they might like to try. This allows for some subtlety on the part of the designer. Key hints could be given and the keyword not added to the list (which would really annoy some players, who would accuse you of design flaws) or the list of choices could always be the same, relying on the character to keep track of what might be important. An example of this type of game would be The Summoning, a single-person dungeon game. Disadvantages: This system might seem to present some of the same limited choices that commonly have players trying vaguely related verbs. For example, the ubiquitous "use" verb that also stands for: twist, read, peel, pry, flick, turn on, etc. The other possible twist is that a player may find out a keyword before the plot would normally present it to them. This might be more common than initially thought, with stumped players frequently requesting this sort of information at the wrong time, or for someone who might by playing a second time. The solution would be to implement the EVENT flag concept, locking out certain keywords and conversations until certain events have happened. This system also suffers from the same lack of intonation as the previous flavor of this engine. # 3.0 Conclusions To be honest, I'm not quite sure. If I had to say that I was leaning towards any particular engine, I'd have to say it was type 2.3.2: standard action words with optional keyword. It seems to offer the strongest balance between player assistance and mystery. Unfortunately, it does nothing to solve the intonation issue. We would seem to need another option for our list of choices: one which allows some flair in conversation, allows the player to choose emotional context for their statements, yet obscure the choices somewhat, making the conversation less of a "try all the choices in order" process. What I'd like to know is if anyone else has thought about this problem, if I've might have missed another way, or if there is a better way to implement one of these choices. # 4.0 Coding Issues As for the coding issues discussed initially, I 'd like to keep those in mind when discussing the possibilities (e.g. how could they be implemented) without clouding the issue with coding techniques just yet. (Because we all completely think through our ideas before we start programming them right? : ) ) Even so, we need to remember that the system should be extensible. If it works well, I intend to adapt the engine for use with examining objects and other sorts of interaction with the environment around the players. Flexibility is the key - we are looking to support both short conversations, as well as longer ones, and we will need to be able to maintain and dry-run our conversations to ensure that they flow. This section will be expanded along with the others as the topic matures. # Bibliography 1. The Journal of Computer Game Design, Volume 6, Number 3. Estvanik, Steve. Designing a Mouse/Command Line Interface. February, 1993. p.10-11. 2. The Journal of Computer Game Design, Volume 6, Number 3. Em, Michele. How to write Interactive Characters and Dialogue. February, 1993. p. 14-5. (Before you ask: "The Journal of Computer Game Design is published six times a year. To subscribe to the Journal, send a check or money order for$36 (\$50 outside North America) to:
The Journal of Computer Game Design
San Jose, CA 95132


Although I wouldn't if I were you. Not that the effort isn't appreciated, but it's hard to get in-depth articles from starving programmers who are already past deadlines. Articles are 1 - 2 pages and very abstract. The Journal has moved away from code-oriented articles in favor of "interactive storytelling" types. I also cannot vouch for the accuracy of this information. I stopped getting it a year ago after the first (and only year) of my subscription.)

3. Hartnell, Tim. Creating Adventure Games on Your Computer. Ballantine Books. New York, New York. 1984.

Report Article

## User Feedback

There are no comments to display.

## Create an account

Register a new account

• 2
• 0
• 0
• 1
• 1

• 14
• 10
• 25
• 9
• 57
• ### Similar Content

• By Seer
I have programmed an implementation of the Separating Axis Theorem to handle collisions between 2D convex polygons. It is written in Processing and can be viewed on Github here. There are a couple of issues with it that I would like some help in resolving.
In the construction of Polygon objects, you specify the width and height of the polygon and the initial rotation offset by which the vertices will be placed around the polygon. If the rotation offset is 0, the first vertex is placed directly to the right of the object. If higher or lower, the first vertex is placed clockwise or counter-clockwise, respectively, around the circumference of the object by the rotation amount. The rest of the vertices follow by a consistent offset of TWO_PI / number of vertices. While this places the vertices at the correct angle around the polygon, the problem is that if the rotation is anything other than 0, the width and height of the polygon are no longer the values specified. They are reduced because the vertices are placed around the polygon using the sin and cos functions, which often return values other than 1 or -1. Of course, when the half width and half height are multiplied by a sin or cos value other than 1 or -1, they are reduced. This is my issue. How can I place an arbitrary number of vertices at an arbitrary rotation around the polygon, while maintaining both the intended shape specified by the number of vertices (triangle, hexagon, octagon), and the intended width and height of the polygon as specified by the parameter values in the constructor?
The Polygon code:
class Polygon { PVector position; PShape shape; int w, h, halfW, halfH; color c; ArrayList<PVector> vertexOffsets; Polygon(PVector position, int numVertices, int w, int h, float rotation) { this.position = position; this.w = w; this.h = h; this.halfW = w / 2; this.halfH = h / 2; this.c = color(255); vertexOffsets = new ArrayList<PVector>(); if(numVertices < 3) numVertices = 3; shape = createShape(); shape.beginShape(); shape.fill(255); shape.stroke(255); for(int i = 0; i < numVertices; ++i) { PVector vertex = new PVector(position.x + cos(rotation) * halfW, position.y + sin(rotation) * halfH); shape.vertex(vertex.x, vertex.y); rotation += TWO_PI / numVertices; PVector vertexOffset = vertex.sub(position); vertexOffsets.add(vertexOffset); } shape.endShape(CLOSE); } void move(float x, float y) { position.set(x, y); for(int i = 0; i < shape.getVertexCount(); ++i) { PVector vertexOffset = vertexOffsets.get(i); shape.setVertex(i, position.x + vertexOffset.x, position.y + vertexOffset.y); } } void rotate(float angle) { for(int i = 0; i < shape.getVertexCount(); ++i) { PVector vertexOffset = vertexOffsets.get(i); vertexOffset.rotate(angle); shape.setVertex(i, position.x + vertexOffset.x, position.y + vertexOffset.y); } } void setColour(color c) { this.c = c; } void render() { shape.setFill(c); shape(shape); } }
My other issue is that when two polygons with three vertices each collide, they are not always moved out of collision smoothly by the Minimum Translation Vector returned by the SAT algorithm. The polygon moved out of collision by the MTV does not rest against the other polygon as it should, it instead jumps back a small distance. I find this very strange as I have been unable to replicate this behaviour when resolving collisions between polygons of other vertex quantities and I cannot find the flaw in the implementation, though it must be there. What could be causing this incorrect collision resolution, which from my testing appears to only occur between polygons of three vertices?
Any help you can provide on these issues would be greatly appreciated. Thank you.

• Hello everyone, I'm new here and sorry if this isn't the right place to ask but i asked in a few forums around the internet and no one yet help with it.. I'm have been trying to mod this game for years, but I still stuck with the raw files from RACJIN games,
Raw Files [ Mod edit: Removed ]
I would like to identify the compression algorithm used to compress these files so that they can be decompressed and analyzed.

Game : Naruto Uzumaki Chronicles 2... A.K.A Naruto Konoha Spirits in Japan.
• By Waaayoff
I'm looking for an algorithm that I can use to remove vertices that are close to each other within a margin of error in a triangular mesh. Pretty much similar to Blender's "Remove Doubles" feature, if anyone is familiar with it.
I think the issue isn't just removing the doubles, but also how would I handle the face indices once I remove "duplicate" vertices?
• By iGrfx
I've learned that the triangle clipping in the rasterization process usually using Sutherland–Hodgman algorithm. I also found an algorithm called "Guard-band". I'm writing a software raster so I want to know what technical the GPU use, I want to implement it for study. Thanks!
updated: what's the more proper triangulate algorithm?

• Welcome to the first part of multiple effect articles about soft shadows. In recent days I've been working on area light support in my own game engine, which is critical for one of the game concepts I'd like to eventually do (if time will allow me to do so). For each area light, it is crucial to have proper soft shadows with proper penumbra. For motivation, let's have the following screenshot with 3 area lights with various sizes:

Fig. 01 - PCSS variant that allows for perfectly smooth, large-area light shadows

Let's start the article by comparison of the following 2 screenshots - one with shadows and one without:

Fig. 02 - Scene from default viewpoint lit with light without any shadows (left) and with shadows (right)

This is the scene we're going to work with, and for the sake of simplicity, all of the comparison screenshots will be from this exact same viewpoint with 2 different scene configurations. Let's start with the definition of how shadows are created. Given a scene and light which we're viewing. Shadow umbra will be present at each position where there is no direct visibility between given position and any existing point on the light. Shadow penumbra will be present at each position where there is visibility of any point on the light, yet not all of them. No shadow is everywhere where there is full direct visibility between each point on the light and position.
Most of the games tend to simplify, instead of defining a light as area or volume, it gets defined as an infinitely small point, this gives us few advantages:
For single point, it is possible to define visibility in a binary way - either in shadow or not in shadow From single point, a projection of the scene can be easily constructed in such way, that definition of shadow becomes trivial (either position is occluded by other objects in the scene from lights point of view, or it isn't) From here, one can follow into the idea of shadow mapping - which is a basic technique for all others used here.

Trivial, yet should be mentioned here.
inline float ShadowMap(Texture2D<float2> shadowMap, SamplerState shadowSamplerState, float3 coord) { return shadowMap.SampleLevel(shadowSamplerState, coord.xy, 0.0f).x < coord.z ? 0.0f : 1.0f; } Fig. 03 - code snippet for standard shadow mapping, where depth map (stored 'distance' from lights point of view) is compared against calculated 'distance' between point we're computing right now and given light position. Word 'distance' may either mean actual distance, or more likely just value on z-axis for light point of view basis.

Which is well known to everyone here, giving us basic results, that we all well know, like:

Fig. 04 - Standard Shadow Mapping

This can be simply explained with the following image:

Fig. 05 - Each rendered pixel calculates whether its 'depth' from light point is greater than what is written in 'depth' map from light point (represented as yellow dot), white lines represent computation for each pixel.

Percentage-Close-Filtering (PCF)
To make shadow more visually appealing, adding soft-edge is a must. This is done by simply performing NxN tests with offsets. For the sake of improved visual quality I've used shadow mapping with bilinear filter (which requires resolving 4 samples), along with 5x5 PCF filtering:

Fig. 06 - Percentage close filtering (PCF) results in nice soft-edged shadows, sadly the shadow is uniformly soft everywhere

Clearly, none of the above techniques does any penumbra/umbra calculation, and therefore they're not really useful for area lights. For the sake of completeness, I'm adding basic PCF source code (for the sake of optimization, feel free to improve for your uses):
inline float ShadowMapPCF(Texture2D<float2> tex, SamplerState state, float3 projCoord, float resolution, float pixelSize, int filterSize) { float shadow = 0.0f; float2 grad = frac(projCoord.xy * resolution + 0.5f); for (int i = -filterSize; i <= filterSize; i++) { for (int j = -filterSize; j <= filterSize; j++) { float4 tmp = tex.Gather(state, projCoord.xy + float2(i, j) * float2(pixelSize, pixelSize)); tmp.x = tmp.x < projCoord.z ? 0.0f : 1.0f; tmp.y = tmp.y < projCoord.z ? 0.0f : 1.0f; tmp.z = tmp.z < projCoord.z ? 0.0f : 1.0f; tmp.w = tmp.w < projCoord.z ? 0.0f : 1.0f; shadow += lerp(lerp(tmp.w, tmp.z, grad.x), lerp(tmp.x, tmp.y, grad.x), grad.y); } } return shadow / (float)((2 * filterSize + 1) * (2 * filterSize + 1)); } Fig. 07 - PCF filtering source code

Representing this with image:

Fig. 08 - Image representing PCF, specifically a pixel with straight line and star in the end also calculates shadow in neighboring pixels (e.g. performing additional samples). The resulting shadow is then weighted sum of the results of all the samples for a given pixel.

While the idea is quite basic, it is clear that using larger kernels would end up in slow computation. There are ways how to perform separable filtering of shadow maps using different approach to resolve where the shadow is (Variance Shadow Mapping for example). They do introduce additional problems though.

To understand problem in both previous techniques let's replace point light with area light in our sketch image.

Fig. 09 - Using Area light introduces penumbra and umbra. The size of penumbra is dependent on multiple factors - distance between receiver and light, distance between blocker and light and light size (shape).

To calculate plausible shadows like in the schematic image, we need to calculate distance between receiver and blocker, and distance between receiver and light. PCSS is a 2-pass algorithm that does calculate average blocker distance as the first step - using this value to calculate penumbra size, and then performing some kind of filtering (often PCF, or jittered-PCF for example). In short, PCSS computation will look similar to this:
float ShadowMapPCSS(...) { float averageBlockerDistance = PCSS_BlockerDistance(...); // If there isn't any average blocker distance - it means that there is no blocker at all if (averageBlockerDistance < 1.0) { return 1.0f; } else { float penumbraSize = estimatePenumbraSize(averageBlockerDistance, ...) float shadow = ShadowPCF(..., penumbraSize); return shadow; } } Fig. 10 - Pseudo-code of PCSS shadow mapping

The first problem is to determine correct average blocker calculation - and as we want to limit search size for average blocker, we simply pass in additional parameter that determines search size. Actual average blocker is calculated by searching shadow map with depth value smaller than of receiver. In my case I used the following estimation of blocker distance:
// Input parameters are: // tex - Input shadow depth map // state - Sampler state for shadow depth map // projCoord - holds projection UV coordinates, and depth for receiver (~further compared against shadow depth map) // searchUV - input size for blocker search // rotationTrig - input parameter for random rotation of kernel samples inline float2 PCSS_BlockerDistance(Texture2D<float2> tex, SamplerState state, float3 projCoord, float searchUV, float2 rotationTrig) { // Perform N samples with pre-defined offset and random rotation, scale by input search size int blockers = 0; float avgBlocker = 0.0f; for (int i = 0; i < (int)PCSS_SampleCount; i++) { // Calculate sample offset (technically anything can be used here - standard NxN kernel, random samples with scale, etc.) float2 offset = PCSS_Samples[i] * searchUV; offset = PCSS_Rotate(offset, rotationTrig); // Compare given sample depth with receiver depth, if it puts receiver into shadow, this sample is a blocker float z = tex.SampleLevel(state, projCoord.xy + offset, 0.0f).x; if (z < projCoord.z) { blockers++; avgBlockerDistance += z; } } // Calculate average blocker depth avgBlocker /= blockers; // To solve cases where there are no blockers - we output 2 values - average blocker depth and no. of blockers return float2(avgBlocker, (float)blockers); } Fig. 11 - Average blocker estimation for PCSS shadow mapping

For penumbra size calculation - first - we assume that blocker and receiver are plannar and parallel. This makes actual penumbra size is then based on similar triangles. Determined as:
penmubraSize = lightSize * (receiverDepth - averageBlockerDepth) / averageBlockerDepth This size is then used as input kernel size for PCF (or similar) filter. In my case I again used rotated kernel samples. Note.: Depending on the samples positioning one can achieve different area light shapes. The result gives quite correct shadows, with the downside of requiring a lot of processing power to do noise-less shadows (a lot of samples) and large kernel sizes (which also requires large blocker search size). Generally this is very good technique for small to mid-sized area lights, yet large-sized area lights will cause problems.

Fig. 12 - PCSS shadow mapping in practice

As currently the article is quite large and describing 2 other techniques which I allow in my current game engine build (first of them is a variant of PCSS that utilizes mip maps and allows for slightly larger light size without impacting the performance that much, and second of them is sort of back-projection technique), I will leave those two for another article which may eventually come out. Anyways allow me to at least show a short video of the first technique in action:

Note: This article was originally published as a blog entry right here at GameDev.net, and has been reproduced here as a featured article with the kind permission of the author.
You might also be interested in our recently featured article on Contact-hardening Soft Shadows Made Fast.