WEBVTT

00:02.560 --> 00:05.970
Welcome back to part six on the Easter algorithm.

00:05.980 --> 00:12.190
Now, although I said the concept is really simple, the code just goes on and on, but we're almost,

00:12.190 --> 00:12.880
almost done.

00:12.880 --> 00:15.220
I think I might have actually said that in the last video.

00:15.460 --> 00:18.010
Anyway, what you've got so far, you should be able to run.

00:18.010 --> 00:20.740
So I hope you had a little bit of a look at it.

00:21.390 --> 00:27.000
But if you couldn't kind of work out what was going on, let's just run it through with you.

00:27.030 --> 00:31.670
So let's press play and we'll generate our ten by ten maze.

00:31.680 --> 00:32.640
So here it is.

00:32.640 --> 00:33.270
Here.

00:33.330 --> 00:40.750
Now, if we hit the P key, we'll get a starting and ending node system sitting in there.

00:40.770 --> 00:49.200
Now, when you hit C, it's going to generate positions on, you know, to start exploring basically.

00:49.200 --> 00:58.050
Let's see if I can just turn this around so we can see the values on those nodes.

00:58.050 --> 00:58.590
There you go.

00:58.590 --> 01:03.670
So we've got G, H and F values just in there.

01:03.690 --> 01:08.670
Now, if we hit C again, then we'll start adding more.

01:08.670 --> 01:15.930
Now, as a node is explored and put into closed, it becomes red, which means we don't explore it again.

01:16.500 --> 01:22.950
So then we keep going and you'll see that we're searching out in both directions until we find a path

01:22.950 --> 01:26.130
all the way to the end.

01:26.130 --> 01:29.880
At which point, if you keep hitting C, nothing's going to happen.

01:29.880 --> 01:37.800
So we've actually found the point here is our final position this way didn't work, we ran out.

01:37.950 --> 01:43.710
And what we have to do now is to actually get the path.

01:43.920 --> 01:50.490
The path isn't all of the red nodes, okay, because they're over here.

01:50.700 --> 01:53.730
So the path to get to here doesn't actually involve these nodes.

01:53.730 --> 01:55.590
We just searched through them.

01:55.590 --> 02:03.510
The path can be found by getting the last node and actually working our way back around to where we

02:03.510 --> 02:04.820
started from.

02:04.830 --> 02:11.760
Now at this point you can hit the p key and because of the way that we coded this, you can start again

02:11.760 --> 02:16.290
and then work through that at your own pace.

02:16.290 --> 02:22.350
To get a better understanding, you'll be able to see how the G, H and F values get updated and changed

02:22.350 --> 02:23.230
in here.

02:23.250 --> 02:27.110
Now, if you want to work with a bigger maze, you can do that too.

02:27.120 --> 02:36.390
So if we click on our maze and come over into the recursive script and change this to say 30 by 30 and

02:36.390 --> 02:41.370
then press play, you'll see how the algorithm behaves in a bigger setting.

02:41.370 --> 02:46.260
Now, of course, we'd have to zoom out to actually see the whole thing, which means you could lose

02:46.470 --> 02:51.720
a lot of the detail of the F values, but you might not be interested in that.

02:51.720 --> 02:57.420
So let me click over here and we hit the P, there's our starting and ending and then you can just hit

02:57.930 --> 03:07.020
the C until we just keep going and going until we eventually get to the end and find a path which could

03:07.020 --> 03:08.490
take a little bit of time.

03:08.490 --> 03:13.980
So I won't sit here and continue doing that, but you'll again see how we've got a lot of closed nodes

03:13.980 --> 03:20.700
in the search that's going on over here, which is probably not going to be part of this actual path

03:20.700 --> 03:22.200
to getting to this point.

03:22.200 --> 03:24.300
And we want to work backwards.

03:24.630 --> 03:25.140
Okay.

03:25.140 --> 03:31.110
So that's the last bit that we actually have to put into our code is getting the path.

03:31.710 --> 03:36.060
Each time we press C, we're going to do a search with our last position.

03:36.060 --> 03:43.140
Now, if we go back up to our search, the last position is set at the end, which is the marker from

03:43.140 --> 03:46.410
the open list with the smallest value.

03:46.530 --> 03:53.010
And then if we have a look at the top and remember what we did is that if we passing through this node

