# Detecting units in line

This tutorial solves a common issue in FPS maps: detecting the first unit in a line (usually in line of a shot).

You may have heard about the traceline algorithm; it is not recommended to use traceline, as it is inefficient. This algorithm uses vectors to make the calculations much simpler.

# Mathematics of this algorithm

Feel free to skip this paragraph over, if you don't/can't understand mathematics.
This algorithm uses vector projection and distance of a point from a line. Vector projection uses the formula *A*B / |B|* for projecting vector A into vector B. We use a vector of length 1 for B, so it becomes a very simple *A*B* formula.
Distance from a point to a line is *(Px*Bx + Py*By)/|B|* for distance between point P and line with *normal* B. Again, B will have length of 1, making this a very simple formula.

# Description

The main goal of developing this algorithm was to limit calling of **Units in Range** function, because it is very slow. Therefore, a single call of this function is executed on entire area, where the shot goes. **(image will be uploaded soon)** Then, all units found by this function are compared againts the point-to-line distance formula, to see whether they are in the line or not.

# Pseudocode for 2D

lv_range = 10; //This is an example value, it can be set differently lv_attacker = (Triggering Unit); //depends on implementation lv_x1 = -Cos( Facing of lv_attacker) ); lv_y1 = Sin( Facing of lv_attacker) ); // vector perpendicular to the direction of shot lv_unitGroup = Unit in Range (lv_range/2) of Point( X of lv_attacker + lv_x1*lv_range/2,X of lv_attacker + lv_x1*lv_range/2 ); //the center is in half of the maximum distance Pick Each Unit in lv_unitGroup lv_tmpX = X of (Picked unit) - X of (lv_attacker) lv_tmpY = Y of (Picked unit) - Y of (lv_attacker) lv_dst = ABS ( lv_tmpX*lv_x1 + lv_tmpY*lv_y1 ); //distance to line calculation if( lv_dst < UnitGetProperty( (Picked unit), Radius) ) //in line of shot AddUnitToUnitGroup( (Picked Unit), lv_possibleTargets ); lv_target = UnitFromGroupClosestToPoint( lv_possibleTargets, Position of(attacker) );

# Pseudocode for 3D

To make the algorithm work in 3D, simply add height check. There is no point making 3D version for units, this example will use camera values to determine the coordinates.

//position of camera eye lv_x1 = X of (Camera target) + Sin( camera yaw )*Cos( camera pitch )*(Distance of camera) lv_y1 = Y of (Camera target) + Cos( camera yaw )*Cos( camera pitch )*(Distance of camera) lv_z1 = Height of (camera target) + Sin(camera pitch)*(Distance of camera) + (Camera height offset) // vector perpendicular to the direction of shot lv_dx = -Cos( camera yaw ); lv_dy = Sin( camera yaw ); //we are tracking FROM eye TOWARDS target -> the angle needs to be reversed lv_tan = Tan( 90 - camera pitch ); lv_range = 10 * Cos(camera pitch) + 1; //10 is an example for maximum shot range, 1 is a reserve. lv_unitGroup = Unit in Range (lv_range/2) of Point( X of lv_attacker + lv_x1*lv_range/2,X of lv_attacker + lv_x1*lv_range/2 ); Pick Each Unit in lv_unitGroup lv_tmpX = X of (Picked unit) - lv_x1 lv_tmpY = Y of (Picked unit) - lv_x2 // HH is height of unit - either create a lookup table for different units, or use units of same constant height lv_tmpZ = Height of (position of picked unit) + Flying height of (picked unit) + HH/2 lv_dst = ABS ( lv_tmpX*lv_x1 + lv_tmpY*lv_y1 ); //distance to line calculation - 2D lv_heightDif = ABS( lv_tmpZ - lv_z1 - lv_tan*(distance between (x1,y1) and position of picked unit ) ) if( lv_dst < UnitGetProperty( (Picked unit), Radius) && //in line of shot lv_heigthDif < HH ) //in proper height AddUnitToUnitGroup( (Picked Unit), lv_possibleTargets ); lv_target = UnitFromGroupClosestToPoint( lv_possibleTargets, Position of(attacker) );