I went to a symposium on procedural content at UCSC the other day. Here are my revised notes, I didn't stay the whole way through all of them, but combined with the links you should get a pretty accurate picture:
Evolving levels for Super Mario Bros.
http://julian.togelius.com/Pedersen2009Modeling.pdfThis research attempted a player experience model based on Infinite Mario Bros. to take data from hundreds of players on the Internet and use their responses to questionnaires to evolve a neural network AI that correlates the level generation process to desired parameters(the ones used were fun, boredom, anxiety, unpredictability, challenge, and frustration).
They achieved a high prediction rate for some of the parameters(notably frustration) but not all. Additionally, some interesting correlations were found through this process; long jumps, for example, were correlated with unpredictability.
The process involved generating first a level that attempted to predict questionnaire responses, and then two levels that are very high and very low in a user-selected parameter, and then a second questionnaire to follow up on the generated levels and tune the process.
Evolving Game Rules
http://julian.togelius.com/Togelius2008An.pdfIn this research a matrix representation of rules for object collision, and movement absent collision, was used to drive a Pac-Man like maze game.
Movement logic is a choice of none, random short, random long, clockwise, counterclockwise, chase, flee.
Effects of collisions include nothing, death, teleport, and score effects(add/subtract)
Time limits and score goals vary
There are four colors, Red, Green, Blue, and player agent(Cyan) each having a unique relationship of interactions with each other.
The fitness function is based on learning progress from Raph Koster's fun=learning theory; fitness over time is associated to some curve. In the ideal curve, the player improves their score linearly with each iteration.
Outcome: It works, but mostly in fine tuning situations. Possible evolutions include the use of Amazon-like collaborative filtering, or adapting it to compositional content creation(evaluating the desirability of each item of content and composing new items from previous data)
The author's observation of this approach is that having a big dataset is the key factor: with enough player data you can avoid getting stuck at local optima. (My own note: an underlying problem with recycling player data into the generator is that it depends on core assumptions about the generation process; if the generation strategy is weak, the entire process is limited.)
Experience Management through Narrative Content Generation
http://www.cc.gatech.edu/~riedl/Goal: Computational models of narrative reasoning and generation
Specifically: Automatic creation of meaningful sequences of events; large-scale, customized storytelling for all applications(entertainment, training, education)
Not about total replacement, but assistance: how far can we get with AI?
Four categories: Authoring, On-Demand Narrative Generation, Experience Management, Game Engine
Riedl determined that a feedback loop is necessary; the user changes their process over time too!
Two basic properties of story were attacked: Logical causal progression, character believability (more complex stuff eschewed for now)
Representation used: Partially ordered plans; AI planning algorithm finds a sound sequence of operations that manipulates the world state into a goal situation.
Planning turns out to be an imperfect model as-is: a naive planner will find the shortest series of steps, short-circuiting the natural storytelling process.
The new model: Intent-Driven Partial Order Causal Link planner
Logical causal intention + reasoning about character intentions
Future developments: Player modeling?
Real-time experience management: manipulating the world so that it conforms to some set of attributes
Model is visualized as a state space wherein the player and the system manipulates the trajectory of the state space.
There are three categories of behavior in real-time experience management: constituent(expected), consistent(roughly expected, with temporary detours from the trajectory) and exceptional(previous trajectory is unreachable).
Example: Player kills the big bad wolf at the outset of Little Red Riding Hood
Solution: Find all possible branch points and generate their results in advance so that the planner can work regardless of what the player does.
(At this point I ducked out because I was starving)
Kate Compton: Using Procedural Generation for Human-Computer Collaboration
(Kate worked on Spore.)
www.galaxykate.comKate opened by pointing out that infinite worlds are the most common application of procedural techniques today, and we have a toolbox of autonomous methods to use them in real-time:
Top-down generation: l-trees, grammars, function-based
Post-generation optimizations: hill-climbing, genetic algorithms
No human oversight
No interaction
The alternate approach is human-computer collaboration. Infinite content is perceived as valueless; human creations are perceived as valuable.
Fitness functions are hard to work with: Slow+complex to evaluate and dependent on how much you simulate, and difficult-to-define variables that vary across the playerbase.
An existing use of the player as fitness function evaluator is in dynamic difficult adjustment; however, calculations behind the scenes to find player frustration are difficult and complex. An alternative: give players deliberate hard/easy choices at various intervals during play, either within the world or via prompting.
The generation system doesn't know what the player wants, but they can filter as the player says "I want that!"
Problems with player as fitness function: Player acts as a highly myopic hill-climbing algorithm, can't jump around to new possibilities, gets stuck at local optima, doesn't have a lot of iterations before their patience runs out.
Solutions: cheat (know approximately what the player wants), encourage local exploration with a strong UI, present copious and continuous feedback, so that the algorithm runs as many iterations as possible.
Creature Creator's reactions are entirely randomized but the player responds to them emotionally, which makes them more engaged.
Terrain Generator had a much bigger problem than Creature Creator: playability. The classic procedurally generated terrain wasn't playable. The team started saving seeds of acceptable planets, but it still wasn't playable, there wasn't enough control, and there was a loss of variety.
Gradually, a script-based system was developed that turned into a "planet editor," with brushes, painting, etc.
The terrain generation process was never fun: feedback was strictly visual and didn't help the user with gameplay rules or possibilities, so all workflow was intuition-based.
Games That Make Games
LBP, Spore Galactic Adventures, Fantastic Contraption, Line Rider
Main thing is user engagement: playing game designer is not the goal for these types of games
Great variation of engagement level: a few dedicated users and a much larger "casual/disinterested" based. Most players only want to change one or two things and they want to feel confident while editing; low confidence in the workability of results, and observed failures of creation, will disengage players.
Brushes can describe visuals of terrain (hilly, snowy, desert, lakes) but they could also describe gameplay features (walkable, enclosed, populated...)
(There's some interplay of randomness, human customization, and AI where procedural techniques really shine, but it seems to vary from case to case and really hinges on the heuristics.)