WEBVTT

00:02.330 --> 00:02.860
Okay.

00:02.870 --> 00:05.720
How are you coping with Easter so far?

00:05.750 --> 00:07.400
Well, we haven't even got into the code yet.

00:07.400 --> 00:10.370
And there's an awful lot of code that we have to write.

00:10.370 --> 00:15.290
But hopefully it's going to seem quite familiar because we've gone through all of the basics and how

00:15.290 --> 00:16.220
it works.

00:16.460 --> 00:20.500
So let's begin now inside of this class.

00:20.510 --> 00:26.060
First of all, we need to grab hold of our actual maze so that we can get its map.

00:26.060 --> 00:29.300
So public maze, maze.

00:29.960 --> 00:38.570
Now, this is going to be a little bit of a combination between actually running the algorithm and then

00:38.570 --> 00:42.170
also showing it, visualising it on the screen.

00:42.170 --> 00:46.970
So we're going to have some constructs that are just for all the number crunching and everything and

00:46.970 --> 00:50.600
then others that are going to show things up for you.

00:50.630 --> 00:50.880
Okay.

00:50.930 --> 00:57.050
So first of all, I'm just going to add in two materials that we'll use to change our nodes from one

00:57.050 --> 00:58.790
color to the other as they're processed.

00:58.790 --> 01:02.390
So material, closed material.

01:03.830 --> 01:10.370
And you can probably guess what the next one is, public material, open material.

01:11.630 --> 01:18.170
Then we need to create our two open and closed lists.

01:18.800 --> 01:24.470
So we're going to have a list of path markers.

01:27.280 --> 01:33.910
Four Open equals new list path marker.

01:37.000 --> 01:39.700
And then we also need one for clothes.

01:39.700 --> 01:41.830
So let's just copy that.

01:43.600 --> 01:46.450
And make this closed.

01:47.290 --> 01:53.560
And then we need to bring in our game objects that are going to be our actual physical markers on the

01:53.560 --> 01:54.550
map that we can see.

01:54.550 --> 01:58.600
So public game object.

02:00.100 --> 02:01.030
Start.

02:02.450 --> 02:07.010
Public game object and.

02:07.520 --> 02:09.260
And public.

02:09.410 --> 02:09.830
Game.

02:09.830 --> 02:10.760
Object.

02:10.760 --> 02:11.750
Path.

02:13.500 --> 02:16.690
Point or path marker or whatever it is.

02:16.710 --> 02:17.180
Okay.

02:17.190 --> 02:18.090
I'm just going to call it that.

02:18.090 --> 02:22.140
So let's just save this and we will switch back into unity.

02:22.650 --> 02:29.670
And we want to go to the Maze Game object in the hierarchy and drag and drop find path a star script

02:29.670 --> 02:30.690
onto there.

02:30.840 --> 02:35.190
Now we're going to populate these items in the script.

02:35.190 --> 02:41.100
So the maze is the script that is generating the maze, which is this recursive script.

02:41.100 --> 02:44.190
So just drag that down into there.

02:44.730 --> 02:53.280
We then have a start and end and our path p markers as well as a closed and open material.

02:53.280 --> 02:59.610
Now attached to this lecture there is a little unity package with some materials and prefabs in it.

02:59.610 --> 03:06.510
If you bring that in, you'll find you get a models folder here which has materials and prefabs.

03:06.900 --> 03:16.110
So if we go to our prefabs first and then select our maze, we can put the start object into the start,

03:16.200 --> 03:22.740
the end into the end, and then the path marker into the path.

03:22.740 --> 03:32.250
P Now we can also set our materials for the closed and open nodes as we're going through.

03:32.250 --> 03:39.180
So for closed I'm going to use red and for open I'll use green.

03:39.180 --> 03:45.960
So this will just make the whole thing more visual so that you can see exactly what's going on as the

03:46.200 --> 03:48.120
star algorithm starts to work.

03:48.540 --> 03:52.590
Okay, so now let's go back into our code.

