Better train logic (smarter alternative route finding)

[GewaltSam]

Okay, so we just built a pretty big train system. We mostly built two parallel rails which are one-way in each direction (so trains can drive in a circle, practically). Crossings and branches are mostly done with a roundabout - simple one-way one-rail circle which leads in every needed direction. I could take a screenshot if that is important, but I think you'll get the idea.

Now, the problem is if a train can't take the rail in front of it because there's already a train on the segment, he will look for an alternative route. But it seems to have no logic if that alternative route really is a good one; our trains regularly refuse to break for two seconds and prefer to ride aaaaaall the way to some circle several miles away; it's not even the shortest or only alternative route, but it is there, so it goes that way.

Is there a chance that trains get a similar logic to robots which try to charge, and there are many bots already waiting at the roboport? You (the devs) once described it something like that: if there are too many bots waiting at the port, the bot will check if the flight to the next roboport is better than waiting because of the queue, in dependence of the distance. Something like that would hinder trains going crazy in your network because there are some theoretical alternative routes on the other side of the map.

I am pretty sure that this isn't because of misplaced or insufficient signals, by the way. Has anyone encountered similar? Or have I missed something central that could help us in our misery?

Thanks in advance.

[Khyron]

While I haven't built a rail network like that myself, I am not especially surprised by the outcome you describe. It's an interesting problem. Esentially, how could a train make an educated guess about how long the busy block will be busy for in order to decide whether to wait or procede imediately to the alternate route? It could count the number of track pieces to determine length, but what if there's a station on one line but not on the other? What if that station is not actually a scheduled stop (false positive)? How do you deal with the problem that one of the alternate routes might be free now but get blocked later, when the deciding train has committed (gone past the point of no return) to the alternate route? What if one of the two paths involves more blocks (more opportunites to have to wait elsewhere). There are a lot of scenarios to cater for.

The drones by contrast have a much easier time of path finding, since they fly in a direct line to their target and have no blocking obstacles.

To start with, I'm not certain there exists a solution.

The first thing that comes to my mind is for blocks to record their average busy duration. Eg: Block 25 is busy for an average length of 18 second. That could be a starting point because the train could compare the 'busy time' of each two paths as a way to estimate travel time more accurately than just counting the number of tiles (ie: it would better account for stations and other blockages).

The next improvement would be for blocks to also record their congestion. Eg: Block 25 is busy 40% of the time. That would help the pathing calculation decide the probabilty of being blocked at some later stage if it were to take the alternate route.

Not all blocks would require these stats, only the blocks which connect in such a way as to allow alternate paths. Each of those blocks would need a stopwatch, counting up the number of seconds it was either occupied or unoccupied, a variable for average busy time and a variable for average idle time. I think that would work pretty well under normal operating conditions (ignoring problems created by trains running out of fuel or beind destroyed or gridlock situations)

[Hindenobyl]

The only way I've manged to think of to solve that problem is to place rail signals every 4th or 5th rail segment. Also I make bypasses with train stops on them and instruct the train to stop for 0 seconds. Eventually, with enough trains, it may become necessary to cover every single track tile with a rail signal to avoid having the trains make an even bigger circle around just to use the bypass. This will sacrifice efficiency, but at least you'll know the trains are going where they are supposed to.

Is this tedious to do? Absolutely. Is this the best way to fix the problem? I'd be surprised if it was. I'm curious as to what others have thought of.

[ssilk]

Read this:
https://forums.factorio.com/forum/vie ... train+path
https://forums.factorio.com/forum/vie ... ath#p56536

In short words: The train searches with an A* algorithm for the direct path, which works quite well. It has only one exception: When a train is now within 2 (formerly 1!) blocks, the train searches again and this search is so simple, that it doesn't compare the length or anything, it just searches a new path for the train as if the former segment isn't existing.

[Khyron]

@ssilk: Hm.. not sure what tone accompanied your last post. Normally when you post links to previous threads like that it reads as if "this has been discussed and resolved before, don't waste your time". I don't think that's the case here. But maybe you were just including those links to help inform this thread. I can't tell. Are you satisfied with the current train pathing algorithm?

The first link explains how the current system works (A*, unsurprisingly). The second link seems barely relevant except you suggested something right at the end which is like my suggestion above (start measuring time). There's no indication from Kovarex if the devs are satisfied (or unsatisfied) with the current system, and no suggestion about desire to change the system.

IMHO this thread is not a bug report or question about how it currently works. This thread is the quest to find a beter solution. Obviously we want a system that is algorithmically simple so as to be easy to implement and also not raise CPU requirements and yet it must cater for a variety of situations.

[ssilk]

I just told it. In my opinion the current behavior is near to a bug. So - as you have already seen - I have posted something there about it after this post, cause I think that the patch from Kovarex has made the situation more worse.
I just edited it.
https://forums.factorio.com/forum/vie ... ath#p57974

[Choumiko]

Okay, so we just built a pretty big train system. We mostly built two parallel rails which are one-way in each direction (so trains can drive in a circle, practically). Crossings and branches are mostly done with a roundabout - simple one-way one-rail circle which leads in every needed direction. I could take a screenshot if that is important, but I think you'll get the idea.

