Forging The River in The Flame in The Flood

[Music] hello good morning thanks everyone for for coming out stumbling out through your terrible hangovers at the cross at the crack of ten I'm to remind you to silence your cell phones and to fill out your evaluations and all that stuff so I've done that now my name is dummy on Isla I have been working games for a while now I come from sort of the Triple A space I worked on a couple of the Halo games spent some time on destiny a little time on BioShock Infinite but for the past couple of years I've been doing the indie thing and most recently with my new company the molasses flood and in fact we're all we we describe ourselves as a company of Tripoli refugees so a good a good number of us all of us came from bigger games including a lot of us from irrational post post post closure

so yeah so we formed this company recently we just released a game called the flame in the flood about three weeks ago so I think like for like a lot of Indies the notion of procedural content is pretty attractive it's a it's a neat idea and especially for us coming from these larger games with very expansive worlds the thought of having some kind of technology that can sort of amplify our very sort of meager art production budget and expand that into larger worlds and make it look good and immersive and all that stuff that's a very attractive thought so I'm going to talk about the river which turns out to be sort of the central element almost of of the game so the game is a third person survival roguelike except instead of crawling through a dungeon you are

taking a long soulful River journey through a post societal American South so you know think maybe don't starve meets journey that's our indie pitch if you're more literary and more inclined towards the literary maybe Huckleberry Finn meets the road or or a retro game pitch Oregon Trail me Steuben tubing is before even my time so I didn't I had no idea I don't get that reference myself and here's how it works as you float down the river you come upon large clusters of islands among those islands are certain locations you can dock at and get off on foot so then there's sort of an on foot exploration mode and you scrounge for survival materials and hopefully avoid the ravenous wildlife and then you hop back on your raft and down the river you go so just to give you a quick look at this is not the greatest intro to the river

but you know at least it'll give you a little bit of an idea of what what it looks like do we have audio [Music] [Applause] [Music] [Music] [Music]

so that's a very small slice but at least you know at a high level what the river looks like we're really excited me about this project when we first started talking about it was that the river is really I mean it is procedurally generated but it is like the central character of the game it controls a lot of the ebb and flow of the gameplay and it does so at many different time scales I mean that's one of the things that I find really interesting about it it controls sort of the hour-to-hour player experience in the transition between different biomes and you know gradually dwindling resources available to you at the dockable locations it provides a lot of interesting minute-to-minute decisions for the players they come into a new island cluster and are forced to make hard decisions between what kind of location which location am I gonna hit am I going to hit the church where I get

certain resources I'm going to hit the gas station where I get other kinds of resources and I can hit both because the river is carrying me for it at all times so that kind of sort of reactive minute-to-minute decision-making and then right down to sort of a more arcade style gameplay of I have to like shoot these Rapids avoid obstacles and and make it out without breaking my my bones so um so yeah so we're gonna we're going to talk about all of that and all of those different time scales but I'll also tell you one big constraint that we that we faced which is that our art director the brilliant Scott Sinclair is incredibly picky in fact he stated straight up at the beginning of the project that he wanted personal control over every single vertex in every single texture so you know he is an extremely sort of detail-oriented artist he wants to control everything about the lighting and all of that so for us some of the sort of may be expected procedural

techniques at the sort of geometric and textural level we were just not going to do so most of our most of our techniques are going to involve the arrangement of pre-made places pre-made pieces so the big exception to that of course is the water rendering which will be generated based on the fluid flow but it's a it's a big constraint but you know I also think it's probably a constraint that a lot of you face as well because you probably a lot of you probably work at places where artists are very used to controlling very specifically you know what the player sees so I'm going to give you the 30,000 foot view this is essentially sort of this staged process by which we generate the entire River we start with layout which kind of represents a high-level plan we go on to composition in which we decide what elements to place in a particular section of the river optimization which lays out which basically arranges the

elements in a pleasing way flow generation where is very simple which represents a very simple fluid dynamics I wouldn't even say call it a simulation I'll call it a fluid dynamics approximation or something and then finally decoration and rendering in which all of those elements are sort of you know a visual pass on them is performed in preparation for presentation to the to the player now my is something by the way is not that everyone's gonna go and like make a rubber game from this I'm gonna try as much as possible to sort of present the this sort of algorithms and techniques we use as fairly general because I think they are fairly general and whether you're making procedural cities or procedural solar systems or any of that stuff I think hopefully you'll find some of these things are pretty relevant to you the other thing I should mention or I should I should yeah I should mention right now is that a lot of this work is

