IsUnitInCone (with Collision)

[Zwiebelchen]

Any idea on how to do this efficiently?

The best simple approach to cone calculation is obviously enumerating units within a circle around the unit and then remove all that are not within the opening angle of the cone. But this doesn't consider collision size of these units.

I basically want even those units to be considered that just touch the cone area with their collision.

I attached a sketch.

 

[GhostWolf]

Cheeky way: make your angle bigger.

Cheekier way: offset the cone's side segments outwards.

Cheekiest way: check the signed distance between the unit positions and the cone line segments. +/- mean inside/outside or the inverse depending on your coordinate system. If it's inside for all 3 segments, the unit is inside the cone. Otherwise, if it's outside but the absolute distance to any of the segments is less than the unit's collision radius, the unit is partially in the cone.

(if the outer part is not a line but rather an arc, do a point-point distance check and compare to both radiuses)

For reference Distance from a point to a line - Wikipedia

 

[Zwiebelchen]

Did it by adding two line intersection checks to the regular cone logic.

Basically my idea was its either inside the cone or the collision circle of the unit intersects the outer two lines of the cone.

Sharing the code here if anyone is interested - for debug purposes I set the units vertex coloring to blue if the unit is not in the cone, red if the unit is completely inside the cone and green if the unit is partially inside the cone:

    function IsPointInCone takes real centerx, real centery, real face, real fov, real pointx, real pointy returns boolean
        local real angle = bj_RADTODEG*Atan2(pointy - centery, pointx - centerx)
        return not (RAbsBJ(face - angle) > (fov/2) and RAbsBJ(face - angle - 360.) > (fov/2))
    endfunction

    function IsCircleOnLine takes real cx, real cy, real radius, real p1x, real p1y, real p2x, real p2y returns boolean
        local real dx = p2x - p1x
        local real dy = p2y - p1y
        local real A = dx * dx + dy * dy
        local real B = 2 * (dx * (p1x - cx) + dy * (p1y - cy))
        local real C = (p1x - cx) * (p1x - cx) + (p1y - cy) * (p1y - cy) - radius * radius
        local real det = B * B - 4 * A * C
        if ((A <= 0.000001) or (det < 0)) then
            return false
        endif
        return true
    endfunction

    function IsUnitInCone takes real centerx, real centery, real face, real fov, real length, unit target returns boolean
        local real radius = BlzGetUnitCollisionSize(target)
        local real p2x
        local real p2y
        if not IsUnitInRangeXY(target, centerx, centery, length) then
       call SetUnitVertexColor(target, 0, 0, 255, 255)
            return false
        endif
        if IsPointInCone(centerx, centery, face, fov, GetUnitX(target), GetUnitY(target)) then
       call SetUnitVertexColor(target, 255, 0, 0, 255)
            return true
        endif
        set p2x = centerx + Cos(bj_DEGTORAD*(face - fov/2)) * length
        set p2y = centery + Sin(bj_DEGTORAD*(face - fov/2)) * length
        if IsCircleOnLine(GetUnitX(target), GetUnitY(target), radius, centerx, centery, p2x, p2y) then
       call SetUnitVertexColor(target, 0, 255, 0, 255)
            return true
        endif
        set p2x = centerx + Cos(bj_DEGTORAD*(face + fov/2)) * length
        set p2y = centery + Sin(bj_DEGTORAD*(face + fov/2)) * length
        if IsCircleOnLine(GetUnitX(target), GetUnitY(target), radius, centerx, centery, p2x, p2y) then
       call SetUnitVertexColor(target, 0, 255, 0, 255)
            return true
        endif
   call SetUnitVertexColor(target, 0, 0, 255, 255)
   return false
    endfunction

 

[chopinski]

How about something as simple as this:

function IsUnitInCone takes unit u, real x, real y, real direction, real angle returns boolean
        return Acos(Cos((Atan2(GetUnitY(u) - y, GetUnitX(u) - x)) - direction)) < angle
