How can I check where is a concentration of units?

[HerlySQR]

Hello, I now that units with abilities like frame strike or blizzard checks if there are a group of units which they can cast those spells, I wanna know how can I do that? Because the methods I'm thinking are not practical.

 

[Dr Super Good]

Your title seems to be asking a different question from your post.

Triggering AoE abilities is done by enumerating units nearby the target point and then filtering down if they are in the desired area of effect using the is unit in range function. Although you can enumerate units in a circle centred at the target point, this is not an accurate area of effect due to only factoring in the victim's origin point rather than their entire collision. To get around this you enumerate units in a bigger circle (radius + maximum collision radius) and then filter for units that are in range of the point since the unit in range function does factor in unit collision and so can accurately model area of effect.

Finding concentrations of units for tactical AI to target AoE abilities at is a lot more difficult and I do not know of an efficient algorithm to recommend. A really dumb but better than nothing approach would be to lookup potential targets in range using circular enumeration and then for each of those targets use additional circular enumeration of roughly AoE size to get an approximation of the number of units that could be hit by the cast. Either take a good enough target (more than X targets affected, not necessarily optimal, scales better) or the best target. The target point could potentially be further refined by additional logic, such as tracking movement for a brief period to try and predict where the unit will be at time of impact if the AoE ability has a delay.

 

[HerlySQR]

At the end what I did is found the mode of the x and y positions of the units to tell me where should I search the concentration:

// Find concentration of units

let E = EULER
let E_INV = 0.3678794
let LN_FACTOR = 1.2840254
let LN_FACTOR_INV = 0.7788008

function ln(real v) returns real
    var sum = 0.
    var sign = 1.
    var r = v

    if r < 0.
        error("Logarithm of negative number is undefined!")
    
    if r < 1.
        r = 1.0/r
        sign = -1.0
    
    while r >= E
        r = r*E_INV
        sum = sum + 1.0
    
    while r >= LN_FACTOR
        r = r*LN_FACTOR_INV
        sum = sum + 0.25

    return sign*(sum + 0.125*(r - 1.0)*(1 + 9.0/(2.0 + r) + 4.5/(0.5 + r) + 1.0/r))

function mode(LinkedList<real> data) returns real
    let n = data.size()

    if n == 0
        return 0

    let intervalNumber = (1 + 3.322 * ln(n.toReal())).round()

    data.sort()

    let minVal = data.getFirst()
    let range = (minVal - data.peek()).abs()
    let amplitude = range / intervalNumber
    
    real array l // lower limit
    real array L // upper limit
    for i = 1 to intervalNumber
        l[i] = minVal + (i-1)*amplitude
        L[i] = minVal + i*amplitude

    int array f // frequencies
    for i = 1 to intervalNumber
        for x in data
            if x.isBetween(l[i], L[i])
                f[i]++
                data.remove(x)
    
    var maxNumber = INT_MIN
    var maxF = 0
    for i = 1 to intervalNumber
        if f[i] > maxNumber
            maxNumber = f[i]
            maxF = i
    
    return l[maxF] + ((f[maxF] - f[maxF-1])/((f[maxF] - f[maxF-1]) + (f[maxF] - f[maxF+1]))) * amplitude

public tuple unitConcentrationResult(bool success, vec2 pos)

/** Returns a point where is a concentration of enemy units or a failure*/
public function unitConcentration(vec2 pos, real range, player owner, real area) returns unitConcentrationResult
    let xVals = new LinkedList<real>()
    let yVals = new LinkedList<real>()
    unitConcentrationResult result

    forUnitsInRange(pos, range, u -> begin
        if u.isAlive() and u.isEnemyOf(owner)
            xVals.add(u.getX())
            yVals.add(u.getY())
    end)

    if xVals.size() >= 3
        let concentration = vec2(mode(xVals), mode(yVals))

        let count = new Reference(0)
        forUnitsInRange(concentration, area, u -> begin
            if u.isAlive() and u.isEnemyOf(owner)
                count.val++
        end)

        result = count.into() >= 3 ? unitConcentrationResult(true, concentration) : unitConcentrationResult(false, ZERO2)
    else
        result = unitConcentrationResult(false, ZERO2)

    destroy xVals
    destroy yVals

    return result

Not sure if is the ideal way, but it worked to me.

 

[Pyrogasm]

Mode seems like entirely the wrong metric to use here because unit XY coordinates are reals not integers. Mode is "most common entry in the list" and if every unit has a unique XY coordinate (because something like (1.202, 300.5) is a different position than (1.200, 300.1)) then no number is the mode. A weighted average makes way more sense to me, where weighting is defined as (inversely?) proportional to collision size. That's effectively the computation for center of mass in physics, so there's a reasonable analogue.

The only advantage I see to using the mode (if one even exists for a given collection of units) would be that the chosen XY coordinates of the "center mass" of the concentration would always be directly on top of at least one unit. With a weighted average of only two units the chosen point would always be somewhere on a line between the two units; if the radius of the 'chosen area' of units is smaller than the search radius that's averaging unit positions, then the target circle could actually miss both units by being between them if it was small enough.

Basically a weighted average doesn't like radially symmetric configurations of units and a mode dgaf about that.

 

[HerlySQR]

I was using "Mode for grouped data" that will work for real values, and find the mode is not to tell me where is the concentration, but for tell me where to search, because I can't even use the average if first I don't know where to search.
And of course the mode is the ideal metric, because is "the tendency", so it will tell me where are more of something.