[Twinsen][0.17.66] Circuit wires sometimes fail to bridge 9 tiles

[quale]

The general contract for circuit wire reach seems to be that the shortest path between selection boxes is measured. It can be from edge to edge and even corner to corner, as evidenced by this screenshot:

Nope.png (1.12 MiB) Viewed 7014 times

But there is an exception. If an entity’s top is below another entity’s top, and its bottom is above the other entity’s bottom, the game fails to recognize the shortest path. It only seems to notice the path between corners, when a more direct path exists. I don’t believe that’s how it was meant to work.

I suspect Factorio checks the shortest path from A’s corners to B’s edges, and the shortest path from B’s corners to A’s edges, and wants both of them to be within reach. In the case I’ve found, only one of those is within reach. The game should recognize that one is sufficient.

Alternatively, assuming axis-aligned boxes, the entire logic can be simplified to this:

dx = max(a.left - b.right, b.left - a.right, 0)
dy = max(a.bottom - b.top, b.bottom - a.top, 0)
distance = hypot(dx, dy)

Can you tell I wanted to learn how reach is determined, only to end up mapping out literal edge and corner cases?

[darkfrei]

If the length of the wire will be dependent on the rectangle radius (like covering by the electric poles, like cover area by radars, effect area beacons), then you cannot have such bugs.

Code: Select all

if (abs(a.x-b.x) <= r_radius) and (abs(a.y-b.y) <= r_radius) then
  possible = true
else
  possible  = false
end

[Twinsen]

Fixed in Version: 0.17.67

I suspect Factorio checks the shortest path from A’s corners to B’s edges

You were exactly right

In case you are interested, here's the new code:

Code: Select all

  bool canWiresReach(const Entity* a, const Entity* b)
  {
    const double maxDistance = std::min(a->getMaxWireDistance(), b->getMaxWireDistance());
    if (maxDistance <= 0)
      return false;

    // Simple position-based distance check
    {
      const double distance = a->position.distance(b->position);
      if (distance <= maxDistance)
        return true;
    }

    const bool aIsElectricPole = a->isElectricPole();
    const bool bIsElectricPole = b->isElectricPole();
    // Simple distance check failed and both electric poles - can't connect
    if (aIsElectricPole && bIsElectricPole)
      return false;

    // Check if both can reach any point on both
    if (b->getSelectionBox().distanceFromPoint(a->position) <= maxDistance &&
        a->getSelectionBox().distanceFromPoint(b->position) <= maxDistance)
      return true;

    // We don't have a "bounding box distance from bounding box" so I check corners of both against the other box for a 'good enough' check
    const BoundingBox aBox = a->getSelectionBox();
    const BoundingBox bBox = b->getSelectionBox();
    return (aBox.distanceFromPoint(bBox.leftTop) <= maxDistance ||
            aBox.distanceFromPoint(bBox.rightBottom) <= maxDistance ||
            aBox.distanceFromPoint(bBox.getRightTop()) <= maxDistance ||
            aBox.distanceFromPoint(bBox.getLeftBottom()) <= maxDistance) ||
           (bBox.distanceFromPoint(aBox.leftTop) <= maxDistance ||
            bBox.distanceFromPoint(aBox.rightBottom) <= maxDistance ||
            bBox.distanceFromPoint(aBox.getRightTop()) <= maxDistance ||
            bBox.distanceFromPoint(aBox.getLeftBottom()) <= maxDistance);
  }

[quale]

You were exactly right

What else would you expect? Guessing at internals is always a bit dodgy, but this was the most reasonable explanation for the observed behavior. Occam’s razor and all.

Interesting to see the code snippet. I didn’t realize you’d have this cascade from simple to comprehensive checks, with early exits in between. It shows how the existence of particular primitives (distance between points; distance between a box and a point) and their cost influences the way you see and solve the problem. I had to fill in the full chain from low-level math to results. Which brings me to this:

Code: Select all

    // We don't have a "bounding box distance from bounding box" so I check corners of both against the other box for a 'good enough' check

That’s what this was:

dx = max(a.left - b.right, b.left - a.right, 0)
dy = max(a.bottom - b.top, b.bottom - a.top, 0)
distance = hypot(dx, dy)

It’s comprehensive and cheap. Feel free to take advantage. If I were to have a go at it, things would end up looking like this:

Code: Select all

double BoundingBox::distanceFromBox(const BoundingBox &b) const
{
  double dx = std::max(std::max(topLeft.x - b.bottomRight.x, b.topLeft.x - bottomRight.x), 0.0);
  double dy = std::max(std::max(topLeft.y - b.bottomRight.y, b.topLeft.y - bottomRight.y), 0.0);
  return std::sqrt(dx * dx + dy * dy);
}

Code: Select all

  bool canWiresReach(const Entity* a, const Entity* b)
  {
    const double maxDistance = std::min(a->getMaxWireDistance(), b->getMaxWireDistance());
    if (maxDistance <= 0)
      return false;

    if (a->isElectricPole() && b->isElectricPole())
      return a->position.distance(b->position) <= maxDistance;
    else
      return a->getSelectionBox().distanceFromBox(b->getSelectionBox()) <= maxDistance;
  }

That much cleaner and more efficient without changing results further. I can think of some more but this is already way more than I’m paid for.

[Twinsen]

That assumes unrotated bounding boxes. Unfortunately our bounding boxes could be rotated is some cases.

[quale]

Fair enough.

[Allaizn]

Once stable hits, I'll write up the necessary code to determine the distance between arbitrary boxes. Maybe it'll get used for that then

[Shingen]

In case you are interested, here's the new code:

umm... i have a couple of questions/issues.

Code: Select all

    const bool aIsElectricPole = a->isElectricPole();
    const bool bIsElectricPole = b->isElectricPole();
    // Simple distance check failed and both electric poles - can't connect
    if (aIsElectricPole && bIsElectricPole)
      return false;

a) no need to create a variable/constant that will be used only once. it's probably gonna be optimized out but still takes some unnecessary space.

Code: Select all

    // Check if both can reach any point on both
    if (b->getSelectionBox().distanceFromPoint(a->position) <= maxDistance &&
        a->getSelectionBox().distanceFromPoint(b->position) <= maxDistance)
      return true;
      
    // We don't have a "bounding box distance from bounding box" so I check corners of both against the other box for a 'good enough' check
    const BoundingBox aBox = a->getSelectionBox();
    const BoundingBox bBox = b->getSelectionBox();
    return (aBox.distanceFromPoint(bBox.leftTop) <= maxDistance ||
            aBox.distanceFromPoint(bBox.rightBottom) <= maxDistance ||
            aBox.distanceFromPoint(bBox.getRightTop()) <= maxDistance ||
            aBox.distanceFromPoint(bBox.getLeftBottom()) <= maxDistance) ||
           (bBox.distanceFromPoint(aBox.leftTop) <= maxDistance ||
            bBox.distanceFromPoint(aBox.rightBottom) <= maxDistance ||
            bBox.distanceFromPoint(aBox.getRightTop()) <= maxDistance ||
            bBox.distanceFromPoint(aBox.getLeftBottom()) <= maxDistance);
  }

b) getting "left top" and "right bottom" corners of a bounding box is done by a field, while "right top" and "left bottom" by a method - is that on purpose?

c) if you're using the bounding boxes in both first and second sections of this code, then why don't you create aBox and bBox before the first one, and skip getting it with a method there?

d) if it's enough that in the 2nd section any of the corners of A are close enough from the bounding box of B (or the other way around) for a wire to connect, then shouldn't it be enough that the middle of A is close enough to the bounding box of B OR the middle of B to the box of A (instead of AND)?

e) is that first section needed at all? as in, if the middle of the entity is close enough to the other's box then certainly one of the corners (of current or the other entity) is already close enough too, so i don't think these calculations are really necessary.
yes, i am aware that these checks are ordered from least to most complex, but you're not doing anything significantly more complex in the 2nd one, so i think skipping the first section here would on average require less checks.
i wrote a quick program in Python counting how many checks does it take to see if 2 3x3 structures with a 4 unit length wire can connect, placing one at (0, 0) and the other in all possible positions of x and y between -6 and 6 (except when they'd overlap), and on average skipping that first section was more efficient. that, of course, does not mean the average number in practical usage is going to be lower, but i think it's worth taking into account.

[Twinsen]

a) no need to create a variable/constant that will be used only once. it's probably gonna be optimized out but still takes some unnecessary space.

