WEBVTT

0
00:10.990 --> 00:16.530
In this lecture, we're going to look at creating a waypoint system that can be navigated with the

1
00:16.570 --> 00:24.810
A* algorithm. To begin, download the resource file that comes with this lecture and in it you'll find

2
00:24.930 --> 00:26.430
this scene with the tank.

3
00:26.430 --> 00:32.130
If you've done any of the other Unity-provided tutorials, you'll have seen these models before and

4
00:32.130 --> 00:37.990
I use them quite often because they're nice to look at and they're convenient and easy, so we don't have

5
00:38.010 --> 00:39.280
to put our own map together.

6
00:39.420 --> 00:42.590
Of course if you want to put your own map together, go for it.

7
00:42.600 --> 00:43.770
That's fine.

8
00:43.770 --> 00:47.130
Now we've got a map and we've also got a little tank.

9
00:47.130 --> 00:50.560
The tank will be our NPC character.

10
00:50.790 --> 00:57.180
What we're going to do is place some waypoints around the map and then we're going to link them up

11
00:57.540 --> 01:05.610
with edges and put some buttons on the screen to give the tank orders of where to go to. The first thing

12
01:05.610 --> 01:08.060
we'll do is place some waypoints.

13
01:08.070 --> 01:14.850
The important thing to remember here is that there's no physics or collision detection that will be in this

14
01:15.180 --> 01:20.420
project, which means you have to place waypoints where the tank can move.

15
01:20.430 --> 01:25.110
So it'll be the paths. In the project,

16
01:25.110 --> 01:29.220
I've created a WayPoint game object asset here.

17
01:29.250 --> 01:37.560
So this prefab, if I drag-and-drop it into the scene, you'll see that it automatically gives itself a

18
01:37.560 --> 01:38.600
number

19
01:39.090 --> 01:43.680
and each time you add a waypoint, it will count up for you.

20
01:43.700 --> 01:49.740
This is so you can keep track of which waypoint is which one, without having to click on it in the Hierarchy

21
01:49.800 --> 01:51.370
each time.

22
01:51.390 --> 01:58.350
So let's just zoom out. I'm going to place some waypoints around this map to get to the helipad, which

23
01:58.350 --> 01:59.440
is down here

24
01:59.730 --> 02:04.560
and one to get over here and to go around this building,

25
02:04.620 --> 02:08.020
but you can place them wherever you like. So I'll just go ahead and do that quickly.

26
02:14.400 --> 02:20.170
With all the waypoints in place, they will become the nodes in our graph.

27
02:20.330 --> 02:29.030
So we need to now determine where the edges are going to be and the edges are the lines that connect the nodes

28
02:29.540 --> 02:33.550
and will tell us where the tank can travel between.

29
02:33.950 --> 02:40.570
As I said at the beginning, these waypoints are also going to specify where the tank CAN'T travel

30
02:40.760 --> 02:45.820
so we don't want to put any paths through geometry.

31
02:45.950 --> 02:49.670
So it's working as a collision avoidance system as well.

32
02:49.670 --> 02:55.750
You can put waypoints like this through buildings if you want your NPCs to travel around in

33
02:55.750 --> 03:00.990
there and look like they're intelligent because then they're avoiding obstacles.

34
03:01.010 --> 03:09.580
So in this case, we can connect waypoint '1 with 2' and '2 with 3' and '1 with 3', anywhere where there's

35
03:09.590 --> 03:17.390
a clear line of sight, we can join them. So we can't get from here over to number 7 at the back, going that

36
03:17.390 --> 03:17.630
way.

37
03:17.630 --> 03:25.010
So we'll put lines here and here and I might even put a one-way path that goes up to here, so that the

38
03:25.010 --> 03:31.010
tank, if it is over here and wants to go back, has to go around this way.

39
03:31.470 --> 03:36.230
With all your paths planned out, you might like to write it down so that you've got a reference for when

40
03:36.230 --> 03:40.940
we go and put this information back into Unity.

41
03:40.950 --> 03:43.110
Now it's time to start creating some code

42
03:43.230 --> 03:50.670
but just before we do, we need an object in the scene which is going to manage all the waypoints.

43
03:50.670 --> 03:59.630
So in the Hierarchy, right-click and Create Empty and we're going to call this object WPManager.

44
04:00.960 --> 04:04.800
So this is our waypoint manager. On that, we'll put some code.

