So I just read this very interesting blog and I thought I would share 

On the 7th day, [insert preferred deity here] became lazy and said, “Nature, design thyself.”

There is an undeniable link between math and nature.  I could start boring you with talk of the Mandlebrot set, Voronoi diagrams, Delaunay triangulations, the Golden Ratio, and so forth, but here is a cool video that does the job better than my words could:

Whether it is nature that defines math or math that defines nature, we will leave those questions to the burger flippers…oh, I mean philosophy majors.   For now, all we need to know is that this link, as programmers and artists, benefits us dramatically.  It means that we can more easily abstract the laws of nature into code, and thus more easily simulate and create nature in a virtual environment.

But procedural generation applies to much more than just nature, it is also perfectly capable of generating non-organic, “man-made” structures.  In fact, it might surprise some people that man-made structures exhibit many organic properties, and are often intentionally designed to mimic nature.  The columns in Ancient Egypt, modeled after papyrus and palm plants, are one simple example of this.  A city map, in some rural areas, often looks similar to the vein layouts on certain plant leafs.  Even in areas not directly tied to nature, structures exhibit mathematical symmetries and designs that can easily be expressed by simple logic.

So, those of you who do not already know might be asking, “What is procedural generation?”  It is, as the name implies, the process of generating things procedurally (or, via code).  The opposite approach would be manual generation, or “doing it by hand.”  As far as it is related to game design, these things are better known as “assets” or “content.”  These assets can literally consist of anything – textures, meshes, animations, scripts, behaviors, parameters, you name it.   In terms of the types of content that can be produced, the sky is the theoretical limit: humanoids, buildings, cities, terrain, plants (flora), animals/creatures (fauna), clothing, vehicles, and so forth.  In some cases, game designers will expose some of the procedural generation abilities of their engine to the end-users, either in-game or in an external editor.  This leads to user-generated content (henceforth: UGC).  In some cases, the mechanisms used to achieve this can be very complex (as with some map-editors), or they can be very simple (masked as elements of gameplay, as in Spore).

So, in less words, procedural generation (henceforth: PG) takes much of the work that your artists and level designers would have to do by hand, and automates it.  Sounds awesome right?  Well, it can be, if it is done right.  But many people in the industry frown upon PG (and UGC, for that matter).  Sometimes, it is with good reason, and sometimes, it is just because they don’t really understand what PG and UGC are capable of and how they can easily be abused.  I would like to clear up a few of those points (I will call them “myths,” but feel free to disagree).  Mind you, all of the “myths” below have been said to me before, often multiple times.

Myth: PG/UGC leads to watered-down, random, sand-boxy gameplay

Many people will claim that PG is a lazy replacement for real, intentional, hand-crafted game design.  And it often is.  In The Elder Scrolls II: Daggerfall, all of the towns, people, dungeons, quests, and so forth, were procedurally (or randomly) generated.  On one hand, this led to a huge game world, far beyond the size of anything that had been made before it.  On the other hand, the towns, people, dungeons, and so forth all had (in my opinion) incredibly boring design, because they all lacked the hand-crafted touch that could have made each character and location unique and interesting.  In some cases, PG gets the job done adequately, like in Rogue-esque games such as Diablo, which are basically all about grinding.

But these are not the best examples, because they were around before the term “procedural generation” was being used a lot.  To date, the reigning champion of PG (and UGC) examples is Spore…unfortunately.  [Side note: I was contacted by someone at EA many years ago that asked if I wanted to work on Spore, after they saw some of my work with PG -  I did not take the job though.]  Don’t get me wrong, it is an interesting game in its own right, but it failed to properly represent the capabilities of PG/UGC on many levels, and caused many people to get the wrong ideas about PG/UGC.  Before I insult anyone that worked on it, let me say that they did a remarkable job given their constraints.  The problem with Spore is that it is not so much of a game as a sandbox.  And even as a sandbox, it wears thin pretty quickly.  Its main problem is that it does not really use PG or UGC to its advantage – the assets you generate do not impact gameplay very dramatically or meaningfully.  Some aspects of it were done very well, but at times it felt a little bit too much like Mr. Potato Head, where the procedural generation was simply pasting together prefabricated assets.

