Coding Challenge #10.2: Maze Generator with p5.js - Part 2

part two of my depth first search recursive backtrack or maze generation demonstration algorithm think here we are so all I did so far this is what I'm trying to build this thing that's going to tick some time and eventually generate this beautiful hopefully well beautiful although mine won't be so beautiful you'll take my code and make something more beautiful but let me show you how to make this maze generation thing now just to recap all we have so far is just this grid so I have this grid and in the code I have cell objects each cell knows where it is what's its column what's its row and it knows whether to draw its walls top right bottom left top right bottom left and it has a boolean variable to keep track of which walls are currently active in there so we need to now go and look at that Wikipedia page where the algorithm is described so I'm going to go over here and look at this this is the rhythm working recursive back tracker so the whole backtracking aspect that's going to be in part three but we're going to do the forward tracking aspect so the first thing here is that make the initial cell the current cell and market is visited okay so this is a really key concept what's going to happen here is that the program is going to start on a given cell and it's going to start walking around the cells and just deciding whether or not it should remove a wall or keep the wall there now as it walks around the cells it should never go back and visit a cell that has already been at so we need a variable to keep track of whether a cell has been visited or not so if I come back over here that's the very first thing I want to add is I want to add another variable here that says this dot visited equals false so each cell should not be Vince so the first it starts as having not been visited sorry now sorry in in the main part of the program what I want now also to have is I'm going to have a variable called current so this variable current is the current cell this is the cell that is currently being visited and in setup we could just have it be current equals grid index 0 so I'm going to start the current cell just at 0 in the top left it could be anywhere concern in the middle card to the bottom right have to do with where you want your maze to begin an end but for now I'm not really gonna worry about it so much starting at grid index zero will be just fine and then in draw the very first thing I'm going to do is say current visited equals true now I think there would be something useful here to do for example what I just to be able to see bet best it would also be really useful for debugging and remember I kept this in here is that we could have put some spaces here if the cell has been visited let's change its color a little bit so that we can sort of see what's going on so I'm going to say if this dot visited draw a rectangle to get good at this update draw a rectangle with so much I want to turn off that autocomplete in between this video the next Rotem make it a nice like purplish color with a little bit of alpha so what we'll see here if I run this again up that's the wrong one here is we can see this cell has been visited just that first cell is now kind of a purplish color okay so now we've got a structure for knowing if a cell has been visited and we're also debugging wise can see if it's been visited by highlighting it which will help us as we try to figure out if the program is working or not so let's now go and look at the algorithm and what's next while there are unvisited cells okay so as long as there are unvisited cells so we know that we're going to be finished when all the cells have been visited worry about that later if the current cell has any neighbors which have not been visited okay this is probably going to be a pretty complicated piece we need to figure out does the current cell have any neighbors which have not been visited so let's figure out how we're going to do that I'm going to go back to my code which is over here and come back and what I want to do is say something like current JA Czech neighbors whoa how did it know that's what I was going to type that's crazy that is insane it's like predicting the future it's got some kind of like deep learning machine learning magic I wasn't even using editor earlier I did type something earlier today that said check neighbors and what's going on some sort of magic okay maybe I opened up a different example already whatever the point is I want to write a function that's called check neighbors so I'm going to add that function this dot check neighbors now it should know is a function so how do I check the neighbors okay let's think about this first of all I don't know I'm in a real place and there could be neighbors outside neighbors or people that are to the right the left in front of me etc let's look at how that works over here so much like we were talking about in the previous video the top right bottom and left walls now if I have a cell there are four neighbors if this cell is at I comma J this is I plus one comma J this is I minus one comma J this is I comma J minus 1 and this is I comma J plus 1 right why goes up by one down by one I goes up by one down by one so this is what we want to check check the neighbors we need to know are any of these neighbors visited or unvisited ok so let's start doing that I'm going to come back over here and say something like so I'm going to make an array called neighbors and I'm going to say write equals grid and now this is where it would be nice if I was using a two dimensional right and you know I want to start with top remember top right bottom left this is how I'm always going to track everything so the top is grid you know you sort of think of it as like this right if I had a two dimensional array I would say I sit J minus one that's the cell above me right but I don't have a two-dimensional array I have a one-dimensional range there is a magic formula the magic formula to get an index into a one dimensional array where every thing 0 1 2 3 4 5 6 7 8 9 10 11 12 the where everything is ordered going across rows but I want to think of the column and row coordinate is as fall index equals I plus J times the number of columns I will link to a separate video we're about pixels where I go through this algorithm specifically if you haven't seen it before but for now you can sort of trust me that that works so what I'm really saying here is this I'm saying I want this particular right neighbor and that's not the right neighbor that's the top neighbor right I want to check is that top neighbor visited or not now because I'm going to need this formula so many times in this program I'm going to write a function I'm going to call it index and index gets an eye in a J and just returns I plus J times the number of columns so I can actually just do this I don't need this code here I could say the top neighbor is index I J minus 1 the right neighbor is I plus 1 J oh you know what I'm going to live dangerously today how kind of fix all the formatting here I'll fix it after the fact when I post the code it'll be all nicely indented in space the way I like it but I'll fix a few things right bottom I can't help it I'm doing it anyway index bottom is I J plus 1 and then left is grid I minus 1 J what J I'm losing my mind here I minus 1 J right because the why is the thing okay so these are the neighbors top right bottom left now first of all have they been visited if top has been visited if top has not been visited then I want to add top two I want to add top to that array neighbors dot push top now I should really probably condense that right now I'm doing something that I do often which is like I'm just writing things out very explicitly I know there's only four neighbors and I can just like have these four neighbors and then duplicate this code four times I could easily do it differently and kind of like figure out a nice way of a nice way of like condensing this code but I'm going to just sort of live with being happy with this because I'm just to do this four times and do if bottom has not been visited put it in if write has not been visited put it in and if left has not been visited put it in and you know what I want to keep the same order even though it doesn't matter it yeah it does it might matter top right bottom left top right bottom left so I want to build an array of things that have not been visited yet but I also have a little bit of an issue I need to deal with it's really unfortunate I wish I didn't have this problem but what if I'm over here I only have three neighbors there's no neighbor to over here and I could do something fancy where if you go over here you could come on that side but I don't want to do that so I also need to figure out to make sure my uh the neighbor that I'm looking for is not negative one or past the width so I need to deal with that I wish I didn't have to do life would be so much nicer if we now these edge cases by the way that's why you call edge case because it's actually on the edge it's an edge case I'm just looking different for it you know if I ever thought about that before but you know so one way I can deal with that is I think I I'm going to do it over here this is a little bit weird but I'm going to say if I because it seemed valid I I want to invalid index if I or J is less than right if I is less than zero or J is less than zero or I is greater than the number of columns minus 1 or J is greater than the number of rows minus 1 all of these are invalid index values right I has to be between 0 and columns minus 1 J is between 0 and rows minus 1 and then I'll just return a negative one so I'm going to get a totally invalid index otherwise I want the correct index and then down here do you know if it get negative 1 do you know what's going to happen here top is going to be undefined or right is going to be undefined or bottom is going to be undefined so you know what I can just do as long as top is a real thing and it hasn't been visited then it can go into the array as long as right is a real thing and it hasn't been visited as long as bottom is a real thing and it hasn't been visited and as long as left is a real thing and it hasn't been visited boy this Czech neighbors function it was a lot to do but we're kind of like we're really like practically there now what we have figured out now is are their neighbors that haven't been visited if so select randomly one of those so now what I want to do is if neighbors is dot length is greater than zero let's pick a random neighbor so I need a random value between zero and the length of that array array and then I'm going to say return that random neighbor otherwise uh what return let's just return undefined it probably would return undefined anyway if it doesn't return a neighbor but I'm going to explicitly say undefined so this is what we're doing we are in a cell that's the current cell we're looking at all its neighbors we're finding any that haven't been visited and then we're going to visit that one so let's go back to this the main sort of part of the sketch and what I'm going to do here is say neighbor equals current check neighbors so this function should check the neighbors find a random unvisited one and return it and I'm going to say if neighbor is not undefined right then what neighbor and you know I'm not going to call this neighbor I'm going to call this next because this is really the next cell current the next cell is one of the available neighbors as long as neighbor is not defined now next is not defined now next has been visited and current should be next right so this is like what we're doing marketing through so let's just look at this if I run this now I'm probably made a mistake so check neighbors is not current dot check neighbors is not a function so let's see what did I miss current check neighbors this Czech neighbor I spelled neighbors wrong okay so now let's run this again look at that so you can think another two let's reduce the frame rate so we can see what's going on I'm going to say frame rate just at five frames per second so you can see here it's marching along and eventually it's going to get to a spot and there's no more available neighbors so we're doing pretty well and actually this is going to be the end of this part because we got to a good bar we got the part of the algorithm where we're marching along to find neighbors until we get to a spot where there's no neighbors anymore now I haven't been removing the walls that's going to removing the walls I'm going to do in the next part but this is pretty good I can hit refresh again and we can see it's going to do this differently every time but you can see it going to get stuck pretty fast so the next thing I need to do and is in the algorithm is actually start removing the walls so that we're carving out this maze so to speak okay see you in the next video

Channel: The Coding Train

Views: 143,163

Keywords: challenge, maze, maze challenge, object oriented programming, programming, p5.js, tutorial, coding challenge, oop, object oriented, programming challenge, p5js, javascript, daniel shiffman, creative coding, javascript (programming language), html5 canvas, coding, recursive, recursive algorithm, depth-first search, recursion

Id: D8UgRyRnvXU

Length: 14min 18sec (858 seconds)

Published: Mon May 02 2016