also the work of my good friend and colleague Brynn Bennett particularly the lay out stage and the decoration and rendering stage he's one of my co-founders the other engineer on the project so just the two of us on the engineering side so let's start with layout so the layout is just basically establishes the high-level shape of the river in our world the river sort of consists of a sequence of biomes wilderness leading into small town leading into wasteland etc and then a biome itself is broken up into a series of what we call river sections which are really just bounding boxes with certain information attached to them so that's what the that image is what the layout looks like so the layout is I mean you another way you could think of it is as a script which is authored by the designer for what the river is going to do so the designer will be able to is able to specify any number of cluster

types in this case and a type and a B type and assign assigned dimensions to them you know within a probability range so you know these eight clusters might be from 50 to 60 in width and from 100 to 120 in length and the B clusters are slightly wider and a little bit longer and then the designer is able to specify a pattern a B so we're just going to take and we're just going to build out the layout by putting in a cluster in a cluster of B cluster a and it will run that out for the entire length of that biome and then we'll move into the next biome and that pattern may change as might be sort of the the the types of of sections that we define so in this case we have a a B section added which adds that X is a little bit of a transition between the a and the C very very simple

now dimensions are not the only thing that designers can specify in each River section they can also specify island density desired visible location count they can control whether Rapids are allowed to appear in fact they can specify whether Rapids are not allowed to appear forced to appear or sort of auto auto detect whether Rapids should be there which is the default sort of state and then also specify for example a scale on the flow speed so that certain sections can be faster than others and so by using using that using those parameters we kind of settled on what is basically the fundamental structure of the island which is of the river which is basically a series of net long narrow corridors with fast flow

speed leading into wide open slower moving clusters of islands where the player is allowed to make choices about where to dock coming back into narrow corridors and on to the next island cluster so that's sort of the ebb and flow of the maybe 15 minutes a half-hour gameplay of the of the entire game and all of our biomes kind of follow that pattern I hesitate to call it a an AI director because in my mind and AI director controls that pacing as a reaction to things that the player is doing so it's more a reactive thing this is not reactive at all to what the player is doing so it's not an AI director exactly but I do think it sort of feels the same sort of functional slot as an AI director does so let's move on to composition now I kind of went back and forth on what to call this this stage but so in composition we just decide okay now for one of those individual River sections what are we

going to put inside it what are we going to spawn there and there's really two kinds of things we spawn there one is just general landmass like islands and river edges so we're going to be placing the edges of the river as well finding finding out where to put them and we also put the resource locations so the special the special locations that the player can dock at so just starting with the with the general landmass general land masses for a given biome we have kind of a library of islands and we divide up those islands into a couple of different size categories and then we combine those with a with the desired density that was specified by the designer for that section and then we run it through a histogram which basically says what is the balance of extra-large to large to medium to small ions that we want to see inside of that inside of that section so with the

fairly balanced with a fairly balanced hopefully you can see that but with a fairly balanced histogram like that you get it sort of a pleasing balance of large and small islands sort of all intermixed with a very sort of small heavy histogram you get a bunch of tiny little islands and you know with a with a extra large heavy histogram you get you know just a few smaller islands now note that the density is actually in terms of land mass per kilometer squared not in terms of islands per kilometer squared and that's just because we can't say decide first that we're gonna place fifty islands and then decide that all 50 islands are going to be extra large so all three of these different configurations on the right are the same density so it should they should represent the same total landmass it just means that if you place extra large an extra large island you place less of

them it's fairly fairly straightforward now on to the resource locations these are the landmarks that the player is gonna you know are gonna recognize they're gonna float down the float down the river and say oh there's a church and they're gonna learn over the course of playing the game and and dying many times that Oh churches provide these kinds of resources gas stations these other kinds of resources and so on so you know balancing the appearance of those of those resource locations is a is a big deal we want to have good control over that from a design balance perspective generally we're going to have maybe three to five of them per River section depending on the size of the river section and we're certainly only going to have one of each type in each River section so you're never going to come to a section and see two churches there you're only get one church so we could do a very very simple thing which is just say hey every every time we were sort of composing a New River

section let's say that there's a certain chance that uh that a church will appear P Church now the nice thing about that is that you know the probability works out such that if I might if my probability of spawning is P Church then one over P Church is the expected interval the average interval between churches so if my spell chance is pointing the church is 0.25 then on average I'll see a church every four sections which is about right for us the only problem with that scheme is that the max interval is infinity I could get really unlucky and never see a church and of course that will provide a horrible experience for the player because they won't be able to get certain needed needed resources and those kinds of streaks of bad luck happen all the time so instead what we do is we take more of a scheduling approach in which the designers for each resource location type get to specify a minimum an average and a maximum interval of appearance so that lets us

