Maze Generation Unity Tutorial

in this video we look at how to generate mazes procedurally using the recursive backtrack or algorithm we will be writing unity independent c-sharp code to generate the maze so let's get started welcome to game dev with Sun lead if you liked the video consider subscribing so what is a maze if you think of your map has a grid of nodes then a maze is essentially making a set of paths such that each node is connected to another by at least one path if you place walls between the nodes that aren't connected by law you have a maze there are quite a few means generation algorithms but we will be using the recursive backtrack oh here is how it works choose a random current node shown here by the red cube and add its position to the stack select one of its unvisited neighbors and break the walls between them move the current node to the new position added to the stack and repeat the process till we reach a dead end once at a dead end we backtrack through the visited nodes by removing elements from the stack trying to find a node with nonzero unvisited neighbors once found we repeat the process till there are no more elements in the stack at that point the maze is complete let's look at the code now let's start by creating a scripts folder in our project that will hold all our scripts and let's create a maze generator script first now in our main generator file we first need to describe what each node is we could define a node as maybe a struct that holds value like boo left wall public pool right wall and so on but instead what you could do is use a flag 'inna for our purpose let's define a flag dinner where each bit in the bit representation denotes whether a node still has a wall or not give it a more descriptive name something like wall state and when I mean each bit so something like 0 0 0 would mean no walls in that particular cell and all ones would mean left right up down all the walls in that cell are still standing so to define this we can just go left is 1 which means 0 0 0 1 in bit representation right is 2 again 0 0 1 0 so each of the bits as I said up is 3 so 0 1 0 0 and down is 4 so the first bit yeah now to use it as a as a flag what you need to do is you need to add Flags attribute and now this can be used as a flag what this means essentially is you can do things like wall state is dot left and if you do the pipe operator that applies wall state dot right and if you do this this essentially means 0 0 1 1 you can add more state to this we're just doing pipe equal to IP co2 all set that up this makes it triple one and to remove a particular flag you would do wall state tilde equal to sorry and equal to tilde wall state dot right and this would make up the bits essentially 0 1 0 1 so each of the cells each of the nodes in our map can be represented using this ena so let's first convert this class into a static class and remove the monobehaviour we will be returning a public static you will be creating a public static wall state 2-dimensional array and we will call this function generate and this will return all the means right so what this would mean is say in width and n type will also give it the seed later but for now let's just use a random seed and let's actually complete this will give it flipped in height and then will sit on the mayor's so that will complete our initial implementation of a median it returns nothing essentially it's an empty means nothing has been done to it but what we could do is actually fill it up properly so in I equal to 0 and I would be less than width and I plus plus let's get another one and J equal to 0 J less than typed plus J and then you would go means I comma J is we want all the walls to be standing in the in the initial each of the cells right initially so what you could do is well state dot right I have all state dot left eyeball state dot and we'll start down we should move this out into a different variable out here all state in your show is this and just just assign this right so that should set it up and what this will do is create a bunch of cells in the 2d array means where all of the values essentially all the values of the bits are going to be one one one one right and then we can use this with something like a has flag check so you can do this and you can check all state dot right and you can check stuff like this this returns a bool and you can do stuff like this to like actually initialize and instantiate the wall prefabs on the monobehaviour side right so let's do that now so let's head back to unity and create a new script let's call it means rendell have a generator and now we have a renderer as well and create an empty object that will hold this is call this means render as well and give this add this component here and what will our means render I need it'll need a wall you need a wall that will render everywhere right so let's create an empty 3d object let's need a cube rename this to war and this is to please the said besides of this so this is what it looks like from the top and giving you prefabs folder will drag our wall not the maze render the wall into the prefabs folder and let's just delete that will also move the camera up so that it's let's see what it looks like if the walls that the camera should be looking down at it so let's move this up again bring this to zero and let's rotate this by 90 so that it the camera is looking down as you can see on the BM scene you can see that one wall will probably need to move this a little further up so that it can see the whole maze when it's rendered but we'll get to that eventually um okay so the walls already ready the camera is properly set up as well let's go to our Me's render class and set it up so that it accepts the knees generated by the machine later class and then draws it now in our means render class let's first set up variables to control how big our maze is so we will serialize this field because you don't want to expose this private and oh let's make it a UN so that it doesn't go below zero width and serialize field drive it you and time right we got our negative values for these so these two will define how big army is is and then let's just initialize these would say ten ten and then what you can do is essentially get the maze from the main generator dot generate and you just pass in the width in the height and we can call it draw function which accepts the maze and the width it doesn't need to which tonight is it so essentially private wide throw and what it will get is a wall street array and it just needs to draw this right that's the problem you're all right our main generator needs ends and our main renderer gives it you went so let's just fix that as well he'll be careful not to pass him negative values I guess you could also like set up range values so that it never goes below zero so we could do range one to say 50 and range 1 to 50 here as well and that will that'll set up a basic basic draw function what we need to do next is maybe called draw instead of calling it on start we could maybe call it on on validate so that it draws every time we change the values but we'll get to that as well next thing you need to do actually is to actually link the wall prefab we created so that we know what to instantiate let's keep this tuned also that unity doesn't complain about this being never ins initialized you need to give it the wallpaper so where is it let's drag that in we'll head back to our maze render class and fill in this draw function so given this means we just need to eye trait over the all the cells of the mains right so we'll go eyes less than width I plus plus J equal to 0 3 less than height and plus plus J and you'll say cell is mazes I Comanche right and for what we need to figure out is if you need to set the position of the cell given the width in the height would be war position is essentially a new vector3 - width by 2 plus I 0 - height by 2 well Jake what we're doing here essentially is that the that the position of each cell is now offset from the center by width by 2 so that the middle of the means actually sits is exactly at 0 0 so now that we have the position we can check it each of the walls exist right so if cell dot has flag wall state dot say up we can place the top wall right so we go top wall is instantiate the wall prefab let's give it the transform so that it becomes a child of the maze general and then the top wall needs to be offset from position let's make this as transform and drop all needs to be offset from the carpet the self-center buy exactly position plus new vector3 so 0 in the x axis 0 on the y axis but 0.5 in the z axis so it's moved up right the 0.5 is actually the size of the of the prefab itself so we could use the local scale of the prefab or you could actually expose a size variable which says how big is our each cell in the node so let's set this to be 2.5 you'll also see realize this and then we can just do size right and I think something has to be done here as well but maybe we'll get to that later we also need to set its local scale so that it matches the size that we defined in terms of so we need to reuse its its thickness needs to remain the same because we set that as a 0.1 in the prefab right but it's x value its actual size along the x axis should be the same as the size of the cell so that it completely cover comes a wall of the whole cell so this is going to be size and actually size is right right right size is the size of the whole cell so let's make that one and this is going to be half of the size you want to move the wall halfway because from the center the top walls position is halfway up so the local scale would be size comma 0 comma sorry you know 1 or actually top wall local scale dot Y and top wall local scale dot set so we just in in the X so that the walls width increases right let's check it let's check it if the cell has a left wall no I'll stay left war left wall and will be instantiated as transform then similar to the top wall we're going to set the left walls position to be position plus an offset essentially where it's going to be minus size by 2 because it needs to move to the left by exactly half of the size of the box and zero comma zero now if you remember our prefab was set up rotated to be along the x axis but the left wall has to be rotated 90 degrees as well so let's do that by just setting the Euler angles right we're just going to say vector 3 this is 0 comma rotated 90 degrees on the y axis and 0 all right we have two walls so not all cells need to draw all their walls if you just draw the up and the left walls most of the cells will be covered you can actually see that let's go check it out right now if you let this run the size is set equal to 1 and we set the width to be say 10 and this is also 10 we click on play right now they should create a nice little grid structure this is all the cells all the box so the first cell here say this is actually the last cell so this cells right and bottom walls are drawn by the adjacent cells right so we don't need to draw all all the walls but you need to draw them for the this this row and this column so we only draw them if F here on the on the last column so that's I equal equal to with this minus one right so this essentially says that we are in the last column then we can just do all the other checks as flag in case one of our outer walls don't know don't need to exist we don't know how the means is going to then generate this right so we will say you say we on the last column you'll check if two cell has a right wall and then we just need to do all of the things that the left wall did right so let's rename this right wall and right wall position is the opposite of the left wall so it has to be offset in the positive direction by sides by two this also has to be rotated and of course the scaling has to be done for all of them so we will just add this left wall add this for the right wall as well all right sorry all right all right wall right now you also need to check if it's the first row so if J is equal equal to zero we will do the same calculations again so if cell has flag wall state dot down right to downward was missing there let's just copy the top wall for you and we just replace this with bottom more instantiating this as just like the other walls the offset has to be in a negative - sighs way to write it has to go down and the scale is the same logic to the scale all right this should enter all the phases that we are looking for if you do this now there you go it actually generates a full grid of all the walls so a renderer is just working perfectly if we remove if we change the big flag of one of these cells the wall should automatically not render right the thing you have to watch out for is that if we remove say for example here on this cell and we remove the right wall we also have to come to this cell and remove the left wall now coming back to the means generator class I actually realized I made a big mistake here the enums need to be four and eight that's what the bit representations mean three is not three is not zero one zero zero so anyway for the recursive bath tracker we need to add another enum to this which is essentially visited we will set this to 128 which would be the first bit in 8-bit representation right so it won't interfere with our walls at all and is going to sit far away right here okay so you're going to use this to mark a particular cell as we visited for the recursive backtrack or the other thing that we need to do is add a public car stock position this is nothing but an XY coordinate for us to keep track of which coordinate we are in the means while we're generating and as I mentioned earlier when you are breaking a wall or removing a wall between two nodes when you're drawing a line between two nodes we need information about which wall we are breaking right so we use a another struct called wall break to hold that information it's essentially going to contain the position of the neighbor we are breaking the wall with and it's also going to can have the wall that we are sharing with the neighbor let's call this shared wall so from the nodes perspective which wall is shared with the neighbor which is described by this position let's actually rename this to a neighbor so this makes more sense and we call this position so the neighbor Sprott essentially contains the position of the neighbor and the shared wall from a particular cell the next thing we need to define here is we need to define a function that returns all the neighbors at a given position that are unvisited so how will you do that is essentially I trait over all the directions check if that neighbor is visited has the flag visited or not and then return added to the list and just return that list so we're going to be using a static function again which is going to return a list of neighbors and it's going to be get enables us be more descriptive get onion visited neighbors and we're going to need a position with P and the hole means right to check through and the height and width of the mail you don't want to be checking out of bounds so we so let's create a list you know list neighbor and it on that list will fill that list up in the middle here the first check we need to do is if P dot X is greater than zero which is I mean you're checking to the left right so you need to make sure that you can use a practice properly you say if you means P dot X minus 1 and P dot Y but has flagged all state dot visited actually need to check if it doesn't have the flag if it doesn't have the flag we'll add it to the list right new neighbor add position is P dot X X is P dot X minus 1 and Y is P dot y and shared wall shared wall would be the left wall now we need to repeat this for all the directions so let's just copy this whole thing we will check for y as well if Y dot Y is greater than 0 which means the bottom walls right so we'll let P dot X P X and P dot y -1 if it's not visited let this be we will subtract minus 1 here and the shared wall is towards the bottom so you check to the oh it's not bottoms or it's down right so down we need to do something similar for the other edges so if P dot y is less than with minus 1 sorry height minus 1 this would check the up wall so we can do P dot y plus 1 is not visited then the position was bigger plus 1 and this is up and let's just copy all of this paste that and B dot X is less than width minus 1 so this is right wall let's do this here and remove this and plus 1 and this is further right wall so this should return a list of all the neighbors that were unvisited by in the maze still so let's start setting up our recursive backtrack or a lot of them it's going to return our maze right just call it apply the cursive back tracker it's going to accept on Mia's and it's going to accept a width and a height and we spin to return the maze so here we make changes the first step in the recursive back tracker is to choose a random position to choose a random position we need a random number generator so we will use the system random function system random class sorry system dot random you can pass in a seed here right but we will do that later when we're ready for it and to choose a random position we can just do position X would be RNG dot next 0 comma width so that will give us a random position from 0 to width and why would be RNG dot next 0 comma height so we have a random position inside the whole grid and we need to mark this position in the maze as visited so let's do that means position the position why is now marked as Allstate visited this essentially makes it such that whatever the position was which it is essentially initially all ones is going to be zero one triple zeros and then one one one one right so that's going to be setting the initial cell as visited we also need to push this position to a stack so we're gonna say position stack a new stack of positions all right and then let's just do position stack push position the next step in the recursive back tracker is to iterate over the position stack till it becomes empty so we'll do position stack dot count is greater than zero and then we need to pop the top of the stack so position stack initially if you just give us back the initial random position we then look for the neighbors of the current position so we can just do get unresisted neighbors at current position take the maze with an hi all right and if the neighbors dot count is greater than zero then we have things to do around the way we are not treated in yet so there is still undecided neighbors around this so we put the current position back into the stack so we do positions tagged are first third and then you need to find a random neighbor around the current position how we can do that is just to take a random index of all the neighbors like random index from the neighbors list so we do run RNG dot next 0 comma neighbors dot-com alright that'll give us a random index from zero to neighbors count minus 1 and then the random neighbor essentially neighbors and remain at the random index value so we have a random neighbor the position of the neighbors let's call it n position is random [Music] position because neighbors have a position and a shared wall right what we can do is first remove the shared wall between them so may is dot current dot X and current out why the way to remove the Meuse I mentioned earlier is to do an equal to and random neighbor dot shared wall that will remove the shared wall on the on the current node we also need to add a function that returns the opposite side of the shared wall so if it says it's a right wall for me it needs to return function let's create a function that returns the opposite side so if it takes a wall state and returns a yet opposite wall and it takes a wall state and there comes the opposite side so it's going to be stretched wall case wall state dot right it means to return all state total a case while staying got left it means to the town wall stage dot right I'm sure there's some building we used to do this but I just want to keep this simple it's just a little extra writing compared to the Crillon case and default is going to be the tongue Volsky dot and that doesn't matter because it going to be passing monotheism so we need to set visas at the neighbors position all right we need to remove the wall on that side as well so we're going to do remove get opposite wall after shared wall on our side last but not the least we need to put the neighbors position onto the stack now that's your whole recursive backtrack algorithm essentially start at the current node find its neighbor go to random neighbor remove the walls push onto stack repeat right now to call this function you haven't yet called it so let's head to the generate function and before we return the maze is just to actually can return the maze go you can just to apply for a recursive drag tracker and you pass the means along means right and that should generate a maze for us let's head over to unity and see how that looks you let it compile for a second and then make you click on play [Music] right I found the problem how we never mark the neighbor as visited so let's do that as well division dot X and not Y is going to be marked as a visitor let's open up our seam and you go clicking on play and the meat is ready let's make armies look a little bit nicer so I'm going to create a few materials in the materials folder what Helios is called this T I'm going to set the value for this to be approximately this it's also create a floor material you don't have a flow yet but I would love to add one should be around the screen I like just being a lot and let's just make it completely smooth let's feed a plane that's going to be our floor and I can drop this into the material set this to be zero and need to add it to the renderer so let's do that so we have that before we draw the whole meal let's instantiate the floor so lower is thank you lower prefab inside the transform and then let's just set the floor dot local scale scale to be free we need to make it as big as the email itself so let's just make it with comma hike zero come right along the x-axis right so that should increase the size of the outer floor itself I need to create a prefab out of this come on here go to the means and we'll give it the floor let's update the material for this let's call this wall material yeah and see how this looks okay something's wrong the problem we set its local scale to be zero so we go back to unity now I think we should be able to see the floor and the maze in its full glory it's Philippe right oh wow so I imported the standard assets and added a third person controller and a free Luc amarak that keeps looking down at the third person controller so let's see how that goes we have our player in the maze run around you can set up exits so how do you wanna go now go to the other corner so the way you would go is right this way I think I I think I know the way let's go I should add something better for this controller the maze looks easier from the top I think it's this way and you are back at D corner I can use that corner as well there you go so that's the median rate of view there are multiple game ideas we can make using this generator we can make a simple maze running game going from one end to the other with global leaderboards for the best kinds or a game where you have to collect a few keys and find the exit let me know what game ideas you come up with and if you have any questions or suggestions drop a comment Cheers hey can't the third person controller jump oh oh man oh man oh it's stuck I guess you gotta do what you gotta do [Music]

Channel: Sandeep Nambiar

Views: 13,856

Keywords: unity3d, maze generation, procedural generation, tutorial

Id: ya1HyptE5uc

Length: 40min 27sec (2427 seconds)

Published: Fri May 22 2020