Pathfinding Thread
#Train Pathfinding
barren barn
Ayoo, so, you've got train pathfinder stuff, huh?
final trench
😭
what exactly makes city blocks slower for pathfinding?
just like the amount of possible routes to take?
barren barn
Multiple paths that are all about the same, with varying degrees of penalty from trains that are stopped
final trench
ahh so it can't filter easily
I'm unfaimiliar with the in-depth mechanics of how trains work
barren barn
branching factor is ridiculously bad for A* when it can't actually use the heuristics properly
Let's say we have a 2 branching factor to get from point A, somewhere on a grid, to point B, okay? We'll give A* the benefit of the doubt and only look at tracks in the correct direction(s), of which there could be 2.
In practice it's going to be higher
turbid kestrel
(I am reading this with interest, thank you)
barren barn
Even at 10 intersections between points A and B, that's 1024 paths. at 20 intersections, it's over 2 million
And a diagonal block is 2 intersections per. Even with optimizations, the problem is that you're introducing the branching factor. The thing that's good about cityblocks, that makes them work, is the UPS killer
final trench
so even for ups they suck
wow
and freeform don't deal with this because way more intersections that don't go where needed so easy to eliminate
and sometimes just straight rail
barren barn
Yeah, there are over a thousand nearly equivalent paths between these two stations lol
turbid kestrel
Surely at least other trains on the network let it arrive at one of them first
final trench
well even then that's just more calculating if there's more trains which will cause path to change
barren barn
Surely at least other trains on the network let it arrive at one of them first
Yeah that's actually why it's worse than branching factor of two. Sometimes it's optimal to turn away from the destination because of trains on the rails
also, all of these starts and stops will cause repathing
Not only is each search significantly worse, you're also doing a metric ton more of them. The more cityblocks do what they're supposed to, the worse it is for UPS lol
final trench
🤕
turbid kestrel
Repathing yes, all I meant was that other trains will avoid the case where A* traces n same-length routes to one stop from the destination before picking one of them, because they will be different de facto lengths.
barren barn
You might make it to the red block on the first pathfind, and the situation on the rails has changed, and so the pathfinder tries to go NW first but it's slow and then finds this path, away from the goal
barren barn
Repathing yes, all I meant was that other trains will avoid the case where A* tr...
Yeah it depends on your implementation of A*, I would assume they've got a good one, but I think it prefers north b/c that's direction 0?
that it always prefers direction in an ordered fashion is at least predictable and does help the PF significantly
I'm not saying A* is bad by any means, I've got my trains pathfinder at 0 in a 20k because A* is great. If you've got pathfinder time at more than zero, and are doing cityblocks... even with how good of an implementation is, it's still costing
wide lake
As I now have delusions of making a megabase this is an interesting topic. I understand the implications of the extra, unused, loco to make it happen, but I'm thinking there's a big potential to reduce path searching by using terminal stations over pass-through stations. Correct?
final trench
What is a terminal station?
wide lake
Dead end
turbid kestrel
I would suspect there's not much difference between the pathfinder going "oh, end of the line, never mind" and "oh, cheaper route to get here, never mind"
wide lake
The ability to route through the station is another alternate path, for every station between A and B. Worse if it happens to also have a stacker. At least, that's my thinking.
barren barn
Dead end
I'm still not following exactly what you're asking
Oh, train stations add a pathfinder penatly
Like 2km?
"Dummy Stations" can be used to make trains avoid paths
turbid kestrel
The ability to route through the station is another alternate path, for every st...
But as soon as the pathfinder traces back to the mainline and realises it knows a cheaper route there, it will give up on the station route - just like hitting a dead end.
wide lake
"Terminal station" being one where the exit is to reverse the train travel direction, even if the mainline is normal 1-way rails.
barren barn
I mean, they can't path through, that much is for sure lol
But even a single station will prevent checking
The right side is more than 2 km longer. This can be used to prevent trains from using alternative paths unless they need to use them
turbid kestrel
The right side is more than 2 km longer. This can be used to prevent trains from...
Albeit presumably then at the cost of the affected train looking at most of the rest of the map before it realises it has to go through the station.
wide lake
I'm thinking of, as an example, the set of stations in the elevated rail FFF where there was a bunch of dead-end stations.
barren barn
Albeit presumably then at the cost of the affected train looking at most of the ...
I mean, it's a 2km penalty, but if the only station with that name is behind it, there's only one path. It's a trick that can be used
turbid kestrel
I mean, it's a 2km penalty, but if the only station with that name is behind it,...
I agree with that, I'm just saying, correct me if I'm wrong, with a potentially large pathfinding cost for doing so.
barren barn
Dead end stations are fine, bidi have a slight penalty b/c of half the locomotives being dead at a time, but it's not bad
barren barn
I agree with that, I'm just saying, correct me if I'm wrong, with a potentially ...
No, it's a pathfinder reduction. Think of it as paths you don't have to check. You shouldn't put a high use station of the same name as other stations outside
A train which has to get there, always will still, no penalty.
turbid kestrel
No, it's a pathfinder reduction. Think of it as paths you don't have to check. Y...
I don't then understand why the train intended to route through the station doesn't first check 2km of route in every other direction.
barren barn
For N:M? It would
that's not the use case
It's to stop the N:M trains from even checking that side rail to begin with. It's cutting THEIR paths off, b/c they don't have to go there
turbid kestrel
Why would it not do so even if it had one destination station (behind the station causing the pathfinding penalty)?
barren barn
You can put a BUNCH of bullshit that train's won't search, guarded by a single station
That block is 2km farther, according to the PF
So the trains are like "oh that's a bad choice" and don't check it
turbid kestrel
You can put a BUNCH of bullshit that train's won't search, guarded by a single s...
Yes, I understand. But if a train wants to go to that bunch of bullshit, is there not then a pathfinding penalty for that train?
It must search 2km deep into the rest of the network before considering going through the guarding station.
barren barn
If there are stations outside, it will prefer to go elsewhere. Yes. That's what I said about "use case."
You can prioritize OTHER stations that way, even
turbid kestrel
OK, but all I am saying is that doing so comes at a large pathfinding cost for trains that do want to pass the guard station, and asking that you correct me if that's wrong.
Of course it may (probably does) mean a net benefit by making other trains not consider it.
barren barn
I didn't correct you 😛 I tried to explain the use case
wide lake
If the guarded station is one of a kind, the guarding station(s), won't matter to the path finder, the distance penalty only matters if there are other choices.
turbid kestrel
I didn't correct you 😛 I tried to explain the use case
Yes, that's fine - I only wanted you to correct me if I was wrong.
turbid kestrel
If the guarded station is one of a kind, the guarding station(s), won't matter t...
I am reasonably sure that's incorrect.
barren barn
No, that's that I was saying. Don't put an N:M behind it, do put unique
Unique stations, that's the only path. It doesn't matter if it's 2km longer. It's the only path
turbid kestrel
Unique stations, that's the only path. It doesn't matter if it's 2km longer. It'...
Well, it will go there, but it will trace deeper into the rest of the network to establish that that's the only path than it would without the guard station.
wide lake
I'm wondering if there are two different concepts of path finding penalty at work here. 1) the cost in ms to find a path and 2) the cost in km of a path found.
turbid kestrel
So I think it is incorrect to say that "If the guarded station is one of a kind, the guarding station(s), won't matter to the path finder"
barren barn
Well, it will go there, but it will trace deeper into the rest of the network to...
You should take a look at the implementation of pathfinder, and how it searches nodes
B/t it's node based, and it culls nodes. That's why it takes so long when you place track on a massive rail base
Rebuilding is the thing that happens then
barren barn
For calculation it uses a simple A*-algorithm[1]: The pathfinder first builds a list of non-disabled stops that match the name in the schedule, then searches outward from both ends of the train at once, if applicable, in segments. A segment is an uninterrupted plain sequence of rails, with no intersections, stops, or signals (all of which define segment borders).
Btw double ended A* is cash money. Halving depth is ridiculous gains on expoential
Testing set membership is cheap aF
If either end reaches a node in the other end's "explored," connect the paths
turbid kestrel
That I knew, but crucially that it keeps a view of the non-dynamic (apart from construction etc) network lying around is - well, stupid of me not to expect it
barren barn
Yeh, still has to update some real time stuff though
turbid kestrel
Hence "non-dynamic". My bad.
(I think the answer to Chindraba's question is still that dead ends are about the same as passthrough but ofc I may not be the most reliable person here :-)
wide lake
So, for UPS performance, the fewer potential paths the better? Without regard to 'distance' calculations?
barren barn
Trains will largely not search siding stations unless they have to. Destination stations aren't penalized the same as "dummy stations" so a copper plate drop is a dummy for iron plate, etc.
Yeah, that's why I have zero pathfinder. The trains have no choice at all
There is exactly one path from source to drain.
wide lake
Due to the organic growth I do have a few, less than dozen overall, cases where trains passing through the center could have 2 or 3 alternative paths, otherwise the only alternatives are which of the same-name stations to go to.
Still small of course, but looking to grow.
barren barn
It takes a lot to abuse the pathfinder, truly
Organic rails rarely run into PF problems before other issues
Mostly because they're purpose driven
You're not laying a bunch of extra track, you're laying the track you need. Perfect, not a lot of extra choices 😛
wide lake
There's still 7 choices of which coal mine to visit, and that could include 2 or 3 on a branch, like a tree rather than a grid.
barren barn
It's going to path once, every minute or two, and it's got like 3 choices and they're all easy lol
Honestly, I think you probably have to push cityblocks beyond one or two other failure points before it even gets to be a problem, like, you have to surpass the TPM problem first lol
wide lake
At some point, even if it's 7 km left on the path, the choice becomes 1.
barren barn
Yep, there is only one path leading to that station
wide lake
And, eventually, only 1 station to choose, so no repath even possible.
barren barn
Yeah, for the most part, I wouldn't be too concerned with UPS regarding pathfinder. Cityblocks in particular for megabasing, eventually it does run into problems
wide lake
I'm going to eventually have to drop the bidi system for throughput, but it's sufficient atm.
barren barn
lol if you're running Bidi, in general you're not going to have UPS issues
though I think it'd be neat to have a fully bidi megabase
Tough challenge
wide lake
The 'challenge' for now is enough coal to keep the lights on. Delivery isn't an issue, yet, having any to deliver is.
barren barn
Hahaha one day at a time. If your goal is to eventually megabase, cityblocks are a great tool to get you over a couple humps
"I've got iron taken care of now, if I need more, I slap down a blueprint"
wide lake
But, with a goal of getting somewehre into megabase range I do have to worry about some things.
barren barn
lol you've got plenty of problems on your plate already 😛 One step at a time
wide lake
I'm thinking that the PF issues of city block are just one more reason not to explore that particular tool.
barren barn
If you can figure out a way to organize your base on a larger scale for 1k SPM without it, that's a fine idea. Tough though, like, you're having to more directly tackle a fairly large logistical problem
I guess 1k SPM is around 37 bluebelts of ore, give or take? Plus some coal and oil. that's a lot of belts
wide lake
And a gang of trains.
Something I've noticed for many showcase megabases is they often rely on placed ores rather than generated maps.
barren barn
Anything over 10k, the point is largely about optimization, and comparing in lab conditions. We know how to mine, that's not the big deal for larger bases. It's about UPS optimization. The fallenghost 40k base I like to link, the TLDR was "performed 1% better than flame_sla's"
Literally like 63 versus 64 UPS over them both doing multiple tests lol.
Meanwhile the reason why I have "Urchin" as my tag is b/c my 20k took me 600h to build in the editor, and I still dropped got to 36 UPS 😦
Not a complete failure but I'm not happy and am looking to improve it
I did do something new though, so that's still cool
wide lake
For me the UPS issue isn't the challenge of how low can it go so much as how far can I get. The techniques for improving UPS apply just as much, though.
barren barn
Yeah, kinda the same difference. A lot of people come in with UPS problems down in the 1-2k range b/c they were not prepared for the changes lol
wide lake
It's more like the UPS issues will eventually force me to stop growing, but it's how much I can get SPM-wise out of the map I have.
And, the oil and coal, so far, have me considering using nuclear fuel in boilers.
barren barn
Eh, eventually the game kinda changes. You have a target, you do the thing, next map
wide lake
Aye.
The last big map was more POC than anything. Only launched the one rocket to "win" the game. Never even made a "science build"
barren barn
There's a lot of fun ways to play the game 😛
I think we might be digressing from the topic at hand though, wanna head back to regular chat?
wide lake
True that. For the PF issue, back to my terminal, or dead-end, stations. Since they have no exit, from a path finding view, are the non-existent in the A* unless they are in the target station list?
I.e. search for path to coal load never even sees the iron load stations?
Or, any branch which only leads to iron load.
barren barn
Yeah, when you have the Y, where one path leads to iron, and the other leads to coal, that's where it chooses
There's one choice and it's just "Is left correct?"
It's not even actually pathfinding yet b/c it's double ended lol
wide lake
Where, if the stations were pass through, the 99% design choice, the path through iron still might have to be checked, at least once to give it a weight?
barren barn
If it's not a coal station it's a "dummy" and that path is 2km longer
The game's optimized insanely well and all of the choices Wube made are correct, as far as I can tell. What I'm doing with UPS optimization is just saying "here's how to use the tools properly"
wide lake
With an organic map, 2 km is nothing.
barren barn
It's not doing 2km worth of search
Oh
That's what's getting messed up
A* looks at nodes, and the next node it searches is a combination of the best heuristic, and best path cost so far. That's A*
So when it pulls a node off the stack, if checking that path is correct, then it'll look. And it'll also see it's explored the exit. It's one node
And the 4km of path it checks next? That's 4km without a branch. It's one node
The length of the path itself doesn't change anything regarding how hard the search is. It's part of the heuristic function. When that node is put on the queue, it's like "oh I'm going to guess that's a bad one, I'll check it later if I have to"
These penalties are just a number. 2km is closer than 4km, search that first
It comes off the queue first b/c of a heuristic score
wide lake
So, in building the queue, is it still testing, eventually, the 2 km fork which ends in iron before the 6 km fork that leads to the coal station it wants?
wide lake
Where, if it was a pass-through station, which 'could' lead to the coal, it might still get checked, even though the iron station is a dummy with a 2 km distance penalty? My map is getting rather large in raw train travel distance even before 'penalites'.
barren barn
Yes, it could. But such pass-through stations will also see that they've explored the exit node already
So they're a single check
B/c they're 2km farther, the exit node will virtually always be explored first and so the branch is terminated immediately
wide lake
So the 'savings' from terminal stations is non-zero while not being as significant as my brain would like to believe?
barren barn
lol yeah, I would classify it as "trivial" cost in the grand scheme of things
You can optimize it away, but also... that happens by accident for other reasons so like, meh lol
Like I showed with that photo earlier, you can do many-to-many with literally no branching
My PF still has to search those nodes, it just makes zero incorrect guesses
wide lake
Somehow that's always been near to what I make. Sometimes there might be 2 choices, but the worse of the two ends up passing through the better one.
barren barn
Like, say it's starting at the east, trying to go to the westernmost iron station. every path could get it there, there are u-turns baked in everywhere. None of them do. They all know it's the wrong path and that the correct path is quicker
The dummy stations adding 2km are part of it
Also, it only chooses a child node at the first chain signal in each group of 7 branching stations there
6/7 are "2km farther"
So it looks at the westbound and never checks the others.
Then it reaches its destination without ever checking branches
wide lake
"Dummy" station is any station in the path with a name other than the target?
barren barn
Yea
Also keep in mind that the station is pathing backwards, too. So it's only got the one way in from that route
Just laying out the rails properly, you can completely take advantage of the pathfinder
I have no pathfinder, because my pathfinder always checks only the correct route.
wide lake
Path penalties is how I made my overflow parking work. I used closed rail signals rather than a dummy station, but still a penalty.
barren barn
Hey, if it works, it works
wide lake
Worked good enough to save my sanity when I rebuilt.
barren barn
Oh yeah there are zero signals in that rail network as well, that's also fun
Those are 1-18 trains too 😛
Stackerless 1-18 is pretty amusing to me
wide lake
For my base, looks like the PF won't be an issue at all. I can worry about other fish in the pan.