TT's pathfinding problems - a solution?

[Mike Wagstaff]

It's just a thought but I reckon that TT's miserable
pathfinding might be partially fixable - at least for
trains. Where things often start to go wrong for me is when
a train hits a red signal; instead of the real-life scenario
where the train would just wait until it turns to green, one
of two things happen in TT:

(1) The train waits for a bit and, if the light is still red
after a certain time, reverses its direction. (Mad!)

(2) Rather than going up the line where the red signal is,
the train takes an alternative route. (Bonkers!)

Correct me if I'm wrong, but I reckon that if trains were to
just wait patiently at red lights rather than doing one of
the two madcap things mentioned above, then things would be
fantastically better. After all, there should be no reason
for them to become permanently stuck at a red light for any
reason other than player error. Perhaps the necessary
alterations to train instructions could be made in a patch?

Unfortunately, this doesn't fix the long-range pathfinding
problem where if two destinations are far enough apart,
mayhem is guaranteed to follow! But fixing one out of two
wouldn't be bad...

-Mike [http://games.hplx.net]

[Patchman]

In article <42949456752854512202NEWS...@news.dial.pipex.com>, Mike
Wagstaff says...

It's just a thought but I reckon that TT's miserable
pathfinding might be partially fixable - at least for
trains. Where things often start to go wrong for me is when
a train hits a red signal; instead of the real-life scenario
where the train would just wait until it turns to green, one
of two things happen in TT:

(1) The train waits for a bit and, if the light is still red
after a certain time, reverses its direction. (Mad!)

(2) Rather than going up the line where the red signal is,
the train takes an alternative route. (Bonkers!)

I'm not sure if you're talking about TTO or TTD, but in TTD you shouldn't
have that problem. The key is using one-way signals where appropriate.
A one-way signal means "go this way if you must, even if the signal is
red". The train doesn't turn around for at least a month, and will
continue happily along its correct way.
On the other hand, a two-way signal means "go this way if it's green,
otherwise try something else". The train would take the other of two
signals, or turn around in the belief that there might be a train coming
its way and it better make room.

This is also why you have to have two-way signals at the entrance of a
roro station, or your trains will only use a single platforms - two-way
signals give them a choice, one-way signals don't.

Correct me if I'm wrong, but I reckon that if trains were to
just wait patiently at red lights rather than doing one of
the two madcap things mentioned above, then things would be
fantastically better. After all, there should be no reason
for them to become permanently stuck at a red light for any
reason other than player error. Perhaps the necessary
alterations to train instructions could be made in a patch?

Waiting at a red signal forever is not such a good idea either. For
example, at a two-way signal, a train might come from the other side, so
that they'd end up staring at each other, waiting for somebody to move.

For one-way signals this is not a problem however, which is why trains do
wait at them far longer.

So, simply waiting longer is not a solution in itself, unless one really
sits down and works out all the problems that could arise - I've only
given one example but there must be many more, I'm sure.

Unfortunately, this doesn't fix the long-range pathfinding
problem where if two destinations are far enough apart,
mayhem is guaranteed to follow! But fixing one out of two
wouldn't be bad...

You can fix that too. For example you could use intermediate
"checkpoints", i.e. stations that are away from everything, just there to
give the trains an intermediate sense of direction so they don't get
lost. However, the far better solution is to build the network
correctly. Assuming you have a two track for trains going both ways,
make sure that at an intersection, turning east really means that the
train ends up going east. Cloverleafs are nice, but for some directions,
the intersection goes the wrong way, and this confuses the trains. I
think they look at the track ahead, for up to 6 - 10 squares, but not
more, so if the track makes a turn after that, they'll never know until
it's too late.

You could have a look at the savegame I've posted recently, and note how
the track is layed out. Only in very rare instances do I mislead my
trains, but even then only for a very short distance, so that they notice
and still take the right turn. That way I only need a single
"checkpoint", and that's only there to make sure my trains take the
shorter way. They wouldn't get lost without it, but take a somewhat
longer time to reach their destination. And yet everything is connected
to everything else without any problems whatsoever.

--
Josef Drexler | http://publish.uwo.ca/~jdrexler/
---------------------------------+---------------------------------------
Please help Conserve Gravity | To email me, please change the country
Carry a helium balloon. | code to .ca - Death to Spammers!

[Peter J. Dobrovka]

Mike Wagstaff schrieb in Nachricht
<42949456752854512202NEWS...@news.dial.pipex.com>...

It's just a thought but I reckon that TT's miserable
pathfinding might be partially fixable - at least for
trains. Where things often start to go wrong for me is when
a train hits a red signal; instead of the real-life scenario
where the train would just wait until it turns to green, one
of two things happen in TT:

(1) The train waits for a bit and, if the light is still red
after a certain time, reverses its direction. (Mad!)

There is nothing wrong with it. Sometimes there are problems which do not
solve (2 or 3 trains blocking each other f.e.). You can prevent the train
from going back the whole map if you have a one way signal behind it.

(2) Rather than going up the line where the red signal is,
the train takes an alternative route. (Bonkers!)

This is also not so bad. And it depends on the signal. If you use one way
signals the train will not take another route. Only if you use two way
signals. Only in this case the trains "thinks" the other way is equal. I
think this is highly efficient. I am using one way signals for crossings but
two way ones for slip switches.

Correct me if I'm wrong, but I reckon that if trains were to
just wait patiently at red lights rather than doing one of
the two madcap things mentioned above, then things would be
fantastically better. After all, there should be no reason
for them to become permanently stuck at a red light for any
reason other than player error. Perhaps the necessary
alterations to train instructions could be made in a patch?

No, this would take away more advantage than it would bring.

Unfortunately, this doesn't fix the long-range pathfinding
problem where if two destinations are far enough apart,
mayhem is guaranteed to follow! But fixing one out of two
wouldn't be bad...

This you cannot fix without rewriting the game. But if you construct your
networks according to this you have no problems:
Trains "look" only about 5 squares ahead in pathfinding. Then they decide by
the direction. Since there are only 8 directions this can be a problem for
goals in about the same direction but not exactly. So you have to build your
intersections where there is no misunderstanding where the tracks lead to.

Peter

[Mike Wagstaff]

I'm not sure if you're talking about TTO or TTD, but in TTD you shouldn't
have that problem. The key is using one-way signals where appropriate.
A one-way signal means "go this way if you must, even if the signal is
red". The train doesn't turn around for at least a month, and will
continue happily along its correct way.

Unfortunately, waits of one month on my networks have been
known! It doesn't happen often, but occasionally at a major
junction. But I agree with you and Eddie that one-way signals
are not a major problem as far as trains turning around goes.

On the other hand, a two-way signal means "go this way if it's green,
otherwise try something else". The train would take the other of two
signals, or turn around in the belief that there might be a train coming
its way and it better make room.

This is the major problem for me. The most common thing to
go wrong is when a train must go a certain route at a
junction or interchange to reach its intended destination.
The route leading from the interchange is usually more
than one track - often up to 5 or 6.

One-way signals can't be used, as trains will then only go
down one particular track, rather than using the
alternatives which are all equally valid. However, from time
to time, all the tracks on that particular route will be in
use - and that's when things start to go wrong. Instead of
trains waiting for one of the tracks to clear, they decide
to take a completely different route! As a result, they end
up goint completely the wrong way and usually get hopelessly
lost.

I do use checkpoints as much as possible to get round this
(for example, see Lewisham in the latest savegame I
uploaded), but even then things still have the potential to
go wrong.

This is also why you have to have two-way signals at the entrance of a
roro station, or your trains will only use a single platforms - two-way
signals give them a choice, one-way signals don't.

Correct me if I'm wrong, but I reckon that if trains were to
just wait patiently at red lights rather than doing one of
the two madcap things mentioned above, then things would be
fantastically better. After all, there should be no reason
for them to become permanently stuck at a red light for any
reason other than player error. Perhaps the necessary
alterations to train instructions could be made in a patch?

Waiting at a red signal forever is not such a good idea either. For
example, at a two-way signal, a train might come from the other side, so
that they'd end up staring at each other, waiting for somebody to move.

This would only happen with a badly designed network, surely?

For one-way signals this is not a problem however, which is why trains do
wait at them far longer.

But not long enough for me! My passengers are exceedingly
patient... they need to be! Basically, I wish the train
drivers were too - could they not just politely sit and wait
for the red signal to turn green, rather than take matters
into their own hands? Not only is it unrealistic, it doesn't
help me in my games.

So, simply waiting longer is not a solution in itself, unless one really
sits down and works out all the problems that could arise - I've only
given one example but there must be many more, I'm sure.

I'd be interested to hear them... I'm sure that such problems
could only arise with a flawed network design. (But I'm
probably wrong!!)

Unfortunately, this doesn't fix the long-range pathfinding
problem where if two destinations are far enough apart,
mayhem is guaranteed to follow! But fixing one out of two
wouldn't be bad...

You can fix that too. For example you could use intermediate
"checkpoints", i.e. stations that are away from everything, just there to
give the trains an intermediate sense of direction so they don't get
lost. However, the far better solution is to build the network
correctly. Assuming you have a two track for trains going both ways,
make sure that at an intersection, turning east really means that the
train ends up going east. Cloverleafs are nice, but for some directions,
the intersection goes the wrong way, and this confuses the trains. I
think they look at the track ahead, for up to 6 - 10 squares, but not
more, so if the track makes a turn after that, they'll never know until
it's too late.

I would use cloverleafs, but they take up too much space. But
I do use your patch to get around the long-range pathfinding
problem by having "non-stop" stations as checkpoints - which
works wonderfully! Muchas grazias!

You could have a look at the savegame I've posted recently, and note how
the track is layed out. Only in very rare instances do I mislead my
trains, but even then only for a very short distance, so that they notice
and still take the right turn. That way I only need a single
"checkpoint", and that's only there to make sure my trains take the
shorter way. They wouldn't get lost without it, but take a somewhat
longer time to reach their destination. And yet everything is connected
to everything else without any problems whatsoever.

Same with the savegame I just posted. Things run pretty
smoothly despite the majority of the 91 trains running
to/from just 5 terminus stations!

-Mike [http://games.hplx.net]

[Mike Wagstaff]

(1) The train waits for a bit and, if the light is still red
after a certain time, reverses its direction. (Mad!)

There is nothing wrong with it. Sometimes there are problems which do not
solve (2 or 3 trains blocking each other f.e.). You can prevent the train
from going back the whole map if you have a one way signal behind it.

Well, like I said in my post to Josef, I reckon that blocking
trains should eventually clear. If not, it's the fault of the
player for a bad design. (I have no sympathy for stupid
players!!)

(2) Rather than going up the line where the red signal is,
the train takes an alternative route. (Bonkers!)

This is also not so bad. And it depends on the signal. If you use one way
signals the train will not take another route. Only if you use two way
signals. Only in this case the trains "thinks" the other way is equal. I
think this is highly efficient. I am using one way signals for crossings but
two way ones for slip switches.

Maybe I didn't quite phrase that correctly. I didn't mean
that the train would take an alternate track leading the same
way; I meant that it would hurtle off down a completely
different track/set of tracks in completely the wrong
direction! This strikes me as a bad design flaw in the game.
If a train can see that a "good" route is currently at red,
but a "bad" route is green, it should wait patiently for the
"good" route to become available, rather than trundle off
down the "bad" route and hope for the best...

Correct me if I'm wrong, but I reckon that if trains were to
just wait patiently at red lights rather than doing one of
the two madcap things mentioned above, then things would be
fantastically better. After all, there should be no reason
for them to become permanently stuck at a red light for any
reason other than player error. Perhaps the necessary
alterations to train instructions could be made in a patch?

No, this would take away more advantage than it would bring.

OK, I will allow this to be optional! <g>

Unfortunately, this doesn't fix the long-range pathfinding
problem where if two destinations are far enough apart,
mayhem is guaranteed to follow! But fixing one out of two
wouldn't be bad...

This you cannot fix without rewriting the game. But if you construct your
networks according to this you have no problems:
Trains "look" only about 5 squares ahead in pathfinding. Then they decide by
the direction. Since there are only 8 directions this can be a problem for
goals in about the same direction but not exactly. So you have to build your
intersections where there is no misunderstanding where the tracks lead to.

That's good advice. Thanks! I don't think it's practical for
every situation, but nice to know all the same. So, when's
the patch coming out to increase the "5 squares"
look-ahead...?!?

-Mike [http://games.hplx.net]

[Mike Wagstaff]

Yeees.. but dont you use one-way signals? They will never turn round
after meeting a red one-way signal, and always wait until their original
path is clear.

As Josef said, even with one-way signals, the trains only
wait a month before giving up. Only a month?! Whatever
happened to patience?!

-Mike [http://games.hplx.net]

[Peter J. Dobrovka]

Mike Wagstaff schrieb in Nachricht

Maybe I didn't quite phrase that correctly. I didn't mean
that the train would take an alternate track leading the same
way; I meant that it would hurtle off down a completely
different track/set of tracks in completely the wrong
direction! This strikes me as a bad design flaw in the game.
If a train can see that a "good" route is currently at red,
but a "bad" route is green, it should wait patiently for the
"good" route to become available, rather than trundle off
down the "bad" route and hope for the best...

With one wayed signals I never saw a train going into the bad direction by
this reason. Maybe if the good track is blocked longer than a month...? But
under a good player this must not happen

Peter

[Mike Wagstaff]

<< With one wayed signals I never saw a train going into the bad direction by
this reason. Maybe if the good track is blocked longer than a month...? But
under a good player this must not happen >>

But I have to use two-way signals because I want more than
one track for each route. In other words, I want more than
one good track - but for that, I can't use one-way signals.
Which means that my trains sometimes go the wrong way...
Aaghh!!! I can't win!!!

-Mike [http://games.hplx.net]

[Peter J. Dobrovka]

Mike Wagstaff schrieb in Nachricht
<189182854509704NEWS...@news.dial.pipex.com>...

With one wayed signals I never saw a train going into the bad direction
by
this reason. Maybe if the good track is blocked longer than a month...? But
under a good player this must not happen

But I have to use two-way signals because I want more than
one track for each route. In other words, I want more than
one good track - but for that, I can't use one-way signals.
Which means that my trains sometimes go the wrong way...
Aaghh!!! I can't win!!!

For this problem there is again a nice solution: on the intersection use
only one-way-signals and split the track only AFTER the intersection. There
you can use two-way-signals, the one-way-signal is already passed...

As I see I use in my savegame the combination of 2 two-way-signals in
direction #1 and and one one-way-signal in direction #2, I will look what
happens if the one-way-signal is blocked...

Peter

[Mike Wagstaff]

For this problem there is again a nice solution: on the intersection use
only one-way-signals and split the track only AFTER the intersection. There
you can use two-way-signals, the one-way-signal is already passed...

It sounds like a very nice solution... I like it! I'll have
to try that one out and see if it improves matters... The
only problem I can think of is that it'll take up an extra
two squares, which could be a bit of problem the way I
play - if you saw my savegame, you'll understand! But, other
than that, thank you!

-Mike [http://games.hplx.net]

[Mike Wagstaff]

---West East---
C D
| |
| |
/| |\
| | | |
/| | | |\
/ * | | * \
------1-----2-----3--------A
------1-----2-----3--------B
\ * | | * /
\| | | |/
| | | |
\| |/
| |
C D

(Left-hand running)

It's a veritable work of art! But it still takes up too much
space for my liking... Mind you, it depends on the map you're
playing, and also the way you're playing.

-Mike [http://games.hplx.net]

[Mike Wagstaff]

A month! If you want your trains to wait for months at signals, you need
to change your layout!

Spoilsport!

-Mike [http://games.

[Peter J. Dobrovka]

Mike Wagstaff schrieb in Nachricht
<303872854503108NEWS...@news.dial.pipex.com>...

For this problem there is again a nice solution: on the intersection use
only one-way-signals and split the track only AFTER the intersection.
There
you can use two-way-signals, the one-way-signal is already passed...

It sounds like a very nice solution... I like it! I'll have
to try that one out and see if it improves matters... The
only problem I can think of is that it'll take up an extra
two squares, which could be a bit of problem the way I
play - if you saw my savegame, you'll understand! But, other
than that, thank you!

I just checked out the promised situation: If you have an intersection with
2 exit directions then one of then can have a double outlet (2 tracks, each
one with a 2-w-s). The other direction needs a single outlet with 1-w-s.
I stopped a train blocking the single outlet so that the 1-w-s was red. And
I looked what will happen if a train comes along and has to go into this
blocked direction. Will it choose one of the green 2-w-signals? - No! It
turned into the right direction and halted before the red signal, ignoring
the two green 2-w-signals which would have leaded into the wrong direction.

So the algorithm seems to be:
If the way that the train would choose without signal has a red
one-way-signal then the train keeps its precalculated route and waits for
green.
If there is a 2-w-s then (and only then) the train will look for another
2-w-s (and only for 2-w-s) and choose an alternative route if that is green.

Now after I understand this principle, my respect of the pathfinding of TT
has a bit grown. Maybe it would be a 100 times better if TT would be
programmed now in the era of 700 MHz PC's. The trains would look ahead 50 or
more squares...?

Peter

[Mike Wagstaff]

[snip!]
I looked what will happen if a train comes along and has to go into this
blocked direction. Will it choose one of the green 2-w-signals? - No! It
turned into the right direction and halted before the red signal, ignoring
the two green 2-w-signals which would have leaded into the wrong direction.

Yes. I looked at that as well and found the same as you.

So the algorithm seems to be:
If the way that the train would choose without signal has a red
one-way-signal then the train keeps its precalculated route and waits for
green.
If there is a 2-w-s then (and only then) the train will look for another
2-w-s (and only for 2-w-s) and choose an alternative route if that is green.

This really is delving into the depths of the game! But it's
useful information for building complicated route
interchanges, nonetheless...

Now after I understand this principle, my respect of the pathfinding of TT
has a bit grown. Maybe it would be a 100 times better if TT would be
programmed now in the era of 700 MHz PC's. The trains would look ahead 50 or
more squares...?

In fact, what would have been really clever was if the
look-ahead value (ie. the number of squares) could have been
dynamic, rather than fixed. Perhaps something could yet be done
about it, now that we all have PIII's and Athlon's... Is
there any chance of finding and altering this value - perhaps
even allow it to be set by the user???

-Mike [http://games.hplx.net]

[Phillip Michael Jordan]

Mike Wagstaff <a...@dial.pipex.com> wrote in message
news:42949605682854517079NEWS2LX@news.dial.pipex.com...

[snip!]
I looked what will happen if a train comes along and has to go into this
blocked direction. Will it choose one of the green 2-w-signals? - No! It
turned into the right direction and halted before the red signal,
ignoring
the two green 2-w-signals which would have leaded into the wrong
direction.

Yes. I looked at that as well and found the same as you.

So the algorithm seems to be:
If the way that the train would choose without signal has a red
one-way-signal then the train keeps its precalculated route and waits
for
green.
If there is a 2-w-s then (and only then) the train will look for another
2-w-s (and only for 2-w-s) and choose an alternative route if that is
green.

This really is delving into the depths of the game! But it's
useful information for building complicated route
interchanges, nonetheless...

Now after I understand this principle, my respect of the pathfinding of
TT
has a bit grown. Maybe it would be a 100 times better if TT would be
programmed now in the era of 700 MHz PC's. The trains would look ahead
50 or
more squares...?

In fact, what would have been really clever was if the
look-ahead value (ie. the number of squares) could have been
dynamic, rather than fixed. Perhaps something could yet be done
about it, now that we all have PIII's and Athlon's... Is
there any chance of finding and altering this value - perhaps
even allow it to be set by the user???
Heeeey! I have a P2! Anything wrong with that? eh?? eh????

OKOK only joking.. I do have a P2 350 though, but it should do fine on it
nevertheless.

Phillip

[Stephen Down]

Mike Wagstaff wrote:

One-way signals can't be used, as trains will then only go
down one particular track, rather than using the
alternatives which are all equally valid. However, from time
to time, all the tracks on that particular route will be in
use - and that's when things start to go wrong. Instead of
trains waiting for one of the tracks to clear, they decide
to take a completely different route! As a result, they end
up goint completely the wrong way and usually get hopelessly
lost.

I've never tried this, it's just a random thought, but it might work...

Have a single one-way signal beyond the interchange, and THEN branch out
into as many parallel tracks as you want with 2-way signals (works best with
pre-signalling as per Josef's patch).

This would only happen with a badly designed network, surely?

It depends.
In TTO, it could quite easily happen.
In TTDx, I'm sure there are times if you are building a complicated network
where it could happen, for example at a terminus station (if you are not
using Josef's patch).

[Stephen Down]

Peter J. Dobrovka wrote...

Trains "look" only about 5 squares ahead in pathfinding. Then they
decide by the direction. Since there are only 8 directions this can be
a problem for goals in about the same direction but not exactly. So
you have to build your intersections where there is no
misunderstanding where the tracks lead to.

Are you sure about that?
I read somewhere that the trains will look up to 64 squares ahead!

[Peter J. Dobrovka]

Stephen Down schrieb in Nachricht <84ljkp$lo...@newsg2.svr.pol.co.uk>...

Peter J. Dobrovka wrote...

Trains "look" only about 5 squares ahead in pathfinding. Then they
decide by the direction. Since there are only 8 directions this can be
a problem for goals in about the same direction but not exactly. So
you have to build your intersections where there is no
misunderstanding where the tracks lead to.

Are you sure about that?
I read somewhere that the trains will look up to 64 squares ahead!

They don't behave like this, definitively! Especially if you build
structures like the cleaf-crossing the trains love to run into wrong
direction.
But sometimes it seems to depend how near the next station is...

Peter

[Stephen Down]

Peter J. Dobrovka wrote:

They don't behave like this, definitively! Especially if you build
structures like the cleaf-crossing the trains love to run into wrong
direction.
But sometimes it seems to depend how near the next station is...

My trains certainly look more than 5 tiles ahead ~ I'm not sure about
64, that's just what I read. Are you sure all your signalling is
correct? Often a train needs to go in a totally different direction at a
junction in order to get to its destination, and it usually manages it.

[Chris Becke]

"Stephen Down" wrote:

Peter J. Dobrovka wrote:

They don't behave like this, definitively! Especially if you build
structures like the cleaf-crossing the trains love to run into wrong
direction.
But sometimes it seems to depend how near the next station is...

My trains certainly look more than 5 tiles ahead ~ I'm not sure about
64, that's just what I read. Are you sure all your signalling is
correct? Often a train needs to go in a totally different direction at a
junction in order to get to its destination, and it usually manages it.

They do look quite a number of tiles ahead. hwever, if that number of tiles
is insufficient to reach the station they are looking for... then they
fallback to a shortrange check "which rail seems to be going closer.

On very comples rail networks the look ahead seems reduced. There is a
scenario with many coal mines and just one powerstation at the far end of
the map. I played this for a bit and got quire frustrated when trains would
get lost by taking an incorrect turning right before the correct turn off.
The station they were heading for is visible on the same screen when fully
zoomed in - certainly less that 64 squares away.

Chris