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_dst = ABS ( X of (Picked unit)*lv_x1     +   Y of (Picked Unit)*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

WIP, but it's not that much more difficult