Making Things Up: The Power and Peril of PCG

[Music] all right I saw hello everyone oh my voice echoes so my name is Julian Smith as Dave said I am an assistant professor at Northeastern University which is in Boston Massachusetts so I'm very grateful to be here where there isn't snow and to give you a little bit of background and why it is and the kind of work I've been doing in content generation I've been interested in procedural content generation as it intersects with game design to enable new playable experiences mix initiative design tools which we'll be talking about in this talk recently I've been doing a little bit of work looking into the history of content generation across games since about the mid 60s or so and the kind of games that I've generated content for in the past in my research have been super mario world western role-playing games style levels and puzzle games thanks and I'm I'm Julie

Antonelli's currently at New York University I've been doing various kinds of things in procedure current generation started out with trying to figure out how to control use evolutionary algorithms to control game characters and I was like hey why not turn it around why not you know clearly come up with levels and stuff instead so I've been using a lot of different methods typically from the biological inspired statistical and the similar non symbolic reams to do counter generation in various games including racing games Super Mario Bros Starcraft etc so this is kind of the the whirlwind tour of procedural content generation so we're gonna be talking about four main things today the first is giving a very high-level overview of different technical approaches and algorithms that you can use for content generation specifically

looking at what we're calling gameplay oriented PSG's so a lot of procedural content generation that you may have seen from like the computer graphics community would be for procedural textures or like height maps or procedural flame effects we're really more interested in the kind of procedural content generation that's for content that players were really deeply interact with and form part of the gameplay experience after giving this sort of very high-level overview of algorithms we'll talk about sort of practical advice so if you want to put content generation into your game what are some of the things you might want to think about talk about using PCG to actually help designers not just replace designers and then end with sort of a very again high-level overview of different debugging and visualization strategies you might want to use I think the key theme across all of this presentation is that there's no magic bullet we we all know this right there's a lot of different algorithms you can use for this and they've got trade-offs

and so the goal that we have with this presentation is to try to make those trade-offs a little more clear we're not gonna be here and tell you like Gramma's those are the best way to generate content and the one true way right there they're good for some things and not as good for other things so with that let's dive in a little bit to some of the we've identified sort of four high level approaches that people can use for content generation talk about what they are and what some of the trade-offs are in terms of what they're good at and badass so the first method the a set of methods that we can think about what we're calling constructive methods so these are typically very ad hoc methods where you might piece together large building blocks of content spelunky is a really good example of a system that uses a kind of constructive method there's there's pre designed by humans tiles that get placed next to each other and then a second pass in the algorithm goes through and decorates all of those

tiles with loot and enemies and so on and Darius Kazemi has a really great blog post online that should be pretty goo global that talks about specifically how the spelunky level generation algorithm works really constructive methods are about sort of directing randomness right so you could just place a call to a random number generator get a bunch of random stuff that shows up on your screen so we try a few different ways to try to influence that random number generator to give something that feels a bit more design early than just being like at the mercy of your random number generator so these can include things like paying careful attention to your knowledge representation and using very carefully crafted blocks that fit together nicely altering your random number distribution so you're not just pulling from a uniform distribution and look up tables and sort of my tagline for constructive methods is like we want to hack something together that works right and it'll it'll probably only work for this game and nothing else but like let's

just get something working well it's really nice about a constructive approach is that it's typically very lightweight algorithmically sort of like a few calls to a random number generator and you're done it puts more sort of burden on to designers and artists and level designers to be able to design your modular content that's going to go together though right which can be a lot if you need to suddenly think about like all possible pairs of all possible tile sets like what's going to happen it's pretty customized to the designs is not very extensible and really the main peril I think of these systems is that you're constantly fighting against human pattern recognition skill we're really good at detecting patterns in content and you'll see patterns in content very quickly and we kind of wanted to give like an extreme example of each possible approach so the extreme example I would say for a constructive method is the a DMD Dungeon generation system which is a paper-based system for procedurally

