Working with trains is a pain in the..

[PyroFire]

I disagree with the implication that "train stackers" make the topic more important. It may or may not be true that "train stackers" are widely used. In any case, use of them to the extent of affecting UPS and needing to "turn off" all trains is uncommon from my perspective. I haven't had any performance issues lately working with new and interesting track layouts while employing similar "stacker" designs on parts of my map.

It's like asking to raise all speed limits in the city whenever there is road construction, just after laying a six-lane road into it. There are better ways to approach and resolve these problems. Ones that players can take themselves instead of asking to alter the base game.

Maybe I'm still missing your point. Maybe you can expound upon it please?

Sounds pretty on-point.
It's difficult to say one way or the other without something to test against.
I'm assuming it is something to do with train stackers as this would seem likely (many trains waiting for a station), but it could be a combination of many factors or something completely different.
So that kinda leaves us with...

If you want anything to come of these thoughts and your raised issues with your save, i suggest posting your save so wube can test

[mrvn]

It's a solved problem. Theoretically and Practically. The electric network has such IDs. The fluid system has such IDs.
Even belts have segments that are basically the same and they merge and split constantly as items are added and removed.

You're so very, very wrong it almost hurts to see it, and i'm actually questioning myself if i'm reading your posts correctly.
Understandable though, it's not a simple problem and a complicated subject.

Yes, you are reading the post wrong. My statement is solely about the IDs. Nothing else.

Rail Network IDs have nothing to do with any path finding on their own. It's simply about giving all rails (and the signals and stations connected to them) that are connected an identical ID. Just like all power poles that are connected have an identical electrical network ID. That way when ever you have 2 rails, signals or stations you only have to compare the Rail Network ID to see if they are connected. The connection might only go one way or be impassable for automatic trains but ignore that. It's just basic connectedness, not if the path is passable.

Maintaining those IDs, merging networks when two are connected or splitting them when they are disconnected is a solved problem. removing a rails is just like removing a power pole. Only simpler since rails only have 2 connections, not 5 (or however many the pole has).

Now for path finding this helps because trying to find a path between stations that aren't connected with rails at all is pointless. It also gives a fast way to decide if any repathing should be done when a rail is built or removed. If the rail in question isn't on the same Rail Network ID as the train then there is no need to do an expensive repath for the train. But that is a different problem. Still simple imho.

No search algorithms are needed for belts or the electric network, and the fluid system has unique behavior with pipe adjacency -- none of them really use or need any kind of searchable pattern of any description, not even close to the likes of A*.

Electricity is simple point-to-point with a bit of balancing math. Not even comparable to rails, not at all.

Fluids aren't moving anywhere with any kind of intention, they are following a sort of "fluid pressure" based on the pipes next to them. These networks only change on pipe/entity built (and fluidboxes touch).

And belts can be pre-cached so that a single unbroken chain of belt can act like a single belt, so to speak, and only really needs to check where the end of the belt lane is (items included). Belt "networks" only change on entity built. It's perhaps the most complicated one so far, but it is absolutely nothing compared to trains and we still don't need a search algorithm.

Comparing rails to any of these other network types is simply nonsensical and irrelevant - they are not relatable in any meaningful way.

The only other reasonably comparable .. comparison, would be how biters and other units navigate the world (like biters avoiding water -- and we've all seen how "good" they are at that).
Looking at mods, another example of something that would need something of a search algorithm is something like how starcraft lays creep - it "searches" outward from the central position for the closest tile, within range, that isn't already creep.

Interestingly, target finders can also be compared, sort of how an artillery turret procedurally scans through chunks over time to find a nearby target -- It won't neccessarily be the actual closest biter nest, but it gets close enough - it will target the biter nest that was "closest" in terms of chunk scans.

Although i agree with the idea of adding some optimization to the trains so that trains don't path on networks that fundamentally don't connect to eachother, as the devs stated, it's adding complexity to an already complicated system, and as Ghoulish too states...

I wanted to bring this issue up again. As it's truly a problem for me. I also wanted to get clarification from those familiar with the topic as.. A*.. it's complicated!

I've written A* before.
It involves math so far beyond your understanding it is hard for me to describe it using just words because it relies on what is essentially an infinite loop, and needs some existing knowledge or experience of how code works.
It's like trying to explain what "great circle distance" is -- you really need an image to illustrate what the math is actually doing, and what we're actually dealing with here.
But first....

And all of this seems to come from misreading. You are trying to solve path finding with Rail Network IDs. They don't do any path finding, they don't help in doing path finding. They aren't involved in path finding at all. None of the path finding code changes one bit.

What they are for is to not do path finding in the first place. So right before you go into the complex warren of path finding there would be one simple check: if (source.rail_network_id != target.rail_network_id) return NoPath;

The impact would be twofold:
1) When you place a blueprint with 1000 rails then you don't get all trains repathing 1000 times even though the rails don't even connect to anything.
2) When you have stations with the same name but not on the same rail network then they wouldn't get included in any path finding.