45
04:04.800 --> 04:12.480
So let's go over to the project and create a new C# script and we'll also call that WPManager.

46
04:12.510 --> 04:14.640
It doesn't matter if they're not the same,

47
04:14.640 --> 04:16.950
I just like to keep it consistent.

48
04:17.160 --> 04:25.380
Now with that WPManager, I'm going to drag-and-drop it onto our empty game object and then we'll open

49
04:25.380 --> 04:34.020
it up and start to edit it. Above the WPManager class, we're going to add in a little struct and that's

50
04:34.020 --> 04:40.470
just there to help facilitate the data entry and storage of our graph.

51
04:40.470 --> 04:47.700
The graph is going into another system, but we still need to be able to put the graph into

52
04:47.700 --> 04:49.770
the WPManager in some way

53
04:49.770 --> 04:54.220
and the simplest way at the moment is just to make the Inspector look good

54
04:54.390 --> 04:56.750
to facilitate this, essentially.

55
04:56.760 --> 05:02.340
So this is a Link and a link is going to be basically the edge.

56
05:02.460 --> 05:09.660
So it defines the nodes on either end of an edge, the direction of it and whether it's unidirectional, which

57
05:09.660 --> 05:16.530
means that it goes in one way, or whether it's bi, which means it travels in two directions...and that's stored

58
05:16.530 --> 05:17.920
down here in the direction variable.

59
05:17.930 --> 05:20.990
So there's only three things in here essentially.

60
05:21.000 --> 05:28.850
Next we're going to define the waypoints, the links and also make a graph from them.

61
05:28.980 --> 05:31.880
So at the top here, add this.

62
05:32.250 --> 05:35.430
So we have a GameObject array holding our waypoints.

63
05:35.430 --> 05:39.870
This will be all of those spheres that we've placed down on our map.

64
05:39.990 --> 05:44.390
Then we have an array of links, which we will also define

65
05:44.400 --> 05:49.110
and this allows us to say 'this one connects to that one' and 'this one connects to that one' and whether

66
05:49.110 --> 05:51.900
you can travel in both directions or not

67
05:52.020 --> 05:58.680
and if there's no link for waypoints, then they obviously aren't connected. Then with all that, we will

68
05:58.680 --> 06:03.090
create a new graph of type 'Graph'.

69
06:03.090 --> 06:12.220
Now the graph code and the A* algorithm has all been written for you and I've provided that inside this

70
06:12.270 --> 06:15.640
'Graphs' folder in Assets. If you have a look in

71
06:15.650 --> 06:22.050
there, you'll find 3 classes. There's one for Graph, one for Node and one for Edge and they're all very

72
06:22.440 --> 06:23.460
elementary.

73
06:23.460 --> 06:30.390
So please do have a look through those, but I won't go into any detail of their inner workings, except to

74
06:30.390 --> 06:33.250
tell you that they use the A* algorithm.

75
06:34.530 --> 06:39.980
Back in the WPManager code, we'll work in the Start function to set everything up.

76
06:40.030 --> 06:47.680
So in here, just add this code. We're going to loop through the waypoints array which is at the top

77
06:47.740 --> 06:51.370
and this is the one we feed our waypoints to manually.

78
06:51.370 --> 06:59.230
If there are waypoints in that array, we're going to loop through each one and feed it into our graph that

79
06:59.230 --> 07:01.500
we've created up here.

80
07:01.840 --> 07:09.280
The graph code has an AddNode method and you can feed the game objects through into there,

81
07:09.280 --> 07:12.340
so each node has to exist.

82
07:12.340 --> 07:17.650
Each game object needs to be added into that graph before you can do anything with your links.

83
07:17.830 --> 07:25.810
After that, we're going to then do the same thing with the links and loop through those and use the

84
07:25.810 --> 07:34.300
graph.AddEdge method to create an edge between one node and the other.

85
07:34.300 --> 07:46.300
Now this AddEdge only does unidirectional edges (so one-directional). If the edge we've defined is a bidirectional

86
07:46.300 --> 07:52.030
one, then I've got a little test in here just to check that you've made it bidirectional and if it

87
07:52.030 --> 07:57.530
is, then it adds another edge and just swaps the two nodes around.

88
07:57.550 --> 07:57.920
All right.

89
07:57.920 --> 08:05.680
So that's all you need to construct the graph and you can now put as many waypoints and edge definitions

