Topic: No transfer at overcrowded stations.

[Lord Vetinari]

I know that there's the "no route over overcrowded" option in simuconf, but I mean something a little different.

In late games, the network can be quite complex, and usually you end up with more than one transfer option for the same destination. The game chooses the first one available (which is good, it makes the things predictable), and stick to that even if it becomes overcrowded. I'm suggesting that if the first transfer option is overcrowded, the next time the route is calculated, the next option is chosen. If no other transfers are available, normal behaviour is applied.

Or, if this is too hard or requires too many computing power, an option in the station dialogue window to manually switch off the transfers at that stop (even better if you can choose which lines can't transfer there, so that you can still use, for example, buses to feed up the station/dock/airport, but you can't transfer from a train or ship to another) can work as well.

[Fabio]

an option in the station dialogue window to manually switch off the transfers at that stop (even better if you can choose which lines can't transfer there, so that you can still use, for example, buses to feed up the station/dock/airport, but you can't transfer from a train or ship to another) can work as well.

this sounds interesting

[Lord Vetinari]

YEs, now that I think about it, it seems the better and more flexible solution.

[IgorEliezer]

Way better than destructing a part of a network and rebuilding it over again with bigger capacity.

If I was a passenger and I want to go from A to D with possible routes A-B-C and A-C-D and I'm warned that B is overcrowded, I'll take C.

