Hi, welcome to this new video. We're going to continue working on our path-finding series, and this time around
in this video, we're going to be
looking at how to calculate the optimal path. Let's start by understanding
what we have achieved. We have been working with a
flat field algorithm that grows a search area, as you can see in the
blue cells on the right, and a frontier that keeps
looking for this end node. When one of the frontier nodes overlaps with the end node, we know that we have found
a path or there is a path, in fact, to reach that end
note from our start point. But we still need to
figure out how to kind of reconstruct the optimal path
back to the start note. This problem is something that we need to do a
second calculation, basically, a second
loop where we're going to trace the path
that took us there. We need to be able to store some information in all
the cells of what is the cell that took me to the point in which I'm
evaluating currently. As long as each cell has, let's say, we're going to
call that a parent cell, a cell that took
me to that cell, once we reach the Bengal, that goal would be
able to trace back its path to the starting node. That's what we're
going to be doing. We're going to be
writing a function that is going to be
reconstruct path. That's going to
use a while loop, where we're going
to use this new property that we're
going to create, which is the parenting property that we basically
start building up the series of cells
that contribute to the solution or
the optimal path. Let's remind ourselves
where we're at. We are here in our
path-finding system. We have a way of drawing walls, and with S. By pressing S, we can start the flat field algorithm that we'll
start searching. You could see this
Canvas is rather large, and it might take a while to test our condition of success. We could decrease the resolution of our Canvas a
little bit so that we can actually run this
situation a bit easier. Let's just do maybe half
of what we have currently. We can do 30 by 15. That's the columns and rows. You can see the solution
becomes a lot easier to evaluate because
we actually get to the goal in a much quicker way. What we want to do
is at this point, once the objective is reached, we can trace back
the information to the path to the start node. Let's start by going
into our tile node, and we're going to
create a new property, which we're going to
call self-parent. This is going to
be equal to none. By default, we're going to
say this property is empty. This property, it's going
to be another node. We're going to be
giving reference to what would be the
node that took me here. The next thing we have to do is actually start looking into our flood fill calculation and understand where
within the code. We basically go through
the evaluation. But at this point, when
we reach the end node, this statement here say, goal reach, we actually have
something that points out, look, we actually
reached the goal. Here, let's say, what
we want to do is the reconstruction, of the path. This happens only once,
once we reach the goal, and we will store this
information into a new list. Let's just look into how to
construct that new list. Let's just go back up here, and we do have the stack list, which is the frontier,
basically, the searching. Let's just create
another one called path. This is also going to be empty. The path is going to
be an empty list, and we're going to
populate that list with our reconstruct path function. We have that information now. We know where we have to call the function, which is here. Now the only thing that we're
actually missing to be able to really write that function
is to store the data. We don't have a way of
currently storing the data. But if you think about it, as we are going through the loop here, each neighbor cell or each cell, we go through its neighbors. In fact, we grow the searching in that
particular direction, meaning that it hasn't been visited and it's
not an obstacle, we add it to the stack. At this point, this cell also, we could say that
the neighbor parent. The neighbor is
basically the cell we're evaluating
from the neighbor, the parent, is equal
to the current cell. Basically, this is
the cell that took me to that new neighbor. This is a way in which we could fill information for those cells that actually do have in fact neighbors that
continue the search. This is a way of
creating this linkage between each node
and its parent node. Now that we have a
parent information, we can actually
write the function. Let's write the function that
is called reconstruct path. We're going to start with self, and let's give current cell. What we want to do, as we discussed is
a while loop while this current cell has a parent, so parent is not known. We're starting here
because we know that we have identified a parent
by default is known. If it's not known,
self.path.append. We're going to add to this
new path the current cell. Now the current cell equals
the parent of that cell. What we're doing here is that we're starting from one cell, which is going to
be the end node. We reach the target.
We have the end node. We find the parent of that node. We go back to that node, and we do the process again. Does this cell has
a parent, yes. It goes back to the parent
that took it there. Basically, we keep doing this sequence until we
reach the start point, which, in fact, if
you think about it, the start point would not
have any parent because the default condition of the start node is to
not have any parents, and that is only a property
that is path as we can calculate further into
the path-finding. Let's just write self.path. Finally, I mean,
outside the loop, once we finish the loop
and just in order to contain the start
note into this list, assuming that we can exit the list when we
reach the start note, we will add the start node to the path. Basically, that should be it. We are reconstructing.
Let's see. I think we have everything here. Instead of this comment
that we left here, we could say self.reconstruct
the path using the current cell as the
point of reconstruction. If things run well, we would actually
end up with a path, but we wouldn't see anything. This is just data at this point. If you think about it, let's
say we will have the path, but we won't be able to see it. Let's just do one more, which is draw path assuming
that that path has been found now. We can draw path. Let's just do copy paste, the same thing that we have, because it's basically
the template for what we're going
to be doing here. Let's do a color. It's maybe 255, 0. This is going to be like
a magenta-like color. What we want to loop through
here is for cell in path. We want to check all
the cells in the path, and then display with a
highlight version of that. Now that we have a
function to draw the path, let's draw it after
visited somewhere here because I do want to draw the end node and
start node on top of it. Let's see if we have
any errors and we come back and fix anything that
might be not working. Let's just run the algorithm. Let's create some obstacle. The algorithm goes very
quickly through that. We've reached the goal, and now if you think about it, what we're doing is starting
from here, we draw this. Cell this cell start being added up to the path until
we reach here. The path is complete, and
now we're actually drawing those cells into the canvas
with this magenta color. If you try it now with a
slightly more complex path. I'm going to try to create
something that would make the algorithm have to struggle in terms of searching
the solution. It's still pretty easy, but we'll see that the flat
field will get to the goal, and then the goal in
order to get back to the starting point
has to go through this particular
sequence to do so. So we do have a path-finding
algorithm at this point. But as you can realize, this algorithm is
not very optimal. We have a lot of visited cells, a lot of computation
that is wasted. It's taking quite a bit of time, especially if we're working
with a much larger canvas. We're going to be looking at different techniques of
how we can improve and optimize this algorithm
in the future lessons. I'll leave it here and I'll
see you in the next video.