Pathfinding?

TROAB · Post by **TROAB** » Sat Nov 04, 2006 10:45 am

I was noticing some of my trains choosing routes which I didn't really think was the best way to go, even on simple layouts so I went into traintable mode and did an experiment... (Trains switching tracks for what appeared to be no reason despite the sudden drop in speed it would cause, etc)

It would appear that the routing engine does not take into account the speed that it can travel. I setup two terminals fairly far apart and gave two alternat routes coming out of the station signal:

A long sweeping curve that is less direct but according to the tooltip will allow up to 200mph
A more direct route of zig-zagging 20mph curves

Then I set up a train on the route, the most powerful engine available (120mph theoretical max speed).

It chose to go the most direct route down the zig zags... Just to confirm that the long sweeping curve was in fact faster despite the extra mileage, I did a few time trials back and forth on the zig zag, then deleted a segment of track from the zig zag and timed how long the train took to go the "long" way.

The "long" way averaged around 20 seconds.. the "short" way took about 50-55 seconds each trip.

Now I know this example is extreme... and I don't think the routing engine would always choose the best scenario anyways because even if it DID choose the fastest route I can imagine times where I want one high priority mail train to use the fast track, while I want a freighgt train to take the slower route to avoid deadlocks.

I'm not bringing this up to be a pain, but mainly to reinforce the need for more control of our trains routes... it's one thing to setup a good rail network, it's another thing to allow the computer to use it however it wants, it takes a human sometimes to manage the rails...

zzbusch · Post by **zzbusch** » Sat Nov 04, 2006 12:27 pm

Which route did you setup first? I find the trains will take the route that is setup first, and only take the other when the first is blocked. Of course, I haven't really studied it, it just seems like it works that way. I've had trains take off in the opposite direction, reach the end of the line and jump around and head back, or magically fly back.

leo · Post by **leo** » Sat Nov 04, 2006 1:42 pm

interesting results ...

markofjohnson · Post by **markofjohnson** » Sat Nov 04, 2006 5:46 pm

I've sometimes been able to fix this sort of problem in a real game the way you did in your experiment. By deleting a piece of track you can force your train on a particular route. Then delete all the cross overs between the two routes, then restore the 2nd slower route. Your passenger train won't have a way back to the slow route. When you create a slow freight train to travel between the same cities it will go on the 2nd rails. You might even see the computer start it on the same rail as the passenger train, then jump it to the other rail. Of course this is very tricky and requires some luck because of the 'feature' that prevents you from deleting rail from that is part of a trains route. You may have to shuffle your freight train off to another city while you rebuild track, or maybe just scrap it for a moment.

TROAB · Post by **TROAB** » Sat Nov 04, 2006 6:18 pm

Wel actually the reason I think this is a real problem is when I have double track with occasional switches to allow trains to get out of eachother's way..

periodically my trains will slow down and take the switch for no reason at all even though it would have been faster to stay on the straight track they were on...

Lama · Post by **Lama** » Sun Nov 05, 2006 1:44 am

zzbusch wrote:I find the trains will take the route that is setup first

Not really. I built a long, lightly curved line from Vienna to Munich, and set up a train on it. Then I branched off to 'Weis', single track, uphill, back downhill, to connect again with the main. This branch was clearly a further distance than to go past Weis on the main. Nonetheless, my express train that did not have Weis on its scheduled traveled over the branch, where it eventually got stuck head-on with the local.
That's broken routing, imho.

As a speculation for a cause, the main line between the points where the branch leaves and reenters it is one signal block, whereas the branch is three signal blocks.
If the express is approaching the switch on the main line from Vienna, and the local is in the block between Munich and the other switch, then the express will see that a train is in the block beyond the main line block between the switches, but will see two free blocks ahead on the branch, and will therefore choose that path.

The solution was to double-track Vienna Station, and to have one of the tracks approachable only from the branch, the other only from the main.

Line lay-out:
MUNICH-S------\-----------------------------/---------S-VIENNA
........................\-------S-WEIS-S---------/

Signaling blocks (main line numbered, branch lettered) and signals (S):
--(1)-S----(2)----\-----------(3)----------/-----(4)------S-(5)---
.........................\--(A)-S--(B)--S-(C)-/

