BackStabbing (Fun with Dot Product)

[PrimalLove]

So lets say you want to determine if a player is behind another player or monster. How would you do this? Well we have to take two equal vector lengths and find the relationship between them. We can do this with something called a Dot Product.

A Dot Product is an algebraic operation that takes two equal-length sequences of numbers and returns a single number. So what does this formula look like?

In Geometry/Trigonometry it looks like this:

A.B = |A| * |B| * cos(theta) : theta is the angle between the two points. //Fixed to lower confusion thanks Hypersonic

This is fine, but more computationally expensive for computer programming languages. We need a more algebraic expression of this. Luckily we have one.

A.B = A.x * B.x + A.y * B.y + A.z * B.z

So there you have it! How to calculate the dot product in a programming language using linear algebra!
Dot Products are used extensively in the Quake Engine Source Code. It is just that you never really see it. But without it quake wouldn't be possible.

But how do we use this to figure out if we are behind a monster?

Well before I mentioned that it returns a single integer. Depending on the number it returns, we can determine where we are in relation to the other vector. For instance, lets say we have the attacker with a view vector (direction he/she is pointing) as V1. And lets say the victim has a view vector of V2. We use the Dot Product to figure out the relationship. If it returns a value of 1 it means we are directly in front of the victim. This is not going to give us a backstab. Likewise if we get a return of 0. This is perpendicular to the victim (To his side). This is also not good enough to be a back stab. However, if we get a result of -1, this is indeed behind the victim and thus we can get a backstab result! The math is self explanatory. But here this is a picture to help visualize it.



So now that we have a better understanding of Dot Product lets make a function for one we can use in qc.

float (vector from, vector to) Dot =
{
	return from_x * to_x + from_y * to_y + from_z * to_z;
};

Ok, you can place that in weapons.qc near the top if you'd like. Now to put it to good use. Scroll down to the W_FireAxe routine. We will be placing this yellow highlighted code into the function:

if (trace_ent.takedamage)
	{
		trace_ent.axhitme = 1;
		SpawnBlood (org, '0 0 0', 20);
                [COLOR="Lime"]// First we need to set view vectors for our trace_ent[/COLOR]
		[COLOR="Lime"]//If the trace_ent is a monster we will use angles instead of v_angles as monster entities do not utilize v_angles only clients[/COLOR]
                [COLOR="Yellow"]if (trace_ent.flags & FL_MONSTER) 
                makevectors(trace_ent.angles);
               else
                makevectors(trace_ent.v_angle);[/COLOR]
                [COLOR="lime"]// Now lets set the view vector. [/COLOR]
		[COLOR="yellow"]def = -v_forward;[/COLOR]
                [COLOR="Lime"]// Now lets make new view vectors for the attacker(self)[/COLOR]
		[COLOR="Yellow"]makevectors(self.v_angle);[/COLOR]
                
[COLOR="Lime"] // Now lets calculate the Dot Product and if it is less than -.05 we will do a kill shot to the victim. Note here that I used -0.5 and not -1. The reason for using < -0.5 is because this gives you some wiggle room in where you can hit the target from behind. Otherwise you'd always have to be directly behind the target to get the kill. [/COLOR]
		[COLOR="yellow"]if (Dot(v_forward, def) < -0.5)
		T_Damage (trace_ent, self, self, [COLOR="lime"]trace_ent.health[/COLOR]);[/COLOR]
		else
		T_Damage (trace_ent, self, self, 20);
	}

And there you have it! Compile and if you can sneak up on an enemy from behind you will get a instant kill shot with the axe. Of course this probably shouldn't happen for Shamblers so you might want to tweak it. Now you understand Dot Product and a cool way to utilize it in qc. Have fun.

[wicked_lord]

Ok, tried to read this post. I'm lost. Good job though, I think? lol

[PrimalLove]

@wicked_lord

Lol! Thanks! Um.. Basically it lets you kill enemies from behind with one shot. Think the spy from Team Fortress. He can kill instantly from behind. This is the same thing. Just the math behind it.

[xaGe]

This sounds familiar somehow.. Hmmm. Part of your collaboration with Cobalt? I know he has added this to TBC as well.

[PrimalLove]

@xaGe

