WEBVTT

00:02.610 --> 00:09.780
The star algorithm was invented by computer scientists Nils Nilsson, Peter Hart and Bertram Rafael

00:10.170 --> 00:16.620
while working on developing a navigation system for the Shakey, the Robot Research Project at Stanford

00:16.620 --> 00:18.690
in 1968.

00:19.440 --> 00:26.850
They had two algorithms that they were working on at the time, trying to find optimized ways of determining

00:26.850 --> 00:28.680
paths through environments.

00:29.310 --> 00:32.370
They called them a one and a two.

00:32.400 --> 00:38.790
It turned out that a two was actually the most optimal, and so they then just called it a star.

00:39.330 --> 00:45.690
The aStar algorithm is pretty synonymous with A.I. in games and used everywhere from planning actions

00:45.690 --> 00:49.680
and characters to determining the best path through an environment.

00:49.860 --> 00:55.500
The star algorithm tends to be something that's a little bit scary when you first get into computing

00:55.500 --> 01:02.220
and you have to develop your own and often you'll find your own library and just use that instead because

01:02.220 --> 01:06.750
it's going to work and then you won't have to understand what's going on underneath.

01:06.780 --> 01:12.990
But it's a very intuitive algorithm based on the way that humans actually think.

01:13.020 --> 01:17.850
So first, let me give you a little bit of a challenge.

01:17.940 --> 01:24.180
Given this maze that I've already created and in fact, just I guess it's a room, but you can only

01:24.180 --> 01:28.440
move in straight up and down or side to side movements.

01:28.440 --> 01:34.680
And I want you to think about what would your path from this starting position be to this ending position

01:34.680 --> 01:40.110
pause video now and maybe draw yourself a little diagram to have a think about what you might do and

01:40.110 --> 01:43.290
then the reasoning about why you did it.

01:51.350 --> 01:51.920
Okay.

01:51.950 --> 01:52.970
How did you go?

01:53.000 --> 01:55.490
Well, there's a number of different ways you can go now.

01:55.490 --> 02:00.170
You can't go diagonally, which would be the shortest path from start to finish, because we have to

02:00.170 --> 02:05.170
move in up and down or left and right, because that's the way we're building our maze.

02:05.180 --> 02:10.490
And so there's a variety of different patterns that you could have come up with going up and across

02:10.490 --> 02:13.910
and up and across, nothing across until you actually hit that upper corner.

02:13.910 --> 02:15.830
And here's just one of them.

02:16.040 --> 02:22.790
Now, you could have gone across and down and then across a few times and then go up.

02:22.790 --> 02:25.130
But I bet that you didn't do that.

02:25.130 --> 02:31.100
And the reason being is that if you go down at any point from the start, you're actually getting further

02:31.100 --> 02:32.660
away from the finish.

02:32.690 --> 02:39.740
And so therefore your choice of which step to take next should be getting you closer to the finish,

02:39.740 --> 02:41.720
not further away.

02:42.140 --> 02:48.950
Okay, so now what if I told you that the maze actually looks like this and there's a bit of a problem

02:48.950 --> 02:50.720
with the path you came up with?

02:50.720 --> 02:55.250
There's actually a wall in the road, and therefore you can't go that way.

02:55.280 --> 02:58.070
Which way would you go instead?

02:58.190 --> 03:05.120
Well, you'd head down to begin with and then come back up again, because that is the only way that

03:05.120 --> 03:06.320
you can go.

03:06.650 --> 03:12.260
But the thing is, when you don't know, those walls are there, so you can't actually see that far

03:12.260 --> 03:12.980
ahead.

03:12.980 --> 03:20.600
You're wanting to move closer to your goal position because that seems to be the more intuitive way

03:20.600 --> 03:21.590
to go.

03:21.590 --> 03:26.240
And this is really the basis of the star algorithm.

03:26.240 --> 03:32.870
It wants to keep trying squares that are closest to the final goal.

03:33.140 --> 03:37.310
Let's step through how a star works by considering this map.

03:37.400 --> 03:42.500
Starting in the bottom right corner, we have to decide which neighbour to pick.

03:42.620 --> 03:46.460
Remember, we are only moving vertically and horizontally.

03:46.460 --> 03:52.070
However, if you did allow a diagonal move then you would have one more extra neighbor.

