In the previous lecture, we started working on our Graph API.
Now we're at the point where we're ready to put in the functionality for an A star algorithm pathfinding
search.
So it probably makes sense to just revise the aStar algorithm that we looked at in the previous section.
So we have a maze or we have a series of waypoints that are connected with edges which aren't any different
to a maze.
So in the maze, each square was basically a node, and if you could get from one square to another,
then that was an edge or a path between them.
So we've got to start position.
We've got a goal position.
We have to calculate how to get through this.
Now, there's three values that we're going to assess each position on, and that is the PH value,
which is the cost of getting to the goal from that node, the G value, which is the cost to get to
that node.
So how much it's already cost to get to that node from the start.
And then we have an H value, which is the addition of both those things that gives the overall node
its like holistic kind of cost I guess on how fit it is, how its the best one to go for.
So we're going to write some of these algorithms into our graph class.
Okay.
So we first of all are going to create our heuristic, which is basically our method that will determine
how fit each node is.
And in this case, we're going to use the distance from the node to the ending location, which is going
to be sort of as the crow flies.
So that's why it's called a holistic I guess it's kind of like the best guess you can make because we
don't know.
We can't actually fly straight across to the ending position.
We might be able to, but from each node, that's just going to be our best way of measuring it.
So let's just create something that returns a float.
Let's call it distance and into it.
We'll pass node A and node B.
Now, of course, this is such a simple calculation that you probably don't need to write a method for
it, but way ah anyway, just so that you can see it.
So what we're going to return in here is the squared magnitude.
So we want vector three squared magnitude.
Now the square magnitude is quicker to calculate than the actual magnitude between two points, which
is a vector.
And it doesn't matter if we use a square magnitude as long as we're assessing every single node based
on the same kind of assessment algorithm, which is this one here.
So our square magnitude will be a dot ID or get I'd dot transform dot position minus and that's got
to be in a bracket around there minus our other node, which is the B node.
So B dot get ID dot, transform dot position like that.
Okay.
So that's going to be our heuristic.
Now, I'm missing a bracket just there.
Okay.
Right now, once we have that associated with every single node, we need to find the one that has the
shortest distance, that means we'll need another algorithm to find it.
Now, in the previous version of a star that we created, in the last section, we used a link query
to do that.
We're not going to do that now.
We're actually going to do it manually.
So this is the same algorithm, but just slightly, I guess, more hands on, more manual way of typing
it all out.
So we'll call this the lowest F and this is basically going to do our LINQ query anyway.
So list node will pass through all of our nodes and then in here we're going to calculate and return
the position of the lowest node.
So we want float lowest f equals zero, int count equals zero int iterator count equals zero.
Now we'll initialize our lowest f value to be lowest f is going to equal the first value in our list.
So L zero dot f and iterate account is zero for that.
So we have to make sure this iterate account lines up with what's in this L here, which we will do
in the following loop.
So now we'll loop through all of them and check them out to find the lowest.
So for int i equals one I is less than l dot count i plus plus.
And then in here.
Here.
We'll go if.
L at position I dot f is less than or equal to the lowest f then the lowest f equals l i dot f and the
iterator count equals our count.
Okay.
So then we.
Then down here go count plus, plus.
And after that we return our iterator count, which will be our node with the lowest F value k.
Now along with those two things, we need to now implement our a star.
So we'll come up above our distance and put those things in here.
K So this is quite a long algorithm which you would have noticed when we went through it earlier, but
this will be the same but slightly different because we're not using that link code in here.
So public bool a star game object start id game object and i d and then node start equals our find node
start ID.
So we're allowing game objects to be passed through and we're using our find node that we created before
to get the correct nodes from the list, find node and id k and then if start equals null or end equals
null, just a little bit of error checking.
If we can't find those nodes, we will return false and say, well, there's no path here.
Okay, so now let's get into the actual a star.
So we need a list of nodes which will be our open list.
So node open equals new list node.
And then we need the same thing again for our closed.
So I'm just going to copy and paste that in.
This is our closed list.
Okay.
Then I can create a float for tentative g score and equal that to zero.
Now what was G?
Well, G is our distance that we've gone so far.
Okay, so the tentative G score is what we would give the node if we're about to put it into a list
and actually select it as our next position in the graph.
So we need to calculate it first.
Basically, then we're going to have a bool.
Tentative is better.
So if we calculate the tentative G score to be actually better than the one that's already on the node,
then we can use the better one.
So let's go with start dot g equals zero.
Now this is before we've actually started looping through anything, so we're just setting these two
values up.
Start at h equals distance of start and k.
So H is our distance to the end.
G is how far we've come all the costs so far, which is going to be zero because we haven't gone anywhere
yet.
And then start dot f equals start dot h because there's nothing to actually add together at this point.
Now open ad is going to equal our start node like that.
Okay, so now for our big wall loop, while open dot count is greater than zero, let's make that a
t int i equals lowest f in the open list because we want to select that our next one we're going to
go to so node this node equals open list at position I then if this dot this node dot ID equals the
end ID, then that means we've found a path.
So in here we will reconstruct the path which I'll type out in a moment.
So reconstruct path that's going to be the name of our method from start to end.
Let's make that a capital and we will return.
True.
So we'll come back and do the reconstructions later on brackets going in there because that's a method.
So let's go down.
And here we haven't found the end.
Let's continue comparing things so open.
Dot remove at.
Let's remove the node we're working with.
I.
Closed ad.
This node because we've now said that we're exploring it.
So node neighbor.
So from that particular node, we're now going to explore all of the neighbors.
So node neighbor.
So for each edge E in this node dot edge list.
So these are all the paths coming out of that particular node that we've just closed.
We're going to explore all of these neighbors.
So the neighbor is going to equal E end node.
Now if.
Closed dot index of neighbor.
So if the neighbor is kind of out of bounds because we've already been there, we will just continue
looking at the other edges because there's no point looking at something that's already being closed.
Okay.
So now also tentative g score equals this node dot g plus distance from this node to the neighbor.
Then if open index of neighbor equals minus one, then it's not in the open list.
We want to add it to the open list.
So open add neighbor so that we can actually explore it again next time and then we'll set tentative
is better to equal true else if ten a2g score is less than neighbor dot g, then we'll also say that
tentative is better.
Equals true.
Otherwise tentative is better.
Equals false.
Okay.
So once we've gone through that process, if tentative is better, if the a g value that we've just
calculated is better than we just want to give that node that new g value.
So if tentative is better than in here, we'll go.
Neighbor Dot came from equals this node neighbor dot g equals tentative g score neighbor dot h equals
distance from this node to the end node and then neighbor dot f equals neighbor dot g plus neighbor
dot h.
Okay, so that's done.
Now if we've got through to here and we haven't actually returned a true further up anywhere, then
we actually want to, which would be up in here where we construct the path is to quit out of here with
a return false, saying that there's still no path.
There's no path between those two nodes anywhere that can be found.
All right.
So this is our A Star algorithm.
We now have within its actual structure the nodes all linked together based on this value here.
So by the time we've run through this, we actually have a long list of nodes like a linked list or
basically it is a linked list of nodes.
We're at the end node, we've got hold of the end node.
Now we have to make our way back up to the start so that we actually the path would be in its forward
direction, not its reverse direction.
So when we come back in the next lecture, we'll keep working on this and we'll write this reconstruct
path method so that we can actually get the path we're looking for.