It's mostly about Dot Product. Nothing to do with any collaboration per say. But yes, I did help with implementing this code with additional code that Cobalt uses in CreepCam and His TBC mod.

[wicked_lord]

@wicked_lord

Lol! Thanks! Um.. Basically it lets you kill enemies from behind with one shot. Think the spy from Team Fortress. He can kill instantly from behind. This is the same thing. Just the math behind it.

Ahh ok, i should know this, I play TF2 quite often.

[Hypersonic]

The vector magnitudes don't need to be the same to get useful information from dotproduct. Also I wouldn't use the symbol x for multiply, people might think is means crossproduct. I admit mag(a)*mag(b)*cos(angle) isn't a good choice for programming, but you can use it for programming. Programming languages do have trig functions. The summing the multiplications of the corresponding components probably uses less CPU cycles, however.

Perhaps instead of makevectors(trace_ent.angles); you meant makevectors(trace_ent.v_angle); as the direction that target is facing is important. Also I'd just say def = v_forward;
Then if the dot is positive it is a backstab (you're facing the same direction as the target) Otherwise it's not.

Here's how TFS did it, from their 2.5 source code release back in 1997

//tfort.qc

// Return the crossproduct of 2 vectors
float(vector veca, vector vecb) crossproduct =
{
	local float result;

	result = (veca_x * vecb_y) - (vecb_x * veca_y);
	return result;
};

the function they call crossproduct actually only yields the z component of the crossproduct (crossproduct is supposed to yield an entire vector.)

//weapon.qc, function W_FireAxe

// Check direction of Attack
			makevectors(trace_ent.v_angle);
			def = v_right;
			if (self.classname == "player")
				makevectors(self.v_angle);
			else
				makevectors(self.angles);

			// Backstab
			if ((crossproduct(def,v_forward) * '0 0 1') > 0) {
				deathmsg = DMSG_BACKSTAB;

1st parameter to crossproduct:
a vector that points to the right of where the target is facing (this is unaffected by the target's pitch angle)

2nd parameter to crossproduct:
a vector that points in the same direction as the attacker

This produces a vector perpendicular to both vectors, direction using the right hand rule. If you're facing the same direction as the target the resulting vector points up. If you're facing the opposite direction as the target the resulting vector points down.

Their crossproduct function only yields the z component of this vector, a float. If the z component is > 0 then it is a backstab.

The float * '0 0 1' part doesn't really make sense, but at the same time it doesn't seem to break the logic either for some reason.

[PrimalLove]

The vector magnitudes don't need to be the same to get useful information from dotproduct. Also I wouldn't use the symbol x for multiply, people might think is means crossproduct. I admit mag(a)*mag(b)*cos(angle) isn't a good choice for programming, but you can use it for programming. Programming languages do have trig functions. The summing the multiplications of the corresponding components probably uses less CPU cycles, however. Also I left a wiki link for those to do more research which would help to eliminate confusion.

I am aware of this. This is a limited scope and a small introduction to the dot product used in a specific case for the purpose of adapting it for detecting a backstab. Yes I realize using a X is confusing. I'll change it. Thanks The computational expense makes the trigonometric function highly wasteful. Yes I shouldn't have given the impression that they are never used.

And no, I did not mean (trace_ent.v_angle) because this tutorial focused more on monsters and they do not use v_angle which is the angle the player is facing with regard to an input device like the mouse. In quake for monsters you need to use .angles. So as you can see in the TF example it uses it in both cases.

if (self.classname == "player")
				makevectors(self.v_angle);
			else
				makevectors(self.angles);

Because it uses v_angle if its a player which makes sense because those are specific to the client/player and angles for a case where the self is not a player (a bot). I should have used both in my example to be more complete.

if (trace_ent.flags & FL_MONSTER)
makevectors(trace_ent.angles);
else
makevectors(trace_ent.v_angle);

You can of course use crossproduct to accomplish the same thing. Tho crossproduct is mostly utilized for view frustum calculations (atleast in game engines) and wasn't the focus of the post. Also the original function they used to calculate crossproduct did not include the z and since z isn't a major factor to be considered they use '0 0 1' Which is just the z vector for both the attacker and the victim.

Thanks for your feedback. Made changes to first post.

[Hypersonic]

Oh ya, I wasn't thinking about monsters. I don't know why iDSoftware never gave monsters v_angle so they can pitch as well.

"Also the original function they used to calculate crossproduct did not include the z and since z isn't a major factor to be considered"
They did not use z as parameters to the crossproduct function, however a crossproduct function returns a vector perpendicular to both input vectors, and this resulting vector will have a z component. Now their crossproduct function only returns the z component of the resulting vector, rather than all 3 components which would be an entire vector.

"they use '0 0 1' Which is just the z vector for both the attacker and the victim."
The thing is they multiply a scalar with a vector, not a vector with a vector. If that results in a vector then what does vector > 0 mean? Perhaps it compares the only non-zero component? If that results in a float then float > 0 does make sense. It seems to me that they forgot their crossproduct function only returned the z compononent, because * '0 0 1' would make sense if it returned an entire vector.

[PrimalLove]

I am not clear why they did it that way. They could have just used (crossproduct(def,v_forward)) > 0) and got the same result.

[Hypersonic]

Ya, the '0 0 1' vector doesn't make sense. Even if you could multiply 2 vectors together all that would do is make x and y components 0 with z unchanged. Scaling a vector with a float just changes the mag and possibly reverse the dir of a vector, but what does vect > 0 mean? UPDATE: unless they thought crossproduct returned a vector and * meant dot product, in that case it would make sense.

Someone not knowing how this particular crossproduct function was defined (thinking it returns a vector) might attempt something like

local	vector	temp;
temp = crossproduct(def,v_forward);	//shouldn't work, trying to assigned a vector to a float
if (temp_z > 0) {deathmsg = deathmsg = DMSG_BACKSTAB;

Prozac CustomTF (which is based on CustomTF which in turn is based on the TFS 2.5 code) changes the backstabbing formula
QuakeForge / Prozac CustomTF for qfcc / [08a9c7] /weapons.qc

boolean (boolean strict) is_backstab =
{
	local	float	d;
	local	vector	dir;

	makevectors (trace_ent.angles);

	dir = trace_ent.origin - self.origin;

	dir.z *= 0.75; // hack

	d = normalize (dir) * v_forward;

	if (d < 0.3)
		return FALSE;

	if (!strict)
		return TRUE;

The key equation is here is:
d = normalize (dir) * v_forward;

normalize (dir) is attacker origin to attackee origin (unit vector)
v_forward is the attackee facing direction (unit vector)

Interesting that the facing direction of the attacker doesn't matter, but we already know that the target has been hit, I guess they don't care if the knife hits with a direct blow or a glancing blow.

What does the * operator mean with vectors on both sides of it? This function assumes the result is a float, so I'm guessing in that case it means dot product (unique to Prozac QC compiler?) So apparently with a dot of over 0.3 it's a backstab. strict was set true so the rest of the function does nothing.

[Hypersonic]

Wow, I didn't know dot product was already a built-in QC function. Check out this engine file
https://github.com/id-Software/Quake...uake/pr_exec.c

function PR_ExecuteProgram

case OP_MUL_V:
		c->_float = a->vector[0]*b->vector[0]
				+ a->vector[1]*b->vector[1]
				+ a->vector[2]*b->vector[2];
		break;

That's the dot product. I'm guessing that this bytecode is invoked when both sides of a * is a vector.

[Cobalt]

Good point. I wonder if Spike has already put it into FTE.

Oh ya, I wasn't thinking about monsters. I don't know why iDSoftware never gave monsters v_angle so they can pitch as well.

[Spike]

c = a*b;
is equivelent to:
c = dotproduct(a,b);
where a and b are vectors.
so yeah, its a dotproduct. there's no built-in support for cross products though.

here's a handy formula:
vel = vel * (((vel * normal) * scale) * normal);
if scale is 1, and normal is the trace_plane_normal of a wall, then the resulting vel will slide along the wall. if scale is 2, then the resulting vel will bounce off the wall instead (with the same energy it initially had). values between 1 and 2 will reduce energy with each bounce (assuming gravity pulls it back towards the surface).
this allows you to do bouncy lightning beams or other such effects.

.v_angle is the player's view angle.
.angles is the (player) entity's displayed angle.
for monsters, there is no .v_angle and the .angles field can be used in its place. There is a changepitch builtin that can be used to change a monster's pitch towards an .ideal_pitch value based upon some .pitchspeed field (this is a DP extension).
There is an unfixable vanilla bug that causes models to pivot the wrong way. Thus the .angles_x value is negated. This combined with trying to stop players from looking goofy means that a player's .angles_x value is equal to the player's .v_angle_x*-0.333
There is no reason that you cannot fix up a monster's .angles_x value in some temp local for makevectors to gracefully allow monsters to aim properly while pitching.

My pourtall mod supports using some 'grabber' weapon to pick up monsters and stick them onto walls/ceilings. Once attached to a wall, they'll walk around and continue trying to hunt the player, despite walking around the wall.
This is achieved using FTE's .gravitydir field combined with some qc fixes to not assume that down is always in the -z direction, including making no assumptions about the monster's angles_x+angles_z field always being 0.

If you want to find how far to the right some object is, you can do offset_right=v_right*displacement. to determine the displacement from an offset, you can use displacement = offset_right*v_right.
to rotate a displacement around a frame of reference, you can do:
makevectors(source.v_angle);
displacement = point-source.origin;
offset_x = v_forward*displacement;
offset_y = v_right*displacement;
offset_z = v_up*displacement;
makevectors(dest.v_angle);
result = v_forward*offset_x;
result += v_right*offset_y;
result += v_up*offset_z;
result += dest.origin;
as you can see, the code above can be used to transform/attach an object to another and keep it in the same relative position despite the object its attached to rotating or moving etc. Note that it doesn't deal with the angles of the attached object - you can separately transform the forward and up vectors of the attached object, and use the vectoangles(fwd,up) builtin to determine the new angles the object should use in order to not perceivably rotate relative to the parent.
This is basically how matricies work. Somehow, it makes much more sense when expressed in terms of dotproducts.

[Hypersonic]

Regarding the handy formula, I assum vel and normal are vectors, and scale is a float:
vel = vel * (((vel * normal) * scale) * normal);

Example1:

vel is '1 0 0' and normal is '0 0 1',  Scale is 1. walking in a +x direction on a level surface.
'1 0 0' * '0 0 1' = 0	//dot, vel*normal
0 * 1 = 0		//multiply, result * scale
0 * '0 0 1' = '0 0 0'	//scale, result * normal
'1 0 0' * '0 0 0' = 0	//dot, vel * result
0			//final result

Example2:

vel is '0 0 -1' and normal is '0 0 1', scale is 2. moving in a -z direction toward a surface
'0 0 -1' * '0 0 1' = -1	//dot, vel*normal
-1 * 2 = -2		//multiply, result * scale
-2 * '0 0 1' = '0 0 -2'	//scale, result * normal
'0 0 -1' * '0 0 -2' = 2	//dot, vel * result
2			//final result

So at the end it seems to be setting a vector with the value of a float. Did I do something wrong with my math, or mis-interpret the variables or operators?


So .angle_x is model pitch, .angle_y is model yaw, and .angle_x is model roll? I wish they used the convention pitch around x,roll around y,yaw around z.

You mention unfix-able, I assume you mean there's a bug in the c code, not the qc code? So basically just don't call the unfix-able c code and make a qc code substitute for pitch control?

Wall walking sounds pretty neat. Does each ent have it's own .gravitydir value, or is that global? If each ent has their own I assume it's always in the opposite direction of the surface's normal they're walking on. If an orge fires a grenade while walking on a wall, does the grenade use the owners .gravitydir or the world's .gravitydir when falling?

So a wall walking monster's z axis is the same dir as the surfaces normal. Does this mod work only on vertical walls, or any angled wall? When orienting the monster do you initially set all 3: angle_x,angle_y,and angle_z. Or do you transform the wall relative angles to world relative angles later? Did you have to modify the wall following code as floors and ceilings are the new walls?


Dot, cross, 'matrix math' all boil down to a series of additions/subtractions & multiplications/divisions. Heck even multiplications/divisions can be boiled down to a series of additions/subtractions, and additions and subtractions are just shifting in different directions. It's good to see the boiled down versions to understand what is going on, 'matrix math' boiled down to dot products in this case. Usually x associates with right and y with forward, is this not the case with Quake1?