03:52.220 --> 03:57.980
The algorithm will work the same, but we aren't doing diagonals at the moment so we can forget about

03:57.980 --> 03:59.420
that particular point.

03:59.870 --> 04:03.320
So which neighbor to make part of the path?

04:03.650 --> 04:09.620
Well, if you eyeballed it, the distance in a straight line from each of these neighbors is pretty

04:09.620 --> 04:10.550
much the same.

04:10.550 --> 04:15.050
Well, it's exactly the same, but a computer algorithm can't eyeball it.

04:15.080 --> 04:20.660
It can, however, calculate the distance that the goal is away from each neighbor.

04:20.660 --> 04:25.460
So we first add to our star algorithm the value of H.

04:25.670 --> 04:31.160
Now H ideally represents the cost of getting from the neighbor to the goal.

04:31.160 --> 04:35.060
In this case, we are going to use the distance as our cost.

04:35.480 --> 04:41.360
Though you could include other things in the cost, such as the shorter path might take you through

04:41.360 --> 04:46.880
a love of bit and therefore you wouldn't just consider the distance as one of the things included in

04:46.880 --> 04:51.470
the cost, but also how much damage to the player it will cause.

04:51.470 --> 04:59.390
So in this case, the distance for each neighbor and thus the h value is 5.8, which I determined using

04:59.390 --> 05:00.800
Pythagoras theorem.

05:00.980 --> 05:09.560
You could also determine it using the number of X moves, plus the number of Y moves between the neighbor

05:09.560 --> 05:10.280
and the goal.

05:10.280 --> 05:15.980
It doesn't really matter how you measure it, as long as it's consistently done for all neighbors to

05:15.980 --> 05:22.220
understand the next value used in the algorithm, we will take a quick look at an example.

05:22.220 --> 05:26.090
Let's say two people are travelling from the surf club to the golf club.

05:26.120 --> 05:33.650
At some point in time one person is here and the other is here just by eyeballing where they are.

05:33.680 --> 05:36.620
Can you guess which one took the shorter path?

05:36.620 --> 05:41.780
If you were to just take their distance to the goal, you wouldn't be getting the full story of how

05:41.780 --> 05:43.940
far they had already travelled.

05:44.690 --> 05:51.200
However, if you combine the distance from the points to the start with the remaining distance, you'd

05:51.200 --> 05:56.870
have a better idea of the total distance travelled by each, and then you could figure out what the

05:56.870 --> 05:58.340
shortest path was.

05:58.340 --> 06:00.560
And that's what the estar algorithm does.

06:00.560 --> 06:06.530
It considers not only the distance from the point to the goal, but also how far you've travelled to

06:06.530 --> 06:07.730
get to that point.

06:07.940 --> 06:12.770
In this case, the distance from the start to each neighbor is one.

06:12.770 --> 06:15.770
This value is denoted by the variable g.

06:16.620 --> 06:22.590
We then combine H and G and get an F value, which is the total of these.

06:22.800 --> 06:29.580
Essentially, the F represents the fitness of that particular neighbor to be on the path towards the

06:29.580 --> 06:30.290
goal.

06:30.300 --> 06:35.940
Once all neighbouring values have been calculated, the neighbor with the lowest F value is chosen as

06:35.940 --> 06:41.040
the next point on the path to keep track of which points have been visited.

06:41.070 --> 06:48.540
There is an open and closed list, so obviously START is going to go on the closed list after its neighbors

06:48.540 --> 06:52.140
are generated because it is well, definitely on the path.

06:52.170 --> 06:55.980
Next, in this case, we have neighbors with the same F values.

06:55.980 --> 07:00.960
So we can choose either one because neither is lower than the other.

07:01.350 --> 07:03.150
So let's just go up.

07:03.210 --> 07:08.250
We add this point to the closed list and then open its neighbors.

07:08.880 --> 07:12.870
Any new neighbors are added to the open list.

07:13.320 --> 07:18.690
Their H, G and F values are calculated in this case.

07:18.690 --> 07:22.890
We now have two points in the open list.

07:23.040 --> 07:24.360
Where do we go next?

07:24.360 --> 07:33.150
Well, we find the point that has the lowest F and we go back to there and have a look at its neighbors.

07:33.150 --> 07:36.690
So in this case, we actually go up for a little bit.

07:36.690 --> 07:43.350
And then because the F value of the Green Point down the bottom is the smaller one, we come back to

