Difference between revisions of "Detecting units in line"

From HIVE
Jump to navigation Jump to search
(→‎Mathematics of this algorithm: fixed links to wiki)
Line 5: Line 5:
 
===Mathematics of this algorithm===
 
===Mathematics of this algorithm===
 
Feel free to skip this paragraph over, if you don't want/can't understand mathematics.
 
Feel free to skip this paragraph over, if you don't want/can't understand mathematics.
This algorithm uses [[http://en.wikipedia.org/wiki/Vector_projection|vector projection]] and [[http://en.wikipedia.org/wiki/Distance_from_a_point_to_a_line|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.
+
This algorithm uses [[http://en.wikipedia.org/wiki/Vector_projection vector projection]] and [[http://en.wikipedia.org/wiki/Distance_from_a_point_to_a_line 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.
 
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.
  

Revision as of 09:43, 13 May 2011

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

You may have heard about a so-called traceline algorithm, don't use it, it is inefficient and ugly. 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 want/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