Procedural Quest Generation

[jdoran]

I haven't discussed this publically in a while, so I would like to take a moment and mention the status of this project.

I recently completed my PhD, with my topic being procedural quest generation. For this I modified EQEmu so that my quest generator could add and remove quests. Since this was on a private server, I was free to make changes to the codebase which might not (read mostly likely not) be agreeable to the EQEmu community. At some point, if there is sufficient interest, I might investigate how to do this in a more agreeable fashion so that the work can be shared.

I am still planning on continuing research along these lines. With a basic functional generator, I am setup to do work in this area. The current crop of quests are OK, but leave a lot to be desired. I am certain that the quality can be greatly increased.

What I did was to study several thousand quests from various MMORPGs and break them down into abstract pieces. I tried to keep track of NPC motivation, and the basic strategies which the quests used. I found many patterns, beyond the basic 'Fed-Ex' quest. But these delivery quests are an excellent example of how patterns can be reused to good effect.

I have a few papers on this subject, as well as my dissertation. There is no need for me to go over it all here. PM me and I'll point anyone to them, or provide copies.

But I would like to mention some of the run-time changes which I think worked out well. Obviously a lot of run-time stuff needed to be done. The generator builds Perl scripts which get dropped into the quests folder, as well has database entries. I am thinking right now of the Perl-callable features.

I added 'micro instancing', which I think is novel. Some content can only be seen by people who are running the quest, or somehow linked. This means if you are grouped, or in a raid with someone running the quest, and this person is at the proper stage in the quest. Otherwise you do not see, nor are affected by the content. This is to keep the world from getting cluttered up by generated content. Examples of this content would be NPCs and buildings. It also extends to dialog with existing NPCs, items on vendors, foragable items.

Destruction of objects (buildings, wagons, chests, etc) was added. This was done by adding invisible proxy NPCs.

Particle effects can be turned on and off at locations in the world.

My quests use the quest task selectors and quest journal. But since they might grow larger than is allowed, only a small set of active quest steps is shown at any time.

Quest-specific loot can be added to a mob when killed by someone running the quest.

Clickable items can be restricted to only work on certain mobs.

Quests can rollback to an earlier state if something unusual happens.

It is also possible to 'lock' mobs so that they cannot be affected by other players. An example of this might be a dragon which is needed by two raids. The first player to engage the dragon would lock the encounter for their raid. This lock is extended to a set of related mobs, so if there are additional mobs in the encounter they could be locked at the same time.

A lot of this was not on live, so might not fit in the scope of what EQEmu is trying to do. Some of it might be downright dumb ideas that needed to be tested.

Finally I should add that in the move to my new job, I lost a few months of work. That is, I don't have the current codebase, but am using an earlier backup. I don't think that will be too bad, since I was mostly writing the dissertation at that time. The other side effect of moving to my new job is that I need to setup a new server, which is doing fine at the moment. And then merge my code.

Anyhow, the point of this post is just to say what I've been working on, and explain some of the oddball questions I may have asked at times.

I am hoping to explore dialog generation in the near future. People have been working on story/dialog generation for decades, and I am wondering if Everquest might provide a narrower scope.

[chrsschb]

You had me at hello.

[jdoran]

Oh, one thing I forgot to mention. Each generated quest is a single XML file which is imported into the server by a stand-alone Java program. Everything for that quest is in that single file. Quests can be loaded/unloaded with a couple of mouse clicks. This is a big departure from the current system, and I had to try it out.

There is the potential for multiple quests to advance with some event. It is remote, and even more so with the event filtering that only considers events which would advance an active quest. But it is still possible to 'hail' an NPC and get responses from mulitple quests. Such is the nature of research.

[Packet]

Very interesting idea. I hope to see more from you.

[Drajor]

I have read one of the papers and can confirm awesome/10

[jdoran]

I was on IRC today, and the view was that without seeing code it would be difficult to form an opinion.

My concern right now is to figure out the best way of merging my changes with the current base. It would be great if I could have some hooks added to the main code-base so that I wouldn't need to do a lot of work each time there was a code change.

Rather than post full files, let me illustrate some of the major concerns.

First, I have been using PERL to hold quest scripts. This was all that was available when I started my work. I may switch to Lua. Keep this in mind when considering the following.

The routine PerlembParser::EventCommon figures out the package name to use based on objid. This will create a name such as qst1234 (for npcid 1234) or qstdefault for other object types. This package name will not work for my runtime, as I need each quest to live in its own package/namespace.

I maintain a notion of 'quest-id' which means that generated quests are assigned a locally unique integer when they are loaded into the server. So we might have quest 400012, and it will have its own namespace. All of the scripts needed for this quest will be placed in this namespace. This keeps name clashes from occuring. If the quest is unloaded and later reloaded, it will be assigned a different quest-id, and this is OK.

