Factorio Forums

Rseding91 wrote: Fri Oct 11, 2019 6:52 pm

PunPun wrote: Fri Oct 11, 2019 10:37 am

Rseding91 wrote: Thu Oct 10, 2019 11:05 pm viewtopic.php?t=52635

OHGODS. It's a djikstra. The only thing djikstra has over A* is that it is easier to implement. No wonder big railnetworks with lots of intersections are slow.

If you say so. The only time I've ever seen rail path finding being "slow" is on rail networks like this: https://www.factorio.com/blog/post/fff-296 and even then it's not actually slow relative to the rest of the simulation (still runs at 60 UPS) - it just takes enough time that I can measure it. All of the time ends up being memory latency at that point.

Have a look at viewtopic.php?p=466888#p466888. In gameplay terms, I think the rail network is close to optimal - highly redundant, high throughput and full coverage everywhere within the walls. I have had rail networks with "narrower" cores buckle with fewer trains than you see there, and that is exceptionally painful to retrofit a fix for. The unfortunate part is that frequently eating up 5 ms or more of your 16 ms budget for trains is pretty significant.

In addition to the absolute cost of the trains, the spiky nature of their performance cost is also annoying. 50 UPS steady is noticeably less annoying than bouncing between 40 and 60 UPS.

Would it be possible to amortize the pathfinding cost over multiple ticks? Perhaps for longer trips trains plot a path to an intermediate point that's closer to their destination and then replot when they get (close to) there instead of plotting out the entire path from the get go.

mr_fancy_pants wrote: Tue Nov 19, 2019 3:08 am for longer trips trains plot a path to an intermediate point that's closer to their destination and then replot when they get (close to) there instead of plotting out the entire path from the get go.

Isn't that waypoints?

quyxkh wrote: Tue Nov 19, 2019 1:52 pm

mr_fancy_pants wrote: Tue Nov 19, 2019 3:08 am for longer trips trains plot a path to an intermediate point that's closer to their destination and then replot when they get (close to) there instead of plotting out the entire path from the get go.

Isn't that waypoints?

More or less, yes. But, automagically generated for the purposes of optimization (and not user visible) rather than manually placed for user level reasons.

How are you suggesting the game find the path to the destination so it can put this waypoint on it?

quyxkh wrote: Wed Nov 20, 2019 5:55 pm How are you suggesting the game find the path to the destination so it can put this waypoint on it?

I'm not sure I understand the question. Factorio already has a pathfinder it can use to reach the waypoints along the way to the final destination, there's no reason it can't use the same pathfinder for the waypoints instead of the final destination.

If you're asking what's the best way to generate the waypoints, that's another question. Taking advantage of the fact that the rail network itself is fairly static, they could be (lazily) generated each time the network changes (adding/removing rails/signals/stations) by running the current pathfinder (ignoring other trains) and picking the rail segment every $n segments away as a waypoint until the destination is reached.

My understanding is that trains need to rerun the pathfinder fairly often (mainly due to other trains that get in the way). If that's true, then any remaining portion of the path that was generated from the previous run but not yet travelled can be considered wasted effort. This wasted effort portion will be larger and larger as train routes get longer and longer, so the waypoints idea is a way to mitigate some of this wasted effort. Even if trains seldom rerun the pathfinder, this should smooth out the rather sharp spikes in UPS that can currently be observed with trains on long routes.

mr_fancy_pants wrote: Thu Nov 21, 2019 1:35 am
I'm not sure I understand the question. Factorio already has a pathfinder it can use to reach the waypoints along the way to the final destination, there's no reason it can't use the same pathfinder for the waypoints instead of the final destination.

If you're asking what's the best way to generate the waypoints, that's another question. Taking advantage of the fact that the rail network itself is fairly static, they could be (lazily) generated each time the network changes (adding/removing rails/signals/stations) by running the current pathfinder (ignoring other trains) and picking the rail segment every $n segments away as a waypoint until the destination is reached.

My understanding is that trains need to rerun the pathfinder fairly often (mainly due to other trains that get in the way). If that's true, then any remaining portion of the path that was generated from the previous run but not yet travelled can be considered wasted effort. This wasted effort portion will be larger and larger as train routes get longer and longer, so the waypoints idea is a way to mitigate some of this wasted effort. Even if trains seldom rerun the pathfinder, this should smooth out the rather sharp spikes in UPS that can currently be observed with trains on long routes.

This got me thinking. If you have 10 trains, going from [copper unload] to [copper load], and you have 20-25 [copper load]. Everytime you add a rail, you will ask the game to generate waypoint for 10*25 path right ?


