Hi, welcome to this new video
on our pathfinding series. We're going to continue our pathfinding
simulation working with the code that we've done in the past few videos. And in this video, we're going to be looking at how
do we consider obstacles, right? We currently have a flood fill
simulation that grows and obstructed by any kind of wall or
anything, any kind of tile. But we would like to make this
simulation grow differently if it reaches an obstacle. That's why we have an environment where we
can customize and draw obstacles for it. So this is going to be giving
us a lot of really opportunities to see how this algorithm
really can become smart and figure out a path through
a challenging setting. What we're going to be doing is rather
simple, but we need to make sure that we are preparing the data to have
the right information, right? Our flood fill, the only variation
that we're going to have, is if you see towards the end of it, when
we're checking if a tile has been visited, we're also going to check if
it's not an obstacle, right? So if it's an obstacle,
it won't add it to the stack. Therefore, the stack cannot grow towards
in an area that it's an obstacle, right? Sounds simple,
Let's add it to the code, but let's make sure that we're actually
providing the information of what is an obstacle in a manner that
actually makes sense for this algorithm. So we're here,
this is what we have so far. We have a flat field calculation
that starts automatically. We're going to change that as well,
so that we can actually decide, give ourselves a little bit of time to draw the
environment before we actually execute. So if you remember,
if we go into the tile, if you remember, we have a variable called is_obstacle,
right? And we have it by default, false. So let's just say that when you create
the tiles or when you paint the tiles, you're changing the tile type from
floor to wall, and so on, right? We would like to specify that if a tile is of a particular type, we will convert it. We're going to decide if it's an obstacle,
right? So we could decide, well, look,
maybe wall and water are obstacles, right? So let's just create a function
that filters through the data, and allows us to say, well, if you
are giving me specific type of change, I'm going to make this property
of being an obstacle being true. So let's say defined change_type, right? So the change_type,
currently we are doing it very manually. The environment sets the type of
the tile to be zero or to be one. Now, they're going to have to
go through this function, right? So that's the opportunity for us to say self.current_type = type. So that's what we have been doing before. But let's add a bit more to that. We could say if (type equals 1 or type equals 3). So 1 and 3 refers to,
if you look at the indices, 1 is wall and 3 is water. And this is, again, you could add
more tiles that represent obstacles. We could say self.is_obstacle = true, right? Else, self.is_obstacle equals false,
right? So now, if we would like to
change the type of a tile, we go through this function, right? So where are we changing the tile type? We are doing that into the paint. Where do we have it? Paint_cell, right? Here, we are using this line
that says current_type = type. That's kind of something that
we don't want to do anymore. We want to say cell.change_type(type) specify in the argument here, right? So we're going to be saying
change it into a wall. And when that change happens, the tile will automatically define if it's
an obstacle or not an obstacle, right? So let's check that this is running. It still should work. We can paint our obstacles,
but as you can see, our obstacles are not by any way
affecting the growth of the algorithm. The second thing I want to do
before I include the obstacle calculation into the system is,
as I mentioned before, I would like to make that
the running starts being false. Are we running this flat fill? We're not, right? We're not trying to run it. It's going to be false. But I would like to add a way
of making it true, right? So let's just here in create
a bit more interactivity here. We're going to say if(keyPressed), if the key that we're pressing is 's'. Or if the key that we're
pressing is capital 'S'. Oops, capital 'S', then my_environment.running = true. So that means that if we press
the key s in our keyboard now, we can start the execution, right? That gives us time to customize
our environment, paint some walls, and paint some regions, and
then execute the running of the flat fill. So that's great. Finally, let's just add that in a flat
fill algorithm here, in this line here. If the neighbor that we're
evaluating is not visited, what else do we want to add there? We want to check if it's not an obstacle,
right? So we also want to say and not neighbor dot, what is the name of the variable? Let's just double-check. The variable name is obstacle, right? Let's just make sure we are using
the same variable name here. If the neighbor is not obstacle, right? We could say if neighbor obstacle
equals true, but we're using the node, meaning if the neighbor has not been
visited and it's not an obstacle, then we can continue growing
our stack in that direction. So let's see if this works. So now, we have the time
to kind of create some kind of environment that would make this flat
fill maybe grow at a different pace. So now the growth, as you can see,
doesn't go through the walls. It's actually being kind of limited
by the walls that we created. And of course, if we want to create
a region that is unaccessible, the algorithm shouldn't be
able to reach the target. So therefore,
it would actually feel everything, but it will not reach the target, but it would actually cover everything
outside the target, right? So yeah, that's how we have obstacles
being taken in consideration. So with this in mind, we have included
obstacles in the calculation. Now, we're going to be able to kind of
start kind of understanding what would be the optimal path. Now that we've done this algorithm,
if we have to backtrack, what would be the best path to
go from the start to the end? So there's a lot of interesting
calculations that we can do on top of this. So I'll see you in the next video.