basically say a church will appear every about two to three sections but never more than five so by the time I get to the fifth section if I haven't seen a church yet my probability of spawning it is one so there's a bunch of ways that you could arrange that this is not what we did it's what I probably should have done if and if I were going to do it again I would have done this I would have just sampled a triangular distribution it's a very very simple probability distribution and so you would just keep track of when was the last time basically like each time you spawn a church say you would sample one of these distributions and that would tell you when the next one should appear so you've just placed a church now place the next one in three sections we did something much more complicated for not a lot of benefit I would say learn from my terrible mistakes and and just to note that this is the way that almost all the resources in the game are are scheduled including you

know what plants appear on the individual Explorer islands what kind of loot we spawn what kind of enemy NPCs get spawned on the different islands and so on so now we get to the DD Center the meeting center of the talk which is optimization composition has given us a list of assets that we want to spawn into a rare section and now we want to just actually find their final locations we want to put them where they belong the islands are for the most part very irregularly shaped they're meant to look organic organic and yet you know and yet generic so that we can make a lot of get a lot of variation out of using the same islands over and over again at different orientations and and that kind of thing and so the challenge is to sort of make all these islands fit together in a pleasing looking way make them look organic make sure that the boundaries don't don't the boundaries between

sections don't you know look too terrible and I guess most elusively of all we want to create a sense of place when when possible and I have some ideas of some vague thoughts on what that means in a little while so here's how optimization works you start with some kind of best guess for where everything should go you evaluate the state of that that state of the world using objective function an objective function is just something that takes in your state and gives you a number and that number four point five or nine point seven and that number either represents how good things are or how bad things are depending on how you doing it and then you sort of iteratively modify that state to either increase the goodness or decrease the badness so we use a scheme called gradient descent and add a sort of a another scheme on top of that that for the best as I can figure out I think

random restarts with random restarts is sort of a fair term for that I couldn't find exactly whether what we're doing has a name but I'll call it gradient descent with random restarts so in terms of a best guessed start for all these things we are placing River edges so we can always sort of place the river edges along the river section geometry where we sort of suspect they're probably going to end up we actually end up doing something kind of kind of sneaky we we place resource locations in pairs along along along the length of the river section and the point of that is to try and create as many situations where we're two different resource locations are going to be on opposite sides of the river so that the player can't visit both of them at once our worst case scenario is you enter into a river section and everything is lined up at a line and that's not interesting because the player is not forced to make any interesting decisions Sid Meier is

on my shoulder here saying interesting decisions so and then the rest which are all but just random islands are just distributed completely randomly so our objective function is in fact an error function so we are going to be doing a gradient descent not a gradient ascent our state is simply the X Y and theta the X Y and rotation of every island in the scene in this section and we're basically just going to generate an error value that penalizes the violation of certain constraints that we want that we want observed for example we want the river edges to match as much as possible the underlying River section geometry so there's an error term that penalizes that gets bigger as those river edges get pushed away from the edges of the of the underlying River section we want

shorelines to stitch together correctly so if they pull apart too much we want to penalize that but then the most important one is we don't want pylons to overlap so as islands do overlap as islands do come too close together that generates an error term as well now the nice thing with what error function is that it's all summable so I can break up those different constraints into individual terms and evaluate each term completely independently of course I could I could architect those terms to in an in a in a not smart way and have them cancel each other out or do something silly like that but for the most part that's that's not an issue so let's talk about air overlap air because it's sort of the easiest to explain and you'll understand how to do the rest when we explain this how do we penalize the overlap between two islands or I would say the total overlap in the

entire scene well we take these arbitrarily shaped islands and our environment artist Chad Chad LeClair who's sitting over there put some spheres on it we call these packing spheres and that's just so that we can deal with a construct or a series of constructs that's a lot more easily dealt with mathematically than an arbitrary polygon so they don't have to be super accurate but they have to capture the overall shape of each Island too and then once we have that it's very easy to say well given these two islands and given their size I want these two islands to have you know a given desired margin between them so you can very quickly see that we can calculate a sphere to sphere overlap air basically just a function of how how how how much too close are these two are these two spheres and just as we broke up the air

function into a series of terms for each constraint we break up the overlap into a series of terms for each island so once you are able to calculate sphere to sphere error clearly the island island error for each pair of islands is just the sum of all the individual sphere errors and my total overlap error is just add up all the sphere to sphere interactions and and there you go very easy because we know how to figure out the distance between two figures as it turns out so if you want to make it look a little more mathy we say well you know just add up the radius of a plus the radius of B plus the desired margin that kind of represents how far we want to be and then the actual distance between the spheres is how far we actually are now that that that overlap is calculated such that if the two spheres are as far apart as desired or farther we get a

zero or negative overlap value and only as they get closer does the error does the overlap become positive and that's just so that we can run it through an error function like overlap squared essentially which is if you've ever done any optimization or anything like that like the square of the error is always like the most default error function to use we've tried actually a couple of different error functions here not just D squared and you could actually use anything as long as well first of all as long as it's zero the error is zero on the left half of the of the x-axis and as long as it's monotonically increasing and as long as it's differentiable as we're going to see so for a gradient descent we now have our state we have our error function and what we need to calculate then is a gradient so we take a whole bunch of partial derivatives and

