im working on a 2D futuristic / urban cyberpunk RPG using C++. ive finished a decent amount of the engine. im able to make as many maps as i want and link them all togeather. so basically, i can have the player walk around a city and go into buildings and stuff. i can also create enemies which will fight the main character. if anyones ever played Shadowrun for the genesis, the game will be very similar to that. anyway, its time to add content. im im the process of learning Python and integrating it into the game. but first, i want to design a system for placing NPC's in the world and having them interact with the game. heres what i just wrote down, and would love comments and critisism. first off, each NPC will have a text file which will be filled with data for that NPC (ie dialogue). so each individual NPC that you could talk to would need its own text file. there could be 100's of NPCs in the game, so im not so sure this is the best method.. but how else could it be done? anyway, this is how i place NPC's in the world: in the map editor's directory, i would have a text file which looked like this:

/////////////////////////////////////////////

NUMBER_OF_NPC'S: 3

NPC_#_1_FILE: npcs/someguyA.txt

NPC_#_2_FILE: npcs/someguyB.txt

NPC_#_3_FILE: npcs/someguyC.txt

/////////////////////////////////////////////

this text file just says how many NPC's are in this map im going to work on, and the path to these NPC's data files. now, once im in the map editor, it will load 3 "brushes" (ie 'buttons' which i would be able to place anywhere in the map. they would just say "NPC1" "NPC2" "NPC3", ETC. now, the user could scroll through and choose if he wanted to place any of the NPC buttons... when he placed an NPCX on the map, it would record the position. now that ive placed all my NPC's, i have there location in the map and the data they store. when i save the map file, ill output all of the NPC's data. now in game when i load a map, ill know what NPC's are in the map, where they are, and what text file stores their data. now, this is what an NPC's data file would look like. for example the file npcs/someguyA.txt

//////////////////////////////////////////////

NAME: Bob

DIALOGUE_ROOT:
Whats up man? i havent got all day.. what can i do for you?

//now this will be the options the player will have
NUMBER_OF_ROOT_OPTIONS: 2

ROOT_OPTION_1: say "I need a job... can you hook me up?"
NPC_REPLY: sure.. i can hook you up
ACTION: LOAD_JOB_OPTIONS
INFO: jobs/newbie_jobs.txt 

ROOT_OPTION_2: say "Do you know where my brother is?"
NPC_REPLY: nah.. dont know what your talking about
ACTION: GOTO_ROOT
INFO: none

ROOT_OPTION_3: say "Take to ya later"
NPC_REPLY: be safe....
ACTION: EXIT
INFO: none

/////////////////////////////////////////////////////

do you see what they hold? basically it holds all the character interaction this NPC does with the player. all dialogue and any actions involved in the dialogue. typically, walking up to an NPC will be like this: you both say hello. your left which a choice of what to say to this NPC. things like asking questions... depending on what you ask, actions will be taken and more dialogue will be told. this could branch off to even more dialogue... if you read the above txt file i posted, you will see what im talking about. DIALOGUE_ROOT is the first thing the NPC says... then ..OPTIONS are the options of things you can say to this NPC, along with the reply the NPC will say back to you, and any actions that will be taken when you pick one of the options. there is also data to go along with the action to be taken. one option could be LOAD_JOB_OPTIONS. this would probably load another script where the npc would give the player a job. the info with this action would be the path to the job script.... it says "newbie" in the title because this NPC gives jobs for newbie characters to the game... the other options are EXIT, ie, exit the conversation.. or GOTO_ROOT ie start the conversation from the begining... the last thing id like advise on is structuring all of this. i planned on doing this:

player will search for npcs()

if player presses a button in range of an npc()

Menu->Chat_NPC(npc_in_range.data_file);

and in Chat_NPC

Menu->Chat_NPC(string data_path)
{

while(!done)
{
//draw GUI

//load a python script, sending it the data_path string
//so parsing the data file and NPC interaction will all be scripted
//in python

//draw text
}

}

the main thing here is, the chat will be handled by a Menu class. currently my menu class only draws the side panel of the screen, IE with the players health and stats and such. but my menu class will also draw / manage all menu's, like the begining of the game, options screens, inventory, ETC... i was thinking that the Menu class would have a NPC_Chat() function which would draw a chat GUI and execute the python script... does this look like a good design? having my menu class manage the NPC chat? or should it be handled by someone else? and am i doing good by parsing the npc_data.txt file via Python, and handling all NPC interaction from Python? also, i guess i have to read more, but will this be a problem since all the drawing will be done in C++ and OpenGL, i mean will i be able to switch in between the script and C++ so i can manage the interaction w/ Python but draw all the stuff needed (ie text) w / OpenGL? the last thing is, can anyone recommend a good method for moving through the dialogue tree? ive never used a tree data structure before... is this what they would be good for? keep in mind, ill probably do the parsing of the data and dialogue / NPC interaction in Python... sorry for the long post.. but this is a huge undertaking and i just want to make sure im going in the right direction before i start. thanks for any help!!!

Your way of doing it is too simplistic, and won't work for a complex game.
The dialogue options and responses should vary according to the stage the player is in the game. For example, if he completed a quest, it should have a different dialogue than if he didn't complete it. Data files like that won't work well.
In Eternal Lands I made all the NPCs to be scriptable. Basically, when you click on an NPC, you get a message from the server with the following info:
1. NPC name
2. NPC portrait
3. NPC welcome text
4. A list of responses (if any)

Any response in that list has an ID.
For example?
Hi = 1
Have any job? = 2
Bye = 3

When the player clicks on a response, the ID of that response is sent back to the server, and the script takes control of the program.

There is a function called respond_npc(player, response_id)
inside that function there is something like (pseudocode):

if(response==1)print(Hi, nice meeting you)

if(response==2)
if(player completed all the quests)print(no, no job now, sorry)
else print(yeah, I have a job...)

And so on.

His method would still work for the situation where dialog changes based on actions. All he has to do is change the input file. So all you have to do is load the dialog into a tree at the beginning of the game. (or, during area loading for each NPC, etc.) Then, when you complete a quest, you can hardcode in during the completion to change a specific NPC's dialog tree. This would assume that all NPCs are loaded at the beginning of th game (though, this doens't mean that their dialog trees cant be loaded during different parts of the game to prevent slow down).