My package names are based on this quest-id, and are therefore unique on the machine. It is very important that when an event is dispatched to a script, that this package name be determined correctly. Currently I am passing the quest-id and the subroutine name into the call to EventNPC (and its ilk).

Official code:

parse->EventNPC(EVENT_SLAY, killerMob->CastToNPC(), this, "", 0);

Modified code:

parse->EventNPC(EVENT_SLAY, killerMob->CastToNPC(), this, "", 0,
                                0, "");

This is an example of an existing EventNPC call, modified to pass in a 0 quest-id and an empty subroutine name. The EventCommon code would continue to work as before. But if my runtime passed in an event, it would have a non-zero quest id. In this case, the package id would be calculated differently. This was done in loadQuest (which is no more) based on the quest type.

        case questLARC:
                packagename = QTriggers::Instance().packageName(questID);
                filename = QTriggers::Instance().questScript(questID);
                path << "quests/larc/" << filename;

                if (QTriggers::Instance().isLoaded(questID))
                {
                        LogFile->write(EQEMuLog::Quest, "quest %d already loaded",
                                questID);
                        break;
                }

                LogFile->write(EQEMuLog::Quest, "Parser: load quest %d: "
                        "package = %s, filename = %s", questID, packagename.c_str(),
                        filename.c_str());

                QTriggers::Instance().markLoaded(questID);
                perl -> eval_file(packagename.c_str(), path.str().c_str());
                break;

Adding two parameters to each EventNPC may be unpopular. I am open to alternatives. And I'm reluctant to make these changes without some positive feedback.

The next modification was the addition of a different event mechanism. I created a structure to hold information on each event, and then passed that into my quest manager. This quest manager object would decide if the event was of interest:

• Does the client have an active quest which will use this event?
• Is the player at the proper point in this quest for the event to be considered?

My goal is to not send each event into the script unless it is needed. Yes, there are ways to do this with globals. My technique isolates one quest from another. I can add/remove quests without worrying about what global flags are being used. The quest manager needs to keep track of the progress through the quest anyways, so there is no additional work.

I should add at this point: The quest manager maintains each quest as a graph of nodes which are connected via events. The quest is in effect a state machine. The events may cause a state change (the quest to advance). The quest manager therefore keeps track of the current state of each quest in the database. Quests are infrequently updated, so there is little overhead in updating the database when a quest advances. And records for active quests are loaded per-character when the character zones in, and only those events which can occur in the current zone are tracked.

        QEventDeath death_event;
        death_event.id = EVENT_DEATH;
        death_event.entityID = GetID();
        death_event.npcID = GetNPCTypeID();
        death_event.init = give_exp_client;
        death_event.killer = killerMob->CastToNPC();
        if (give_exp_client)
        {
                death_event.character_id = give_exp_client -> CharacterID();
        }
        else
        {
                death_event.character_id = 0;           // gm kill perhaps
        }

        death_event.spawngroup = GetSp2();

.... and later

                                        QTriggers::Instance().processEvent(&death_event);

I think there is plenty of info in my structure to generate an old-fashioned EventNPC call. But there is not enough info in the EventNPC call to replicate my processEvent. For example, some quests might advance when N mobs are killed out of a spawn group. (or out of a set of spawn groups).

These two issues are my major concern right now. The rest of the changes are isolated. Well I think there is another call made when the client zones in.

[KLS]

I've been thinking about this but don't have any great answers right now.

Anyway:
-I would create a separate parser implementation for your quest system. Piggybacking on existing systems is a bad idea because as you can see the internals are subject to pretty broad change.

-I think we need to look at how we pass information in a standard way (right now we have a ton of variables of different types which is kind of messy).

-You can get the event name from the event code we already pass so I'm not entirely sure what you're asking for there.

[jdoran]

KLS, Thanks for your reply.

I don't think a separate parser will help. The parser interface is insufficient. Now if the parser interface was extended, a separate parser would be fine. There just isn't enough information passed to methods like EventNPC().

I do not need the *Event* name. I need a package name, which is derived from the quest-id.

I also need a subroutine name, which is based off of a trigger-id. Triggers are objects that can cause a quest to advance. They may need to fire multiple times in some cases (collect-n, kill-n). But the trigger decides when its preconditions are met. These cannot be based off an event, since the same event (EVENT_MERIT_KILL for example) might occur multiple places in a quest.

I mentioned in my last message that quests are represented as a graph. Each node in the graph has a set of triggers that must all fire before the quest is allowed to advance. One possible trigger is a subquest. I don't have a list of trigger types handy, but some are {match, subquest, assign, give, kill}. So a trigger might be named subquest_13 (which means the 13th trigger of the quest, which happens to be a subquest).

