Hi guys,

Currently I am working on PCG system to generate dynamic quests. Till now I have found some papers and articles that talk about the subject. The most important in my opinion is Ian Parberry's and Jonathon Doran's paper "A Prototype Quest Generator Based on a Structural Analysis of Quests from Four MMORPGs" (here: http://larc.unt.edu/ian/pubs/pcg2011.pdf). It mainly analyses about the structure shared in most MMORPGs and uses that analysis to create a prototype quest generator. I have made an initial implementation of the ideas included in the paper.

But the problem with most (if not all) of the results I found so far is that they didn't manage to provide a good solution to the narrative and plot part of the quests generated. I mean, you can generate random quests with whatever length and complexity of actions you like. BUT making some kind of logical sequencing or consistency between the quests is not that good.

Unfortunately the idea of procedurally generated quests is not that clear or polished in my mind yet. So I hope through this thread to start a discussion about the latest trends in random/psuedorandom generation of quests.

Any contributions such as research papers, articles, tools or engines that help in defining the idea of generating good-quality quests will be very helpful.

Just BTW I have no authority in this subject. I've never any papers, and I've gotten into this stuff, but here's a link to an article I read a while ago. It talks about generating interesting questlines by reference that is used in Malevolence: The Sword of Ahkranox

http://www.altdevblogaday.com/2012/04/22/kevin-bacon-in-video-gaming/

There are a few articles here that might be of interest. http://www.gamesbyangelina.org/ Maybe the Jul 20 one?

Important - procedurally generated to use templates of real patterns (hierarchies of them actually).

Things (including Quests) have to be generated with quite a bit of cohesiveness and interelated detail being precanned (even if they are just archetype specification) will do that.

The problem with a freely created 'random' generation is all the rules that must be observed for something to be 'proper' and 'correct' (use creating realistic terrain as an example...). You prefer to minimize the rule testing in-real-time as that can result in discard and retry looping (and the more complex the rules are the more that will happen). So a moderate amount of prebuilding of 'proper patterns' should be used where alot of that is pre-resolved.

Remember you can randomly pick from a multitude these 'templates/patterns' and recombine them sufficiently and substiture many 'independant' factors/details to resolve into the useable Quest instance (and have them be sufficiently unique).

As it is, having the quest adapt to the current game situation (always a good thing) will require more than a little scripted logic and the (hierarchical) templates themseles would have their own local logics (and leeway) to adjust themselves and their subcomponents.

Aethetics for situational props is another aspect which pre-canning assemblages of prop objects can save alot of runtime processing (or just poor obviously random looking generation results ). Example - compose furniture in a room to match door/window placement -- ever try to script that logic?

And nothing says you cant still script alot of such, but run it offline where it wont stress the games processing load. Select from a half dozen precanned patterns , semi-randomly place varying prop objects of the needed types in the spots, place plot relevant objects and you have a sufficienly varying situation. Same for a boss fight arena, or a generic city street or the tavern where the quest giver hangs out.

Ugh. I wish I could tell you about what I'm working on.

*sigh*

Oh I can take it one further with 'Player Created Assets' (particularly for MMORPGs who constantly need lots of new content)

to use players to create the templates/patterns and many of the props to multiply the options available to a games auto-generator..

The sticking point is the tools, but the cost of game assets are huge and that will get worse the more complex they are (its why we are in a rut with so many games basicly being the same as old ones and the playthru hours continue to drop)

Oh and I didnt mention seed-maps where themes and local prevalences are defined to guide the auto-generator (and how the map might mutate as influence maps of entities reacting to player actions ie- player cleans out an area and the local spawns shift and something else moves in to take up the vacuum (Farcry 3 didnt qite do this because there was no backpressure from the opponent factions to 'take back' their lost territory)

Ugh. I wish I could tell you about what I'm working on.

*sigh*

I wish you tell me so that I can cheat from you :D

Important - procedurally generated to use templates of real patterns (hierarchies of them actually).

Things (including Quests) have to be generated with quite a bit of cohesiveness and interelated detail being precanned (even if they are just archetype specification) will do that.

The problem with a freely created 'random' generation is all the rules that must be observed for something to be 'proper' and 'correct' (use creating realistic terrain as an example...). You prefer to minimize the rule testing in-real-time as that can result in discard and retry looping (and the more complex the rules are the more that will happen). So a moderate amount of prebuilding of 'proper patterns' should be used where alot of that is pre-resolved.

Remember you can randomly pick from a multitude these 'templates/patterns' and recombine them sufficiently and substiture many 'independant' factors/details to resolve into the useable Quest instance (and have them be sufficiently unique).

As it is, having the quest adapt to the current game situation (always a good thing) will require more than a little scripted logic and the (hierarchical) templates themseles would have their own local logics (and leeway) to adjust themselves and their subcomponents.

Aethetics for situational props is another aspect which pre-canning assemblages of prop objects can save alot of runtime processing (or just poor obviously random looking generation results ). Example - compose furniture in a room to match door/window placement -- ever try to script that logic?

And nothing says you cant still script alot of such, but run it offline where it wont stress the games processing load. Select from a half dozen precanned patterns , semi-randomly place varying prop objects of the needed types in the spots, place plot relevant objects and you have a sufficienly varying situation. Same for a boss fight arena, or a generic city street or the tavern where the quest giver hangs out.

Semi-random is interesting too. I think that quest generation can't be done all programmatically or randomly. The problem of creating a meaningful story-line or plot remains, as far as I know, an unsolved challenge.

A great study that my be of benefit to the poeple interested in the subject

http://escholarship.org/uc/item/004129jn?query=The%20Grail%20Framework:

Important - procedurally generated to use templates of real patterns (hierarchies of them actually).

...

quest giver hangs out.

Semi-random is interesting too. I think that quest generation can't be done all programmatically or randomly. The problem of creating a meaningful story-line or plot remains, as far as I know, an unsolved challenge.

Some elements are substituteable (possibly with a little 'fitting' scripting to adapt to the particular instance)

Other elements are 'variable', such as coefficient attributes which control object behaviors (which actions/tactics they 'prefer')

A big future step is more sophisticated NPC AI which can adapt to varying environmensts/situations (including societal roles) to act appropriately.

Preprocessing to 'organicly' mutate into a cohesive/valid situation would be done to 'set the stage' of the quest drama

All of the above of course requires being to handle the diverse game environment --- the handling code required probably increases by the square of the complexity and the processing by the cube (or worse) even if there is ALOT of generaization/templating of common interactions.

Plots and story-lines could be similarly handled in this level/extensiveness of programming. They can be templated and hierarchicalized and 'fitted' much the same way. Theme factors would just be inputs (for code able to handle them and adjust/mutate to/with them.

This aspect means implementing societal roles/behaviors/relations and complex inter-object interactions (adding how many more magnitudes of coding ??)

Generalization means that much of this 'code/logic' could be reuseable if done systematically (thus saving on REINVENTING "not just the wheel but the whole car" ). I have hopes that eventually these risk-averse game companies will eventually move on/be dragged on to using things like this (preferably before we are all dead)

----

BTW the 'plot' in such a world system operating in the biggest way mentioned above comes from not just the Worlds NPCs/factions/polical entities "moving in their orbits", but from the players' actions within that world (its just more inputs...). The horrifying problem is prebalancing/self-balancing such a system (grow organicly again...). For games like MMORGP I would allow for (hopefully infrequent) MANUAL GM macro level adjustments/interventions to correct for pendulum swings which otherwise would unbalance and destroy the world (and you KNOW that players will be using their skills/effort to attempt that)

So add a final layer of human intervention when possible.

BTW alot of those 'templates' still originate as hand crafted (to make them cohesive) even if they do have elements of substitutions systematically built in