Avoiding other units without using pathfinding

Started by
25 comments, last by bot_hot_dog 1 week, 4 days ago

JoeJ I understand why you want to add a vector to a point, that’s how you move a character. When you multiply a vector ( is it a unit vector in this case? )with a float you do that because you want to set the amplitude ( amount)of movement. I also understand that when you perform a point minus point operation you end up with a vector (not a unit vector in this case ) . However I have no clue about the purpose of all the other operations in your class (dot and all the others).

My project`s facebook page is “DreamLand Page”

Advertisement

Calin said:
move a character. When you multiply a vector ( is it a unit vector in this case? )

No. Velocity is a vector where it's magnitude defines speed. So a magnitude of one would be a rare coincidence.
For most cases a vector just means a ‘single’ number, but with multiple dimensions.
The magnitude then is often used to reduce it to a single dimension. For example, speed is a single value of only one dimension. So velocity.Length() tells us this single value, removing the information of direction which the velocity vector has as well.

Calin said:
When you multiply a vector to a float first you do that because you want to set the amplitude ( amount)of movement.

Not sure what you mean with ‘amplitude’, but likely ‘magnitude’, which tells the length of a vector, and it is always a positive number.

So if we do: pos += velocity * deltatime, we add to the position:
The velocity times a given duration of time, assuming velocity remains constant during that duration.
It's the same as: pos.x += vel.x * dt; pos.y += vel.y * dt;
So there is no magic or new stuff at all, but we introduced some new terminology and concepts for basic math things you already know.

There is no need for unit vectors either here, which comes next…

Calin said:
However I have no clue what‘s the use of all the other operations (dot and everything else in your vector class)

Length() gives magnitude, SquaredLength() gives squared magnitude (which is often good enough but faster to compute).
To calculate the length of a vector, we use the Pythagoras formula a^2 + b^2 = c^2 of a right triangle.
We can do this because our x and y axis are perpendicular, guaranteeing a right angle between the axis.
Thus we get: x^2 + y^2 = length^2, and we need a square root to get length.

Thus, the only really new stuff to you might be Dot() and Perp().

I'll do an example: Say we have some wall of a polygon shaped base for your game, and we want to resolve collision of a unit represented by a point.

Maybe after adding velocity to our blue unit it went through the wall of the base, accidentally ending up inside.
To move it outwards, we want to calculate the green vector to resolve the collision.

Basically we want to project the blue point to the line AB.

We can do this easily using the dot product:

Vec2 line = B - A;
Vec2 lineDir = line / line.Length(); // lineDir is now a unit vector, drawing in red
Vec2 diff = unit.pos - A; // drawing blue
float t = lineDir.Dot(diff); // 0.7
Vec2 projection = A + lineDir * t; // purple X

Make sure to follow the code.
Basically the dot product tells us the length of diff projected to lineDir.
So we can use the result to calculate the projected X to resolve the collision.
X is the closest point to unit.pos on the infinite line defined by A and B.

This is really important to grasp.
After using this some times for all kinds of geometrical problems, you should be able to write such code without looking up resources.

It's also an example of why unit vectors are nice sometimes.
But it's not really needed. I could optimize the code this way:

Vec2 line = B - A;
Vec2 diff = unit.pos - A;
float t = line.Dot(diff) / line.SquaredLength();
Vec2 projection = A + line * t;

That's faster because i don't need a square root.
But it's also less intuitive. To learn the math, just use unit vectors where it feels convenient.

Ok, so now we have resolved the collision using the super power of the dot product.
But maybe we only want to know how far the unit is behind the wall.
To calculate this, we could just calculate the green vector and it's length:

Vec2 resolve = projection - unit.pos; // the green vector
float penetration = resolve.Length(); // how much do we penetrate the wall

But there is a problem here:
We would get a positive penetration value also if our unit would be outside the base.
Actually we do not know if the unit is in front or back of the wall.
So we did not actually calculate a signed penetration value, but just an unsigned distance from the wall, not telling if we are inside or outside.

To solve this, we can use the Perp() function, which gives a perpendicular vector:

Vec2 perp = lineDir.Perp(); // because lineDir is a unit vector, perp will be unit too. drawn in green

float signedAndCorrectPenetration = perp.Dot(diff); // same value as before, but now it's signed. If it's negative we are behind the wall, if it's positive we are infront. (Or vice versa - i'd need to compile and test to figure out)

Notice: We do another projection, but this time to the green and perpendicular direction, to tell us if we are inside or outside.

We could now calculate the vector to resolve the collision also this way:

Vec2 resolve = perp * -signedAndCorrectPenetration; // (not sure about the sign - need to try)
unit.pos += resolve; // done :)

That's the things you need to know about vectors to tackle geometrical problems.

It might take you some time, but after using it a few times it becomes second nature quickly.
And after that, you have learned a whole lot about math, because:

The Perp() is used in 2D for the same things we use the Cross Product in 3D. (Cross product needs 3 points or two vectors to define a plane, while in 2D we need only two points or one vector to define a line.)

The red and green arrows define orthogonal basis vectors as used in transformation matrices.
So if you understand this, you also understand matrix multiplication and how this can do rotations.
You only need to realize it's all the same thing: Dot products and orthogonal (right angled) basis vectors.

The lineDir is ‘tangent’ to the line, while the ‘perp’ is normal to the line.
Which we can use as a foundation to jump from the just learned linear algebra basics to calculus.
(well, afaict at least, since i'm amateur with math myself ; )

Amplitude is a Romanian only word, sorry. Magnitude is the correct term.
The amount of code in your examples is so small I guess that’s basic stuff for someone who has got a hang of it.

My project`s facebook page is “DreamLand Page”