I think a screen would be helpful. I'm also using circles for junctions and the pathing changes quite a bit when you have signals inside them (and where) or not. Did a quick test:
rail3.jpg : No signals inside. No observed detours (coal and iron train are suppossed to go north, coming from the east. Both did, when clearing signals with the manual train.
rail4.jpg : Signals before merging tracks. Detours
rail5.jpg : Signals before splitting tracks. No detours
I did not thest every case, so i might have missed some severe faults.

I'm not a frequent train passenger, but to me signals are only a sign whether a block in front is occupied or not. They are no indication to take an alternative route, as the occupied state most of the time is shorter than any other route.
If that's not the case then something is wrong (deadlock, out of fuel, no path), which is most likely the players or biters fault.

[sillyfly]

Yes, this has been discussed before. Yes, this has been suggested as a bug. And I too do not recall the developers ever stating clearly whether this is something that will be fixed in the future (I guess they are swamped with other works, and as I understand it trains were a bonus to begin with...).

But I do believe there could be a better solution, which isn't as complicated as Khyron described (as a result it would also not be as good/efficient, but I believe it could still be better than the current situation).

The idea is to have a cost associated with every rail piece - say 1 unit - and an additional cost per signal - say 20 units. Tinkering with these numbers would hopefully eliminate most cases of a train taking a much longer route just to avoid a red signal.
Additionally, a train should never EVER reroute through a route that would eventually take it to the same segment it is trying to avoid. As I understand GewaltSam's case, and as was for me many times - a train would arrive at a junction to find the way it needs to go blocked, then it would take a very long trip, only to come back to the very same signal (or a different signal leading into the same segment - it makes no difference). This should never happen, as it is clearly always the wrong decision.
Admittedly, it would in some cases be used to "free" a deadlock, but such a deadlock could be avoided by a smart design of the network.

Finally, this could be developed further by allowing the player to assign a cost to rail segments (say - in this segment every piece costs 0.5 units instead of 1), thus favoring some paths over others. This is similar to Khyron's idea with congestion monitoring, only it is A. static; and B. delegated to the player. This again assumes the player knows what they are doing, but they can always elect not to use such an option.

[Keyalha]

Okay, so we just built a pretty big train system. We mostly built two parallel rails which are one-way in each direction (so trains can drive in a circle, practically). Crossings and branches are mostly done with a roundabout - simple one-way one-rail circle which leads in every needed direction. I could take a screenshot if that is important, but I think you'll get the idea.

Now, the problem is if a train can't take the rail in front of it because there's already a train on the segment, he will look for an alternative route. But it seems to have no logic if that alternative route really is a good one; our trains regularly refuse to break for two seconds and prefer to ride aaaaaall the way to some circle several miles away; it's not even the shortest or only alternative route, but it is there, so it goes that way.

Is there a chance that trains get a similar logic to robots which try to charge, and there are many bots already waiting at the roboport? You (the devs) once described it something like that: if there are too many bots waiting at the port, the bot will check if the flight to the next roboport is better than waiting because of the queue, in dependence of the distance. Something like that would hinder trains going crazy in your network because there are some theoretical alternative routes on the other side of the map.

I am pretty sure that this isn't because of misplaced or insufficient signals, by the way. Has anyone encountered similar? Or have I missed something central that could help us in our misery?

Thanks in advance.

Since the train system is modular and shapable by the player this is a NP complete problem like the traveling salesman problem. There is no "smart" way to do it. The way it is currently is the only feasable way to do it performance wise and programming time wise.

[sillyfly]

Since the train system is modular and shapable by the player this is a NP complete problem like the traveling salesman problem. There is no "smart" way to do it. The way it is currently is the only feasable way to do it performance wise and programming time wise.

It is more like Dijkstra's algorithm, which is polynomial.

[ssilk]

Since the train system is modular and shapable by the player this is a NP complete problem like the traveling salesman problem. There is no "smart" way to do it. The way it is currently is the only feasable way to do it performance wise and programming time wise.

Nope. As sillyfly said, it is always wrong to calculate a route, which comes back to the same point. This is just useless.
And it would be easy to fix this most anoying thing: When the train-path-finder is able to find a route, which will NOT run into the next two red signals, so it should be possible to remove the current block in this direction also out of this calculation.

I think this will remove 50% of the obviously wrong routings.

For the other possibilities this is of course more difficult, because we need to seek for a way, which is around the current blockade, but not much more around than useful.
And yes, it is some kind of traveling salesman problem, but in reality we don't have this problem most the times, cause we have signs and smaller and bigger streets.
The measuring of the length and then estimation is just one possibility of many, because we can add signs too. "To OUTPOST 19" for example and then the train will not take any other route, if he wants to OUTPOST 19.
Another idea, which copies "bigger and smaller roads" is to have another tier of rails, which are a bit faster. Internally the routing now prefers to stay on that rails. A train tries to get as soon as possible to those priority tracks and tries to run as short as possible on side-tracks.

Just some examples of many to make this problem really low or non existent.

[The Lone Wolfling]

Yeah.

The specific case of "the next signal is red so let's take this detour that takes me... back to the same red signal" makes no sense. All it does it waste time and burn more coal.

[Keyalha]

Since the train system is modular and shapable by the player this is a NP complete problem like the traveling salesman problem. There is no "smart" way to do it. The way it is currently is the only feasable way to do it performance wise and programming time wise.

Nope. As sillyfly said, it is always wrong to calculate a route, which comes back to the same point. This is just useless.
And it would be easy to fix this most anoying thing: When the train-path-finder is able to find a route, which will NOT run into the next two red signals, so it should be possible to remove the current block in this direction also out of this calculation.

I think this will remove 50% of the obviously wrong routings.

For the other possibilities this is of course more difficult, because we need to seek for a way, which is around the current blockade, but not much more around than useful.
And yes, it is some kind of traveling salesman problem, but in reality we don't have this problem most the times, cause we have signs and smaller and bigger streets.
The measuring of the length and then estimation is just one possibility of many, because we can add signs too. "To OUTPOST 19" for example and then the train will not take any other route, if he wants to OUTPOST 19.
Another idea, which copies "bigger and smaller roads" is to have another tier of rails, which are a bit faster. Internally the routing now prefers to stay on that rails. A train tries to get as soon as possible to those priority tracks and tries to run as short as possible on side-tracks.

Just some examples of many to make this problem really low or non existent.

The Problem with such approaches is that you dont see a use for that others might do and then would be limited by it without knowing why it behaves how it behaves. You have to keep in mind that every player INSTANTLY needs to know how the system works. The more (from player viewpoint) arabitary limits you add the more freedom you take away from the train system.

Per example feedback loops would no longer be possible with your approach, which in several cases are useful (2:1 ratio circles per example ALWAYS loop back).

[hitzu]

Seeing that thread I'm just wondering why the train even search new route looking at red signal? Yes, it have to do this in the case of broken rails, but not in the case of red signalling cause lights turn red only when the route is occupied by another train, which is always a temporary state. So I really don't see any particular reason for that train behavior.

[ssilk]

@Keyalha: I don't know what you mean. It is currently the case, that the player don't knows exactly, why a train uses this path and not another. But when you implement for example traffic sign or priorized rails, then this is the case. The player can use those stuff to tell the train exactly, how to calculate the paths.

@hitzu: You need to read mentioned threads. The reason is because of https://forums.factorio.com/wiki/inde ... stop-trick
If you name two trainstops with the same name, the train will normally find only one way to this train stop. This is because it searches the shortest way to the nearest train stop and uses only that. Therefore the devs implemented this simple lookup: If the two blocks before are blocked (=train waiting on trainstation or any other signal), it searches for the other train station. The problem occurs because, a) A train does not always wait in a block at a trainstop. It can wait also at any other signal and b) it works perfect, if the train has no other possible way, but if it has some possible pathes to reach the target, it will use them.

