Hi, welcome to this new lesson. We're going to continue working
with our pathfinding algorithm, and we're going to jump
straight into the code. In the past video, we actually understood
how the Astar algorithm actually operates. So let's just jump into code and
start seeing how to work with it. I'm going to continue working
with the same script that we have from the last session,
where we have been building the flood field algorithm that has
a optimal path solution. This is the algorithm
that we're working with. And what we're going to be doing here
if we just jump into the environment, as you can see here,
we are using still the flatfield. I'm going to comment that out. This is going to be our first
neighborhood calculation. We're going to use a different one this
time, which is going to be our a star, right? So let's just,
maybe we can call it out here already. So self.a_star_search, right? And we don't have that function yet,
we're going to construct that. So let's just go ahead just above
the flood fill because we know that's the area where we actually worked on
the tower search algorithm, the flatfill. So we're going to use a different one. It's going to be borrowing
a lot from the flat field, but it would be fundamentally different
in many other domains, right? So there's a few things
that we want to change or data that we might want to
have available to us. So we have already an open list, let's say
a list that it's called a stack, which we use as the frontier, the kind of searching
nodes that keep on growing, right? So we're going to keep this,
traditionally in the a star algorithm, this is usually called the open list,
right? So we're going to keep it called stack. But if you see this algorithm online or
you find reference to it, I'm going to remain maintain this name,
right? So let's create another
list called the closed. And I'm going to close
the closed_stack just for the sake of having some reference
to this one here, right? So you can refactor those things,
these two, if you want to be, have this algorithm
kind of more accurately connected to how you might find it in a textbook, right? So we have the stack and
the closed stack, so basically one will represent the areas
that we have already searched. The closed and the open stack would be
the areas that we're still evaluating. So that's great. We actually doing the same thing, adding the start node to the open,
to the stack basically. And we're kind of ready to go to start
writing the algorithm as we have it here. So we're going to do the same thing
that we've done before if running. So we're going to be
checking if we are running. If the stack is not bigger than zero,
this is also going to be the same. I'm going to copy paste the things that
are exactly the same from our flood fill. If the stack is bigger than zero here, we're going to be doing
something different. If you think about it, the current
cell here, it's going to be equal. Once we grow the algorithm, let's say to
its neighbors, the selection of which cell we're going to be growing towards, it's
going to be a specific selection, right? Previously we were just saying, hey,
from the stack, pick the first one in the order that they came,
just goes through all of them, right? So here,
there's going to be a major difference. I'm going to make a comment here, and I know this is going to end up in
an error if we would write it this way. But we're going to find the closest f,
right. If you remember from the past video, the f
value, which is a summation of h and g, meaning the cost of the path plus the
distance of the path that is remaining. So we're going to evaluate those values
and find the, the smallest one or the, or the closest one to
continue the search, right? So we have to pick one specific cell. So we're going to write a function for
that. Let's go to the tile. And in the tile I would like to add after
the parent a few attributes that we will need. So self.g,
all of them will start with zero, self.h, and by all means just
create comments to this, right? The g being the cost of the path,
h is the heuristic function, which in this case is
going to be distance. So distance to reach the goal. And finally f,
which is going to be also zero. But you can write a comment that
is the summation of g and h. So now a tile should have these
properties that we can use, right? Why do we want to use these properties? Because we will need a function. Let's just create that
function right away, which is going to be find closes f, right. So define closest f, right? We'll assume first of
all that we have a self, and we're going to pass a list. So if we provide a list of nodes,
we will need to calculate which is the smallest
f available, right? So we're going to create lowest f,
let's start with a very big number. Lowest f node, it's going to be none. And we've done this calculation before. We've done it for other things, finding
the closest particle, things of that sort. But in a similar fashion,
we're going to just loop through the list. So I'm looking through the list, if the node.f is smaller
than the lowest f, right, then the lowest f equals the f of that node, right? So here and the node would be the node
we're currently evaluating, right? So we're saying if the distance
is smaller than, or the f number is smaller than this
large number, then at that point that becomes the smallest number and that
becomes the node that we should check. But we loop through all of them. And this would allow us to pick out of a
list of many nodes which has the lowest f, right? So then at this point we
can return the lowest node. So what we're really looking for is the specific node that
has the lowest f, right? So out of having many nodes, we would end
up with one, the one with the lowest f. So this calculation here, which before,
if you look at the flat field, was selecting the first item, now it's
going to be fulfilled by this function. Out of a list make sure you
pick the one with the lowest. We haven't really yet
assigned a g score or an f score to our nodes, right? So for now it's kind of going to work
similar in the sense that the value would be zero. But we will do that in
the rest of the algorithms. So let's just do this for now. We're going to find the closest,
and we're searching for the closest within the stack, right? The stack is kind of the open list and
there we go, right? So the next part, it's going to remain relatively similar
to the flood fill is this part of the algorithm where we're actually
checking how we reach the end, right? Let's just copy paste,
paste this for a moment. And what we're saying here is that if the current cell is
equal to the final node, we reach the goal,
we stop running the algorithm and we can reconstruct the path, right? Let's do the following, which is we're going to,
from the open set, we're going to remove the cell self.stack. So from the stack,
let's just remove, you see, because here we're not
using the pop function, which automatically removes
the entry from the list. We're going to remove the current cell so that we don't end up with always
some nodes that are there. We need to make sure that
list starts becoming smaller, and we're going to add
that to the closed stack, which is equivalent to the visited nodes,
right? So for the closed stack, we're going to
append the current cell, right? So we're transferring the cell out
of the openstack to the closed stack if we evaluate it, right? And this is only happening if
we haven't reached the end goal, which is the moment where
the algorithm actually stops. So let's go through now
the neighborhood calculation again, very similar to what we've
done here in the flood field. Let's just go through for a neighbor in current_cell.get_neighbors, right. So the first thing we want to do,
similarly, as we have done before,
we're going to say if the neighbor, in this case, in, if we're going to check, is it in the closest tag or
is it an obstacle, right? In that case, continue,
just like skip this one. So we're going to say self.closed_stack or sorry, in close_stack, right. Or neighbor.is, I believe that is obstacle was written
a little bit like this. Let's double check how
we did the obstacle. Yeah, this is a function. There we go. So we're saying if this particular
neighbor is in fact within the closed stack or is an obstacle,
let's just say continue. And continue is a keyword that maybe we
haven't used too much, but it's a way of like breaking from this for loop, meaning
that the for loop can continue otherwise. But if it reaches any of these conditions, it would skip this,
this particular iteration, right? So let's write a variable
called tentative g and the tentative g is this cellscurrent. Cells g, meaning that the cell that we're
currently evaluating has probably like, let's start with g,
which is a cost of zero. We're going to add one to that. So as we kind of grow the search,
we're going to be adding, this is the way in which we
keep growing the value of g. So every step we're
going to be adding one. And we're going to create a variable,
say new path equals false, which we're going to be
using within the loop. So let's just wait a moment and
we're going to be using this. This is something that is
going to just allow us to signal if we have found a new path,
right? So if the neighbor in self.stack. So if the neighbor that we're
currently evaluating, right, is part of the stack,
we're going to do the following. We're going to do neighbor.g
equals ten to tg, Right, so we're assigning to that neighbor
the tentative g and new path equal true. Right. And else, meaning that the, if the
neighbor is not in the OpenStack right, We will actually append it to the stack. So we're doing the same thing for both
of them, but we want to make sure that if we're evaluating a neighbor
that is not in the stack, we're adding it to the stack, right. So we would say the same thing here, Plus, Right. And finally now,
if we have found a new path, so only in the case that if we
have that path that we marked. So if new path has been found,
let's assign some of the values that we've been discussing, the h and
the calculation of g plus h. So neighbor.h, which if you remember
the h is the distance, or the heuristic, it's going to be the distance from
that neighbor to the end node. So we want to say distance. And a lot of algorithms actually use
different distance calculations that could be more efficient. We're going to use the inbuilt
distance that processing offer us. Neighbor.position.x, neighbor.position.y, self.end_node.position.x and feel free to just break
this into two lines. Find necessary. So the distance between the neighbor,
which is the current cell we're evaluating,
and the end node, right. So that is the h, the distance, right. And the neighbor.f would be neighbor.g plus neighbor.h. So this is the part where we
have already calculated the g, which is the cost of the path,
how many steps have we taken? At this point we also calculate the h,
which is the distance remaining and the f would be the addition of those two,
right. G plus h. And then at this point we could say
that the parent is the current cell. So neighbor parent equals current cell. Well, there's one final else that
we might want to include, and this is maybe optional. I'm going to think it's here. Let's just see. We're going to say print line No solution and self running equals false. Yeah, so basically this is it. We have two new functions. The start, the a star search,
and the find closest, which is used within the a star search,
right. And there's a particular point where
we actually calculate the distance and mainly this equation is used here. But more importantly, when we
are selecting which is the next cell to evaluate, we have to do it by searching
the smallest f or the closest f, right. Let's see what errors do we have? Well.
So it's actually working already very well. So as you can see,
the path reconstruction, because we're using
the same parenting system, the parent, it's achieved here,
it still works. The obstacle detection, it's also working
because we're including that here. We're avoiding cells
that contain obstacles. What we are not visualizing currently, like if you think about it, we have been visualizing the stack which
remains being the open set, which is demonstrated with CN, right? With the CN color we have the open set. So there was search going in this
direction and then it changed its mind and it went this way. And that's all good, but
we would like to visit, probably these cells here were visited,
so they were part of the closed tag. So we're actually going to spend
a bit more time really understanding the algorithm in the next few
videos through some visualization. Like adding some of the text
on the algorithm, but also being able to paint the cells that
are being evaluated with what data, right? So I'll see you in the next video. Yeah, we're going to continue
looking at that data then. See you then.