90
08:05.800 --> 08:08.920
into these things via the Inspector

91
08:09.040 --> 08:11.390
and if you build it all for you.

92
08:11.440 --> 08:19.180
Now one last thing will be really nice is if we can see the edges because we can already see the nodes

93
08:19.270 --> 08:20.350
on the map.

94
08:20.560 --> 08:30.130
But if we can see the edges, it will help us to debug the program. In the graph, it's got a debugDraw

95
08:30.550 --> 08:39.110
method like that. If we put that in the Update, then we can see the edges that we have created.

96
08:39.110 --> 08:39.420
All right.

97
08:39.430 --> 08:42.270
So save all that and we'll go and

98
08:42.280 --> 08:48.910
fill up the Inspector with our nodes and edges. On the WPManager

99
08:49.210 --> 08:53.570
you'll now find Waypoints and Links.

100
08:53.710 --> 09:00.610
So we've got 11 waypoints (so put 11 in here to open that up)

101
09:00.610 --> 09:04.200
and these are all the separate waypoints and I want them to be in order.

102
09:04.210 --> 09:08.780
That means I need to drag them in one-by-one, so I'll quickly do that...

103
09:12.060 --> 09:19.080
The next thing to fill out is the links. I've got 13 links and that's the number of individual paths

104
09:19.080 --> 09:21.460
between each of your nodes.

105
09:21.540 --> 09:26.060
So I'll put 13 in there, which will expose all of the elements.

106
09:26.100 --> 09:29.050
So I'm now going to create these links one-by-one.

107
09:29.130 --> 09:35.750
The first link that I've got is the one between waypoint 1, over here and waypoint 2, down there.

108
09:35.760 --> 09:43.460
So I'll grab hold of waypoint 1 from the Hierarchy and drag it into there and waypoint 2 into there.

109
09:43.470 --> 09:49.080
Now if you have a unidirectional link, which only goes in one direction, then you want to put the starting

110
09:49.080 --> 09:52.910
node first and the second node next. With this set to UNI,

111
09:53.100 --> 09:56.460
it will only let the tank go in this direction.

112
09:56.520 --> 09:57.930
It couldn't go back again.

113
09:58.140 --> 10:04.100
So I'm going to set that to BI because I do want the tank to be able to go back and forward between those

114
10:04.100 --> 10:04.930
two.

115
10:04.980 --> 10:11.390
The next element that I'll put in, just to show you what's going on with the link between 8 and 9.

116
10:11.400 --> 10:13.970
Remember I said I wanted to put it just in one direction?

117
10:14.100 --> 10:21.960
So I want it to go from 8 (which will be our first one) to 9 (which will be the next one here) and then

118
10:21.960 --> 10:25.920
leave it at unidirectional instead of changing it.

119
10:25.920 --> 10:28.260
So it'll only go in one direction.

120
10:28.290 --> 10:30.700
All right so I'll go through and do the rest of these

121
10:30.930 --> 10:35.700
and it's probably easiest if you did have all this written down on a piece of paper like I've got and

122
10:35.700 --> 10:40.710
then you can cross off each path as you've done it, which will make it a lot simpler.

123
10:42.520 --> 10:48.760
When you think you're done with all of your paths, you can press Play and then switch back into the Scene view

124
10:48.880 --> 10:51.460
and you'll be able to see those paths.

125
10:51.640 --> 10:57.310
So they're drawn out where you've created a link and you can see them there.

126
10:57.310 --> 11:05.380
Now if you zoom in a little bit closer, the line or the edge has a blue mark at the end of it.

127
11:05.400 --> 11:07.840
So that shows you the direction it's going in.

128
11:07.840 --> 11:12.710
In this case, you can see that there's a blue mark on both ends of that line.

129
11:12.730 --> 11:15.200
So that means you can travel back and forward along it.

130
11:15.280 --> 11:18.940
Now our only unidirectional one at the moment, if

131
11:18.940 --> 11:25.530
I come around here, is this line here and you can see there's

132
11:25.870 --> 11:33.800
(I hope you can see, it's quite small isn't it! Let me move up...)

133
11:33.900 --> 11:36.170
So there it's got a bit of blue

134
11:36.390 --> 11:43.230
and at the other end, it's got no blue which means it's traveling in this direction

135
11:43.300 --> 11:44.530
in our unidirection.

136
11:44.530 --> 11:51.180
So if our tank ends up down here, the only way it will be able to get back to anywhere over here is to

