Godot Tutorial -- 2D Navigation and Path Following Video Lecture | Godot Game: Learn and Master - Game Development

hello this is Mike again from scratch
and welcome back to our ongoing Godot
engine tutorial series today we're going
to be looking at two of the fundamental
requirements for artificial intelligence
the first one is path following very
simple to find a path and thus follow it
a lot of paths especially in now
especially older 2-d kind of games think
space invaders have said for a Ouray I
generally just followed a predefined
path still used commonly and even up the
Triple A games today you define a pre
path a predefined path generally using a
spline of some forms and then over time
you follow it we're gonna look at that
exact process today and then we're going
to look at nav meshes navmesh is a
little bit more sophisticated basically
it's a way of scanning the scene for
where you can walk in where you can't
and then figuring out the best possible
path within that so if you're moving
around the world this is how you would
programmatically determine the best
route to take and those are the two
things we're gonna look at today once
again I'm going to assume you've watched
or read any of the prior to tour all of
the prior tutorials in this series so if
I go over something and I didn't cover I
probably covered it in the past also
there is a version of this up on game
from scratch comm a text version if you
preferred it'll also have all of the
code samples that we are going to
discuss today so if you want to head on
over to game from scratch pick tutorials
Godot engine and this is part 11 so
let's jump in go ahead and create a
project now and we shall call this 3d AI
demo and go ahead
and run oh so I'm gonna get all the
default stuff out of the way first we're
gonna create our root node
just make it a node like so we're gonna
save our scene faults fine and then
we'll set it as the oops I missed
oops uh project settings and set our
scene as active uh you've probably done
this a thousand times already so kind of
used to fit okay so first off we're
gonna bring in a game background so a
world to navigate through and this one's
gonna look somewhat familiar let's just
import the graphic sitting on my desktop
and it is called Mac level give it a
place to exist like so and run all right
so just import our level let's go ahead
and actually instantiate it so it's add
another node that's right so our
background is simply going to be a
sprite simple enough that our texture
load it to pack level like so you don't
want it centered alright so there is our
background and we'll just check
something quickly desktop II back level
is 512 by five seventy one okay so just
go ahead and set our dimensions to that
okay so let's go ahead and run it make
sure our game world is set up and going
there you go so there is the world we
are going to play in looks somewhat
familiar to you I imagined so now let's
go ahead and first set up path bindings
we just want to go to define a path on
the map and then follow it so we're
gonna need something to actually
traverse the world we'll make this off
the route actually no we won't we'll be
creating that later well create a
character later on so ultimately we need
to work with two pieces here first up is
a path to actually follow and then we've
got the path follow to D which is going
to actually do the following so let's
start off by creating our path and that
is a matter of to create a new node and
so you got the 3d and the 2d version so
we want the 2d version so path 2d just
go ahead and create one of these routed
in our scene and now you'll notice as
you added this there's a bunch of new
options in your editor so you got select
you can change the control point handles
like for Bezier curves or nice smooth
cornering you can add points you can
delete points and you can close a curve
now what we care about is adding a point
so just click that guy and now what
we're going to do is set the path for
our character to follow so we start here
and we want to go here here say here
you're here you're there so there is a
nice simple path that we are going to
want to follow now we need to create an
object that's actually going to follow
that path that is simply a matter of a
path follow 2d path of all 2d data has a
few values that are somewhat important
first off we don't care to rotate so as
we're following the path we're not going
to rotate along it so we're gonna also
zero out this rotation is applied so you
can have your object as it's going along
the path rotate with it we don't want
that in this case and the key thing is
going to be this offset this is how far
along the path to go and then you've got
other things here like you can loop your
animations etc how far had to look now
we've got this created now finally we
just need something to actually follow
that path and that will slave it to this
path fall so this is a node that's gonna
move along the world but it's not
visible so this is going to be going
like
yeah through the world as time goes on
so now we just need a parent or child an
ode to it that is visible and that would
be our games right so so now we just
need to bring a character sprite in well
just go ahead and use the icon so and
it's a little too big so we'll just
scale it by half there all right zoom in
slightly him nicely positioned there you
go so now this guy is going to follow
the path that we want and that's not
gonna do anything as of yet if I go
ahead just play this nothing so now
let's add a little bit of code to
actually handle this for us and you got
a couple of options where to put this
code I'm just gonna go ahead and add it
right into the sprite itself so let's go
up here add a new script to it and
alright what am i doing I can name it
okay
our script none of this stuff and
already we are going to just simply say
that we have fixed update functions so
it's going to get called each frame go
ahead set that is true and that's it and
our logic is going to be in the tick or
the fixed process call and that is a
matter of fixed underscore process it's
passed the Delta value so and our logic
is very very simple we get our parent
which is the table 2d node and then we
set its offset now the offset is how far
along the path you are currently moved
and we're gonna move this guy at about
50 pixels along the path each frame so
we will sorry per second so we're gonna
normalize the amount that we move we're
gonna multiply it by Delta otherwise
we're gonna move it 50 pixels per second
but we're gonna do the movement called
each update that's what I meant to say
so first thing we need to do is get our
current level along the offset like so
and simply add 50 times Delta so every
second it's going to move 50 seconds
along the offset and that's it that's
actually all we need we'll go ahead and
run this and that salutely nothing
happens okay what did I do
one second I didn't pay any attention to
the actual error that was happening my
bad
Wow the code I have on the blog is all
wrong
one second ah okay let's try it that way
and now we're gonna go ahead and run it
and hopefully have less errors and there
you go and it simply follows the path
and then when it gets to the path and it
loops and does it all over again I can
of course be controlled with that
looping value set the path it's no one's
in the path follow so if you don't want
it to loop you can change that value
right here but that's it that's all
that's a matter of creating any kind of
node can be made to follow along the
path using this simple hierarchy so
basically at the top you create your
path 2d attached to it you create the
path follow and attach to that you won't
have whatever your visible node is that
you want to be following that and that
is simple path finding now of course you
can go into our code increase our speed
a fair bit and there that's all that's
involved in path fighting very very
simple now let's look at looking and
making this a little bit more dynamic
how do we determine how to get to this
point and in order to do this we're
actually gonna use something called a
nav mattre now a nav mesh is if you can
think of it as a polygon overlay on your
level that's going to say these are the
areas where you can walk that way the
computer can figure out the best path
upon it by calculating the the quickest
route in the walkable area so first
thing we need to do is actually define
that area so let's shut this down switch
back to our scene and we don't actually
need any other so I'll get rid of that
node we just need our background like so
and now we're gonna add a new node in
here and it's called mm navigation hoody
so make this your root node like that
and now we go ahead and add another node
to that and this is the polygon instance
and this is the mesh that we were
talking about the nav mesh itself and
now we have to define this thing and
I'll show you the beginning of this
process because it's really kind of an
honest I'm not going to show you the
entire thing because it'll be very very
very boring to watch but simply what you
want to do is Mark out the areas where
you can go so we'll start by just
defining a polygon in the bounds of the
walk of
areas and that starts with that you'll
notice as we have this polygon instance
selected right here we have new tools up
here we can create and we can edit the
first thing we want to do is create and
we'll just come in here I'm gonna do
this pretty roughly just marking yeah I
want to go ahead and create it mark in
the entire walkable area very quickly
into an outline boundary like so and
done so now to the navmesh this entire
area is walkable and obviously that's
not the case we want to mask out the
areas where the character can't go and
that is also used by creating new
polygons inside unfortunately it's not
gonna prompt us if we want to create it
now and you just go around each area
that you want and create new polygons so
now you see it's blocked out so that is
an our non walkable area you just want
to repeat this process over and over I
really wish I knew what the hotkey was
to create a new polygon from scratch
because as you saw from the map there's
about twenty thirty areas I need to mask
out now you'll see this outer area this
area actually presents a little bit of a
challenge because you can't go into the
existing but you can't leave a gap so
we'll define another one here you just
want to get right along the edge like so
and close see it it's not the overlap
doesn't work so now I need to actually
come in here and get this guy so it's O
far enough that it determines that it's
unique polygons so there's no gap so
that's your challenge at those edges and
I'll show you what happens when you do
this wrong I'll actually intentionally
do one wrong and we'll see the effect on
the path finding so I'm just gonna pause
this now while I go ahead and mask in
the rest of this crap so be right back
all right all done about four minutes
later here is the end result and as you
can see we've just walked around and
done bounding polygons all around the
areas you cannot walk this is leaving us
this blue area we
you're navmesh this is the area that the
AI is gonna go oh hey I can walk here
for determining it throats and if we
just go back here so it's not selective
you can see the result so this is a
bluish area right here this is our
resulting navmesh now you'll notice I've
actually made a couple of intentional
mistakes you're seeing right here this
is little blue gap blue gap blue gap no
blue gap well the problem is well we'll
see when we get to it anyways this is
going to be a problem but as you can see
you don't have to make it this way you
just have to be very precise in your
your boundary polygons when you're
creating them but this wall things to
watch out for because it can lead to
some weird bugs on your code now
speaking of code it's time to create
some I'm going to make it so that your
guys gonna start here and then whatever
you click it's gonna show you the path
to get there in order to do this I'm
gonna want to label each one so I'm
gonna want to bring in a font quickly we
covered this in a previous tutorial I
believe it was the one on UI in themes
so if you need more both fonts go back
there windows fonts and standard warned
warning you have no rights to
redistribute this font so if you do use
a font like this in your game be sure
you have the license to use it okay so
now we have a font to work with let's
write some code and we are going to make
the code in here just attach the script
just call this nav code horrible name
but works for me alright so first things
first get rid of all the junk him gone
and him gone and alright first we're
gonna need we're gonna get that font we
just created so we'll grab it on load
I'm sorry are now ready so font you was
load and the path will be res arielle
like so and we want to be preferring
processing so set process oh sorry we
want to handle input processing
my bad input processing so that's true
and we're going to mainly call draw and
I don't know if I've covered this in the
path or past or not but you can do have
draw function in though it can be used
for drawing things like lines circles
etc on top of your image and by default
it will only be called once so the first
time you runs it will call draw but you
can call it again by calling update
manually so we're gonna be using draw to
draw our UI today we'll start with a
blank one and then we're gonna want to
process our input so input event like so
and we'll leave that blank for now to
come back to our scene we need to add
our character into it so see it's not
actually going to do anything so it
doesn't have to be parented so just make
it off the root it's a sprite user icon
again and half the size so let's grab
him and I came to the start position so
we'll be using him as just more or less
our start locations so its pivot point
is going to be the starting location for
our pathfinding and now we need to
actually add some logic so that when we
click the button we create a path and
we're going to need a couple more
variables so let's go on back so we are
going to add our path as an empty
already to start or touch or click
position
yeah that's good for now so in our input
all we want to do is check for the mouse
or touch and handle it accordingly so if
event type equal input event that Mouse
why am I not getting there we go button
then let's see if it's the right mouse
button button index equals two let's
create our path so this is the code
that's actually going to go ahead and
create the path for us the the shortest
route using the navmesh and it's very
very simple keep mine we're inside
navigation too so this is a property of
navigation two objects and as a method
called get simple path so all we wanna
do is set our path equals get simple
path and then you just pass it to vector
twos one is the where from and where to
so let's start with the where from
there's get node wrote get all right why
are you and then our second value is
where we click so I'll create a new
vector two from the event X event dot y
so those are the two values of where
it's clicked that's and I'm not getting
syntax highlighting so I've made an
error what is the error let's run it get
my error out of the way you've any
you've any where did I typo then event
event I don't see any venue oh where the
hell are you there you are
alright okay so now that should work so
this was now going to have a path of the
shortest path it's gonna be a basically
a vector array of vector two's sorry
it's gonna be an array of vector two's
each one being the position in the next
location so now we're just gonna go
ahead and actually draw those on screen
and that is in our draw method so we
just drop him down so we no longer need
the pass here and instead what we are
going to do is say if at that size so if
there is a path of any length whatsoever
now let's loop through that path so and
draw each point and we're just going to
draw we're gonna draw a string at
location it correspond to its index and
we're going to draw a circle where each
possible plot point is going to be in
our path string using our font object
and then create a new vector to of path
dot I X I dot Y was 20 so we're gonna be
slightly above it and then we're just
gonna turn our index to a string all
right and I'm plotting it just because
you don't really start at 0 for
something like this and draw a circle at
that location or draw a critical draw
circle so our call there we go and first
we need path it I is our position to
draw it at our radius 10 pixels or 20
wide and our color is going to be house
white sound like so hopefully I haven't
made any mistakes here and we are all
good so go ahead and run this and I have
made a mistake okay expect the car okay
what did I screw up that shouldn't exist
that might be it all right there we go
now if I click right click we have an
error okay why ours our error get
position in null on null instance okay
one second my bad
sprite is in the root our hierarchy
sprite is not owned by navigation it's a
peer like so two ways to deal with this
I could either make it one or I can
change the pathing and I'll just be lazy
and make it one okay so now our code
should work just fine
good all right what the hell
hmm it's still not finding it as a child
node all right
Oh sprite - you did I already use ups
right I did background my bad okay that
should do it now you're starting to
irritate me yeah where I saying this
gets called once and only once
unless you call update which of course I
didn't now that should cause it to draw
there you go we're not getting our text
this is your path and you can see here
the problem so this is the shortest path
so it goes here then here then here and
here here then here and then here is the
quickest way to get from here to this
location however if there's a gap all of
a sudden it thinks this it's the correct
path and this is one of security I
really have to watch out for that it's
very simple to fix I just want to make
sure that your your navmesh is
watertight and all you do is to come
back in here and just go you just really
want to get rid of this gap here
that's as easy as that so now I'll go
ahead and run that and it works fine now
as to why I'm not getting my labels that
is because for some strange reason my
font was named wrong I don't know why it
ended up with no name
alright I'll just delete that and we'll
bring it in again font font so I must
just not have named it here my bad I
kind of wish sucka don't gave you a few
more error messages sometimes makes this
stuff a little bit easier to track down
so now we have the right font this one
selected that's fresh yeah I don't even
care it's irritating but now I run it
we should have text now well I don't we
have text yet alright one second this is
your it alright it's not showing up in
my resources
all right there it is
those days isn't it I rent again I
really wish if it failed on this stuff
it gave you more of a warning or an
error as supposed to trust trying to
trial and error figure this stuff out
yourself there you go
typos away let's see we're doing it
again the gap over here that would again
have to be fixed but you can see is
doing the shortest possible path to the
location you need to go and that's the
essence of a navmesh very handy very
quick now let me show you one other
quick function out bit of functionality
that's built into the navmesh and that
is when you're outside of the navmesh so
let's say right here for example and you
want to calculate what the closest point
within it is that's easily done as well
let's go ahead and add the code to
handle that hopefully less typos in
errors and annoyances we're gonna add
another fly so far draw touch equals
false and we're gonna add a new variable
now called closest position inspector
I can't type today and start off at
nothing so now what we want to do is add
another event handler there mouse button
and if it is if a button equals up
button index equals 1 here we want to do
our logic for our our button so first
we're going to check to make sure that
we've done at least one path so path dot
size and if we have touch position
equals or two event x dot y so we just
want to grab the location of the touch
and now we want to draw the touch yes
and now we want to actually figure out
what that closest point is and again
this is a method of navigation 2d that
we're going to be using just like we did
with get simple path and it is called
get closest point and that is why we
need this variable earlier closest
position equals get closest
wait and who are touch position like so
and once again we need to update it
student wrong language let me just get
rid of that evil semicolon all right so
now we need to call the draw again and
now we need to actually do something in
draw to actually draw where these two
touches are very simple
so over here stroke this down and if
draw touch it's true simply draw a
circle a critical kind of doing that a
lot today sorry I just cannot talk to
type today we get ten radius and color
is green come on code and this is the
closest position ten green hopefully no
typos and that is it let's go ahead and
run that and now when you click left
with outs so if you click left on the
inside nothing's gonna happen because
you're within the navmesh what if I
click left on the outside yeah nothing's
gonna happen oh I didn't do a path sorry
my god so if I click left it's going to
give me the closest spot that's within
the navmesh
so if you want to get back within the
walking space where you need to teleport
back into a walkable area or you went
out of bounds and needed to do something
or sometimes I guess for logic you're
gonna want to find the closest boundary
or wall or whatever this gets it for you
so as you can see as we run around the
edge now you're gonna have the same
logic problem as before I haven't fixed
up these edges so right here it's gonna
find that outside edge and that
shouldn't be happening on once again and
just fix all those once and for all that
is a matter of fixing this gap here so
there is no gap
but you just don't wanna go to
or actually it's fine after you've
created it so you can't actually overlap
once it's created
you just can't well creating otherwise
it won't work okay so that's I think
this is still gapped a little bit and
okay so that should be it so now I click
inside of so our path right click
alright there's still a gap there
there's not there there you go
clicking inside of everything obviously
you're not gonna get the second point
because you're within the navmesh it's a
way to find the closest area of the
navmesh when you're outside of it is by
using that method of get closest point
there's another one also called get
closest point owner where you can
actually determine what it is that
you're clicking within when you're doing
that so quick recap the beginning part
is we looked at path finding in 2d
started by creating a path to D and then
you create a path finder and you use its
offset to determine how far along it is
and it's simply done by attaching a
miserable node on top and it will follow
along with it yep the paths follow 2d
object and then we looked at navmesh and
this is a matter of you create your
navigation 2d object and you parent to
it
navigation polygon instance which you in
turn draw to show where the walkable
areas are and aren't by creating a
sequence of polygons to cut out your
mesh like so and then you use to
navigate it let's go back to our code
you can use the simple method get simple
path which is going to in turn give you
vector to array of vector twos that
represent each point or location
alongside pehle
I'm not actually in the running
application so gives you each point
along the path like so now there is one
thing that you probably notice here is
in pac-man this actually isn't a really
good method to use because you'll notice
right here
it's literally taking the closest path
so
cutting here whereas this guy moves in
cellular units like don't don't
so your logic is going to have to be to
find the locus the closest midpoint to
translate to you're going to have to
offset your character to be appropriate
because this is going to like go right
up to the edge and the other thing that
really sucks on this setup is it is
going to no account for how big you are
so as you saw here for this gap you can
get the smallest gap if it's there you
can go through it so this path is
finding a path for anything from
anything of one pixel to a thousand
pixels in size and it does not take you
to account your character and that's a
big limitation in my opinion of
navigation 2d I don't really know how to
get around that I wish you could pass in
something about a bounding box or a
radius parameter to it so it says find
the closest path fitting this object and
I don't really know how you're going to
get around that to be honest this will
locate a path for the smallest size
possible and that's one of those things
where you probably would need to change
the code if you have a better
requirement now a lot of games you can
get away with if the path wedding is for
your character itself size everything
for your character
so if this space wasn't big enough for
your character to get through you simply
wouldn't have drawn it and you control
it then with the navmesh here so you
size your nav mesh to the actual
character you're working with but if you
have multiple characters or multiple
sizes trying to use the same nav mesh
isn't going to work because of that lack
of that one function hopefully something
that could be added pretty simply I may
actually look into adding it myself or
as possible it's built into the engine
and I just missed it completely I'm not
really sure 100% which one that is but
yeah definitely something to hopefully
have addressed or hopefully there is a
way around it and I just particularly
don't know it but that's simply it
that's that's a path following and
navmesh navigation in Godot so sorry
about my bumbling along a bit there I
have trouble thinking and typing and
reading today apparently so lots of
typos and that allows a type of hunting
so if sorry for the pauses that we had
but hopefully that all made sense this
stuff can all be used together pretty
easily to create some pretty power
full navigation and controls and a I
fake AI it cetera in your game I hope
you enjoyed that stay tuned for the next
part thank you very much
bye