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