generating an entire dungeon as you go it has four pages of look-up tables tied to each possible dice roll you can do for placing like all of this crazy stuff in and it's it's like it's kind of inspiring really yeah sounds like a lot of fun yeah so the more the more sort of structured way in a sense of doing bottom-up content generation if you compare to constructive methods is grammars and this is grammars right of like computer science 101 or 1 or 2 fame or Chomsky famous something they're used for linguistics so basically you define an ontology of objects that can exist in the world and then you design a set of production rules and what object gives can be in each production step be transformed into what Ellis this has been more probably most famously used for for generating vegetation plants and

trees think SpeedTree for example but he can be used for lots of other things as well so in the background you see a part of your wrist Dorman's grammatical system for generating dungeons and quests in zelda like games it's computers good that's very broad applicability you can do lots of other things and it's easy to sort of combine different design elements you have a it you can get surprisingly complex results that still adhere to basic design principles out of very little you put in in a sense so it's very useful in that sense the perils of over generating or like the power of obj generating is also parallel for generating you can generate huge structures that often show a lot of regularity perhaps more regularity than you would actually want to do so but this can be solved by combining it with

some sort of testing procedure where you sort of if you generate something that doesn't actually look cute or doesn't play well according to some automatic master you can cut it down and regenerate which brings us to which brings us to so constructive methods and grammars are really more bottom-up approaches like you define a set of rules and kind of see what bubbles up and like what interesting surprising emergent things happen the other two approaches that we want to talk about a really more top-down methods where you as a designer and AI program like in combination that's what's cool about PCG or like doing AI end design together you can sort of specify high-level goals that you have and let the system figure out what to create that meets those high-level goals so there's a relatively new within the academic procedural content generation community approach of looking at constraint based systems to be able to do procedural content generation the idea behind these systems is that you specify what you want to be true about

your final content using logical language so you could say like I want to have a cave system and it should be 30 by 30 tiles and I want there to be at least five rooms and I want those rooms to be connected by at least 10 corridors and I want you know there to be lots of enemies and at least one of the rooms and you're giving these very high level design constraints and then you kind of hit the generate button and let this off the shelf constraint solver figure out what all of the different variables are and what they need to be set to to create a system for you so an example of a like out in the wild right now game the users constraint based PCG is this educational puzzle game called refraction where which is from university of washington where you're trying to control how lasers move around and Bend so that you can power spaceships with fractional portions of lasers this is a really powerful way of

doing content generation you need to be able to figure out how to express your entire domain in logic programming though which is a non-trivial task so we're working on making it a little easier so some of the really great things about constraint based systems you can make promises about design issues and guarantee that you will meet those promises which is huge like coming from grammars where you've got this emergent stuff that bubbles up you can't make any promises it is hard to even make promises about playability right like validity with constraint systems you can guarantee validity it's a fairly flexible and general-purpose language that you can use so it's very extensible anything that you can figure out how to express in it will work you don't need to like tack on a bunch of extra custom created AI modules some of the cons are you need to define your domain very very tightly including what seems like common sense rules so this is a a I system called Sinagra that uses a numerical constraint solving and is like

just even like specifying that platforms need to be attached to each other feels like a very common-sense constraint you need to explicitly make that clear to the AI system and it can have some scalability issues and those scalability issues and not super well understood right now as an extreme example variations forever is a constraint based PCG system to generate an entire space of potential acade style games and so you can specify the rules for the games using constraints as well and get really weird stuff that comes out of it yeah so another system which is more top-down than put them out for another sort of class of systems is optimization based systems also called search based systems depending on which right-right-right we have not disagreed over this at all ever so this is basically idea of using

an evolutionary algorithm or something similar a stochastic optimization algorithm to evolve your content so evolutionary algorithms is the easiest thing in the world you just take their win in evolution you have lots of content different levels or whatever random is generated you keep the good ones throw away the bad ones and make mutated copies of the good ones maybe and let them sort of cross over with each other and this works very well in theory it often works very well in practice it despite the extreme simplicity of the ID it requires quite a sophistication to use sometimes the fitness function need here is one of the key parts you need you didn't fit advantage or to sort of judge how good the content is the study can be used in very different scales from just trying to tune your game to creating a completely new game so what you see in the background here is Paul - source