137
11:51.180 --> 11:55.890
go around this shed or whatever it is.

138
11:55.890 --> 11:59.010
Ok, so now we have our waypoints,

139
11:59.010 --> 12:02.270
we just have to let our tank know about them.

140
12:02.410 --> 12:04.920
We'll create some driving code for the tank.

141
12:04.920 --> 12:15.010
Go into 'Create > C# Script' and we'll call this FollowPath and this code is based on the

142
12:15.030 --> 12:17.720
MoveLocal code that we've used before.

143
12:17.730 --> 12:20.390
So, in here we're going to add some code.

144
12:20.400 --> 12:24.100
I'll put it all in at once and then go through it with you.

145
12:24.230 --> 12:24.500
Ok.

146
12:24.510 --> 12:30.540
So here it is. Like before, we have a goal, but it's not exposed this time because we're not passing the

147
12:30.540 --> 12:35.010
goal through as something that the NPC can grab hold of.

148
12:35.070 --> 12:38.880
The goal will come from our A* algorithm.

149
12:38.880 --> 12:41.510
Next we have the usual suspects.

150
12:41.520 --> 12:47.960
We've got our speed, accuracy and rotational speed, so we need those values again.

151
12:48.030 --> 12:55.980
After that, we'll need a public-exposed value for WPManager because the WPManager holds all of the

152
12:55.980 --> 13:01.080
waypoints and the graph information and the NPC needs to know about that.

153
13:01.110 --> 13:09.210
So we'll pass that through to this code in the Inspector. Next I'm creating some local values,

154
13:09.210 --> 13:16.110
so a 'wps' here, which will grab hold of all the waypoints from the manager and then we've got a

155
13:16.110 --> 13:24.900
GameObject representing the current node that we're trying to get to and that, I guess essentially, is our goal

156
13:24.960 --> 13:26.940
at any particular time.

157
13:26.970 --> 13:30.300
After that there's an int called currentWP.

158
13:30.330 --> 13:38.900
Now this is the index of the waypoint along the path that we're following.

159
13:38.910 --> 13:44.400
So if we're going along a path and let's say there's three waypoints in it, then the first waypoint

160
13:44.400 --> 13:46.160
would be 0,

161
13:46.230 --> 13:49.570
the next will be 1 and the next will be 2.

162
13:49.770 --> 13:56.490
So this is just to keep track of how we've moved along the path that the A* algorithm has calculated

163
13:56.490 --> 14:02.370
for us. It doesn't have anything to do with the waypoint's position

164
14:02.370 --> 14:03.840
in our waypoint array.

165
14:03.930 --> 14:06.010
So it's a completely different thing.

166
14:06.510 --> 14:10.720
Now after that, I've got Graph declared as well

167
14:10.830 --> 14:17.220
and these things, this 'wps' and 'Graph' is just to make our code a little bit shorter later on and you'll

168
14:17.220 --> 14:21.390
see why immediately because in Start is where I set them up.

169
14:21.390 --> 14:25.370
If I didn't have these two things we'd have to type this code in each

170
14:25.360 --> 14:29.070
time we wanted to grab hold of something from the waypoint manager.

171
14:29.070 --> 14:34.480
So it's much easier just to assign it into these variables here where we can grab it.

172
14:34.530 --> 14:41.870
Next, we need to set the current node which is this game object up here which does point to the physical

173
14:42.230 --> 14:46.030
node, the physical game object sphere that's in our world.

174
14:46.790 --> 14:57.590
This here is set to 7 in this case because my tank (if we have a look here) is near 7.

175
14:57.590 --> 15:01.010
Actually it's NOT near 7, it WAS near 7, it's near 1 now.

176
15:01.250 --> 15:02.990
My waypoints have renumbered.

177
15:03.050 --> 15:11.350
So let's just change that to 0 because for waypoint 1 in the array, we're positioned at 0.

178
15:11.450 --> 15:16.400
So whatever waypoint your tank is near,  that's what you want for your start,

179
15:16.400 --> 15:23.780
so it has some kind of a reference as to where it currently is and then how it's going to calculate

180
15:24.650 --> 15:27.280
how it moves through the A* algorithm.

181
15:27.350 --> 15:29.470
So that's the start.

182
15:29.510 --> 15:35.090
Now after that there's two functions that I'm going to come back to...let's go down here.

