Programming Mazes

hello whilst recently on my holidays I met a strange man and he told me I had two minutes to create a maze that would take him longer than one minute to solve so I did this and said solve that there you go and if you haven't guessed already this video is about mazes but more specifically it's about algorithms and this is an algorithm that I have loved since I was a child I first encountered it in the BBC micro magazines where you have to type in the programs you sell from acres and acres of soft listing rarely did the programs actually work but this one always stuck with me because it's a fantastic algorithm and it's perfect and it's complete and we'll look at the details of it later and I think it's a great example of programming and computer science at its absolute best in just in case you're wondering today I am living proof that programmers and code is actually go outside so there we go now before we get stuck into the code I'm just going to provide a quick primer for the uninitiated and that is what is a stack because this is fundamentally a stack based algorithm and a stack can also be known as a LIFO which stands for last in first out some people may also call it a Philo it's the same thing and the idea is I wanted to imagine a box like this and if we put some data into this box it sits at the bottom and then if we put in some more data into the box it sits on top but we can't access this data at the bottom anymore we can only take off the last bit of data that was put on there's a little bit of terminology we always push items onto the stack and we pop items from the stack and the top of the stack is always the most recent item that was pushed onto it now because this is a video primarily about algorithms I'm not going to go into the implementation of the stack there are many ways to do it suffice it to say that if your system or your code uses a stack it will behave like this now the algorithm I'm going to talk about for developing a maze is known as the cursive back tracker I'm unsure of the origins of this algorithm but it has been around for a very long time and has some fantastic properties but whenever you want to write code that involves a more complex algorithm than normal it's always good to get the pen and paper out first make sure you understand it so I'm going to go through it by hand here on this very simple maze and it's four by four and along the top here along my x-axis I've got four cells 0 1 2 3 and I've got my y-axis going down my plan is to fill this 4x4 array with maze and I'm going to start by arming my stack with some data and I'm going to armed it with the starting coordinate which in this case is going to be 0 0 so that's 0 along and 0 down I'm going to mark that cell as being visited so any cells that have a blue blob in the middle are going to be visited and I'm going to get a tick here and I'll know when to stop my algorithm because I should have visited all of the cells at the end and out therefore I'll have 16 ticks now I'm not going to make you sit through all of this I will speed up parts of it but it's a nice visual example of how the algorithm is put together don't forget that even though there's only one item in my stack the top of my stack is 0 0 and the algorithm goes like this from my current position which is the top of the stack I've got to choose one of my neighbors randomly so from position 0 0 here I've got a choice of this neighbor 1 0 or this neighbor 0 1 I roll the dice create a random number and I select 0 1 so I set that self to be visited and I create a link update my visited count and I've pushed the new location on to the top of my stack so now I repeat I look at my immediate neighbors and choose one of them at randomly that I've not already visited so my immediate neighbors consists of 0 0 1 1 and 0 2 well 0 0 doesn't count because I've already visited it after rolling my dice I've decided that I'm going to move east and I create a link to it push the new cell onto the top of my stack that the cell is visited so one more time with commentary for completeness I take the top of my stack I choose a random direct neighbour so in this case I've got 1 0 2 1 0 1 and 1 2 I can't use this neighbor because I've already visited randomly choosing I'm going to go again to the east push the new coordinates to the top of my stack and update my visited count so now I've let the algorithm run for a few iterations and we've hit a problem I now need to choose a neighbor has not been visited before so my immediate neighbors are of course now 0 0 1 1 & 2 0 however they've all been visited so I have no neighbors which haven't been visited I've now got to backtrack and this is where the stack became useful the stack contains a history of all the locations that I visited to the top of my stack is my current location and if I pop the top of the stack I can move back one but note I don't remove anything from the visited column and here I face the same situation all of my neighbors I visited before so I've got to move back one by popping off the top of the stack now I'm back at this location this is the first cell as we're backtracking that's got a neighbor that I can actually plot into which in this case is three to all of the other neighbors are not available they've already been visited so I've got little choice I've got to go here this is a new cell so it becomes visited and we pop the location onto the stack and now we'll let the algorithm continue again but now if it's a dead end again as we can see got no neighbors which I've not previously visited so I've got to backtrack and I do that by popping the top off the stack and using the top of the stack to set my current position and when I go to this location I do have one neighbor I have not already visited and it's the only one I can choose and so here I've now got sixteen ticks which is the number of cells that I've visited this algorithm is really nice because it guarantees completeness it doesn't matter how big my maze is it will fill all of the cell and it guarantees that every cell can touch every other cell so it doesn't matter where you start in the maze you're guaranteed to get to the objective location within the maze and like all perfect algorithms it's completely scalable not just in terms of dimensions of the maze but in how you apply it in this case I've got a single cell where I can visit my immediate neighbors north south east and west but it needn't be the case I could have many neighbors and apply the same algorithm and get a perfectly complete maze out of it once you've visited all the cells it's up to your rendering algorithm to then try and draw the maze so in this case I'm going to fill in wherever I haven't got a link between two cells so I'm going to draw a line here and here and here and once I filled in all the lines just develops the walls for my maze at which point we no longer need the stack and we can get rid of all of this construction data which leaves us with a really nice albeit rather small maze like structure now let's see how we will do this in code I'm going to start with a blank int main program as I always do and I'm going to pull in the one lone coda console game engine which you can see in the video marked in the little tab above now since this is the first video I've done that uses the technology I'm only going to go over it very briefly because you can look at that other video for the finer details but ultimately I need to derive a class from my console game engine which just handles all of the console stuff for me if you've seen my other videos you'll know that all of my programs involve creating a screen buffer and using get a sink key state to emulate some sort of game engine I've wrapped that up into a nice tidy package that I've called the one lone coda console game engine and there are two functions in this on user create which is where we do all of our definitions and creating of resources and on user update which is basically a per frame function so this is where we put all the fun stuff and implementing the class couldn't be simpler we just create the variable we construct the console to the dimensions that we want so in this case it's 160 characters across by 100 wide and each console character is going to be 8 by 8 pixels so then we call the start function this is only for Windows the construct console function calls things to the windows operating system that define how the console should look but you shouldn't let that put you off if you're a Linux or a Mac user the algorithm is still going to be platform independent now from my maze algorithm I know that it's fundamentally stack based so I'm going to include the stack from the standard library and in the game class I'm going to create some variables that define the maze specifically my maze has a width a height and I'm going to create an array here dynamically which stores a value for all the cells and I'm going to use this value to tell me which neighbors the cell is connected to and so to make this a little bit more readable I'm going to create an enumeration here where I'm defining some constants so for any given cell I can tell whether it's connected to its neighbors because the int value that represents that cell will contain the bits set in the appropriate locations and if I visited the cell as well I know that the algorithm also requires me to keep track of how many cells I've already visited and finally of course I'm going to need the stack and this might use something a bit new to the one-line code of videos I'm using the pair type pair allows you to store two things at the same time I could create a struct here myself that stores an x and a y-coordinate but I'm going to use the pair anyway why not this is new and so I have a stack that stores an object which I've typed pair but the pair is that templated to store two integers the first one will be the x-coordinate and the second one will be the y-coordinate now I'm ready to specify some parameters that define my maze so I'm going to set the width of the maze to 40 and the height to 25 I've already predetermined that this dimension looks quite nice on the screen and because I might want to play with these numbers later I'm going to allocate the maze memory dynamically based on the dimensions we've just set it's also quite important that we set all of the elements in the maze array to 0 to begin with I'm using the mem set command for this and now I need to specify the staffing conditions for my maze the stack has to have something in it to begin with so I'm going to push on to that a new pair and I'm going to usually make pair function and we're going to start like I did when I was drawing it by hand in the top left hand corner which means I also have to set that cell to be visited and conveniently the top left corner of my maze array also happens have the index 0 I'm going to use one of the bits that I set before and because I've already visited one cell I'm going to set my visited cell count to 1 as you can see there's very little required to initialize this algorithm but it's important that you do before we get stuck in with the algorithm I think it's quite important that we have a way to visualize it that way we know if we're coding it in the right direction so to begin with on the on user update function I'm going to clear the screen and that involves basically drawing a space to my console in all locations screen width and screen height from the top left corner and as discussed previously my maze consists of a 2d array of cells so I'm going to iterate through each of the cells mates with and mate height and for each cell in the array I'm going to check does the integer have the cell visited bit set in which case if it does we draw a white pixel or a white block character to that location on the console or we draw a blue one so let's just have a quick look what that looks like well it's a blue rectangle with a tiny little white dot so that's good I mean that indicates that our maze of the dimensions 40 by 25 does have 40 blue characters by 25 blue characters and the one cell we've already set to visited in the top left has been set however everything looks a bit small and there's a problem we don't have anywhere to draw the walls I'm going to introduce the notion of a path width which will specify how many on-screen console character cells represent a single cell in my maze so for example if the width is set to 2 i actually occupy a 2 by 2 block of cells on the console which represents one cell in my maze then i can surround the two sides to the east and the south of that one cell with blocks that represent wall so here's my 2 by 2 cell and here is a 2 by 2 cell and here is a 2 by 2 cell and we've now got positioned to add walls I only need to concern myself with walls at the east and south side of the cells because if two cells are linked then this cell loses its western wall and this cell loses Eastern wall ie the wall is shared between them and of course the same applies for north and south so this is now cell position zero zero and this would become cell one zero and this one would be 0 1 and 1 1 but the relationship to the console characters underneath is now the cell coordinate times 2 to get us to here and we always plus 1 to give us some wall at the end and of course that happens in both axis so we can consider then a whole complete cell with walls and exits and everything else is a multiple of path width plus 1 let's add another variable to our class path width and we'll define this as being 3 so our May cell will represent 3 console characters across and one for the wall we then need to modify our drawing algorithm to accept this change in scale so every position becomes x path width plus 1 let's take a look well we can now see that it's spread out across the whole console which is good but it's not filled in the individual cells which is bad therefore I need an additional loop inside my maze loop here let's draws in each cell so for each cell in my maze I'm now going to go through each cell in the console for the path width and we just have to add this onto the end take a look excellent we now have cells which are 3x3 with a wall of 1 on our console great we're also in tourney to draw in our pathways to overwrite the wall so we can show the cells are connected so if any of our cells have the path to East or path to South set we also want to draw those in as well and because our walls are always only one character thick I don't need to do a two-dimensional plot this time and get away with a single dimensional one so I'm just going to go through the path width one at a time and the first thing I want to do is check well does the cell in this case does it have a self path and if it does I want to draw in the cells to give us that passageway from the north cell to the South cell or from the South cell to the North cell who knows and we'll do the same for east to west so if the cell has a passage from the east to the West in either direction we want to overwrite the wall the black cells in the background on the console we want to draw them in with path color which is white now we've got a way to visualize the maze let's get stuck into the really fun stuff let's actually create it the maze creation can also go in the on user update function and we want to create maze only if the number of visited cells is less than the width times the height ie we can only do more maze development if there are any cells that we haven't visited step one is to create a set of the unvisited neighbors let's consider the North neighbor first as we're working with 2d arrays we don't want to go out of bounds and cause all sorts of memory errors so it's important that we don't check for neighbors that the relative bounds of our maze and if we're checking for northern neighbors that means we shouldn't be checking for any if we're currently on the top row of our mates because they just don't exist there aren't any northern neighbors so that's the first thing I'm going to check for and to do that I'm going to take our stack and I'm going to look at the element that's at the top of the stack using the top function and I'm going to check because the stack contains pairs I'm going to check the second element of that pair which if you remember is our y coordinate and I'm going to ensure that it's great than zero now we're trying to develop a list of all the neighbors that haven't been visited so we need to check that in our maze array and to do this we need to get the index now we're currently using the stack and it's using a pair of second and first for Y and X and so that looks something like this which you can see is a bit of a mouthful and we want to see how's the cell visited flag bit bin set which will do by checking if it's equal to one but this isn't very useful to us at all in fact very difficult to read and the y coordinate in this case would get replaced with minus one because we're checking for the neighbor above us in our y axis and the x coordinate gets set to zero because we're checking in just in vertically we're not bothered about the east to west so in the event of us being in a valid location in the array and that our neighbor to the north of us exists and haven't been visited we want to store this and I'm going to do this by creating a vector with the vector I'm going to push to it and identify and in this case I'm going to use zero that will say that my northern neighbor exists and is unvisited and I can use similar code to check for my eastern neighbor which in this case I'm going to use one as the identifier but here I don't want to check for minus one I want to check for zero in the y axis and plus one in the AL are you know what this is actually getting too much I've just gotten to the point where I can barely understand my own code so I'm going to create a little lambda function to help me out the lambda function is going to take an X and a y-coordinate and do this horrible little bit of offsetting for me let's change that to an X and change that to a Y and semicolon and get rid of this now and just call my lambda function so if I'm checking in the northern direction I know I'm not bothered about X but I'm looking at minus 1 in the Y that's much much tidier and I can also do the same for my Eastern function which in this case I'm looking along the x-axis by 1 but I'm not looking in the y-axis at all now you might be thinking why don't I just do this with a macro well of course you could do this with a macro but the language now provides the auto feature quite like this I like the lambda function approach to doing this it means I'm forced to put the code where it's needed macros can be any word and a little bit unregulated they can get a bit dangerous and fiddly will also exploit the fact that the if statement is checked in order so we can get rid of this secondary call to if which makes that line of code much more concise now I'm going to repeat that for the other directions and here we can see I've got now an ID of zero for north one for East two for self and three for West you'll notice with the east and west neighbors I'm not using the y component of the vector to check whether I'm in bounds or not I'm using the X which is the first of the pair I've just flagged a little error here I'm not actually checking if the cell is visited of course I am checking if the cell is not visited so I want to make sure that that is a zero and not a one my apologies so now I have a vector that contains only valid neighbors that I can visit which I might not have any at all so I need to check for that if I don't have any then I'm going to be popping off the stack if you remember the algorithm before but let's for now assume that I do have some neighbors and the nice thing about bundling things into a vector this way is it makes other operations easier so I want to choose a neighbor at random well to do this all I need to do is randomly choose a number from the neighbors size and use that as the index so I can get something that tells me what direction is my neighbor now and because I've been pushing zero one two and three I know from this identify which way to go next so that's the value that gets stored into the next cell Direction variable the algorithm says that once I've chosen a neighbor I then need to create a path between the neighbor and the cell that I'm currently in well now that they know both of those cells I'm just going to use a little switch block here and fill in the blanks so let's assume the neighbor is north I want to create a path to the north so my current cell which is locally represented by 0 0 here because remember this lambda function uses the stack to work out where they say it always used at the top of the stack and all of the coordinates are relative to the location at the top of the stack so if there's a path to the north I'm going to or it with the path to the North bit whilst I'm here I may as well tell the cell that's above me ie my northern neighbor that the one below it has a path to the south and then going to push to the top of my stack the northern neighbors coordinates so as I push to the stack I create a new pair the x coordinate is the current top of the stacks x coordinate plus 0 and the y coordinate is the current top of the stacks second part minus 1 so this is the y coordinate minus 1 to the northern neighbor if any of this switch block executes it assumes that I have now entered that new cell so I need to increase my visited cell count and I also need to make the cell that I am currently in so the one that's now the top of the stack which is the new cell which I can index with 0 0 now I need to tell that cell that I have been visited so I'll just put in new cell here is a bit of a reminder let's duplicate this code for the other options so for South instead of checking for -1 we're now checking for +1 and of course the southern neighbor we set the northern path and we set our current path to self let's not also forget the coordinates of the new cell so all of this was on the condition that we had some neighbors that we hadn't visited what if we didn't have any neighbors well if you remember from the algorithm before we need to backtrack and because we're using a stack that's really really complicated done so let's take a look and see what happens well I think that's fantastic we've got a really large and complex maze and labyrinth okay it's really nice I'm going to slow down the algorithm by adding an artificial delay remember this is just for visualization it's not that important that we're breaking some rules here so I'm going to use the sleep floor function to delay for 10 milliseconds in each of our on user update calls this means we'll have a maximum of 100 cell updates per second ie were limiting programs through at about 100 frames per second let's have a look the algorithm is really pleasant to watch we can see the choice to draw the longest path that it possibly can until it boxes itself in and then it back tracks to illustrate this I've also got it to draw the top of the stack with a green rectangle in many respects this is similar to a flood fill algorithm and will probably definitely have a look at those in the future and so there you have it the quick look at a very simple maze generation algorithm there are many other algorithms for generating mazes particularly if you want mazes with a set of properties such as long corridors or extra rooms but you can always use this one as a starting point for example you could proceed some of the cells as being already visited now I appreciate that this video hasn't been as simple as some of my others and this is going to happen from time to time sometimes the topics are quite complicated and need me to use more advanced coding techniques than perhaps you see in some of my other videos and I'm still not sure yet about using something like the one learned coder games console engine in the background I don't know if it does actually accelerate the development of the code or the video but I've got some other ideas for it for other projects which require things to be a bit more graphical and I'm trying to avoid needing to develop a Windows application anyway as usual the codes going to be available on github you can download it hack it generate some mazes for me if you've enjoyed this give it a thumbs up it does great wonders for my self-esteem and please think about subscribing lots of people have been subscribing recently and I'm really grateful for some of the fantastic comments that people have been leaving so please keep all that up and I'll see you next time take care

Channel: javidx9

Views: 124,632

Keywords: mazes, labyrinth, programming, c++, onelonecoder, one lone coder, tutorials, command prompt, ascii, algorithms, recursive backtracker

Id: Y37-gB83HKE

Length: 27min 10sec (1630 seconds)

Published: Mon Jul 10 2017