07:43.350 --> 07:49.890
there and put it in to the closed list and then open its neighbors.

07:50.880 --> 07:55.500
And we continue like that until we reach the goal location.

07:56.750 --> 07:57.230
Okay.

07:57.230 --> 08:01.040
Let's have a look at an example of this working.

08:01.080 --> 08:01.300
Okay.

08:01.310 --> 08:05.750
So I've generated a maze using the recursive method.

08:05.750 --> 08:13.010
Plus I've done a little bit of random wall removal and I've put in here some markers to show you where

08:13.010 --> 08:16.130
the start and end for our A Star is going to be.

08:16.130 --> 08:21.170
So the orange is the start and the yellow down here is the ending position.

08:21.320 --> 08:25.880
So each marker is going to show you a G, H and F value.

08:25.880 --> 08:33.050
So G is the distance from the start which is here can you can see that it's one for that one and one

08:33.050 --> 08:33.410
for this one.

08:33.410 --> 08:42.530
So these were the two neighbors that you could move into and the h value is the distance to the yellow.

08:42.530 --> 08:47.870
So I'm just using a straight old distance calculation Pythagoras theorem.

08:47.870 --> 08:53.120
And so from this one it's 4.47 and from this one down here it's 4.24.

08:53.120 --> 08:54.730
So this one is obviously closer.

08:54.800 --> 09:03.860
The F value, which is the addition of those two, gives us 5.24 for this red one and 5.47 for the purple

09:03.860 --> 09:04.310
one.

09:04.310 --> 09:12.410
Now, both of these get put into the open list and then the one that has the smallest F value in this

09:12.410 --> 09:18.980
case, this one gets picked out as the next point to have a look at to generate neighbors from now.

09:18.980 --> 09:20.180
That's why it's gone red.

09:20.180 --> 09:23.960
So it's going to go immediately red as it selects the next one from the open list.

09:23.960 --> 09:28.790
So it gets taken out of the open list, which means it can't come back to that one.

09:28.910 --> 09:32.720
Okay, so now let's go and have a look at the next values that are generated.

09:32.990 --> 09:33.320
Right?

09:33.320 --> 09:36.380
So this one here generated some neighbors.

09:36.380 --> 09:41.390
Now it's gone back and generated one at the start, which is okay, because in this case I don't have

09:41.390 --> 09:47.780
my start added into the open list at the beginning and then it's not marked as closed though.

09:47.780 --> 09:50.570
I could do that, but this still works anyway.

09:50.570 --> 09:52.640
Let's have a look at the distance values.

09:52.640 --> 10:02.870
So the distance of this one from the start is going to be the distance that it's parent one is so where

10:02.870 --> 10:07.160
it came from, which was one plus the distance from there.

10:07.160 --> 10:10.310
Okay, so now we get two, which makes us two from there.

10:10.310 --> 10:18.200
So we add this distance and this distance, the distance is then this distance across to here.

10:18.230 --> 10:24.110
Now this got it calculated as well, but because it's further away, it's basically going to get ignored.

10:24.620 --> 10:30.680
This one here would then have had its values updated again.

10:30.680 --> 10:35.960
So it's going to be still one from the actual start, which is still here.

10:36.350 --> 10:39.980
Now, you might be wondering, why does this say 24g up here?

10:39.980 --> 10:47.390
Because this was a node or a neighbor of this one, and it actually went the path to get back to this

10:47.390 --> 10:49.280
one, went like here and then back to there.

10:49.280 --> 10:50.810
So that's why that's a two.

10:51.020 --> 10:55.580
And it puts it out of contention basically because it's a very high value.

10:55.760 --> 10:56.150
Okay.

10:56.150 --> 10:59.690
So let's have a look at what's going to be chosen next.

10:59.900 --> 11:05.510
This one obviously, because it's gone red already and it's been put in the closed list, 5.47 for the

11:05.510 --> 11:06.230
F value.

11:06.230 --> 11:08.900
And down here we got 5.61.

11:08.900 --> 11:15.110
So this one is just going to sit in the open until it becomes a smallest, if ever.

11:15.230 --> 11:16.790
Okay, so let's go again.

11:17.330 --> 11:17.660
Right.

11:17.660 --> 11:22.940
So now this one has generated another point back to there, which is just basically ignored.

11:23.090 --> 11:27.920
And its other neighbor, which is over here, has its G, which is two.

