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