it might work like this. you start with a camera, then from the camera you het a hit result, and based on the hit result you have a line. if you get the length of the line then you can make multiple cameras and multiple hit results just point the camera in different directions offset at an angle from each other.

then move forward and measure the lengths of the hit results and go to the longest hit result.

see my unreal engine blueprint shows how i get the length of the hit result, right click image and open in new tab to see in fullscreen:

following my previous post logic i got this from somebody else:

you can use get actor forward vector.if that camera is a component you can use get forward vector (get forward vector,without actor version ).
For offsetting the vector there’s a “rotate vector” node.you can use it to easily offset/rotate a vector (by degrees).

bot_hot_dog said:

following my previous post logic i got this from somebody else:

you can use get actor forward vector.if that camera is a component you can use get forward vector (get forward vector,without actor version ).
For offsetting the vector there’s a “rotate vector” node.you can use it to easily offset/rotate a vector (by degrees).

Sounds you propose to trace random rays to sense the environment. But that's really inefficient, even if you would implement it with C++ instead blueprints.

I guess you could define a bounding box around the character, then query all actors in the box. Should be faster than tracing a single ray and much more robust. Then you can just iterate nearby actors to model some behavior.

A similar thing is ‘trigger volumes’. If some actor enters the (invisible) box placed in front of a door, the door can open automatically for example.

Idk how such things are called in UE, but they are surely available also for blueprints.

I made the blueprint for unreal to shoot at different spots and find the distance of each hit, right click image and open in new tab to see the full image:

placing a trigger volume in front of the player would work too but it would be a poor judge of distance.

The blueprint i showed shows only 2 hits, but it could be 360 degrees or 360 sequences, incrementing rotate vector by 1 each sequence on the z axis which for me is the yaw. Yaw is rotation around the Z axis in unreal.

bot_hot_dog said:
placing a trigger volume in front of the player would work too but it would be a poor judge of distance.

The idea is to find the set of close NPCs quickly, then calculating their distance or angle is trivial.
But you might still trace rays to them afterwards, to find out if they are actually visible or occluded.
If there are 3 close units, you trace only 3 rays vs. 360 to find them by random luck.

To find the enemy quickly using something like a trigger volume, add sphere collision and make a bunch of them and then walk around.

if an enemy touches one collision sphere then now you can see which sphere collision was touched and use that to do something?

There's no limit to the number of these sphere collisions you could make even hundreds of then nested all around the player.

bot_hot_dog said:
if an enemy touches one collision sphere then now you can see which sphere collision was touched and use that to do something?

Yes.

bot_hot_dog said:
There's no limit to the number of these sphere collisions you could make even hundreds of then nested all around the player.

But still: Each sphere will do it's own traversal of spatial accelerations structures, and if there is no AS it will iterate over all enemies to find those who intersect. So it's better to use just one large sphere instead multiple small ones.

As the game gets larger and there is more stuff around, such optimizations can make a big difference.

Advertisement