that looks super super ugly but in fact just as we broke up error to be just a sphere to sphere calculation the gradient also can be calculated broken all the way down it's also summable so you can also break it all the way down to an individual sphere and just calculate for each sphere on the sphere interaction what is its own contribution to the gradient and you add them all up and you get a gradient and then we do a very standard gradient descent set where we step basically in the in the negative gradient direction now if people are don't know what a grading is no no what the hell gradient descent is it's um it's really it's actually conceptually very simple I have an island it's at an XY and XY position at a certain angle theta because what the gradient tells me is what direction should I move that island in in order to most quickly decrease the

amount of error so the gradient tells me essentially this islands should start heading in this direction and start rotating this way and so it doesn't tell us how far to go it just tells us that this is the direction that decreases the error and so we can we can at that point step in that direction and see what happened to the error if we go too far maybe the Erica error will actually be bigger but um but in any case it gives us a good hint on where to go so the tough part in all of this is in actually calculating those partial derivatives and in the interest of keeping this going I put that into an appendix so you'll be able to get these slides afterwards and and take a look at the horrific math if you'd like if you're that kind of person but this is abrasive to say you know it's a partial derivative it's a

couple you know couple applications of the chain rule you know freshman year of college math stuff I know what you're thinking you're thinking shut your damn mouth and show me a video so here's the action here's the here's the sort of system in action so the jiggling that you see back and forth is us kind of searching through you know basically following the gradient and sort of finding these little valleys of error and you can see that as each section spawns in its initially random but very quickly the islands kind of settle and find their find their place now I noted earlier that this represents sorry that overlap error is just one of the constraints that we're imposing in in the error

function so the other constraints that you're seeing right now are for example the the Shore linking constraints which is which is keeping the individual River edge pieces from pulling apart too much so if the if the River edge piece is kind of feel like they're on a series of hinges that's because that error is keeping them from floating apart too far you also might have noticed that there's some like jiggling sometimes it settles and then it sort of restarts again and then resettles that's sort of a random restart mechanism that I'm going to talk about in it so on the left is like one of our very early sort of reference river sections that Chad put together so in the early days we didn't call this system the auto Chad and then on the right is is an example that I captured yesterday of you know what a what a reception looks like once gone through the optimization phase and I mean it's

not exactly comparable because the density on the right is a little bit higher than the density on the left and so on but there's a lot of stuff that I like you can you can really see how the irregular shapes are kind of like complimenting each other they're kind of fitting in together it's almost like loose puzzle pieces that to me is is sort of what makes the system fairly successful it makes it feel organic it kind of feels like these islands pieces settled together a little bit and they they feel they feel right I wish I had an objective like success metric oh yes this is this is this is correct I don't think we have a metric other than like yeah it feels good nor is it very useful looking at real world reference by the way like rivers don't really have violence and if they have Islands they're really uninteresting Islands so this is much better than real life

there's a there's another example of a long section of River so one of the big problems with with gradient descent in general as you will know if you've ever done it is that it's very easy to get caught in these local minima in other words we follow the the error landscape downhill and we get to a little we get to a bowl in which there's no way locally to decrease the error and if if that bowl is low enough in error if it if it my constraints are more or less you know satisfied then you know that's fine maybe I just accept that but um but local minima can have this really rather catastrophic effect for our players they can create things like River blockages where all of a sudden you just run out of river which is pretty pretty frustrating experience so there's a whole bunch of optimization techniques that that basically use some amount of

randomness to get around this simulated annealing is a good example where simulated annealing will with great frequency randomly choose a new state based on an old state and even if that state has higher error it will jump to it anyway because you know maybe it's better overall to go in that direction it's kind of amazing that it works at all but we kind of take a we take we take a kind of cue from that by adding a certain amount of randomness and the way that we do that is that in addition to create a to of calculating overall error we also calculate something we call critical error that is if two spheres are far too close together you know say 70% too close together then we register that as critical error and and and register the island as being engaged in some kind of critical overlap and then we run all the way through a gradient descent we get to the end and we say oh we have these ions that are still in critical error in a critical error State

and just those islands we randomized we just replace them somewhere else in the map and then we run gradient descent again and we do that a couple of times and usually I mean usually there's no critical air at all I would say 50% of time does no air at all I would say another you know 40% of the time after the first or second run through the critical air is gone if by like the fourth run through we still have critical error then we just start deleting Islands particularly if they're if there are non visible ions it's kind of cool you can you can actually graph this and see exactly what's happening the yellow line is the error and the red line is the critical error so you can see how we run to about 80 iterations I think maybe is our maximum iteration step we have too much critical error and so we randomized and we suddenly get a big error spike but then it settles again and then by