I still remember the day that I surprisingly discovered that one of my lines got empty because I had built another line somewhere else. If not wrong, the new line was a line of small capacity, and then the main one gradually became unused and everything messed up. I was forced the undo what I have done. :(

[Dwachs]

This is a very sensible request, and I wonder why it was not implemented this way.

There was an extensive discussion in the past

http://forum.simutrans.com/index.php?topic=1040.0

but I do not know what the conclusions were.

[prissi]

This would mean for any destination lots of routes more must be tested in later games after each schedule change, where this already eats up considerable calculation time. Furthermore such things usually generate oscillating routes and in the end everything is overcroded instead only the hubs that really needs attention.

[Lord Vetinari]

Yes, the more I think about the automatic option, the more it seems a bad idea.

But what about the manual option? In that case there souldn't be any additional calculation time or random result, as it's all set by the player. If not at the stop, it could be done in the line schedule.

[prissi]

Single (not get off/no get off) stops would be possible within the current system. However I fear for inexpected behavior, which is then labled as bug again.

Furthermore, after getting all the money you can dream the ultimate challenge is to keep everything reasonable working, isn't it?

[knightly]

This would mean for any destination lots of routes more must be tested in later games after each schedule change, where this already eats up considerable calculation time. Furthermore such things usually generate oscillating routes and in the end everything is overcroded instead only the hubs that really needs attention.

If a hub is seriously overcrowded, why couldn't the player choose to relieve the overcrowding by providing a comparable alternative route? Why should we dictate how the players deal with the overcrowding condition, forcing them to tackle the problem at the overcrowded hub? Even database servers may use load-balancing to tackle enormous traffic load, why should we forbid our transportation networks to have parallel routes? IMHO this is limiting the freedom of players.

And what is the problem with finding different routes at different times? If conditions change, choices also change. The current implementation is like this : calculate the first route with the minimum number of transfers; when a route is found, if "no route over overcrowded" option is set, check if any transfer in that calculated route is overcrowded; if yes, consider that route as bad and abandon the trip. This is simply absurd. Sensible routing would consider overcrowding status during route search, not after. I agree that games are supposed to simplify reality, but such ridiculous logic is not simplification.

Besides, in multi-player games, such deterministic, non-oscillating search may lead to overcrowding of one player's route and starvation of another player's route.

I know that you want to keep things simple, as you think that the game is already difficult enough. But to keep the game simple does not necessarily mean keeping things static; and keeping things static does not necessarily make the game simple. In this case, players would expect pax/mail/good to make dynamic choice of routes depending on existing conditions; keeping the routes static will only go against the players' expectations and confuse them -- many players asked in the past why an alternative route is never/seldom utilized.

[prissi]

Well the overcrowded flag was introduced to reduce the number of traveling passengers. If they were just rerouted, it would defy this purpose.

But on another note, I see your argument. Especially the multiplayer argument is very valid, and such a behaviour may be even needed for competition. (Although it should be configurable, since it changes between cooperative gaming with public transfer hubs and competitive gaming with parallel networks.)

[jamespetts]

Simutrans-Experimental has a means of dealing with this situation, although in a somewhat more subtle way. In Simutrans-Experimental, the more crowded that a station/stop is, the longer that people will have to wait to get on their next mode of transport. Each month, the routes are recalculated, and the fastest route overall is selected; the waiting times are included in the calculation of the journey time of any given route. This way, automatic and realistic load-balancing is achieved without any more overhead than is necessary to implement the journey time based routing system in the first place (which is a little more than that required for the simpler system in Simutrans-Standard, but not so much that my 7-year-old computer can't handle it without difficulty on even a very large map).

[knightly]

Well the overcrowded flag was introduced to reduce the number of traveling passengers. If they were just rerouted, it would defy this purpose.

I understand that the original intention of the overcrowded flag is to help a player to understand why the routing doesn't work. However, please take a step back and look at the situation again : if the main route [as calculated by suche_route()] plus the parallel route(s) have a sufficient enough combined capacity to avoid overcrowding, but ends up only the main route is utilized, this overcrowded flag is actually raised as a consequence of such deterministic, non-oscillating route search, and does not correctly reflect the real situation. The overcrowded flag is founded on a flawed assumption -- that overcrowding cannot be circumvented by taking an alternative route.
Edit : If there are too many pax, we should fix the problem in pax generation code instead.

But on another note, I see your argument. Especially the multiplayer argument is very valid, and such a behaviour may be even needed for competition. (Although it should be configurable, since it changes between cooperative gaming with public transfer hubs and competitive gaming with parallel networks.)

IMHO cooperative gaming does not require deterministic, non-oscillating routing any more than a single player game. If two players choose to use public interchanges, those interchanges will become the only connection points between their respective networks and routes must go via those interchanges anyway. The routing mechanism is essentially the mechanism of how Simutrans citizens choose their routes; I fail to see why they should evaluate routes differently just because of different game modes (single vs multi player).


As to the original problem of this thread, one problem is that the next transfer is cached and do not change if it becomes overcrowded. This can be solved by checking overcrowdedness of next transfer while loading the pax/mail/goods, and recalculate the route where necessary.


Drawing from the experience of EXP, I would consider the following as desirable changes to the routing mechanism :
1> a criterion on search which encompasses factors like number of transfers, number of stops, convoy/line nominal speed, nominal waiting time
    -> cached as the basis of route comparison, to be used in route searching and for comparison in <4> below
2> cache the best line/convoy
    -> used in <4> to determine distribution of pax/mail/goods loading
3> route search with multiple start halts
    -> this is essential to allowing fair competition; this can be done with a single search
4> proportional distribution of pax/mail/goods during loading at stops
    -> this avoids all-or-nothing distribution and allows room for survival of the weaker competitors
It would also be a good idea to consider the following at the same time :
5> journey tolerance
    -> calculated with a simple formula, for capping the search and preventing unreasonable detour
6> preference for local/nearer destinations
    -> more reasonable distribution of pax destinations; Z9999 seems to have a patch on this
Of course, I am not suggesting to implement these in the same way as EXP does, or copying its code. We just borrow the concepts, and we implement it in a way suitable to Standard.

[prissi]

I think I would avoid rerouting of passengers already en-route. Rerouting will be happen anyway during stop extension, adding of new vehicles etc. The different route should imho rather apply for route search, i.e. only new passengers (or passenger first arriving at a tranfer) will find this route.

And such flag is mandantory for competitive network gaming. But again, you nearly convinced me, that it will not harm normal gaming with single exchange hubs.

EDIT: All (few) really heavy loaded games I had (with more than 4000 convois) either crashed experimental or were completely unresponsive. Kepping in mind that the slowest computer in a network game limits the game ... And a month without fast forward can be very long, so it could take very long until new routes propagate.

Multiple start search is probably rather an option if there is no route on the first step for pax. For industry this can be easily added (and is imho done, if I remember correctly, you can compete with an AI for oil for instance.)

[jamespetts]

EDIT: All (few) really heavy loaded games I had (with more than 4000 convois) either crashed experimental or were completely unresponsive. Kepping in mind that the slowest computer in a network game limits the game ... And a month without fast forward can be very long, so it could take very long until new routes propagate.

Prissi - can you upload the games that crashed Experimental so that I can check to see if I can track down the problem?

[knightly]

EDIT: All (few) really heavy loaded games I had (with more than 4000 convois) either crashed experimental or were completely unresponsive. Kepping in mind that the slowest computer in a network game limits the game ... And a month without fast forward can be very long, so it could take very long until new routes propagate.

I am not suggesting to use Floyd-Warshall algorithm, which computes all possible paths between 2 halts in both directions. So, the EXP situation is irrelevant to the current discussion. Just as I said, we adopt the concepts, not implementation. If you still remember, last year I attempted to rewrite the search code (I still have an outdated copy), and told you that search speed was roughly like before my transfer-centric route-searching patch got committed. And there should still be room for improvement.

Multiple start search is probably rather an option if there is no route on the first step for pax. For industry this can be easily added (and is imho done, if I remember correctly, you can compete with an AI for oil for instance.)

If 2 players' halts are adjacent to each other, when new pax are generated in the vicinity, shouldn't both halts be compared to see which starting halt can transport the pax faster to their destination? Without such check, how can there be fairness in multiplayer games?

[prissi]

@jamespett
Unfourtunately those are really large games, the biggest with tons of addons. Do you have an emails that can handle 100 MB+? Please email me.

The main concern I have is that "fast" is also arbitary, especially when same destinations are served by different convois simultaniously. For fairness the criterion should be predetermined, like total number of stops or total distance travelled, weighted by transfers or number of convois between two destinations and their theoretical max speed. However, every deeper convoi like investigation could require much more time rerouting for lineless convois, so it has to be weighted.

I am not sure I remembered your patch correctly; could you give me a pointer to the thread? (This forum seems to work very crappy for me at the moment, with lots of error messages ... )

[whoami]

Regarding oscillating/unstable routing: if there was a method to stabilize this, a modification to the routing algorithm (choosable with no_routing_over_overcrowded = 2?), which allows alternative routes, might become within reach. Some ideas (some may have been mentioned before):
1) re-test the overcrowding state of a station only with low frequency
2) instead of the overcrowding flag, take the level of crowdedness as a routing malus
3) choose a random route from the possible ones
combining 2) and 3): take this malus into account for probability; combine with 1) to make this stable

