WEBVTT

00:02.830 --> 00:03.520
Okay.

00:03.520 --> 00:07.830
Let's get back into this Astra algorithm and finish it off.

00:07.840 --> 00:14.020
So we're still in begin search and we've created our starting and ending locations.

00:14.020 --> 00:18.700
So under here, what we're going to do is clear out our open and close lists.

00:18.700 --> 00:31.030
So open, dot clear and closed, not clear where they're going to add the starting position to the open

00:31.030 --> 00:31.270
list.

00:31.270 --> 00:36.460
So open add start node.

00:37.180 --> 00:45.100
And then finally, if you remember, we created that last pause, we're going to set that to equal the

00:45.640 --> 00:47.770
start node at this point.

00:47.980 --> 00:48.550
Okay.

00:48.550 --> 00:52.540
So we're ready to start searching under here.

00:52.540 --> 00:54.670
Let's create another method for searching.

00:55.030 --> 00:59.640
And this is really where you'll see everything we've been talking about so far come together.

00:59.920 --> 01:08.410
So void search and we'll pass through the path marker of this node.

01:10.250 --> 01:10.630
Okay.

01:10.640 --> 01:15.380
The first thing we're going to do is to test if we've hit the goal.

01:15.590 --> 01:19.400
So this is the sort of ending condition for everything.

01:19.520 --> 01:30.920
So if this node dot equals so there's one about equals coming into play goal node, then we're going

01:30.920 --> 01:35.600
to set dun equals true and just return.

01:35.960 --> 01:36.320
Okay.

01:36.350 --> 01:41.300
And basically the goal has been found.

01:41.960 --> 01:42.390
Right.

01:42.410 --> 01:50.300
Next, we're going to loop through and find all of the neighbors.

01:51.080 --> 01:51.380
Okay.

01:51.380 --> 01:55.930
Now, this is very similar to what we were doing in all of our maze algorithms.

01:56.030 --> 01:56.400
Okay.

01:56.420 --> 02:01.640
How did we get the neighbor of the current position?

02:01.670 --> 02:04.040
Well, let's just go back into Maze.

02:04.490 --> 02:09.890
We've already got that construct defined for us right here.

02:09.960 --> 02:13.930
Okay, so this is getting our neighbors for the map.

02:13.940 --> 02:19.940
We can also use it for our a star because we only want the horizontal and the vertical ones.

02:20.180 --> 02:26.390
However, if you want to be able to search on diagonals, there is no reason you can't put the diagonal

02:26.390 --> 02:28.220
coordinates in here.

02:28.220 --> 02:33.740
And the ASR algorithm we're about to write will work exactly the same.

02:33.940 --> 02:37.400
Okay, so let's start by looping through those map directions.

02:37.400 --> 02:49.400
So for each map location, dear in maze dot directions, let me scroll this up for you.

02:49.550 --> 02:52.370
We're going to find the neighbor.

02:52.640 --> 02:58.520
So map location neighbor is going to equal the direction.

02:58.520 --> 03:03.020
Plus this node dot location.

03:03.770 --> 03:11.410
Right now, before we can actually process this particular neighbor, it needs to meet a few conditions.

03:11.420 --> 03:14.900
The first one is that it shouldn't be a wall.

03:15.080 --> 03:21.330
If it's a wall, then we're just going to not process it and go to the next neighbor.

03:21.350 --> 03:27.740
So as a challenge, what I'd like you to do is write this if statement to check if the neighbor is a

03:27.740 --> 03:31.720
wall and if it is a wall, then to continue.

03:31.730 --> 03:32.570
So pause the video.

03:32.570 --> 03:35.510
Now, when we come back, I'll type that up for you.

03:36.630 --> 03:37.040
Okay.

03:37.080 --> 03:37.880
How did you go?

03:37.890 --> 03:39.450
Well, it's pretty straightforward.

03:39.450 --> 03:53.910
If maize dot map at the neighbor dot x and neighbor dot z equals one, it's a wall and we will continue.

03:53.910 --> 04:02.490
So continues just going to allow us to go to the next map direction which will take us to the next neighbor.

04:02.490 --> 04:11.460
Now the next if statement that we're going to have to consider is if the neighbor is outside the realm

04:11.460 --> 04:12.750
of our maze.

04:12.780 --> 04:13.260
Okay.

04:13.260 --> 04:15.240
So another challenge for you, right?

04:15.240 --> 04:22.890
This if statement to check if that neighbor is outside of where you want it to be, then also continue

04:22.920 --> 04:23.580
pause video.

04:23.580 --> 04:27.330
Now type that in when you come back, I'll shall continue.

04:28.300 --> 04:28.680
Okay.

04:28.690 --> 04:29.660
How did you go with that line?

04:29.680 --> 04:46.090
Well, it's if neighbor dot X is less than one or neighbor dot X is greater than or equal to May's dot

04:46.090 --> 05:03.880
width or neighbor dot z is less than one or neighbor dot z is greater than or equal to May's dot depth.

05:04.120 --> 05:07.990
And if that's the case, then we're going to continue.

05:08.440 --> 05:10.240
Now, one final condition.

05:10.360 --> 05:18.220
If the neighbor is already in the closed list, then we're also going to continue because we don't want

05:18.220 --> 05:24.610
to process it, but we haven't yet put anything in any closed lists, even though we do have a close

05:24.610 --> 05:25.180
list.

