Jump to content

  • Log In with Google      Sign In   
  • Create Account

Latest trends in procedural quest generation


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
11 replies to this topic

#1 Ergawy   Members   -  Reputation: 184

Like
1Likes
Like

Posted 26 September 2013 - 08:41 AM

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.



Sponsor:

#2 CulDeVu   Members   -  Reputation: 1001

Like
1Likes
Like

Posted 26 September 2013 - 01:55 PM

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/
I'm sorry about any spelling or grammar mistakes or any undue brevity, as I'm most likely typing on my phone :P

#3 Druzil   Members   -  Reputation: 627

Like
1Likes
Like

Posted 26 September 2013 - 04:37 PM

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



#4 wodinoneeye   Members   -  Reputation: 877

Like
1Likes
Like

Posted 26 September 2013 - 04:39 PM

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.


--------------------------------------------Ratings are Opinion, not Fact

#5 IADaveMark   Moderators   -  Reputation: 2532

Like
3Likes
Like

Posted 26 September 2013 - 11:05 PM

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

 

*sigh*


Dave Mark - President and Lead Designer of Intrinsic Algorithm LLC

Professional consultant on game AI, mathematical modeling, simulation modeling
Co-advisor of the GDC AI Summit
Co-founder of the AI Game Programmers Guild
Author of the book, Behavioral Mathematics for Game AI

Blogs I write:
IA News - What's happening at IA | IA on AI - AI news and notes | Post-Play'em - Observations on AI of games I play

"Reducing the world to mathematical equations!"

#6 wodinoneeye   Members   -  Reputation: 877

Like
1Likes
Like

Posted 27 September 2013 - 05:34 AM

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)


Edited by wodinoneeye, 27 September 2013 - 05:38 AM.

--------------------------------------------Ratings are Opinion, not Fact

#7 Ergawy   Members   -  Reputation: 184

Like
0Likes
Like

Posted 30 September 2013 - 08:57 AM

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



#8 Ergawy   Members   -  Reputation: 184

Like
0Likes
Like

Posted 30 September 2013 - 09:01 AM

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.



#9 Ergawy   Members   -  Reputation: 184

Like
0Likes
Like

Posted 30 September 2013 - 09:30 AM

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:



#10 wodinoneeye   Members   -  Reputation: 877

Like
0Likes
Like

Posted 08 October 2013 - 05:15 PM

 

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


Edited by wodinoneeye, 08 October 2013 - 05:26 PM.

--------------------------------------------Ratings are Opinion, not Fact

#11 AngleWyrm   Members   -  Reputation: 554

Like
1Likes
Like

Posted 08 October 2013 - 07:00 PM

Maybe generate something based on plots and literature. Someone once said (in a reeeely long book) that there's only ever been seven plots. Seems like NPCs often provide #3 "The Quest" and that's pretty much it.

  1. Overcoming the Monster: Hero learns of a great evil threatening the land, and sets out to destroy it.
  2. Rags to Riches: Surrounded by dark forces who suppress and ridicule him, the Hero slowly blossoms into a mature figure who ultimately gets riches, a kingdom, and the perfect mate.
  3. The Quest: Hero learns of a great MacGuffin that he desperately wants to find, and sets out to find it, often with companions.
  4. Voyage and Return: Hero heads off into a magic land with crazy rules, ultimately triumphs over the madness and returns home far more mature than when he set out.
  5. Comedy: Hero and Heroine are destined to get together, but a dark force is preventing them from doing so; the story conspires to make the dark force repent, and suddenly the Hero and Heroine are free to get together. This is part of a cascade of effects that shows everyone for who they really are, and allows two or more other relationships to correctly form.
  6. Tragedy: The flip side of the Overcoming the Monster plot. Our protagonist character is the Villain, but we get to watch him slowly spiral down into darkness before he's finally defeated, freeing the land from his evil influence.
  7. Rebirth: As with the Tragedy plot, but our protagonist manages to realize his error before it's too late, and does a Heel Face Turn to avoid inevitable defea

Edited by AngleWyrm, 08 October 2013 - 07:05 PM.

--"I'm not at home right now, but" = lights on, but no ones home

#12 wodinoneeye   Members   -  Reputation: 877

Like
0Likes
Like

Posted 12 October 2013 - 02:51 AM

 

Maybe generate something based on plots and literature. Someone once said (in a reeeely long book) that there's only ever been seven plots. Seems like NPCs often provide #3 "The Quest" and that's pretty much it.

  1. Overcoming the Monster: Hero learns of a great evil threatening the land, and sets out to destroy it.
  2. Rags to Riches: Surrounded by dark forces who suppress and ridicule him, the Hero slowly blossoms into a mature figure who ultimately gets riches, a kingdom, and the perfect mate.
  3. The Quest: Hero learns of a great MacGuffin that he desperately wants to find, and sets out to find it, often with companions.
  4. Voyage and Return: Hero heads off into a magic land with crazy rules, ultimately triumphs over the madness and returns home far more mature than when he set out.
  5. Comedy: Hero and Heroine are destined to get together, but a dark force is preventing them from doing so; the story conspires to make the dark force repent, and suddenly the Hero and Heroine are free to get together. This is part of a cascade of effects that shows everyone for who they really are, and allows two or more other relationships to correctly form.
  6. Tragedy: The flip side of the Overcoming the Monster plot. Our protagonist character is the Villain, but we get to watch him slowly spiral down into darkness before he's finally defeated, freeing the land from his evil influence.
  7. Rebirth: As with the Tragedy plot, but our protagonist manages to realize his error before it's too late, and does a Heel Face Turn to avoid inevitable defea

 

defined by conflict and opposition

 

man vs man

man vs nature/environment

man vs society

man vs himself

man vs fate /god(supernatural)

 

 

also they often are synthesis of multipl plot types in the same story

 

 

you could probably templatize and add sequential progression  (compound quest) for the story the player has to play thru

 

making sure the different substuituted elements are related to each other and the proper props are placed and act correctly ,  overall themes etc....

---

 

Ive been thinking about how this would be done (for years)  and have come to the conclusion that you still have alot of hand crafting, but now it would be of hierarchical templates   (and a fairly irregular tree of options you chose from/thru).    Again liklely some kind of matching code would be required to check if a candidate was applicable to the players situation and then fitting logic to select a valid set of substitution elements.      

 

So alot of filtering and if-this-then-that  code  and classifications of useable elements/props/behaviors/etc..  but at least now it could be reused instead of precanned crafting of largely unique scripting for a particular even in a particular game.

 

Reuse across multiple games  (generic patterns with game specific elements reapplied)  to amortize the cost of the complex (expensive) system

 

My 'big' idea is for (in MMORPGs or modding Solo games) Player Creation to supply ALOT more templates and elements  to substiture  (a whole horrendous system in itself because of the huge number of near idiot proof tiools required)).

 


Edited by wodinoneeye, 12 October 2013 - 03:05 AM.

--------------------------------------------Ratings are Opinion, not Fact




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS