Procedural Generation using Constraint Satisfaction

welcome my name is Terry soul and this is programming chaos a channel devoted to fun and interesting programming projects to help you hone your programming skills today I'm going to be looking at procedural generation using constraint satisfaction so this can be used to generate all sorts of different procedural content from maps to plant like growth to whatever this thing is the idea behind constraint satisfaction problems is fairly simple we have a set of variables each variable has a range of possible values and then there are a set of constraints that limit what those values can be and the goal is to find a value to assign to each variable so each variable gets a value that doesn't violate any of the constraints and by setting up the correct constraints we can generate all sorts of procedural content that meets a set of rules or in this case a set of constraints a canonical constraint satisfaction problem is sudoku in Sudoku if you're not familiar with it the idea is for each cell you need to fill in a value between one and nine so a cell represents a variable and it needs to be assigned the value between one and N the constraint than Sudoku is that no two values in the same Row the same column or the same subcell can be the same so for example if I want to fill in a value here it can't be a nine or a one or a four because those are already in this column so I have to find a value in the range from 1 to 9 that doesn't violate any of those constraints that makes this a constraint satisfaction problem and there are algorithms you can write to solve it fairly easily the tricky thing about Sudoku is because you start with some of the values filled in there's only one possible solution and so the techniques the algorithm that you would need to use to solve this are fairly specific they have to be a global search technique that exhaustively searches all possible solutions in a smart order in order to find the one right solution for procedural generation we often in fact we should have lots of possible solutions that's the idea we can procedurally generate all sorts of variation so to understand that let's think about a map so here I've started to fill in a map with different terrain you can think of this for example as Forest Beach and water so each cell again represents a variable and it can have values of forest Beach or water and then we could put in some constraints for example you can't have Forest next to water and you can easily imagine that there are lots of different ways to fill in this grid without violating those constraints so this is a solution Rich environment there are of course lots of ways to fill it in that would violate the constraints we just want to find one of the ones that wouldn't and so because there are lots of possible solutions we can use what are known as local search techniques so the basic idea that I'm going to use here is to fill in all of the values semi- randomly so I'll go in and say well I don't have a value here yet let me pick one and if I do that randomly or even semi randomly I might violate a bunch of the constraints I might accidentally put some water next to for so then what I'll do is go back over the map and I'll look for places that have a violated a constraint and I'll try and find a new terrain type that minimizes the number of violations so this is sometimes known as minimum conflicts or the minimum conflict algorithm it might be if I have a complicated map with lots of different terrain types for a given cell I can't find a perfect value on the first pass but I might change it so that there are fewer violations and then I might go to one next to it and change that so that there are still fewer violations until hopefully I come up with a map that has no violations all of the constraints are met and then I'm done so this is known as a local search technique because we start with one particular map which again May violate some of the constraints and what I'm basically doing is looking at nearby maps I'm changing a few of the cells at a time so that's what makes it a local search technique if you're familiar with wave function collapse it has some similarities to the wave function collapse algorithm so in order to code this basically what I need is a map and then I need a way to go through and pick random cells see if there are any constraints that are being violated so I'll check for conflicts and if there are conflicts then I will change the value in that cell so with that in mind let's start the programming so I'm going to be programming in this in Java using the processing environment if you're not familiar with processing you can download it for free from processing.org it's a nice environment for doing quick procedural generation projects testing things out all processing projects basically have some boiler plate code there's a setup function which creates the window that I'm using and then a draw function which Loops infinitely updating the drawing in the window the first thing I need for my code besides those pieces of sort of boiler plate is my map so I'm going to create a map and this is just a two-dimensional array of integers where each integer represents the different possible terrain types and then I need to know the size of the map and the cells in my map are going to be bigger than a pixel so I'm going to set a cell size and the cell size is something that you can play with I'm going to start with one that's maybe a little on the large size sort of 5x five just so that the code will run and generate Maps fairly quickly so now that we have those variables defined I need to actually give them values so the width of the world is actually the width of my window divided by the size of my cells so my window is 800 wide but I'm dividing it into cells of size five and that gives me the width of the world and I'll do the same thing for the height and now I can Define the map and I see I misspelled height there there we go and now what I want to do is fill in the map and there's two options here for procedural generation you can either fill in the map with random terrain values and then try and correct any conflicts or you can fill it in with undecided values in wave function collapse this would sort of be thought of as a superp position of all possible terrain types and which approach you take can influence what the results look like for map generation I found that starting with undecided values tends to work better cu the idea is the entire map will be undecided and then we'll randomly pick a square and maybe fill in mountains and then you tend to get mountains that sort of expand from there because you can have mountains next to each other but you could start by filling in entirely random values if you want it in any case let's put in the code for that so I'm going to be using zero as my undecided train type and it's probably useful at this point to think about the other terrains that I want and so I'm going to go to the beginning and put this in as just comment so zero like I said undefined Undeclared type a one will represent mountains two will be Forest four water five will be deep water and six will be high mountains and the deep water in high mountains tends to give you a little better in my opinion looking of a map you get more consistent mountains and Water by including some extreme values those are the different types although so far all I'm putting in is zero for Undeclared the next thing I want to do is draw the map it won't be very interesting yet because all the values aren declared but it's good to make sure everything is working properly so let me move this up a little bit and I'm just going to cut and paste my XY Loops here because I need to go through the whole map printing each cell and what I want to do is just draw a rectangle for each cell but I need to make sure they're the right color based on the terrain and so I'm going to set the fill color for those rectangles Phill determines the color inside the rectangles and I'm going to do it based on an array of the different shades that I want and I haven't filled in this array yet I'm just going to put in the code here and then I'll create the array afterwards so this will look at the current map XY location which is a number between 0 and 6 and then it'll look in the shades array to figure out what color that should be so let me go back to the beginning here and set up my shades array so it is an array of color values and for the Undeclared I'm just going to use black so I'll put that in as hexadecimal value and then for mountains I'm going going to use a grayish color for Forest I want a dark green and so if you're curious where these hexadecimal values are coming from basically I went and found a little app on the web where you could pick a color and it would tell you its hexadecimal value there are lots of those out there and if you don't like my colors you can certainly use that to pick your own let's see so that's Forest the next thing I have is PLS I'll just make those bright green and then I have water I'll make that bright blue and so if you're not familiar with hexadecimal colors this is the amount of red zero this is the amount of green the middle two values also zero and this is the amount of blue because it's written in heximal FF is my maximum amount of blue so this gives me maximal blue this for example is maximum green this is a fair amount of green but it's not maximal so it's a darker green for the forest so that's how those are represented and then I need deep water so that's blue but less blue and so it'll be a darker color and then I need my high mountain color and I'm going to make that maximal red blue and green I.E white and so it's going to be like snow cat mountains so now if I run this it will draw the map but it's all black because all of my cells are in the Undeclared State the next piece of the code involves going through and looking at each cell and if it's Undeclared or if it has conflicts then we try to find a new value for that cell that minimizes the number of conflicts so let's put that in and I'm going to have this function return a Boolean value true if it's succeeded at setting no conflicts and false if there are still some conflicts that might need to be resolved I'll call that success and I'll begin by assuming that the success is true and that's the value that I want to return although as we'll see as I go through and look for conflicts if I find any conflicts I'll set that to false saying well we found some conflicts we tried to resolve them but it might be necessary to call this function again so the idea is we call this function over and over again until hopefully we have in this case a map with no con conflicts in it what I need to do is go through and look at different XY positions see if they have conflicts and try and fix them if they do what I'm going to do is go through and look at a number of cells equal to the total number of cells but I'm not going to do it systematically so you might have been thinking all along but we'll start in the upper left and systematically go through and check each cell to see if there are any conflict and if there are pick a new terrain to minimize them the problem with that is it creates artifacts in your map so if I start in the upper left and say this is going to be mountains then I'm very likely to put mountains to the right of it and when I get to the next row below it and so you tend to end up with terrain types that move down and to the right if you go through your map systematically so I don't want to do that I'm going to pick randomly scattered points to change the drain in and that way I won't get those artifacts for other problems it may be that doing it systematically makes sense so in particular for these plants which I'll talk about more later on I am trying to resolve the conflict systematically from the bottom up and that makes sense because the plants grow from the bottom up and so the order in which you look at yourselves and try and resolve conflicts depends a little bit on what problem you're dealing with for maps because I don't want any weird artifacts I want to do it randomly for plants that are growing up I may actually want to do it systematically from the bottom to the top that's the number of cells that I'm going to check for conflicts on a given pass of this function and I just need to find random cell locations to look at I'm going to pick a random X location and a random Y location and I should go ahead and declare those two variables and then I need to check and see if for that particular cell location there are any conflicts and I need my conflicts variable and I haven't written the check conflict function yet I'll need to write that but assuming that it exists I can now say if the number of conflicts is larger than zero for the location XY that means I need to pick a new terrain type there the other case where I need to pick a new terrain type is if it's Undeclared and in order to pick a new terrain type what I'm going to do is pick a random type fill it in and see how many conflicts that that new terrain generates and if it's fewer I might want to keep it and if it's more I want to throw it away and what I'm actually going to do is try several different terrain types and pick the one one that has the fewest conflicts what I need to know here is what is the best terrain type I found so far and how many conflicts did it create so I can see whether the next terrain type is better or worse than that and I'll make a little more sense once I have all of the code written so let me get started so the best type of terrain I found so far and the least conflicts I've found so far and I'm just going to make that a big number like a 100 and then the temporary terrain type so my tempt is temporary type and the temporary number of conflicts and here's how that will work I'm going to try some number of times and how many is up to you I'll maybe try eight times so I'm going to try eight different terrain types randomly which means I'm going to pick some of the same terrain types twice but this guarantees that I try each one probably at least once and you might be thinking well why do that randomly so actually let me fill in the random part first so the idea is my temporary terrain type is equal to 1+ the number of types minus one and I haven't defined this I have seven types but it's good to make that a variable that's easy to change so the idea here is I have seven types 0 through six but I only want to pick types 1 through six cuz I don't want to pick the undefined anymore I want to pick a definite type and so a reasonable question to ask is well why am I picking a random type why don't I go through them one at a time start with mountains and then forest and then planes and see which one causes the fewest conflicts well it turns out if you do it in order like that you're heavily biasing your search towards mountains in fact there's a very good chance that you'll just entirely fill the map with mountains and say done no conflicts violated it's all mountains that can be next to each other so it turns out it doesn't work well to do it systematically we have to try and fill in random types to make sure we end up with a random map so before I forget I want to go declare this types variable up here there I have my seven types and what makes this useful is if I add more types of terrain I can just change this variable right here to match the types of terrain I'd also need to add some more shades and the code will work perfectly well so I'm trying to make this very general in case as you probably should you want to add some additional terrain some deserts or some beaches or whatever other types you would like now I have my temporary type and I need to calculate how many conflicts this results in so I'm again going to check for conflicts at this location and if I've improved I want to remember that so there we go if my new temporary type results in fewer conflicts then that becomes my new best type and the idea is at the end of all of these tries so down here I'm going to make that the new type to put in the cell and the one thing that I failed to do is before I check for conflict I do need to fill in that temporary type so pick a random terrain type say planes put it into the map see how many conflicts that generates if it's fewer than the number I used to have remember that is planes are the best terrain type so far but then I'm going to try a few more Ty times and maybe I'll randomly fill in a forest or a deep water and see if any of those result in fewer conflicts the other thing that I need to do is at the very end I'm going to return whether or not I would was successful I'm going to say that if I have to correct any of the train type so if I have a conflict that is larger than zero My Success is false it is possible that down here I'll correct that conflict and I'll have a perfect map but I'm still going to return false and that means I'm going to call this function one more time and I'm going to try and fill in all of these different cells and if for every single one of those cells I don't find any conflicts then I'm going to assume that the map is perfect it's not necessarily the case if we want to be very technical it's possible that there's a conflict in the map and I just happen not to check that cell but that's okay I'm at least for this sort of procedural generation if we've got one mountain in the middle of the Plains I'm not going to worry about it too much if it's something that you really have to avoid what you want is a separate function that does go through systematically and checks every cell and if none of them have a conflict then you're confident that things are fine now what I need to sort of finalize this is to put in my check conflict function and that is given a particular XY location and checks the terrain around it to see if there are any conflicts it actually counts the number of conflicts and returns how many there are and what I I want to do is from that XY location check the cells in a neighboring region and I'm not necessarily just going to check the neighboring ones I might want to check two or three cells in each Direction so I can check a wider patch and that ends up being a parameter that you might want to play with so I'm going to put in here a range of cells that I will check around so this is the idea I'm going to start start at the negative of the range so from whatever cell I'm at I'm going to check three to the left and then I'll go all the way across to three to the right checking to see whether there are any conflicts and I'll do the same thing from top to bottom and so I need my sort of temporary value so there's my temporary x value it's the X location plus this Delta x 3 over 2 over 1 over Etc but I have the problem that if I'm at the left edge of the map If I subtract three that's going to be put me all the way off the map so I add the width which will allow me to wrap around if necessary and then in addition I'm going to do a modulus of the width of the world so that if I go too far to the right off the map to the right that will wrap me around to the left and I need a TX variable and I'm going to need a Ty Vari variable here in just a moment as well cuz I'm going to do the same thing for Ty there we go so that gives me my temporary locations that I know to check against my XY to see if there's a conflict if there is a conflict what I'm going to do is add it to my running sum of the number of conflicts so conflict we add to that and I'm going to do it this way and then explain it I'm going to look in an array of which terrain types are not allowed to be next to each other so it's going to be a two-dimensional array a table basically saying mountains are allowed to be next to mountains but mountains are not allowed to be next to water for example so I look at my central location the XY location and compare that in the table to this temporary location what is the train at my center location versus what is the train at the neighbor one that I'm checking and is that allowed or not allowed and for the not allowed like I said I'm just going to create a table of not allowed values and I want to go up here and make that a global table so there's going to be my two-dimensional table and for example the first row is going to be comparing Undeclared to all of the other types and so UND declared can be next to anything so I have my seven types an Undeclared type can be next to any other type and then make this nice and readable by putting the next row underneath now I do mountains mountains can be next to Undeclared mountains can be next to other mountains and I'm putting in a zero for allowed in part cuz if it's a one I'm adding it to the number of conflicts and then mountains can be next to Forest but mountains cannot be next to Plains cannot be next to water cannot be next to deep water but can be next to high mountains and then I'll just fill in the rest of that so this is talking now about Forest which can be next to Undeclared mountains Forest itself or next to Plains but can't be next to water or deep water or high mountains there always has to be mountains between the high mountains in the forest and then these are the other rows so for example high mountains can be next to Undeclared can be next to mountains or can be next to other high mountains and with that I think as long as there are no errors this should run see here we go incomplete because I forgot to close my two for Loops down here at the bottom and best type may not have been initialized so I do need to give this at least an initial value I'll do it is Undeclared and that is all black let's see and I see that least conflicts is not being used that's because my check here should use least conflicts and then the one other piece of code that I'm missing is I'm never actually calling my least conflict so let's put that in there we go and now I should be able to run this and you can see the map slowly resolving it's basically going through and on each iteration it's picking a bunch of random Loc ations to fix the conflicts to minimize the number of conflicts and it takes several passes which is why the map doesn't settle down immediately and if I run this again we get a completely different map and you could see it took a little longer here to sort of resolve all of the conflicts I have my stroke in so you can see the edges between the cells we could add the no stroke command to get rid of that and a couple of other things I talked about one is the range that we're checking for conflict so if we come down here to my check conflicts the range I'm using is three so if I have for example high mountains there can't be anything except mountains within three of them so that gives me a fairly wide range of mountains if I were to change that to something like two you get sort of a higher resolution grid we've zoomed in a little bit so now we can have planes closer to the mountains and I took off the stroke so you don't see see the cell lines if we make this a range of only one then you can see it's even more detailed because now we can have mountains that are only one away from the plains for example so we can adjust the resolution of the map in a sense by using the range and also of course the cell size another thing that's nice about this approach is it wraps correctly so when I'm checking for conflicts I'm wrapping around the map and so this bit of mountain here aligns with this bit of mountain over there it's now not too hard to go in and say I'm going to add some more terrain types so we would put in additional terrain types we would expand the not allowed map and we'd put in some more shades and you can H create all sorts of different Maps if you want another thing that's sort of interesting here is this is giving us sort of a uniformly filled in map if we want to put in particular structures all we have to do is set some of the initial values so let me show an example of that and I think I will set my range a little larger I kind of liked it at three and the idea is here when I'm creating my map and filling it in with all zeros I can instead say well I want some regions of my map to be deep water so the way to do that is to look for particular parts of the map that are in I'll do this as a distance from the center so this is calculating the distance from the center and if it's larger than 75 I'm going to make the type five which is deep water and there we go I now have instead of a uniformly filled map I have an a circular map based on distance from the center and I realize I used World width here instead of world height so it's up a little not actually centered so this gives you a slightly different map structure and by setting these initial conditions you can create all sorts of different map shapes so a nice way of procedurally generating Maps using this idea of minimal conflicts local search and as I showed before in addition to Maps we can apply this exact same idea to all sorts of other problem cases for example to grow the these plants that I have in my background I'll show you the code running and I've slowed it down so this is doing one frame per second and you can see the updates here where it goes in and removes or changes the cells that have a conflict and there's a couple of things that I did a little bit differently here that are worth talking about you'll notice at the very bottom everything is all green so the bottom row is always green and then as I mentioned before when I look for conflicts I do it from the bottom working up systematically the rule here is a cell can be green if one of the three cells under it is green and then I put in another rule that said a cell can be red if there is a red cell above it or a green cell above it and so that gives you these little sort of Droopy berries I guess the idea is you can make up whatever rules you want and it will go through and systemat aut atically search for an image that doesn't violate them but there are lots of possible options so if I run this again and you can see it resolving the conflicts as it goes we get similar but certainly not identical plant structures and then the third example I showed just happened to do the same thing in 3D and this is actually quite similar to the previous rule set in terms of you can have green green if there's Green in one of the nine cells underneath and you can have red if there's red or green above so the general idea for constraint satisfaction problems is we create rules for what values are allowed in our cases in a grid and then we systematically go through and change values using a minimum conflicts local search in order to find a set of value vales that satisfies our rules and allows us to procedurally generate all sorts of different structures Maps plants Etc and it gives us a fairly simple framework to build from because once we have the basic idea as I said using Maps as an example it's very easy to go in and put in more types of terrain and different restrictions on them we can increase or decrease the range and so forth if you have ideas for projects that could benefit from this sort of procedural generation please put a comment down below I'd be thrilled to hear about them and of course if you've enjoyed the video I encourage you to like And subscribe I have lots of other videos on procedural generation and other creative programming projects finally thanks for your time and Happy coding

Channel: Programming Chaos

Views: 2,695

Keywords: maps, procedural generation, Soule, tutorial, programming, java, processing, gamedev, fractal, wave function collapse, WFC

Id: gKNJKce1p8M

Length: 32min 35sec (1955 seconds)

Published: Wed Jul 10 2024