the fourth time it has found an acceptable an acceptable statement I had never actually done the the graphing of this so when I when I did that specifically for this talk I was very pleased that it was such a clear trend line I was very rarely rarely does the rematch match reality but it did by some miracle so here's an example I mean here's a river section that is far too dense for the size I cranked the density way up so there's really no way that that it should be able to just to spawn these to fit them all but you can see it just sort of searching for four different configurations and then it just gives up and deletes a bunch of stuff obviously the player doesn't see this like if the player we're able to move the camera up they would not see the islands jiggling around in front of them but you know it's it's just it's a

cool visualization to actually see what's going on and very obviously very useful to to debug stuff okay so let's talk about flow generation we've now got our River section we've decided where all the islands are going to be and now we want to generate the the flow of the water around the different islands so obviously we're interested in doing this to sort of support the interesting fiction that we're on a river it it is great because it makes navigation challenging it gives actually a wave in in which the player can get better at at navigating the river as they learn to sort of read where the flow is going and understand how to sort of slingshot around islands and that kind of thing so it's it's a it's a it's a neat feature but that being said we're not super interested in creating like really super realistic flows I like like

the next programmer nerd I love like Navi or Stoke simulations and watching like fluid smoke sim and that kind of stuff but there's a lot of strange effects to that there's a lot of turbulence there's a lot of Eddie's and stuff and that kind of stuff is not generally going to be readable by the player nor can we necessarily afford a sort of ongoing simulation at the sort of resolution that we would need so we're really looking for is sort of some kind of cartoon fluid dynamics solution and one that is static one that we just calculate the flow and then we're done and then we just and then we just query it so like a lot of things and like the other like the other steps we've placed a series of angled bounding boxes over the river we call these flow volumes and for each of those flow volumes we will run a fluid solution a flow solution on there and then we'll line up the next

box and and and do it again and between those boxes will you know will basically blend flow angles and do silly stuff like that so the output of all this is going to be a flow map that's basically just a 2d grid of vectors where I asked for the cell and the cell gives me back a flow velocity at that point and so it's basically like a texture and and in fact that will be used as a texture when we pass it down to to the to the water rendering and then of course at runtime we can also do some like simple bilinear interpolation stuff to blend between those different cells so I was really worried about time on this on this talk and I had a whole bunch of slides here

culminating the demo and then I thought well forget it why don't we just go to the demo and I'll explain it there so let's see can everyone see that more or less it's a little dark I apologize for that this is um I ship the game before this called third eye crime and it was a 2-d game and I built my own engine for it it was a fantastic experience that I recommend no one ever do but in moving on to the flame in the flood I continued to use the engine that that I had built for a lot of different kinds of prototyping so I did a lot of the NPC prototyping originally in Next button because the name of this engine and I also did a lot of the flow a lot of the flow stuff so here's an example of a of a river section obviously the first step in creating this representation is to

sort of rasterize the environment in some case we just in some way we just take the environment as it exists in the river section and we turn it into a grid of cells and each cell is either empty or it's solid space so empty space water can flow through and then we also specify those blue the blue and the red lines that the edges are the input and output so we're flowing from left to right here we're going to be so there's a before we actually calculate the flowed directly there's an important intermediate step which is called well which we call an ISO map I'll show you I'll show you an ISO map god-willing there it is so an ISO map is actually like very much like a topographic map in a topographic map there's a bunch of lines and those lines represent constant altitude so if I were

to walk along a line then I would remain at the same altitude as I walked around hills and mountains and that kind of thing well very similar here except a line of constant value in the ISO map represents a line of flow okay so if I would just say like well let's take the easiest example this is full red down here if I just move from one full red to another full red I'll move along the bar can you see my hand you can see my cursor I'll just move along the bottom shore line similarly up here and if I take half red I'll move again you know basically through some line of flow and in fact I can sort of place down some things I'm kind of cheating I mean I have talking about the ISO map and I haven't told you yet how actually calculate a vector out of that a flow vector but in any case so the very I'm

almost embarrassed at how dumb this is but all we're going to do so it's easy to do this when you have a section of river and no islands in it you basically using an algorithm called Dijkstra's everyone everyone who saw my talk of the a Simon knows that I love Dykstra's Dykstra is is a is an algorithm where I can create a distance map so I can say in this case create a map which tells me for every single point on this open space here how far am i from the right shoreline and I can create a different map that tells me how far am i from the left shore and combining those values I can make an ISO value that varies smoothly between those two shorelines so literally we have a value that is 0 here and 1 here it's pretty easy expensive but easy and

