Welcome to part three of my depth first search
recursive backtracking magic maze generating Algorithm in the browser using p5.js project
So this is what [I'm] trying to make and where [I] am so far is kind of along the way there
You can see this something similar is happening
Here where I'm starting with a cell and a grid and I move to a cell next to it and I move to a cell
Next to it
I move to a cell next to it
And I never go back and move to a cell that has already been visited the visited cells being highlighted in purple
[so] what are the next steps?
Let's go to our Wikipedia
Page that had the algorithm very nicely laid out for us and we could kind of see what we've done so far
So by the way there were on part one right now
Part one if the current cell has any neighbors which have not been visited
We did that already what choose randomly one of the unvisited neighbors? We've done that already
skip step two skip step three step four
Make the chosen cell the current cell and market is visited so all I've done so [far] in building
This is step one and four so I'm just moving from cell to cell to cell to cell not revisiting any cells now
[part] step to push the current cell to the stack. This is something I'm going to visit in the next video
What is the stack why do I have to keep track of [the] stack what does that all mean?
I'm Gonna get to that this video
I'm gonna work on part three remove the wall between
The current cell and the chosen cell the chosen cell who is the chosen cell okay?
Let's figure out how we're going to do that
I kind [of] like figure out in the code where that is or what we're even talking about
[so] there's we already have the pieces of this somewhere, so here. We are. This is the thing running here is our code
let's go down [to] the cell object and
We can see here's one thing so each cell object has an array called walls with four true variables in it
True. [oh] top right bottom left top right bottom left. So let's say the two cells are next to each other
One is to the left and one is to the right one of them needs to remove its
Right wall so that would become false and the other one needs to remove its left wall
For and that would become false. I got to draw a diagram here to understand this let me come over. This this is tricky
And I think we can just get rid of this larger grid now. We kind of understand that so this is what I mean
There's really four scenarios
Right this is this [is] the cell and this is the neighbor
This is the cell and this is the neighbor, right?
So this is the wall that needs to be removed the cell needs its right wall removed the neighbor needs its left wall remove
Here the cell needs its bottom wall removed the neighbor needs its top wall removed
how do we know which is which well if this is I and this is I plus [one] right the difference between
You know one cells you know
Like cell index I - neighbor Index I right that'll tell us if it's to the right or the left
Because if this is I is 45 and this I is 46 and we take 45 minus
46 we are going to have what?
Negative 1
So if we get negative 1 that means we have a neighbor to the right so let's let's sort of what I'm tripping over lights
And things let's start looking at that in our code
So what I'm going to do now is I'm going to write a new let's look in [the] program
Where are we we're right here in the algorithm right? This is this is a
Step 1 and
This is Step 4
According to that Wikipedia page right step 1 is market is visited and step 4 is set it to be the next one
Actually step [1] is really here pick a random neighbor
[pick] a random neighbor market is visited and in step 4 is current equals the next one so what I need to do is implement
Step 2 which if you recall is
Not step two step three
which is remove the wall between the current cell and the chosen cell so I want to do is fe and you know what I'm
Going to make that in a separate function. I'm gonna. It's already knows what I'm going to type doesn't that insane?
remove Walls and
Between what current and next right we need to figure out current and next I want to remove the wall in between them
So now I just sort of thought of a function. That's good
I could say a current dot remove walls next but I'm just going to put it in a function and a passed them two cells
Figure out how they are in relation to each other and remove their walls so I can just go all the way to the bottom
Of my code now and work on this somewhere else
So I'm going to say function remove walls a b. So I just have to whoops come on
Let's save it wants to get rid of all [my] white space on the bottom, but I want white space on the bottom white space
Because I want to type it in here, okay?
[so] [I] want a [generic] function that takes two cells and removes the wall between them sell a and sell B
So what do I need to do the first thing?
[I] need to do I'm going to call x be a dot I minus b
I so this is exactly what I'm doing [the] value x is the difference between
This cell and that cell so let's think about this scenario
Where this is cell 46 and this is cell Column 45
This is a index i [b] index I a index. I minus b index I is [1] so
if
x is Greater Equal 1
that means a
Dot walls what okay? Okay? Come back over here?
[I] want the left wall to be removed
Top right bottom left 0 1 2 3
so I want a
Wall Index 3 to be False and now B
should have its right wall moved removed top right bottom left 0 1 a
B dot Walls
Index 1 equals False
else if x equals negative 1
then I want to say
then there the inverse of that right if it's negative 1 then I want the
Right of a and the left of B to be removed that's pretty good right [this] makes sense
And I'm going to use triple equals to be kind of more serious about I'm very serious about my equals
Ir believe and as many equal signs as possible to be sure we know what's going on
So that's your work now. I need to do the same thing with y
And so y is what?
Aj - BJ, and I'm going to do exactly the same thing and
Say now if y is 1 or y is negative 1 [and] now okay, so let's think about this
Let's say I think we can figure this out without a diagram, but I'm going to do it anyway, so let's say
This is y and it is [row] 30 and this is a and this is B. And it is Row 29
so a
Dot J. Minus B
Dot j. Is 1 so if that's the case if a dot [jayma] then a needs it top removed and B
Needs its bottom removed ok coming back over here. [I]
[need] its top B. Needs its bottom 0 1 2 so [a] needs its top B. Needs its bottom here a
Needs its bottom and B. Needs its top removed. I think we've got this right
There's only one way to find out and we are going to now call. Did I already call remove walls in the right spot, right?
[here] yeah, so [here]. We go. Let's just try it. It should when those go false. We shouldn't see the lines anymore
Let's just see how it goes, ooh
Huh, so I don't seem to be seeing anything happening here. So what's going on?
What did I miss still kind of marching along?
but I'm still seeing the walls being drawn so
What did I what did I miss here, so first of all let's just make sure this is happening
and
So [ok] so that function is being called all right? So what am [I] missing in that function?
Let's look at what x is
whoops
Console.log let's look at what this value of x is
Negative 1 0 1 negative 1 0 1 so that should be it seems to be giving me numbers that are the right idea
so let's just see
let's just log the object here ah
okay, yep, yep, yep, so
now I'm going to look at one of these and
Look at the Walls array ah so zero and three got turned to false, so this is working like stuff is happening here
[right] you can see by the way. This is like a nice way [of] debugging I can look at each object
I can see its walls array. So what did I miss?
Probably maybe something in the actual cell object. Oh, you know what I bet you is happening. Oh
I bet you what a silly little problem
That I forgot to say no stroke here
So the rectangle that I'm drawing to highlight the ones that have been visited always has its stroke
So it makes it draws the full rectangle. No matter what so I think that should be there
We go so we can see now as it's moving the walls are being removed. Oh, beautiful. [oh] come on
Give me a longer. Give me a longer sequence here now one thing. I would like to do also
Just like keep the highlighting stuff going is let's just go back to
[-] to the main program [and] I'm going to call at the end here a
Current highlight, so I also want to be able to step see which one is current
This is just a little I'm really done with this part
But I just want to visually add something that I think will help us so in the object
I'm going to add a function called this
highlight and
What do I want [to] do? I want to draw a yet another?
Rectangle no stroke, and I will color it a some green color with some alpha
and draw a rectangle xy
with the same size
I just wanted to add that really quickly and refresh this now so now we can see also which [one's] the current cell
Okay, great. So here's the thing. This is actually working out, and it's making our maze. Well. [I] [just] love it
Look we can see our maze the problem is it gets to a certain part?
It's like trying to figure out this maze, and it's done
It needs to go all the way back and break out somewhere else like it needs to go back track now
Maybe once it gets to here
Actually, all you [need] to do is go here and then start going this way because that turned out to be a dead [end]
So it can start going this way, so this is where the backtracking comes in right? This is where in the
Algorithm part two comes in push the cell to the current stack and then if the stack is [not] empty pop a cell make it
the current cell so I need to discuss that need to unpack that figure out that's a confusing piece this will involve a lot [of]
additional concepts
I'm going to do that in the next video
So right now if you're following along and building this you should at least though have this much done and just for fun
Before [I] end this video. Let's make this like 10, and let's like make it go fast now and hit
Refresh and just so we can see like we can see this is really
Doing something now [like] it's actually like just carving out this maze and in with a finer degree of detail
It's going to be a while longer before it
Finally gets stuck but [okay], so you see that we're almost there and we're going to go to the backtracking in the next video
Okay, see you there