city conquest which used evolutionary algorithms to tune it quite successfully as I understand the other example you see here in the background is Cameron Brown's Ludi system well it's not actually that it's actually the game Avila which is a game you can a simple board game you can buy in a box set which is apparently out there making money which was not designed by the game designer Cameron Brown but the sound by the system that Cameron Brown built which uses evolutionary algorithms to explore the space of different board games he sort of made it easy for himself by constraining himself to a very sort of narrow set of board games but nevertheless it works for him it works very well here so the screens to know for me the power of these systems is that are extremely general you can basically put anything else in there and it will work and it requires some relatively little domain knowledge to set an evolutionary system up to do

search for content the parents are one is that it can be very very slow so if you need something that sort of is guaranteed to generate a new level or a new sort of enemy or whatever before the next frame maybe you shouldn't trust evolutionary computation maybe it might be far too slow but if you do it on the silent on this different thing the other peril is that you really need to come up with a fitness function that captures what you actually want to capture which is trickier than what you what you will expect right so to take an extreme example here this is a very fascinating one this is Michael cooks Angelina which is a backronym for a novel game revolving laborat I named Angelina yeah so this system tries to complete come up with complete games including mechanics levels and and

it even shoots us sort of themes for its games and graphics by for example reading The Guardian and then using that as input to an evolution or algorithm therefore you get these sort of rather odd teams here this is a very fascinating system that is really trying to push the boundaries and do something that has not been done before if it was successful most of us will be unemployed unfortunately fortunately it's not really working all the way so at the end of this sort of survey of these four main classes of content generation algorithms there are several others which we did not really find the time to include here we just to sort of point out that very often the greatest power can be had from combining them so you can combine basically the examples we have optimization and grammars constraints and grammars optimization and constraints and you can have multiple layers or constructive algorithms on top of each other so you

see in background there's a Super Mario Bros level generated by an evolutionary grammatical system so basically and a system that evolves grammars that creates Mario levels and with some pretty good effect actually you can get a very large number of levels that look like this and that look completely different but according to the same pattern very easily so yeah so so in summary there's sort of four main classes of algorithms that we've talked about at a very high level at the end of this talk we'll give you some resources to go find out a little bit more about them and each one sort of has these different trade-offs it's so constructive algorithms can be very very simple to offer can be very highly customized to your particular game but they can lead to this peril of having a lot of repetitiveness in your content the players will start to see very very quickly and their ad hoc so they're not really extensible across games or if you

want to be able to like modify like if your game design changes there might be a lot of like backwards work that you need to do constraint based systems are really powerful for being able to give all of these design guarantees you're using a declarative language to be able to describe all of your content which means that while the logic programming language is not super friendly to designers unless they're you know really super into AI as well the like general mode of thinking and our experience has been really more accessible to non-technical designers the peril being that you need to figure out how to translate all of that stuff to different constraints and also debugging constraint based systems can be very challenging because often if you give a conflicting set of constraints to it and like tell it to find an answer it'll just tell you that it can't it won't tell you why it can't do that optimization based approaches have really good generality and very interesting emergent behavior can come out of them but it can be very hard to

define your fitness function and very tempting to try to define it as like what's a fun level and then you end up with this like weird situation where you're trying to come up with a mathematical definition of fun which is on the right or the one which Julian thinks as possible and I think maybe and they're also they can be fairly slow grammars again have a lot of emergent properties that come out of them and they're relatively easy to offer but you need to spend a lot of time thinking about how you're going to filter the content that comes out so with all of that sort of very high-level overview that now you know sort of four main classes of algorithms for content generation like how do you pick what you want to do and what are some of the design considerations you might have when you're making a content generator and there's sort of four different classes of things that you might want to think about now delve into each one of these in just a minute you can think about like what the building blocks are that you're constructing from right are

you working with like free authored chunks of content from someone in like the level design team are you working with like sub components kind of like a tile set like with no semantic knowledge attached to it is that what you're trying to do with stages in between do you need your content generated to run online and response to what players are doing or do you need it or is it okay if it runs offline what and then I think the two that I'm maybe the most interested in recently is what kind of player interaction do you want to have with your content generator if at all do you want to just be generating content and then the where gets dumped into that content and it's as though as though a human had created it right it's just the computer happened to do it or do you want players to actually be able to manipulate that content generation system as part of play which can lead to some interesting things and then also the extent to which you want to have control over the the