then um so when we then want to add islands in so what I can do is just come in here and draw an island like this I can recalculate what the island is going to do is just basically distort the underlying ISO map and basically stitch itself in to the ISO map and the very simple way that we do that is that we pick a point on the island let's see let's say well anyway we pick a point on the island that's going to be that's going to represent the break point the point at which the flow moves either left or right we're going to pick a point on that island and we're going to look at what the ISO value is and what we can say at that point say the ISO value is 0.6 what we can say at that point is that the entire perimeter of this island in the ISO map is going to be 0.6 we're gonna just force it to be

0.6 all the way around and that's so that you know again a line of flow comes up to the center of the island it's going to break around both sides and then and then continue and then we take that 0.6 and we just fade it out so we literally just take an ISO value and we blend it out over some margin and that's all it is and that's how these that's how these islands are stitching themselves in hopefully that makes some amount of sense those slides that I took out which explain this a little more visually those again will be on the on the slides if you want to look up the slides later so now how do we actually take it from an ISO map to a actual flow vector well we actually use the gradient again we calculate a gradient for every single little point and the grading again tells us what direction at what direction do I have to

move in to increase the ISO value okay and that gives me up here it gives me a direction say straight towards one towards one towards one Shore and then at that point we literally just rotate it 90 degrees to the right and that gives us our flow vector so I can actually show you the flow vector now let's see yeah so that's what if that's what the flow vector ends up looking like if I run this I think these are mapped to red and blue the red and blue channels so red a positive red value is going to the right and then blue is the amount of blue is telling me how much vertically I'm moving so you can just see that if I put a little a little piece of debris right there it goes down if I put a little piece of debris up there it goes up and it all just kind of

flows together actually it's more compelling it like 10 times speed so there we go we do a couple of other I think cool things at this at this stage as well I mentioned Rapids numerous times and we kind of treat Rapids as a feature detection problem so I can turn on for example Rapids that I have discovered wow that's pretty extreme rapid it's pretty thick but the green the bright green area basically basically what there what that feature detector is doing is looking for narrow channels and and having found one seeing how long the channel is and and then marking all of that as as Rapids area so I can see just I'm just going to try and take away one of those islands so it's kind of

it's kind of nice to be able to kind of nice to be able to edit these things on the fly and just see what the reaction is so you know as I move things around it tells me where the rapids would go and then the last thing that we also do here is we sort of look for splash zones so basically areas where it's areas where it'd be interesting to to put like splash effects and that kind of thing see yeah so the little white areas are basically showing me where the river the flow is coming up against an island and the little I know if you can see the little dots but the little dots are suggested locations for actual effects placement so placing placing splash effects in that kind of thing anyway

that's a very quick view of that hopefully that made a tiny amount of sense so very quickly go on to sort of the rendering and decoration phase we now have our flow calculated we have all the islands where they belong and we have to do a couple of things here to sort of prepare the scene for for final viewing by the player one is we're going to do a little some simple you know randomization on the islands themselves like a lot of the islands have a couple of random variants that it can switch between and try and make a little more mileage out of like the same pieces of geometry you know spawn a billboard here or don't next time spawn some kind of rock feature there or not that kind of thing so a little bit a little bit of that goes on we place we place effects kind of including the splash effects that I

just alluded to in the in the fluid sim light shafts and for creating dramatic godrays and water streamers these big water worms that sort of flow and they're actually quite important for us because they actually are yet another cue that the player can use to read where the river is going and in fact we purposely place a lot of those water streamer effects at the break points of the islands to try and emphasize what point do I have to aim towards to sort of floor on the left side versus the right side so we try to accentuate that break point as much as possible and then of course we generate the water geometry itself it's just a very highly tessellated mesh that sort of follows the river layout and we add some undulation in the in the vertex shader and then we do the water shader itself I'm not going to I'm not going to

talk at all about the water shader only because what we did is not particularly new in fact we basically exactly did what what the portal tube guys did so they wrote a great presentation for SIGGRAPH 2010 which you'll see referenced everywhere we did exactly the same thing and it worked pretty well so just a few quick words on how we get all this stuff to work together again that's sort of the that's sort of the series of steps that we've gone through and I kind of like pointing out that in some in some ways those different time scales of gameplay that I talked about early on actually kind of correspond to various stages in that in that pipeline so performance is of course a big concern almost all the steps that I went over

particularly complicated ones involve some kind of horrible and cubed iteration over something including Dykstra's Dykstra is the not a super cheap not a super cheap process so we there's two fairly straightforward strategies that work absolutely fine for us the first of course being parallelization the flow generation in particular is I think really amenable to this because the input and the output are so well defined once you have rasterized your environment you can just take that texture and boot it off to another process including maybe you know including a including a processor maybe that doesn't even share memory with your with your main process it's it's fairly well-defined little chunk of memory that you need to pass back and forth and it's also a fairly well-defined chunk of memory that needs to pass back so it's it's it was actually shockingly easy for us fairly late in the game to shuffle that process off to a shuffle