UGC is an issue on its own.  It can be difficult to monitor UGC, and in some cases it can detract from the suspension of disbelief (especially when juvenile humor is involved).  A strong brand and design can also be easily destroyed by UGC.  That said, UGC can be given constraints that make it an effective tool for growing your game’s content while not destroying its image.  The best way to do this (in my opinion) is make the design process for UGC directly affect gameplay.  So, for example, if users are building a castle in an RTS game, it will survive if it is properly designed to defend its people, and it will be destroyed if it is a pile of garbage.  People can also police/moderate themselves, which is also sometimes an effective mechanism.

As for PG, I would argue that it is almost always a good thing, if it is done right.  PG should be used to help the designers and artists, and get rid of monotonous work.  If it can’t be properly automated, then it should not be.

Myth: Procedural Generation == Random Generation

Random Generation is a subset of Procedural Generation, just as squares are a subset of rectangles.  Procedural Generation does not have to be, in any way, random.  Explicitly provided parameters can be used to adjust every aspect of procedural content (for example, the radius of a tree trunk or the number of buildings in a city).  Random generation can often work against designers, and they will find themselves regenerating assets constantly to get them to “look right.”  Even “random” assets can be given a consistent look by using a fixed number for the seed in the random function (versus, say, basing the seed on the system timer).

Myth: Procedural Generation cannot produce assets of type X

Anything that you can logically describe can be procedurally generated.  Some things are much harder than others.  One of the hardest things, in my opinion, is procedural animation of creatures and humanoids.  It has been done successfully, to varying degrees, depending on how you define success.  But I still do not think anyone has yet created creatures that use true AI (without any preset behaviors or motions) to navigate through complex environments using all of their limbs (for example, jumping and grabbing onto ledges, and so forth).  I’m working on that one, I’ll get back to you on it….;)

Myth: Procedural Generation cannot produce stylized characters or assets

Wrong.  Spore is very stylized, although, as I mentioned before, it is, at times, a bit too cut-and-paste of pre-fab assets.  As stated before, procedural generation can produce anything that can be logically described, which is…anything.  As humans, we like to think that we have some kind of special “creativity” gene that computers can never replicate, but our notion of “creativity” is clouded and vague.  Creativity is actually very simple – it is simply the process of absorbing all that we have learned to produce something “new” (not necessarily unique) that has intentional meaning.  To clarify, even if a computer randomly threw blobs on the screen, and ithappened to look like a butterfly, that is not creativity, it is coincidence.  Computers can, and have, already produced creative works of art, without explicitly being told how to do so.  That said, at this point in time it is not really the job of PG to be “creative” – PG is only supposed to help artists and designers express their creativity faster and more efficiently.  Artists should be able to tweak almost every attribute of a PG object to style it according to their vision.

Myth: Procedural Generation is a lot of work, and often not worth the effort

It is true that procedural generation is more work than it is worth, if you are looking at one title.  But if you are reusing your work, PG is the goose that lays golden eggs.  Once it is built, it is built, and there is no need to reinvent the wheel, only fine tune it.  When I look at many modern games, I cannot help but think what a shame it is that so many artist hours are wasted on what are essentially identical assets.  Even worse, all of the work that goes into assets that never get past the cutting floor – PG can at least let artists experiment rapidly with prototypes, before they go in and fine-tune things manually.

Myth: Procedural Generation is too slow to be used in commercial games

Some consoles might be too limited to use PG with (in terms of memory), during runtime.  That part is true.  But you can do PG offline and benefit from it as well.  However, if it is done right, PG can be a lot faster than loading dense meshes and texture maps from disk (That is, generating data in memory, even with a bit of CPU work involved, has the potential to work faster than a hard disk or DVD can load).  Often times, it will be too slow to generate assets every frame (as with procedural textures), but it can be done once and then cached in many cases.

