WEBVTT

00:02.860 --> 00:06.940
In the previous lecture, we started working on our Graph API.

00:06.970 --> 00:13.510
Now we're at the point where we're ready to put in the functionality for an A star algorithm pathfinding

00:13.510 --> 00:14.290
search.

00:14.620 --> 00:20.940
So it probably makes sense to just revise the aStar algorithm that we looked at in the previous section.

00:20.950 --> 00:28.870
So we have a maze or we have a series of waypoints that are connected with edges which aren't any different

00:28.870 --> 00:30.020
to a maze.

00:30.040 --> 00:36.280
So in the maze, each square was basically a node, and if you could get from one square to another,

00:36.280 --> 00:39.220
then that was an edge or a path between them.

00:39.340 --> 00:41.500
So we've got to start position.

00:41.500 --> 00:43.000
We've got a goal position.

00:43.000 --> 00:45.690
We have to calculate how to get through this.

00:45.700 --> 00:52.600
Now, there's three values that we're going to assess each position on, and that is the PH value,

00:52.600 --> 00:59.440
which is the cost of getting to the goal from that node, the G value, which is the cost to get to

00:59.440 --> 00:59.920
that node.

00:59.920 --> 01:02.860
So how much it's already cost to get to that node from the start.

01:02.860 --> 01:09.850
And then we have an H value, which is the addition of both those things that gives the overall node

01:09.850 --> 01:17.380
its like holistic kind of cost I guess on how fit it is, how its the best one to go for.

01:17.380 --> 01:22.630
So we're going to write some of these algorithms into our graph class.

01:23.680 --> 01:24.160
Okay.

01:24.160 --> 01:31.540
So we first of all are going to create our heuristic, which is basically our method that will determine

01:31.540 --> 01:33.700
how fit each node is.

01:33.700 --> 01:39.760
And in this case, we're going to use the distance from the node to the ending location, which is going

01:39.760 --> 01:42.160
to be sort of as the crow flies.

01:42.280 --> 01:47.410
So that's why it's called a holistic I guess it's kind of like the best guess you can make because we

01:47.410 --> 01:47.920
don't know.

01:47.920 --> 01:51.700
We can't actually fly straight across to the ending position.

01:51.700 --> 01:57.550
We might be able to, but from each node, that's just going to be our best way of measuring it.

01:57.550 --> 02:00.220
So let's just create something that returns a float.

02:00.220 --> 02:03.160
Let's call it distance and into it.

02:03.190 --> 02:07.740
We'll pass node A and node B.

02:07.750 --> 02:13.900
Now, of course, this is such a simple calculation that you probably don't need to write a method for

02:13.900 --> 02:15.940
it, but way ah anyway, just so that you can see it.

02:15.940 --> 02:21.670
So what we're going to return in here is the squared magnitude.

02:21.670 --> 02:24.850
So we want vector three squared magnitude.

02:24.850 --> 02:30.400
Now the square magnitude is quicker to calculate than the actual magnitude between two points, which

02:30.400 --> 02:31.840
is a vector.

02:31.840 --> 02:37.930
And it doesn't matter if we use a square magnitude as long as we're assessing every single node based

02:37.930 --> 02:41.020
on the same kind of assessment algorithm, which is this one here.

02:41.020 --> 02:54.400
So our square magnitude will be a dot ID or get I'd dot transform dot position minus and that's got

02:54.400 --> 03:00.460
to be in a bracket around there minus our other node, which is the B node.

03:00.460 --> 03:09.160
So B dot get ID dot, transform dot position like that.

03:09.160 --> 03:09.610
Okay.

03:09.610 --> 03:12.430
So that's going to be our heuristic.

03:12.610 --> 03:15.880
Now, I'm missing a bracket just there.

03:15.880 --> 03:16.340
Okay.

03:16.360 --> 03:25.090
Right now, once we have that associated with every single node, we need to find the one that has the

03:25.090 --> 03:28.660
shortest distance, that means we'll need another algorithm to find it.

03:28.690 --> 03:37.870
Now, in the previous version of a star that we created, in the last section, we used a link query

03:37.870 --> 03:38.920
to do that.

03:39.280 --> 03:40.180
We're not going to do that now.

03:40.180 --> 03:42.280
We're actually going to do it manually.

03:42.280 --> 03:48.970
So this is the same algorithm, but just slightly, I guess, more hands on, more manual way of typing

03:48.970 --> 03:49.600
it all out.

03:49.600 --> 03:55.270
So we'll call this the lowest F and this is basically going to do our LINQ query anyway.

