PyroFire wrote: ↑Tue Dec 10, 2019 3:56 pm
mrvn wrote: ↑Thu Sep 12, 2019 5:47 pm
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.
PyroFire wrote: ↑Tue Dec 10, 2019 3:56 pm
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...
Ghoulish wrote: ↑Wed Dec 04, 2019 8:38 am
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;
PyroFire wrote: ↑Tue Dec 10, 2019 3:56 pm
mrvn wrote: ↑Tue Dec 10, 2019 1:22 pm
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.