Another approach: snapshot pointer/counter
Let's store the network state in each goods packet, so the original routing decision (at passenger generation/goods release) is retained. Totally crazy idea? The idea is to store only an identifier (perhaps an 8 bit number) into the goods packet *or* the containing convoy, pointing to a 'snapshot', i.e. the overflowing state of transfer stops at a certain point of time in the past. For this, the stops have to have a kind of history (obviously, a method to identify real transfer stations is useful to keep space requirements low). The larger the network is (in terms of travel time), the longer the time between two snapshots will have to be (variable time resolution).
By this, the original routing decision can be repeated, I hope.

More details:
What happens when the counter has to change to a value already in use? Either keep them as they are, or else all packets/convoys will be checked for packets with that value, and those packets should expire: set the counter to a reserved value, e.g. 0, to mark them as obsolete - discard them at their chosen transfer stop or any next stop - *or* revert to standard routing (do not check for overcrowded state). Regarding the "black hole" argument against discarding: these packets will have used a lot of capacity x time, blocking other customers from being served, perhaps generating no revenue in the meantime (depending on pay_for_total_distance setting).
If the counter is attached to the convoy, the re-routing decision at the next transfer stop would still be influenced by the olf value (however, we need to synchronize the convoy at each stop, at least each real transfer stop), so we have at least stabilizing effect for the time between two stops.
If the counter is attached to the goods packet, it could also serve a purpose in a different revenue calculation scheme (using overall travel time), but then variable time resolution cannot be used.

[Isaac.Eiland-Hall]

emails that can handle 100 MB+? Please email me.

Wouldn't FTP be easier? I can easily set up a private FTP connection and send the details to the both of you.

[knightly]

And such flag is mandantory for competitive network gaming. But again, you nearly convinced me, that it will not harm normal gaming with single exchange hubs.

Sorry, forgot to ask : why is the overcrowded flag mandantory for competitive network gaming?

The main concern I have is that "fast" is also arbitary, especially when same destinations are served by different convois simultaniously. For fairness the criterion should be predetermined, like total number of stops or total distance travelled, weighted by transfers or number of convois between two destinations and their theoretical max speed. However, every deeper convoi like investigation could require much more time rerouting for lineless convois, so it has to be weighted.

Well, there indeed are various issues to sort out for the criterion, like : what about running a 120km/h bus on 50km/h city road? For lines, the best we can do is to take the minimum of max theoretical speed of all involved convoys (do we need to calculate per goods category?).

I am not sure I remembered your patch correctly; could you give me a pointer to the thread? (This forum seems to work very crappy for me at the moment, with lots of error messages ... )

