YAPF - Testers needed!

KUDr · Post by **KUDr** » 12 Oct 2006 16:55

bobingabout: hey, wake up! What solution are you mentioning again and again? You either totally ignore what i try to explain you or you misundertand because of my limited english skills.

NPF doesn't decide to ping-pong! NPF gave up and routed you just "somewhere". For NPF it is the same situation as "no route found". Just blind decision "should i go lef or right?" is made different way. This is not solution at all as it doesn't work always. Try to play with different track layouts and you will see what i am talking about.

You just found the case when the blind decisions differ (between NPF and YAPF) and accidentally the final result was better with NPF. But your track layout is wrong, not YAPF in this case. I can give you another example (same principle, just different layout) where the result will be just opposite.

Please read again all above and try to understand it finally. My patience is limited, while your ignorance seems not.

DaleStan · Post by **DaleStan** » 12 Oct 2006 17:49

No.

The pathfinder serves the rail, not the other way around. If a path exists that pathfinder cannot find, then the pathfinder is wrong. Just because all the other pathfinders are also wrong in the same situation doesn't make this particular pathfinder any less wrong.

KUDr · Post by **KUDr** » 12 Oct 2006 18:13

DaleStan: hehe. As usually, in the theory you are right. But, you lost the point.

1) the discussion was about the "solution" used by NPF and about comparison between YAPF and NPF. Not about "ideal" pathfinder. Bobingabout doesn't understand why his particular case works with NPF, but not with YAPF. We are not trying to discuss the "ideal" or "perfect" solution as it would be senseless.

2) I am not perfect developer so my PF is also not perfect. Try to make better pathfinder that will take into consideration also dead ends. You will see that it is not so easy. I don't want to support all corner cases. There must be some limit. When I worked on YAPF, everybody told me that NPF works well, only it is slow. I used NPF as the reference PF during development. There are many other requirements (like performance, load balancing, extensibility, configurability, maintenability, flexibility and so on), that are much more important. I will not make YAPF significantly more complex (and buggy) just because you want it.

3) I don't think that supporting unreasonable "paths" would be considered as reasonable. Next time you will tell me: "the path through one way signal in the wrong direction is also a path, so PF should support it". Where is the limit for such stupid requirements? We can discuss it for long time, but i don't think we can agree.

4) If you want to use such "unresonable path" you can normally use waypoint(s) to help the pathfinder. Just accept, that nothing what is made by human is perfect.

RiTi · Post by **RiTi** » 16 Oct 2006 12:02

KUDr wrote:[Last message reply]

To give some positive feedback I give you my experience with YAPF in general.

I run a game with 1.111 trains (some are huge, some are small) on a big map. When I play the game with NPF at about 600 trains the game slows down. With YAPF the game starts slowing down at 800 trains.

The most trains have a "full load" option. With YAPF the trains leave the station almost directly when they are full. With NPF the trains are still waiting for some time before they leave.

I have made a large railroad network, heavy crossings and therefor much traffic and possible jams. With YAPF when two trains arrive at a crossing, the first one who was at the crossing goes first (as it has to be). With NPF this isn't always the same (sometimes the train who arrived second goes first).

So far with YAPF I have no problems playing the game I want to play it. I think you (and others?) made a good job and I am pleased with it.

bobingabout · Post by **bobingabout** » 16 Oct 2006 12:30

KUDr wrote:Bobingabout doesn't understand why his particular case works with NPF, but not with YAPF.

i understand perfectly well, Yapf is flawed because if no route is found, it goes to a depot. if a route is still not found, it goes to the next depot, which is actually back to the first, meaning the train will just constantly go to a depot and never manage to find a way to its destination. NPF however, if no route is found, it heads in the general direction, this general direction often leads to a deadend or a station, where it can turn around. the way i design my tracks, this always resulted in a lost train finding itself on the right path, this was true with OPF, NTP and NPF, but not YAPF, because the first 3 go in the general direction, but YAPF changes the rules and instead of going in the general direction, goes to a depot instead, this results in my networks, which have worked for over a decade, to not work anymore.

