Difference between revisions of "Detecting units in line"

From HIVE
Jump to navigation Jump to search
m
m
 
(2 intermediate revisions by one other user not shown)
Line 3: Line 3:
 
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.
 
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===
+
=Mathematics of this algorithm=
 
Feel free to skip this paragraph over, if you don't/can't understand mathematics.
 
Feel free to skip this paragraph over, if you don't/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.
  
===Description===
+
=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.
 
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===
+
=Pseudocode for 2D=
 
<pre>
 
<pre>
 
lv_range = 10; //This is an example value, it can be set differently
 
lv_range = 10; //This is an example value, it can be set differently
Line 22: Line 22:
  
 
Pick Each Unit in lv_unitGroup
 
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
+
     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
 
     if( lv_dst < UnitGetProperty( (Picked unit), Radius) ) //in line of shot
 
         AddUnitToUnitGroup( (Picked Unit), lv_possibleTargets );
 
         AddUnitToUnitGroup( (Picked Unit), lv_possibleTargets );
Line 30: Line 32:
 
</pre>
 
</pre>
  
===Pseudocode for 3D===
+
=Pseudocode for 3D=
WIP, but it's not that much more difficult
+
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.
 +
 
 +
<pre>
 +
 
 +
//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) );
 +
</pre>
  
 
[[Category:StarCraft II]][[Category:Triggers]][[Category:Tutorials]]
 
[[Category:StarCraft II]][[Category:Triggers]][[Category:Tutorials]]

Latest revision as of 21:35, 8 April 2012

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