There was no thread and no patch posted. Since that was experimental in nature, I only discussed with you via PMs (that was before the Programmers' Corner was set up). I stopped working on that patch, because at that time Gerw said he might make some big changes to the system. I can try to work on it again, but only if you are committed to revamping the routing system -- it takes time to understand the relevant parts again, so I don't want to restart unless you have the resolution to do so and until there is a complete blueprint for the new routing system.

The only thing I can say at the moment is that, search speed of my patch (also using Dijkstra) was acceptable, but definitely not as fast as current implementation as the current one is a special case which doesn't even require a min heap to keep the open nodes in order.

[jamespetts]

Wouldn't FTP be easier? I can easily set up a private FTP connection and send the details to the both of you.

That would be helpful - thank you!

[Isaac.Eiland-Hall]

Accounts set up and PMs sent to Prissi and jamespetts...

[prissi]

Back to the slightly off-main topic:

As Knightly pointed out, choosing alternative routes for crowded conditions is required for competitive network games.

I would not change routes after a pax is enroute; normal passengers change routes only in transfer stations and not suddenly in between. I would keep this the good records as they are.

For weighting connection, maybe the possbile capacity (or maybe even available capacity) for the statistisk of line/convoi could be a good measure of a connections. It could be the sum of (capacity*max_speed)/distance+intermediate_stops of each convoi going on that connection. Same for transfer stops, where the overcrowding in percent could give a malus. This could work for a connection search similar to the way searcher, even testing the condition of reached the destination and otherwise choosing the route with highest number. A* seem not possible, since I have no idea how to define a metric on the connections.

Alternative start stops would increase the calculation time, since always the whole connections tree would have need to be searched.

[knightly]

Back to the slightly off-main topic:

Maybe our discussion should be splitted and moved to Development and Bug section?

I would not change routes after a pax is enroute; normal passengers change routes only in transfer stations and not suddenly in between. I would keep this the good records as they are.

Please read carefully. I did not suggest to change routes when the pax are on board; I said, check and change route where necessary at the transfer when the pax are about to be loaded onto the convoy.

For weighting connection, maybe the possbile capacity (or maybe even available capacity) for the statistisk of line/convoi could be a good measure of a connections. It could be the sum of (capacity*max_speed)/distance+intermediate_stops of each convoi going on that connection. Same for transfer stops, where the overcrowding in percent could give a malus. This could work for a connection search similar to the way searcher, even testing the condition of reached the destination and otherwise choosing the route with highest number. A* seem not possible, since I have no idea how to define a metric on the connections.

Considering available capacity is a good idea. However, if you incorporate it, any significant change should trigger refresh, or have periodic refresh. Yes, players may build halts, update lines, etc., but players may also run the game in fast forward for a year without intervention -- in that case, the data may become obsolete. As for transfer overcrowding level, I think we should forbid routing via overcrowding transfer altogether -- it's ridiculous to have 100K people waiting at a 1K capacity halt. BTW, you haven't answer my question : why is the overcrowded flag mandantory for competitive network gaming?

As for the forumla, adding intermediate_stops to distance is understandable, but why speed over distance instead of the other way round? And why available capacity x speed? It seems to give available capacity too much importance than it deserve. Compared to capacity, service frequency (how long to wait between consecutive convoys) may be even more important.

Besides, can you also make some comments on points <2>, <4>, <5> & <6> above?

Alternative start stops would increase the calculation time, since always the whole connections tree would have need to be searched.

Of course, everything comes with a cost. But then, if you are one of the multiplayers, and you have a stop adjacent to your opponent, but your opponent's stop attracts all pax for no apparent reason, how will you feel? Is it fair?

As you can see, implementing network mode implies a lot of changes to the core code. And frankly speaking, EXP is far ahead of Standard with regards to multiplayer games.

[prissi]

BTW, you haven't answer my question : why is the overcrowded flag mandantory for competitive network gaming?

I never said this; different routes changing with overcrowding needs to be considered, as you suggest. Maybe this is a misunderstanding.

Currently different routes are only considered with goods. Here the capacity of the starting stop is the ultimate limiter, since truck stops are very fast overflowing comparing to train stations. This is not problematic calculationwise, since there are a limited number of factories and transfers for them on a map.

Please read carefully. I did not suggest to change routes when the pax are on board; I said, check and change route where necessary at the transfer when the pax are about to be loaded onto the convoy.

When there is a rerouting, people a intermediate stops will be rerouted anyway. Also since passengers are frequently merged, remembering a decision seems difficult. But it may not be needed: If you have traveled via boat to the airport of the next island, it would not shorter to go again back take the transfer bus to the train station and then go the other route unless the current one is a very bad connection routingwise. THus only a few passenger will reroute. I hope this answers also

Besides, can you also make some comments on points <2>, <4>, <5> & <6> above?

thus, I think I would rather avoid storing the initial decision "network state", since it is not needed, because traveler en route will not all travel back that far to go a new route.

but players may also run the game in fast forward for a year without intervention -- in that case, the data may become obsolete.

The longer I am thinking the more I would favour theoretical capacity. Running a game 1 year without intervention defies the aspect of gaming "aka interaction" a little; furthermore it would just generate the current situation, which is not entirely bad, as people have been fairly content with it for the last 12 years ...

About the formula: The better connection is the one with a higher throughput which means passengers/time. Taking a passenger with 1000km/h or 10 passenger with 100km/h will transport the same number over 1000km (1 passenger/h). Thus capacity*speed/distance give passengers/time [in simutrans units]. On average it will be proportional to the time between consecutive convois [assuming they are not stuck somewhere] but will be more reflect the player's intention. (Maybe the intermediate stop number should not be used anyhow.)

And on a side note: Network games tend to be larger than normal games (at least judging from OpenTTD). Thus I would keep this in mind.

[whoami]

I would not change routes after a pax is enroute; normal passengers change routes only in transfer stations and not suddenly in between.

I did not suggest to change routes when the pax are on board; I said, check and change route where necessary at the transfer when the pax are about to be loaded onto the convoy.

I think that, even with re-routing only at transfers, oscillating routes (causing passengers to move back and forward) will happen in nontrivial networks. That's the reason why I made the suggestion above (maybe this wasn't clear). How are you going to stabilize that without storing any information about the original routing decision, no matter how that is calculated? OTOH, how about just implementing alternative routing (load-balancing) within the current routing system, leaving its activation and evaluation of the effects to the user? Maybe it is already sufficient for most cases. It may be necessary to differentiate between pax+mail (many small packets, which however aggregate at transfer stations) and goods (mostly huge chunks with one destination from generation onwards).