flow generation off to another another thread and then the other one is good old time slicing we just simply say that we're only allowed to do one expensive thing every tick and all of those different processes share the same the same time slice and so a a tick on which composition for example is spawning some number of islands in that same tech grading descent will not be allowed to run and breeding descent will run each each tick gradient descent if it is holding the time slice right now it will run one iteration of gradient descent and and no more and that's uh it's actually sort of once you get that hand off correct it's it works really well we did have some performance issues on the on the Xbox one in particular fairly late in the game but

that was some of what prompted us to move flow generation in particular off to the other thread now the other complication of all this is that in that pipeline each stage of the pipeline is passing data on to the next one so you know flow generation can't run until optimization is completely finished just as you know water though the water rendering cannot happen until flow generation has happened so we do have kind of a a staging concern that we have to figure out and again it's not that complicated what we say is that there is some maximum distance at which we want to start composing and optimizing the river so say it's maybe five kilometers we want to if we get to a river section within five kilometers of a river

section we want to ask that River section to start placing islands and optimizing them so we have some desired range but then we also have a range at which we say well if you haven't if you haven't finished we're actually business we're just going to straight-up block until you finish literally the player will literally the screen will freeze the player will say what is this game broken and then it will suddenly go on again so it doesn't doesn't usually happen but it is a very hard hard constraint that says we have to be done with the optimization phase by the time the player gets within in this case three kilometers of a river section and there's a very similar thing for flow generation we start trying to grab the time slice to prep to to generate flow at about three kilometers and we will straight up block on until if we get to one kilometer and that's just so that we can be ready with

all the water surface generation and decoration by the time it comes anywhere near the visual frustum you know within the visual field of the player I'm doing better on time than I thought I would so we're coming to the end that's the that's the overview there's a lot a lot of details of course that I that I kind of skipped over but of course happy to answer any questions about details you might have and again like I'm going to put the slides online so that you can if you want to look at them in more detail including some of the ugly math so clearly PCG is a big deal these days this was really I mean for me I have never done PCG in any form at all before and this was like a really cool opportunity to do that particularly for a sort of element of the game that was so central to every second of the players experience at the same time I do

realize that the flame in the flood is kind of this it's a little bit of a unique case because it has this sort of linear unidirectional structure for the entire game and there are certain techniques like the scheduling techniques and the sequence techniques of the layout that you know that it's hard to see exactly how they would apply to say a procedural landscape or something like that so in other words you know we're sort of we're sort of less this and more this so the takeaways I would say come in two flavors there's sort of the technical takeaways I again sort of I think I think the way that we did schedule and histogram based spawning is is pretty useful and certainly like the use of gradient descents to optimize some some pre-made pre-made pieces I think is interesting and probably very applicable to other kinds of other kinds of games

and including non River games and you know if you are making something with flow in it then you know maybe the cartoon fluid dynamics model will be useful to you but I think there's also maybe an architectural thing here which I'd love to have more conversations with people who have also done sort of PCG pipelines I feel like the layout composition optimization and decoration pipeline is actually something that is probably fairly generalizable a phase in which we sort of plan out the overall shape of things a composition phase in which we decide how individual pieces of that layout will be structured or what will contain on optimization which you know finds the natural configuration for all those elements and then a decoration in case the stage in which everything is is prepared for four-player viewing so um so let's make it happen we'll call it the El Cod architecture it's very

interesting to Google image search for COD because you get a bunch of pictures of fish interspersed with screenshots of Call of Duty so that's what I got please contact me if you are interested if you have questions offline the slides will be very soon at my website right there and I think we have maybe four minutes for questions it's a miracle thank you yeah I was just wondering how you handled the seams between your river sections it seems like if you've heard too far on keeping things away from there you would get kind of gaps of content content and was that just something you dealt with or you mean for the so the question was the question was how do we deal with the transitions

between different River sections exactly and I kind of want to make it look like there is no scene but yeah so in particular the transition between maybe more narrow sections and wider open sections or mitigating or like navigating like particularly the optimization phases if I'm understanding yeah yeah thank you very much for that question because I had a whole bunch of slides on that and I thought I was not going to get time to do it we actually do a thing where when we when we do optimization for a river section we actually allow that River section to adopt some number of the islands of the previous section so basically if I'm a wide open section I'll actually be able to grab the the islands that have already be placed and sort of reactivate them and run and run with run the optimization phase with those included in the in the calculation and what that does is it allows those river pieces to sort of it actually rather well smooths out the transition so that everything