Myth: Procedural Generation will never go mainstream

I would argue that, as a force of nature, it will have to.  Budgets for games are simply growing too big.  People simply cannot produce content fast enough for consumers.  There is not enough room for risk and innovation.

Myth: Procedural Generation will replace artists/level designers

PG will empower artists and level designers, but it will never replace them until we can build an AI that can do everything an artist or level designer can (no small task).  At that point, we would probably have AI that would mostly replace programmers as well.  Whether or not that is possible, feel free to debate, but I think it is – however, not for a very, very long time from now.  Regardless, the goal is not to replace people, but allow them express their vision easily without worrying about the tedious details.  If you define procedural generation as taking a high-level command to create/modify low-level data (a mesh, texture, etc), artists already use procedural generation every single day.  A brush stroke in Photoshop takes a click and procedurally turns it into a set of pixels (or bytes) to mimic a brush stroke.   A tween procedurally creates frames of animation between the parent key frames, freeing the artist of a time-consuming task.  I could go on…

Conclusion

In short, I think that procedural generation has a bright future, but we still have yet to realize a fraction of its potential.  Progress has been slow for two reasons, in my opinion: the misconceptions listed above, and the generally low appetite for risk within the industry.  I think that PG has the potential to bring us back to the golden era of the 80s and early 90s, when “AAA” games were made by small teams.  I have much more to write on this topic but I need to leave room for my next articles.  Please join me next time for a more interesting and in-depth discussion on PG and UGC.

http://altdevblogaday.org/2011/03/23/procedural-generation-and-user-generated-content-part-i-intro-myths-and-facts/

In my last article, I gave a brief overview of Procedural Generation (PG) and User-Generated Content (UGC).  In this article, I have decided to discuss something that gets surprisingly little attention: procedural generation of storylines/plot/quests/dialog and so forth.

Procedural generation of storylines is very common, whether or not we realize it.  Sadly, most of these consist of fetch object X to receive reward Y or kill monster A to proceed to area B.  We use these kind of mechanisms all the time, but we have a hard time pinning down what is “wrong” with them.

I think that games stand as their own medium, but that does not mean we cannot learn from other types of media.  Imagine that you are reading a book.  Throughout the book, the character kills monsters, grabs loot, travels through different areas, and talks to different people.  This describes many books, but it is a superficial aspect of them.

Bad books tend towards this superficial aspect.  Good books have something going on under the surface.  Everything that happensmakes sense, but at the same time, is not entirely predictable.  There are a million ways you can break it all down, but I am going to start from the top and work downwards.  Note that I have no formal education in writing, so I am doing my best to describe patterns as I have seen them.  I will scatter some examples from popular stories throughout.

At the top level, you have:

• Characters (Actors)
• Items (Props)
• Environments (Scenes)

CONTEXT

Now, let’s dig deeper.  Every character, item, and environment has a timeline that dictates their qualities, abilities, and motivations, from past to future.  We will call this the context.

• Characters (Actors)
  • Beginning: Character is born, genetic makeup is determined.  Also notable are the family and environment the character is born into. (Hercules was the bastard child of Zeus and Alcmene, Zeus’s real wife Hera was pissed.)
  • Past: Character’s back-story, determine’s their learned behavior.  In combination with their genetic makeup, this determines their personality and motivations. (Jean Valjean was born into hardship, learned the ways of a thief, and grew to value morality over the law.)
  • Present: Character’s current state, location, conflicts, tasks, etc. (Horton’s acute hearing tasks him with helping a village of tiny people.)
  • Future: potential of character, fulfillment of a prophecy, etc. (Harry Potter was viewed as one of the few people who could defeat Voldemort.)
• Items (Props)
  • Beginning: how the item came to be; where its resources were collected from, how it was crafted, etc. (The Ring was forged in the fires of Mount Doom.)
  • Past: who owned the item, what historical significance the item has, etc. (The Ring was lost in a river and eventually found its way to Gollum and corrupted his figure and morals.)
  • Present: where the item currently is, its current state (broken, hidden, scattered across the land, etc). (Frodo carries the Ring, Sauron is looking for it.)
  • Future: where must the item go? (The Ring must be taken to Mount Doom and destroyed.)