11:27.920 --> 11:33.770
Okay, because it's like one, two and then it's H value which is 4.12.

11:33.770 --> 11:37.850
Again, this distance here gives it 6.12.

11:37.850 --> 11:44.180
This value here got recalculated or reused because it was still open, remember?

11:44.240 --> 11:47.930
And so it's smaller, so it gets chosen.

11:47.930 --> 11:50.390
So now the neighbors for this will get generated.

11:50.900 --> 11:52.730
So that means this one gets generated.

11:52.730 --> 11:55.280
Remember, that one's already in the closed list, so it won't happen.

11:55.280 --> 11:55.760
Okay.

11:55.760 --> 12:02.360
Now, if we have a look at these two values, we can see that this is obviously going to be the closest.

12:02.360 --> 12:04.700
So we go again and we get here.

12:04.700 --> 12:05.870
Now, look at this.

12:05.870 --> 12:10.160
This one is now 6.24.

12:10.760 --> 12:15.980
Even though it's actually closer, we can see physically that it's closer.

12:15.980 --> 12:20.720
This point up here is 6.12.

12:20.720 --> 12:26.000
Now, this was still open until recently, just went red, which means it's in the closed list.

12:26.000 --> 12:28.820
It's the one that's going to get the next neighbor calculated.

12:28.820 --> 12:33.110
So if we go for that, it didn't generates a point over here.

12:33.530 --> 12:38.270
Now, it ended up with an F of seven, which put this one back into contention.

12:38.270 --> 12:39.770
So we've come back to here.

12:39.950 --> 12:41.330
Okay, we get some more neighbors.

12:41.330 --> 12:47.240
So these two, this one ended up closer, then we generate another neighbor there.

12:47.270 --> 12:47.630
Okay.

12:47.630 --> 12:55.700
Now, if we have a look at these ones that are open, you can see that they are, in fact, all values

12:55.700 --> 12:55.850
of.

12:55.970 --> 12:56.630
Seven.

12:56.630 --> 13:04.190
So it's just picking one of those at random because it's going to order them by the smallest, but they're

13:04.190 --> 13:06.020
all the same, so we're just picking one.

13:06.200 --> 13:08.210
So we've just bounced up back to there.

13:08.210 --> 13:12.170
It'll generate this one, which is 8.12.

13:12.200 --> 13:17.630
Now, you saw that this went red, so it decided it would pick this one instead, which generates that

13:17.630 --> 13:23.090
one, which then comes down and generates this one, which is our final value.

13:23.300 --> 13:23.600
Okay.

13:23.630 --> 13:28.010
So you can see that the a star doesn't just go dum dum dum dum dum dum all the way down here.

13:28.010 --> 13:32.810
It actually will bounce back and forward a bit as it explores more of the stuff around it.

13:32.900 --> 13:39.030
The beauty of that is that it's never really looking ahead too far at all, okay?

13:39.110 --> 13:44.600
It's only ever calculating those distance values, the distance that you've already travelled and the

13:44.600 --> 13:47.260
distance you've still got to go, basically.

13:47.360 --> 13:54.860
Okay, so now if I just hit my mapping key that I've programmed in, it will show us our path that was

13:54.860 --> 13:55.670
calculated.

13:55.670 --> 14:01.850
Now to get the path at the end, you end up with all of these neighbours or nodes.

14:01.850 --> 14:06.080
We could call them in the closed list right back to here.

14:06.080 --> 14:13.040
So what we do is we start with this one and we follow it back to the points that we came from.

14:13.040 --> 14:18.380
So as we're travelling around, every time we go to a new neighbour, the neighbour has to remember

14:18.380 --> 14:19.660
its parent.

14:19.670 --> 14:25.850
So in the end we can travel back up through that parent tree and get our path.

14:26.720 --> 14:30.620
Okay, so that is the star algorithm and how it works.

14:30.620 --> 14:34.220
So it is quite a simple algorithm.

14:34.220 --> 14:36.410
I mean, the ideas are very simple.

14:36.410 --> 14:41.210
It's not doing anything extraneous, like I said, looking ahead or anything like that.

14:41.840 --> 14:48.620
And so now I hope that you have a better understanding conceptually of how it goes together, because

14:48.620 --> 14:54.530
when we come back in the next lecture, you're going to actually build this into your maze system.