Regarding merging of packets: for my suggestion, this would be possible to some extent: merge packets where the following transfer stop has the same state, according to the referenced snapshots.

[knightly]

@Prissi

When there is a rerouting, people a intermediate stops will be rerouted anyway. Also since passengers are frequently merged, remembering a decision seems difficult. But it may not be needed: If you have traveled via boat to the airport of the next island, it would not shorter to go again back take the transfer bus to the train station and then go the other route unless the current one is a very bad connection routingwise. THus only a few passenger will reroute.

I got your point here, and actually I did not object to your previous reply (that's why I made no further response). So we may drop this topic and focus on other issues.

I hope this answers also

Besides, can you also make some comments on points <2>, <4>, <5> & <6> above?

thus, I think I would rather avoid storing the initial decision "network state", since it is not needed, because traveler en route will not all travel back that far to go a new route.

I don't quite follow here : <2> is about best line/convoy, <4> is about loading what % of pax (for different lines/lineness convoys connecting current halt to the same transfer) <5> is about journey tolerance and <6> is about preference for local/nearer destinations. What have these to do with `storing the initial decision "network state"`?

The longer I am thinking the more I would favour theoretical capacity. Running a game 1 year without intervention defies the aspect of gaming "aka interaction" a little; furthermore it would just generate the current situation, which is not entirely bad, as people have been fairly content with it for the last 12 years ...

Well, players may sometimes fast forward a few months to accumulate enough money for further investment, so such fast forward is actually part of the game play But of course, if you use theoretical capacity, that would not fluctuate.

About the formula: The better connection is the one with a higher throughput which means passengers/time. Taking a passenger with 1000km/h or 10 passenger with 100km/h will transport the same number over 1000km (1 passenger/h). Thus capacity*speed/distance give passengers/time [in simutrans units]. On average it will be proportional to the time between consecutive convois [assuming they are not stuck somewhere] but will be more reflect the player's intention. (Maybe the intermediate stop number should not be used anyhow.)

I see. However, according to your example, although throughput is the same, customer experience is different -- it takes much shorter time (time saving) to travel with that 1000km/h convoy, right? As for convoy frequency, 1 convoy with 1000 capacity yields the same result as 10 convoys with 100 capacity (ceteris paribus), but the service frequency (and hence convenience) is better with 10 convoys. As I have said earlier, the routing mechanism is the mechanism by which citizens choose their route; normal people do not consider throughput, but consider cost, journey time, waiting time, comfort (overcrowding), convenience (service frequency). As for intermediate stops, I think it should be included as they lead to longer journey time.

@whoami

I think that, even with re-routing only at transfers, oscillating routes (causing passengers to move back and forward) will happen in nontrivial networks. That's the reason why I made the suggestion above (maybe this wasn't clear). How are you going to stabilize that without storing any information about the original routing decision, no matter how that is calculated?