MagicBuzz · Post by **MagicBuzz** » 16 Oct 2006 12:56

If I just can say a word...

bobingabout, it's a miracle the others PF can find a path in your tracks. I won't blame YAPF for being unable to find a way is your network. I just can't find anyone myself. In french, I could say "Une chatte n'y retrouverait pas ses petits" (A cat wouldn't be able to find its babies in it)

I think KUDr is true when he says it's "stupid" to make the YAPF working well in any case, even the most "stupid" ones.

Just start to make a clear network, then any PF would be able to find a way. Don't try to exploit the PF bugs to get it work as you want, just make track correctly so the PF can work as desired.

MeusH · Post by **MeusH** » 16 Oct 2006 20:00

It would be great if train that can't find a way, should stop in a depot and display a message, instead of pointless cruising between depots. What do you think about that?

XeryusTC · Post by **XeryusTC** » 16 Oct 2006 20:06

SVN changelog wrote:KUDr * r6791 /trunk/yapf/yapf_rail.cpp: -Fix: [YAPF] YapfFindNearestRailDepotTwoWay() did not work for train inside tunnel.

KUDr forgot to credit me, so I do it here myself

.

Brianetta · Post by **Brianetta** » 16 Oct 2006 21:24

MeusH wrote:It would be great if train that can't find a way, should stop in a depot and display a message, instead of pointless cruising between depots. What do you think about that?

Sometimes a route can be found from another depot. Perhaps it should just maintain a small list of depots that it's been to since it first failed to complete a route, and stop if it returns to any of them.

RiTi · Post by **RiTi** » 16 Oct 2006 22:21

MeusH wrote:It would be great if train that can't find a way, should stop in a depot and display a message, instead of pointless cruising between depots. What do you think about that?

Instead of a message it's maybe easier to give the depot itself a color:

Brown, standard color no train in it
Green, train in it, with order to leave
Red, train in it on hold (not started yet or lost).

You can couple the depot color to the flag color of a train. If a green and a red flagged train are in depot then the depot is red (red is a higher alert then green).

MeusH · Post by **MeusH** » 16 Oct 2006 23:14

Brianetta wrote:
MeusH wrote:It would be great if train that can't find a way, should stop in a depot and display a message, instead of pointless cruising between depots. What do you think about that?
Sometimes a route can be found from another depot. Perhaps it should just maintain a small list of depots that it's been to since it first failed to complete a route, and stop if it returns to any of them.

Then we may set a limit of depots to visit...

RiTi, I still think messages are much easier to do code-wise, they would be also noticed. It's unlikely for a depot to be seen if I'm currently placing tracks in a other part of the map...

KUDr · Post by **KUDr** » 17 Oct 2006 07:53

Heh, thanks for replies. Bobingabout still understands nothing or he tries to make me more and more angry. Nobody can be so stupid i guess.

Last attempt to clarify it (hopefully):
1. The behavior of NPF and YAPF in the situation when no route was found is EXACTLY THE SAME. They both navigate you just "somewhere".
2. NONE OF THEM PREFERS DEPOTS or something mysterious what you call "GENERAL DIRECTION". Both do just blind guess.
3. But both are deterministic. So both can repeat their behavior again and again if you give them the same input data (track layout, source, destination, etc.).
4. Your crazy example just shows the situation called "user error". None of PFs you have tried can find the path. All of them make pseudo random decison where to go next on each crossing. Just because you were "lucky" you have found the special case where:
- one deterministic random behavior accidentally leads to the dead end (so train can reverse there and try it again from better position)
- while other one, also deterministic will forever cycle between depots (just because of different random generator it uses).

Or you may better understand this:
Your network is controlled by pseudo random generator. It works perfectly when the number '3' is beween first 10 generated numbers. One generator you tried accidentally has number 3 as the first number it generates, while the other one not. Is the other one broken? Or is it your network, what is broken here? Try guess