03:53.250 --> 03:59.760
Now, these three things are our game objects that we're going to instantiate and then hold onto them

03:59.760 --> 04:02.460
inside path marker objects.

04:02.820 --> 04:12.630
So we'll create a path marker for the gold node and we'll also create one for the start.

04:12.630 --> 04:17.280
So path marker, start.

04:17.880 --> 04:18.810
Node.

04:19.740 --> 04:22.350
We'll also need another path marker.

04:22.590 --> 04:29.670
And this path, mark, is going to keep track of the last point that we're at, so last position in

04:29.670 --> 04:30.690
this case.

04:30.990 --> 04:38.670
And then we're also going to keep track of a bull called Done, which will be true when we've found

04:38.670 --> 04:41.100
our way to the end of the path.

04:41.100 --> 04:45.000
So let's initially set this to false like that.

04:45.000 --> 04:45.240
Okay?

04:45.240 --> 04:50.940
So that's all of the things that we need at the top, all of our variables.

04:51.120 --> 04:51.540
All right.

04:51.540 --> 04:56.610
So I'm going to save that again, switch back to Unity and show you something before we continue.

04:56.610 --> 05:04.140
So if we go into our prefabs where I've got these markers and just click on one, if you go over into

05:04.140 --> 05:08.490
the inspector, you'll see that they are tagged as marker.

05:08.670 --> 05:16.470
I've done this so that we can remove them with a key press out of the map, which will come in useful

05:16.470 --> 05:17.280
in a moment.

05:17.640 --> 05:25.770
So what we're going to be doing is having the ability to be able to remove them all and then do the

05:25.770 --> 05:30.540
ASR over and over without restarting our code, which means you can have a bit of a play around with

05:30.540 --> 05:32.370
it and get used to the results.

05:32.520 --> 05:41.430
So let's create a void, remove all markers, and this is just going to be a really quick loop that

05:41.430 --> 05:42.780
just destroys everything.

05:42.780 --> 05:44.700
So game object.

05:46.750 --> 05:49.030
A ray of Marcus.

05:50.980 --> 05:53.280
Equals game objects.

05:53.420 --> 05:57.040
Find game objects with.

06:00.230 --> 06:00.770
Tag.

06:00.770 --> 06:05.530
Make sure you use game objects with the SE and that'll be marker.

06:07.450 --> 06:07.870
Okay.

06:07.870 --> 06:20.980
And then we'll just do a quick then we'll just do a quick for each game object m marker in markers.

06:24.240 --> 06:26.100
Destroy em.

06:27.870 --> 06:30.750
So that will be called shortly.

06:31.110 --> 06:33.720
All right, let's now begin our search.

06:33.720 --> 06:34.890
So void.

06:35.610 --> 06:37.560
Begin, search.

06:37.770 --> 06:42.990
We will allow this to be called over and over again, as I said before.

06:42.990 --> 06:46.860
So every time we do, we're going to set done to equal false.

06:48.540 --> 06:50.010
And then we will run.

06:50.010 --> 06:53.910
Remove all markers.

06:56.770 --> 06:57.460
Okay.

06:57.460 --> 07:02.170
So now we can actually go about creating our goals and everything.

07:02.950 --> 07:12.550
So first of all, we have to pick two positions in the actual maze that are going to be our start and

07:12.550 --> 07:13.030
end.

07:13.030 --> 07:19.840
And we could do it quite randomly, where we just keep picking random values and seeing whether they

07:19.840 --> 07:23.440
are a space or a wall and of course, use the space.

07:23.560 --> 07:30.760
A better way is to actually put all of the spaces or all of the maze locations that aren't a wall into

07:30.760 --> 07:31.690
a little list.

07:31.720 --> 07:38.050
Shuffle that list using the shuffle method that you'll find in the extensions file and then just like

07:38.050 --> 07:39.280
pick them off the top.

07:39.640 --> 07:50.950
So I'm going to create a list of map locations, and that's going to be called Locations Equals New

07:51.700 --> 07:52.720
List.

07:53.810 --> 07:56.120
Map location.

