[0.16.51] Train collision inconsistency

Bugs that are actually features.
Post Reply
Allaizn
Former Staff
Former Staff
Posts: 90
Joined: Sat Mar 03, 2018 12:07 pm
Contact:

[0.16.51] Train collision inconsistency

Post by Allaizn »

While tinkering with trains, I uncovered another bug/ weird behavoir of trains:
Collision detection on curves seems broken:
Trains can merge using curved rails, then drive fine on straiht ones, but crash into each other on the first turn.

To reproduce:
1. Load up the attached save file:
1000x1000 preset.zip
(1.73 MiB) Downloaded 103 times
2. Notice three identical setups. For now focus on the lower one, and rotate the inserter to start the contraption
3. Notice that the timing works out and the trains merge successfully onto the same line
4. Run to the left until you see the right turn and notice the trains happily driving behind each other
5. Watch the trains collide at the beginning of the curve

Notes:
This happens regardless of physics update order! But the timings change: The uppermost setup has reversed train ID order (and therefore reversed update order) compared to the lower ones, but the timings for the upper two are identical (1 tick off from the bottom one).
The middle setups allows trains to drive, which is expected, since there's now an 1 tick gap between them, but the upper ones collide in exactly the same way as the lower ones.
I know about the inherent order of collision updates and do not intend to make this a bug post about them. Instead I lament the inconsistency that some curved (like the merging) behave differently than others (like the right turn).

What I expect to happen:
Rail merges and curves should have the same throughput/ minimal train distance.
Ideally, straight rails would also have the same throughput.
My wishful dreaming would be that the update order thing would go away, too, but that's just what it is: a dream.
Attachments
factorio-current.log
Log for completeness
(5.97 KiB) Downloaded 87 times

Rseding91
Factorio Staff
Factorio Staff
Posts: 13178
Joined: Wed Jun 11, 2014 5:23 am
Contact:

Re: [0.16.51] Train collision inconsistency

Post by Rseding91 »

Thanks for the report however the trains aren't merged. The collision box of the train is much smaller than the visual it renders.

The blue rectangle is the first trains bounding box (and the rails below it) and the green is the second trains bounding box (and the rails below it). They aren't colliding so the trains drive just fine. When the trains start to turn the bounding box rotates and the corner then hits the rear locomotive and that's what you're seeing.

Image
If you want to get ahold of me I'm almost always on Discord.

Rseding91
Factorio Staff
Factorio Staff
Posts: 13178
Joined: Wed Jun 11, 2014 5:23 am
Contact:

Re: [0.16.51] Train collision inconsistency

Post by Rseding91 »

Allaizn wrote:My wishful dreaming would be that the update order thing would go away, too, but that's just what it is: a dream.
How would that ever work? The game runs on a CPU which can only be doing one entity update at a time so there must always be some update order.
If you want to get ahold of me I'm almost always on Discord.

User avatar
TruePikachu
Filter Inserter
Filter Inserter
Posts: 978
Joined: Sat Apr 09, 2016 8:39 pm
Contact:

Re: [0.16.51] Train collision inconsistency

Post by TruePikachu »

Rseding91 wrote:
Allaizn wrote:My wishful dreaming would be that the update order thing would go away, too, but that's just what it is: a dream.
How would that ever work? The game runs on a CPU which can only be doing one entity update at a time so there must always be some update order.
Probably if an entity update only needs data from previous frames, and not anything from the current frame. Yes, there will always be some order, but the ideal case is that the order doesn't matter for anything deterministic.

Allaizn
Former Staff
Former Staff
Posts: 90
Joined: Sat Mar 03, 2018 12:07 pm
Contact:

Re: [0.16.51] Train collision inconsistency

Post by Allaizn »

When the trains start to turn the bounding box rotates and the corner then hits the rear locomotive and that's what you're seeing.
But shouldn't that be also the case at the merging site?
I merely wanted to point out that it's weird, that the bounding box rotation doesn't cause a collision on the merger, but the first curve does.
How would that ever work? The game runs on a CPU which can only be doing one entity update at a time so there must always be some update order.
Let's see:
  • 1. Bucket all trains into spatial groups, let's say 2x2 chunks each. Since trains can only move 1.38 tiles/ tick, such a bucketing makes it more performant to find other trains to collide with. But I'd guess that you already do that kind of thing.
    2. assume constant speed for every pair of trains that could potentially collide. This is a fair assumption, since the current engine does this anyway (at least I think so). Collision detection can now be simplified by noting that collision boxes don't matter: only the linear distance between them does.
    3. calculate their current track offset s and their current speed offset v. Their future offset will be s+v*t and this should always be greater than the constant minimal collision preventing distance between trains d. Rearranging gets us v*t>d-s. Note that that's always true if the speed difference v is non-negative, and for negative v the time of collision is given by t=(d-s)/v, which should be greater than 1 tick. In other words: v*(1 tick) < d-s means no collision. In summary, we can check for collision is done by evaluating

    Code: Select all

    NOT [v >= 0 OR (d-s) < v * (1 tick)] 
    4. Note that all these checks can be done for all train pairs independently (which is great for things like SIMD), and usually all these bools return false, because train systems try to avoid any collisions. This justifies the possibility to take a slower approch to resolve collisions: Mark the colliding train pairs, resolve the collision and then recheck the pairs influenced by this change until no more unresolved collisions are found.
A nice side effect of this would be that you're able to make more realistic collisions in step 4, which depend only on the relative velocity of the trains! (I think that currently, a 250kmh train would completely destroy a 249kmh train in front of it, but a 1kmh train wouldn't do anything against a 0kmh train)
I can try and code it all up if you'd like to see a potential implementation, just give the order and I'll reallocate playing time into coding time :D

