For me, it seems like the most reasonable solution for our initial problem would be that trains won't reroute simply to be at the exact same spot in the end. I think it would be a lot more difficult to implement that than it sounds, but I think it should be like this in the long run anyway. Oh, and waypoints are a nice and relatively easy solution, although it will lead to a lot of fiddling for every train in bigger networks, and that kinda works against the spirit of the game (because it gets more complicated and time extensive, and you can't really automate it away).
I am completely sure that when the lategame is fleshed out more and factories become bigger, more of you will have to deal with complex train systems. And I don't think that this is a bad thing. Trains are a lot of fun once you get the hang of it, and it adds a whole new network to the game (and an important one, if you need to rely on it). Problem is the current ore generation, but there are other threads that discuss this problem.
Better train logic (smarter alternative route finding)
Moderator: ickputzdirwech
Re: Better train logic (smarter alternative route finding)
Clearly there's a bug (pathfinding a longer route that includes part of the shorter route). We should discount that as a bug (report it) and move on. [Pathing through blocks 1, 2, 3, 4 should not be considered a path worthy of evaluation if there is a path 1, 3, 4].
GewaltSam's original post was about making train path finding more intelligent. Solving this bug doesn't make the system smart. It could still take an unnecessarily long (distance or time) path if one is available.
To be intelligent the path finding will need to correctly identify valid paths (ie: fix the bug) and then make some kind of evalutation about whether to wait for a shorter path or divert via the longer path. The system will not be 'intelligent' as long as it is hard coded to proceede to the unblocked route.
GewaltSam's original post was about making train path finding more intelligent. Solving this bug doesn't make the system smart. It could still take an unnecessarily long (distance or time) path if one is available.
To be intelligent the path finding will need to correctly identify valid paths (ie: fix the bug) and then make some kind of evalutation about whether to wait for a shorter path or divert via the longer path. The system will not be 'intelligent' as long as it is hard coded to proceede to the unblocked route.
Re: Better train logic (smarter alternative route finding)
I want to make a little recap and a humble suggestion, as this topic is dear to me (as I hope it is to more of us Factorians 
).
0. Description of problem:
Currently, the train pathfinding has some problems - mostly related to taking very long or stupid paths (i.e.: detour which includes the path to be avoided, etc). In addition, there is no easy mechanism (no mechanism at all?) to control or hint the pathfinding methods to use one path over the other.
If I understand correctly, the bugs stem mostly from trying to accommodate the option to have multiple train stations with the same name, and allow a train to choose a vacant one. This is currently done by actively avoiding red signals if certain conditions are met [1](I admit I do not fully understand what these conditions are, but evidently they are not very clever, as they cause lots of unwanted routing).
1. Solution requirements
A solution to these problems should have the following:
2. Solution proposal
Finally, I wish to present a solution I think answers all of the requirements, and especially should be very easy to implement (although I obviously can't tell for sure).
The solution is using a weighted A* algorithm, with one special-case, which I will come to in the end. As splwnd said[1], the current pathfinding is implemented with a simple A* algorithm, with the aforementioned special case, which has it's drawbacks, so supposedly changing to this weighted A* shouldn't be too complicated.
I start by describing the weighting:
A single straight-track has weight 1.
A single curved-track has weight 4 (a curved track is roughly 4 straight tracks in length).
A signal has weight of 50 (a signal may introduce extra waiting time, and this should be taken into account. a value of 50 seems reasonable).
A train stop has weight 500 (although a train stop incurs no time penalty, passing through a non-required stop may block a train wanting to go there, and thus should be avoided very strongly. This also relies on the fact that on most systems train stops are on dedicated branches, and the player almost always intends trains to go into the branch only if they need to stop there).
Now, if the target stop of a train is unique, this should be sufficient, and no special treatment should be programmed. The only exception is if the target stop is not unique, in which case the following rule would be employed:
Special rule for multiple stops with the same name
If a train is headed to a train stop where there is more than one stop with the same name, it would calculate the path as normal, but upon entering the last segment before the segment it calculated it's stop to be in, it would recalculate, taking into account red signals leading into segments with a valid target stop.
To give an example: train A needs to get to station "IRON SUPPLY", which has 2 stops with that name, all at the same place in different branches coming off the same segment, with an additional path-through segment without a stop:
Where * is a signal and & is a stop. In case both stops are empty it would take either, according to the regular pathfinding. If one is taken and the other is not, it would take the other. Similarly - if there are multiple stops, some are empty and some are taken, it would take the empty one with least cost.
If, however, all stops are currently taken, it will route itself to the shortest (taken!) stop, and wait for it to become available. It will never *ever* take the path-through route - it is there only for trains which do not need to stop at those stops.
This may seem complicated, but it is only one rule and it is actually dead simple - if you have a choice of stop, wait until you are at the segment before the stop, and then only consider empty stops, or all of them if all are taken.
3. Solution analysis:
Let's revisit the list of requirements:
4. TL;DR:
I propose to change the pathfinding algorithm to a weighted A*, with weight of 1 per track tile, +50 per signal, +500 per stop, to hopefully allow for more intelligent pathing and some user tweaking of pathing.
The only additional rule is that if (and only if!) a train is destined to a stop-name which has many stops, it would re-evaluate at the last segment before the chosen stop, and if there is another empty stop of the same name *also at the next segment* it may take it, if the original is blocked.
Reference:
[1] slpwnd's post about how the pathfinding currently works: https://forums.factorio.com/forum/vie ... 834#p37808
TODO:
Change the example schematic to actual image, which will be easier to understand
Thank you for your time, and looking forward to hear your comments
).0. Description of problem:
Currently, the train pathfinding has some problems - mostly related to taking very long or stupid paths (i.e.: detour which includes the path to be avoided, etc). In addition, there is no easy mechanism (no mechanism at all?) to control or hint the pathfinding methods to use one path over the other.
If I understand correctly, the bugs stem mostly from trying to accommodate the option to have multiple train stations with the same name, and allow a train to choose a vacant one. This is currently done by actively avoiding red signals if certain conditions are met [1](I admit I do not fully understand what these conditions are, but evidently they are not very clever, as they cause lots of unwanted routing).
1. Solution requirements
A solution to these problems should have the following:
- Trains should never take obviously stupid routes.
- Shortest (in some form) path should preferably be taken.
- Be easily understandable by users (not very much special cases and obscure mechanics), and relatively simple to implement (should not take too much time to compute on the fly, nor too much effort to program into the game).
- Hopefully - allow players some ways to hint/control the pathfinding to tweak it to their needs.
2. Solution proposal
Finally, I wish to present a solution I think answers all of the requirements, and especially should be very easy to implement (although I obviously can't tell for sure).
The solution is using a weighted A* algorithm, with one special-case, which I will come to in the end. As splwnd said[1], the current pathfinding is implemented with a simple A* algorithm, with the aforementioned special case, which has it's drawbacks, so supposedly changing to this weighted A* shouldn't be too complicated.
I start by describing the weighting:
A single straight-track has weight 1.
A single curved-track has weight 4 (a curved track is roughly 4 straight tracks in length).
A signal has weight of 50 (a signal may introduce extra waiting time, and this should be taken into account. a value of 50 seems reasonable).
A train stop has weight 500 (although a train stop incurs no time penalty, passing through a non-required stop may block a train wanting to go there, and thus should be avoided very strongly. This also relies on the fact that on most systems train stops are on dedicated branches, and the player almost always intends trains to go into the branch only if they need to stop there).
Now, if the target stop of a train is unique, this should be sufficient, and no special treatment should be programmed. The only exception is if the target stop is not unique, in which case the following rule would be employed:
Special rule for multiple stops with the same name
If a train is headed to a train stop where there is more than one stop with the same name, it would calculate the path as normal, but upon entering the last segment before the segment it calculated it's stop to be in, it would recalculate, taking into account red signals leading into segments with a valid target stop.
To give an example: train A needs to get to station "IRON SUPPLY", which has 2 stops with that name, all at the same place in different branches coming off the same segment, with an additional path-through segment without a stop:
Code: Select all
* &*
=======
/ * \ *
====A>=================
\ * &*/
=======
If, however, all stops are currently taken, it will route itself to the shortest (taken!) stop, and wait for it to become available. It will never *ever* take the path-through route - it is there only for trains which do not need to stop at those stops.
This may seem complicated, but it is only one rule and it is actually dead simple - if you have a choice of stop, wait until you are at the segment before the stop, and then only consider empty stops, or all of them if all are taken.
3. Solution analysis:
Let's revisit the list of requirements:
- Trains should never take obviously stupid routes: As the only exception rule can only change a route so that the next segment is still the desired target segment, no "stupid paths" should result.
- Shortest (in some form) path should preferably be taken: A* finds a shortest (weighted) path. This may not be the shortest in time (if a lot of the signals are red), but due to the weighting unnecessary signals should be avoided, as well as stops which are not part of the route.
- Be easily understandable by users , and relatively simple to implement: As I understand it, those changes should not be hard to implement, nor should be considerably more complicated to calculate on the fly. As for easily understandable - I'd say it is, but I hope to get your input on this!
- Hopefully - allow players some ways to hint/control the pathfinding to tweak it to their needs: The addition of weights allows players to favor one route over another - simply putting signals through a path would increase it's cost, and so deter trains from taking this path. An advanced player may even choose to place "ghost" stops only to additionally increase the cost of a path. All of this is done without adding any new entity or configuration to the game.
4. TL;DR:
I propose to change the pathfinding algorithm to a weighted A*, with weight of 1 per track tile, +50 per signal, +500 per stop, to hopefully allow for more intelligent pathing and some user tweaking of pathing.
The only additional rule is that if (and only if!) a train is destined to a stop-name which has many stops, it would re-evaluate at the last segment before the chosen stop, and if there is another empty stop of the same name *also at the next segment* it may take it, if the original is blocked.
Reference:
[1] slpwnd's post about how the pathfinding currently works: https://forums.factorio.com/forum/vie ... 834#p37808
TODO:
Change the example schematic to actual image, which will be easier to understand
Thank you for your time, and looking forward to hear your comments
Re: Better train logic (smarter alternative route finding)
I think the weighting is good. I want to add:
- using signals to add weight is sometimes the wrong way. It should remove weight!
Why? Simply, because on a track with two signals there can be only two trains, on the same track with four signals, there can be four!
Ok it can also be seen the other way, before crossings for example. There, adding is correct. It depends on the block-width. It depends on, how many other routes lead into this track.
... Dunno, but I think Signals needs a bit more, then just adding weight.
- sometimes taking a new path is quite ok.
I think you cannot have more than 7 or 8 trains per minute on one track in average. If you need more, then currently you can lay just one track more; the train chooses automatically the second track, if the first is full. This is useful.
I would like to have some kind of entity, which forces the train to recalculate it's path, depending on how the next signal is switched. Like now, but a bit more contollable.
- using signals to add weight is sometimes the wrong way. It should remove weight!
Why? Simply, because on a track with two signals there can be only two trains, on the same track with four signals, there can be four!
Ok it can also be seen the other way, before crossings for example. There, adding is correct. It depends on the block-width. It depends on, how many other routes lead into this track.
... Dunno, but I think Signals needs a bit more, then just adding weight.
- sometimes taking a new path is quite ok.
I think you cannot have more than 7 or 8 trains per minute on one track in average. If you need more, then currently you can lay just one track more; the train chooses automatically the second track, if the first is full. This is useful.
I would like to have some kind of entity, which forces the train to recalculate it's path, depending on how the next signal is switched. Like now, but a bit more contollable.
Cool suggestion: Eatable MOUSE-pointers.
Have you used the Advanced Search today?
Need help, question? FAQ - Wiki - Forum help
I still like small signatures...
Have you used the Advanced Search today?
Need help, question? FAQ - Wiki - Forum help
I still like small signatures...
Re: Better train logic (smarter alternative route finding)
How about fake train stop?
- can be added to the train route between train stations.
- trains will route through it, but will not stop at it like normal train stops
Sort of like:
Station A
- waypoint A1
- waypoint A2
- waypoint A4
Station B
....
- can be added to the train route between train stations.
- trains will route through it, but will not stop at it like normal train stops
Sort of like:
Station A
- waypoint A1
- waypoint A2
- waypoint A4
Station B
....
Re: Better train logic (smarter alternative route finding)
Yes, I agree, but I tried to make it simple both to understand and to implement.
My thinking in suggesting signals add weight is that having a signal is characteristic of having a junction / turn. Think of having two parallel tracks, but one goes end-to-end, and the other with lots of junctions - you would want to only have trains which need to go through those junctions use this "slower" track, and trains that go the long distance to use the "undisturbed highway".
As for the current system - if I understand correctly, it still not always avoids red light, only in certain cases, so it won't necessarily choose a different path...
As for the "force recalculate" entity/signal - yes, I thought about it as well. I think it would be a good addition! At first I wanted to suggest it instead of the multiple-stops rule, but then I thought not having more signals would be easier to explain and understand probably.
So maybe something like what I suggested at first, and later add an "advanced signal" for forcing recalculation, or load-balancing - like a splitter for trains - send one train through one track, the next one through another. But such signals would probably need more thought to figure exactly how to model and implement them. I also think they would have to be connected (a few signals together) to really be effective, which as far as I know is not currently possible.
My thinking in suggesting signals add weight is that having a signal is characteristic of having a junction / turn. Think of having two parallel tracks, but one goes end-to-end, and the other with lots of junctions - you would want to only have trains which need to go through those junctions use this "slower" track, and trains that go the long distance to use the "undisturbed highway".
As for the current system - if I understand correctly, it still not always avoids red light, only in certain cases, so it won't necessarily choose a different path...
As for the "force recalculate" entity/signal - yes, I thought about it as well. I think it would be a good addition! At first I wanted to suggest it instead of the multiple-stops rule, but then I thought not having more signals would be easier to explain and understand probably.
So maybe something like what I suggested at first, and later add an "advanced signal" for forcing recalculation, or load-balancing - like a splitter for trains - send one train through one track, the next one through another. But such signals would probably need more thought to figure exactly how to model and implement them. I also think they would have to be connected (a few signals together) to really be effective, which as far as I know is not currently possible.
Re: Better train logic (smarter alternative route finding)
If the next block (for the current 0.11 the next two blocks) on route is red, the train will recalculate the route. It will take only the current path, if there is no alternative route (= other way is also red, or there are just no switches).sillyfly wrote:As for the current system - if I understand correctly, it still not always avoids red light, only in certain cases, so it won't necessarily choose a different path...
I use this behavior for a kind of "resorting and pre-acceleration of trains into the same directions". And for a train station with four stops and about 10-12 trains per minute.
Cool suggestion: Eatable MOUSE-pointers.
Have you used the Advanced Search today?
Need help, question? FAQ - Wiki - Forum help
I still like small signatures...
Have you used the Advanced Search today?
Need help, question? FAQ - Wiki - Forum help
I still like small signatures...
Re: Better train logic (smarter alternative route finding)
Isn't it only for the first block in the route? Right after the train left a stop?
This is how I understood slpwnd's message... but I may be wrong
This is how I understood slpwnd's message... but I may be wrong
Re: Better train logic (smarter alternative route finding)
No. That would be stupid, cause how does the train know, what happens in a minute?
Maybe I need to mention, that the definition of "next block" is a bit complicated.
The point is, when the train is on top-speed, it takes a very long way for him to stop. Eventually much longer then the trains length. They prevented collisions on that speed with a simple trick: The train stop point.
You can see this point:
https://forums.factorio.com/wiki/inde ... Debug_mode
-> check show_train_stop_point and look for driving trains, especially when stopping.
Indeed it is so, that this point elongates the lenght of the train. It is really that long.
The next block is the block before this stop point. Simply, because if there is red signal, the train needs to brake now. I think this is also the trains decision: is there a red signal in my way? yes? That's bad, search for a better one. If no alternative route found, only then it needs to stop.
Maybe I need to mention, that the definition of "next block" is a bit complicated.
The point is, when the train is on top-speed, it takes a very long way for him to stop. Eventually much longer then the trains length. They prevented collisions on that speed with a simple trick: The train stop point.
You can see this point:
https://forums.factorio.com/wiki/inde ... Debug_mode
-> check show_train_stop_point and look for driving trains, especially when stopping.
Indeed it is so, that this point elongates the lenght of the train. It is really that long.
The next block is the block before this stop point. Simply, because if there is red signal, the train needs to brake now. I think this is also the trains decision: is there a red signal in my way? yes? That's bad, search for a better one. If no alternative route found, only then it needs to stop.
Cool suggestion: Eatable MOUSE-pointers.
Have you used the Advanced Search today?
Need help, question? FAQ - Wiki - Forum help
I still like small signatures...
Have you used the Advanced Search today?
Need help, question? FAQ - Wiki - Forum help
I still like small signatures...
Re: Better train logic (smarter alternative route finding)
Ok, so how about instead of the current rule, and instead of my suggested rule, we have this rule:
If the next block is red, the train may choose a different path, under two conditions:
1. That the alternative path is at most 400 units more in weight: This is to prevent very long detours, and make it so a train never re-routes through another station (because that is almost always wrong!).
2. That the alternative path would not take the train through the red signal it is currently trying to avoid - this should be clear, but currently it is not the case.
This would also make the rule I have previously suggested redundant, because if a train comes to a station and one stop is taken, a different one would almost always be < 400 tiles away (I think it is safe to assume if it was 400 tiles away the player probably didn't consider them the same station anyway...)
If the next block is red, the train may choose a different path, under two conditions:
1. That the alternative path is at most 400 units more in weight: This is to prevent very long detours, and make it so a train never re-routes through another station (because that is almost always wrong!).
2. That the alternative path would not take the train through the red signal it is currently trying to avoid - this should be clear, but currently it is not the case.
This would also make the rule I have previously suggested redundant, because if a train comes to a station and one stop is taken, a different one would almost always be < 400 tiles away (I think it is safe to assume if it was 400 tiles away the player probably didn't consider them the same station anyway...)
Re: Better train logic (smarter alternative route finding)
To the topic of allowing players to influence the route: the simplest way would be to just change the train stop so that if I set a time of zero, the train should not slow down at all, just drive through. Currently, when I set time to 0 seconds, the train still slows down, stops, and immediately starts again.