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:
- 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.
Some people proposed a much smarter algorithm which would/should take into account system loads, and dynamically calculate the best path (shortest actual/expected
time), but I think this is not absolutely required at the time, and would almost definitely be harder to implement correctly.
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>=================
\ * &*/
=======
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:
- 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.
I hope I have shown this solution should (at least in theory) fulfill all 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