content that comes out do you want to be able to influence like directly influence aspects of the player experience so we can think about the building blocks aspect to sort of a question of data versus process it's so offered chunks I should maybe have a better term for these are these like pre authored big piece like set pieces that you can just like glue together in different ways or maybe you've got templates this is like the mad libs of procedural content generation right like a lot of stuff that's human authored and then like some rules to control what goes into the different slots and maybe those rules are really finely crafted to be able to make sort of always valid design like design controlled content or maybe those rules maybe those rules are a little crazier like Mad Libs so that you get weird stuff coming out at the end but these are both very data oriented ways of thinking about procedural content generation that maybe lend themselves to data oriented algorithms that you would

want to use like a constructive algorithm or maybe like a grammar grammars are really good for template based control on the other end of the spectrum and this is probably where a lot of academic research and procedural content generation has been focusing is on process oriented content generation so what of the the amount of content that your algorithm has to work with is like a single level component so maybe if it's Super Mario World your level component might be a platformer with an enemy on top of it like this has some semantic information attached to it and that you can kind of tell the AI system what that means but it's not really enough to be like a meaningful piece of player experience on its own so you need to have this intelligent process that's running that's trying to capture some amount of design knowledge for how to assemble you know he was trying to like take the designers brains and like squish it down into an algorithm without like

lobotomizing them right so these are much more process oriented ways and you may want to work with the component level maybe you don't have like a big design team that can put together huge amounts of content for you so you're like traps this is like the reducing authoring burden argument for content generation right if you don't want to have big set pieces you want to have smaller pieces then you're gonna need a much more complicated algorithm to be able to set those smaller pieces together and there you're starting to work something like evolutionary algorithms or constraint based systems algorithm speed is often a big question right and and this is kind of a no-brainer if you want your content generated to be able to run online and respond to players you're gonna need to pick something that's pretty fast right grammars are pretty fast you can customize your constructive whatever you've created to be pretty fast constraint these systems it depends on the size of your domain and what you're working with you can have a constraint

based system that will generate so like two Nagre which you'll see in a minute generates levels using a constraint based system but it's domain is so constrained that it can do that in real time if you want to have like a massive piece of content that you're generating you're looking at sort of on the order of a few minutes maybe in a few hours to generate something that's not going to work online for evolutionary approaches you can think of having a human in the loop right so you could replace your fitness function with humans voting and the game go out your arms race which you should all go look up if you haven't heard of it before use of this really effectively if you're running offline then you can be a lot more flexible in the algorithm that you choose and then finally we can think I like what about the players right maybe we shouldn't think about them finally maybe we should think about them first but the the type of control that you want to be able to have really dictates the kind of algorithm that you have so if you want a parameterised control sort of civilization map generation style control where you can tweak in the

beginning like I want there to be lakes and I want there to be no barbarians and a few other things these are parameters right that tends to lend itself fairly well to like weighting different rules in your grammar if you want indirect control over what's being created like like saying galactic arms race it's a space shooter game where the weapons are procedurally generated and the way that those weapons get generated is by evolving the next weapon based on the one that you've used the most frequently in the game so that's a really indirect kind of control you can also think of like the experience manager and left for dead it's sort of an indirect kind of control that the player might have over what's going on in your in your system and then you can also think about what level of design control you want to have so do you want experiential control where you're actually explicitly modeling some aspect of the players experience like the pacing of a platforming level are you good with compositional control which is really more like saying I want

50% of this world to be like covered with ocean and 20% of it should be sort of like built-up cities and that can guide the kind of decision-making you're making as well yeah so we talked a lot about individual methods and types of methods for generating content and when you should use one when you use should use the other and so on and by now it should be getting clear that there are lots of trade-offs and I mean confusing but then there's also the matter of where in the chain are you gonna use these how are you gonna use this are you gonna use an algorithm as game runs or the same time or you're just gonna are you just going to let a producer convert for you or be happy with it or key somehow interact with it so recently there's been a couple of prototypes that I loved on how you can come up with authoring tools for different games that use the full power of these AI methods to create content but together with you and in a sort of dialogue with you in a mixed initiative

