In this lecture, we're going to look at creating a waypoint system that can be navigated with the
A* algorithm. To begin, download the resource file that comes with this lecture and in it you'll find
this scene with the tank.
If you've done any of the other Unity-provided tutorials, you'll have seen these models before and
I use them quite often because they're nice to look at and they're convenient and easy, so we don't have
to put our own map together.
Of course if you want to put your own map together, go for it.
That's fine.
Now we've got a map and we've also got a little tank.
The tank will be our NPC character.
What we're going to do is place some waypoints around the map and then we're going to link them up
with edges and put some buttons on the screen to give the tank orders of where to go to. The first thing
we'll do is place some waypoints.
The important thing to remember here is that there's no physics or collision detection that will be in this
project, which means you have to place waypoints where the tank can move.
So it'll be the paths. In the project,
I've created a WayPoint game object asset here.
So this prefab, if I drag-and-drop it into the scene, you'll see that it automatically gives itself a
number
and each time you add a waypoint, it will count up for you.
This is so you can keep track of which waypoint is which one, without having to click on it in the Hierarchy
each time.
So let's just zoom out. I'm going to place some waypoints around this map to get to the helipad, which
is down here
and one to get over here and to go around this building,
but you can place them wherever you like. So I'll just go ahead and do that quickly.
With all the waypoints in place, they will become the nodes in our graph.
So we need to now determine where the edges are going to be and the edges are the lines that connect the nodes
and will tell us where the tank can travel between.
As I said at the beginning, these waypoints are also going to specify where the tank CAN'T travel
so we don't want to put any paths through geometry.
So it's working as a collision avoidance system as well.
You can put waypoints like this through buildings if you want your NPCs to travel around in
there and look like they're intelligent because then they're avoiding obstacles.
So in this case, we can connect waypoint '1 with 2' and '2 with 3' and '1 with 3', anywhere where there's
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
way.
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
tank, if it is over here and wants to go back, has to go around this way.
With all your paths planned out, you might like to write it down so that you've got a reference for when
we go and put this information back into Unity.
Now it's time to start creating some code
but just before we do, we need an object in the scene which is going to manage all the waypoints.
So in the Hierarchy, right-click and Create Empty and we're going to call this object WPManager.
So this is our waypoint manager. On that, we'll put some code.
So let's go over to the project and create a new C# script and we'll also call that WPManager.
It doesn't matter if they're not the same,
I just like to keep it consistent.
Now with that WPManager, I'm going to drag-and-drop it onto our empty game object and then we'll open
it up and start to edit it. Above the WPManager class, we're going to add in a little struct and that's
just there to help facilitate the data entry and storage of our graph.
The graph is going into another system, but we still need to be able to put the graph into
the WPManager in some way
and the simplest way at the moment is just to make the Inspector look good
to facilitate this, essentially.
So this is a Link and a link is going to be basically the edge.
So it defines the nodes on either end of an edge, the direction of it and whether it's unidirectional, which
means that it goes in one way, or whether it's bi, which means it travels in two directions...and that's stored
down here in the direction variable.
So there's only three things in here essentially.
Next we're going to define the waypoints, the links and also make a graph from them.
So at the top here, add this.
So we have a GameObject array holding our waypoints.
This will be all of those spheres that we've placed down on our map.
Then we have an array of links, which we will also define
and this allows us to say 'this one connects to that one' and 'this one connects to that one' and whether
you can travel in both directions or not
and if there's no link for waypoints, then they obviously aren't connected. Then with all that, we will
create a new graph of type 'Graph'.
Now the graph code and the A* algorithm has all been written for you and I've provided that inside this
'Graphs' folder in Assets. If you have a look in
there, you'll find 3 classes. There's one for Graph, one for Node and one for Edge and they're all very
elementary.
So please do have a look through those, but I won't go into any detail of their inner workings, except to
tell you that they use the A* algorithm.
Back in the WPManager code, we'll work in the Start function to set everything up.
So in here, just add this code. We're going to loop through the waypoints array which is at the top
and this is the one we feed our waypoints to manually.
If there are waypoints in that array, we're going to loop through each one and feed it into our graph that
we've created up here.
The graph code has an AddNode method and you can feed the game objects through into there,
so each node has to exist.
Each game object needs to be added into that graph before you can do anything with your links.
After that, we're going to then do the same thing with the links and loop through those and use the
graph.AddEdge method to create an edge between one node and the other.
Now this AddEdge only does unidirectional edges (so one-directional). If the edge we've defined is a bidirectional
one, then I've got a little test in here just to check that you've made it bidirectional and if it
is, then it adds another edge and just swaps the two nodes around.
All right.
So that's all you need to construct the graph and you can now put as many waypoints and edge definitions
into these things via the Inspector
and if you build it all for you.
Now one last thing will be really nice is if we can see the edges because we can already see the nodes
on the map.
But if we can see the edges, it will help us to debug the program. In the graph, it's got a debugDraw
method like that. If we put that in the Update, then we can see the edges that we have created.
All right.
So save all that and we'll go and
fill up the Inspector with our nodes and edges. On the WPManager
you'll now find Waypoints and Links.
So we've got 11 waypoints (so put 11 in here to open that up)
and these are all the separate waypoints and I want them to be in order.
That means I need to drag them in one-by-one, so I'll quickly do that...
The next thing to fill out is the links. I've got 13 links and that's the number of individual paths
between each of your nodes.
So I'll put 13 in there, which will expose all of the elements.
So I'm now going to create these links one-by-one.
The first link that I've got is the one between waypoint 1, over here and waypoint 2, down there.
So I'll grab hold of waypoint 1 from the Hierarchy and drag it into there and waypoint 2 into there.
Now if you have a unidirectional link, which only goes in one direction, then you want to put the starting
node first and the second node next. With this set to UNI,
it will only let the tank go in this direction.
It couldn't go back again.
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
two.
The next element that I'll put in, just to show you what's going on with the link between 8 and 9.
Remember I said I wanted to put it just in one direction?
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
leave it at unidirectional instead of changing it.
So it'll only go in one direction.
All right so I'll go through and do the rest of these
and it's probably easiest if you did have all this written down on a piece of paper like I've got and
then you can cross off each path as you've done it, which will make it a lot simpler.
When you think you're done with all of your paths, you can press Play and then switch back into the Scene view
and you'll be able to see those paths.
So they're drawn out where you've created a link and you can see them there.
Now if you zoom in a little bit closer, the line or the edge has a blue mark at the end of it.
So that shows you the direction it's going in.
In this case, you can see that there's a blue mark on both ends of that line.
So that means you can travel back and forward along it.
Now our only unidirectional one at the moment, if
I come around here, is this line here and you can see there's
(I hope you can see, it's quite small isn't it! Let me move up...)
So there it's got a bit of blue
and at the other end, it's got no blue which means it's traveling in this direction
in our unidirection.
So if our tank ends up down here, the only way it will be able to get back to anywhere over here is to
go around this shed or whatever it is.
Ok, so now we have our waypoints,
we just have to let our tank know about them.
We'll create some driving code for the tank.
Go into 'Create > C# Script' and we'll call this FollowPath and this code is based on the
MoveLocal code that we've used before.
So, in here we're going to add some code.
I'll put it all in at once and then go through it with you.
Ok.
So here it is. Like before, we have a goal, but it's not exposed this time because we're not passing the
goal through as something that the NPC can grab hold of.
The goal will come from our A* algorithm.
Next we have the usual suspects.
We've got our speed, accuracy and rotational speed, so we need those values again.
After that, we'll need a public-exposed value for WPManager because the WPManager holds all of the
waypoints and the graph information and the NPC needs to know about that.
So we'll pass that through to this code in the Inspector. Next I'm creating some local values,
so a 'wps' here, which will grab hold of all the waypoints from the manager and then we've got a
GameObject representing the current node that we're trying to get to and that, I guess essentially, is our goal
at any particular time.
After that there's an int called currentWP.
Now this is the index of the waypoint along the path that we're following.
So if we're going along a path and let's say there's three waypoints in it, then the first waypoint
would be 0,
the next will be 1 and the next will be 2.
So this is just to keep track of how we've moved along the path that the A* algorithm has calculated
for us. It doesn't have anything to do with the waypoint's position
in our waypoint array.
So it's a completely different thing.
Now after that, I've got Graph declared as well
and these things, this 'wps' and 'Graph' is just to make our code a little bit shorter later on and you'll
see why immediately because in Start is where I set them up.
If I didn't have these two things we'd have to type this code in each
time we wanted to grab hold of something from the waypoint manager.
So it's much easier just to assign it into these variables here where we can grab it.
Next, we need to set the current node which is this game object up here which does point to the physical
node, the physical game object sphere that's in our world.
This here is set to 7 in this case because my tank (if we have a look here) is near 7.
Actually it's NOT near 7, it WAS near 7, it's near 1 now.
My waypoints have renumbered.
So let's just change that to 0 because for waypoint 1 in the array, we're positioned at 0.
So whatever waypoint your tank is near, that's what you want for your start,
so it has some kind of a reference as to where it currently is and then how it's going to calculate
how it moves through the A* algorithm.
So that's the start.
Now after that there's two functions that I'm going to come back to...let's go down here.
Now in the LateUpdate there is
first of all an 'if' statement asking us if the path length from our graph (so
if(g.getPathLength() == 0)
which is essentially saying there is no path length, or the current waypoint index is equal to the path
length.
If you've got a path with 3 nodes in it and you're up to the third node and your path length would
then be 3 as well
because it's got three things in it.
If these two are the same, it means you're at the end.
So if you've got an empty path or you're at the end of the path, then just return.
You don't want to keep moving towards any goal because there is no goal.
After that we set the current node to get the path point at the current waypoint value.
So if we're moving along a path and we're up to say position number 3, then we say we want the third
node along this path and it will give us the physical node that we need to be heading towards here.
After that, we've got a very familiar-looking 'if' statement, which is testing our accuracy.
So if the distance between the tank (which is this transform.position) and the point at the current
waypoint is less than our accuracy, then we're close enough to have been hitting our waypoint, just
like the other algorithms we've already written.
In this case, we just increment the current count along our path and this will allow us to calculate
the next point and head off towards the next point.
Next, we're doing another test to ensure that we haven't hit the end of the path (because this code up
here might mean that we've hit the end of the path) then we can move our tank forward and we're moving the
tank using the exact same code (which is this here) that you'll find that we developed in our MoveLocal
script previously for moving and turning towards a point.
So this is exactly the same
and the goal I'm just setting to be equal to the transform of the current sphere that is at position
'currentWP' in the path.
So exactly the same code, same sort of movement.
All we're doing is now following a path given to us by waypoints rather than us giving the agent
a position to go to because it's following something around on the map.
Lastly (and because I'm running out of time in this 20 minute video) you need to add these two public
functions which I'll show you how to use in the next lecture.
They are public functions that could be run outside, so we will connect buttons on the screen up to
these.
What they're doing is running the A* algorithm, so this is the bit doing all of the work.
If we want to go to the helipad, then the helipad is at waypoint 2.
I've still got my old waypoint systems in here. Waypoint 2 is going to be waypoint 1 in the array because
remember arrays start counting at zero.
And the Ruin is waypoint 7 for me, which would be 6 in the array there.
So it takes the current node that you're at, the destination and runs it through the A* algorithm which
will give you the path that is now used in LateUpdate. After each one of the
A* calls, make sure you set your waypoint counter back to 0, so that you can start at point 0
on the map and then head through.
So that's all the code for FollowPath. Save that and I'll catch up with you in the next lecture, where we'll
implement this with some buttons.