So what? is source code file size an issue? It's still perfectly readable and the comfort of not having to "fix" it is the only argument.

b) getting "left top" and "right bottom" corners of a bounding box is done by a field, while "right top" and "left bottom" by a method - is that on purpose?

A bonding box is defined by leftTop, rightBottom. The methods do calculations to infer the other corners.

c) if you're using the bounding boxes in both first and second sections of this code, then why don't you create aBox and bBox before the first one, and skip getting it with a method there?

No real reason why they are like that, no real reason why they aren't, both are perfectly fine.

d) if it's enough that in the 2nd section any of the corners of A are close enough from the bounding box of B (or the other way around) for a wire to connect, then shouldn't it be enough that the middle of A is close enough to the bounding box of B OR the middle of B to the box of A (instead of AND)?

Box to box check is still preferred for super large entities. Otherwise you could possibly end up in a case where you can't connect a wire to a large entity.

e) is that first section needed at all? as in, if the middle of the entity is close enough to the other's box then certainly one of the corners (of current or the other entity) is already close enough too, so i don't think these calculations are really necessary.
yes, i am aware that these checks are ordered from least to most complex, but you're not doing anything significantly more complex in the 2nd one, so i think skipping the first section here would on average require less checks.
i wrote a quick program in Python counting how many checks does it take to see if 2 3x3 structures with a 4 unit length wire can connect, placing one at (0, 0) and the other in all possible positions of x and y between -6 and 6 (except when they'd overlap), and on average skipping that first section was more efficient. that, of course, does not mean the average number in practical usage is going to be lower, but i think it's worth taking into account.

distanceFromPoint is a pretty complicated method so I doubt calling it 1-10 times is more efficient than just calling the much simpler distance method. Even so, this check will most commonly return in the first code path anyway in real use, as the check rarely fails.

[Shingen]

Box to box check is still preferred for super large entities. Otherwise you could possibly end up in a case where you can't connect a wire to a large entity.

uh... yeah, i know. that's why i wrote point e).
point d) was about changing AND to OR the same way that you - most likely - changed it in the last return.
you know, the line that changed from

Code: Select all

aBox.distanceFromPoint(bBox.getLeftBottom()) <= maxDistance) &&

to

Code: Select all

aBox.distanceFromPoint(bBox.getLeftBottom()) <= maxDistance) ||

(based on your conversation with quale)

my suggestion was to change

Code: Select all

      if (b->getSelectionBox().distanceFromPoint(a->position) <= maxDistance &&
        a->getSelectionBox().distanceFromPoint(b->position) <= maxDistance)
      return true;

to

Code: Select all

      if (b->getSelectionBox().distanceFromPoint(a->position) <= maxDistance ||
        a->getSelectionBox().distanceFromPoint(b->position) <= maxDistance)
      return true;

because with one entity larger than the other, one of the checks may succeed while the other will fail. the function overall still works fine in this case because of the corners-to-box checks afterwards - and that is why in point e) i suggested to remove this part altogether.

distanceFromPoint is a pretty complicated method so I doubt calling it 1-10 times is more efficient than just calling the much simpler distance method. Even so, this check will most commonly return in the first code path anyway in real use, as the check rarely fails.

but i'm not talking about distance method at all. i'm talking about calling distanceFromPoint 1-10 times vs. calling it 1-8 times for the same result but on average quicker.
the "first/second section" referred to the parts of the code that i quoted only.

[Allaizn]

It doesn't really matter how often the distance to point function is called here, and whether you can change the code to make it work with fewer such calls. The real answer is to properly implement a "distance between BoundingBoxes" (or probably squared distance) and use that, since it will be only marginally more expensive than a single distance to point call.
I already mentioned above that I will most likely do that once stable hits, which makes any such optimizations now rather pointless, since they merely introduce the risk of extra bugs (however small that risk is) for practically no reason - something that is to be avoided since the Devs are pushing for stable right now.

[Jon8RFC]

@Twinsen

Since you've already become familiar with this code, are you able to make a minor adjustment to keep this behavior consistent (still exists in 0.17.69):
viewtopic.php?t=74580

Here's a video showing the selection rectangles (inserter selection rectangle isn't square, isn't centered, or both):
https://youtu.be/ibnZkPIZWAA