fashion meaning that you can take initiatives and the program can also take initiatives so we'll briefly show three examples that all come out of academia actually our labs and but and but which showcases in various ways the first here is Tamera yeah yeah so I can talk very quickly about something I think Sagar was shown at the AI summit three or four years ago I want to say so five or six well that makes me feel old doesn't it so it's an auger is a system that uses a combination of constraints and reactive planning which is really like it's actually a grammar going on to have human-computer interaction for creating platformer levels this is a prototype tool it's obviously not like ready to go out into the real world and be used by platformer level designers but it's sort of playing with the idea of what this could look like so the idea is that the

human and the computer can interact in real time to collaborate on what the design of the level should be the human cut is sort of through interacting in the user interface is continually editing constraints that are placed onto the level and the machine is sort of brainstorming ideas for what levels can look like that meet the constraints that you're adding on to the system and it provides a level of experiential control so you can actually as a designer directly manipulate the pacing of the level you can say I want it to be fast paced in the middle slower paced at the end and it will be and it will create geometry that meets those pacing constraints without you needing to say what geometry should go into place so I'm so I'm going to kind of skip around in this video a little bit because it's whoops come on so this is you can hit

the generate button and it generates a bunch of different ideas what levels could look like you could draw in platforms and anything that's showing in in dark is a constrained system and generate stuff that fits in between them you can play test it in the editor and this is what happens when you tell a computer scientist to make that the computer scientist me to make the art for your a item because I know how to draw robots and birds that's it this is the point where you can directly manipulate the pacing so there's this beat timeline down at the bottom where you can add in areas where the player needs to be taking more actions you can remove actions are from the end and you can see that the level geometry is continually updating to me sort of the pacing that you want and you can regenerate at any time you can also grab platforms drag them around and it will automatically keep up with what's going on so this is a direct interaction where the content generation system yes

and where stenography studies about like co-authoring with a machine based on the constraint based systems sentience caps bridges another idea of using evolutionary system and other kind of search based systems to assist the player so this is some system for general sort of strategy game sketch generation let me talk a little bit over this video how do you start it you show me oh there's a mouse pointer right beautiful yeah okay good right so this is the sentence gets booked to playing yeah right you create it represent this right game maps it's a sort of high-level chunks which abstracted with um represents like impassable areas which could be wards and so on a Starcraft or base resources and so on so as you go

along and edit and draw things here you see those little screens to the right these are suggestions that are based on what you're currently editing which is generated using evolutionary search and something called novelty search which is a way of finding diverse similar but diverse sort of content it also gives you this little sort of meters that gives you immediate feedback as you add it about like the balance do you have like the same amount of bases next to you and and you have space around the base access to resource and so on you can get these various views to show you based on gameplay features various aspects of fairness and game balance and as you go along you might choose to you implement one or several of these suggestions and we place you map with it every time you do it the two learns from you and tries to figure out what kind of aesthetic preferences you have oh this person is trying to generate very sparse maps so

this file person is trying to very generate maps with lots of choke points and so on so it has various detectors but these are designed to design features and as you go along with this you can then come up with you can export it to various kind of game modes and we have an export of a Starcraft and also for like our own sort of you know simple map for material but it's trying to operate at the somewhat more abstract level it's not not not a level of a particular strategy game but of like some sort of abstraction of what what goes into a strategy game they take an example of something which is a lot more tailored a particular game we have what we call the road possum or a possum or something which is a level generator for cut the rope this yeah mobile puzzle games been very very successful uses three search and mmm and grammar based

genetic programming so basically evolving grammars so both people come up with levels and to help you solve levers and wheel turn right no yeah right so we have the same thing here we have an editor which actually is like a clone of the catalogue game using the original assets which they were happy to let us use you can put things out there you can press the bottom check for playability and it gives you the complete sequence of actions you take to sort of them to play the game this uses a pretty interesting tree search algorithm which I won't get into here but they took us I'm thinking and it can also sort of um there's a separate way of visualizing what can happen which is an occlusion based view with which shows you what kind of effects each component has as you put them in here and what what includes it and what