I don't understand how generating waypoint automagically (sic) would be less costly than just running the algorithm to the end. Since for even the 1rst waypoint , you need to have the full path calculated, otherwise you might draw a waypoint that leads to a dead end. ( even if you don't end up using it, i wouldn't consider the obsolete path wasted effort ).

for longer trips trains plot a path to an intermediate point that's closer to their destination and then replot when they get (close to) there instead of plotting out the entire path from the get go.

This is like in RTS; units act like that , they start moving even if the destination is out of reach towards a generated waypoint, because else it would give information about defense/blocking units/buildings. There are different behavior when they " realise " they can't reach the end, sometimes go back, sometimes try to go around the obstacle in one direction, circle around, stay as close as possible ... depending on context.

But here a train on track can't adapt. If some waypoint leads to dead-end, the train will need manual intervention. This is avoided when the full path is checked before the trains is allowed to move. Which makes me feel like adding waypoint is something you ask the game to do after the regular pathfinding.

Now if you MANUALLY place the waypoint, it changes everything, the path that is checked before the train starts moving is only a small portion instead of a massive tree with 120232 junctions that leads to 1234324545634 path to reach your destination , ( which is the annoying 60-40-60 UPS behavior ) the pathfinder will have to find a way between like 6 junctions, which can be 256 possibilities ( all made up numbers )and do the same at the next waypoint; this will "cut" the long routes, making UPS smoother.