[hitzu]

@hitzu: You need to read mentioned threads. The reason is because of https://forums.factorio.com/wiki/inde ... stop-trick
If you name two trainstops with the same name, the train will normally find only one way to this train stop. This is because it searches the shortest way to the nearest train stop and uses only that. Therefore the devs implemented this simple lookup: If the two blocks before are blocked (=train waiting on trainstation or any other signal), it searches for the other train station. The problem occurs because, a) A train does not always wait in a block at a trainstop. It can wait also at any other signal and b) it works perfect, if the train has no other possible way, but if it has some possible pathes to reach the target, it will use them.

Oh! I see. I think the train have to search new way and not wait before the red signal if and only when there is the trainstop it headed for on that particular block. How about that?
As for me, I have never had such a situation cause I never use loops preferring them two-headed trains.

[Choumiko]

@hitzu: You need to read mentioned threads. The reason is because of https://forums.factorio.com/wiki/inde ... stop-trick
If you name two trainstops with the same name, the train will normally find only one way to this train stop. This is because it searches the shortest way to the nearest train stop and uses only that. Therefore the devs implemented this simple lookup: If the two blocks before are blocked (=train waiting on trainstation or any other signal), it searches for the other train station. The problem occurs because, a) A train does not always wait in a block at a trainstop. It can wait also at any other signal and b) it works perfect, if the train has no other possible way, but if it has some possible pathes to reach the target, it will use them.

If that's the whole reason then it should be enough to only reroute when there's a trainstop within the next 2 blocks, or am i missing something?

[ssilk]

Hm. The targeted trainstop?

Yes.
But that would be boring.

[Night_Ange1]

I would like to suggest (or resuggest) waypoints. It doesnt help in gridlocks but it would prevent the alternate pathing issue I believe given enough waypoints

[SHiRKiT]

I would like to suggest (or resuggest) waypoints. It doesnt help in gridlocks but it would prevent the alternate pathing issue I believe given enough waypoints

This is by far the easiest solution. It would force trains to go to that Waypoint, that is defined by the user. It would remove all the complexities from the developers and throw them at the users. Since normal train users normally don't face this issue, only advanced users would benefit from this, which is this case, and all that with minimal effort.