endfunction

To compensate for collision, just use a wider angle.

 

[GhostWolf]

Using a wider angle will work for some models, but if you think about it, it can easily miss units, especially ones close to the start of the cone, and especially if your units have varying collision circle sizes.

Gotta do the real math if you want it to always hit what it's meant to hit.

 

[AGD]

Here is one with actual collision checking

function IsUnitInSector takes unit u, real collision, real x, real y, real radius, real face, real fov returns boolean
    local real a

    if IsUnitInRangeXY(u, x, y, radius) then
        set x = GetUnitX(u) - x
        set y = GetUnitY(u) - y
        set a = Atan2(y, x)
        set fov = fov/2 + collision/SquareRoot(x*x + y*y)
        /*
        collision/SquareRoot(x*x + y*y) is a good approximation for
        the angle of the unit's center to its body with reference to
        the center of sector for relatively small collisions

        Can be replaced with a cosine law expression for better precision
        */

        return RAbsBJ(face - a) <= fov and RAbsBJ(face - a - 360.) > fov
    endif

    return false
endfunction

if IsUnitInSector(u, BlzGetUnitCollisionSize(u), centerX, centerY, radius, face, fov) then
    call BJDebugMsg("Unit is inside the sector (totally or partially)")
endif

 

[Zwiebelchen]

How about something as simple as this:

function IsUnitInCone takes unit u, real x, real y, real direction, real angle returns boolean
        return Acos(Cos((Atan2(GetUnitY(u) - y, GetUnitX(u) - x)) - direction)) < angle
endfunction

To compensate for collision, just use a wider angle.

Just using a wider angle doesn't properly catch corner cases in which the target is very close. Cone checks often fail in short distances when the cone area is still tiny.

 

[Zwiebelchen]

Here is one with actual collision checking

function IsUnitInSector takes unit u, real collision, real x, real y, real radius, real face, real fov returns boolean
    local real a

    if IsUnitInRangeXY(u, x, y, radius) then
        set x = GetUnitX(u) - x
        set y = GetUnitY(u) - y
        set a = Atan2(y, x)
        set fov = fov/2 + collision/SquareRoot(x*x + y*y)
        /*
        collision/SquareRoot(x*x + y*y) is a good approximation for
        the angle of the unit's center to its body with reference to
        the center of sector for relatively small collisions

        Can be replaced with a cosine law expression for better precision
        */

        return RAbsBJ(face - a) <= fov and RAbsBJ(face - a - 360.) > fov
    endif

    return false
endfunction

if IsUnitInSector(u, BlzGetUnitCollisionSize(u), centerX, centerY, radius, face, fov) then
    call BJDebugMsg("Unit is inside the sector (totally or partially)")
endif

Interesting solution. Its much shorter than the mathematical precise solution I posted. Ill check it out and see if its sufficient for my case.

 

[AGD]

I can't remember why I chose to use an approximation, when an exact formula is just as brief

