BWAPI distance calculations are wrong

[ankmairdor]

First, the function for distance from unit to position int UnitInterface::getDistance(Position target) const actually calculates the distance between the unit and an area with size[3,3]. Seems to be the result of a copying code from unit to unit distance. According to openBW, the bounding box adds 1 to the right and bottom of a unit. When we substitute a target position for a target unit, it creates an asymmetric relationship in the calculation, thus the current result is incorrect. I propose the following code as a fix.

int UnitInterface::getDistance(Position target) const
  {
    // If this unit does not exist or target is invalid
    if (!exists() || !target)
      return std::numeric_limits<int>::max();

    /////// Compute distance
    // compute x distance
    int xDist = this->getLeft() - target.x;
    if (xDist < 0)
    {
      xDist = target.x - (this->getRight() + 1);
      if (xDist < 0)
        xDist = 0;
    }

    // compute y distance
    int yDist = this->getTop() - target.y;
    if (yDist < 0)
    {
      yDist = target.y - (this->getBottom() + 1);
      if (yDist < 0)
        yDist = 0;
    }

    // compute actual distance
    return Positions::Origin.getApproxDistance(Position(xDist, yDist));
}

Second, the function for Starcraft distance from position to position int getApproxDistance(const Point<T,Scale> &position) const has a minor difference in conditional logic from openBW.

BWAPI:

int getApproxDistance(const Point<T,Scale> &position) const
    {
      unsigned int min = abs((int)(this->x - position.x));
      unsigned int max = abs((int)(this->y - position.y));
      if ( max < min )
        std::swap(min, max);

      if ( min < (max >> 2) )
        return max;

      unsigned int minCalc = (3*min) >> 3;
      return (minCalc >> 5) + minCalc + max - (max >> 4) - (max >> 6);
};

openBW:

int xy_length(xy vec) const {
	unsigned int x = std::abs(vec.x);
	unsigned int y = std::abs(vec.y);
	if (x < y) std::swap(x, y);
	if (x / 4 < y) x = x - x / 16 + y * 3 / 8 - x / 64 + y * 3 / 256;
	return x;
}

When comparing note that x was max in openBW; the reversal in BWAPI is irrelevant because of the swap. The last conditional of each function is where the problem occurs, but let me explain why.
The BWAPI version returns when true, otherwise it calculates.
The openBW version calculates when true, otherwise it returns.
Thus the conditional has been negated, between versions. Here are the steps to convert the openBW conditional to the proper BWAPI conditional.( ! at start represents the negation between versions)
!if ( x / 4 < y)
if ( x / 4 >= y)
if ( max / 4 >= min)
if ( (max >> 2) >= min)
if ( min <= (max >> 2) )

Current BWAPI conditional:
if ( min < (max >> 2) )
It has < rather than the expected <=. The impact of fixing should be about a 1.85% decrease in range for == cases.

[heinermann]

How do you know that OpenBW is correct? I'll have to reverse engineer these in BW again to verify.

[ankmairdor]

@heinermann I don't know that openBW must be correct. My assumption was that BWAPI was effectively derived from openBW as the calculation code in BWAPI felt more thought out. But I can be certain that BWAPI is wrong on the first issue, as the core issue is the math, not the state of openBW.

[heinermann]

BWAPI and OpenBW were separately derived from Broodwar (BWAPI first). Will check them out after work.

[ankmairdor]

@heinermann I did a in-game test with two siege tanks(size[32,32], range 224). I set them up with center to center difference in positions of [256,88] this results in a edge to edge difference of [224,56]. If the distance function simply returns max then result is 224, else if calculations are performed the result is 228. 224 / 4 == 56 so according to openBW the tanks are in range of each other, and according to BWAPI the tanks are out of range(228 reported in-game by BWAPI). The tanks shot each other from those positions. Verification would be great, but at this point I am pretty sure openBW is correct.

[ankmairdor]

@heinermann Another slight issue, though this one would be quite difficult to test in-game. While siding with openBW has been pretty reliable so far, if you are still reverse engineering this would be something to check. BWAPI uses minCalc to reuse calculations, but compared to the openBW version this results in a round-off error after the first bit shift division which changes the results on the next line. Some ranges will be 1 shorter than they would be in openBW.

[ankmairdor]

(edit: original photo had minor inaccuracies due to shortcuts used when drawing points near the vertical axis)
This was the project that lead to exposing the issue. I drew all points corresponding to the concentric distances. In descending order of draw priority: green is BWAPI edge to point distance, red is openBW edge to point distance, orange is Pythagorean center distance plus average of sides(though drone is square). 20 pixel interval.