This video could have been in chapter one
of the Nature of Code playlist.
Because it is about a specific piece of vector mathematics,
the dot product, and a concept known as scalar projection.
However, it is here in this section of the Nature of Code,
because I eventually want to make this example.
This is crowd path following, a demonstration of one
of the combined behaviors in Craig Reynolds' Steering
Behaviors for Autonomous Characters paper from 1999.
And in order to make this example,
I, first, just need to work out path following itself with one
little following the path.
And in order to figure out path following,
I need to understand the concept of scalar projection.
Scalar projection is actually a foundational concept for three
of these behaviors, containment, wall following,
and path following.
I hope I can eventually make a video on each of those.
They're all super interesting on their own,
but I'm going to focus just on the concept of scale
of projection and lead it into path following.
So what is scalar projection in the first place?
Scalar projection is a concept that applies
when you have two vectors.
Here, I have vectors A and B.
Projections are things I've covered before, and, in fact,
I did a whole video on how to render
3D geometry in a 2D canvas with the concept of projection.
And here, we've actually got a simpler scenario.
Let's say, there's a light source up here.
You could imagine a shadow being cast of the vector A
onto the vector B. This blue vector
is then the vector projection of A onto B.
It's magnitude or its length is the scalar projection.
I may not have drawn this perfectly, by the way,
but this is a right angle here.
This vector here pointing up is known as the normal.
It's the normal to this vector B.
It's perpendicular at this point,
so I'll get to why I want this value in a moment.
But let's just say, right now, I want
to know the scalar projection.
What is the length of this vector?
How do I calculate that?
Let's say, I make this the angle theta.
Well, if you recall from chapter three,
and trigonometry, I could say that cosine of theta
equals adjacent.
Oh, look, the scalar projection.
I'll call that SP divided by the magnitude or length of vector
A. I don't recall, whether I specifically mentioned this,
but you can refer to a vectors magnitude
with these two pipe or line--
what do you call these?
These little symbols next to the A.
Another way of writing this is scalar projection
equals the magnitude of vector A times cosine of that angle.
Do you remember?
It was just about 45 minutes ago, but hopefully,
just a few minutes for you.
Because I've been trying to figure this out for a while.
I mentioned the product.
Why did I mention the product?
Again, what am I trying to solve for?
The scalar projection.
I know the magnitude of vector A. I made that vector up.
I know the-- oh, I don't know that angle.
I'd have to figure out that angle.
How do I figure out the angle between vector A and vector B?
A ha, the dot product is a mathematical operation
between two vectors typically referenced with a dot,
and it's the key to unlocking the angle between two vectors.
Now, I could possibly go and make a whole video
just about how to calculate the angle between two vectors,
and key five actually has an angle between function, which
will just give you the angle between two vectors using
the dot product.
But for our purposes here, I think
the thing that's most useful is for me to define how it
is you calculate the product.
The product of A dot B equals the magnitude
of vector A times the magnitude of vector B times
cosine of the angle between the vectors.
I just want to note that this looks really, really
similar to this right here.
The only thing that's different is that the magnitude of B
is missing from here.
Well, that might just may be a unit vector.
Then its length would be 1, so this
is the dot product between A and B, if B is a unit vector.
The scalar projection equals A dot B if B is a unit vector.
Well, any vector, I could just call normalize on.
But, aren't you just going in circles here?
Because, now, if I calculate this product between A and B,
I mean, I've got the magnitude of both vectors.
But I don't have that angle.
Well, guess what?
There's an entire other formula to calculate
the dot product of two vectors that doesn't involve the angle.
It's equivalent you will get the same result as this,
but you don't need the angle.
Therefore, you could solve for the angle.
Let me divide A and B into its components.
I can represent the vector A as A sub X,
sub Y. I can represent the vector B as B sub X, B sub
Y. The dot product of A dot B also
equals the X component of A times the X component of B
plus the Y component of A times the Y component of B.
And if I started with these two vectors,
I could just normalize B and then
compute the product this way.
And I have the scalar projection.
If you want a little exercise to yourself,
you could also now work out the math
for how you would calculate the angle between two vectors
by knowing that these two equations are
equal to each other.
Again, you don't need to, because there's
the P5 angle between function that does that math.
But you could.
Let's see what this looks like in code,
so I'm going to start with something that closely mirrors
what I've drawn over here.
I have two vectors, A and B. And I've
picked somewhat arbitrary numbers for them,
but I'm trying to match the visual to what
I have on the board
I'm drawing each vector as a line
that emanates from an arbitrary position, 100, 200,
in the canvas.
Now, what I'd like to do is draw this blue vector.
So first, let me try calculating the scalar projection.
So I've written a function, the scalar projection
of two vectors, A and B, which equals
the vector A dot the vector B, if B is a unit vector.
So I can say B dot normalize return A dot B. Let's just take
a look at this for a moment.
It's A dot, dot B. We actually have a function named dot.
We get to write the dot and have the word dot.
It's so much dot.
Now, let me call that function with A and B. Now,
I have to be careful here, because this function is
altering the vector B. It's normalizing it,
so is it better for me to make a copy of it in the function
or to call it with making a copy here?
I think I'll make a copy in the function.
Because that way, whoever is calling
the function doesn't have to worry.
The function will protect you from yourself,
so I'll write it out as one line.
Copy the vector, normalize it, and then return A dot
the copy of B.
So that's the scalar projection, but I kind of
want to see just visually, this vector projection.
So what do I need to do?
I could just take, oh, that vector B, make a copy of it,
and then said it's magnitude to the scalar projection.
Maybe I should make that function
be the vector projection.
In other words, take the vector B. Make a copy of it.
Normalize it.
Calculate A dot B to get this scalar projection length,
and then take that normalized B. And set its length to that.
Now, I've got this blue vector.
Let's see if we got it right.
Calculate the vector projection of A and B,
And then draw that, as a line, emanating
from that same position.
Oh, let me make it blue.
Drum roll, please.
[DRUM ROLL]
I see the blue line there, but I've got an error.
Oh, whoops.
I forgot that I left this function call down here.
I kind of want to double the thickness of everything
to make it a little easier for you to see.
Let me also add a little point here at the end, which I think
would be useful to see.
I'll show you why in a minute.
There we go.
I've tweaked it a little bit and drawn all the elements
I want to draw.
If I have this vector A and vector B,
I can now find all of the points that make up this full triangle
here, this point that I'm calling pause,
the endpoint of this vector, and now, this
point here, which is the endpoint of the vector
projection.
Why do I care so much about this?
I'm so afraid to erase this, because it's all this stuff
that I've worked out.
But I need to draw from a blank slate.
In the next video, I want to look at path following.
Let's say, this line is my path.
Of course, I could eventually have a curved path
or a bunch of line segments.
But just for simplicity, let's think of the path as a line.
Then I've got a vehicle.
Maybe that vehicle is over here, and it's
traveling with this velocity.
Well, the path following steering behavior
is a multi-step process.
Step number one is predict a future location of the vehicle.
I could say that it's over here.
After a certain amount of time, moving at this velocity,
the vehicle will be over here.
Then look at the distance between this vehicle
and the path.
How do I define the distance between this point and a line,
right?
Have you ever spent the time, searching
online for what is the distance between a point and a line?
I've done this so many times.
Fortunately, I think I, finally, have it for the most part,
and the key is everything we just worked out
with scalar projection.
Let me show you why.
Well, I could consider this path to be a vector.
Call it B. I could consider making
a vector that points from the beginning to this path
to this point.
Call that A.
Well, the definition of the distance
between a point and a line is find the normal vector
at that line that intersects the point, right?
The normal being this perpendicular vector,
and at the end of that normal vector
is this point, which lies at the scalar projection of A onto B.
So any time I want to find the distance between a point
and a path, or a wall, or an obstacle, in some sense,
depending what the obstacle is, I could look at this scalar
projection to find the distance, the normal from that surface
to a particular point.
So coming back to here, let's say,
I'm not starting with vector A. Instead,
I'm starting with this point, and let me make that point,
where the mouse is.
Vector A is there for the mouse point minus that position.
I'm going to call B path, and then I'm
going to calculate the vector A, right here, and draw.
Now, I don't know if I need to do anything more.
Let's see if this all just still works.
Cannot read property X of undefined.
Well, I forgot I used B everywhere.
Let me change that to path.
Oh, and this has to be dot.
I always forget to write the subtract for some reason.
Look at this.
As I move the mouse around, I'm always
finding the corresponding point on the line,
even if I go back here.
I'm extending the line past.
Oh, my goodness, so the idea of the line segment is irrelevant.
It will always find the scalar projection to that vector.
I want to just comment out some of the things
that I'm drawing to just get back to the sort of scenario
that we're going to see in the next video for a moment.
So now, we can see without drawing
all that extra debugging information,
I'm just finding that projection point
onto a line from another point in the two dimensional space.
OK, I hope you found this useful and helped
you understand the concepts of both scalar
projection and the dot product.
There's, obviously, missing details there,
and I will add a bunch of links to the video's description that
go through both of these mathematical concepts.
But the code that I've written here
is everything that we need to implement containment, wall
following, and path following.
So I'm going to go ahead, and in the next video,
work on path following.