Actually, both Prissi and I now agree that there is no harm to have oscillating routes -- oscillating routes does not mean oscillating travel, which happens when pax move from A to B and from B back to A again as you wrote. Oscillating routes here means, that suche_route() will generate different routes between the same origin and destination at different times to circumvent overcrowded transfers; mainly only new pax are affected. And from Prissi's previous reply to my queries, it seems that he wants to avoid storing the inital routing decision. But let's hear his opinions on this.

[prissi]

I would avoid storing the intial routing decision, as it will be unmergable or, seeing, how long passsengers stay in transfer stops, it will get stale fast.

Now I got you question for 1-6:

2> cache the best line/convoy
    -> used in <4> to determine distribution of pax/mail/goods loading
4> proportional distribution of pax/mail/goods during loading at stops
    -> this avoids all-or-nothing distribution and allows room for survival of the weaker competitors
5> journey tolerance
    -> calculated with a simple formula, for capping the search and preventing unreasonable detour
6> preference for local/nearer destinations
    -> more reasonable distribution of pax destinations; Z9999 seems to have a patch on this

2> not needed with static criteria
4> is implmented for goods. Passenger and mail start their journey usually at bus stops which overcrowd very fast if not a frequent service is used. Therefore it might be enough to start alternate stop search only when first stop is overcrowded (and that is already done).
5>
6> Passenger will not travel if the destination catchment area include the starting tile, but will generate happy passengers. Imho that is ok be me. I do not see this unreasonable, it happens mostly in the city center, where a high probability of selection a building. But I will test this.

[knightly]

2> not needed with static criteria
4> is implmented for goods. Passenger and mail start their journey usually at bus stops which overcrowd very fast if not a frequent service is used. Therefore it might be enough to start alternate stop search only when first stop is overcrowded (and that is already done).
5>
6> Passenger will not travel if the destination catchment area include the starting tile, but will generate happy passengers. Imho that is ok be me. I do not see this unreasonable, it happens mostly in the city center, where a high probability of selection a building. But I will test this.

<2> are for cases where two or more lines (or lineless convoys) serve between current halt C and the next transfer T. Since T would be calculated based on the best line/transport between C and T, if only the next transfer is stored, any convoy (even rather slow ones) serving between C & T will load the pax/mail. It is possible that taking a suboptimal transport is worse than taking an alternative route, thus defeating the purpose of finding the best route. <4> is based on the best line/linesless convoy in <2>, to give full loading to optimal lines/lineless convoys, and to give a reasonable share of load to suboptimal lines/lineless convoys. [Of course, if T is determined based on the worst line/transport, both <2> and <4> are unnecessary.]

Please note that <4> is not multiple start-halt search; <4> is done at loading, not during route search. Multiple start-halt search is for assigning pax fairly to the start half of the faster route among the different routes of the players -- currently pax is assigned to a random start halt, which is unfair. I would suggest you reread the relevant parts of my previous posts to fully understand why multiple start-halt search is essential to multiplayer game.

Let's just leave <5> for the moment if you have no idea what I am talking about.

People who walk to their destination should not be counted as happy passengers -- passengers by definition are those who take a transport. Treating those who walk as happy pax are exaggerating the happy ratio and giving players an inaccurate picture of the real situation. Having said this, what is the relation of "walking" to "preference for local/nearer destinations" as suggested in <6>?

Besides, I would also like to hear your feedback regarding my comments on your throughput formula.

P.S. It seems to me that both of us do not understand what the other is talking about very well ... sometimes even talking about seemingly different things ...

[Dwachs]

Imho, the routing of goods needs improvement as indicated here. However, I have no solution at hand

Drawing from the experience of EXP, I would consider the following as desirable changes to the routing mechanism :
1> a criterion on search which encompasses factors like number of transfers, number of stops, convoy/line nominal speed, nominal waiting time
    -> cached as the basis of route comparison, to be used in route searching and for comparison in <4> below
2> cache the best line/convoy
    -> used in <4> to determine distribution of pax/mail/goods loading
3> route search with multiple start halts
    -> this is essential to allowing fair competition; this can be done with a single search
4> proportional distribution of pax/mail/goods during loading at stops
    -> this avoids all-or-nothing distribution and allows room for survival of the weaker competitors
It would also be a good idea to consider the following at the same time :
5> journey tolerance
    -> calculated with a simple formula, for capping the search and preventing unreasonable detour
6> preference for local/nearer destinations
    -> more reasonable distribution of pax destinations; Z9999 seems to have a patch on this