MeusH: I agree. There should be such message. It would eliminate such crazy discussions as user could immediatelly see that all PFs have the same problem with his network.

Also for normal user it can be helpfull to see that his last track changes have broken some routes. But how to show it? Standard message for each such train? Or one message only with just one train number? Or message + train color in the train list?

Post by **peter1138** » 17 Oct 2006 08:27

Well, there is the old 'vehicle lost' message. Maybe just have something like that but triggered (once, somehow) when a vehicle can't find a path, instead of a few months down the line...

I don't think adding 'dead-end' routing would work that well. Generally there are a lot of dead ends for it to try. This might result in a vehicle taking a very long route compared to a fixed network.

KUDr · Post by **KUDr** » 17 Oct 2006 08:33

Brianetta wrote: Sometimes a route can be found from another depot. Perhaps it should just maintain a small list of depots that it's been to since it first failed to complete a route, and stop if it returns to any of them.

NPF and YAPF plan routes through depots. The number of depots that can be visited during one route plan cycle is not limited. But each depot can be visited only once for one particular route.

PF is invoked every time the train needs to choose (left, middle, right) track on the junction. It starts with the "clear state" - no information is maintained between runs. So it can happen, that train will cycle between depots if it can't find its way.

The problem with dead ends is that if we want to support them we must take into consideration also train length and the way it came from. When the train's engine reaches the dead end, the train can still stay on junction(s). Those junctions must not be treated as junctions in that case. When train reverses, it can't choose different track there. This is the reason why dead ends are not supported by PFs. It would be unreasonably complicated to do it and the only benefit would be "one bobingabout less to worry about".

Depots are different story. There are 2 major differencies between depots and dead ends:
- train always fits in the depot (no matter how long the train is, no special logic is required for long trains)
- it may be reasonable to force train to go through depot (maintenance, train accumulators, etc)

This is why NPF and YAPF support planning routes through depots.

KUDr · Post by **KUDr** » 17 Oct 2006 08:49

peter1138 wrote:Well, there is the old 'vehicle lost' message. Maybe just have something like that but triggered (once, somehow) when a vehicle can't find a path, instead of a few months down the line...

Good idea. Maintaining the train routing status (just one flag 'no route to destination') + simple logic:
- when it is set to TRUE, message is generated.
- Any successfully found route will clear this flag to its original state (FALSE).
- flag probably doesn't need to be stored in savegames

Up to here i can do that. Can someone help me with the rest (message) please?

Does it need to be configurable (_patches)?

Post by **peter1138** » 17 Oct 2006 08:53

Use the existing setting for lost trains, I think. Maybe even copy the code that shows the lost train message...

KUDr · Post by **KUDr** » 17 Oct 2006 09:04

same string or different one? User can get confused with the same message.

Brianetta · Post by **Brianetta** » 17 Oct 2006 09:09

Same string. The message is absolutely correct in this case, whereas t used to mean "I haven't completed this order for 180 days" (or whichever value was specified). Since NPF, a train's time since completing an order is not an indication of a lost state, because the pathfinder is complete.

I'd suggest that the message be displayed on a time basis only when using the NTP pathfinder (or other incomplete pathers). When using NPF or YAPF, the game should instead use the pathfinder to decide when to announce a train as lost.

KUDr · Post by **KUDr** » 17 Oct 2006 10:16

WOW! It works fine with YAPF. Only not sure how to decide if proceed with message or not based on _patches.lost_train_days. Show it only when it is nonzero number there?

Or should I suppress the old way of reporting? Then the "number of days" is bit inappropriate.

Edit: now it works with NPF too!

KUDr · Post by **KUDr** » 17 Oct 2006 10:31

Now it works with all 3 pathfinders. Only what i am missing on this feature is different color of the "Heading for blabla station" in the bottom of the train window if train has no path found.

So theoretically the old way can be replaced by new one. What do you think?

Transport Tycoon Forums

YAPF - Testers needed!

Who is online