//****************************************************************************//
//****** Procedural Generation / Terrain Generation - March 6th, 2019 *******//
//**************************************************************************//
- 2 minutes to launch, class upcoming...
- "I mean, you guys CAN keep talking...I get paid either way, you know..."
------------------------------------------------------
- We've been going through the background of procedural content generation - what it is, why games care about it, and so forth - and hopefully we'll wrap that up today
- After that, we'll start getting into the specifics of different algorithms - y'know, the FUN stuff!
- Most recently, we were talking about "design time" PCG, which is when designers use procedural generation to help them make games more efficiently, rather than any PCG that end users will notice
- In particular, this helps out designers with "economies of scale" - as games get bigger and bigger, handcrafted content gets more and more expensive linearly. It just takes people more time to make more content!
- Procedural stuff, on the other hand, has an upfront time cost when you're building the tool, but once it's built, you can use it to make a LOT more content more quickly than a human designer can
- This is assuming the quality of stuff your algorithm makes is comparable to the hand-designed stuff, of course
- If you need to put in a LOT of effort to get the algorithm working at all and its content interesting, the upfront cost is higher, meaning you'll need a LOT of content before it makes more sense to build a tool than to hire a bunch of designers
- So, what types of content does it make sense to procedurally generate?
- There are 2 broad categories of content:
- THROW-AWAY content is stuff that you just use once and then don't have to think about again, and don't meaningfully affect gameplay (e.g. trees in a forest, sky textures in the background)
- These are GREAT targets for PCG; most of the stuff is eye-candy, we tend to want a lot of variety, players aren't paying a lot of attention to it (compared to the rest of the game), and it doesn't destroy the experience if it's slightly off; it just needs to be "good enough"
- REUSABLE content (which should really be called "meaningful interaction") is stuff the player directly interacts with, like quest NPCs, enemy behaviors, etc.
- From there, we have to think about having RUN-TIME PCG
- Run-time PCG is where we generate new content every time the player runs the game, like terrain generation, adjusting difficulty levels, etc.
- This is best used when you need to adjust content with information you won't have until the game starts (e.g. Left 4 Dead's difficulty manager), or when you can't pre-compute something due to memory limitations
- This type of content lets us deal with the "optimization problem," i.e. deciding the "best" content for the optimal player experience
- Oftentimes, this involves us needing to create a PLAYER MODEL representing what we know about the current player, and evaluating which content or parameters are "best" for a given player
- This has some challenges, though: what stuff do we model? Where do we get this model from? etc.
- So, let's sum up this background stuff:
- PCG promises to help us make a LOT of stuff without the designer getting involved, such as:
- Creating in-game entities
- Generating custom NPC histories
- Generating puzzles and levels, and adjusting their difficulty to the player's tastes
- Making less-repetitive content (e.g. permadeath)
- Doing custom story generation ("I've spent about 15 years of my life on this - it's REALLY exciting, but we're not quite there yet")
- Changing the pace of the game dynamically
- Extending the game's "lifetime" (imagine infinite, free DLC, FOREVER)
- But, with all that promise, there's gotta be a few risks:
- PCG for anything non-trivial is an NP-hard problem - we can spend a LOT of time doing this, both researching techniques and executing them!
- Completely testing our content generation is IMPOSSIBLE - we couldn't manually build it ourselves in the first place, so there's no way we can see it all!
- For instance, in No Man's Sky, there was NO WAY they could check every planet; they just spot-checked certain planets, but they missed a lot of nonsensical combinations
- We can end up with a ton of mediocre, bad, or even straight-up offensive content that doesn't result in a good gameplay experience
- Professor Riedl once worked with a magic spell name generator that put together random words and, well, use your imagination for some of the stuff that came out of that...
- "Also, terrain that resembles anatomy will just...happen"
- The LEGO company famously tried to build a Minecraft clone, and then scrapped it because they couldn't build a phallus detector
- Similarly, we can just end up with a lot of boring, meaningless content that bores people - it's possible to generate TOO much stuff ("just because we CAN build a world the size of Connecticut doesn't mean we should")
- Some of the "unsolved," research level problems still in this area include:
- Procedures for structuring the player experience (ESPECIALLY doing narrative generation)
- Creating accurate player models
- "Say I like 'My Little Pony.' How is the game supposed to figure out I like 'My Little Pony?'"
- Avoiding and dealing with catastrophic failures at runtime
- "Healing" a broken level (updating your procedurally-generated level to dynamically patch itself when bugs are found)
- Moving from a "generate and test", trial-and-error approach to algorithms that "understand" what makes content good
- Personalizing the content to the player model
- Providing a sense of "meaning"/progression in the content
- Figuring out in advance if the content we're making is any GOOD - how can we make sure our algorithms make something interesting on their first try?
- OKAY - that was a lot of background stuff, but it's done. Now, we can start moving on to some algorithms.
- The first, usually simplest, and (surprisingly) often the best approach is to try and make EMERGENT SYSTEMS - that is, simple rules that operate together to make complicated results
- There are two systems of this type that we'll be looking at: rule-based systems/agents, and cellular automata
- As an example of this, let's consider terrain generation:
- One way we could do this is MULTI-AGENT terrain generation"
- Here, we start by creating a number of specialized agents that all operate in parallel: maybe a "coastline agent" that produces uniform-height islands with interesting shapes, "beach agents" that flatten the land near water, "mountain agents" that raise certain parts of the terrain, "river agents" that create rivers, "smoothing agents" that get rid of erroneous terrain, etc.
- Each of these "agents" can be literally 10 lines long; for instance...
- COASTLINE agents are where just start with all the land slightly underwater, and we plop a bunch of these agents into random spots
- If they land in the water, they'll raise some points above sea level according to some criteria
- If they land where there's already land, they'll walk around until they get to the water, then continue raising the land according to some criteria
- When multiple agents operate on the same spot, interesting stuff can happen
- We let these agents run until some "stopping criteria," we designate is reached, be it a certain amount of land that's generated, a certain amount of time that's passed, etc.
- BEACH agents then randomly walk until they reach some coastline, flatten the points they find to slope down to the water, and keep walking around until they get to the next piece of coast
- MOUNTAIN agents spawn in a random point on the land, choose a random direction, and raise the land wherever they pass through
- At random points, they'll change direction by some random amount, and will follow the coast if they hit it
- In the real world, mountains are mostly formed by tectonic plates crashing into each other, which results in this zig-zaggy shape; we're
- These might also spawn
- RIVER agents begin at the coastline, then slowly move uphill, lowering the land as they go and decreasing in width as they get farther inland, stopping after some max distance
- SMOOTHING agents, finally (or in parallel), randomly walk around the landmass and average the height of all the points around it, smoothing out the terrain and preventing too-extreme terrain from forming
- We COULD run all these agent types in parallel, or we could run them successively (e.g. coastline agents do their job, THEN we span beach agents, etc.); that's a design decision
- All of these agents individually, though, are pretty simple
- We could also generate terrain with a CELLULAR AUTOMATA
- Let's say we want to create a 2D cave or dungeon for a rogue-like; how'd we do this?
- Well, first off, let's explain what a cellular automata is
- Cellular automata are just a 2D (or 1D, or 3D, or what-have-you) grid of "cells," each of which behave according to some simple set of rules
- These rules tell the cell to change state based on what its neighbors' states are; for instance, the cell might have the possible states:
- Dead
- Still Alive
- Born
- "These systems were partially inspired by bacteria, where the kinds of states made sense"
- Probably the most famous example of a CA is "Conway's Game of Life," which is a 2D grid with the following rules:
- If a cell is alive and has less than 2 "alive" neighbors (lonely), OR more than 3 neighbors (overcrowding), it dies
- If a live cell has 2 or 3 neighbors, it stays alive
- If a cell is dead, but has EXACTLY 3 neighbors, it comes back to life
- To get to the next state, we copy the entire grid, and then for each cell ask if the cell should be "alive" or "dead" based on its neighbors in the old grid
- These rules are really simple, right? But the behavior of a system like this ends up being pretty interesting!
- "Professor Riedl, that's very interesting, but I WANT CAVES!"
- So, this system has to be MORE complicated than Conway's Game of Life, right? WRONG, YOUNG FOOL!
- We'll have 2 states: "walls" and "floors," and begin with a map of all walls EXCEPT for a few randomly-scattered floor cells
- We'll then say that for each cell:
- If, of its 8 neighbors, 5 or more are walls, then the cell becomes/stays a rock
- Otherwise, it becomes a floor
- If we run this for "n" iterations, the floor cells will keep growing together until we end up with a semi-convincing cave system, with the number of neighbors required/floor cells we start with changing what our final result looks like
- Alright, we'll keep digging into these on Monday - don't forget your homeworks are due SATURDAY, and adios!