Hello welcome to a coding
training coding challenge. What does the coding
training bring us today? Forget about that. So what I'm going to do is this,
it's something called A Star. Is a pathfinding algorithm. I'm actually recording
this part of the video that you're watching
after I did the challenge, was a bit of a mess. I have to admit, you what you're
about to watch is quite a mess. It took me 2 and 1/2
hours to sort this out. I had a lot of bugs. But what are you going to
watch is a little bit shorter, some of it's edited out. If you want to watch the full
archive of the live stream, you can find a link to that
in this video's description. This is the final
result. What I'm using is an algorithm
to find the optimal path from the top left
corner of the screen, to the bottom right
corner of the screen going around some obstacles. And you can see here
this is that path. And there's a lot
of pieces to this. The video is going
to be in two parts. So the first part of the
video, the only thing that I'm going to do is look at how
to make the optimal path from the top left to the
bottom right with no obstacles, and not being allowed
to go diagonally. And then that video will finish. And the second part of
the video will show you how to add diagonals,
and how to add obstacles. And so enjoy,
watch, if you don't see the second half
published as part of my feed go check this video's
description to be a link to it. So enjoy all aboard the code
train, and coding train, or whatever it is, enjoy
this A star challenge. So let's dive in and make
the A star algorithm, or an implementation
of it in JavaScript. So first of all, what
is the A star algorithm? The A star algorithm
is a search algorithm, meaning there's some
space of possibilities and you want to search
through that space for a particular needle in
a Haystack, so to speak. Solution and afterwards solution
out of all possible solutions. And typically speaking, there
are a lot of search algorithms to be able to come back to
others A star is typically applied to a pathfinding
kind of search problem. So let's talk about what
I mean by pathfinding. So here's one scenario,
incidentally a scenario that A star can actually
be applied to is trains, like how to make an
optimal path of freight trains between a
whole bunch of cities to get stuff from
one city to another. So let's sort of imagine
driving of cars in cities. So if you have a
bunch of cities, and they're connected by
roads in some arbitrary way, not everything is
connected to everything. And you're starting
at city A, and you want to get to city B, what
is the optimal path to get there that's the shortest? So we could eyeball this
and well actually there's only really one path, but I'll
connect things a bit more, add some more cities. So you could see there's
more possibilities here like this would be, if I were
to start here and go like this, I'm going to get all
the way to city B, but I can see that
this would be shorter. So you could imagine an
algorithm for just trying out every possibility. You could use recursion
because recursion is this kind of like
self-referential function, because you're at one city
and you try all the roads out of that city and you
get to other cities, and for those cities you try all
the roads out of those cities, and for those cities you try all
the roads out of those cities, and eventually some of those
paths will make it to the end. And then you could keep track
of how long it took you, and which one was the fastest. You can kind of do a search
every single possibility. What I just described
to you is essentially what's known as
Dijkstra's algorithm. Dijkstra's is an algorithm that
looks at every possible path, and tries to find
the optimal one. It works and it will
find you the optimal one, but it's not super efficient. So A star because it
takes a long time. Like this didn't take
that long, but if they're like thousands of nodes it
takes a really long time. The A star algorithm is very
similar to Dijkstra's algorithm but it uses a concept
known as heuristics. I have no idea if I'm going
to be able to spell this, heuristics. Heuristics is like
a really fancy word, how you would use it
you sound like you know what you're doing. But it's really just
a word for describing- I would say one way to think
about as an educated guess. So instead of having to check
every single possible route, what if we could just
sort of make a guess. This route is probably
going to be the best, I kind of know if
I go backwards, it's going to take me longer
than if I go forwards. So I can skip checking
the possibility that goes backwards. So this kind of heuristic. This kind of educated
guessing allows you to skip checking a
lot of the possibilities, and makes the
algorithm much faster. And the algorithm is typically
written with a formula. This formula is
actually quite simple although any time you
write a formula it starts to be like, Oh my God, is this
really what we're doing today. But f of n equals
g of n plus h to n. So I figure what all
these things stand for the h stands for
heuristic, the g, I don't know what it
stands for maybe we'll look on the Wikipedia page
and see, but so f of n it's like a cost function. Cost being like for
each one of these nodes, how much does that node cost? In terms of our time
in getting from point A to point B, the path
we're trying to find. So if it takes, the g
is the known amount. Like this distance
for this node is g. If I then went to this node
next, the g for this node is this distance
plus that distance. That's the g. So the g is the
like actual I would say cost, the
time, the distance, from beginning to end. Now the h is how
long does it take to-- g being like
how long did it take me to get
from the beginning, h is like how long is it going
to take me to get to the end. So if I knew what g and h
were not as a heuristic but as an actual value for
every single node, I could see very quickly
what's the fastest path is. The idea is, I'm traversing
this tree, this node, this path, and I get to here, I
don't actually know. I know how long it
took me to get here, I don't know how long it's going
to take me to get to the end. But I could make an
educated guess, because I know where the end is. I know the end is over here,
I don't know how to get there, but I know where it is. And what's my educated guess? How about just the
actual distance between these two points. If there were no
roads I could just go up in my helicopter,
coding helicopter. That was really the
same ring to it. That the coding training
has a ring to it exactly, but anyway if I could
go up in my helicopter just fly straight there, it
would take this amount of time. And an important thing about
your heuristic, your educated guess, in A star
algorithm is you don't want it to
ever overestimate the amount of time. If it underestimates
it, you're OK and how the algorithm is going to work. If you overestimate it,
you could have a problem in not getting the
optimal answer at the end. And in this case, we
can see that there's no way to overestimate if I'm
using the actual distance. Because no matter what, even
if there's a road from here to there, that's
the actual distance. If there's a lot of other roads,
there's a lot of other roads. So that's the basic idea. For every single one of these
nodes, I want to figure out, I know how long it
took me to get there, and then I want to
guess how long it's going to take me to the end. So and the way this is going
to work is if I'm here, I'm going to look at all
of the possibilities, so I could go here, I could
go here, or I could go here. And what I'm going
to do is I'm going to look at what the value of how
long it took me to get there, and the guess of
how long it takes to the end of each one of these. And I can pretty much see
that this one is going to win. So I'm going to pick the
total cost of how long it took me to get there plus my guess
of how much more I have to go, that's the way I'm going to go. And you'll see it's
still going to leave the others as an option, it
might have to back up and check some of those other ones later,
but that will actually work. So let's look at actually
trying to implement this with some code right now. So I have a Wikipedia page open
to the A Star Search algorithm. And if I scroll down
something that's going to be helpful to
us is this pseudocode. So there's a lot of tutorials
you can probably find, examples of the
A star algorithm. I'm going to make my own. I'm going to kind of use this
as something to refer back to as we start to
program as a reminder, but I'll try to explain
things as I go as well. The thing that I need to talk
about, which I came over here unnecessarily is that
the system that I'm to build, I am not going
to build this node space type of map, it's going to
be a little bit different. Let's say this is my Canvas. And let's say what
I'm going to do is think about there
are cities in a grid. The Canvas is a big grid
of cities like this. And every single
city is connected to every city around it. Like this, I won't keep
drawing all those lines. So if I'm trying
to get to here, I might figure out
the optimal path you could imagine as something
like this or whatever. And then at some point
what am going to do is I'm going to add
obstacles, and see how the A star
algorithm can solve going around those obstacles. So this is a generic
way of finding a path through any given pixel space,
because pixel spaces are just grids. And we could do
things like then add a sort of steering agent
to follow the path, or that sort of thing. Or we could kind of create
a non-traditional grid of network map like this. But I think it's going to
be a classic implementation and demonstration is
using a system like this. And this is a full grid I just
didn't draw out all the pieces. So that's what I'm going to do. And we'll see how that goes. So coming back, the first
thing that I want to do is I want to have
a two dimensional array that can store information
for every spot in the grid. So let me go to my code,
and what I'm going to do is I'm going to create
a variable called grid. And I'm going to
use some Java syntax and you know what
I'm going to do too, is I'm going to say I want to
have some variables that say, let's start small,
there's going to be five columns and five rows. So the grid is 5 by 5. Two dimensional arrays are
sort of goofy in JavaScript. What I ultimately want to do is,
I want to say things like grid 0, grid index 0, index 3,
is like the first column and the fourth row. Counting starting from 0, zero
is number one, zero, one, two, three is the fourth one. So I want to be able to
refer to any spot in the grid by its column and row position. But the first thing I
would do is just make the an array itself with a
certain number of columns. So the array, is an array of
certain number of columns. Each column has an array
for all those spots that are in the rows. So what I will do here is I
would say for var i equals 0. i Is less than
columns i plus plus, and I would say grid index
i is a new array, rows. So this is really
making a 2D array, and if I then say
console dot log grid, we can see what I've got here. Where am I? This is where the
code is running, you can see what is a
two dimensional array and it's 5 by 5. But it's an array of five
arrays of five things in it. So that's the grid. Now what do I want to put in
the grid, this is a question. So now what I want to do
is every spot-- now here's the thing, remember this
algorithm that I'm working on, the idea is that
every single spot has a cost associated with it. How long did it
take to get there. And what's its
guess for how long it's going to take to the end. So I want to store
that information in each one of these spots. I want an object that
can know what's my. I'm a node, I'm a cell, I'm
in this grid, what's my cost? So coming back
over here I'm going to do another loop
that's going to go through every column
and every row. And I'm going to kind of do
this in an object oriented way, I should say that
a bunch of things I'm going to do
in this video, I'm doing for ease, readability,
and not necessarily for optimal efficiency. I'm definitely going to make
the most efficient version of this algorithm, and I'll talk
about some things maybe later at the end that will see
that being more efficient. But I want to make each
spot in the grid an object. I'm going to call it a spot. Let's call it a spot. I don't know what a good
name for this would be. So what I need is
like a constructor function to create an object. So every object will have a
f value, a g value, and an h value. So those are the things that
I'm going to count spot. Every spot I need to calculate
the g, the h, and the f value. You need to know for each
cell in the grid, what are those values? There are some other things
I'm going to want to know. We're going to have to add
a bunch of things actually, let's add things
as we need them. So that I've done that. So now I have a grid of spots,
and now what I need to do now-- here's the thing, the A
star algorithm by definition is a loop. It's trying a lot
of possibilities until it gets to the
solution and then it's done. So what I want to do is have my
example demonstrate and animate the process. So I'm going to do
something a little bit different than probably
what's found in that Wikipedia pseudocode. I forgot to mention I'm using a
JavaScript framework called P5. And as P5 ask you to write
a set up function, which is kind of the beginning
and I make a Canvas, and draw is a function that
loops, it's an animation loop. What you do like normally with
like set request animation frame or something like
that with native JavaScript. So what I'm going to do is
I'm going to use the draw loop as the loop. So if I go back to
this particular page, we can see here
where is that loop. There's this loop here
while open set is not empty. So this is it doing this
thing to solve the problem. So here's the thing,
what's going on. Open set, close set. So this is a concept that's
part of the algorithm that's quite important. We have this idea of
an open set, which is an array, or
a map, or a list, or whatever the data structure
is that you're using, I'm going to just use an array. And we have this
idea of closed set. So the idea is that closed set
stores a list of all the nodes that have finished
being evaluated. So this is everything
that's done that you don't need to ever revisit. That's going to be closed set. Open set are nodes that
still need to be evaluated. We need to consider and evaluate
them they're not closed yet. The algorithm is finished
when open set is empty. There's nothing left
to be evaluated. Actually that's
not entirely right, so the algorithm is
finished, there's two ways the
algorithm can finish. One is I'm going to be
searching through nodes. And if I ever arrive
at the end I'm finished because I
arrived at the end, I found the optimal
path all the way there. That's the way this
algorithm is working. However, if I have nothing
left in open set to review, nothing left to look at,
and I haven't arrived at the end I also have to stop. That means that means
there's no solution. So it's possible we could
build a maze of obstacles with no way to get
to the actual end. And so if there's nothing
left to evaluate you haven't got the end it's also. So these closed set starts
as empty, open set starts with just one node. At the beginning the open set
has just the starting node. So let's go into my
code again, and let's create and make some of
these global variables just so we can kind of
look at them in the console if we need to or evaluate
them, closed set. So I'm going to create
two arrays, open set and closed set. And what I'm going to
do right here in Setup, is I'm going to say I'm going
to make a start and an end. And so a start is going
to be the top left. THE start node is grid at 0, 0. And the end node is grid at
columns minus 1 rows minus 1. So these could be picked
randomly or through a variety of other ideas. But the idea is that
I want to start here, and I want to get to there. That's I want to find the
path from the top left to the bottom right
of the window. So then what do I need to do? I need to say open
set, push, start. So we're starting with open set. I'm going to look,
that's the thing I'm going to iterate through and
check every possibility there. And so let's look
at the algorithm. We're going to talk about came
from in a second, g score we're going to talk
about that, f score these are a bunch of things. But here's really
where I need to start. I need to say while
open set is not empty, as long as there are
spots to be evaluated, let me start
evaluating those spots. So the thing is I don't
need a while loop remember, I'm going to use the draw loop. So the draw is already
looping I'm just going to say, if open set is not empty-- the way I'll say that
is if open set dot length is greater than zero,
great, we can keep going, otherwise no solution. I say no solution. There's nothing left and haven't
gone there's no solution. Now what I also want to do just
because I want to debug this as we're going, is I
want to write something where I draw all the
spots in the grid, and maybe I debug in some ways. This will be good for debugging. So I'm going to write
another double loop. This is a long
problem by the way, this is going to be a
kind of a long video, you're still watching? This could be like
multiple parts but maybe I should do
multiple part videos. I don't know. Grid i, j, and I'm
going to do show. So I'm going to
write a function. Each spot is going to be
a function to show itself. And what I'm going to
do is, I'm going to say, this dot show equals function. So how can the spot show itself
it doesn't know where it is. So I'm going to give each
spot an x, in each spot a y. So when I create each spot I'm
going to pass in the i and j. So each spot knows where it is. This is going to become
important later actually. And then in the
show function, I can draw a rectangle
at this dot x, this dot y but here's the thing. I have a sort of
scaling issue, which is that if my
window is 400 by 400 but I only have 10 by
10 columns and rows and you figure out
how wide each cell is. So I can do that with
some global variables. I'll just make a
variable w and h. And what I'll do is say that
w equals the width divided by columns, and the number
of columns or if it's 400 and I have 10 columns, each
spot is 40 pixels wide. H is height divided by rows. This is pretty good. And so then I want
to just multiply by that w, multiplied
by that h, and then have it with in height. I probably need one
variable to be honest because I'm making everything
a square but whatever. Let's say fill 255, stroke
zero, and let's run this again, we can see there's my grid. Maybe what I should do is
I'm getting ridiculous here as I should make everything
like one pixel left, so I can see the full
grid but whatever. So you get the idea. There's the grid. Good call. Good job. So what I want to do is I also
want to do some debugging, so what I'm going
to do actually let's make this show
function get a color, and forget about the stroke. I could keep the
stroke but no stroke. So what I'm going
to do is whenever I call the show function,
I'm going to use a color. So in my debugging I could say
I want everything to be white. But I also want to look
at the closed list. And I also want to look at
the closed lists and open set, closed set, open set,
whatever, I can't remember what these are called. I'm going to say closed
set index i dot show and I'll make these green, are
closed will be red I guess. Somebody will come up with
more beautiful and interesting colors and nicer design
choices, and open set will be green for open. And so now if we do this,
no stoke is not defined. No hey no stoke man. That does not make
any sense, no stoke. There we go. So we can see things
are looking up here. Now I can see that's my open
set, nothing is closed yet. So I want to have this because
I want to be able to debug it as it's going. I need to draw stuff to see
how the algorithm is working plus this is going to open
a lot of interesting visual possibilities for you guys. So let's keep going. Now what do we do? We've got to start thinking
about this algorithm. So let's go back to the
Wikipedia pseudocode. The idea here is
current should be the node in the open set
that has the lowest f. So in other words,
I want to evaluate, here I am, I want to evaluate
all the open set possibilities and what has the lowest f. What's going to be the best
thing getting me to the end. So how do we find
what something f is, and which has the lowest f. So first thing I
can do is I can say for var equals 0 i is less
than open set dot length i plus plus. So I'm going to say of
our lowest index equals 0. So I'm going to assume
in the open set-- there has to be something
in the open set, I'm going to assume that the
lowest one is the first one. The winner, the record keeper,
I could say winner, index, or whatever, I don't know
what to call it, lowest index. It probably has a variable
name in the pseudocode. So what I'm going
to do now is I need to say if open set dot index
i dot f is less than open set lowest index dot f. Lowest in this is such a long-- let's just call it winner. Winner dot f if it's less
than then the winner is i. so we're looking to see if we
have which one is the lowest. That's good that's an
easy algorithm, loop through everything, find
the one that's the winner. What do we do next? So first thing we have to
say, if the winner is the end we're done. So let's add that in right here. If open set winner
equals end, remember end is a variable that's
holding on to that last spot, then console dot log DONE. So that's where we're done. So we start with the open
set, we look at all the what all the things in
the open set, what's best, if the one that's best
is actually the end, then we're great,
then we're done. Now the next thing
is, whichever one we found current is the node in
the open set having the lowest score. So you know what I should do? I should say var current
equals and this is really winning index, I'm going
to say open set winner. So if current-- and, boy,
I have lots of typos here. Remember if you want
to test it something is equals in JavaScript
you use double equals. If you really want to test,
if you really want to be sure use the triple equals. So if current is
the end we're done. Otherwise what do I want to do? I want to add close
set, push current, and then I want to say
open set remove current. This is not any
actual real code. So here is one of
the tricky things. What I want to do is, there
is a function in JavaScript to add a particular object
to an array, that's push. There is no function
in JavaScript is just arbitrarily say, hey,
this thing if it's in the array remove it. So and this is where I'm going
to not do things so optimally, but what I'm going to do is
I need to find that object and remove it. And I'm just going to write a
function, remove from array, open set current. So I'm going to write
my own function, I'm going to stick it
just at the top here. Function remove from array
and function array element, and then what I need to do is I
need to loop through the array, but I want to loop through it
backwards to say i in a second. i is the length of the array,
length of the array minus 1 will be starting at the end
going all the way down to zero, and if the array index i equals
elt, then array splice i, 1. So what is that? I just really quickly
wrote a function that loops through the array,
since if it has that element, splice being a function to
delete a particular element add an index from the
array, and only want to delete that one array. I'm sure somebody can tell
me a better way to do it. But then it will
work for right now. Maybe I'll come back
and optimize that later. But why do I go
through it backwards? The reason why I go
through it backwards is if I'm going through
the array forwards, and I delete something, then
all the elements come back and I'm moving forwards
I could skip an array, so skipping elements. So I want to go
through it backwards. So we want to remove it. Remove from array,
current from open set, current add to closed set. So now what do we do? If I go back to the
algorithm, I need to figure out what should
I add to the open set. What new nodes do
I need to evaluate. And if we think about
this, if I have just gone if I started here,
if this is the grid. We try to fill out a
little more of this. Just so it doesn't
look so empty. If this is the grid, what I want
to do I've just evaluated this. It's my best node coz
I only had one choice. That just went into closed set. It came out of open set. Now I need to
figure out what are some nodes I need
to check next, it's anything that's neighboring
that particular node. This one, this one, or this
one, as long as they are nodes we've already checked
or finished with before. So how do I get the neighbors? So I need some way-- I'm in wrong keyboard,
I need some way of figuring out what are all
of the neighbors of current. Guess what, I think a
nice way of doing this. One way of doing this would be
to add a function in the let's add an array. So let's have each spot
keep track of its neighbors. And let's add a function
called add neighbors. What I'm going to do
is do things like, so add neighbors from
a particular grid, just pass it in. And so what I'm
going to do is I'm going to say this dot neighbors
push, grid, this dot i plus 1. I'm going to do
something silly just to make it a little
more readable. Say var i equals this dot
i, var j equals this dot j, I might need those out. I'm losing my train
of thought here. But this is fine. i plus 1, j. So there's four neighbors. i plus 1, j, i minus 1 j,
i, j plus 1, i j minus 1. So these are the four neighbors. I want to add those. I want each as they emerge,
but there's an issue, what if i is on the edge. So you know there's so
many nice and probably concise and strange and
optimal ways of writing this, but I'm going to do something
really simple which just says, as long as i is less
than columns minus 1, then I can add that neighbor. As long as i is
greater than 0, then it's OK to add this neighbor. And then as long as j is less
than rows minus 1, very tedious the other way of doing this
I can add that neighbor as long as j is greater than 0. And you know what, I
called these x and y. So this is one of these
things about programming. You got to keep
track of your stuff, and I'm not doing
a very good job of naming things in such a way
that making it easy on myself. I was calling it i and j,
and then I call it x and y. So maybe I'll change
these to i and j, because it's not really the
x and y, the x and the y is really the location
this start i times. So I think this is
going to be better. And then if j is greater than
0 at this particular neighbor. So here now I can add
all the neighbors. So this is a function
for any given spot to add neighbors that
are in a particular grid. Where do I do that? Well you might think-- I kind of want to do it here. But I have a feeling this is
going to cause a big problem. The reason why I
can't do it here, is because this is where
I'm making all the spots, and I can't add the
neighbors while making the spots because I want to make
the spot that's next to it yet. So this is very inefficient
I'm sure I could come up with a different
way of doing this. But I'm just going to add
a completely other loop. Just to do this again. And say add neighbors. So I want to make all the
spots, loop through everything and have everything
at its own neighbors. So now just let's
refresh this and see I don't have any errors. Oh I know what the error is. I wrote it in such a
way that it to pass and because maybe you
want to add neighbors from a different grid and
some other life that you have. I could just use it
as a global variable. Great now I'm going
to look at grid, and we can see that each
spot has an f, g, and h, j, and a list of neighbors,
and the neighbors-- something's wrong here. Oh look at this, look at this
comma in a totally nonsensical location. That's not right at all. A lot of you are screaming
at the computer I'm sure. Hopefully you were just
saying in a nice way like, excuse me I might like to
point out your small but subtle error there. Why debugging is good. Let's look at this again. Let's look at this, and
let's look at this spot, and let's look at its neighbors. It's got three neighbors. And where is it? It's like the
location 0 comma 1. So let's go back to
the Wikipedia page. For each neighbor of current. So we want to see what to do
about all the neighbors we're going to add to the open set. But before we put
them in the open set we need to evaluate them. So first let's say for
each neighbor of current. So what I'm going to do
is, I'm going to go here, and where are we in the
algorithm, sorry right here. So I want to get all the
neighbors current dot neighbors. I'm just going to put
this in a variable so I don't have to say current
dot neighbors all the time. Var neighbors equals
current dot neighbors. I'm going to use a for loop
to check every neighbor. For var i equals 0, i
is less than neighbors dot length, i plus plus. So this is every
neighbor and then I'm just going to say neighbor
equals neighbors index i. So this is me checking
every neighbor. Now what do I need to do
for every single neighbor. Well the first
thing I need to do is that neighbor, if I'm
moving to that neighbor, the g should increase by 1. I started here, it makes
sense that g would be 0 here. The amount of time
it takes me to get to this spot at the beginning
from the beginning is 0. So if these are the
neighbors, actually these are the only two neighbors. I'm not doing diagonals. So I don't know why
circle that I just realized I'll add diagonals
later I can see what that does. But so I can either go
here, or I could go here. And the g for each one
of these should be 1. So another way of
saying it should be 1, it's whatever it was
previously connected to plus 1. Because if it takes me like
10 steps to get to here, and then I'm going here,
then this would be 11 steps. So the first thing
I want to do is I want to say neighbor dot g
equals current dot g plus 1. Except I don't entirely
want to do this. So let's go back and
look at the algorithm. There's a couple of
things I need to check. First of all, what if that
neighbor is in the closed set? If the neighbor is
in the closed set, then I don't want
to evaluate it. Because by that definition it's
something that's done already. I don't need to revisit
it, I've already visited there through
some other optimal path. So let's add that in. So what I need to
do is first say, now how do I say if an
object is part of an object. So this is, again,
where I would want to do some type of efficient search. This is a search algorithm,
but a search within a search to figure out if
something is in a list. So I want to make that more
efficient somehow here. Because I want to say, so as
long as closed set does not include the neighbor, then
I can change its g value. Although can I really? So let's look at
the algorithm here. Sorry back here. So you'll notice
in the algorithm it says the tentative gscore. The reason why I actually don't
want to just automatically give it a new gscore, is
I might have gotten to that if it's not
in the closed set, it still could be something
that's been evaluated already, and I might have gotten to it in
a bit more of an efficient way. So I need to check some things. Because if it's in the open set
already but it's a neighbor, I might have gotten to
it with a lower gscore and I want to keep
that lower gscore. So what we're
going to do is say, I'm going to actually say var,
I'm going to call it tempG. So I want to keep track
of what the G would be, and you'll notice in
the algorithm that says current plus distance
between current and neighbor, so in a more generic version
of this algorithm where the nodes might have different
distances between each other. I would have to evaluate that. But the way that I've
done this over here. But you can see
this pretty well. Is that everything
has a distance of one. So I'm going to add one, now. Now what I need to do
is I need to figure out, is this something
that's actually already in the open list. So does the open set
include that neighbor. So I want to check
is it something I've evaluated before,
because if it's something I've evaluated
before I want to figure out is this a better g. Wherever kind of like way
that I'm checking right now, have I gotten there
more efficiently. So if tempG less
than neighbor dot g. If that's the case, then
I've got a better g. So now I can be that new g. I want to be the new g
that's lower than my old g. Old g. So if we go back
I get that right, so right if the tentative
score is greater than gscore don't do anything. Just kind of doing it in the
algorithms, the pseudocode describe it a little
different way. But so then, if
it's not in there, if it's not in the
open list then great. Neighbor dot g should
have that score, and open set, push
that neighbor. So all of these things they're
either already in the open set, and if they're already
in the open set of things to be evaluated
still, I should see if I've gotten there faster
than maybe I did previously. And if they're not
in the open set then, I've gotten there and
add it to the open set. So once I've done all
of this, and we've got to check to make sure
I'm still within the right if statement. I'm still within
this if statement of if it's a neighbor that's
not in the closed set, as long as it's something--
and now we can see is here's what I need to do. What I need to do is figure
out, what it's gscore and what's it's fscore,
that's interesting. So what I'm going
to do here is-- so I need to figure
out what is fscore. It's time for the heuristic. Are you guys excited? You've watched I don't a
really long video so far, and I'm only now arriving
at the point where you need to calculate the heuristic. So I'm going to
say neighbor dot h, the heuristic is the
heuristic, I just want to use that
word that sounds so fancy, between the
neighbor and the end. So here's where I now need
to make an educated guess. How long can I guess
that it's going to take me to get to the end. So there are a lot of
different kinds of heuristics. And they'll give you
different results. But the heuristic I'm
going to use just right now is just the raw
Euclidean distance. I'm going to change it
later, because you're going to see I will get
slightly different results. But I'm just going to say,
what's the raw of distance? So I know that that's
always going to be less than what it actually is. But it's a good educated guess. So coming back here I
need to write a function. And I'm zoomed in. I'm going to write a function
at the top, function heuristic and between points
A and B. So I want to say var d equals the
distance and distance is a p5 function between a dot
i a dot j, b dot i, b dot j. So that's just do what's
known as Euclidean distance it uses the Pythagorean
theorem, just like how long is the line
between those two points. And then return D. So
that's the heuristic. So if I come back now
into my algorithm. The h-- I have a run this
is why I don't recommend, usually I like to
run the code a lot in between every direction
on the errors but here we go. That neighbors h is the
distance between A and the end. And then that neighbor's
f, it's g plus it's h. So the whole point
of this, is to know how long did it
take for me to get there, what's my
guess for how long it's going to take
to get to the end, add those two things
together, and that's the sort of score of
this particular node. And once I've done
that what do I do? I need to add that
to the open set, I don't see that
anywhere in here. I did that already. Open set add neighbor. I did add that here. So it's either already in there
and I'm updating its values, or it's not in there
and I'm updating it. So there's a little
bit of something like this doesn't
need to happen again, if I'm not updating the g
because the heuristic is never going to change. But it's fine it'll work anyway. So now that that's good,
I think we're good. Came from, so I'll
get to that later. We're going to need
that came from thing. So let's just run
this see what happens. Well, it made it to
the end, hold on OK. So let's make a bigger grid. Did that really work. Yeah oh that's just
doesn't look right to me. OK well, I think there's
a bug in my code, which I'm going to have
to find definitely, but I can't be 100%
sure I sort of missed a key part of this, which
I really would like to add. So if I go back to
the algorithm here, you'll notice this
now this pseudo code is written with a
particular kind of style. I don't want to
get too far in to. But you can see that,
these are like these maps. Like this is a map of all
the g scores for every spot, this is all the f
scores for every spot. I've done it differently,
in a different way I have this two dimensional
array of all these spot objects each of those have properties. But one of the properties
that each spot needs, is to keep track of
where it came from. Like as I'm going through
this, what was the node that was previous to it. And you think of
that as like a parent node, or the previous
node because eventually once I get to the
end and it's done, I want to be able to
trace back and find what that optimal path was. So what I need to
do here is add-- where am I? What I need to do in the
code is I need to say, neighbor dot previous
equals current. So I want to just use previous,
I could say came from, or parent but may say previous. Where this neighbor
came from is current. And so you know what I
might do up here just to be clear about this, as I say
this previous equals undefined. That's unnecessary because by
definition will be undefined, or null, or whatever, but I
just want to have that in there. So what I'm going to do
then is when it finishes, this is where it finishes. Wherever the open
sets, whenever the best the item in the open set,
the spot in the open set, with the highest fscore, the
gscore and the hscore combined, the lowest that is the best one. If that happens to be
the end, then I'm done. So now what I need to do
is I need to find the path, and the way that I'm
going to do that, is I'm going to make this a
global variable just again so I can kind of evaluate this stuff. I'm going to say the path. And so what I want to do when
I find the path, where so much code it would be nice
to organize this better. Is I'm going to say
path is a new array, and I'm going to
say var, I don't think I can mess anything
up by messing with current, but I just say temp equals
current, because at the end. And as long as temp has a
previous, as long as there exists a previous
what I should do and then I should also say path
dot push temp, path dot push, temp dot previous, and then
temp equals temp previous. So this is an algorithm I
kind of do this in my head here a little bit. I think I need to
explain this right. What I'm doing is I'm
starting with an empty list, and I'm going to put
the end in the list. And then the end is connected
to the one before it, so that goes in the list. And that was connected
the one before it, so that one goes in the list. So as long as there
is a one before it, put the one before it and now
the thing that I'm checking is the one that was before it. So this is a nice
little algorithm to sort of backtrack
over that path. And then what I should be
able to do is when I'm done, I should be able to say if you
know where I want to draw this. I'm going to do this down here. I'm scrolling around
like a crazy person. I'm just going to initialize the
path as an empty array up here. So I want to say, as
long as I know I can say, I want to loop through
the path, and I want to say path index i dot
show with a color, 0, 0, 255. So again I'm not being
far from about the colors. The closed set are red,
the open set are green, and the path is blue. So let's see what happens here. Oh you know what, I should
evaluate that path always. Why not? To see what the current path is. It's only going to do it
when it gets to the end. It makes sense, that
makes sense as the path. I think. I got to check, I feel like
there's a bug in the code. So one thing as I'm just
realizing is I can be done, and I can say like no
loop to stop the looping. But there's no reason
why I shouldn't just evaluate what the current
path is like every frame. And I can actually just
do that right here. So let's do that. Well, what am I getting. So I think things
are actually working and maybe we're going to see
some improvements if I add a few more things to
the code, and also kind of add some obstacles. So let's just keep
going with this. So what I'm going
to do, a couple of things I want to
do, first of all this really isn't a good heuristic. Where's my heuristic
function, here it is. Using the Euclidean
distance, which is actually just kind of measuring
that distance, isn't really accurate
when I can only make steps that aren't
diagonal like this. So there's actually
a distance that's called a Manhattan distance
or taxicab distance, which is just measuring the difference
in x and the difference in y. So let me put that
heuristic in which I think will give us some results
that look a bit more like what we might expect. So I'm going to put
that into that's the absolute value of the
difference between the i values of the x values, plus
the absolute value of the difference between
the j or the y values. So I can run this
now, and we're going to see we can see it trying
to solve this problem. The funny thing
is, the reason why it's covering this
whole space is because in a way like the top
and the bottom are equivalent in distance so it
ends up checking everywhere, but we'll be able to
see here that if I were to just change the end
spot for example to where do I set the end. The end spot to
like the fourth row. Then actually what it's
doing is it's optimally finding that path very quickly. It doesn't have to
check every possibility because what are we doing, we're
using the A star algorithm. So there's a couple of things
that I want to add to this. Number one, let's
add some obstacles. So obstacles are
really going to help us understand how this is working. And number two, let's think
about adding diagonals as well, and how that works
if we add diagonals.
