Welcome to this new video
on our pathfinding project. Today, we're going to be looking
at a really fun algorithm, a calculation that we're going to be
calling the Flood Fill calculation that is going to allow our cells to grow and
access neighbors and continue accessing neighbors until we
can go from one point to another, right? So let's just look at what
we're going to try to do. So the Flood Fill calculation,
it's a simple way for a cell that we're going to create,
it's going to be a start node, right? So we're going to define one arbitrary
cell to be our starting position, and we're going to basically expand and understand what are the neighbors
of that cell, right? And once we have the neighbors,
we're going to flip the information. We're going to need
a variable called visited, meaning we've already covered this cell,
right? Visited this cell, but at that point, we
add all those cells to a new collection, which we're going to call a stack. Also could be understood as a frontier,
and we're going to repeat the process. Basically, we're going to access
the neighbors of those cells and only if we haven't visited those cells, we
added those new cells to our new stack or our frontier. That would naturally start creating
a sense of expansion, right? The blue tiles, as you can see here,
are going to be the visited tiles. The new tiles that we are evaluating
are going to be the outermost tiles, the frontier,
which are going to be a list, a specific list of tiles to
be further evaluated, right? And if we actually have an end node,
if we reach an end node, we could actually stop the simulation,
so this doesn't run forever, right? This would naturally cover out
the entire grid in this case, but because we're trying to implement
these ideas, pathfinding logic, we're going to create a start point,
an endpoint and once we reach an endpoint,
we will, in fact, stop, right? This is the idea that the frontier or the stack we're going to be calling
a stack is going to be a list of tiles. That is, we constantly going to
be going through this list and expanding that list through
the neighborhood calculation. So adding new tiles to that list until
we really kind of run out of tiles or we reach our target. So, it will make more sense
as we start writing it and we start kind of visualizing
some of the information. So let's start writing it
in processing together. So I'm continuing the project
where we left off. We have a neighborhood calculation
which works if you want to revert to the customization of the environment. You can comment out the neighborhood. This was just a check to see if
the neighborhood calculation was in fact working well. But we basically should have an
environment that we can customize, right? So let's draw work here
in the environment. Let's create a few things that we
might need for the simulation to run. So sometimes I like
leaving a bit of space, knowing that this is kind of
the initiation of the sales function. But let's just create a variable
called self.start node. And we could start with something like, or basically none,
just to have something self.endnode. At this point,
we could basically define like these nodes are going to be necessary for
our simulation, right? going to be our start point, an endpoint. Let's just,
instead of making them be empty nodes, let's just create self.getcell. And here we can specify the index of
a cell or, sorry, a coordinate, right? Somewhere we say 100, 100, right? The cell associated with that
will be the start node and the cell that would be our end node, let's just do something within the canvas. I don't want to break the logic here and
get something outside the canvas. We wouldn't get a correct node, but
we know that our canvas is 1200 by 600. So I'm trying to get something
in the top leftmost corner and somewhere in the right corner
to be starting an end nodes. I would like to visualize those nodes. And we actually have
a pretty handy function that makes those nodes
visible to draw highlights. So we could say something like draw start. And then here we could say that the color,
I mean, remember what we were doing in the last
video is basically this equation here. So the start would be a color, right? Let's make that red. And the cell that we want to
draw is the start node, right? So let's just draw the start node. Let's draw it with this color, right? So let's see. Okay, so we don't see it. We have to draw the start. We have to call this within our, Run loop, right? So we have our start node here. And I'm going to do this as independent
functions because I like having, even if there's going to be several functions
here, we're going to copy that function. Let's draw end, And let's do this one green, right? And here the node that we want
to draw is the end node, right? So basically we can copy paste this now. So we have a start node and an end node. Basically we are creating
an arbitrary node to be our starting node and
an arbitrary node to be our end node. So that's great. Now let's start creating some
of the data that this algorithm, the Flood Fill algorithm will need, right? So let's just create an empty list that
we're going to call the stack self stack. Stack. It's going to be an empty list and
we also want to add to that stack. A stack it's an arbitrary name. If you want to use
a number like frontier or something like that,
that makes more sense to you, right? By all means, just change that. We're going to do append, we're going to add the,
what do we want to start with that stack? We want to use the start node, right? So basically the stack is going to
be the nodes that we are evaluating. Sorry, that should be self.start node,
right? Again, let's double check
that we're not any error. That's fine. We can construct environments, but we'll
see that our system is not going to read these columns just yet, but or these walls
just yet, but we're going to get there. So we have basically a point of start. Our stack has a node to work with, right? So we can actually start writing
our algorithm right now. Let's just call it, we're drawing the tiles here, let's create a bit of space here and call it the flood-fill, right? So one thing that we would like to do,
where are we going to call this algorithm? We're going to call it within our run
function, so if we run it forever, it would actually continue growing, right? So for
that I would like to have a variable which is going to be a Boolean that
we can call here self.running. And let's say that's true,
let's do true, right? Basically I want to have a condition
that starts growing, but eventually we reach an exit point and
we stop running it, right? So with this variable in mind,
we can write our first line or our flood-fill, which is that,
well, if it's running, right, let's execute the algorithm, right? The second thing we want to do is
that if the length of the stack, We're checking if the stack
is bigger than zero, meaning that we haven't run out
of tiles to execute, right? What we're going to be doing
is picking an entry on stack, get its neighbors, and
add those to the stack basically, right? So we're going to say that the current cell equals self.stack. And here we're going to use the pop,
something we learned a little bit ago in the second course, I believe, when
we were talking about list operations. And we haven't been using pop too much,
but it's incredibly useful here because pop,
it removes an entry from the list, right? So think of that,
you start with one point or one node in that list and
you're assigning it to this cell. But now that list, you remove
that entry from that list, right? So the first entry of
the list gets removed, gets assigned to the current cell. That means that the stack,
it's kind of shrinking. It's obviously, it's going to grow
as well when we get the neighbors. But we don't want to have that stack
like just adding entries to that list. We want to be able to make sure that we're
not going through entries twice, right, so the pop is going to be really useful. What we want to say is that the
current-cell has been visited, right, but that information is not part of the tile,
right? So let's add a new variable to
the tile called self-visited, it's going to be a Boolean,
it's going to be false, right? So once we have that, we could actually
assign now to the current-cell. This current-cell,
we could say visited equals true, right? Because I want to make sure
that we marked it said, well, this has been visited,
therefore we can move on, right? And we're going to visualize this as well,
I think it's useful for us to make a visualization
of the visited tiles, right? The next thing that we want to
check how we reach the end, meaning we have an end node, right? So if the current-cell,
it's equal that the self-end-node, then at that point we've reached our goal. We could actually print line and say, hey, we Goal Reached. But most importantly, in order to
stop the running of the simulation, we could say self.running,
which is that Boolean equals false, right? So we could say at this point stop
running the simulation, right? That's the goal of achieving,
we're first checking, we check if that node is
in fact the end goal. Obviously in the setup that we have right
now, the start point is not the end point. So it's not going to happen right away,
we need to kind of start growing now. So here's where we're going to do
our neighborhood calculation and we're going to say for
the neighbor in current-cell. So we're checking the current-cell,
we're going to get the neighbors. So that's a function that we constructed
already, right, let me just a column here. So we're saying if the neighbor we're checking in this loop hasn't been visited, right? The neighbor, Becomes visited and we added to the stack. So self.stack.append neighbor, right, so let's see what's happening here. The stack only has one entry point,
right, we loop through its neighbors. If those neighbors haven't been
visited for whatever reason, maybe the algorithm is kind
of running around a corner. At some point we're checking if
that neighbor hasn't visited, we will check that neighbor has
visited and we add it to the stack. So that stack entry now will actually
repeat this loop will actually go again and
basically the stack will continue growing. One of the things that I like
visualizing are two things, is which tiles have been visited and
which tiles are the current stack, right? Because those are dynamically
changing over time, right? This is the entirety of the flood field,
but we wouldn't see much. Maybe if we let it run for
a while we'll see goal reached, right, because the growth eventually will reach. But I don't like really operating under
the premises that we cannot see what's going on. So let's for
now do one more function here which is going to be the definition
to draw the stack at least. So we draw the stack and then we go and
see how to visualize the visited tiles. So the draw-stack will be, We're going to use
the same idea of a color. Let's just use a cel color this time where we use something like that. And for cell in, basically we are looping through this stack this time, right? And we could say cell-display, right? Display highlight, which is basically
this function that's, Becoming very useful to visualize all sorts of
cells in different conditions, right? So let's just make sure
that we add first the flood field to actually, so we draw the start, we draw the end,
we execute the flood field and we also want to visualize the stack. Let's see if we're running into errors. Okay, so this is running, so
we're seeing now that the stack are all the cells that are in CN and
they're actually growing. It's not moving inwards because these
cells here have been visited and seeing those would actually
be really useful as well. So let's just do a visualization of that. Let's just check if the algorithm at least
once it reaches one of these stack nodes, if it becomes equal to the end node, we
should get a message that says we reached the goal, right, and it stopped, right? Great, so this in fact worked,
we reached the goal and basically one of the stack cells
was equal to the end node. So it's a very slow
algorithm to actually reach. It doesn't have too much intelligence, but
it's in fact using the neighboring cells. Let's just finish this lesson with
visualizing the visitor nodes. So we drew the stack,
how could we draw the visitor? So dev draw visited, we're going to say these are going to be blue as we've done before, RGB, right? And here is for column in self.cells,
this is a nested list, in all of them we're going to
check if visited, which is the, it's probably not a very
efficient way of doing it for now because we are kind of looping
once again through all the cells. But I would like to kind of for
graphic purposes, this is a kind of a visualization
layer that we're going to turn off, so I don't want to kind of
embed it into the tile. So we're saying for column in cells, list a cell for each entity called cell within the column if that cell is visited, right? Has the property which is a boolean true,
right? If that's true, cell.display highlight, with the color blue in this case, right? Because we said we define the color, that's the color we're going to pass here,
we're passing the color. So the same function, display, highlight can display things
in different colors, right? So that is dev visited,
and the visited here's where the order might be
important because if we draw the visited,
I'm going to draw the visited first. Because I would like to draw the end and
start node and stack on top of that, right? So let's see if this runs okay,
so that's more graphic. Yeah, so
we have an algorithm that basically, every time that you're in Photoshop and
you press like feel like an area and it would kind of spread
pixels in that area. This is kind of roughly what's going on,
right? We have pixels that keep expanding within
that region based on adjacency and neighbor relationships. And in this case we're kind of putting
it to the task of reaching an end node, a specific node that we
know that it's our target. So yeah, we have some
visualization of the visited nodes, the stack which is the dynamic list
that we're using to keep track of which are the new frontier neighbor or
frontier cells that we're using to continue growing our search and
the start node and end node. So with this,
we're going to leave it here and start talking about obstacles in
the next video, I'll see you then.