• Environments (Scenes)
  • Beginning: How was the land formed, how was the structure built, what inherent qualities does the land have, etc.
  • Past: how did the environment change over time, what happened in the area, etc.
  • Present: the present state of the environment, what events are occurring.
  • Future: what will happen to the environment (The Tree of Souls will be destroyed unless the Navi can stop the humans.)

All of these things set the context – they explain why things happened, what is happening, and what might happen.  But the context alone does not make a story, in fact it only introduces what we need to know to understand the interactions that will occur throughout the story.

INTERACTIONS

Given the context of the characters, items, and environments, how will things play out?  These interactions are a fundamental part of the progression of the story, but on their own they do not necessarily make for an interesting story.

Lets look at all of these permutations of interactions – below are just a few examples, I am sure you can think up more:

• Character-Character: Characters talk to each other, lie, fall in love, (attempt to) assassinate each other, vow for revenge against one another, transport one another (hostages, bodyguards…), etc.
• Character-Item: use items to empower themselves (i.e. drink a potion) or achieve a goal (i.e. using a key to unlock a door), or even kill themselves (Juliet uses Romeo’s dagger to kill herself.)
• Character-Item-Character: characters give an item to empower or curse another character, they use items on one-another, etc.(The Witch gives Snow White a poisoned apple.)
• Character-Environment: Characters must travel to their destination, seek haven, find a place to eat, etc. (Harold and Kumar seek out White Castle.)
• Character-Environment-Item: Characters must seek out hidden items from environments, collect items scattered across different environments, use an item to proceed to a new environment, etc.

Interactions will create a story, but not necessarily an interesting one, as stated earlier.  You need to have a clear goal and progression in order to derive meaning.

MEANING

Meaning is all of those “intangible” things you learned about at some point: theme, climax / turning point, epiphany, character progression, and so forth.  Instinctively, we might think that it is impossible to put effective meaning into games, unless they are very linear in nature like books and movies.  I would argue that it is not impossible, just hard.  If you give your users free reign and make a total sandbox game, chances are they won’t produce a very effective storyline.

This “problem” has been solved, and it might surprise you how old the solution is.

Dungeons and Dragons.  I must shamefully (proudly?) admit that I have never played the board game.  Regardless, I understand the mechanics behind it.

I am sure there have been plenty of D&D games where players kind of just mess around and do what they want.  Interestingly, these have probably been the least enjoyable games for everyone.

When players follow a structure, and more importantly, play a role, they tend to have much more interesting sessions, because their games have meaning.

Roleplaying has become a bit of a misnomer.  We are very, very rarely playing a role in modern video games.  We are controlling a person who has a context and is capable of many different interactions, but they are rarely confined to a role. This is why most of the characters we play feel like they have no personality – because we aren’t really confined to one (I’m looking at you, Commander Shepherd).

I am as much against artificial constraints as the next guy, but I think we can easily introduce motivations for people to play their role.  We can do this without having to pretend, but instead using the game’s inherent mechanics.

It all comes back to meaning.  I can go slay the monster, collect the loot, and return for another quest, but what does it all mean? You cannot have meaning without persistence.  What impact does my action have on the world, and what is my incentive to perform this action?  How can we effectively insert meaning into nonlinear games?

STORY ELEMENTS AS GAME MECHANICS

In order to have any semblance of structure, we must play a role.  How do we get players to fulfill roles without placing artificial constraints on them? We have to make qualities of the role a tangible aspect of gameplay, and reward players for following their roles and not reward (or punish) them for stepping out of their role or diluting their role.  Given our character’s context, we must determine their motivations. We must also determine how their interactions fulfill or conflict with their motivations.