set fov = fov/2 + Acos((1 - (collision*collision)/(2*(x*x + y*y)))

I think it's better to use this one

 

[Zwiebelchen]

I can't remember why I chose to use an approximation, when an exact formula is just as brief

set fov = fov/2 + Acos((1 - (collision*collision)/(2*(x*x + y*y)))

I think it's better to use this one

Ill do a quick comparison between yours and mine approach and if it yields the same result, ill make the switch. Thanks mate.


Edit: @AGD doesn't seem to yield the same results as my function. There must be something wrong with the formula.

 

[AGD]

@Zwiebelchen I mistakenly used 360 even tho I'm using radians. Here is the fixed version. Additional check to prevent division by 0 is also added.

    function IsUnitInSector takes unit u, real collision, real x, real y, real radius, real face, real fov returns boolean
        local real a

        if IsUnitInRangeXY(u, x, y, radius) then
            set x = GetUnitX(u) - x
            set y = GetUnitY(u) - y
            set radius = x*x + y*y

            if radius > 0. then
                set a = Atan2(y, x)
                set fov = fov/2 + Acos((1 - (collision*collision)/(2*radius)))

                return RAbsBJ(face - a) <= fov and RAbsBJ(face - a - 2.00*bj_PI) > fov
            endif

            return true
        endif

        return false
    endfunction

Btw, your current check also includes units in the borders of the cone in the opposite side of the angle, as seen on the screenshot.

Screenshot

Enumerated (yours = exclamation mark, mine = colored red)
Outside units (colored green)

Here is the Test script used

scope EnumerationTest initializer OnInit

    //==================================================================================================

    function IsUnitInSector takes unit u, real collision, real x, real y, real radius, real face, real fov returns boolean
        local real a

        if IsUnitInRangeXY(u, x, y, radius) then
            set x = GetUnitX(u) - x
            set y = GetUnitY(u) - y
            set radius = x*x + y*y

            if radius > 0. then
                set a = Atan2(y, x)
                set fov = fov/2 + Acos((1 - (collision*collision)/(2*radius)))

                return RAbsBJ(face - a) <= fov and RAbsBJ(face - a - 2.00*bj_PI) > fov
            endif

            return true
        endif

        return false
    endfunction

    //==================================================================================================

    function IsPointInCone takes real centerx, real centery, real face, real fov, real pointx, real pointy returns boolean
        local real angle = bj_RADTODEG*Atan2(pointy - centery, pointx - centerx)
        return not (RAbsBJ(face - angle) > (fov/2) and RAbsBJ(face - angle - 360.) > (fov/2))
    endfunction

    function IsCircleOnLine takes real cx, real cy, real radius, real p1x, real p1y, real p2x, real p2y returns boolean
        local real dx = p2x - p1x
        local real dy = p2y - p1y
        local real a = dx * dx + dy * dy
        local real b = 2 * (dx * (p1x - cx) + dy * (p1y - cy))
        local real c = (p1x - cx) * (p1x - cx) + (p1y - cy) * (p1y - cy) - radius * radius
        local real det = b * b - 4 * a * c
        if ((a <= 0.000001) or (det < 0)) then
            return false
        endif
        return true
    endfunction

    function IsUnitInCone takes real centerx, real centery, real face, real fov, real length, unit target returns boolean
        local real radius = BlzGetUnitCollisionSize(target)
        local real p2x
        local real p2y
        if not IsUnitInRangeXY(target, centerx, centery, length) then
            return false
        endif
        if IsPointInCone(centerx, centery, face, fov, GetUnitX(target), GetUnitY(target)) then
            return true
        endif
        set p2x = centerx + Cos(bj_DEGTORAD*(face - fov/2)) * length
        set p2y = centery + Sin(bj_DEGTORAD*(face - fov/2)) * length
        if IsCircleOnLine(GetUnitX(target), GetUnitY(target), radius, centerx, centery, p2x, p2y) then
            return true
        endif
        set p2x = centerx + Cos(bj_DEGTORAD*(face + fov/2)) * length
        set p2y = centery + Sin(bj_DEGTORAD*(face + fov/2)) * length
        if IsCircleOnLine(GetUnitX(target), GetUnitY(target), radius, centerx, centery, p2x, p2y) then
            return true
        endif
        return false
    endfunction

    private function InitEnumerationTest takes integer unitId, integer I, integer J, real spacing returns nothing
        local integer j
        local real offset = -(spacing*I*0.5)
        local unit u
        loop
            exitwhen I == 0
            set j = J
            loop
                exitwhen j == 0
                set u = CreateUnit(Player(0), unitId, I*spacing + offset, j*spacing + offset, 90.00)
                if IsUnitInSector(u, BlzGetUnitCollisionSize(u), 0, 0, 1200, bj_PI*0.25, bj_PI*0.25) then
                    call SetUnitVertexColor(u, 255, 0, 0, 255)
                else
                    call SetUnitVertexColor(u, 0, 255, 0, 255)
                endif
                if IsUnitInCone(0, 0, bj_PI*0.25*bj_RADTODEG, bj_PI*0.25*bj_RADTODEG, 1200, u) then
                    call AddSpecialEffectTarget("Abilities\\Spells\\Other\\TalkToMe\\TalkToMe.mdl", u, "overhead")
                endif
                set j = j - 1
            endloop
            set I = I - 1
        endloop
        set u = null
    endfunction

    private function OnInit takes nothing returns nothing
        call FogEnable(false)
        call FogMaskEnable(false)
        call PanCameraToTimed(0.00, 0.00, 0.00)
        call InitEnumerationTest('hpea', 30, 30, 75.00)
    endfunction

endscope

EDIT:

I realized that it's still not exact, but is so close that I didn't notice an error upon testing. This must now be the exact formula

    function IsUnitInSector takes unit u, real collision, real x, real y, real radius, real face, real fov returns boolean
        if IsUnitInRangeXY(u, x, y, radius) then
            set x = GetUnitX(u) - x
            set y = GetUnitY(u) - y
            set radius = x*x + y*y

            if radius > 0. then
                set face = face - Atan2(y, x)
                set fov = fov/2 + Asin(collision/SquareRoot(radius))

                return RAbsBJ(face) <= fov and RAbsBJ(face - 2.00*bj_PI) > fov
            endif

            return true
        endif

        return false
    endfunction

Still incorrect, see the correct formula below

 

[Zwiebelchen]

Made the switch now. Thanks for your suggestion!

 

[chopinski]

@AGD just so you know, your function do not work for the 3° and 4° quadrants of the circle (180° <= angle <= 360°).

A a visual example where face is 180° and fov is 90°

 

[AGD]

@chopinski here is the fixed version

function IsUnitInSector takes unit u, real collision, real x, real y, real radius, real face, real fov returns boolean
    if IsUnitInRangeXY(u, x, y, radius) then
        set x = GetUnitX(u) - x
        set y = GetUnitY(u) - y
        set radius = x*x + y*y

        if radius > 0. then
            set face = face - Atan2(y, x)
            set fov = fov/2 + Asin(collision/SquareRoot(radius))

            return RAbsBJ(face) <= fov or RAbsBJ(face - 2.00*bj_PI) <= fov
        endif

        return true
    endif

    return false
endfunction

 

[AutisticTenacity]

@AGD
Nearly a year late, but I'd like to point out a catastrophic fail state of your algorithm, and a different inaccuracy, via this convenient Desmos graph.
ArcDemonstration
Arcsine() becomes undefined when the collision size is larger than the distance from center - thankfully you can fix this easily because in the cases where it is undefined, it is also within the cone via its own collision size.
The inaccuracy is that it's not taking collision size into account for when it is outside of the sector radius. This is a simple fix for when your checked angle is already within the sector, but when the angle is outside of the sector you end up needing to do a distance comparison between your target's point, and a clamped point within the sector (which you need to calculate yourself with an additional bit of math).

I've also made a few optimizations to a simple angle in cone/arc to remove an additional conditional check. It works by aligning/rotating the clockwise angle to the "seam" (the point where the angle values loop around) of the angle range, so that it only requires a single check to complete, as well as covering the edge cases where the clockwise and counterclockwise angles normally cross the seam.

//anglearc is half of fov
function AngleInArc takes real checkedangle,real baseangle,real anglearc returns boolean
    return ModuloReal(checkedangle - baseangle + anglearc, bj_PI * 2) <= 2*anglearc
endfunction

And here is my version of the precise cone/sector unit enumeration, that takes into account the collision size of the unit, as well as including a minimum radius and a maximum radius of the arc. Optimized to a single trig call per unit, and no SquareRoot() calls

function GroupEnumUnitsInArcPrecise takes group g, real x, real y, real angleDir, real angleDiff, real mindist, real maxdist returns nothing
    local group g2 = CreateGroup()
    local real minsqr = mindist*mindist
    local real maxsqr = maxdist*maxdist
    local real distsqr
    local real x2
    local real y2
    local real dx
    local real dy
    local real clampedangle
    local real clampeddist
    local real clampedx
    local real clampedy
    local real anglecw = angleDir-angleDiff
    local real angleccw = angleDir+angleDiff
    local real coscw = Cos(anglecw)
    local real cosccw = Cos(angleccw)
    local real sincw = Sin(anglecw)
    local real sinccw = Sin(angleccw)
    local real cos
    local real sin
    local real tau = 2*bj_PI
    local unit selected = null
    local real size

    call GroupClear(g)

    if angleDiff > bj_PI then
        set angleDiff = bj_PI
    endif

    call GroupEnumUnitsInRange(g2,x,y,maxdist+200, null)

    loop
        set selected = FirstOfGroup(g2)
        exitwhen selected == null
        set x2 = GetUnitX(selected)
        set y2 = GetUnitY(selected)
        set dx = x2-x
        set dy = y2-y
        set distsqr = dx*dx+dy*dy
        set clampedangle = Atan2(dy,dx)

        if ModuloReal(clampedangle - anglecw, bj_PI * 2) <= 2*angleDiff then

            set size = BlzGetUnitCollisionSize(selected)
            if distsqr < (maxdist+size)*(maxdist+size) and distsqr > (mindist-size)*(mindist-size) then
                call GroupAddUnit(g,selected)
            endif

        else
          
            if ModuloReal( clampedangle - angleDir, tau) > bj_PI then
                //right clockwise side
                set cos = coscw
                set sin = sincw
            else
                //left counterclockwise side
                set cos = cosccw
                set sin = sinccw
            endif

            //distance along line
            set clampeddist = cos*(dx) + sin*(dy)

            if clampeddist > maxdist then
                set clampeddist = maxdist
            elseif clampeddist < mindist then
                set clampeddist = mindist
            endif

            set clampedx = x+clampeddist*cos
            set clampedy = y+clampeddist*sin

            if IsUnitInRangeXY(selected, clampedx, clampedy, 0.00) then
                call GroupAddUnit(g,selected)
            endif

        endif

        call GroupRemoveUnit(g2,selected)
    endloop

    call DestroyGroup(g2)
    set g2 = null
endfunction

The CreateGroup() can be optimized with a group recycler, or a reusable global temp group for the function. And the blizzard native BlzGetUnitCollisionSize(selected) can be replaced with whatever previous methods were used to get unit collision sizes, (either manually writing in hashtable entries manually, or using IsUnitInRangeXY() to binary search unit collision sizes, then adding them to the hashtable).

Edit: Realized ModuloReal() could be optimized and replaced with a specialized version, which can replace a division operation with a multiplication one, via precalculating 1/2pi, for negligible performance gains.

//Original ModuloReal, as defined in blizzard.j
function ModuloReal takes real dividend, real divisor returns real
    local real modulus = dividend - I2R(R2I(dividend / divisor)) * divisor

    // If the dividend was negative, the above modulus calculation will
    // be negative, but within (-divisor..0).  We can add (divisor) to
    // shift this result into the desired range of (0..divisor).
    if (modulus < 0) then
        set modulus = modulus + divisor
    endif

    return modulus
endfunction

//Specialized ModuloReal, specifically for divisor = 2*pi
function ModuloReal2PI takes real dividend returns real
    local real modulus =  dividend - I2R(R2I(dividend * 0.15915494)) * 6.2831853
    if modulus < 0 then
        set modulus = modulus + 6.2831853
    endif
    return modulus
endfunction

 

[Prometheus3375]

@AutisticTenacity if you are on 1.29+, you can use % operator instead of ModuloReal.

 

[Kakerate]

Wow really impressive work there @AutisticTenacity, I've always kinda wanted to write this myself but had made put with the limitations of WC3 engine.