Coding Challenge #10.1: Maze Generator with p5.js - Part 1

welcome to a new coding challenge mais generation so I've got a maze generator running behind me it's using something called a depth-first search and a recursive back tracker those are all very fancy sounding names and what I'm going to do in this challenge probably in multiple parts so it'll be two or three videos you can follow along in sequence is build this simulation entirely from scratch and will cover a lot of concepts in object-oriented programming thinking about arrays thinking about something called a stack thinking about recursion all sorts of crazy stuff so um so without further ado so to speak let's just get started ah no actually there is some ado here so this is the aversion of it running that I built a while ago meaning earlier this morning and I just want to show you where this comes from all this will be linked to the source code for this and this Wikipedia page will be linked to in the description this is a Wikipedia page on mais generation there's a lot of different algorithms if I were to just keep scrolling I'm implementing this depth-first search and I'm actually going to implement exactly this pseudocode which is written right here under a recursive back tracker but if you keep scrolling down you'll see there's various other algorithms and maybe we'll come back and in future videos if you like this topic do more of them so this is what I want to focus on now before I can even focus on really getting to the algorithm I need to kind of like set the scene of what what is it that we're building so I'm going to come over here to the white board and what I'm going to have is I'm going to have a canvas so I'm going to build this on a web page in a browser using html5 canvas using p5.js and I'm also using an atom as my text editors tools that I'm using here but what I ultimately need is I need to think of this canvas as a grid and each spot on that grid is a cell object and essentially what the program is going to do is it's going to figure out what walls should be removed to make a nice maze pattern and you can sort of see what I'm doing here if I remove certain walls you could see now ah here is sort of a maze that you want to follow so before I can and there's going to be a strategy for like why do we remove certain walls to create a continuous maze continuous labyrinth but the first thing I knew before I could do any of that is just sort of set myself up with some kind of data structures to figure out how to do this in the first place so what I need is a cell object the cell object should know where it is in this grid it should know what column it's in and what row it's in so every one of these spots has like a column number zero one two three or four and a row number zero one two or three so the cell needs to know where it is it also needs to know like what's the deal with its waltz does it have it is the wall to the right open or closed is the wall to the top open or close the left open close to the bottom open it close so let's go and build this cell object and I'm going to use a constructor function so I'm back over here this is uh so I'm going to this is still running we'll let that run I'm going to come over here this is my blank canvas with nothing in it yet I'm going to go to my code editor I'm using atom and I've set up just create canvas and background so in this first video all I'm going to do is get the dig the grid there so the first thing I want to do is write a constructor function for a cell object so oops so you can see and I want to put some line breaks down here at the bottom so this is what I'm trying to do I'm trying to create a cell object that has an i and a J the I being it's column number the J being it's row number so actually let's think about how do we even know what how many columns and rows are are so I want to have some global variables I'm going to call those columns and rows and I also want to have another variable which is the size I really need a variable which gives keeps track of like how wide and high how big is this square it's going to be a square not a rectangle same height same so I can have a single a single variable I'm just gonna call it variable W and let's just say that variable is 40 so right I have a canvas that's 400 by 400 and the width and height of each square is 40 so it's 10 rows and 10 kalo 10 columns and 10 rows it's an easy way of thinking of it first and how do we calculate that we say column ly equals with / ee that's the total number of columns with divided by how big each one is rows equals the height divided by how big each one is and I should also use the floor function to make sure I'm dealing with integers here whole numbers even though I know that 400 divided by 40 is the whole number 10 but what if I have a different size canvas and that'll just make things easier so now that I have that I have a cell object each cell gets its i and j get this look gots its column and row okay so how do I create all the cell objects well I want to say for every row for every row go through every column so the first row creates now create all these cells the next row create all these cells the next row create all these cells that means I need a nested loop so for I goes through all the rows and you know what I like to call J I'm thinking of J as the row so I'm going to change that to J and I could use the x and y that might even make things easier but I'm used to I and J as my sort of names of things so so so it kind of makes sense in my brain immediately you know use your whatever variables make you feel comfortable about columns and rows that's what you should use maybe you can use cat and kitten or something but anyway and then I want to say I want to make a cell is a new cell at I J so this now is a nested loop that's going to make 100 cell objects write 10 by 10 grid every for every outcome of every row make 100 cell objects make that each know where they are now where do I put those what I want what I need is an array so I need an array and I could use a two dimensional array and I two dimensional arrays in JavaScript for though there's not really any such thing as a two-dimensional array it's really just an array and the things in the array or other arrays that's a two-dimensional array but and there's some conveniences for doing that but I think it's going to be simpler actually if I use a one-dimensional array and we'll sort of talk about why and see some pieces of that as I keep going okay so I have a one-dimensional array right this list it's going to store all the cell objects and I'm going to say grid dot push cell so all I'm doing here is I'm saying all of these cell objects and put them into this big array once I have that in draw I could actually then loop through all of them and display them I'm going to call function called show so what this means is what I want to do now is just see that this is working and so what am I going to do in this cells in what I need now is a new function called show in the cell object so I can add that here this cell sorry this dot show equals a function and here I want to draw something so where is the x-coordinate for this particular cell well it's at the eye location it's column location times W right because it's column 0 1 2 3 or 4 scaled up by how big those squares are X is this J times W and then so I could just draw a rectangle at X Y at that size and I could say stroke 255 no fill and now if I run this we should see ah ok so what did I miss cells is not defined sketch J s line 25 ok so the array I called it grid not cells whoops wonder why grid is a oh and this should be grid also ok so that should fix that great so you can see now I have that grid there now we should dig a little bit deeper here because the whole point of doing this was not to draw rectangles here but each cell has walls it has four walls atop a write a bottom and a left so I should be either draw the wall sure either be there they shouldn't be there so I need to draw them as individual lines so let's figure out how I would do that so here where I'm drawing instead of drawing a rectangle I want to draw the walls so to draw the wall I'm just going to use line so we can get rid of the rectangle I might want this later so I'm going to leave that comment it out I'm going to say line what X X comma Y X plus W comma Y what's that going to give me so you can see here that that gives me a line from the top left to the top right of each cell now I could also draw from X comma y plus W to X comma y plus W no no no no no no - yeah yeah X plus W okay okay okay let's go to the whiteboard here because this will be easier to figure out if I do this here okay so what's going on each cell this location is X Y this location is X plus W comma Y this location is X plus W Y plus W and this location is X comma y plus W I think I got all those right so I need to draw a line from here to here a line from here to here a line from here to here and a line from here to here let's do that so that should be and I can refer I can look back you know you can kind of imagine that that's there but I'm looking back at it and I'm saying the next line is X plus W oops I don't know where that came from X plus W comma Y to X plus W y plus W and then I need X plus W comma y plus W and there's an extra boy's all doing all sorts of autocomplete stuff for me I'm gonna have to work that out in this editor so - X comma y plus W oh boy we're going to get this eventually and then X y plus W back to X Y so now if I run this we can see it looks just like it did before but let's just sort of make sure things are working here like what if I take out this particular line actually does it look any different because if I take out the right side the left side of the cell next to it always picks it up but if I take out both both sides we just see only the on the top and the bottom we only see the the horizontal lines okay so uh okay so okay I'm getting somewhere but I gotta think one thing I want to do this is me being like the anal anybody see the silent live sketch anal-retentive chef we're like the garbage goes in the ziplock bag and then that gets like and then the Gazette bag goes in the past the paper bag the paper bag gets folded and gets taped well I am the anal retentive coder and what I want to do is just like align all of this so I can kind of like see this more easily what's going on and this has bothering me because I want spaces here you should now turn this video to two times speed while I'm doing this and then go back but this I think is useful to be able to see exactly what's going on and I will do this periodically and this needs a space boy what is go I have just lost my mind here and this needs to space oh you know one thing I need is auto format I'm gonna when I take a break to go to the next video will edit this part out okay so oh and I need some spaces here this is really I really have you should not be like me be like some don't have this kind of problem be fine with the spacing everything not being exactly right you know indentation is important but at some point in your life you just need to like write your code anyway the reason why I did this is I want to see like okay I want to see clearly like this is the x coordinate this is the y this is the X I wanted everything to line up nicely okay now how am I going to figure out a way I need something else for these cells I need you to figure out a way to know does it have a wall on any of these sides so what I'm going to do is gonna be a little bit straight I think a way of doing this is to create boolean variables so I have a boolean variable for the top for the right for the bottom and for the left top right bottom left are are their walls from Earth or does the wall exist for this particular cell so let's let's look at how I might do that so each cell and honestly I think what would be easier would be to say this dot walls equals true comma true comma true comma true so I'm creating an array so each cell when it starts every wall is there true true true true so it's up to me to memorize let's all memorize this together top right bottom left top right bottom left stay with me top right cot of left okay that's going to be the order did I get it right here top right bottom left I think that's the right order X 2 X plus W oh I to y plus W X plus W 2 X y plus W 2 y I'm pretty sure I got that right so what I can say here now is if walls index 0 then draw this line and I'm going to repeat this a bunch of times and put in and picture there's a key command this is the first time I've ever used Adam I bet you there's a key command to auto format it and one and two and three now I'm sure some of you could come up with like a case statement or you wouldn't need the curly brackets but I'm trying to be as explicit as possible so these are the lines I'm going to draw if the wall exists so you can see here I hit refresh ooh walls is not defined so what of course I made the mistake that I always make which just needs to say this dot walls in all of these and you can see there it is now if I change this to false false false top middle right weight top right bottom left all right if you got top right bottom left we should only see the left lines and you can see those are all the left lines so and we can be sure about so so you can see it at some point I'm going to be able to change these boolean variables from true or false to add and remove walls based on how that labyrinth should look ok so I think I'm actually this concludes this first video where essentially all I've done is set up a grid a two-dimensional array ah it's a one-dimensional array and it has a bunch of cells that live on a grid each with an eye in a J each cell is drawn as four lines top right bottom left I probably said something totally wrong before because I think I was middle there's a middle top right bottom left top right bottom left and I also have a mechanism an array that has boolean x' in it to know whether top is right is true right is true bottom is true left is true if those lines should be there or not okay in the next video I'm going to look at the algorithm and see how we start to start from one of those cells and decide whether to remove a wall or not and that will start us with actually start the maze creation itself

Channel: The Coding Train

Views: 329,501

Keywords: coding challenge, p5.js, maze code javascript, object oriented programming, programming, processing, challenge, tutorial, maze challenge, oop, object oriented, programming challenge, p5js, javascript, programming maze, nature of code, coding, recursive, recursive algorithm, depth-first search, recursion, recursive backtracking, depth-first search javascript, maze generation, maze generation javascript, maze algorithm, creative coding, javascript maze, maze, recursive backtracker

Id: HyK_Q5rrcr4

Length: 16min 4sec (964 seconds)

Published: Mon May 02 2016