Slide 1OverviewIntroductionIntroductionOverview(Very) Brief HistoryOverviewBasic Generators Linear Congruential GeneratorBasic Generators Linear Feedback Shift RegistersBasic Generators Linear Feedback Shift Register VarietiesOverviewContemporary Generators Perlin NoiseContemporary Generators L-SystemsContemporary Generators L-Systems ContinuedContemporary Generators L-Systems ContinuedContemporary Generators L-Systems Demonstration 1Contemporary Generators L-Systems Demonstration 2Contemporary Generators Expert SystemsOverviewFuture WorkFuture WorkFuture WorkExample Applications MinecraftExample Applications CityEngineExample Applications SubversionExample Applications .kkriegerReferencesSlide 28Procedural Content GenerationJames GrisetOverview•Introduction•Brief History of Procedural Generation•Basic Generators•Contemporary Generators•Future Work•Example ApplicationsIntroductionWhat is Procedural Content Generation?•Generic term for the usage of algorithms to generate content rather than manual creation of content.•“Content” refers to media content such as in movies, games, pictures, simulation, etc.IntroductionWhy Use Procedural Generation?•Reduce production time by focusing on mechanics, rather than simulation artifacts•Maintain consistent design style across multiple artifact designs, while allowing for controlled variationOverview•Introduction•Brief History of Procedural Generation•Basic Generators•Contemporary Generators•Future Work•Example Applications(Very) Brief History•Procedural Content Generation has existed to some extent for as long as the Computer Science field•Simple generators have been used in Monte Carlo simulation•Used in computer games as early as 1982•First notable use of procedural animation was in the Lord of the Rings trilogy•Widespread use in video games and simulationOverview•Introduction•Brief History of Procedural Generation•Basic Generators•Contemporary Generators•Future Work•Example ApplicationsBasic GeneratorsLinear Congruential Generator•In the form of XN+1 = aXN + c (mod m)•Programmer controls output through values of a, c, m, and X0 (seed value)•Implemented in the C language through rand() and srand()•May be expanded to higher order polynomialBasic GeneratorsLinear Feedback Shift Registers•Based on a “shift register” with bits shifted in to the left and shifted out to the right•Programmer controls output through setng the “polynomial” and initial state•Slightly higher quality than LCGsBasic GeneratorsLinear Feedback Shift Register VarietiesFibonacci•Bit shifted in is based on several bits of current stateGalois•Several bits are modified based on bit shifting outOverview•Introduction•Brief History of Procedural Generation•Basic Generators•Contemporary Generators•Future Work•Example ApplicationsContemporary GeneratorsPerlin Noise•Mathematical interpolation of floating point numbers•Creates fractional Brownian Motion•Used to make CGI textures look more realisticContemporary GeneratorsL-Systems•Lindenmayer systems•Defined as a 3-tupleV, the alphabet of the system (variables and constants)ω, initial string of the system (axiom, start, or initiator)P, set of production rules (one for each variable in V)Contemporary GeneratorsL-Systems Continued•At each iteration, each variable in the current string is replaced with its corresponding production to produce the next string•State is the string after a given number of iterations•The state is usually used to direct a “turtle graphic”•One of the most commonly used PCGsContemporary GeneratorsL-Systems ContinuedExampleV = {A,B}ω = AP = {A→AB, B →A}Iteration•A•AB•ABA•ABAAB•ABAABABAContemporary GeneratorsL-Systems Demonstration 1V = {F,+,-}F means “draw forward”‘+’ and ‘-’ are used to change angleω = F--F--F--P = {F→F+F--F+F}Contemporary GeneratorsL-Systems Demonstration 2V = {X,F,[,],+,-}F means “draw forward”‘[‘ and ‘]’ are used to save and restore position‘+’ and ‘-’ are used to change angleX has no meaning outside of the L-Systemω = XP = { X → F-[[X]+X]+F[+FX]-X, F → FF }Contemporary GeneratorsExpert Systems•Departure from previous approaches•Use statistical methods to determine world shape and item placement•First notably used in Procedural Content Generation in Valve’s Left4DeadOverview•Introduction•Brief History of Procedural Generation•Basic Generators•Contemporary Generators•Future Work•Example ApplicationsFuture Work•Most contemporary PCGs are involved in generating terrain artifacts (landscape)•Some use in animations, textures, and lightingThe next generation of Procedural Content Generation will be involved in creating entire mapsFuture WorkGoing to the extreme:Programming programs that program programsIn a paper published this year, Mahlmann, Togelius, Yannakakis at the IT University of Denmark suggest the use of Procedural Content Generation for entire games, including rule sets, unit hierarchies, game maps, etc.Future WorkAnother paper by Dimovska, Jarnfelt, Selvig, Yannakakis from the same university explores the use of procedural techniques to aid in physical rehabilitation using the Wii platformExample ApplicationsMinecraft•Terrain is generated procedurally•“Mobs” are placed procedurallyExample ApplicationsCityEngine•Middleware intended for simulation and use in motion pictures•Requires map data for input•Creates road layouts, building shapes, and textures based on user parametersExample ApplicationsSubversion•Independently developed game•Goal is for the entire world to be procedurally generatedExample Applications.kkrieger•Created circa 2004 for the then state-of-the-art hardware•Uses PCG techniques to create maps, play music, and place items and enemies all at runtime•Executable is 97,280 bytesReferencesKnowledge•The omniscient www.wikipedia.org•Mahlmann, et al. “Towards Procedural Strategy Game Generation: Evolving Complementary Unit Types” (link)•Dimovska, et al. “Towards Procedural Level Generation for Rehabilitation” (link)•Müller and Parish. “Procedural Modeling of Cities” SIGGRAPH 2001 (link)Example Applications:•http://www.theprodukkt.com/kkrieger•http://www.introversion.co.uk/subversion•http://www.procedural.com•http://www.minecraft.net"Anyone who considers arithmetical methods of producing random digits is, of course, in a state of
View Full Document
Unlocking...