03:55.270 --> 04:05.830
So list node will pass through all of our nodes and then in here we're going to calculate and return

04:05.830 --> 04:07.930
the position of the lowest node.

04:07.930 --> 04:21.940
So we want float lowest f equals zero, int count equals zero int iterator count equals zero.

04:22.720 --> 04:33.460
Now we'll initialize our lowest f value to be lowest f is going to equal the first value in our list.

04:33.460 --> 04:40.270
So L zero dot f and iterate account is zero for that.

04:40.270 --> 04:46.300
So we have to make sure this iterate account lines up with what's in this L here, which we will do

04:46.300 --> 04:47.410
in the following loop.

04:47.410 --> 04:50.560
So now we'll loop through all of them and check them out to find the lowest.

04:50.560 --> 04:59.230
So for int i equals one I is less than l dot count i plus plus.

05:00.820 --> 05:01.430
And then in here.

05:01.480 --> 05:01.810
Here.

05:01.810 --> 05:03.700
We'll go if.

05:04.000 --> 05:21.790
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

05:21.790 --> 05:25.750
iterator count equals our count.

05:27.380 --> 05:27.690
Okay.

05:28.120 --> 05:28.840
So then we.

05:28.840 --> 05:33.730
Then down here go count plus, plus.

05:34.900 --> 05:48.150
And after that we return our iterator count, which will be our node with the lowest F value k.

05:48.160 --> 05:54.070
Now along with those two things, we need to now implement our a star.

05:54.070 --> 05:59.080
So we'll come up above our distance and put those things in here.

05:59.380 --> 06:05.440
K So this is quite a long algorithm which you would have noticed when we went through it earlier, but

06:05.530 --> 06:12.460
this will be the same but slightly different because we're not using that link code in here.

06:12.460 --> 06:35.890
So public bool a star game object start id game object and i d and then node start equals our find node

06:36.820 --> 06:38.530
start ID.

06:38.560 --> 06:43.090
So we're allowing game objects to be passed through and we're using our find node that we created before

06:43.090 --> 07:02.410
to get the correct nodes from the list, find node and id k and then if start equals null or end equals

07:02.410 --> 07:05.740
null, just a little bit of error checking.

07:05.740 --> 07:10.810
If we can't find those nodes, we will return false and say, well, there's no path here.

07:11.970 --> 07:15.850
Okay, so now let's get into the actual a star.

07:15.850 --> 07:20.830
So we need a list of nodes which will be our open list.

07:20.830 --> 07:26.770
So node open equals new list node.

07:28.970 --> 07:31.850
And then we need the same thing again for our closed.

07:31.850 --> 07:33.800
So I'm just going to copy and paste that in.

07:33.890 --> 07:35.810
This is our closed list.

07:37.250 --> 07:37.490
Okay.

07:37.550 --> 07:48.080
Then I can create a float for tentative g score and equal that to zero.

07:48.110 --> 07:49.540
Now what was G?

07:49.550 --> 07:55.280
Well, G is our distance that we've gone so far.

07:55.310 --> 08:04.310
Okay, so the tentative G score is what we would give the node if we're about to put it into a list

08:04.310 --> 08:08.570
and actually select it as our next position in the graph.

08:08.570 --> 08:10.190
So we need to calculate it first.

08:10.190 --> 08:12.980
Basically, then we're going to have a bool.

08:13.280 --> 08:16.190
Tentative is better.

08:16.190 --> 08:24.590
So if we calculate the tentative G score to be actually better than the one that's already on the node,

08:24.590 --> 08:27.050
then we can use the better one.

08:27.560 --> 08:31.490
So let's go with start dot g equals zero.

08:31.490 --> 08:35.300
Now this is before we've actually started looping through anything, so we're just setting these two

08:35.300 --> 08:36.080
values up.

08:36.080 --> 08:44.970
Start at h equals distance of start and k.

08:45.200 --> 08:48.200
So H is our distance to the end.

08:48.200 --> 08:52.910
G is how far we've come all the costs so far, which is going to be zero because we haven't gone anywhere

08:52.910 --> 08:53.300
yet.

08:53.300 --> 09:02.930
And then start dot f equals start dot h because there's nothing to actually add together at this point.

09:02.930 --> 09:09.650
Now open ad is going to equal our start node like that.

09:09.650 --> 09:21.770
Okay, so now for our big wall loop, while open dot count is greater than zero, let's make that a

09:21.770 --> 09:33.350
t int i equals lowest f in the open list because we want to select that our next one we're going to

09:33.350 --> 09:51.170
go to so node this node equals open list at position I then if this dot this node dot ID equals the