typedef struct npc {
int x, y, z;
tree *dialog;
}

typedef struct tree {
int parent;
int nrChildren;
char *dialog;
tree *children;
}

Seems simple enough.

What you really need to rethink about is how you read in different branches. So lets say from ROOT you have 5 branches, well, each of those branches may have MORE braches. I would personally try to figure out how Never Winter Nights was able to develop their dialog tree to include actoins. Maybe something like this

0 TALK "Hello. How can I help you?";
0 ANSW "How are you?"; GOTO 1;
0 ANSW "I hate you."; GOTO 2;
1 TALK "Decent, thanks. Yourself?";
1 ANSW "I am good..."; EXIT;
1 ANSW "Dude, my life totally sucks."; GOTO 3;
2 TALK "I hate you to!"; SET_NPC_HATE_LEVEL 1; EXIT;
3 TALK "Ah, sorry to hear that. Here is some gold."; GIVE 1000 GOLD; REMOVE NODE 3;

That can be parsed line by line. Any that is an ANSW is a child. Each line can be strtok()ed by ;, and then further parsed by spaces, or something like that. Something like REMOVE NODE 3 would remove itself, and the parent node.

[Edit: I tried to draw the tree. It didn't work. I am sure you can draw it yourself though.]

Fairly scriptable, fairly simple. If you really want to get really simple about it, make a rule. For example, every single line starts with a node number, and all commands are 4 letters. So SET_NPC_HATE_LEVEL could be HATE 1; I dunno, you figure it out.

Alright, good luck.

Still, it has a drawback: When the NPC says something (or when you respond to a message), it is sometimes usefull to do other programming liek things, such as set a flag, or spawn a monster, etc.
This can't be easely done with a home mad script.
My method is a little more complicated, but allows total flexibility.

It usually works best if you simply have something for each NPC that lists keywords and how to guage how they'll respond to said keywords.

You definitely want to use a scripting language for something like this, honestly.

The order that the questions are asked really shouldn't matter much.

For example, you could even have a simple xml file that looked like this:

<NPCDIALOG>    <EVENT>        <KEYWORDS>blacksmith, black smith, smithy</KEYWORDS>        <RESPONSE>The blacksmith is next to the pub.</RESPONSE>    </EVENT>    <EVENT>        <KEYWORDS>guild, guild hall, training</KEYWORDS>        <RESPONSE> The guild hall is on the other side of town, near the church </RESPONSE>    </EVENT> </NPCDIALOG>

Then you simply compare what the player types (within the NPC's "hearing range") to the keywords. Simple.

Like I was saying, if you want something complex, a simple XML won't really help, it has to be hard coded. Or you can store each text and response ID in the XML, but then you'd have to parse XML files at runtime, which is not very fast (especially if done for an MMORPG).

hello everyone. first, i would like to thank all of your for your responses. this is a huge undertaking for me, and every bit of help i get is GREATLY appreciated! now, id like to talk about some of the things you guys suggested. before we (hopefully) talk more about it, id like for you guys to understand how the NPC interaction will work.

first, when a user clicks "T" by an NPC, he will talk to this NPC. this is what happends

The game screen disapears, and a chat GUI pops up. the user is presented with dialogue choices. heres what it will look like (from the game Shadowrun on the Genesis)

(when the player walks up to an NPC, and presses the chat button, this is the initial screen)


now, when i choose "looking for information", this is the next screen that popped up


do you see how it works? basically, it keeps going on like this. conversations could get deep. also, like Radup did in his RPG (and what i want to do), is depending on the state of the game, the chat could be different. for example, say you go to an NPC to give you a job. a random job will be picked and given to you. now, you have to go do that job. when you talk to that NPC again, if you completed the job, you will get paid. if you didnt complete the job, he wont pay you and might be a little mad...

even more complex, is there is a non-linear plot that un-ravels when talking to NPC's. depending on what NPC's you talk to, more and more of the plot will un-ravel. so if you talk to NPC A, he might give you no info. if you talk to NPC B, he'll give you some info. when you go back to NPC A, you can now talk about what NPC B told you about. and NPC A will now give you info.

i have no idea how to accomplish such a thing. i can come up with a system where an NPC will have a static dailogue, which is what i posted in the first post. (ie the dialogue tree will be in a .txt file and read in when the user chats with the NPC). but how do i make it dynamic, where the dialogue will branch differently depending on what ive done, who ive talked to, the state of the game, etc?

Quote: Original post by Raduprv
In Eternal Lands I made all the NPCs to be scriptable. Basically, when you click on an NPC, you get a message from the server with the following info:
1. NPC name
2. NPC portrait
3. NPC welcome text
4. A list of responses (if any)

Any response in that list has an ID.
For example?
Hi = 1
Have any job? = 2
Bye = 3

When the player clicks on a response, the ID of that response is sent back to the server, and the script takes control of the program.

There is a function called respond_npc(player, response_id)
inside that function there is something like (pseudocode):

if(response==1)print(Hi, nice meeting you)

if(response==2)
if(player completed all the quests)print(no, no job now, sorry)
else print(yeah, I have a job...)

And so on.

ok, but, how is this different from what i posted? basically, im doing the same exact thing. the user is presented with choices, and the choices can result in responses / actions...


@visage:

ok, so that tree struct will be how ill manage all the dialogue? basically, an NPC will have a pointer to a tree? why a pointer, though?

then, each tree will contain a string for that dialogue, and a pointer to the next dialogue? also, is this just a linked list? your example is in C, but im using C++. i could see doing this with a simple std::list Tree, i think. also, like i mentioned earlier, im going to be using Python for scripting. so maybe i would manage all the dialogue in Python? (ie the tree struct would be a Python class instead...)

@etnu:

in my first post, i said i was using text files. i know there are C++ and Python libs which can use XML. im dont really want to use XML (yet) though, because im already trying to learn Python, how to bind it to C++, AND how to manage this huge system. adding XML will just make my brain explode =)


thanks a lot guys for anymore help!!!

Define your plot to have "plot points", where the way NPCs react changes at the achievment of certain plot points. Plot points can be simple integers, although you probably want to name them for readability.

You can then have your script divided into sections, where you'd do something like:

Suppose plotpoint 23 means "troll killed" and plotpoint 15 means "quest to kill troll issued" and plotpoint 26 means "reward issued":

ifplotpoint 26:  tell player there's nothing else to do, perhaps   go see the other guy across town?ifplotpoint 23:  dialog to issue reward  set plotpoint 26ifplotpoint 15:  remind player that the troll still isn't dead  maybe give a hint about whereaboutsdefault:  tell player that the troll needs to be killed  if accepts, set plotpoint 15

You would need for game actions to be able to set plot points (kill the troll), as well as dialog choices.

This system wasn't my invention, by the way; I stole it wholesale from Well of Souls (which allows you to design your own stories like this).

Mine is different from the other guys because mine, being scripted, allows additional code, not only responses. So inside an if(){} you can also place code to set flags, reset flags, spawn monsters, etc.
The ideas the others posted won't let you do that.

Where in my code do I not allow further functions? Infact, I give a perfect example of GIVE 1000 GOLD. Why wouldn't he also be able to do something like SPAWN TROLL 11 EVIL 10 20 (spawn a troll of level eleven that is evil aligned, at 10, 20). Hell, he could do an if statement if he wanted to implement it. He just needs a line identifier so that he knows action belongs to what node. For example, every new node line could start with a N, and every line after that could have an A for action or something.

You could even easily implement static variables. For example %playerx% and %playery% could be the players X and Y positions.

N 0 TALK "Hello, how can I help you?"; //no action, show child nodes
N 0.1 ANSW "How are you?"; GOTO 0.1.1; //jump to a child node
N 0.2 ANSW "I hate you!";
A IF %currNPCtype% == BLACKSMITH; GIVE 1000 EXP; ENDIF
N 0.1.1
...

etcetera.

I thought about mine and thought that it would be hard to tell what nodes and subnodes are. So I rethought it and rewrote my original script (it will make the above more legible).

0 TALK "Hello. How can I help you?";
0.1 ANSW "How are you?"; GOTO 0.1.1;
0.2 ANSW "I hate you."; GOTO 0.2.1;
0.1.1 TALK "Decent, thanks. Yourself?";
0.1.1.1 ANSW "I am good..."; EXIT;
0.1.1.2 ANSW "Dude, my life totally sucks."; GOTO 0.1.1.2.1
0.2.1 TALK "I hate you to!"; SET_NPC_HATE_LEVEL 1; SPAWN TROLL 11 EVIL 10 20; EXIT;
0.1.1.2.1 TALK "Ah, sorry to hear that. Here is some gold."; GIVE 1000 GOLD; REMOVE NODE 0.1.1.2.1;


As you can tell with this other way, it is much easier to tell what is a child of what, and which nodes are brothers and sisters. Though, it may be a little harder to parse.

Anyway, the tree was a pointer so that you could dynamically change its size, depending on its children. I don't think making a linked list would be a good idea. Simply, for each "level" have an array, whose values are their children.

So at level 0, you have two entries: 0.1 and 0.2
At level 1, you have two entries: 0.1.1 and 0.2.1 (each in their respective branch)
At level 2, you have two entries, 0.1.1.1 and 0.1.1.2
At level 3, you finally have one entry, at 0.1.1.2.1

So try drawing out the tree. It is hard to explain in words.

So it comes down to the fact that you want a very dynamic scripting language, so you can perform actions, but you really want definitive rules, so that it is easy to read and parse, especially because it is in real time. If you want a really simple way of performing actions, use a function pointer. Give each NPC struct (or class or whatever) an "action" pointer. If you want something performed, code it in C and call it in your script.

%currNPCaction% = givegold (int)1000;

givegold is a function you have already coded in C, and (int)1000 would be the argument.

Just call currNPC.action(); after every frame or something while the player is talking. When you dont want anything done, set it to NULL. when the pointer is NULL, just dont perform it.

[in a cpp file. NOT SCRIPT]
NPC currNPC = BlackSmith1;
currNPC.action = NULL;
... //do parsing stuff here
if(currNPC.action != NULL){ //we have loaded in a function
currNPC.action(); //call the function
currNPC.action = NULL; //reset it so that we dont continue to call the functions
}

This could allow for cool things, like hardcoding in a battle with an NPC just by using a function pointer to some function you have written, then after beating them, setting the pointer to NULL.

Anyway, I hope all these ramblings and ideas gave you something to chew on.