Of course, I am not suggesting to implement these in the same way as EXP does, or copying its code. We just borrow the concepts, and we implement it in a way suitable to Standard.

My comments/ questions on this list:
(1) sound good. But I fear there much balancing needed to get things right.
(2) what about storage requirement for caching? how will you achieve this?
(3) this is for a better distribution between different stations? called upon generation of a passenger?
(4) loading .. in the sense of loading goods to a convoi?
(5) necessary. clear.
(6) I did not look into z9999's code. This decision is to be made when a passenger is generated to give him a travel target?
It seems to me that your are suggesting a mix of different changes to tackle the problem and its consequences.

If you still remember, last year I attempted to rewrite the search code (I still have an outdated copy), and told you that search speed was roughly like before my transfer-centric route-searching patch got committed. And there should still be room for improvement.

What kind of patch / feature do you mean? I was not involved in your private communication

Just another thought: What about adding a penalty to overcrowded stations in the route search? Maybe equivalent to 1 or 2 more interchanges. That is passengers would prefer routes that are 1/2 interchanges longer than a route over an overcrowded halt. With some index magic this can be implemented in the current breadth-first search.

[knightly]

Thanks a lot for your feedback, Dwachs

1> Basically, what we need is a "reform" of the routing system in order to make multiplayer games work. I see no way to simply adapt the current system slightly to achieve the goals.
2> warenziele would cache the reachable halts, their connection weights as determined by the factors in <1>, as well as the best line/lineless convoy.
3> it would be nice if we can distribute across different start halts proportional to the weights; if that cannot be done, at least distribute to the start halt of the best route, not any random start halt. And yes, it's done during pax generation.
4> that's right, when loading goods from a stop into a convoy
6> I haven't look into z9999's code either. I raise this out of EXP's implementation, which is done in pax generation code
These are what I think desirable features from EXP which are worth considering. These features have been used in EXP for a long time, so we can draw from their experience.

What kind of patch / feature do you mean? I was not involved in your private communication

We can ignore that patch now, as that was my private experimentation only. What is important now is, we come up with a feasible blueprint together, and have that blueprint implemented efficiently.

Just another thought: What about adding a penalty to overcrowded stations in the route search? Maybe equivalent to 1 or 2 more interchanges. That is passengers would prefer routes that are 1/2 interchanges longer than a route over an overcrowded halt. With some index magic this can be implemented in the current breadth-first search.

IMHO, the current implementation which considers only the number of transfers is not sufficient to differentiate a good player vs a poor player. I can create a direct, no-transfer route between origin and destination but with a very slow convoy : under the current scheme, my route is preferable to a faster route with one transfer. And personally, I prefer to avoid routing over overcrowded stops altogether.

[whoami]

Just another thought: What about adding a penalty to overcrowded stations in the route search? Maybe equivalent to 1 or 2 more interchanges.

You have linked to the other thread where this had been brought up. From my little experience (small maps only) with no_routing_over_overcrowded=1, I can say that overcrowding stops (regarding passenger+mail) are regulated rather strictly with this setting. Using the level may ease this a lot, especially if there are no alternative routes.
But the overflowing stops are only a symptom of lacking transport capacity - a non-overflowing next transfer stop can also mean that the capacity to it (from the current stop) may be too low. From the other posts, I see ideas on how to move the focus to vehicle capacity (but the aggregate capacity of all vehicles+lines between two stops has to be considered).

{ This posted edited by Isaac Eiland-Hall to remove certain off-topic parts. If you require more information, contact me. -Isaac }

[jamespetts]

This is a rather interesting discussion, although I do not pretend to have looked at all the details in depth. Having created Experimental about a year and a half ago to achieve some of these objectives, it is most interesting to see discussion of the basic ideas that go into Simutrans-Experimental routing being put into Simutrans-Standard - as Knighly points out, it is necessary if there is to be any sort of competition between players serving the same area for there to be some sort of merit based route selection.

The view that I always take with simulation software is that, the closer that the actual mechanics of the software is to the actual mechanics of the thing being simulated, the easier that it is to work out how to make it work, the less likely that it is that there will be anomalous behaviour, the easier that it is to balance, and the easier that it is for users and fellow coders alike to understand. That is the approach that I have always adopted in Experimental - if I see something in Simutrans where the player has an incentive to do something very different to what a person in the position of that player would have an incentive to do in reality, I ask myself what economic forces are at work in reality that give rise to those incentives, and then what the most parsimonious way of simulating them is. That is how I came up with waiting and travelling times in Experimental as a means of determining the journey length.