07:58.390 --> 07:58.640
Okay.

07:58.720 --> 08:04.030
We're then going to create our nested loops to loop around our map.

08:04.030 --> 08:12.940
So if we want to for int z equals one to Z is less than our maze depth.

08:14.590 --> 08:18.070
Minus one and then Z plus.

08:18.070 --> 08:18.750
Plus.

08:18.820 --> 08:20.560
Same thing for.

08:21.830 --> 08:22.800
X.

08:23.510 --> 08:27.080
So let's change that to X and X.

08:27.080 --> 08:32.420
And in this case, we want our width and make that x.

08:32.420 --> 08:41.750
And inside of here we're going to test if may stop map for that x.

08:41.990 --> 08:47.750
Z does not equal one, then we will put it into our list.

08:48.170 --> 08:55.550
Locations dot add new map location.

08:56.770 --> 08:57.580
X.

08:57.610 --> 08:58.420
Z.

08:59.050 --> 09:03.640
So why are we using not equals to one in this code?

09:03.670 --> 09:09.520
Well, in the mice code, if you have a look in there and the recursive algorithm that's writing it

09:09.730 --> 09:15.340
in the mazes that we're generating, there's a value of zero where there's an empty space and a one

09:15.340 --> 09:16.570
where there's a wall.

09:16.600 --> 09:22.660
However, when you're creating mazes, you might have other values that represent other things inside

09:22.660 --> 09:24.140
of that maze area.

09:24.160 --> 09:30.730
So we're only really worried if there is a wall there at the moment as far as where we can move.

09:30.730 --> 09:35.600
And that's why we're using not equals to one here.

09:35.620 --> 09:44.230
So we do know that ones are the walls and the starting positions can be any other value at this point.

09:44.230 --> 09:46.530
So that's why I've got not equal to one.

09:46.540 --> 09:50.890
So but the time we've gone through this, we now have all of these locations.

09:50.890 --> 09:56.080
And so if we just shuffle them, so locations shuffle.

09:57.690 --> 10:04.920
That's going to give us a couple of values sitting on the top of that list that we can go ahead and

10:04.920 --> 10:09.630
pluck out and use as the goal location and also as the starting location.

10:10.680 --> 10:12.570
So let's go ahead and do that.

10:12.570 --> 10:18.930
So after the shuffle, I'm going to create a vector three, which will be our start location.

10:20.660 --> 10:27.320
And we'll set that to a new vector three and to get the values, we're going to pluck them out, as

10:27.320 --> 10:36.830
I said, the location and we're going to give it locations at position zero dot X and then we can just

10:36.830 --> 10:44.990
put it zero for the Y value and locations, zero for the Z position.

10:45.320 --> 10:49.910
Now we're putting zero as the height because I have done that with pretty much everything that we're

10:49.910 --> 10:53.600
just zeroing it as a flat surface.

10:53.900 --> 10:57.260
So it's basically sort of two D at least.

10:57.410 --> 11:04.550
And then once we have this location, we're going to instantiate our first node at that location.

11:04.550 --> 11:07.190
So I'm going to create a start node.

11:09.690 --> 11:14.310
And that's going to equal a new path marker.

11:15.490 --> 11:18.370
Which will be a new map.

11:19.490 --> 11:28.310
Location, locations zero dot X, locations zero dot Z.

11:28.310 --> 11:31.100
So the same uses you're using for the position.

11:31.160 --> 11:41.480
And then we're going to send through a zero, then we're going to zero our G, our H and our F values.

11:41.750 --> 11:48.320
And for the game marker, I've just come down a line so I don't go off the screen for you.

11:48.560 --> 11:53.900
We will instantiate the start.

11:54.620 --> 11:55.640
Start.

11:57.130 --> 11:58.570
Location.

11:59.830 --> 12:08.350
And then we'll just put Kitten in dot identity for the rotation because that's not really important.

12:08.440 --> 12:11.260
And finally, the parent is going to be null.

12:11.260 --> 12:12.730
So we'll just put that there.