I should take a short moment to highlight one oddball requirement: quests do not need to be generated on the server which later runs them. They can be generated off-line. They can be generated on a remote machine and sent via email, since a quest is a single XML document. This quest can be loaded onto a server without affecting any other quest. It can be removed at any point without harm. (Actually there is a bug I've been meaning to deal with, but it is minor: Quest-specific items may be in inventory, and these are not scrubbed when a quest is removed. However, they get removed from inventory upon zoning, but the item is still in the inventory table. I'll fix this once I get everything ported to the current code base.)

One objection I have to using an object-id for a package name is that a single object (such as an NPC) may be involved in more than one quest. I require each quest to be in its own namespace. This is to avoid collisions in subroutine names, which are based off of "trigger" names. A trigger name such as "subquest_13" is not guaranteed to be server-unique. Multiple quests may have a similarly named trigger. Consider that if NPC 100000 is involved with two separate quests, and each has a trigger named "subquest_13", there would be two Perl subroutines with the same name in the same namespace. A separate namespace solves this problem. (Why use names like subquest_13 which could collide?? The quests may be generated on a machine with no knowledge of what subroutine names are available). At one point the generator named the triggers "trigger_1", "trigger_2" etc. The word "trigger" was later replaced with the trigger type as a debugging aid.

The quest-ids are assigned when a quest is imported into a server. This number is server-unique, but not globally unique. Each quest does have a GUID assigned, but this is too cumbersome to be used in subroutine/package names. I mainly use it to prevent the same quest from being added multiple times, and to remove a quest based on the XML document. When a quest is loaded onto the server, it is assigned an id such as 500200. From that point on, the runtime code uses this quest-id. When an event (such as our MERIT_KILL) occurs, it is passed to each trigger which registered that event type. If the trigger fires, it would pass the quest-d (500200) and the subroutine name (kill_21) to the parser.

By the way, clarifying these points is very helpful to me, so please point out anything that isn't clear. I am thinking of writing this up and presenting the generator at a conference. I will probably consult these forum posts when it comes time to decide what material to discuss.

[KLS]

I'm sorry if it seems like I'm talking down to you (I'm not trying to) I'm just trying to get as much info as possible to help extend the interface in a way I would find acceptable. Maybe that I'm giving off that vibe is just in my head tho =p

Another question:

How did you accomplish the passing of extra info before?

[jdoran]

KLS, I'm not picking up any vibe. I'm happy to have this discussion, since it raises my hopes that someday some of this work can be shared. I don't want to find myself fixing merge errors anytime anyone touches origin/master.

I think my post of 9/28 has the information you are asking for. If I'm misunderstanding your question let me know. When you ask how I passed the extra info, I have two possible answers.

The first type of additional information would be the quest-id, subroutine name passed into EventNPC (et al.). I added two additional parameters to each call. This is a bit invasive, but I was in a hurry to put together a proof-of-concept demo. (As an aside I used the Cleric epic for this demo). My example above with EVENT_SLAY was taken from attack.cpp, and shows these two parameters added to existing code. When my new code sends an event to the parser, I fill in real values. An example:

                parser->EventNPC(EVENT_DEATH, deathEvent-> killer, deathEvent->init,
                        "", 0, getQuestID(), getSubroutine());

I'd like to make this clear: The above code comes from new code in a new source file (QTriggers.cpp is the current name). All calls to EventNPC in existing EQEmu code have 0 and "" as the last two parameters. Speaking of deathEvent...

The second type of additional information which you might be asking about is the event-specific data. Existing calls to EventNPC are passed sufficient parameters for the quest code to do its thing. My quest runtime needs more context data. This is not for the parser, but instead for my filtering code. In my 9/28 post I showed a QEventDeath structure being filled in and passed to the QTriggers object. This method keeps all of the data in once nice package, which the receiver is free to use or ignore. I dislike long parameter lists, because I lived through Windows 3. (Oh dear dog, what is the 15th parameter of this function again?)

[jdoran]

I've had some time to actually work on the code today, and have a couple of observations:

The parameter lists to routines like EventNPC are getting long, and the calls are not clear. For example:

parse->EventNPC(EVENT_HATE_LIST, owner->CastToNPC(), m, "0", 0);

The decision of whether the event should be associated with an NPC, player, item or spell is contained in the method call.

I wonder if it would be an improvement to have a central event handler which would make the calls to EventCommon based on a context object being passed in.

I was using a structure in my old code, but I think promoting it to a class might be worth it. I base this partly on observing that a lot of calls to the event system are using default parameters. Subclasses of this event context could have their own set of defaults.

If all of the parser calls to an event handler were replaced, there could be one central place where we could change event handling. If a new event is added which needs an extra value, the originator of the event could just call a new method to fill in this value and existing code wouldn't need to be changed.

The list of events is maintained in several locations. The parsers have their own id->string maps. Adding a new event type means updating several files.