03:53.010 --> 04:00.240
and it's actually equal to the goal node, it's just going to return without doing anything and set

04:00.240 --> 04:02.550
done to equal true.

04:02.550 --> 04:10.290
So that means after we have finished finding the goal location and what I'm going to do just down in

04:10.290 --> 04:16.710
here to make sure we don't keep trying to run that is put and not done.

04:17.910 --> 04:22.050
It's going to basically stop us doing anything when we press.

04:22.050 --> 04:25.320
See, now, what have we got at this point?

04:25.320 --> 04:33.190
Well, if we have a look at an example map, what you'll see is a whole bunch of closed nodes there,

04:33.240 --> 04:34.110
all the red ones.

04:34.110 --> 04:39.690
This isn't the path, as I've said, these are just all the ones that we've explored and could possibly

04:39.690 --> 04:40.830
be on the path.

04:40.890 --> 04:50.190
The ones that are on the path are the ones linked by that parent value that we added right up here.

04:50.460 --> 04:53.910
So here's our parent value in our path marker.

04:53.910 --> 05:02.910
So if we get our very last node, our goal location node and follow it backwards up to its parent,

05:02.910 --> 05:07.200
then get the parent of that one and the parent of that one until you'll get all the way back to the

05:07.200 --> 05:07.680
start.

05:07.680 --> 05:12.420
We will actually have our a star path.

05:13.290 --> 05:13.740
Okay.

05:13.740 --> 05:20.910
So considering by the time this C key doesn't work anymore and done.

05:21.050 --> 05:22.910
Is equal to true.

05:22.940 --> 05:30.800
The value of last position is going to have the goal position in it.

05:31.310 --> 05:38.390
Taking that into consideration, we're going to use that to backtrack up through the parent list.

05:38.450 --> 05:50.120
So let's put another IFF in here, input dot get key down and I'll put key code dot m for map in this

05:50.120 --> 05:50.720
case.

05:51.470 --> 05:58.550
And then if that is the case, we're going to get path.

05:59.060 --> 06:02.840
Of course, we haven't written that yet, so that's going to be above the update.

06:03.810 --> 06:04.450
Void.

06:04.530 --> 06:05.760
Get path.

06:05.880 --> 06:15.180
And in here, what I'm going to do is, first of all, remove all of the markers, which means we've

06:15.180 --> 06:22.140
cleared all those little blocks off of the map and we can actually put markers just where the path is

06:22.380 --> 06:24.150
and we'll get our starting position.

06:24.150 --> 06:26.670
So path marker.

06:27.720 --> 06:31.890
Begin equals the last pause.

06:33.960 --> 06:34.830
Okay.

06:35.490 --> 06:40.110
Now, you didn't think it was going to be that easy or that I'd let you off that easy?

06:40.350 --> 06:44.520
What I'd like you to do as a challenge is finish this method.

06:44.520 --> 06:52.350
So you're going to have to start with the last pause and loop somehow back up through all the parents.

06:52.350 --> 06:58.800
Each time you encounter the parent, you want to put a marker down on the map at that location.

06:58.800 --> 07:02.620
And this is going to happen when you press the key.

07:02.640 --> 07:09.270
Once you've gone through all the C's and you've run out of actual markers and you've found a path,

07:09.600 --> 07:14.130
okay, so pause the video now go and give that a go.

07:14.130 --> 07:17.040
And when we come back, I'll show you my solution.

07:19.430 --> 07:20.090
Okay.

07:20.180 --> 07:22.500
How did you go with that?

07:22.520 --> 07:27.110
Bit of a challenge, but nothing that I'm sure you can't handle.

07:27.470 --> 07:29.420
I'm going to use a wall loop for mine.

07:29.420 --> 07:34.670
So while we're not at the start node.

07:34.670 --> 07:35.240
So start.

07:35.240 --> 07:39.020
Node dot equals begin.

07:39.230 --> 07:40.270
So we'll begin.

07:40.280 --> 07:46.070
It's not the same as the start node and begin does not equal null.

07:47.240 --> 07:51.830
So hopefully we actually have a path marker to start from.

07:51.860 --> 07:55.640
While this is true, we're going to instantiate.

07:57.360 --> 08:11.010
A path pe prefab at the position so new vector three and it'll be begin location dot x and don't forget

