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

This subforum contains all the issues which we already resolved.
Post Reply
quale
Inserter
Inserter
Posts: 20
Joined: Thu Aug 15, 2019 4:16 pm
Contact:

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

Post by quale » Sat Aug 17, 2019 4:35 pm

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
Nope.png (1.12 MiB) Viewed 928 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?
Attachments
factorio-current.log
(4.24 KiB) Downloaded 7 times

User avatar
darkfrei
Smart Inserter
Smart Inserter
Posts: 2171
Joined: Thu Nov 20, 2014 11:11 pm
Contact:

Re: [0.17.66] Circuit wires sometimes fail to bridge 9 tiles

Post by darkfrei » Sun Aug 18, 2019 9:00 am

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
Factorio Staff
Factorio Staff
Posts: 1033
Joined: Tue Sep 23, 2014 7:10 am
Contact:

Re: [0.17.66] Circuit wires sometimes fail to bridge 9 tiles

Post by Twinsen » Mon Aug 19, 2019 11:23 am

Fixed in Version: 0.17.67
quale wrote:
Sat Aug 17, 2019 4:35 pm
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
Inserter
Inserter
Posts: 20
Joined: Thu Aug 15, 2019 4:16 pm
Contact:

Re: [0.17.66] Circuit wires sometimes fail to bridge 9 tiles

Post by quale » Mon Aug 19, 2019 2:59 pm

Twinsen wrote:
Mon Aug 19, 2019 11:23 am
You were exactly right :)
What else would you expect? :D 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:
quale wrote:
Sat Aug 17, 2019 4:35 pm
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
Factorio Staff
Factorio Staff
Posts: 1033
Joined: Tue Sep 23, 2014 7:10 am
Contact:

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

Post by Twinsen » Tue Aug 20, 2019 8:36 am

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

quale
Inserter
Inserter
Posts: 20
Joined: Thu Aug 15, 2019 4:16 pm
Contact:

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

Post by quale » Tue Aug 20, 2019 7:03 pm

Fair enough. :)

Allaizn
Long Handed Inserter
Long Handed Inserter
Posts: 59
Joined: Sat Mar 03, 2018 12:07 pm
Contact:

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

Post by Allaizn » Tue Aug 20, 2019 7:33 pm

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

User avatar
Shingen
Inserter
Inserter
Posts: 34
Joined: Fri Jan 04, 2019 3:25 pm
Contact:

Re: [0.17.66] Circuit wires sometimes fail to bridge 9 tiles

Post by Shingen » Tue Sep 10, 2019 9:50 pm

Twinsen wrote:
Mon Aug 19, 2019 11:23 am
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
Factorio Staff
Factorio Staff
Posts: 1033
Joined: Tue Sep 23, 2014 7:10 am
Contact:

Re: [0.17.66] Circuit wires sometimes fail to bridge 9 tiles

Post by Twinsen » Wed Sep 11, 2019 9:32 am

Shingen wrote:
Tue Sep 10, 2019 9:50 pm
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.
Shingen wrote:
Tue Sep 10, 2019 9:50 pm
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.
Shingen wrote:
Tue Sep 10, 2019 9:50 pm
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.
Shingen wrote:
Tue Sep 10, 2019 9:50 pm
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.
Shingen wrote:
Tue Sep 10, 2019 9:50 pm
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.

User avatar
Shingen
Inserter
Inserter
Posts: 34
Joined: Fri Jan 04, 2019 3:25 pm
Contact:

Re: [0.17.66] Circuit wires sometimes fail to bridge 9 tiles

Post by Shingen » Wed Sep 11, 2019 6:10 pm

Twinsen wrote:
Wed Sep 11, 2019 9:32 am
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.
Twinsen wrote:
Wed Sep 11, 2019 9:32 am
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
Long Handed Inserter
Long Handed Inserter
Posts: 59
Joined: Sat Mar 03, 2018 12:07 pm
Contact:

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

Post by Allaizn » Thu Sep 12, 2019 5:11 am

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.

User avatar
Jon8RFC
Filter Inserter
Filter Inserter
Posts: 455
Joined: Tue May 10, 2016 3:39 pm
Contact:

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

Post by Jon8RFC » Sat Sep 21, 2019 3:47 am

@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
Image

Post Reply

Return to “Resolved Problems and Bugs”

Who is online

Users browsing this forum: pavlukivan