12:12.730 --> 12:16.000
And for the goal location, we do the same thing.

12:16.240 --> 12:22.180
So I'm just going to copy all of that, save typing it out again, put it down here, make sure that

12:22.180 --> 12:28.210
we're talking about the goal location, the position of the goal location.

12:28.210 --> 12:33.850
We're going to use that as the second value in that locations array that we shuffled.

12:33.850 --> 12:36.250
So let's just set all of those values there to one.

12:36.400 --> 12:41.470
And then this node down here is going to be our goal node.

12:41.740 --> 12:50.020
Now, at the same time that we actually create the path marker, we're going to instantiate those prefabs.

12:50.320 --> 12:56.170
So this one here is actually going to be the end prefab that we sent through before.

12:56.470 --> 12:57.040
Okay?

12:57.040 --> 13:03.760
So now we can actually run, begin, search and we'll be able to see those markers come up.

13:03.760 --> 13:06.310
So I'm going to do that down in the update.

13:06.310 --> 13:19.030
So just in here, let's put if input dot get key down is key code dot p.

13:20.190 --> 13:23.390
Then we'll do a bargain search.

13:23.850 --> 13:32.070
Now, one little tweak we need to make to this code is to add in a scaling value because the maze itself

13:32.070 --> 13:40.770
uses a scale to make it bigger on the screen for you to actually bring it out and the actual positions

13:40.770 --> 13:42.150
in the map there.

13:42.150 --> 13:43.620
Okay, they don't need to be scaled up.

13:43.620 --> 13:45.870
They're still in light unit positions.

13:45.870 --> 13:52.530
But our start location and our goal location need to be scaled up according to what the map scale is

13:52.530 --> 13:53.560
set to.

13:53.790 --> 14:00.540
So for the actual map values, we're not scaling those up by the map scale, but for any positioning

14:00.540 --> 14:02.280
we do of objects.

14:02.280 --> 14:06.420
So what I'm going to do up here is put in multiply.

14:08.180 --> 14:10.940
Maize dot scale.

14:11.390 --> 14:20.090
And then we want to use that value there and put it for our Z location and also for our goal location

14:20.090 --> 14:20.900
here.

14:21.920 --> 14:22.720
Okay.

14:22.730 --> 14:23.090
Right.

14:23.090 --> 14:27.440
So that's now going to give us a better location.

14:27.590 --> 14:33.500
I've also just noticed that should be goal location there as well, so that we can see the goal in the

14:33.500 --> 14:34.460
goal location.

14:34.490 --> 14:34.790
Okay.

14:34.790 --> 14:35.910
So let's save that.

14:35.930 --> 14:38.120
We'll switch back to unity now.

14:38.120 --> 14:41.870
We're going to have a look at the maze for a second before we press play.

14:42.140 --> 14:49.220
And in this case, you can see that my recursive script has the map size at 30 by 30.

14:49.490 --> 14:54.260
You could leave it this big, but it'll be a long time finding a path through there.

14:54.260 --> 15:02.390
So what I recommend is that you actually set it down to ten and ten, so it makes it a manageable sized

15:02.390 --> 15:03.320
maze.

15:03.470 --> 15:09.890
Okay, so now if we hit play, we'll be able to see our small maze pop up.

15:09.890 --> 15:12.980
There it is over there so you can go and focus in on it.

15:13.640 --> 15:20.120
And then if we hit the P key, make sure you've clicked in the game window so that will become active.

15:20.150 --> 15:29.450
Hit the P key and you will see that you get your starter positions popping up there because remember

15:29.450 --> 15:35.570
we're setting them randomly and there's nothing else going on between just creating them.

15:35.740 --> 15:36.030
Okay.

15:36.080 --> 15:41.840
So you can see very clearly where you've got to start and where you are going to end.

15:41.870 --> 15:42.170
Okay.

15:42.170 --> 15:44.410
I'm going to leave this video here for now.

15:44.420 --> 15:51.500
When we come back, we will continue working on the aStar algorithm to do some pathfinding.