This would work, but I'm pretty sure you would simply be replacing one problem with another and you also don't really solve the problem.
Why not only make the check when both sides of the rail are connected to something? This may have more desirable results with less work.

It is my guess that "rail network ID's" as you described it, would reduce the performance for everyone by a linear amount and improve performance exponentially (better performance for bigger factories).
And reminder, this is only in the circumstance of having e.g. 100 trains siting in a station on automation waiting for its next station to open while you are placing a rail segment.

I think the devs said it's more than just the trains sitting at a station on automation waiting for its next station to open. At a minimum every train blocked on a chain signal is affected.

As for the cost. Placing/removing rails would add the extra cost of maybe remapping all network IDs. Which is basically the same as doing one path finding with a destination not on the network. So if placing/removing eliminates one train repath on average you basically break even.

Note though that when placing a large blueprint most rails will connect just a handful of rails. Remapping a network of something like 5 rails is not really costly. Connecting large networks is the exception.

[ssilk]

Mrvn, what I still don’t understand: why do think a network ID would make things faster?

Yes they will improve speed, for that super special case, but it will slow down everything in the “normal” case. Why? A network Id will need 2 extra bytes in ram. Two extra bytes, that needs to be read, when doing the pathfinding. No good idea.

Instead I would send the map into the optimzation-thread (viewtopic.php?f=5&t=17501 ) and hope that the problem is maybe fixed, because all what we can discuss here about implementation of features is nothing than hot air.

Btw: viewtopic.php?f=5&t=17501&start=240#p462970

[PyroFire]

Mrvn, what I still don’t understand: why do think a network ID would make things faster?

This is related: viewtopic.php?p=470179

The A* stuff is about how you would need to write a separate pathfinder thing to map and cache all the rails and stations that are touching with a single id so that the engine only re-paths trains that are "updated" by the placement of a rail, and that this would always need to happen for every rail placed.
And because this check is hypothetically cheaper than "update ALL the trains!" on rail placement, it should solve the lag frames (100 trains repathing in the same frame).
Those repath frames need to happen, and the ID suggestion is to search for trains that were affected by a placed rail and only update those.
Except... the counter argument is you're spending performance to do those additional checks in the first place, even if it's not needed.
So i go ok what if a rail is only connected on both sides -- a single rail only connected on one side or not at all is never going to result is a new path for any train, ever.
Though it only happens in giant factories with lots of trains so i'll leave this one to wube.

The impact would be twofold:
1) When you place a blueprint with 1000 rails then you don't get all trains repathing 1000 times even though the rails don't even connect to anything.
2) When you have stations with the same name but not on the same rail network then they wouldn't get included in any path finding.

This would work, but I'm pretty sure you would simply be replacing one problem with another and you also don't really solve the problem.
Why not only make the check when both sides of the rail are connected to something? This may have more desirable results with less work.

It is my guess that "rail network ID's" as you described it, would reduce the performance for everyone by a linear amount and improve performance exponentially (better performance for bigger factories).

[mrvn]

Mrvn, what I still don’t understand: why do think a network ID would make things faster?

Yes they will improve speed, for that super special case, but it will slow down everything in the “normal” case. Why? A network Id will need 2 extra bytes in ram. Two extra bytes, that needs to be read, when doing the pathfinding. No good idea.

Instead I would send the map into the optimzation-thread (viewtopic.php?f=5&t=17501 ) and hope that the problem is maybe fixed, because all what we can discuss here about implementation of features is nothing than hot air.

Btw: viewtopic.php?f=5&t=17501&start=240#p462970

Those 2 extra bytes (and you better make that 4) are read once before you pathfind. During pathfinding any rail that can be reached will have the same network ID so you never ever need to check it. It's about preventing pointless pathfinding, not improving the pathfinding in any way.

Why do I think it's needed? See the above map for an extreme case.