09:51.170 --> 09:56.390
end ID, then that means we've found a path.

09:57.860 --> 10:02.690
So in here we will reconstruct the path which I'll type out in a moment.

10:02.690 --> 10:09.830
So reconstruct path that's going to be the name of our method from start to end.

10:11.960 --> 10:16.070
Let's make that a capital and we will return.

10:16.790 --> 10:17.690
True.

10:17.990 --> 10:24.020
So we'll come back and do the reconstructions later on brackets going in there because that's a method.

10:24.260 --> 10:25.760
So let's go down.

10:25.760 --> 10:27.660
And here we haven't found the end.

10:27.680 --> 10:31.060
Let's continue comparing things so open.

10:31.170 --> 10:33.170
Dot remove at.

10:33.170 --> 10:35.390
Let's remove the node we're working with.

10:36.710 --> 10:37.520
I.

10:39.900 --> 10:41.700
Closed ad.

10:42.820 --> 10:47.950
This node because we've now said that we're exploring it.

10:47.950 --> 10:49.990
So node neighbor.

10:49.990 --> 10:56.500
So from that particular node, we're now going to explore all of the neighbors.

10:56.500 --> 10:57.910
So node neighbor.

10:58.030 --> 11:04.330
So for each edge E in this node dot edge list.

11:04.330 --> 11:08.980
So these are all the paths coming out of that particular node that we've just closed.

11:09.730 --> 11:12.820
We're going to explore all of these neighbors.

11:12.820 --> 11:19.030
So the neighbor is going to equal E end node.

11:20.980 --> 11:22.300
Now if.

11:23.020 --> 11:27.580
Closed dot index of neighbor.

11:28.060 --> 11:35.410
So if the neighbor is kind of out of bounds because we've already been there, we will just continue

11:35.440 --> 11:41.620
looking at the other edges because there's no point looking at something that's already being closed.

11:41.770 --> 11:42.340
Okay.

11:42.340 --> 11:53.260
So now also tentative g score equals this node dot g plus distance from this node to the neighbor.

11:54.370 --> 12:04.890
Then if open index of neighbor equals minus one, then it's not in the open list.

12:04.900 --> 12:06.730
We want to add it to the open list.

12:06.730 --> 12:15.250
So open add neighbor so that we can actually explore it again next time and then we'll set tentative

12:16.180 --> 12:35.080
is better to equal true else if ten a2g score is less than neighbor dot g, then we'll also say that

12:35.080 --> 12:37.990
tentative is better.

12:38.860 --> 12:40.330
Equals true.

12:40.510 --> 12:44.070
Otherwise tentative is better.

12:44.080 --> 12:45.850
Equals false.

12:47.280 --> 12:47.820
Okay.

12:47.820 --> 12:54.630
So once we've gone through that process, if tentative is better, if the a g value that we've just

12:54.630 --> 12:58.560
calculated is better than we just want to give that node that new g value.

12:58.560 --> 13:03.630
So if tentative is better than in here, we'll go.

13:03.630 --> 13:20.970
Neighbor Dot came from equals this node neighbor dot g equals tentative g score neighbor dot h equals

13:21.090 --> 13:37.140
distance from this node to the end node and then neighbor dot f equals neighbor dot g plus neighbor

13:37.500 --> 13:39.630
dot h.

13:41.370 --> 13:43.110
Okay, so that's done.

13:43.110 --> 13:54.840
Now if we've got through to here and we haven't actually returned a true further up anywhere, then

13:54.840 --> 14:00.720
we actually want to, which would be up in here where we construct the path is to quit out of here with

14:00.720 --> 14:03.900
a return false, saying that there's still no path.

14:03.900 --> 14:08.070
There's no path between those two nodes anywhere that can be found.

14:08.370 --> 14:09.060
All right.

14:09.060 --> 14:11.850
So this is our A Star algorithm.

14:11.850 --> 14:22.680
We now have within its actual structure the nodes all linked together based on this value here.

14:22.680 --> 14:28.710
So by the time we've run through this, we actually have a long list of nodes like a linked list or

14:28.710 --> 14:30.750
basically it is a linked list of nodes.

14:30.750 --> 14:33.870
We're at the end node, we've got hold of the end node.

14:33.900 --> 14:39.960
Now we have to make our way back up to the start so that we actually the path would be in its forward

14:39.960 --> 14:42.510
direction, not its reverse direction.

14:42.750 --> 14:48.750
So when we come back in the next lecture, we'll keep working on this and we'll write this reconstruct

14:48.750 --> 14:53.670
path method so that we can actually get the path we're looking for.