kind of you know pulls together in a certain way I wish I could have the slide somewhere but um but yes so each time we generate each time we we generate a whole bunch of new islands we also adopt from the previous section some number rounds and that's how we run and that solves the problem you've also got a hard limit on there's only one of those features per section so how do you handle or prevent a probability of one for more than one feature in a given section well you can I mean you can I mean it just means that you know again like there are three to five of these visible locations per section so if it you know we're gonna spawn a church and a gas station then fine maybe they both had probably as one but you you do you I think you're touching on a really good question which I don't have a good

answer for which is say I've specified I can have maximum five locations here and all seven locations say oh now I have to spawn well what can you do you end up you only spawn five of them and you tell two of them well you're gonna have to wait till till next section so it's absolutely true that in theory of the the the average interval is is reflected by the by the spawning frequencies but every once in a while there'll be a collision of so many that you have to so so the effective average interval is probably a little bit longer than the desired but don't matter I was surprised that you were using Dijkstra for this map wouldn't have been much easier to simply generate why you said implicit functions of the the course edges of the river because then you would have an

immediate formula from computing the distance an implicit function of sorry but it do you mean based on the packing spheres or sure yeah that's true it is yeah and I'm and I'm a completely irrational fan of Dijkstra's so I use it everywhere yeah if I could if it's true and actually one of the ways I think in which the River Edge will the the flow is going to be improved in later iterations is actually to do some of the simplification of the of the river of the shoreline that maybe your that maybe you're alluding to so yeah I mean such an implicit representation of course would not handle cases where there are concavities in one shoreline or another

but but you're right I mean that might be a faster yeah that's a good that's a good optimization yeah thanks do you want to curate that experience did you find one of the elements of Robles can be that kind of player story element where you did get ten floors without a health pickup and that was kind of almost more interesting cuz it's like it's that one-in-a-million chance where that really really bad can happen but that's more a story to tell was there kind of an inside kind of decision made in the design point of is it worth giving them up to get a more curated more kind of balanced experience but with less of those super highs and super lows were really crazy things you know yeah I mean I it's a great question like so the question was like is it is it worth creating bounds on those spawning frequencies because when you do

get a really bad run it can have story value to the player I would say that like you know players don't often have a lot of sense of humor about like not getting their Flint you know they want their Flint so I I don't mind such a thing I I feel like the possibility for such streaks of bad luck should at least be consciously authored by design and I think we can say things like well you know in the end churches are not a hundred percent required to play the game so maybe we make Church be one of those things a church that'd be one of those things second you know maybe you'll never get one but um but I will say that this approach is one that we happened upon because people were finding it frustrating that they would just go you know did have one run you know it's it's a problem especially for this kind of game when we're trying to teach the players certain things about resources

and you know and about you know the the the beginning of the game right we're you you come to learn these strategies like well when I'm out of the gate first thing I need is to expand my pouch which requires me to you know get these kinds of resources and you want the player to learn that but then it becomes like really frustrating and crappy if like on a particular run no sorry there's no pouches for you because just because so yeah I would say if there are going to be such you know streaks of bad luck I would prefer that they be sort of consciously designed in rather than everything's random with the with the random sorry Sagan with the random island rotation how do you handle the lighting lighting it's all I mean it's all we don't have any pre-baked lighting or anything it's all dynamic lighting so it's not at all an issue there are certain elements there are certain

elements on the islands like billboards that we actually do like rotate towards the camera or one suite that's part of the decoration phase that I didn't thought it in talked about but you know if you took the author to island and you just like rotated at 90 degrees you would probably get a lot of like billboards like this so we rotate those back as part of the decoration phase but but lighting itself was not an issue because all dynamic I took a lot of that and actually I was smiling a lot about your how you think so we should talk afterwards but my question is how long did you iterate and change and rewrite the whole thing when when you when you came up visit events and all that so we figured out fast it was it was like really a long time we worked all on triple a bigger project and doing

that that was really astonishing how how long it took for pre-production - because we changed and change - change and then try to figure out all that stuff so how long did it take until you had the feeling oh now we have it now it's working now we can throw content or you don't throw so much content you get that yeah so the question is like how long was it before this system was like at least basically in place before weekly before we could yeah we had we had before we had confidence that like okay there's a game here and we can hang it around this structure I mean I would say actually like it was fairly fast I mean it was um we started and we started together as a company around May June of 2014 and then we you know had all of this in place certainly by the time we did a Kickstarter in October but even

given that timeframe I wasn't working on that full-time by any means so it was probably I would say the initial probably two months of like getting things to basically work and of course it wasn't totally I mean I think we had the basic framework for the solution after about two months and we were certainly confident enough to go forward with it at that point and then you know you know a week here in a week there in two weeks here in two weeks there you know that clearly adds up but that was much more of a you know long term iteration spread out with between other things please yeah okay oh yeah all uh I'm all done thank you everybody you