How do we turn this into something tangible?  There are many ways, but I will point to one obvious way: the meter.  If you ever played The Sims, this game used a system of meters to determine the state of your character.  They had a hunger meter, a bathroom meter, a fatigue meter, and various meters representing their emotional needs.  If their needs were met, they would function properly and succeed in the various aspects of their life (career, relationships, etc.).  In theory, you could do whatever you wanted with your Sims, but the game encouraged you to try and fulfill the needs of your Sim.

Imagine that in your roleplaying game, a character has a meter (or some other tangible entity) that measures how well you have fulfilled their ambitions, goals, and so forth.  Perhaps this meter affects other areas of gameplay (i.e. how effective your character is in combat), or perhaps it has direct effects of its own.  If your character is a thief, perhaps you must satisfy their urge to steal, and you must avoid combat because it makes your character uncomfortable (they prefer to sneak around).  In order to construct an effective storyline, you need a number of roles to be played.

• The Hero(es)
• Neutral Characters
• The Villain(s)

Additionally, each role should have a fairly well-defined subset of abilities.  Characters that can do everything and have no weaknesses are boring characters.  This is why we have archetypes in stories.  Each character is a piece of the puzzle and they all use their strengths to achieve a goal while their weaknesses are exploited by the villain or other circumstances.  Character archetypes are popular in story-telling, here is a fairly comprehensive list of them:

http://www.listology.com/list/character-archetypes

EMERGENT STORYLINES

We can encourage characters to go down certain paths and motivate them to play their roles, but how do we create a game engine that constructs meaningful storylines on its own?  It is actually surprisingly simple, and only involves a little bit of AI work.  I won’t delve into the technical details, but if you understand propositional logic, backwards chaining, expert systems, and how languages like Prolog work, you probably have a good idea of how to implement systems like this.  I will layout the basic functionality of this system below:

• You play a character who has a set of motivations that you try to fulfill.
• The game controls a number of NPCs via AI.  Each NPC has its own set of motivations.
• One or more NPCs has motivations that are in conflict with yours.

Let’s take a look at a simple example.  Imagine that we present the following facts into our system.

• There is a playing field with a limited amount of gold and three characters, and random walls everywhere.
• One player can only see another if a wall is not blocking their line of site.
• You control character A (the “hero”), whose motivations are to abide by the law and collect as much gold in your stash as possible.
• The computer controls character B (the “villain”), whose motivation is to collect as much gold in their stash as possible.
• The computer also controls character C (the “guard”), whose motivation is to enforce the law and prevent crime.
• The law states that it is illegal to kill or steal, and the punishment for either one is death.
• Dead people cannot perform any actions (namely, they cannot collect gold).
• If a crime is not seen, a punishment cannot be enforced.

Left to its own motivations, the villain might try to kill you (the hero), even though it was never explicitly instructed to, because out of all the paths it can take, killing you might yield the maximum amount of gold (provided it can do so without being seen by the guard).  Or, if the guard is always too close to the hero, the villain might just try to steal from the hero’s stash instead.  On the other hand, you will probably not kill or steal, because the game mechanics will find some way of punishing you for defying your given role, whether or not the guard is watching.  Also, interestingly, the guard will probably follow around the villain more closely, because it knows that the villain is more likely to break the law and it is motivated to prevent crime.

This is a very simple example, but the important thing to note here is that there are no explicitly-defined scenarios, everything isimplicit based on the circumstances.  Personally, I think that explicitly-defined plots are bad for gameplay.  They might be able to create a better, more powerful storyline, but they are bad for gameplay because they tend to force players into linear scenarios, thus limiting replayability, increasing predictability, and diminishing the feeling of a truly interactive environment.

So, what do you need to form a coherent, emergent storyline?

• Characters, Items, and Environments (this should be a given…)
• Context (properties and history of each entity)
• Interactions (each character has a given set of actions they can perform which are probably partially dictated by what items they posses and their current environment)
• Meaning (motivations to perform actions that make sense, clear end-goals)
• Well defined roles
• Abstraction of each of the former for the purposes of AI and gameplay mechanisms – most things should be able to be measured by a number or boolean/fuzzy logic.

