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) );