05:25.330 --> 05:34.060
So let's instead create our own method that checks if a neighbor is in that list.

05:34.480 --> 05:36.790
So just under the search, I'll put it down here.

05:36.790 --> 05:49.240
So let's put a ball is closed and then we'll pass through actually the map location marker and then.

05:50.850 --> 05:52.080
For each.

05:54.090 --> 05:55.050
Path.

05:56.390 --> 05:58.810
Marker p in.

06:00.200 --> 06:10.190
We're going to test if p dot location equals marker.

06:10.250 --> 06:12.410
Then we're going to return.

06:13.100 --> 06:14.060
True.

06:14.570 --> 06:17.210
Otherwise, we're going to return.

06:19.530 --> 06:20.340
False.

06:20.390 --> 06:20.900
Okay.

06:20.910 --> 06:27.630
Now, it seems a little bit long winded the way that we're passing through a marker and then we're actually

06:27.630 --> 06:34.740
looping through a closed loop which has path markers in it, and then actually testing against a marker

06:34.740 --> 06:41.430
and the location of a path, because this is the way we have to do it at this point.

06:41.430 --> 06:45.210
Up here, neighbor is just a map location.

06:45.210 --> 06:46.350
It's just a position on the map.

06:46.350 --> 06:49.110
We haven't given it a path marker.

06:49.110 --> 06:58.050
So it hasn't got like an instantiation of one of those path game objects that we've passed through above

06:58.050 --> 06:58.890
yet.

06:59.070 --> 07:06.720
So that's why we have these tests on a map location against whether there's a path marker with that

07:06.720 --> 07:07.770
location.

07:07.920 --> 07:08.370
Okay.

07:08.370 --> 07:15.750
So down in here we can put another if statement in if is closed neighbor, then we're just going to

07:15.780 --> 07:16.680
continue.

07:18.270 --> 07:24.540
Next, we're going to calculate our G, our H and our F value.

07:24.560 --> 07:38.040
So float g equals it's going to be the vector two dot distance from this node dot location, dot to

07:38.040 --> 07:48.630
vector and neighbor, dot to vector, dot to vector.

07:48.630 --> 07:50.760
So that's finding your Pythagoras.

07:50.790 --> 07:59.010
Now we've found the distance between the current node K and its neighbor.

07:59.010 --> 08:03.180
So this node here is basically the one that's going to be next to the neighbor.

08:03.270 --> 08:10.950
But you need to find the distance that has been travelled the entire way up to that node and then beyond.

08:10.950 --> 08:20.430
So you have to do that and then also add in this node and it's g value which is going to allow you to

08:20.430 --> 08:26.400
move one from your current node, plus add up all the path distance that you've accumulated along the

08:26.400 --> 08:27.030
journey.

08:27.300 --> 08:27.660
Right?

08:27.660 --> 08:29.010
And then we go to float.

08:29.010 --> 08:35.730
H Now this is the distance between where that neighbor is and the final goal.

08:35.730 --> 08:41.940
So again, we're going to use a vector to distance and we're finding the distance this time between

08:41.940 --> 08:46.770
the neighbor dot to vector to.

08:47.930 --> 08:50.000
And the goal node.

08:50.780 --> 08:51.350
Goal node.

08:52.670 --> 08:55.790
Location to vector.

08:56.900 --> 09:00.140
Back to vector, not vector too.

09:00.380 --> 09:06.080
And that's all you need to do for your h value and then float.

09:06.110 --> 09:12.620
F Now you should know what this is because it's probably the easiest calculation in the whole a star

09:12.620 --> 09:15.970
and that is g plus h.

09:15.980 --> 09:23.060
So basically it's just a summary of our path distances or the costs involved in travelling it.

09:23.570 --> 09:26.600
Okay, so now we've got that done.

09:26.600 --> 09:33.800
What we can do is create a game object to put on our path for this particular spot.

09:33.800 --> 09:38.690
So this neighbor is going to get a open block basically.

09:38.690 --> 09:51.080
So game object, path block equals instantiate and we want that path P that we passed through before

09:51.260 --> 09:55.100
and new vector three.

09:55.100 --> 10:00.860
This is the position in the actual game world where we will put that so it'll be our neighbor dot x

10:01.070 --> 10:11.510
and don't forget to multiply by our map dot scale back here which is in maze dot scale and then at zero

10:11.540 --> 10:20.780
in the Y and then neighbor dot z multiplied by maze dot scale.

10:20.900 --> 10:30.110
And then we want to just put Catalonian dot identity at the end of that.

10:31.190 --> 10:39.260
Now the path block itself or I should say the path this game object, if you have a look at it, let's

10:39.260 --> 10:42.380
go back into unity this prefab for path.

10:42.380 --> 10:51.410
If you open that up as a prefab and have a look at it, you'll see that there's a G and H and an F text

10:51.410 --> 10:53.180
mesh attached to it.

10:53.180 --> 10:57.500
And that's how I'm displaying the values of G, H and F.

10:57.500 --> 11:03.410
Of course, when you're using this in production to do a star, you don't have to worry about all little

11:03.420 --> 11:08.690
sort of interface and fancy stuff, but I want you to be able to see it as you step through.

11:08.720 --> 11:09.080
Okay?

11:09.080 --> 11:15.470
So that means our code needs to set those values and we'll come back in the next video and continue

11:15.470 --> 11:16.850
working on this code.