08:11.010 --> 08:26.100
to multiply it by our maze dot scale zero and then begin dot location dot z multiplied by maze dot scale

08:26.640 --> 08:29.460
and then of course a kitten in.

08:30.960 --> 08:32.560
Dot identity.

08:32.580 --> 08:35.040
Just to finish off the creation.

08:35.340 --> 08:41.240
Now that creates a block or a marker at that last pause.

08:41.250 --> 08:48.150
We want to now step up to the parent of last pause or in this case begin, because we've started at

08:48.150 --> 08:48.750
begin.

08:48.930 --> 08:55.560
So what we're going to do is say that begin now equals begin dot parent.

08:57.300 --> 08:58.080
Like that.

08:59.400 --> 09:00.540
Okay, great.

09:00.540 --> 09:08.010
Now, once we've done that, we can also put the starting node there, the one we actually started from,

09:08.010 --> 09:11.850
just in case it's not in any of these lists.

09:11.850 --> 09:17.010
And the start node actually doesn't have any parents or anything, so it might be left out.

09:17.010 --> 09:19.170
So I'm just going to instantiate that.

09:20.710 --> 09:39.880
Path pea new vector three start node dot location dot x multiplied by our maze dot scale zero and our

09:39.880 --> 09:40.870
start.

09:41.740 --> 09:49.990
Node dot location y multiplied by our maze dot scale.

09:51.550 --> 09:56.650
And then a turn in identity.

09:57.190 --> 10:04.450
Okay, now, because we're looping while we're not equal to the start, meaning that we actually have

10:04.450 --> 10:10.780
to do this here at the end and not forget to put a comma at the end of there.

10:11.050 --> 10:16.810
I just had the idea that this could be a do while loop, which would then incorporate that in there,

10:16.810 --> 10:18.850
and you may have actually done that yourself.

10:18.850 --> 10:23.020
So if you did, well done and this is pretty much it.

10:23.200 --> 10:25.780
Noticed I've just got a Y there instead of a Z.

10:26.590 --> 10:32.590
If you've come up with something different for this loop, then please do share it on the forums or

10:32.590 --> 10:38.500
the Q&amp;A wherever you can get in touch with us because we're always interested to see in how other people

10:38.500 --> 10:39.820
have solved the same problems.

10:39.820 --> 10:44.200
And as I always say, my code is not the most optimized or efficient.

10:44.200 --> 10:46.780
It's built so that you can actually read what I'm doing.

10:46.900 --> 10:48.750
Okay, so let's save that.

10:48.760 --> 10:55.240
We're going to go back into unity and we're going to try this out.

10:55.240 --> 10:58.750
So first of all, let's go the maze and make it smaller again.

10:58.750 --> 11:02.340
So let's make it like 15 by 15.

11:02.350 --> 11:07.270
Okay, so we press play, which will get us our maze.

11:07.360 --> 11:10.960
Let's just get that into the screen so you can see it.

11:10.960 --> 11:15.340
Now we hit P, which will give us our starting and ending positions.

11:15.400 --> 11:20.170
Then we hit C until we actually find a path.

11:20.170 --> 11:20.860
And this is the case.

11:20.860 --> 11:21.970
It's quite easy.

11:22.120 --> 11:28.330
Then if we hit M to get our path, you can see that goes through and it deletes everything and just

11:28.330 --> 11:31.690
leaves you what is in that path list.

11:32.170 --> 11:33.430
K Let's have another go.

11:33.430 --> 11:35.860
So let's go to P again.

11:35.860 --> 11:44.140
They're a little bit further away this time and we hit C until we exhaust our search or get to the end,

11:44.140 --> 11:53.080
which we're going to K and then we hit the key and it gives us our path from one to the other or this

11:53.080 --> 11:56.880
one goes like that and around there, okay.

11:56.890 --> 12:05.470
So that is the a star path algorithm visually represented so that you can actually work through it,

12:05.470 --> 12:08.400
work through the values and the calculations of the G and F.

12:08.410 --> 12:12.910
So you really get a handle on how it works.

12:12.910 --> 12:17.920
And trust me, there's no end to the uses for this particular algorithm.

12:17.920 --> 12:25.150
We see it all the time in AI, so I hope you really enjoyed this section and you got a lot out of it.