In the situtation where the jam occurred, the express was in block 4 traveling westbound, the local in block 2 eastbound.
Blocks 3 and A would show that there was a train in block 2. Blocks B and C would appear empty.
Therefore, the express would choose block C (showing two free blocks ahead) over block 3 (showing only one free block ahead).
The local would still enter block A, because, if the express is still in block C at the time the local reaches the switch, block A shows two clear blocks ahead (A and B). Besides, the local has no choice but to go through Weis, its next scheduled stop.
As a result, we end up with the WB express sitting in block B, and the EB local in block A, with the engineers looking at each other and getting out their lunches.

It makes perfect sense, taken what we know about the way signals handle, that this would happen. But I think it is a design flaw, nonetheless.
Can't we expect there to be some sort of dispatcher AI that can anticipate the movement of trains, based on their schedule?

drivebymaster · Post by **drivebymaster** » Sun Nov 05, 2006 8:19 am

I would rather like a more manual type movement. like I would beable to take a train that is in a grid lock, point and click on it, then select a button somewhere and allow for me to have it move in the direction I so choose.

like click and drag a line that snaps to the track and would have that train follow that path.

Crazy but it would solve alot of our traffic jam problems

Falconer · Post by **Falconer** » Sun Nov 05, 2006 9:03 am

Ehm, guys, this behaviour of the game is by no means a 'problem' in pathfinding.

There are several technologies that become available that are directly related to this, most noteably the tech that increases speed in tight corners.

TROAB · Post by **TROAB** » Sun Nov 05, 2006 11:46 am

Are the patents considered active or not in train table mode?

And I'm having trouble believe that a speed increase in tight corners will make up for the time difference of about 300%...

Falconer · Post by **Falconer** » Sun Nov 05, 2006 2:08 pm

Not if it's one corner but with so many corners, the train will never ever reach its fill speed.

Think of it this way:

You take the car and have to be on the other side of the city you live in. There's an uninterrupted freeway around the city or you can go right through it, having to navigate through the city streets. Your average on the freeway will probably be something like 60mph. Your average through the city itself, if you're lucky, will likely be something like 20mph. Every corner will slow you down.

custardo · Post by **custardo** » Sun Nov 05, 2006 8:34 pm

The thing with a realtime game is, you have to calculate everthing in realtime. So when the algorithm decides on with route to take it will probably not factor in all variables. As railroad design in a normal game isn't this extreme, i suppose the the game thinks the shortest route is the best one. It depends on the pathfinding algorithm, and the nature of these things is that you can't really search for the most optimal route, only for a most likely reasonably optimal one. On top of that, the limited number of CPU cycles decreases the chance of finding the best route even further.

If you run the example with two trains, the result is probably much better. The lesson you can learn from this is: don't build your tracks this way

TROAB · Post by **TROAB** » Sun Nov 05, 2006 9:24 pm

All of these things I understand gentlemen. By showing these results my intent was not so much to condemn the game or the pathfinding engine as much as it was to reinforce the need for more control of our routes.

Obviously there is no reason one would build a track like the one in my screenshot... I used that as an extreme to test my theory on the behavior.

(Of course if the pathfinding engine were improved to take into account the "speed limit" of the track I think that would be great too)

Falconer · Post by **Falconer** » Sun Nov 05, 2006 9:33 pm

We understand TROAB.

If anything, your experiment showed that longer, fluid routes are more viable than shorter ones and that it's worth spending the extra cash on track if it means trains can get up to their full speed. It's good info.

drivebymaster · Post by **drivebymaster** » Sun Nov 05, 2006 11:35 pm

its a great test...but I hate when I put the occasional switch in here and there to allow for trains to pass uninterupted, to just have one train thats going 80 or so SLOW down switch tracks and then speed up again wehn there was no train in sight.

I still stick by my idea that they should incorporate a custom route designer. lol but hey beggers can't be choosers

KW33D · Post by **KW33D** » Thu Nov 09, 2006 6:48 am

If the pathfinding was just a little better it would be much easier to grasp the harder elements of the game.
Although it makes the game harder to master

I know I will be playing it for quite some time.