I'm not sure my reasoning is correct, also i don't know much magic and pathfinding is using some so maybe ! ( biters pathfinding : https://factorio.com/blog/post/fff-317 )

To try and retrofit such network foor trains i would try to combine 4 cells into 1 by getting rid of the middle cross, or even 6, 8 into 1 when it's away from heavy traffic while keeping the same robotport/power tile-coverage.

Also for such tight grid, in cities it's not uncommon to have them one-way only and alternating, one horizontal lane goes to the left, the next one to the right, etc. This would reduce the complexity of path for the algorithm while maintaining easy access to everywhere. It can be done with or without removing the middle cross on some part. Still without changing the spacing roboport/power. Still a pain given the size of your base i know.

Manual waypoints in such conditions i would use them at the entrance of the base [Entrance Iron 1] [Entrance Iron 2] and so on, before the stacker, and in chokepoint, roughly North, Easth, North East etc... , on each side of track ( Left and Right ), just to cut the long routes , as your mining station have individual name, you'd know that [copper 42] is [North east], the schedule would look like this :[ Copper 42] [North East 1R] [ Copper 1 entrance] [Copper 1 drop ] [ North East 1L]

Using station without waiting conditions and several waypoints, would possibly allow you to keep every single tracks and signal, while spreading the load over time with few efforts. ( I'd test that first for the low effort , but i'd keep my expectations low ). You got a good test map for sure

mmmPI wrote: Thu Nov 21, 2019 9:49 pm

mr_fancy_pants wrote: Thu Nov 21, 2019 1:35 am
I'm not sure I understand the question. Factorio already has a pathfinder it can use to reach the waypoints along the way to the final destination, there's no reason it can't use the same pathfinder for the waypoints instead of the final destination.

If you're asking what's the best way to generate the waypoints, that's another question. Taking advantage of the fact that the rail network itself is fairly static, they could be (lazily) generated each time the network changes (adding/removing rails/signals/stations) by running the current pathfinder (ignoring other trains) and picking the rail segment every $n segments away as a waypoint until the destination is reached.

My understanding is that trains need to rerun the pathfinder fairly often (mainly due to other trains that get in the way). If that's true, then any remaining portion of the path that was generated from the previous run but not yet travelled can be considered wasted effort. This wasted effort portion will be larger and larger as train routes get longer and longer, so the waypoints idea is a way to mitigate some of this wasted effort. Even if trains seldom rerun the pathfinder, this should smooth out the rather sharp spikes in UPS that can currently be observed with trains on long routes.

This got me thinking. If you have 10 trains, going from [copper unload] to [copper load], and you have 20-25 [copper load]. Everytime you add a rail, you will ask the game to generate waypoint for 10*25 path right ?


I don't understand how generating waypoint automagically (sic) would be less costly than just running the algorithm to the end. Since for even the 1rst waypoint , you need to have the full path calculated, otherwise you might draw a waypoint that leads to a dead end. ( even if you don't end up using it, i wouldn't consider the obsolete path wasted effort ).

It's not, generating the waypoints is going to be roughly as expensive as a full pathfinding run. The reason it works is that you remember those waypoints for next time, and continue reusing them until the rail network changes.

for longer trips trains plot a path to an intermediate point that's closer to their destination and then replot when they get (close to) there instead of plotting out the entire path from the get go.

This is like in RTS; units act like that , they start moving even if the destination is out of reach towards a generated waypoint, because else it would give information about defense/blocking units/buildings. There are different behavior when they " realise " they can't reach the end, sometimes go back, sometimes try to go around the obstacle in one direction, circle around, stay as close as possible ... depending on context.

But here a train on track can't adapt. If some waypoint leads to dead-end, the train will need manual intervention. This is avoided when the full path is checked before the trains is allowed to move. Which makes me feel like adding waypoint is something you ask the game to do after the regular pathfinding.

The trains can actually adapt, to the degree of redundancy in your rail network. Also, the waypoints follow a path that is guaranteed to reach the destination based on the pathfinder's original calculations. There may be temporary roadblocks (other trains), but those are as noted... temporary. It's already possible for trains to deadlock and/or get temporarily stuck behind other trains when other paths are still available, so this doesn't seem too unreasonable.

mr_fancy_pants wrote: Fri Nov 22, 2019 5:26 am It's not, generating the waypoints is going to be roughly as expensive as a full pathfinding run. The reason it works is that you remember those waypoints for next time, and continue reusing them until the rail network changes.

Except you generate waypoints for all possible path everytime you add a new rail. If 50 stations have the same name : (defense) , instead of generating the path and doing the pathfinder only when you need one specific path aka when a train use it, what you propose will end up requiring all 50 path being covered with waypoint again everytime the network change right ?

Sounds like running the pathfinder at a different time, not less.

mr_fancy_pants wrote: Fri Nov 22, 2019 5:26 am The trains can actually adapt, to the degree of redundancy in your rail network.

I disagree, if you want trains to adapt you want them to run the pathfinder. Why would you make such waypoints then since you rely on the old method anyway ?

Let say first waypoint can't be reached by train A because a train B is blocking a path.
Train A run pathfinder to adapt looking alternative path to final destination? , to next waypoint ?

You could say, it save time if trains calculate for next waypoints instead of final destination, and you seem to have this idea when you say:

mr_fancy_pants wrote: Fri Nov 22, 2019 5:26 am Also, the waypoints follow a path that is guaranteed to reach the destination based on the pathfinder's original calculations. There may be temporary roadblocks (other trains), but those are as noted... temporary.

BUT: if the waypoints are guaranteed to reach destination base on pathfinder calculation, this means you run the pathfinder for all path of all trains everytime you add a rail. Just to prevent calculating the path at this precise moment.

What if you remove a rail that prevent a train from reaching it's destination ? You run the pathfinder for all possible destination with the same name of those on schedule for all trains, to redo their waypoint right ? This is the only option if you want the waypoint to guarantee the end destination is in reach.

mr_fancy_pants wrote: Fri Nov 22, 2019 5:26 am It's already possible for trains to deadlock and/or get temporarily stuck behind other trains when other paths are still available, so this doesn't seem too unreasonable.

This is different.

If waypoint guarantee the end destination is in reach, then it is no problem and the whole RTS comparaison is out of place.

The cost of this being true is running massive amount of pathfinder when you modify the network topology as i understand it.

And not only :

-What if you ask a new train to reach a place he can't ? Well you need to run the pathfinder first. To create the waypoint. Then the trains should say no path.

-What if you change schedule to a trains ? you redo the waypoints too ?

There are others things that you need a more in-depth explanation to convice me your idea is not overlooking some potential unreasonable consequences :

Let say train A is stuck behind train B, can't reach waypoint 4, it has a path to reach the end destination available, it has a path for waypoint 5, yet the train is stubborn, he tries to reach waypoint 4. By doing so it find a very long way around train B, which makes it come very close to the final destination but train A doesn't get distracted he found a way to waypoint 4 so he disregard the final destination that is so close, it will clear waypoint 4 first.

Then same thing occurs too waypoint 5, 6 , 7 etc.

How do you make sure this doesn't happen ?

( see previous point, should the train tries to reach next waypoint to save time ? or the final destination, disregarding the waypoints ?)

Again i'm no expert i was intrigued at the idea it got me thinking "that can't be this easy" maybe i didn't fully understand your idea, at least it got me trying to express some thought .

mmmPI wrote: Fri Nov 22, 2019 2:00 pm

mr_fancy_pants wrote: Fri Nov 22, 2019 5:26 am It's not, generating the waypoints is going to be roughly as expensive as a full pathfinding run. The reason it works is that you remember those waypoints for next time, and continue reusing them until the rail network changes.

Except you generate waypoints for all possible path everytime you add a new rail. If 50 stations have the same name : (defense) , instead of generating the path and doing the pathfinder only when you need one specific path aka when a train use it, what you propose will end up requiring all 50 path being covered with waypoint again everytime the network change right ?

Sounds like running the pathfinder at a different time, not less.

As mentioned earlier, the waypoints need not be generated eagerly. You have 50 stations named defense, but you're only going to one of them at a time, so you only need one set of waypoints generated.

mr_fancy_pants wrote: Fri Nov 22, 2019 5:26 am The trains can actually adapt, to the degree of redundancy in your rail network.

I disagree, if you want trains to adapt you want them to run the pathfinder. Why would you make such waypoints then since you rely on the old method anyway ?

Let say first waypoint can't be reached by train A because a train B is blocking a path.
Train A run pathfinder to adapt looking alternative path to final destination? , to next waypoint ?

You could say, it save time if trains calculate for next waypoints instead of final destination, and you seem to have this idea when you say:

They of course run the pathfinder, to the next waypoint, not the final destination.

mr_fancy_pants wrote: Fri Nov 22, 2019 5:26 am Also, the waypoints follow a path that is guaranteed to reach the destination based on the pathfinder's original calculations. There may be temporary roadblocks (other trains), but those are as noted... temporary.

BUT: if the waypoints are guaranteed to reach destination base on pathfinder calculation, this means you run the pathfinder for all path of all trains everytime you add a rail. Just to prevent calculating the path at this precise moment.

What if you remove a rail that prevent a train from reaching it's destination ? You run the pathfinder for all possible destination with the same name of those on schedule for all trains, to redo their waypoint right ? This is the only option if you want the waypoint to guarantee the end destination is in reach.

As mentioned above and earlier, waypoints don't have to be generated eagerly. Mutating the rail network in general would trigger a regeneration of waypoints. However, this doesn't have to be immediately, and in many cases it need not alter trains already en route if none of the rails in the already calculated path were removed. In this respect, network mutation actually doesn't really change much compared to today, you're really just invalidating the waypoint cache for the next time, whereas today your cache is always cold (because it's not populated by design).

Imagine you have a network with point A and B, the current rail distance between the two is 1000 tiles. There is a much faster route between A and B, but it's not available because a rail is missing. Send the train on it's way from A to B, and then put the missing rail back in place while the train still has a chance to take the faster route and see if it actually does. You'll see that in many cases it won't take the faster route - I just tried it now. Taking the faster route would require a rerun of the pathfinder and trains don't necessarily do that at mutation time as we just saw, so the same applies with waypoints.

Trains do seem to (re)run the pathfinder in a number of cases, you can observe their path changing fairly often in a busy network. I'm not totally sure on all the different ways a pathfinder rerun can get triggered, but more than one run per trip is definitely not unusual, empirically speaking.

mr_fancy_pants wrote: Fri Nov 22, 2019 5:26 am It's already possible for trains to deadlock and/or get temporarily stuck behind other trains when other paths are still available, so this doesn't seem too unreasonable.

This is different.

If waypoint guarantee the end destination is in reach, then it is no problem and the whole RTS comparaison is out of place.

The cost of this being true is running massive amount of pathfinder when you modify the network topology as i understand it.

And not only :

-What if you ask a new train to reach a place he can't ? Well you need to run the pathfinder first. To create the waypoint. Then the trains should say no path.

-What if you change schedule to a trains ? you redo the waypoints too ?

There are others things that you need a more in-depth explanation to convice me your idea is not overlooking some potential unreasonable consequences :

Let say train A is stuck behind train B, can't reach waypoint 4, it has a path to reach the end destination available, it has a path for waypoint 5, yet the train is stubborn, he tries to reach waypoint 4. By doing so it find a very long way around train B, which makes it come very close to the final destination but train A doesn't get distracted he found a way to waypoint 4 so he disregard the final destination that is so close, it will clear waypoint 4 first.

Then same thing occurs too waypoint 5, 6 , 7 etc.

How do you make sure this doesn't happen ?

( see previous point, should the train tries to reach next waypoint to save time ? or the final destination, disregarding the waypoints ?)

Again i'm no expert i was intrigued at the idea it got me thinking "that can't be this easy" maybe i didn't fully understand your idea, at least it got me trying to express some thought .

It's not different, it's core to the approach. To guarantee that trains always take the absolute best possible (ie, fastest overall, averaged across all trains in the network) route is likely not practical to do in real time, and may not be possible to solve in the general case at all, as it's basically multiple interdependent TSPs.

So, trains today are not guaranteed to pick optimal paths. Indeed, they have many non-optimal behaviours that are not hard to observe in practice. Unless they run on isolated tracks, they're also not guaranteed to make their trip in the same amount of time each time. Even if they do run on isolated tracks, you need to consider things like fuel type, running out of fuel, technology upgrades, unload/load speed (which varies with technology as well), etc. So, few will expect trains to be as consistent as say, a belt.

The existing system has corner cases that can produce broadly non-optimal results and so does the proposed system. I don't think the proposed system is noticeably worse here. If you feel that a train taking a non-optimal path is unacceptable, then you also find the current system to be unacceptable.

'Trains do seem to (re)run the pathfinder in a number of cases, you can observe their path changing fairly often in a busy network. I'm not totally sure on all the different ways a pathfinder rerun can get triggered, but more than one run per trip is definitely not unusual, empirically speaking."

Path validation rules are on the wiki:
https://wiki.factorio.com/Railway/Train_path_finding

mr_fancy_pants wrote: Sat Nov 23, 2019 7:13 am As mentioned earlier, the waypoints need not be generated eagerly. You have 50 stations named defense, but you're only going to one of them at a time, so you only need one set of waypoints generated.

Ok you arrive at this 1 station, and also let say the waypoints are existent for the way back. But now the trains needs to go to the 2nd station (out of 50 ).Well then the pathfinder needs to be run again, to find the waypoints for the new path. Which would result as doing the same as right now, calculating long route when a train wants to initiate a travel. ( and cutting it into waypoints afterwards ).

However, this doesn't have to be immediately, and in many cases it need not alter trains already en route if none of the rails in the already calculated path were removed. In this respect, network mutation actually doesn't really change much compared to today, you're really just invalidating the waypoint cache for the next time, whereas today your cache is always cold (because it's not populated by design).

It is immediate with the current game, when you add a rail, it leads to train repathing, the more you have the worst it gets when you place a big blueprint.

this was linked https://wiki.factorio.com/Railway/Train_path_finding it is very useful,

Also you can use the F4 key and ask the trains to show when they repath with a little text in game.

Using those you can mitigate the effect by not having your train in a state where they would repath when you build. ( mostly you'd want your train waiting at station rather than at signal for example.)

Trains do use this behavior if you connect a new rail to their path that leads to the final destination quicker. They would repath according to the rules. And doing so realise the new way is shorter and use it. Which can lead to game slowdown in the current version but i can't find the post that taught me this . ( which hints me that the proposed system might add on top of that).

To guarantee that trains always take the absolute best possible (ie, fastest overall, averaged across all trains in the network) route is likely not practical to do in real time, and may not be possible to solve in the general case at all, as it's basically multiple interdependent TSPs.

I think it is a little different. In the TSP the order in which you cross the waypoint is yours to choose. Not for the trains they do not consider overall distance if you make them go through station 1 2 3 4 5, and you have 10 station from each name scattered accross the map. They will go to the closest 1, then closest 2 from where they are, then closest 3 from where they are when reaching 2 etc.

This means the complexity is not the same else i would agree it wouldn't be practical.

So, trains today are not guaranteed to pick optimal paths. Indeed, they have many non-optimal behaviours that are not hard to observe in practice.

The existing system has corner cases that can produce broadly non-optimal results and so does the proposed system. I don't think the proposed system is noticeably worse here. If you feel that a train taking a non-optimal path is unacceptable, then you also find the current system to be unacceptable.

I don't find current system unacceptable as you probably have guessed by my conservative stance already but I don't want to close my mind to new things either !

I think there are tools already to make the trains networks functions in a quite optimal ways, there are also some mods like https://mods.factorio.com/mod/train-pubsub or https://mods.factorio.com/mods/Optera/L ... ainNetwork that enable different logic to automate trains.

I understand not everything is possible in vanilla Factorio, i see the actual system as optimized in the sense of the saying " it's not when you have added enough , is when you can't remove anything anymore. It is used in many different ways by different players because it's made of simple bricks/rules that you can combine yourself. The more you ask the game to do for you is also the less you have to design yourself for your train network as a player.

Meaning i see corner-case and suboptimal behavior of trains as consequences of players choices, part of the fun, like a technical limitation that you discover half-way through a project and you need to adapt. And at the end when the thing is running that's what i remember .

There are plenty possibilities that have their own pros and cons, rather than seeking for "the best way". Which sounds to me like the proposed system, a "more smarter" way to handle things vs providing "various different" ways to handle things. At the cost of performance ? can't tell , i'm not coding nor knowledgeable , it still seems to me from thinking about it though.

This is no longer on topic.
Closed.