Rseding91
Factorio Staff
Factorio Staff
Posts: 13178
Joined: Wed Jun 11, 2014 5:23 am
Contact:

Re: [0.16.51] Train collision inconsistency

Post by Rseding91 »

You're forgetting that trains can also collide with players, gates, biters, cars/tanks, and anything set to collide with them - not just each other.
If you want to get ahold of me I'm almost always on Discord.

Allaizn
Former Staff
Former Staff
Posts: 90
Joined: Sat Mar 03, 2018 12:07 pm
Contact:

Re: [0.16.51] Train collision inconsistency

Post by Allaizn »

You got me there! I initally thought that you'd be able to circumvent that by splitting collision into two cases, but I now realise that it's not really worth the code complexity (and hence risk of unintended behavior) just to fix this one minor issue.
I spent the last couple hours trying to find a better solution, but rigid body collision is really complex. Thanks to angular velocity, even two body collisions need a substantial amount of math to do correctly, as seen in e.g. this article from this series. But the main problem is that there're plenty of possibilities in factorio, where multiple entities collide simultaneously with each other, and the best thing I found in that regard was a full blown matrix solver.
And even I, who has no fear of any math, would hate to implement such a thing, especially since there's not much to gain. Even if you'd be a god like programmer (and you at Wube sure seem like it), there's no guarantee that such a solution will even work as intended and solve all issues, even though the simulation would be perfectly realistic :(
But before giving up entirely, I managed to remember that there's another problem in factorio connected to this one. And I already invested quite some time thinking about that one, but ultimately decided to not bother you about it because I'm quite possibly the only one doing it right now: cars on belts.
I was particularly bothered by the fact that my fully set up car based smelter producing iron, copper, steel and engines for 10k spm took and still takes a whopping 11.5ms update time, which will be about half out the expected total.
Allow me to describe a potential "fix" for both problems, trains and cars:
First, we'll divide all entities into three categories for collision detection:
  • First, there're all non moving buildings like assemblers, power poles, wall etc. These buildings don't have active collision, but they're rather only there for other entities to collide against
  • Second, there're all actively moving entities. But that I mean all entities that not only move, but also decide their velocity and direction on their own. Examples for this are mainly biters and players, as well as players driving cars and tanks
  • Third, only passively moving entities remain. These are entities that are either moved by something else, or you can treat them as such. Trains and cars/ tanks on belts fall into this category
Let me explain why such a seperation is useful:
Seperating buildings is kind of obvious, since they then don't need to be updated, and thats the best kind of update!
Collision detection for the second group falls into two cases: collisions for biters can make as many sacrifices as necessary for the sake of fast computation, since there's simply no need for high precision collision, while collision for players is allowed to make huge sacrifices in performance to ensure accuracy/ good gameplay, since even 100 players are a drop in the buckets compared to tens of thousands of active entities. The most important thing about this group is that collision doesn't need to be easily predicatable (exactly). Biters die under a barrage of gunfire or in a radioactive cloud regardless of their exact position, while players are impossible to control so precisely anyway.
I'd say that the current collision detection is perfectly fine for this group, as its decently fast, modders don't seem to have problems with it (as far as I know), and the gameplay feel is also optimal.
The reason that trains and cars on belts should get their own collision is that optimization fundamentally builts on information: the more information there is about an object, the more chances you'll get to find a creative way of using that information to do fewer calculations. And trains as well as cars on belts have a huge piece of information accompanying them: they'll only move along a predefined and rarely changing path!
And I think its possible to exploit that knowledge to optimize and improve collision detection, so let me explain my thought around that topic:
Comming first is of course the interplay with the other two types: collision with passive obstacles can be optimized by telling each rail piece/ belt piece its sideways clearance as a list of nearest collidable buildings in each direction, indexed by their distance. This not only allows cars to simply check the belt they're on to decide whether or not they get hung up on a building to the side, but trains also easily detect other rails merging into them!
Entities in the second category can be rather easily ignored, since it's their job to collide against a train/ car. You may raise the question how collision response should look like in this case, and my answer is that entities in the third category should get movement priority over those in the third!
The reason for this is mainly quality of life: trains and cars on belts were planned to be there, and hindering their movement could wreck finely tuned setups. I can't count how often I ran into cars on belts and killed its delicate timing :cry:
Furthermore: trains kill everything in their path instantly anyway if they're going fast, and I argue that it's acceptable that they push everything infront of them away at low speeds. A thousand kilo car (which would be a rather small one) on an industrial conveyor also shouldn't be stopped by a mere hundered kilo human in it's way: the enginieer should be pushed around.
All in all I suggest that second category entities should watch out for third category entities, and always make space for them. Since third category is routed anyway, it's rather simple to find a direction in which one would leave the track.
Having the third category entities be bound to their tracks makes it rather easy to find them, too: Second category entities check for buildings around them anyway, so rather than ignoring belts and train tracks, they instead use the pointer to them to find the corresponding transport line and from there any third category entity can be found.
Lastly, the collision between third category entities themselves can be handled via my previous method if they're on the same line, and collision between lines can be done in a similar way by following the clearance pointer to neighboring lines. As mentioned in my previous post, collisions here would be able to correctly take the entity speeds into account.

In summary, I think that this collision system improves the current one by abolishing update order dependencies on automateable entities, makes delicate systems more robust by giving them priority, and last but not least has a pretty good shot at being better for performance!

PS: This system would even allow sideways facing inserters like seen here to bind to the belt beside and sleep until container like cars come into range, because it could check for them and their clearance.

Post Reply

Return to “Not a bug”