Hi. Welcome to this new video. We are continuing to work
on the path finding series, and we've reached a point where
we can actually introduce a very interesting
algorithm that would solve some of the inefficiencies
that we've been working with, and that's the A-star algorithm. Let's understand what we
are already achieving, and what are the challenges for this particular
algorithm to work with. We have a path finding problem that if we use a
brute force approach, meaning that we're
actually looking at every possible
cell to eventually find the solution or the
path to get to a target, we end up losing a
lot of resources. We actually end up looking into the wrong places
for a long time. The A-star algorithm, alongside with other series of
path finding algorithms, has been path finding
solutions that try to build upon the optimization and efficiency for this algorithm
to run and perform better. The way this is
achieved, is that, we have some information
of distance or some heuristic that
would allow us to understand are
we getting closer? Is this potential path tentatively better
than another path, and we would actually
prioritize this path first. We will see that
there's an equation within the algorithm
that would determine not all cells are equal or consider equally
so that we don't grow the algorithm
in all directions. But some of them
seem to be pointing out that those are more
interesting to be explored first. If we think that the
algorithm starts from a start point and we
have the series of cells, the first thing that
the algorithm would do is actually create two sets; the open set and the close set. We could think about those similarly as we have been doing the flat field in terms of the frontier and
the visited cells. But we have to actually calculate that within
the evaluated cells, in this case, the open set, that would be the point
of looking for new cells. We would have a series
of calculations. The first one of them, there's going to be something
we're going to call h, which stands for a
heuristic function. For our returns of purposes on this grid it would be a
distance calculation, but heuristic function means
that we could actually use a different heuristic or a different criteria
to evaluate, say, something that is being more performative
than something else. If we imagine this
particular condition, the distance of each one of these cells to the
gold or to the end node, some of them would have
a closer distance. We might say, well, that's
actually potentially. We don't know if that's going to lead to the optimal path. That's potentially a better
way to explore first. We're going to prioritize
the cell, in this case, with the h of 89, that would be a cell that we're going to
be exploring first. There's a second layer of scores that would be taken into
account by this algorithm. The second series of course
is the g or the g-score, which actually stands for
the cost of the path. To understand this, is that, for instance, if you move
one point in the grid, you have a cost of one, if you move two points in the grid, you have
a cost of two. You actually might also be
taking into consideration how long has it taken you to be
in that particular position? That, together
with the distance, which is what we're
going to call f, which f is going to stand by
the summation of g and h, gives us a final score. We're going to be talking
about this final score f, which is a merger of how much has cost us to be
where we're at in the search, and how much is the
distance of what is left to arrive to the target. Those two conditions, if we're actually
reaching a dead end, if you imagine you're
reaching a dead end, it might be that your cost
starts being very high. You might switch to
a different part of the algorithm where
the cost was lower, but perhaps the
distance was higher, and perhaps that becomes the most tentatively
more interesting path to keep on evaluating. This algorithm
would actually not grow in a uniform way
in all directions. It would actually
grow specifically, on the areas that has a hint that could be performing better. This would give us incredible efficiencies in a
way in which we could arrive to a target in the least amount
of calculations. Let's look at a simple example. We're going to be looking
just at the f-score, which is the summation of
the cost and the distance, the h. If we start
on the start note, just by looking at
the cells here, we've marked with numbers, just the final f-score. There might be
cases in which you might have two f-scores
that are the same. In that extent, the
algorithm would actually pick the one that
is first in the list, but we could see
how the algorithm would be calculating constantly. We will not visit all
the cells in the grid. We would actually just move
rather quickly to the cells that are closer and
closer to the end node. This is the logic
of what we have. Let me show you a little bit of what we're
going to be building before we actually jump
into the code itself. We're going to be building
this in a couple of sessions, but if we have this
condition here, we have all the cells
marking the f, the h, and the g. As we still have
a dynamic environment, let's imagine that we're
creating this condition here, and maybe also
something like this. You can see that the amount
of cells that are being evaluated is drastically smaller than what we have been
using with the flat feel, and you can actually
start reading the numbers and
understanding that the f condition
constantly goes down. What is quite intuitive and interesting about doing this
interactive simulation, is that, by just drawing
a different environment, you would be able to
put to the test of how the algorithm performs when it has to find the
dead end condition, maybe we has to switch and go
back to a different route, and ultimately find a path to this labyrinth
that we're building. We're going to be
building this together in the next couple of sessions. I'll see you in the next video.