183
15:36.200 --> 15:39.740
Now in the LateUpdate there is

184
15:39.740 --> 15:46.640
first of all an 'if' statement asking us if the path length from our graph (so

185
15:46.650 --> 15:48.570
if(g.getPathLength() == 0)

186
15:48.770 --> 15:57.080
which is essentially saying there is no path length, or the current waypoint index is equal to the path

187
15:57.080 --> 15:58.400
length.

188
15:58.460 --> 16:05.570
If you've got a path with 3 nodes in it and you're up to the third node and your path length would

189
16:05.570 --> 16:06.640
then be 3 as well

190
16:06.640 --> 16:07.760
because it's got three things in it.

191
16:07.760 --> 16:10.830
If these two are the same, it means you're at the end.

192
16:11.000 --> 16:15.220
So if you've got an empty path or you're at the end of the path, then just return.

193
16:15.230 --> 16:18.990
You don't want to keep moving towards any goal because there is no goal.

194
16:19.130 --> 16:28.920
After that we set the current node to get the path point at the current waypoint value.

195
16:29.090 --> 16:36.650
So if we're moving along a path and we're up to say position number 3, then we say we want the third

196
16:36.650 --> 16:43.190
node along this path and it will give us the physical node that we need to be heading towards here.

197
16:43.220 --> 16:50.330
After that, we've got a very familiar-looking 'if' statement, which is testing our accuracy.

198
16:50.330 --> 16:59.270
So if the distance between the tank (which is this transform.position) and the point at the current

199
16:59.270 --> 17:06.860
waypoint is less than our accuracy, then we're close enough to have been hitting our waypoint, just

200
17:06.860 --> 17:09.470
like the other algorithms we've already written.

201
17:09.470 --> 17:16.580
In this case, we just increment the current count along our path and this will allow us to calculate

202
17:16.610 --> 17:19.940
the next point and head off towards the next point.

203
17:20.030 --> 17:26.180
Next, we're doing another test to ensure that we haven't hit the end of the path (because this code up

204
17:26.170 --> 17:33.020
here might mean that we've hit the end of the path) then we can move our tank forward and we're moving the

205
17:33.020 --> 17:41.570
tank using the exact same code (which is this here) that you'll find that we developed in our MoveLocal

206
17:41.570 --> 17:46.130
script previously for moving and turning towards a point.

207
17:46.130 --> 17:48.050
So this is exactly the same

208
17:48.410 --> 17:56.720
and the goal I'm just setting to be equal to the transform of the current sphere that is at position

209
17:56.840 --> 17:59.440
'currentWP' in the path.

210
17:59.510 --> 18:03.040
So exactly the same code, same sort of movement.

211
18:03.170 --> 18:09.800
All we're doing is now following a path given to us by waypoints rather than us giving the agent

212
18:09.800 --> 18:14.520
a position to go to because it's following something around on the map.

213
18:14.670 --> 18:20.840
Lastly (and because I'm running out of time in this 20 minute video) you need to add these two public

214
18:20.840 --> 18:24.570
functions which I'll show you how to use in the next lecture.

215
18:24.890 --> 18:30.800
They are public functions that could be run outside, so we will connect buttons on the screen up to

216
18:30.810 --> 18:31.150
these.

217
18:31.160 --> 18:35.840
What they're doing is running the A* algorithm, so this is the bit doing all of the work.

218
18:36.500 --> 18:42.500
If we want to go to the helipad, then the helipad is at waypoint 2.

219
18:42.500 --> 18:47.900
I've still got my old waypoint systems in here. Waypoint 2 is going to be waypoint 1 in the array because

220
18:47.900 --> 18:50.140
remember arrays start counting at zero.

221
18:50.480 --> 18:56.900
And the Ruin is waypoint 7 for me, which would be 6 in the array there.

222
18:57.080 --> 19:04.640
So it takes the current node that you're at, the destination and runs it through the A* algorithm which

223
19:04.640 --> 19:11.690
will give you the path that is now used in LateUpdate. After each one of the

224
19:11.690 --> 19:18.410
A* calls, make sure you set your waypoint counter back to 0, so that you can start at point 0

225
19:18.500 --> 19:21.170
on the map and then head through.

226
19:21.440 --> 19:28.070
So that's all the code for FollowPath. Save that and I'll catch up with you in the next lecture, where we'll

227
19:28.160 --> 19:30.360
implement this with some buttons.