Make a 3D Top Down Shooter with Godot - Part 2.4 Map Connectivity with a Flood Fill Algorithm

hello folks welcome to the age of asparagus and the fourth part of phase two of making a 3d top down shooter in godot by the end of this video our level generator will place objects in such a way so that the center tile will always be open for our player to spawn in and we'll use a flood fill algorithm to prevent objects from cutting off any part of our level so that all open spaces remain connected okay the first thing we want to do if i hit 7 here to go into top down view is i want to make sure that the center of our map never has an obstacle there because that's where we want to spawn our player so if i click on the map and just change the seed here you can see that our obstacles can be generated there that should be pretty easy so let's go to our map script and at the very top of our script here we're going to create a new variable and we'll call it map center and we want this to be a quart object our custom inter coordinate class with an x and a z value and we're going to set the map center anytime that we change the width or the depth of our level so let's go to the width and depth setters and underneath that we'll create a new function and we'll call it update map center center center and we can say map center equals chord dot new and we'll set it equal to the map the map width divided by 2 and the z value will be the map depth divided by 2. and we're going to want to call this method before we generate our map after we update the width or the depth okay and then the last thing we're going to need to do is down in our add obstacles method right before we add the obstacle let's just check and make sure that we the coordinate where we're trying to make the obstacle is not the map center so let's go if quart does not equal map center then we can create an obstacle here now this isn't actually going to work if we change seeds we're still going to get obstacles appearing in the center and that's because oops let's save that and give it a try we're still going to get obstacles at the center and that's because gdscript doesn't know how to compare two coordinate objects those are a couple that's a custom class we created so these are objects and these are not the same objects so they're not going to be equal and unfortunately we can't override operators in gdscript at least uh that did not appear to be the case from my scouring of the documentation uh however we can just create our own little equal method so let's do that up here in our chord class let's just go funk and we'll call it equals good enough right and then we're going to pass it another chord and then all we'll do is we'll return let's just type in the kind of easy to read way we'll go if chord.x equals x and this you could also put self.x here if you just wanted to be clear and chord dot y zed equals self.z then return true and we could have else return false but just an easier way here is we're just going to return that so if the coordinate that we're providing the equals method has the same x value and the same z value it'll be true okay does that work uh let's get rid of that it's no longer an if statement good so now when we go down we can compare two coordinates here we can go if chord dot eek will now because this is in a in a loop here in an iterator we can't provide type hints for this so instead let's just let's use the map just to make sure we're doing it right let's use map center dot equal equals and then we can pass it the chord um and then we want to say if not right because if it's not if they're not equal then we can create an obstacle let's try that and go up to 3d view here and it's promising so far but let's just try a few seeds and then make sure we don't get anything appearing there and that looks pretty confident and of course if we turn our obstacle density up to max we should get everywhere except for the center a little bit of lag there okay okay now the next thing we want to do is we want to make sure that our level doesn't generate these little pockets if our player is spawning here and an enemy spawns here or here the enemy isn't going to be able to find a path to our player and the player will be stuck and this will be a pretty dumb game so as we're placing obstacles we want to make sure that no sections get cut off not even little single ones where enemies could possibly spawn and just get stuck and unable to leave and we're going to do that with a flood fill algorithm which if we go here and we reduce the obstacle density a little bit to something like this and actually you know what let's let's reduce this rate down to a width of five and a depth of three something really simple here and i'm going to go to seed one two four one seven and i'm hoping you will get the same result if you enter that seed as well and i'm gonna have an obstacle density of 0.3 okay so as we're placing obstacles we need a way to determine whether placing a new obstacle let's say we've placed these three and everything's good and then now we're going to try and place this obstacle and we want to determine whether it cuts off a section of the map and what we're going to do is we're going to start at the center of the map since we know that one's going to be open and we're going to use a flood fill algorithm and you can imagine if this was a paint program and you dropped your paint tool right there you can imagine that all of this would fill up with paint and then what we're going to do is we're going to compare how many coordinates how many of these cells ended up getting filled with paint compared to how many we should expect to fill up with paint if everything was open then these would fill up with paint too and we could go oh yeah the amount the number that filled up with paint equals the number that we expected to however in a case like this we'll go wait a second we only got seven squares filled up with paint whereas we were expecting 11 and then we'll know well this object cannot go there we'll remove it and then we'll try another place so algorithms are pretty fun but when you just go dive right in and write them in code especially for people who've never seen them before it can be pretty confusing so i'm going to explain as best i can how the flood fill algorithm is going to work in the way we're going to implement it okay so let's say this is our level and so far our level generating tool has placed three obstacles at two zero three zero and three one and the next obstacle it tries to place is at tutu now we're going to run our flood fill algorithm to make sure that the map is still fully connected and obviously it isn't here you can see these four squares have been cut off but let's walk through the process to see how that's going to work so i'm going to run through some of the data and variables we'll need to complete our algorithm here we'll need an obstacle map variable to hold the position of all the obstacles in the level that looks something like this since the obstacle map is a two-dimensional array where this would be zero zero this would be zero one and this would be zero two so we're talking about this spot this spot and this spot and then the next element in the array would be the next column so to make this a little easier for us i'm going to display this a little differently i'm going to display that same array like this so visually you can see that it matches whether there's an obstacle in these three cells in this column so false false false and then you can see how we get our full map and if we add the array indices you can see this maps nicely to our x and our z coordinates and it becomes really easy to see how these true values map to the location of our obstacles in our level so as we conduct our algorithm we're going to need to track which cells we've already checked over so we're going to do the same thing we're going to create a two-dimensional array of boolean valuable values that will be true if we've already checked that cell and there it is we'll initiate them all to false because we haven't checked anywhere we're also going to create another array chords to check and that'll be our q for which cells we need to look at next and to initialize this process we'll throw in the starting cell the very center 2 1 into our array and that's all it will contain at this point and finally we'll create another variable that'll hold the current coordinate that we are checking as part of our initialization we should probably also set the fact that we've already checked the center tile 2 1 and so we can set that to true and what that means is we've already considered it we maybe have already put it in the queue maybe a better name for already checked would be already cued or something but i'm going to use already check not to be confused with the fact that we still actually need to run the algorithm over it okay so i'm going to write a little bit of pseudo code here that's just going to outline our algorithm and then we'll walk through it and see how it works so we're going to start with a loop that checks whether there are any coordinates left to check we're going to be pushing and popping coordinates in and out of our chords to check array and as long as there's something in here the loop is going to continue so we'll pop the coordinate we're going to loop through its neighbors and then as we loop through each of its neighbors we're going to make sure we don't go off one of the edges we're also going to make sure we haven't checked here yet we're going to make sure it's not an obstacle and if all those things are true then we're going to add it to our coords to check array and then finally we'll mark that coordinate as already checked so again i'm sorry with the confusing terminology here uh the way i named them but we're going to mark it as checked which means we'll mark it true in this array when we add it to our queue of which ones we want to check over really this should say already added to the chords to check maybe would be better but and i'm just going to change the coloring here to coordinates that are already checked in an actual flood fill algorithm this might be the point where you actually this pixel gets filled up with the color you're filling it in an actual like paint program for example so i'm just going to change this over to cyan to differentiate the colors make it a little easier to follow okay so let's go through this let's try it we'll start at step one here while there are any coordinates to check yes we still have one so let's go into this loop we'll pop a coordinate let's pop out the only value in the array and we'll assign it to our current coord variable and let's loop through the neighbors now we're only worried about the neighbors that share a full edge we're not worried about diagonal neighbors here because enemies won't be able to pass through that corner and similarly in a flood fill depending on the algorithm the color might or might not leak through corner like that so let's start with this neighbor the order of the actual neighbors will depend on how you implement that loop in code but we'll start with this one uh coordinate one one does it go off the edge nope have we checked here yet well we can see we haven't but let's check in our already checked we got false so we have not checked and is it an obstacle obviously it's not but we will be checking our obstacle map 1 1 is also false so we'll add it to our coordinates to check 1 1 and we'll also mark it as checked so at 1 1 this will become true which is like painting that pixel with the color now we're still in this loop here so we'll go to the next neighbor and go through the same process so we're not going off an edge we haven't checked here yet this is 2-0 and it's not an obstacle 2-0 actually it is an obstacle so we're done with that one and we'll move on to the next one you can see what's going to happen it's an obstacle so we'll skip that one it's an obstacle so we're going to skip that one now we're done looping through the neighbors we end up back on our outer loop to check again if there are any more coordinates there is there's a new one so let's pop it and we'll start looping through its neighbors so we'll have these four let's start with this one again it doesn't go off an edge we haven't checked here yet it's not an obstacle so let's add it to our coordinates to check this is zero one and let's mark it as checked moving on to the next neighbor we don't go off an edge we haven't checked here yet and it's not an obstacle so we're going to add it 1 0 and we'll mark it as checked the next neighbor here we don't go off an edge we have checked here already as you can see we're going to check this one right here 2 1 we have checked so let's carry on to the next neighbor doesn't go off an edge haven't checked here i think you're getting the idea right not an obstacle so let's add it to our queue 0.12 and mark it as checked okay so are there any more coordinates to check there are a bunch of them so let's go ahead let's pop one of the coordinates we're now looking at zero one so here we have it we're going to loop through the neighbors this one goes off the edge so we're going to ignore that one this one we haven't checked it's not an obstacle so we're going to add it to the queue and mark it as checked this one we've already checked this one looks good add it to the queue looks like we're on a space and we'll mark it as checked should have been flood filling these as we go these pixels get filled in now in our game obviously we're not coloring the blocks filling in pixels we're just marking them in our two-dimensional array that they are open and free and accessible from this point in some way so i'm just i'll just do one more here let's pop the next coordinate one zero and we'll go through its neighbors we're now on this one and you can see here this neighbor's off the edge this neighbor's an obstacle this neighbor's already checked this neighbor's already checked nothing to do pop the next one one two same thing pop the next one zero zero same thing pop the last one zero two same thing so at this point in our loop while there are coordinates to check this chords to check array will be empty and our flood fill algorithm will be complete if we were creating a painting program all our pixels would now be colored however we're not painting we just want to know if the whole map is accessible so how do we use everything we've done so far to determine whether the map is accessible visually it's obvious but how does our code know that what we're going to do is we're going to compare the number of tiles that should be accessible to the number that actually are accessible so we'll have a target count which is just going to equal the total number of cells less the number of obstacles which in this case this is a five by three the total sales is fifteen the number of obstacles is four so we'd expect to have eleven tiles accessible one two three four five six seven eight nine 10 11 and what we'll do is we'll compare that to the actual count which is one two three four five six seven and actually there's one little extra step in here we're going to want to do is we're going to want to increment every time we find an accessible one we're going to increment a count variable which will be that one so every time we mark one of these blue we'll add one to it we can compare the target count with the count and if they are the same we can return true which means adding this obstacle will keep our map accessible but in this case adding this obstacle blocks part of the map because the target count is not the same as the actual count and the method we'll create will return false and after we do that we'll remove this obstacle and we'll try and place it somewhere else and we'll repeat the process okay let's write this in code so let's start go back up to the top here and we're going to create a new variable and let's just do it underneath our map chords array because this is going to be another array and we'll call this one our obstacle map and we'll just set this equal to an empty array and somewhere down here we will add we'll need to fill up our obstacle map so let's do it underneath the fill map chords array method create a new function called fill obstacle map field obstacle map so our obstacle map is going to be a two-dimensional array of boolean valuables true and false so let's start by setting the obstacle map people equal to an empty list empty array obstacle map and then we're going to loop through the x and the z values the width and the map so now here since we're creating a two-dimensional array every time we loop through an x value in the width we're going to have to append and empty another empty array this will create our second dimension so obstacle map dot append and we'll append an empty list and then as we loop through the in this case for example like our three z values in the depth we will obstruct why don't you like my oh comma dot append there we go yay okay uh obstacle map obstacle map and we'll take the x in the first dimension and we'll append the we're going to append false because we're filling it up with boolean values where true is an obstacle and false indicates there is no obstacle there and if you just wanted to check that this is working of course you could print the obstacle map and we scroll down of course we never call phil obstacle map so we should do that now and we'll do that at the top of our add obstacles method so we fill the map chords array and then we'll fill the obstacle map and when i save it here you see of course it's going to do it a whole bunch of times but if i clear that and then just update the seed you'll see it's a 5 by 3 dimensional array just like our width and depth and all those indicate cells with no obstacles okay so let's jump in we're going to need to create a variable here that's going to hold our current obstacle count and we'll set that equal to zero and then what we're going to do is ins before we place the obstacle permanently we're going to make sure that the map is fully accessible but to do that we actually need to temporarily create the obstacle so we'll actually create it and then we'll also increment our current obstacle count so we'll go plus equals one we'll also set our obstacle map to true at this point so this is going to be chord.x remember this is two-dimensional array and then chord dot zed and we'll set that value to true and then once we've registered the obstacle there in fact we even created it which we don't need to do so let's comment that out we're going to create it that could probably be a big performance hit right creating the obstacle actually creating an obstacle in the scene and then deleting it after if we find out it's bad really our algorithm is only going to use the obstacle map this boolean value so we don't need to actually create the obstacle here okay so now we're going to check if the map is fully accessible this is the method that we're going to create our that contains our flood fill algorithm and that is not close to how you spell accessible accessible maybe and we're going to send it our current obstacle count so that it can check to make sure it can fill up all the open spots that it's expecting to and if the map is fully accessible then we will actually create the obstacle here at xz otherwise we're going to want to remove the obstacles so what we'll do is we'll take away that count minus equals 1 and we'll also set that location back to false again because we never actually did create the obstacle in the scene all right so now the last biggest step here is we need to create our flood fill algorithm so let's do that right below here new function map is fully accessible and this is our flood fill frodo fill okay some variables we want we already checked here and that's going to be remember a two-dimensional array of boolean values as well so we're going to have to initialize that let's go up to our fill obstacle map and do the same thing here how'd i land there we go so we'll go for x and range map width and this time it's going to go we already checked here and we'll set fill up this two-dimensional array with false values another variable we're going to need is chords to check and we'll set that to that's going to be a list and we're going to start with only the map center in there we initialized our we already checked here to false everywhere but we actually want to set the map center as true so map center dot x and map center dot zed we'll set that one equal to true because we have already checked there and the last thing we're going to need is our accessible tile count which we will count up every time we check a tile and it's good it's empty so we'll set that equal to one because we're starting with the map center which we know is already accessible so like i explained in the algorithm here we're going to start our code so the loop is while we have chords to check oopsy chords chords to check and you could check if this is an empty list but similar to python gd script will if this is an empty list it will be a falsy value and it'll break the loop so we can write it like this it's much easier to read we can print things along the way but i think i'm just going to plow through this since i spent quite a bit of time explaining how the algorithm works so let's go we're going to set our current tile equals chords to check and we're going to pop what methods do we have front or back it doesn't really matter so let's just pop from the front that's going to remove the value this is now going to be an empty list and we now stored the map center in the current tile and now we're going to loop through the neighbors so we'll go 4x in and i'm just going to put negative 1 0 1 here and we'll go for zed in again negative one zero one so these are the offsets from our current position from the current tile that we want to check so let's create a new neighbor coordinate neighbor equals chord dot new and we'll give it the value of current tile dot x you know what let's uh let's give this a tight end of chord because i just you know i like the autocomplete to save my horrible typing skills and current tile dot zed didn't seem to help did it let's uh not print out i'm just going to jump up here and not print out our obstacle map don't need that okay so we're going to set our neighbor to the current tiles x and z offset by the values in these loops so we're going to add the x value which will be negative one then zero then one so we're going to kind of go in a ring around the current tile plus zed let's add some spaces in there now we we don't want diagonal neighbors so if the x value equals zero or the z value equals zero then that means it's going to be a non-diagonal neighbor because if it's negative 1 and negative 1 it's a corner if it's a 1 negative 1 it's a corner either this x or z value has to be 0 for it to be like a horizontal or vertical neighbor that should have been a comment and in fact why don't we move this variable creation into the loop so we're not creating unnecessary tons of unnecessary variables next we want to make sure we don't go out the map which i think i'm just going to put into a different method to keep this a little cleaner so we'll just say if on the map and then we'll pass it the neighbor coordinate and we can create that here function on the map let's get these errors away for now okay so how do we know if we're on the map well let's just return this will be true we're on the map if neighbor dot x is greater than or equal to zero and neighbor dot x is less than the map width width and neighbor dot z is also greater than or equal to zero and neighbor dot z is less than the map depth i'm going to pull that in and see all the code hopefully that makes sense we'll find out soon enough if it fails if i screwed up my logic there so next we're going to check if we i you know what these comments are kind of pointless because the way the way i'm naming my functions is kind of self-documenting right so the next one is going to be so if we haven't already checked there so if not we already checked there in not would help if i if not we already checked here and we're going to give it the neighbor dot x and neighbor dot z if not we already checked here so if we already checked here is false we haven't checked here then we can keep going and if it's not an obstacle so if not obstacle map same thing actually i can probably just copy this whole this is also a nested list so there's no obstacle if we get here there's no obstacle we haven't checked here yet it's on the map and it's a non-diagonal neighbor well that looks like a hit right that means we can fill this with paint which in our case is just setting we already checked here to true except instead of the map center we're going to set the neighbor's value to true we're going to add it to the chords to check which really means the chords that we need to check their neighbors on still and we'll append the not chords to check we'll append the neighbor we're gonna increment our accessible tile count and that's that is our algorithm loop here so the only that's gonna go through this is our flood fill and the only thing we need to do now is after our whole loop is finished we need to go check that we were able to fill up the target number of cells so let's create a new variable called target accessible tile count and that's going to equal our map width times our map depth so that's all the cells but then we're just going to subtract the current obstacle count that will tell us how many cells left should be open if we were able to flood fill the entire map so that's our target obstacle count and now we can just check if the target obstacle count target accessible tile count sorry is equal to the actually accessible tile count that we've been counting up as we fill the flood fill the the map then good location and we can return true else bad location cuts off a part of the map and then we'll return false so when we return false let's get rid of some of this extra space here when we return false remember up here when we're adding the obstacles if map if what that should say map is fully accessible so if the map is fully accessible if that turns out to be false oh we'll subtract that temporary obstacle we place there and we'll remove it from the obstacle map and then we'll the loop will go through to the next possible location for an obstacle and it will try and place it there i'm a little nervous let's do it did it work we're not getting errors that's a good sign um it's looking good i'm not seeing little pieces cut off let's go big let's go big go big or go home fill this up looks good let's let's crank up the uh obstacle density here you see anything getting cut off oh this is pretty neat isn't it let's crank it right up yeah that worked it worked so cool uh let's let's see if we can just make this as big as we can go like which i think was like 20 oh this is going to get a little bit of lack here because we do not have the most efficient flood fill algorithm um but i think it was a 15 by 19 15 by 21 okay and i'm just gonna pop the seed here and give it a moment to do all those calculations and it seems to be working and the center tile's always empty there's nowhere an obstacle could spawn that would cause them to get trapped what about right there uh nope you can come all the way around here all right and if we reduce that it should go oh whoa that was some lag uh before we finish let's remove these print statements because these are actually the most inefficient part of our code at the moment causing the most lag um and that'll speed up our flood fill algorithm all right well that was cool and fun i hope you enjoyed that i hope it was easy enough to follow along i know um fancy algorithms like that are take a little bit of time to wrap your head around i'm hoping to get the opportunity to explain and code a few more algorithms like this i enjoy doing it i love playing with them until next time

Channel: Age of Asparagus

Views: 544

Keywords: AgeOfAsparagus

Id: wePC460mmVA

Length: 32min 51sec (1971 seconds)

Published: Mon Apr 26 2021