Somewhat ironically, some of the suggestions being made in this thread appear to be even more elaborate than those in Simutrans-Experimental (such as routing decisions being based on multiple criteria - in Experimental the only criterion used for routing decisions is journey time, precisely because it is hard and computationally expensive to implement a multi-criterion routing mechanism), and the irony comes of the need to branch Experimental arising from a desire to keep Standard simple.

In fact, I think that the (relatively) simple approach of Experimental works best in terms of route selection and deals in one relatively simple and readily comprehensible mechanism with lots of the issues being discussed here for which specific and fairly elaborate mechanisms are suggested, such as vastly overcrowded stations. How to deal with overcrowded stations? Simple: measure the waiting time of all the passengers (etc.) in all stations. The station being overcrowded means that there are more passengers (etc.) arriving than leaving, so the waiting time will keep going up. There will come a time when that waiting time is so enormous that the total journey time will be so long that passengers won't want to travel on that route at all.

How to deal with overcrowded stations having more people than the population of a large town? Simple: if passengers have to wait more than a certain amount of time, they leave (and make the transport company that brought them there refund approximately what they paid to get there in the first place, to avoid exploits). Passengers who leave register double the time that they have actually waited as a waiting time to take account of the fact that they still had not caught their connexion when they left.

Load balancing also works surprisingly well without any specific load-balancing code. Once a particular route gets so crowded that convoys become full and people can't get on immediately, the waiting time goes up, and a different route, that otherwise would take longer, can have a shorter overall journey time in some situations. It doesn't end up as an all-or-nothing thing because people (or goods) going to different destinations along the same route and from different origins may or may not find specific alternatives shorter depending on the length of the journey compared to the waiting time, the extent of the particular detour, etc..

Have a look at an Experimental game and see how well that this functions in practice. This has been in development for some time now, and has the advantage of being tested over a number of months by quite a few people. The routing element of things has been found to balance well - the things that need more work at present relate more to the money side of things, although that is largely pakset related, I suspect, rather than the code. This is why I was keen to see the saved games to which Prissi refers that crashed Experimental - in the early days, Experimental was quite unstable (I don't pretend to be anything other than a somewhat inexperienced programmer, although I am always learning), so what crashed version 5.1 may very well not crash 8.2.

As to performance - Knightly worked wonders with the performance with his new routing algorithm last year, and that is really rather good, too. It's not as fast as current Standard (because current Standard is very, very simple), but it is very good, and not that far off. Before re-inventing the wheel, therefore, there may be much to be said for looking at Experimental's implementation of routing.

Incidentally, if we're going to have competitive games, don't we need to address the anomalous situation in which the maximum theoretical speed of a convoy determines the price bonus, rather than the actual speed?  If the speed is to be measured for the purposes of routing, then it's a small step to using it for revenue calculation. This is another feature that's been in Experimental for over a year.

[prissi]

I still want to summarize the reasoning, as I understood so far:

better routes should be preferred to enable competition:
- better means: more throughput, more convois, less stops in between, less traveling time, transfers less crowded

calculation of these factors may be static or dynamic:
- static has less hassle and less impact on the map. In network games (where this may be more urgent) continues change (and thus frequent recalculation) may occur anyway
- dynamic has the advantage that the current situation can be better reflected and even in fast forward the situation continuosly adapts. If there are many reroutings request during a network game, an monthly (or maybe ever 10 realtime minutes) rerouting may save even time.

always all possible routes should be considered:
- this would imply multiple searches for every passenger and compare the result
Depending on competition and density of stops this might occur not to often during starting of the game (where routing is not a problem). Maybe a parameter that at most (for pax) two routes are considered.
- somehow this happens already with the old code, when the closest stop was overcrowded.
- maybe routing has to be done with a table listing next stop and the cost (as determined above) for it. For the realistic maximum of 10000 stops this is 381MB: should be handled by todays computer. However, building such a connection table needs a million routes searches. Maybe here the cached route search approach form experimental may help.

I am still not sure what "journey tolerance" means. Tolerance against what?

{ This posted edited by Isaac Eiland-Hall to remove certain off-topic parts. If you require more information, contact me. -Isaac }

[jamespetts]

I am still not sure what "journey tolerance" means. Tolerance against what?

If this phrase is meant in the same sense as I use it in Simutrans-Experimental, it refers to the maximum journey times that passengers/goods will tolerate. In Simutrans-Experimental, this is set randomly for each packet within a predetermined range, which range can be set in simuconf.tab.

[Isaac.Eiland-Hall]

Off-topic conversation will be moved to a private thread for further discussion. Please do not discuss it further here; please continue on topic where applicable.