sort of pass you can actually need to take you can at any point sort of fix parts of the design and have it regenerate the rest of the sign and yeah so I guess wouldn't have time to go through this very much all right so I wanted to close with some thoughts on how to like yeah how to actually visualize and and debug these systems right so you've got Adam Smith has this way of talking about generative systems where you're sculpting a design space basically you need to to shift your thinking from how to design a single piece of content how to create an entire space of potential content and he has this very like nice Quay based metaphor that I just I really love it feels very artsy but it's it's tempting when we build generative systems so just like hit the generate button a few times say yeah this looks you know this looks like it's making reasonable stuff so I guess

my generator is like done right but it's difficult to actually sample reasonably from the space and actually Nathan and his talk is going to be talking a little bit about a solution he has for this you can think of it as like if you have a hundred coins and you flip them you would expect that 50 times you would get heads and 50 times you would get tails but it's entirely possible that you'd get heads like 90 times and tails ten times so it's hard to know that when you hit the generate button you're really getting a representative sample from this massive space of content that you're making so one of the ways that we've talked about trying to resolve this problem is by trying to actually map out the expressive range of a generative system and roughly the way that we've been mapping this out is defining several numerical metrics or numerical scores for the content that your system can produce generating a huge amount of content from that system

and with lightweight methods that will go relatively quickly with heavier weight methods that might you know you might need to like run this some overnight or something and then score each piece of content that you create and map out with the 2d histogram that can be visualized as a heat map what kind of space of content you're getting so these are each one of these graphs is a heat map for a different generator for a 2d platforming game mapping sort of a rough approximation of difficulty on the y-axis against a rough approximation of linearity so like how flat the levels are basically and you can see that each system is creating very different looking spaces of levels so the the green points in these maps sort of areas where the generator is biased towards creating a lot of levels in that space and then it falls off so we even have some systems like in the top right that system creates kinds of

levels that the system in the the middle top will never be able to create right so it's kind of interesting to be able to look at the space of content that you can get for reference some of the metrics that we're talking about here leniency which is like an objective approximation the difficulty by weighting each component that appears in a level by how much home the player would come to were they to fail the interaction with it it's like if you fail the interaction with a gap you're dead if you fail the interaction with a Goomba then you've just like lost your powerup right so it's not quite as harsh as a gap is also linearity like density of challenges and then pattern density and pattern variation or two metrics that are looking at how close to the original Mario levels the generated levels appear the other cool thing that you can do when you've got this ability to

visualize the generative space is that you can look at how your generative space is changing when you vary certain input parameters and uncover unintentional biases that you might have in your generative system so these are a bunch of heat maps for a single level generator where each one is a different configuration of input parameters to it and for the sake of time I won't say exactly what all of those parameters are but suffice to say they're different and you can see that there are certain configurations of parameters that bias the generator towards creating particular kinds of content more than others and you can talk to us and ask us about exactly how this is working after the talk of you would like so we wanted to close with just some further resources and ideas so if you if your interest is piqued by this like very high-level very well wind overview of like all of procedural content generation yeah man like 40 minutes

that's hard to do these are some resources that you might find useful so this is the procedural content generation Google group this is a google group and a mailing list that consists of indie game developers I think some people from triple-a industry and academics who are all sort of talking about procedural content generation it varies in its amount of activity and please if you joined us as many of you might be logging in and trying to do now please write like something in the recent for joining box so we know that you're not about right and and if you join please contribute to discussion there's a thread saying introducing ourselves please add to that introduce yourselves there's two game jams that are going on one happened last November called the procedural content generation Jam it will be coming back again in 2015 that's organized by Mike cook there's also the AI based game jam that's being organized by Alex's earth that's going to be taking place around the end of March there's a websites for those there's a wiki that has sort of

information about different algorithms we've talked about an in-progress textbook that's currently free online at PC G book those compo edited by Julia yes it will continue to be free but it would also come out as like a book PCG book calm have a look at it right now and then finally these are some of the academic venues where PCG research gets published we know that the paywall is a thing we know that the paywall is a huge pain and we hate it as much as you all do the first three of these are either open access or mostly open access means you don't need to pay to be able to find our work that we're doing and with that I think we should transition to Mason thank you [Applause]