Tying it all together: in every instance/turn, characters weigh the facts (context), the state of their present environment, and their motivations against a list of possible actions.  They then select the action with the highest predicted return towards their motivations and the system is updated with the new data.  Repeat as necessary.

MYSTERY

Good storylines have mystery and plot twists, even if they are not explicitly classified in the “mystery” genre. It is fairly easy to incorporate these elements meaningfully into a game.  For example, lets take another set of facts from a hypothetical game (here, the “?” represents facts that are not immediately apparent to the player or AI):

• A farmer has the motivation to keep his sheep alive and has some money.
• You play a mercenary that will kill anything for money.
• Dragons kill sheep.
• ?
• A farmer’s sheep are being killed.

With a bit of backwards chaining, the farmer will probably deduce that he can keep his sheep alive by paying you (the mercenary) to kill the dragon that is killing his sheep.  So, you camp out, waiting for the dragon to attack.  Instead, you see some wolves attacking the sheep (this fact is represented by the “?” – and represents part of the mystery/plot twist).  Again, this is a very simple scenario, but imagine the possibilities when you set the stage with a myriad of characters, items, environments, and context with high potential for mystery, conflict, and other story-telling mechanisms.

DIALOG

So, how might you handle dialog in a non-linear game with emergent storylines?  Well, lets keep it simple for now and imagine that everything is text (no recorded speech).   Creating an AI that is able to fully understand and parse every word you type is probably beyond the scope of most games, but there is a simpler alternative: sentence fragments.  Imagine that you are able to construct your dialog from a series of words or sentence fragments.  Here is one example: [promise to][kill][1][dragon][in return for][20][gold coins].  It might seem difficult to interpret a series of fragments like this, but we have been doing it since the dawn of computer languages.

If you have ever written a compiler, this is exactly what you would need to handle something like this.  So, you have a series of sentence fragments or words, which are basically the equivalent of tokens/keywords/functions in a compiler.  Then you have names of people, places, and items, which are the equivalent of IDs or variables in a compiler.  You could parse any string of sentence fragments and validate it against a Context-Free Grammar (which is basically a grammar check).  Upon parsing and interpreting your sentence, the AI adds it its database of facts or propositions, and then acts on its new set of data.

I cannot recall a game that has yet implemented something like this to an effective degree.  It would lend itself to many interesting possibilities though.  The AI might try and manipulate your character’s motivations by lying to you, or similarly you could attempt to manipulate the AI by asking NPCs to do tasks for you (i.e. distract a male guard by telling a female NPC that the guard thinks they are attractive, thus prompting the NPC to flirt with the guard).  Even beyond manipulation, it could be the infrastructure that creates a real, breathing world in which characters interact with one another in a totally improvised, but believable, manner.

In a greater scope, it might sound like a pipe-dream, but I think that if we attempt to implement simple game mechanics systems like this are totally doable.

There is room for a lot more discussion in this area, but I should probably cut it short at some point. I apologize if I lack clarity but feel free to ask me anything.  Mostly, I just want to get the gears turning.  What do you think? Are systems like this a good idea or doomed for failure? 

http://altdevblogaday.org/2011/04/06/procedural-generation-and-user-generated-content-part-ii-storylines-ai-and-emergent-gameplay/

Posting so I can read this properly when I have more time. Seems like an interesting article(s).

booked mark

well I thought it was interesting...

Great article. I liked his conclusions on the nature of PG - that it isn't a magic wand but can allow the player to experience a unique story. Minecraft does this best. And PG of environments will have to happen more as budgets increase.

An interesting read. I've been hoping for a few years now I guess that procedural generation would become more common. It's doesn't - and shouldn't - make everything 'generic', but it has great potential to make developing bigger games cheaper, quicker, and overall, more efficient. Also, I like RPGs but I hate scripted quests that are the same every time and especially if they feel pretty 'generic' - I'm looking at you, Oblivion (luckily Skyrim seems to be doing a lot better job here).