The International Simutrans Forum

Development => Bug Reports => Topic started by: jamespetts on December 20, 2008, 06:42:36 PM

Title: Passenger routing code?
Post by: jamespetts on December 20, 2008, 06:42:36 PM
I am looking into the (probably rather complicated) task of modifying the code such that passengers will not route unless all the stops at which they need to change are not overcrowded (in code terms, not having the status COL_RED). However, the routing code is (predictably) quite intricate, and it would help me greatly if somebody familiar with the code could let me know where to start looking. I know that it will be somewhere in simhalt.cc - but is there a specific routine where passengers check for the crowding of a stop? If the stop is overflowing with mail, but has plenty of room for passengers, is there a way to distinguish that (and vice versa)?
Title: Re: Passenger routing code?
Post by: prissi on December 20, 2008, 10:21:32 PM
The only way to do this is suche route, which is already called from step_passagiere and also everytime some goods arrive at a station and not other goods are waiting there. However, if goods are already waiting there, no route will be search but goods will simply joined.
Title: Re: Passenger routing code?
Post by: jamespetts on December 20, 2008, 10:30:45 PM
The only way to do this is suche route, which is already called from step_passagiere and also everytime some goods arrive at a station and not other goods are waiting there. However, if goods are already waiting there, no route will be search but goods will simply joined.

Thank you for the information - I shall look into that :-) If a route search is not carried out when there are already goods at the station, is there a way to re-check the routes periodically to ensure that there are no overcrowded stops on the way? Or are the routes already periodically recalculated?
Title: Re: Passenger routing code?
Post by: prissi on December 20, 2008, 10:31:31 PM
Routes are only recalculated when a schedule is changed or a stop is changed (or a factory pops up).
Title: Re: Passenger routing code?
Post by: jamespetts on December 20, 2008, 11:09:16 PM
Routes are only recalculated when a schedule is changed or a stop is changed (or a factory pops up).

Thank you for the information :-) Do those events call suche route?
Title: Re: Passenger routing code?
Post by: isidoro on December 21, 2008, 06:28:56 AM
After some private eye work, I've found out that suche_route is called whenever new passengers are generated and can, perhaps, return if any of the stations in the found route is overcrowded for the calling routine to decide if those passengers desist.

In uint32 haltestelle_t::starte_mit_route(ware_t ware), passengers packets are added to their station when created.  In uint32 haltestelle_t::liefere_an(ware_t ware), all packets (passengers or not) find next transfer when arriving to a transfer station.  I've programmed very easy patch in which passenger arriving to a transfer station in which the next transfer is crowded, will refuse travelling and become unhappy.

I've tested with a well developped game in which the yellow company deals with urban passenger transport and the red one with interurban passenger transport.  As you can see in the picture their profits go down as expected.  I'd like to test the patch with a fresh new game and see.  In the picture you can also see how a transfer station becomes uncongested and even with no unhappy passengers.

Title: Re: Passenger routing code?
Post by: gerw on December 21, 2008, 12:53:59 PM
I'm currently reorganising the routing of goods (http://forum.simutrans.com/index.php?topic=1016.0 (http://forum.simutrans.com/index.php?topic=1016.0)). I will also include a caching system for the routes in order to decrease computation time. Thus a dynamical routing of passengers will make this impossible.

And I think, it's also not realistic:
If a passenger starts to travel, how can he know which stops are overcrowded and which aren't??
Title: Re: Passenger routing code?
Post by: jamespetts on December 21, 2008, 02:04:18 PM
Grew,

the extreme overcrowding of some stops is a serious gameplay problem. In real life, 27,000 or so passengers do not accumulate at a railway station because the local 'busses can bring passengers there faster than the trains can take them to their destinations, yet this can regularly happen in Simutrans with larger towns.

What I suggest is not a system where passengers re-check their route on the fly and abandon their journeys half-way through, but a system where passengers check the entire route for overcrowded interchange stops on the way, and only add themselves to the route at all if none of the interchange stops are seriously overcrowded (behaving in the same way as if the origin station is overcrowded if any of the interchange stations are).

I do not know whether this will fit with your caching system, but it really is important to have it in the code somewhere, because the (sometimes absurdly) excessive overcrowding levels can seriously distort the game and have a substantial adverse impact on enjoyment.
Title: Re: Passenger routing code?
Post by: isidoro on December 21, 2008, 06:02:25 PM
[...]
And I think, it's also not realistic:
If a passenger starts to travel, how can he know which stops are overcrowded and which aren't??

The check is done only when transferring, not while in the vehicle.  If the passenger arrives at a transfer station and get informed that the next transfer station is crowded, he becomes unhappy, refuses to travel and hire a private car (won't use collective transportation).  Just the same that is done on starting his journey if he knows the destination is crowded.

James is right in my opinion: what really makes no sense is some 20000 people waiting at a station...
Title: Re: Passenger routing code?
Post by: jamespetts on December 21, 2008, 06:22:38 PM
Ahh, interesting. Isidoro, your approach is slightly different from mine in that I'd planned to set it so that only at the origin station is it checked whether the route is overcrowded (if that is done, then the transport company gets no money for transporting people part-way through their journies only to have to abandon them to hire a car or take a taxi...).  But if Isidoro's patch prevents the population of a medium sized town waiting at a single railway station, then it is certainly worthwhile...
Title: Re: Passenger routing code?
Post by: whoami on December 28, 2008, 12:39:06 PM
Nice to see this happen (probably), but please don't limit the function to passengers (or mail). It should be used for all types of goods.
Checking for overflowing transit stations once (at the origin) will be sufficient to get the effect.

And I think, it's also not realistic:
If a passenger starts to travel, how can he know which stops are overcrowded and which aren't??
The mechanism isn't so realistic, but the result will be. In real life, people will fail to get reservations for their trains/airplanes, or read (in the news) about extended waiting times due to lack of capacity, and therefore choose to avoid the congested routes, or even the transportation company in question.
Title: Re: Passenger routing code?
Post by: jamespetts on December 28, 2008, 12:44:09 PM
Whoami,

ahh, yes, both good points. One other thing that could stand to be added is a phased effect, so as to avoid the position where, if the station is 1 below capacity, 100% of passengers/goods will route, and if it is 1 above capacity, 0% of passengers/goods will route. In real life, stations can still work when they are overcrowded, but they become increasingly unpopular the more overcrowded that they are. I suggest a system whereby a weighted random proportion of passengers (etc.) refuse to route if the station is overcrowded, the weight being determined by taking the station's capacity, an overcrowded maximum specified for the purpose of this system, and taking the difference between the two divided by the maximum as the chance of failing to route to feed into the randomiser.
Title: Re: Passenger routing code?
Post by: isidoro on December 29, 2008, 01:28:16 AM
I've been playing with the code patched and haven't noticed those effects.  As it is now is simple and:
  • Stations get at maximum 110% capacity
  • Building station adequate station premises plays an important role
  • Playability:  I don't know.  The game seems nice to me, but I have not played the same game without the patch.  Some additional feedback would be great.

BTW, the original patch, though small, was wrong.  If the destination station is crowded, the passenger will not travel and become unhappy.  That case should be eliminated since that passenger will not wait at the station.  Here is the version updated and corrected.
Title: Re: Passenger routing code?
Post by: jamespetts on December 29, 2008, 10:08:41 AM
Isidoro,

I have not had a great deal of time yet to look at your patch in detail, because I have been spending a very long time trying to set up a read-ahead for the speed limits in order to allow smoothed slowing for speed limits (I am still debugging my data structures). However, as I understand it, your patch means that, when passengers hit an overcrowded station (i.e., a station at >110% of capacity), none of them will continue on their journey; whereas, if passengers hit a station that is not overcrowded (i.e., a station >= 110% of capacity), all of them will continue on their journey. What I suggested was a system (which would also be simple) that set for capacities between, say, 100% and 130%, a certain proportion of passengers to continue, and a certain proportion to leave, depending on where between 100% and 130% that they are, which would make the impact of overcrowding less erratic and more realistic.

As to the point about the original patch: I thought that the idea of unhappy passengers is that they were registered when they arrived at a station and did not travel because they were unhappy: are you saying that the original did that and that the new one does not, or that the new one does that and the original does not? Certainly, if passengers arrive at a transfer station and find it overcrowded, and cease the rest of their journey for that reason, they should register as unhappy, since that is the same behaviour as for passengers arriving from the local area rather than from other forms of transport.
Title: Re: Passenger routing code?
Post by: whoami on December 29, 2008, 02:28:41 PM
(...) cease the rest of their journey for that reason, they should register as unhappy, since that is the same behaviour as for passengers arriving from the local area rather than from other forms of transport.
Since the passengers' origin isn't known at that point, they would be counted the same way as unhappy people from the station's coverage area, and that would lead to misleading numbers. A new variable per stop would be advisable for this, also if the check is only done at the origin.
Title: Re: Passenger routing code?
Post by: jamespetts on December 29, 2008, 09:11:26 PM
Since the passengers' origin isn't known at that point, they would be counted the same way as unhappy people from the station's coverage area, and that would lead to misleading numbers. A new variable per stop would be advisable for this, also if the check is only done at the origin.


Ahh, I see what you mean. Would it be possible to set it so that it checks at the origin station whether any of the stops en route are overcrowded, and for the passengers to count as unhappy and refuse to board at that stage if there are? That would solve that problem.
Title: Re: Passenger routing code?
Post by: isidoro on December 29, 2008, 10:39:25 PM
It's not exactly as that.  When a passenger arrives at a transfer station, he checks if the next destination is crowded (100% crowded, not 110%).  If it is, he becomes unhappy and desists, unless the next station is destination, in which case, he does travel.

So unhappy people is counted at origin stations, not destination and makes sense.

@James: I'm for the simple case, all or nothing.  Even with your prevention, stations will get overcrowded, since there is local people trying to travel.

Title: Re: Passenger routing code?
Post by: jamespetts on December 29, 2008, 11:08:00 PM
It's not exactly as that.  When a passenger arrives at a transfer station, he checks if the next destination is crowded (100% crowded, not 110%).  If it is, he becomes unhappy and desists, unless the next station is destination, in which case, he does travel.

So unhappy people is counted at origin stations, not destination and makes sense.

Will stations be able to become infinitely overcrowded with people whose destination is the next station, in that case?

Quote
@James: I'm for the simple case, all or nothing.  Even with your prevention, stations will get overcrowded, since there is local people trying to travel.

I'm not sure that I understand why simple is better when simulating reality which is far from simple - but the local people trying to travel, as I understand it, are already accounted for in the code: people arriving at an overcrowded station from the local area, not as transfer passengers, already desist from travelling if the station is overcrowded.
Title: Re: Passenger routing code?
Post by: isidoro on December 30, 2008, 05:55:39 PM
I cannot make myself be understood.  ::)  The patch is so simple that I think it is better to explain it.  In simhalt.cc, there's a function called uint32 haltestelle_t::liefere_an(ware_t ware).  Whenever a new packet of goods/passengers arrives at a station, the function is called.  Following the source code, these steps are done:
  • if next transfer or destination is invalid, return
  • if the destination was this station: if factory, add cargo; if passengers, add pedestrians; return
  • If there are other stuff with the same destination, merge with it, return
  • Calculate next transfer
  • if next transfer or destination is invalid, return
  • (*) Here comes the patch
  • If there are other stuff with the same destination, merge with it, return
  • add the stuff to the station waiting list

And the patch says:
if(ware.gib_besch()==warenbauer_t::passagiere && ware.gib_zwischenziel().is_bound() && ware.gib_ziel().is_bound() && ware.gib_zwischenziel()!=ware.gib_ziel() &&  ware.gib_zwischenziel()->gib_ware_summe(warenbauer_t::passagiere)>ware.gib_zwischenziel()->get_capacity()) {
               ware.gib_zwischenziel()->add_pax_unhappy(ware.menge);
               return ware.menge;
       }


Translated to Shakespeare's language: if stuff is passengers and transfer is valid and destination is valid and transfer different from destination and passengers at transfer is greater that capacity at transfer, then add these passengers to unhappy count at transfer and return.

I'm not sure that I understand why simple is better when simulating reality which is far from simple

I'm fan of the Occam's razor.  Let's not forget this is a game.  You can be more precise or accurate in the calculations but the results may be the same, or quite similar and not worth the effort.  That's why I asked opinions about how is the patch felt for playability just now.  A sculpture should be balanced.  Not too much detail in one hand and a ball in the head.


Nice to see this happen (probably), but please don't limit the function to passengers (or mail). It should be used for all types of goods.

It should be quite simple to eliminate the condition "if stuff is passengers", but then those goods will disappear.  I don't know what is the procedure followed by factories and if they will order more...  I'll try.
Title: Re: Passenger routing code?
Post by: prissi on December 30, 2008, 07:51:20 PM
Goods should not disappear. Otherwise I can built one giant oilrig serving thousand of oiltankers, because the connected power station is served by a single truck. For goods maybe whole route should be checked; alternatively, it should not unload (since the new system the convoi wil go filled between those two destinations and ear no money but costs a lot. Also simple to do this.)
Title: Re: Passenger routing code?
Post by: jamespetts on December 30, 2008, 08:22:12 PM
Prissi,

ahh, the alternative suggestion is an ingenious one!
Title: Re: Passenger routing code?
Post by: isidoro on December 31, 2008, 01:17:54 AM
Goods should not disappear. Otherwise I can built one giant oilrig [...]

Good point!  The alternative is a pretty hard one, though.  Some present running games, with low profit goods transportation would ruin at once :D  And surely someone would be tempted to ask for a wait until unloaded option like in OTTD, which I don't like too much.  There has to be an easy alternative...

Factories push goods to the transportation system and other factories pop goods.  If the intermediate buffers are full, no more goods should be allowed. Perhaps it can be done locally, a transfer station is no more than a "special factory"...  I have to think it a little more and a temperature is no good companion.
Title: Re: Passenger routing code?
Post by: prissi on December 31, 2008, 10:12:49 AM
Well, if a full convoi runs between those station, the origin stations will be overcrowded soon and stop good acceptance. There is a delay but not too large, imho.
Title: Re: Passenger routing code?
Post by: isidoro on December 31, 2008, 06:51:26 PM
That's true.  But the cost...  it's a question of trying and see.  Game will be harder, that's for sure.

I've thought of another possibility that seems pretty simple but for a small thing:
  • When the next transfer of a loading vehicle is full, simply don't load.  If the vehicle is waiting for full load, keep waiting.  If not, continue travel unloaded.
  • The small thing: when more free space appears at the transfer station, the waiting vehicles trying to go there should be warned to try lo load again.

That will not guarantee that there be no surplus, but wouldn't be very big.

Do you think it is worth trying?
Title: Re: Passenger routing code?
Post by: prissi on December 31, 2008, 07:48:31 PM
Sounds better to me than full meaningless convois.
Title: Re: Passenger routing code?
Post by: isidoro on January 04, 2009, 04:08:03 AM
I've come with a modification to the patch.  The modification is three lines long and took me two and a half days.  Frustrating...

With the patch:
  • Transfering passengers or mail with next transfer overcrowded are discarded and, if persons, added to unhappy people at next transfer
  • Goods with a full next transfer will refuse to load at origin until there is place at the transfer station.  This is not applied if next transfer is also final destination

Warning:  I've tried the patch with an old savegame and profit dropped enormously.  Care must be taken when designing stations with this patch.  I liked the experience at first glance, though.

Title: Re: Passenger routing code?
Post by: emaxectranspoorte on January 04, 2009, 04:11:19 AM
Warning:  I've tried the patch with an old savegame and profit dropped enormously.  I liked the experience at first glance, though.

THIS IS EXACTLY THE SAME POINT I tried to make all this time. ::)
Title: Re: Passenger routing code?
Post by: jamespetts on January 04, 2009, 10:50:47 AM
This looks very interesting - thank you Isidoro for putting so much work into this. I shall have to have a look at this one when I have finished with the various settings for corners and weight limits.
Title: Re: Passenger routing code?
Post by: isidoro on January 06, 2009, 06:48:41 AM
Patch updated for r2118...

The test game I'm playing keeps interesting.  It is perfectly possible to get a decent profit with the patch, yet not having overfilled stations.  One of my favorite ways of gaining an easy and quick profit is trying to build a line in which trains transport cargo in both directions.  For example, if I connect A--B--C--D--E, with:
  • B, factory, serving A and E
  • D, factory, serving A and E
  • C, transfer station, built because A,B and D,E heights differ.
I build two lines B--C and C--D and both trains get loaded in both directions and profit is big.  With the patch, it works, but hardly.  If producing factories B and D get overfilled, trains in the middle won't travel.
Title: Re: Passenger routing code?
Post by: jamespetts on January 06, 2009, 12:27:44 PM
Another version - excellent! This patch is very worthwhile. I am somewhat sorry that I have not yet had more time to test it (I have been working on other patches instead), but it looks extremely promising. The overcrowded stations problem was a major drag to gameplay in Simutrans (and made things very confusing for newer players, too: I remember being confused about that when I was new) - this might make a really make a difference. Excellent work!
Title: Re: Passenger routing code?
Post by: prissi on January 06, 2009, 09:51:11 PM
Maybei this should become something like "Advance Player mode" like "normal player mode" and "Beginner Mode"
Title: Re: Passenger routing code?
Post by: jamespetts on January 06, 2009, 09:58:08 PM
I'm not sure about the advanced bit - the huge overcrowding of stations is actually quite overwhelming and confusing for newer players. Whilst it is harder in some respects to make a profit without mega-overcrowding being allowed, it makes for a better and more balanced game overall. New people to the game who try it first in "normal mode" might be put off by the excessive overcrowding, as I almost was when I first played Simutrans.

Edit: It is actually more fun and more relaxing to be limited in the game by not having enough money, rather than by not having enough time. Having overflowing coffers but not anywhere enough time to add enough capacity to deal with all the passengers (without often having to pause the game) makes the game not very fun to play.
Title: Re: Passenger routing code?
Post by: isidoro on January 07, 2009, 04:04:24 AM
I'm now playing with the patch and I like it very much.  You have to be *very* careful when designing your network.  But I'm with Prissi in that it may be confusing for new players.

It usually happens that a vehicle is ready to load but it doesn't load with no apparent reason.  I know the reason is that the transfer station is full, but that is not clear for a beginner.  I, when beginner, got confused with station types (passenger, cargo, etc.) and took me some time to make the first line work.  Imagine if, once I get it, the trains stop for no apparent reason...
Title: Re: Passenger routing code?
Post by: colonyan on January 07, 2009, 04:35:36 AM
Hum...... I'm kind of afraid to ask this but,,,, so we will have this problem solved soon?
From what I read, it seems like so.
If so, this will be included in next release with along the curving patch?
Title: Re: Passenger routing code?
Post by: z9999 on January 07, 2009, 07:58:46 AM
@isidoro
One question.

In simutrans, capacity of station is for each goods category.
So, overcrowded is also for each goods category.

Why do you use "sum_all_waiting_goods" ?


[edit] Very sorry. "Category" is not right. Not category but goods.
Each goods has its own capacity, station status bar above station name label shows this.

[attachment deleted by admin]
Title: Re: Passenger routing code?
Post by: prissi on January 07, 2009, 10:40:14 AM
The question is, if the sum should used instead?
Or that the capacity should be counted for the three categroies, i.e. passenger capacity, mail capacity and freight capacity?
Title: Re: Passenger routing code?
Post by: z9999 on January 07, 2009, 10:46:40 AM
No, using sum of each goods categories, - piece goods, bulk goods, etc.

[edit] Very sorry. This is not right. Not category but goods.
Each goods has its own capacity, station status bar above station name label shows it.
Title: Re: Passenger routing code?
Post by: jamespetts on January 07, 2009, 11:03:48 AM
It would make more sense to me for capacity to be counted per category - after all, passengers are not going to be dissuaded from using a station if its post office is overflowing with mail!
Title: Re: Passenger routing code?
Post by: isidoro on January 07, 2009, 07:59:19 PM
You're right in my opinion.  The patch is a first approximation.  The only problem I see is that when you add a new platform or a new hotel, the capacity of the station is increased by a quantity.  It doesn't make a difference in present code whether you add passenger or goods thing.  Should there be three different capacities in a station or can we cope with the present system as an approximation?
Title: Re: Passenger routing code?
Post by: prissi on January 07, 2009, 08:20:12 PM
I would like to have three different capacities for a station. At least for "Adavnced play".
Title: Re: Passenger routing code?
Post by: whoami on January 07, 2009, 09:22:32 PM
I would like to have three different capacities for a station. At least for "Adavnced play".
Sounds good. On top of that, the different extension buildings could then dedicate their capacity to one area (needs to be displayed in tooltip).
Title: Re: Passenger routing code?
Post by: isidoro on January 08, 2009, 03:23:30 AM
That would also change pak specification, wouldn't it?
Title: Re: Passenger routing code?
Post by: whoami on January 08, 2009, 04:21:44 AM
As always, downwards compatibility would be achieved by keeping the traditional behaviour as the default.

Or use the existing parameters differently: the capacity of a station building would be distributed among the types that it also enables, and maybe split the capacity into three parts for those that don't enable any type.
Title: Re: Passenger routing code?
Post by: prissi on January 08, 2009, 10:58:35 AM
I thaught like whoami: If a station enables post and freight, its capacity goes into those categories.
Title: Re: Passenger routing code?
Post by: Fabio on January 08, 2009, 11:03:18 AM
even better, each station or addition should add x to passenger capacity, y to mail capacity and z to freight capacity, as specified in its dat (or, maybe, x level * const to passenger, y level * const to mail, etc...)
Title: Re: Passenger routing code?
Post by: jamespetts on January 08, 2009, 11:37:58 AM
If this suggestion was implemented, certainly, there would have to be a new version of the .dat files allowing the pakset authors to specify themselves how much is added to each capacity. The GUI should also be changed to show in the toolstrip for the station extensions how much capacity is added to each category by each building (indeed, capacity is not shown in the toolstrip at all at present, which makes buying stations a rather hit and miss affair...).
Title: Re: Passenger routing code?
Post by: z9999 on January 08, 2009, 11:53:42 AM
Three type capacities is also good for "normal mode".

That would also change pak specification, wouldn't it?


I think current one is enough. It is simple enough and easy to understand for players
.
Only the problems are ...
Some stations like airstop have no P/M/G type.
It needs new cost/maintenance cost calculations according to sum of levels.
Title: Re: Passenger routing code?
Post by: VS on January 08, 2009, 12:12:02 PM
Whoami's approach seems both intuitive and simple. Waiting hall does not usually increase capacity for coal, while on a plain concrete slab platform can stand people - or lie heaps of coal.

This also fits nicely the current usage: nothing-enabling pieces have low capacity anyway.

By the way: There are no buildings that enable all three classes. In fact all pak64 buildings enable only one class, and in pak128 the only combination used is psg+mail, otherwise all classes are enabled separately.
Title: Re: Passenger routing code?
Post by: z9999 on January 08, 2009, 12:20:05 PM
By the way: There are no buildings that enable all three classes.

Pak96.comic are.  :)
Title: Re: Passenger routing code?
Post by: sojo on January 08, 2009, 12:29:27 PM
Pak96.comic are.  :)

That's true. In pak96.comic we have some goods at town. For example    vegetables and flour. This will delivered by a small truck. Nowhere will build a truck-stop for a short stopping truck.

I think a stop at an end user (factory) can accecpt all. Than the car supplies the factory not the stop.
Title: Re: Passenger routing code?
Post by: VS on January 08, 2009, 12:30:43 PM
Well, in a comic land, everything is possible... :D
Title: Re: Passenger routing code?
Post by: ij on January 21, 2009, 09:30:21 PM
This cargo stuff will open a possibility of a new kind of deadlock... If a transfer station gets full from input, the later-in-the-chain goods cannot (re)-enter there (if that would be necessary because of such routing layout) and eventually everything gets filled up in that cargo-loop and stops, which again might cause more deadlock since some trains can never leave a station.

It would be nice to have per station value to configure how large share of the cargo capacity a particular type of goods can take instead of 100% that gets now used.
Title: Re: Passenger routing code?
Post by: whoami on March 06, 2009, 01:12:22 PM
It seems that one implementation went into the trunk (tested: r2368):

Code: ("simutrans/config/simuconf.tab") [Select]
# things to overcrowded destinations won't loaf if active (default off)
avoid_overcrowding = 0

I used an older, well-developed savegame with avoid_overcrowding=1 (also seperate_halt_capacities=1, discussed in this same topic), and found the change to work (detail: people who want to go exactly to the overcrowded station, seem to travel even in that case), but the overall result is rather unsatisfactory (in my opinion).

For example, I looked at two major backbone nodes, both a little(!) overcrowded: most of the time, nearly empty trains run between the two, because the people from the first node won't travel to the second, as it is already too full, and vice versa. This is a kind of deadlock, which in itself might eventually become resolved over a longer time. However, the leaf nodes of the network keep filling up with people waiting for the upper nodes to clear, so whenever those leave overcrowded state, they will return to it immediately, and the deadlock continues after a short interruption.

(One alternative suggestion in this topic had been to not route across full nodes, so alternative routes would first be used, and after that fails, people would decline to travel over the player's network at all.)

(edit: removed claim that this was my idea)
Title: Re: Passenger routing code?
Post by: jamespetts on March 06, 2009, 05:58:00 PM
Interesting point about the deadlocks. I believe that Isidoro's original patch discarded passengers (and marked them as "no route") if the transfer stop was overcrowded. Perhaps this latest version should be modified to do the same thing?

(Incidentally, this version does have one major advantage over Isidoro's original, in that it respects the separate capacities of the station, so, if the station is overflowing with mail, for instance, it will not affect passengers).
Title: Re: Passenger routing code?
Post by: prissi on March 06, 2009, 09:08:06 PM
No isidoros patch did not load and discarded them, if they were already loaded. However, the next version will get a difficulty settings were every users can do what they like. I run into the same problem between a harbour and a hub, sunce the harbour was immediately filled when a ship arrived.

(That people, who wants to go to an overcrowded stop still go there is intended: The do not care if the have no waiting space left.)
Title: Re: Passenger routing code?
Post by: jamespetts on March 06, 2009, 11:52:55 PM
Perhaps a better way of addressing the whole overcrowded stop issue is for passengers, etc., to abandon the journey (and report as "unhappy" in the graph) if they have had to wait more than a certain amount of time at a station?
Title: Re: Passenger routing code?
Post by: z9999 on March 07, 2009, 10:33:06 AM
Discarding like the first patch is a bad idea. We will get many problem reports, like as we got for the new revenue system in v101.0.
At least people ride on a vehicle, they must pay.
We want to enjoy the process of the game, not the result of the game.

deadlock ? It's good, because people desired this kind of puzzled game, didn't they ?  :P

I want to enjoy to transport them instead of not to transport them.
Title: Re: Passenger routing code?
Post by: jamespetts on March 07, 2009, 11:08:33 AM
Z9999,

I am having difficulty understanding your comment: why would there be more problem reports for a discarding system than an insoluble deadlock system? People must indeed pay for the part of the journey that they do take (and can pay just before they are discarded for their journey so far), but there is no reason why they should pay for the journey that they were planning to take but cannot because the station is too full?

I also have difficulty understanding your point about enjoyment: why would creating an insoluble deadlock make the game more enjoyable?
Title: Re: Passenger routing code?
Post by: whoami on March 07, 2009, 07:19:42 PM
However, the next version will get a difficulty settings were every users can do what they like.
The current state (haven't checked the latest nightly, though) leads to situations where adding transport capacity cannot help, and adding storage capacity may only help to some extent, and there is a runaway effect in both directions (good and bad), so it is unstable by design.

Quote
I run into the same problem between a harbour and a hub, sunce the harbour was immediately filled when a ship arrived.
That's slightly different from the problem that I described: the stations should be large enough to handle the largest vehicle that uses them.

Regarding the alternatives:
Discarding is not so bad with passengers/mail (just let's say that these take different means of transport, like a taxi), but with goods, it may be very bad: the station may be full of cheap, useless stuff, but the arriving goods may be expensive, rare ones urgently needed for a complete production/transport chain.

To me, the approach of changing the routing to neglect overflowing stations appears more and more like the best way: it even allows for load-balancing between different connections and players.
Title: Re: Passenger routing code?
Post by: jamespetts on March 07, 2009, 08:38:37 PM
Whoami,

changing the route will only help if there is an alternative route available; but, even then, that is likely significantly to increase computational cost. If there is no alternative route available, the deadlocks will persist.
Title: Re: Passenger routing code?
Post by: whoami on March 07, 2009, 08:49:05 PM
changing the route will only help if there is an alternative route available;
Yes, that was part of the idea.

Quote
but, even then, that is likely significantly to increase computational cost.
That may be true, especially if there are alternative routes. However, if you have a strictly hierarchical network, it can even decrease CPU consumption, as the routing often gives up early.

But let me clarify what I meant:

Quote
If there is no alternative route available, the deadlocks will persist.
How? This was meant as a replacement to the current behaviour (which I consider broken), not as an addition. People+mail which cannot find a route over other stations should be put into unhappy, and refuse to enter my network (see first page of this topic). In case of goods, they wouldn't be put at my station, but remain at the output storage of the producer.
Title: Re: Passenger routing code?
Post by: Dwachs on March 07, 2009, 08:49:35 PM
And if there is an alternative route present it could happen that people never reach their goal:

Code: [Select]
A --> B --> C -->D
         \              \
          E--->F --> G

At B people realize C is overcrowded, now they travel to E. But meanwhile F gets overcrowded and the situation at C has relaxed. People go back to B ....
Title: Re: Passenger routing code?
Post by: whoami on March 07, 2009, 08:56:46 PM
And if there is an alternative route present it could happen that people never reach their goal:
That is because the number of vehicle switches isn't recorded in the goods packet.

Quote
At B people realize C is overcrowded, now they travel to E. But meanwhile F gets overcrowded and the situation at C has relaxed. People go back to B ....
True, there can be some bouncing also with this method. But I hope :) that the limited transport capacity stabilizes the situation.
Title: Re: Passenger routing code?
Post by: jamespetts on March 07, 2009, 08:57:35 PM
Whoami,

ahh, I didn't realise that it was supposed to be a replacement. In that case, it makes more sense. What did you mean by a hierarchical network, though?

Dwachs,

presumably, that would only be a problem if the routing code did not check to see whether the alternative route could get the packets to their destinations?
Title: Re: Passenger routing code?
Post by: whoami on March 07, 2009, 09:10:11 PM
What did you mean by a hierarchical network, though?
It means that the whole network is a tree, or at least has loops only on the highest level (and all stations on this level need to have direct connections between each other).

Quote
presumably, that would only be a problem if the routing code did not check to see whether the alternative route could get the packets to their destinations?
Another problem is that we can't store the preferred route into a goods packet, and it may change dynamically at any transfer station. Refusal to route across overflowing stations should indeed happen only at the origin station. But what happens later? The packets should be delivered, even if all nodes in between are overflowing. Here, the least overflowing node should be chosen (EDIT:) or use a routing malus, derived from the ratio occupied/capacity (I am sure that I have written about this before). If the overflowing status would be neglected completely during dynamic routing, the alternative routes would become useless.
Title: Re: Passenger routing code?
Post by: jamespetts on March 07, 2009, 09:17:07 PM
Hmm, one cannot assume that players will always design their network in a particular way.
Title: Re: Passenger routing code?
Post by: prissi on March 07, 2009, 09:31:57 PM
I think this problem affects only existing games; for new games plannign can be done in such way to avoid this deadlock. It is then up to the user, for instance to extend the stations capacity.
Title: Re: Passenger routing code?
Post by: jamespetts on March 07, 2009, 09:37:24 PM
In my view, there should be no possibility of deadlocks of this nature at all - it is highly unrealistic, counter-intuitive, and likely to be extremely confusing and frustrating for players if they ever encounter it. What to do to solve it is not in the least obvious, since the behaviour of the goods/passengers in the game is not similar to the way in which they would behave in reality. That people have to plan to avoid these deadlocks is part of the problem, not the solution.
Title: Re: Passenger routing code?
Post by: whoami on March 07, 2009, 10:15:55 PM
Hmm, one cannot assume that players will always design their network in a particular way.
Yes, but if you see it the other way round: by choosing the network design (and perhaps a simuconf.tab parameter), the player has the choice over this, too. The use of alternative routes (to avoid an overflowing station) is an addition inside that approach, it can also be omitted, but the players would prefer to have it, I think. Currently, the chosen route is rather random from the player's view if the transfer count is the same for several routes, (edit:) so hierarchical networks are already useful.

I think this problem affects only existing games; for new games plannign can be done in such way to avoid this deadlock. It is then up to the user, for instance to extend the stations capacity.
(My view:) The network would have to always provide a lot of excess capacity in both vehicles and stations, to make sure that the problem will never arise, because it is a self-increasing one. My savegame initially had only one overflowing (edit:) backbone station (the big central node), but the effect spread over the whole network due to what I already called "runaway effect". Once the situation is there, adding vehicles even in large numbers may not help (because passengers still refuse to enter them), even though a shortage in that regard caused the problem. Sure, the effect will not happen when starting a game, but complex games could suffer. Regarding station upgrades: especially in cities, space is limited.
So, if these concerns are true, I can only share jamespetts's opinion (previous post).

Title: Re: Passenger routing code?
Post by: prissi on March 07, 2009, 10:25:05 PM
Then I would just not enable this option. It is off by default for a reason. See it as "very hard" difficulty setting.

The only other way out would exclude those stations from routing and leave everything as it is. Not difficult, but requires extra code in the mode time critical routine we have ...
Title: Re: Passenger routing code?
Post by: jamespetts on March 07, 2009, 10:27:14 PM
Or just use Isidoro's original idea of discarding packets when stations are overcrowded, and adding the respective number to the "unhappy" statistic at the transfer?
Title: Re: Passenger routing code?
Post by: isidoro on March 08, 2009, 12:23:07 AM
I support the old Prissi's idea of a beginner, standard, advanced, and custom configuration.  Designing a deadlock-free with overcrowding avoidance would be for advanced players only and starting new games from scratch.

Not being a real solution to deadlocks, re-routing avoiding overcrowded stations will waste resources and make the algorithm more complicated and difficult to debug.

The problem with deadlocks here, as I see it, is more or less the same as the problem with deadlocks of trains on shared tracks.  The latter is solved with signals and one-way tracks.  The former can be solved with one-way loading vehicles in a similar fashion.  With the max. loading patch I've posted recently, it can be solved, imho.  But, that and overcrowding, and pay relative to destination, I think should be optional.  Only for advanced players.  Otherwise, beginners will refuse to try ST.
Title: Re: Passenger routing code?
Post by: jamespetts on March 08, 2009, 12:27:49 AM
Whenever there are problems like this, usually both the easiest way to resolve it, that is also simultaneously the easiest for players to understand, is to look to what happens in reality (it is easiest to understand because, in a simulation game, players will assume that the system works as in reality). In reality, there can be no such deadlocks: passengers do not wait on stations because they know that they next station at which they need to change is overcrowded. They get on the train, not knowing whether it will be overcrowded or not, and, if they find out that it is when they get there, become very unhappy and cease to travel entirely (perhaps they do that the next time, since they may well be stuck if they cannot afford a taxi, but the effect is more or less the same).
Title: Re: Passenger routing code?
Post by: isidoro on March 08, 2009, 01:27:15 AM
Yes, that solves the problems for passengers and mail and was my approach in the patch, but it doesn't work for goods.  As prissi stated, if goods are discarded a way of making unlimited profit can be exploited.
Title: Re: Passenger routing code?
Post by: whoami on March 08, 2009, 01:31:11 AM
Not being a real solution to deadlocks, re-routing avoiding overcrowded stations will waste resources and make the algorithm more complicated and difficult to debug.
To avoid the deadlocks, I effectively suggested to completely replace the current handling of overflowing stops by another method, the decision right at the origin, optionally(!) completed by re-routing packets with respect to overflowing stations.
Performance will be a concern for the latter, yes, but IMO much less for a single decision at the origin.

Quote
The problem with deadlocks here, as I see it, is more or less the same as the problem with deadlocks of trains on shared tracks.
The main differences would be: on tracks, the player defines how many vehicles there are, and a deadlock can (at the worst) be solved by selling vehicles in place. But passenger generation is dynamic, the player would have to monitor the whole network for bottlenecks, as he is unable to control utilization directly.

Quote
The former can be solved with one-way loading vehicles in a similar fashion.  With the max. loading patch I've posted recently, it can be solved, imho.
Sorry, I don't understand how these are connected, but it's already late at night here. edit: I just saw http://forum.simutrans.com/index.php?topic=1648.0 (http://forum.simutrans.com/index.php?topic=1648.0), which explains this further.

Quote
Otherwise, beginners will refuse to try ST.
ST is made for real men!  ;D

As prissi stated, if goods are discarded a way of making unlimited profit can be exploited.
It can, as already mentioned, also have negative effects (edit:) for the player.
Title: Re: Passenger routing code?
Post by: jamespetts on March 08, 2009, 11:12:31 AM
Isidoro,

there is no reason in principle why goods and passengers/mail should not be separated in the coding and treated differently. Perhaps discarding could be used for mail/passengers, and Whoami's system for goods?
Title: Re: Passenger routing code?
Post by: isidoro on March 08, 2009, 05:15:14 PM
To avoid the deadlocks, I effectively suggested to completely replace the current handling of overflowing stops by another method, the decision right at the origin,

Unfortunately, that will not get rid of deadlocks in all cases.  If you make the decision at the beginning, by the time you arrive at a transfer station, the situation may have changed to a deadlocked one.  A well designed unidirectional goods transportation network with max loading will do, imho.

Another possibility I'm now thinking about is:
  • Once in a while, the system looks for deadlocks.
  • If one is found, the vehicles waiting are allowed to load the same amount
  • The net amount will not overflow the stations and the deadlock would be solved

Example: A:200 (wood->B)   B:150(wood->C)   C:50(wood->A)
Vehicles waiting are allowed to load 50.  Once transported, the net amount of wood waiting would be the same, but deadlock has vanished!

Now, who is the programmer out there with enough of what a programmer should have to program this?   :P

ST is made for real men!  ;D

Vide supra  :D

Title: Re: Passenger routing code?
Post by: prissi on March 08, 2009, 08:56:06 PM
People avoiding overcrowded stops is not neccessarily the case. I was happyly loaded into a flight to Paris even though it was clear from the beginning that my connection flight was cancelled due to strike and any other possible route in that day way overbooked. Had to spend a day in Paris (not to bad punishment, but CDG was definitely overcrowded that certain day.)

But I will look into routing, I got an idea which should be almost neutral on speed.
Title: Re: Passenger routing code?
Post by: jamespetts on March 08, 2009, 10:09:50 PM
Prissi,

I shall look forward very much to your idea!
Title: Re: Passenger routing code?
Post by: isidoro on March 09, 2009, 02:10:18 AM
@prissi: Paris, the city of love, the river Seine, the Eiffel tower...  My experience there was not exactly the same as yours...  I had to go there once and stayed in a hotel.  Let's say that a couple in the room just besides mine was experimenting the "charm of the city".  And God that they lasted to get it...  All night long hearing that rhythmical sound...   :P
Title: Re: Passenger routing code?
Post by: z9999 on March 09, 2009, 08:11:52 AM
Checking overcrowded states during suche_route is a bad idea.
r2372 has a biiiiiiig problem.
All goods on intermediate stop will be removed if next intermediate stop is overcrowded.
Why it need to remove all of same destination which are already there ?

I think the best way is only when called from step_passagiere and after they find their root, check all parent node and if there is overcrowded stop, they don't enter stops.

The problem is current suche_route code don't know whether it was called from step_passagiere or not.
Title: Re: Passenger routing code?
Post by: prissi on March 09, 2009, 09:32:49 AM
I was not very keen on this anyway from the start; and since this was ment for factories, simfab.cc must do the same.

The good were just removed because they had no valid route anymore ... error in routing => removed. But now suche_route will get the check only from simcity and smfab
Title: Re: Passenger routing code?
Post by: z9999 on March 09, 2009, 01:47:01 PM
I tested in r2373, but I don't understand your way.
Do you use both "don't move if next stop is full" and "don't enter if one of node stop is full" ?
I think this is meaningless and same as 102.0.
This don't solve deadlock and addition, as Dwachs said they sometimes go back their route.
Title: Re: Passenger routing code?
Post by: jamespetts on March 09, 2009, 02:51:07 PM
As usual, I find that, in these situations, the most sensible thing to do is to consider how it would work in reality. That, after all, is what players are implicitly given to expect will happen from the very fact that this is a simulation game. Anything that departs from reality significantly and in a non-obvious way is likely to be confusing.

Looking at the reality of things, with passengers, they generally have a limited tolerance and will only wait so long for a train before considering abandoning their journey, or looking for other modes of transport. Passengers will tend to avoid stations that are known to be very overcrowded, especially if there is a possibility that they will not be able to fit on a train for quite some time. Although passengers cannot predict how crowded that stations down a line are on an individual journey, if a station becomes notoriously overcrowded, the same will apply.

So, a sensible solution for passengers is to have a quality of service metric based on average waiting times per line per station, and average crowding levels per station. Passengers would choose, where there is a choice, a route that had origin and transfer stops with higher, rather than lower, quality of service metrices. If a station ever became excessively crowded, such that no more passengers could fit into it at all, then newly arriving passengers should effectively be discarded en route (abandoning their journey or continuing it by taxi). Furthermore, if passengers have to wait too long at any station, they should also abandon the journey. Passengers abandoning a journey should record themselves as "unhappy" at the station at which they so abandon.

Mail and goods are different: they are not sentient and do not therefore have a tolerance level. Some goods are more urgent than others, so, if, for example, mail is not picked up for some time, the people in charge of the postal system will become concerned and potentially withdraw it. Likewise, food will perish if not collected before a certain time. So, as with passengers, certain goods, if they have to wait too long at a station, should be discarded, and lost to the player. The situation is different for, say, coal or iron ore, the delivery of which is not urgent, per se, but, even then, suppliers will not want to have their valuable product sitting unused in a station's store for ever. Eventually, that, too, would be withdrawn and private transport arranged. So, all goods should have an expiry time: a wait time (in months) beyond which they will abandon the journey. That could be specified in simuconf.tab for each different type of transported item.

Similarly, if goods arrive in a station that is already too full, there is nowhere to put them. For a while, they can be piled up in the car park or in the stationmaster's office, but there is a limit even to that. In reality, operators would know that a certain station is becoming overcrowded, and would avoid routing via it (remember: with goods, the transport company decides the route which they take; passengers decide their own route). However, there might be no alternatives. It would make sense for the transport company to hold back the goods to prevent them from being lost at the transfer; but, after a while, they would be withdrawn in any event.

With all that in mind, here are some summarised suggestions:

(1) each type of goods/passengers should have its own maximum waiting time at each transfer, beyond which the journey will be abandoned;

(2) there should be a quality of service rating per station per line, which determines relative routing preferences;

(3) goods/passengers unloaded at very overcrowded stations should be discarded; and

(4) if a vehicle comes and the next transfer is overcrowded, don't load the packet unless it has been waiting at the station for more than, say, two thirds of its maximum wait time (passengers get desperate, and take the next train that will take them to their destination somehow or other; goods get routed to avoid the possibility of abandonment).

Hopefully, the above set of solutions will add realism and interest to the gameplay and avoid deadlocks all at the same time, whilst maintaining a realistic response to the issue of station overcrowding: players should be penalised for it to some extent, but not in the form of irresolvable deadlocks. The capacity of a station should also be somewhat elastic, such that some goods can unload when it is overcrowded, but only a few.
Title: Re: Passenger routing code?
Post by: prissi on March 09, 2009, 04:29:02 PM
The no load on full was isidoros idea. I added the routing to relieve the deadlock. When I programmed did I was just waiting for people to request that skip the no-load, just avoid routing over such stops. However, the latter is hard, du to joining packets. If there is still one with the old overcroded routing in there, it will win.

I think this feature needs more finetuning, and thus I wait to create at least a nightly to have people comment further on that.
Title: Re: Passenger routing code?
Post by: z9999 on March 09, 2009, 07:20:07 PM
My patch for r2373.
Title: Re: Passenger routing code?
Post by: prissi on March 09, 2009, 09:25:05 PM
But sometimes there is a longer route with one transfer more without overcrowding. If I see correctly, suche routes would be not considered.

Another possible with oyur patch would be making passengers unhappy instead of no route; but then we need more discussion.

Not sending passengers/goods out to overcrowded stops makes gamesplay actually easier, since one do not need to care about overcrowding. Or am I wrong?
Title: Re: Passenger routing code?
Post by: jamespetts on March 09, 2009, 09:37:07 PM
It can't necessarily follow from the fact that routing tries to avoid overcrowded stops in some conditions (if my suggestions were adopted, only if the packets had not been waiting too long) that one need never worry about overcrowding, as there will always be a limit in capacity of the network, however efficiently that the network is managed. There may be many situations where there are few, if any, alternatives to changing at one particularly overcrowded transfer. The code should, perhaps, consider only those routes that are X numbers of transfers more than the one that would have been used but for the overcrowding (say 2 or 3 more).
Title: Re: Passenger routing code?
Post by: isidoro on March 10, 2009, 01:04:33 AM
Rerouting is no solution for deadlocks.  One solution is discarding, but it's not good for goods.  The problem is transfer stations.  They hold free space (the goods waiting) and requires free space from other stations in order to transport it.

The theory of deadlocks is simple.  For a deadlock to happen, four conditions have to be met.  Avoid any of these and deadlocks will never happen:
  • Mutual exclusion: free space can not be shared between stations
  • Hold and wait: each station participating in a deadlock must hold space and wait for free space in other station
  • No preemption: space cannot be freed once occupied
  • Circular wait: there has to be a closed chain of waiting for conditions:  A->B->C->D->A, for instance

For example, discarding passengers works because the third condition doesn't hold.  My solution with one-way routes works because it's against the second condition though it's a constructive one (the player should build a working network).

SIMPLE POSSIBLE SOLUTION:
Here's another possibility I'm just thinking about:  the problem is connected stations dealing with goods. The solution is to divide the storage space you have at every dangerous station evenly among the possible destinations of goods at each station.

Example: Let's consider this situation:

A------.                        ,-------- E
        --- C --------- D ----------- F
B------'                        `-------- G


All stations have a capacity of 600.  Only C and D are sources of possible deadlocks (condition 2).  Let's work against it:
  • In station C: 200 is reserved for goods going to A, 200 for goods going to B, and 200 for goods going to D
  • In station D: 150 is reserved for C, 150 for E, 150 for F, and 150 for G

With that simple solution, there will never be deadlocks.
Title: Re: Passenger routing code?
Post by: z9999 on March 10, 2009, 04:09:32 AM
Not sending passengers/goods out to overcrowded stops makes gamesplay actually easier, since one do not need to care about overcrowding. Or am I wrong?

Not sending passengers/goods out to overcrowded stops causes deadlock, this is meaningless.
But discarding passengers makes gamesplay actually easier as you said.
I also said this before. So, this doesn't add penarty. It's a cheat.
Make player happy is not a purpose of this setting.

The only solution for this is "close entrance". This is no cheat.
Once player allows to enter, he/she must transport them responsibly.

Rerouting is no solution for deadlocks. 

Yes, it is. Alternative route never work like that. If the network is complex enough, they can always find their alternative route, but they don't go that route. As I said they will go back their route.
Especially, goods often take an undesirable route.

Another possible with oyur patch would be making passengers unhappy instead of no route; but then we need more discussion.

No. There is a chance for other passengers to enter the stop. And repair imbalance of passengers.

My patch is very simple solution but really reduce passengers and reduce waiting people well. If player won't solve overcrowded stops, they will get big penarty.
But if you played well, you don't get any penarty.
Title: Re: Passenger routing code?
Post by: ij on March 10, 2009, 10:12:21 AM
  • ...
  • Circular wait: there has to be a closed chain of waiting for conditions:  A->B->C->D->A, for instance

SIMPLE POSSIBLE SOLUTION:
Here's another possibility I'm just thinking about:  the problem is connected stations dealing with goods. The solution is to divide the storage space you have at every dangerous station evenly among the possible destinations of goods at each station.

Example: Let's consider this situation:

A------.                        ,-------- E
        --- C --------- D ----------- F
B------'                        `-------- G


All stations have a capacity of 600.  Only C and D are sources of possible deadlocks (condition 2).  Let's work against it:
  • In station C: 200 is reserved for goods going to A, 200 for goods going to B, and 200 for goods going to D
  • In station D: 150 is reserved for C, 150 for E, 150 for F, and 150 for G

With that simple solution, there will never be deadlocks.

I proposed this earlier in another form in this thread, for some reason people didn't take notice (probably since nobody hadn't yet encountered deadlocks for real since then :-)). I'd have wanted the max per a goods type to be configurable for a station (in general the circular loop is refining a product so the goods type shouldn't be same even if they fall into same category such as crude oil and its derivates). I'm not sure you can easily find out the correct divisor automatically.

Because of latency involved in the feedback (the cargo "in-flight") we might also need another workaround to fully avoid possibility of deadlocks: If a goods type is above the allowed per type maximum on a station, loading it to a vehicle regardless of destination status might be necessary. However, a plain simple approach to actually do that probably just results in circumvention of the whole overcrowded thing here and there, but I guess the sources will still slow down since they shouldn't be congested so the rate will slowly settle to a bearable one. Just to point out that these non-linear transients really make this problem somewhat more complicated. The other option is to the divided rate as hard maximum but that will disrupt the smoothness of cargo flowing really.
Title: Re: Passenger routing code?
Post by: whoami on March 10, 2009, 05:06:09 PM
One simple approach (don't route at all if the route chosen by the traditional algorithm has any overflowing stop) will not create deadlocks for passengers and mail, because they will (practically) be discarded even before their journey begins. For goods, there is a low probability for a deadlock, which increases together with network size and industry density. The remedy would be in network design: stops -that are in danger of a deadlock- should be split up to cover a single factory each. This approach allows to disregard overflowing stops once a goods packet has been released - the result won't be perfect due to transport delays (it need not be anyway), but stop capacities will have full effect, and CPU utilization will not increase by much.

If dynamic routing also excludes the overflowing stops, both static deadlocks and discarding of pax/etc. could be avoided by this: if no route with only non-overflowing stops can be found, search again, but this time including overflowing stops (edit: ij mentioned this already) (optionally combined with check for average or maximum waiting time of a goods packet). Being able to stabilize routing (by sticking to the previous decision for the packet) would have been nice, but the necessary information for that is missing. There is still the chance of a dynamic deadlock (packets bouncing back and forward). EDIT: a single free bit in the goods packet would allow packets to be flagged as exceptional, so their routing would be the traditional kind.

The idea of a routing malus for an overflowing stop (increase transfer count by a number depending on over-utilization) has been mentioned already.

How about this idea: let the player detect a deadlock, who then presses a red emergency button, leading to alternate operating mode of the network (or part of it): ignore overflowing stations for routing, but don't accept new pax/etc. until the exceptional situation is over. The deadlock detection could also be automated: have a threshold for number of people/etc. that want to go to another stop, but can't because it is overflowing, and also the sending stop is overflowing.

EDIT:
Here's another possibility I'm just thinking about:  the problem is connected stations dealing with goods. The solution is to divide the storage space you have at every dangerous station evenly among the possible destinations of goods at each station.
I think you also need the number of different recipients of the same goods type/category that a given stop may connect to, or even the amount of goods already en-route to these. What defines a "dangerous station"?
The brute-force approach would be to reserve enough space on each stop across the whole route, which works in principle, but the program cannot handle the necessary data in a practical manner. Also, much more space would be needed at transfer stops.
Title: Re: Passenger routing code?
Post by: jamespetts on March 10, 2009, 09:38:40 PM
This is indeed a thorny issue. I should counsel against approach that requires the player actively to manage deadlock situations: that is the sort of number-crunching micromanagement that turns a fun simulation into hard work. It is also likely to be bewildering to players who expect their network to behave in a realistic fashion: as mentioned before, these sorts of deadlocks are not realistic. There is no way that a player who has not read all of the documentation about routing in detail, and carefully thought through all of the detailed permutations would have any appreciation that a deadlock might occur in these circumstances. Simutrans is, after all, a simulation game, not Tetris with trains. Players need to be making abstract design decisions, not solving logic puzzles.

Z9999 made a very interesting point about discarding, which is that, without a separate penalty, it makes things too easy. That, I think, is a valid point. However, that is not a reason to abandon the discarding idea: a penalty can easily be built in to prevent discarding giving the player a free ride with insufficient capacity. If each discarded packet recorded a negative score against a station's quality of service rating, and the quality of service rating of each transfer station was taken into account when calculating the revenue (on the basis that the fares would be set at levels that people are willing to pay, and that they are willing to pay less for poorer services), then that would, if correctly calibrated, be an effective penalty.

So, the game is made easier in the sense that it is devoid of brain-bending logic puzzles, but the more high-level, economic element of the challenge is preserved and strengthened by creating an economic penalty for a failure to solve the operational problem of under-capacity. There may also be some benefit in modifying the routing algorithm to attempt to avoid overcrowded transfers, but care must be taken to avoid making the routing algorithm too slow, or making passengers/goods take too tortuous a route: after all, increasing the necessary number of transfers by many times will greatly increase the possibility of overcrowding transfers, and so potentially create serious positive feedback with, eventually, nearly all the stations on the network becoming completely full as alternative route after alternative route is found to avoid a capacity problem that perpetually overflows into the next route that it tries.
Title: Re: Passenger routing code?
Post by: whoami on March 10, 2009, 10:18:44 PM
Financial incentives are OK, but the player also needs an automatic feedback mechanism, otherwise people will push and shove into the network, and then demand a refund because they get stuck. In real life, you need to get a reservation to be sure to get a seat. If there are not enough seats to reserve, people may go away, that's enough penalty in my eyes. We can't handle reservations without sacrificing performance, but this discussion shows some ideas that may allow to get similar effects without slowing down the game or confusing the player.

QoS as a feedback mechanism sounds good, but my experience with other simulation games (e.g. TTD, Traffic Giant) tells me that it's not easy to get it right - from the examples: the rating followed the actual service quality with huge delays, and it could be very difficult and costly to maintain a decent rating. If the formula for rating calculation is complex, the game becomes harder to understand. Having to permanently check and adjust the whole network sounds like work, too.
Title: Re: Passenger routing code?
Post by: isidoro on March 11, 2009, 02:52:59 AM
@z9999: I've been working with deadlocks for a long time and, believe me, rerouting is not an alternative.  Your packet can go back and forth and, in between, the header stations can get flooded with new goods.  And that, considering that there is an alternative route.  It may not even exist.  Once a deadlock exists, it will never be solved by itself.  Your "complex enough" network will slowly "die" with more and more deadlocks until it eventually dies completely.

@whoami: reservations is not an alternative.  If you use reservations, the whole system has to be changed.  With reservations, a packet has to travel exactly as was designed at origin.  Delete a road, change a station and you will end with lots of stale reservations and goods rerouting for alternative ways with no reservations (new deadlocks).  You can solve that by cleaning the reservations when rerouting, but then, those reservations should be stored in packets themselves: not possible in present ST.

@ij: deadlocks may exist even with only one kind of goods.  So, it has nothing to do with it.  In the example, if you have 600 of wood in C going to D and 600 of wood in D going to C: deadlock.  So division should be done considering possible destination stations, not types of goods.  And since the capacity of a station for goods is a global quantity, we can treat goods as a whole.  No need to consider different types for this.

@whoami: even with one station per factory without max load, you can get deadlocks.  To your question about which are the "dangerous" stations, they are the ones with more than one connected station.  In the example, A, B, E, F and G are not dangerous: they are leaf-nodes.  In an example of A - B - C, with my max-loading patch, B can be made "not dangerous".  In normal ST, it always is.

In summary, to avoid the deadlock problem, you have two possibilities:
  • You guarantee there is a 0% chance of deadlocks, since a small probability will grow slowly since an established deadlock will survive forever
  • You allow deadlocks to be manually removed, like in whoami's idea, by destroying goods

An advanced mode together with max-loading is a 100% safe method if networks are well-designed (by an advanced player only, others can play with overcrowded stops), it's simple, it can solve other previous requests and it's already programmed.  Who can give more for less price?   ;D

Title: Re: Passenger routing code?
Post by: Dwachs on March 11, 2009, 06:27:24 AM
Quote
An advanced mode together with max-loading is a 100% safe method if networks are well-designed (by an advanced player only, others can play with overcrowded stops), it's simple, it can solve other previous requests and it's already programmed.  Who can give more for less price?


This requires to set the max-load to 0% ?

Imho, it would be more intuitive if overflowing is treated on the supply side, that is, passengers/goods start to travel only if a route without overflowing stations is found. Otherwise they try to use a network from a different player or do not travel at all. Such a system hopefully balances itself out in the long run. To avoid switching effects, one can use a soft barrier, ie. a route is rejected with probability p(x) if stations on it are full to x percent.

Here is another, different idea (from gerw) for goods: Each industry stores the amount of goods that are on the map and going to this industry. A supplier will send goods to a particular industry with a probability inversely proportional to the amount of goods already traveling to this target. This could solve problems, where goods are travelling via unintended connections.

Maybe a similar system could be applied to passengers too?
Title: Re: Passenger routing code?
Post by: prissi on March 11, 2009, 09:42:21 AM
Such bookkeeping is likely to run out of sync very fast, and will be impossible to restore after saving and reloading.

I followed z9999 idea of letting the suche_route check for overcrowding. If overcrowded route, goods will not sent out (reducing profit) and passengers will be unhappy. This is the option no_routing_over_overcrowded = 1 in simuconf.tab.
Title: Re: Passenger routing code?
Post by: isidoro on March 11, 2009, 01:42:21 PM
@prissi:  good luck with it.  I hope I'm wrong.

This requires to set the max-load to 0% ?

It's a possible solution.  To design a working network, you can draw and sketch.  Points will be stations and arrows from station 1 to 2 indicate that there may be goods in station 1 blocked because station 2 is full.  Whenever there is a loop in the drawing, there is a risk of deadlock.  Example, problem in B and C:

           /--->---\
A --->--- B         C ---<--- D
           \---<---/


This system is equivalent and will never be in a deadlock, for example:

 /--->--- B1 --->---\
A                   C ---<--- D
          B2 ---<---/


But there's a problem.  In present ST, whenever you build a route between two transfer stations two connections are automatically generated and a loop is automatically there and a risk of deadlock.  You need a means of doing "one-way connections", like the one in C --->--- B2 in the drawing.  That can be done easily with 0% load.  There would be a route like this one:
  • C
  • 0% max loading in B2

So, C is connected with B2, but B2 is not connected with C.  Hope I made my point clear.
Title: Re: Passenger routing code?
Post by: z9999 on March 11, 2009, 02:21:02 PM
Easy way to avoid deadlock is playing with "avoid_overcrowding=0".
You wrote a code to make deadlock and wrote a code to avoid deadlock.
Too funny. They are unnecessary code.
Title: Re: Passenger routing code?
Post by: jamespetts on March 11, 2009, 07:58:19 PM
Z9999,

they are not unnecessary, as overcrowding, without a system for avoiding it, can be overwhelming and unrealistic. I have played games with 27,000 or so passengers waiting at a station, where I was turning over vast profits. That sort of setup is simply absurd.
Title: Re: Passenger routing code?
Post by: isidoro on March 11, 2009, 08:17:45 PM
Easy way to avoid deadlock is playing with "avoid_overcrowding=0".
You wrote a code to make deadlock and wrote a code to avoid deadlock.
Too funny. They are unnecessary code.

You are not being fair, z9999.  The story is different: I wrote a code to avoid overcrowding.  An unexpected side-effect is deadlocks.  So, I'm responsible and try to give some solutions (2) the best that I can (you have the option of following it or not, I have no special interest in it and I don't care very much if I'm right or wrong, I always try to do my best and sometimes I fail, that's the good thing of being human and not a machine).

You are saying something like this: "isidoro built a spring because he was thirsty.  The spring has a problem and some water goes into houses. So, please destroy the spring and die of thirst instead of trying to fix it".  Even you have tried to fix the spring yourself, so your sentence has no logic inside for me...  That's the good thing, btw, I like feelings much more than cold logic.  I'm a southern.  So, thanks anyway.
Title: Re: Passenger routing code?
Post by: whoami on March 11, 2009, 10:08:16 PM
I followed z9999 idea of letting the suche_route check for overcrowding. If overcrowded route, goods will not sent out (reducing profit) and passengers will be unhappy.
This sounds very much like what jamespetts suggested in the very first post of this thread :), but many ideas came up after that. The downside of the simple approach is that the network may be capable of transporting more, via different routes (perhaps set up on purpose => player may be confused/frustrated), but those wouldn't be used with the simple check "accept for transport yes/no". People also asked for the possibility of alternate routes, e.g. here (http://forum.simutrans.com/index.php?topic=1164.0).

I still consider these ideas as worthwhile to discuss further:
- if there is any route with only non-overflowing stops, accept the input for transport (maybe limit the amount for a single input action, e.g. matching the size of a small stop)
- whatever is already in the network, should be transported by any means, but preferredly over nodes that are not overflowing, or those with the least over-utilization. => no possibility for simple deadlock, but still for bouncing (routing back and forth, or in a loop).

To prevent bouncing, there should be a method to tell when a packet should stop looking for the best route, and just take any working route (let's call this state any_route). I asked whether it would be possible to (ab-)use a single bit in ware_t as a flag for this. Independent from this bit (which is needed for persistency across stops => stable routing), how would we decide if this state should be chosen? I think that the arrival at an overflowing stop would be the correct indicator => it works as flag for all packets at this stop (waiting and arriving). I assume that this might just move the possibility of bouncing and unstable routing to a higher level, unless the decision can be stored in ware_t. Note: when a stop becomes overflowing, the state any_route also applies to goods packets waiting there, so their routes need to be recalculated. When a stop leaves the overflowing state, the routes should stay as before, to keep routing more stable, otherwise bouncing may reappear quickly. EDIT: this doesn't prevent bouncing completely, but the transport delay should stabilize the whole situation. The cost for bouncing depends very much on revenue calculation settings. Another reason to set the flag any_route would be the arrival at a transfer stop where the calculated next stop is in the schedule of the unloading vehicle (still can't detect loops). A deadlock detection mechanism can also set the flag, but for all stops. The complete solution requires ware_t to record the number of transfers in the past => more bits needed.

Alternate routes, once implemented, can then be extended to use QoS rating of any kind.

An extension request that makes sense separately from the routing discussed here: allow the player to discard selected passengers/etc. from a stop, in order to free up space ("remove" button in the list of goods), perhaps linked to paying a penalty. Currently, the only way to get rid of stuff is to delete the entire station, which breaks routing.
Title: Re: Passenger routing code?
Post by: jamespetts on March 11, 2009, 10:22:54 PM
Whoami,

coincidentally, I have just been adapting Simutrans-Experimental to use Prissi's latest code, and the adaptation that I have come up with in effect implements what is currently a simplified version of your first suggestion. The code searches through all the possible origin stops within reach of the passengers, and checks each of them for a suitable route. Only if no route is found (or, with the latest code, no route that is not overcrowded) from any of those possible origins are the passengers discarded as "no route" (unless they have access to a car, in which case they take their car instead and add some congestion to their origin and destination towns).

A further development would be for the route searching function to use a number of metrics to choose the passengers'/goods' preferred route (average speed, comfort, etc.), but, similar to another one of your suggestions, if the packets have been waiting more than a certain amount of time to be collected, let them take any route. Indeed, it might be possible for packets to store different possible routes simultaneously, and board whichever is the first mode of transport that will use any of those routes, but that might adversely impact on performance.
Title: Re: Passenger routing code?
Post by: whoami on March 11, 2009, 10:39:51 PM
Only if no route is found (or, with the latest code, no route that is not overcrowded) from any of those possible origins are the passengers discarded as "no route"
That will help in some cases, but not for the typical setup where all bus stops of a town connect through the central train station/airport/whatever.

Quote
A further development would be for the route searching function to use a number of metrics to choose the passengers'/goods' preferred route (average speed, comfort, etc.)
Alternative routes, whatever decision base they have, need stable routing, or bouncing will likely happen. 

Quote
but, similar to another one of your suggestions, if the packets have been waiting more than a certain amount of time to be collected, let them take any route.
That's another instance where to set the flag that I suggested, but this needs to store the waiting time per packet (average time, I guess). True, the overflowing state need not be used in an isolated, simple yes/no decision, it can be part of a bigger QoS scheme.

To make the routing decisions stable, the QoS rating may have to have a big delay (the one that I criticized in other games), the actual time depending very much on the network's size and the typical travelling times in it. If only overflowing state is used, it still has to be change very rarely - and maybe use it also for initial acceptance.

Quote
Indeed, it might be possible for packets to store different possible routes simultaneously, and board whichever is the first mode of transport that will use any of those routes, but that might adversely impact on performance.
Moreover, I see the possibility of bouncing here, again.

(edit: some clarification/correction)
Title: Re: Passenger routing code?
Post by: jamespetts on March 11, 2009, 11:22:00 PM
Whoami,

can you tell me a little more about what you mean by route stability and bouncing here? What I envisage for the new revenue system is having additional metrics: average speed for each line and each convoy (where a convoy is part of a line, the line average is used, otherwise the convoy average is used), average comfort for each line and convoy (relevant only to passengers), average overcrowding for each line and each convoy (using the existing "free capacity" variable, with negative values for overcrowding), and average waiting time for each line and each convoy. Stations would not have any additional metrics, but the number of unhappy passengers may well be used to adjust the revenue. Thus, instead of a single, global "quality of service" value, there would be a number of metrics that would be more precise and easier to understand.

Passengers/goods would pay based on the previous month's averages, not the exact speed of the current journey. (The fares that a company is able to charge are, after all, based on its general reputation for punctuality, comfort, etc., and do not vary with every trip). The same would apply for passengers/goods choosing a route, where there are viable alternatives (I plan to extend the system beyond choosing different starting stations). Would that system be stable enough in the sense that you mean stable? Or would something else be required?
Title: Re: Passenger routing code?
Post by: whoami on March 11, 2009, 11:56:49 PM
can you tell me a little more about what you mean by route stability and bouncing here?
The optimum might rather be a situation where every ware_t instance would store the (preferred) route, which should only change if the network doesn't allow to finish this route at all. This is not possible (it requires much more space than any of the other ideas), so one important view onto this whole discussion is: can we simulate the static route? (We need something like that to prevent packets from getting stuck in loops.)

One approach is to have a decision algorithm whose result will hardly change over the whole route(!), even if the latter involves huge delays and network changes (which do not invalidate the original route). Using metrics that change very slowly is one way towards this goal, but "change slowly" is only relative to the actual difference of metrics among possible routes, so that difference should be rather large. I doubt that a metric algorithm like this is possible at all.

The suggested flag (any_route) is only a way of giving up, and it may not be able to cover all possible cases.
Recording the number of previous transfers in ware_t would be a better solution (e.g. 4 bits/16 values: allow 14 transfers maximum; 15 means: give up rerouting/don't try to avoid overflowing stops = same as the flag). I am fully aware that extensions of ware_t are extremely unlikely to happen. A comprehensive QoS solution will have more chance to get some data into ware_t.

I also mentioned the automatic deadlock/bouncing detection as a method to (globally) change the behaviour of routing.
Title: Re: Passenger routing code?
Post by: whoami on March 13, 2009, 07:33:39 PM
Some feedback for r2382 with settings
Code: (simuconf.tab) [Select]
seperate_halt_capacities = 1
pay_for_total_distance = 1
avoid_overcrowding = 1
no_routing_over_overcrowded = 1

no_routing_over_overcrowded=1 improves the situation a lot, deadlocks are less likely to occur, and can be dealt with easily when they happen; overflowing stops are reduced by much. There are still some things:
1) the capacity limit is not applied for all goods together, but for goods grouped by type and next transfer stop (this behaviour might be limited to goods being released by a connected factory, routed goods might have other behaviour); it may be useful and intended, but it is still quite generous towards the player.
2) For goods, the input behaviour may now switch between full stop and full flow, depending on the state of transfer stops. When releasing goods, it might be a good idea to check for the remaining input storage capacity of the recipient, and limit the good's amount at the origin stop to that remainder, instead of filling it with as much stuff as possible; the same check could be done for transfer stops, to avoid a fast return of the transfer stop to overflowing state, even worse than before. However, if a vehicle is set to full load at the origin stop, this simple mechanism would be bypassed, to another throttle method would be needed (e.g. control release rate).
3) certain hubs tend to nearly always stay in overflowing state because of 1) and 2) (together with transport delay); instead of yes/no decisions, randomization could be used, with a routing/acceptance probability depending on the grade of over-utilization. (Any call for a random number generator etc. would have to  happen outside of the routing code.)

Now after setting avoid_overcrowding to 0 (does this still have an effect anyway?): I still get some instances of the behaviour with this parameter set to 1: goods will not be loaded if the next transfer stop (the only possible one) is full, although the goods have already been released by the factory, and the recipient is not overflowing. So, the check seems to happen not only for the release of goods, but for in-transit routing, too.

I think that the code for no_routing_over_overcrowded is on the way to provide sufficient control against overcrowding, therefore the behaviour set by avoid_overcrowding (don't load if next transfer stop is full) is not necessary.
Title: Re: Passenger routing code?
Post by: prissi on March 13, 2009, 09:17:02 PM
avoid_overcrowding will be saved already with a game. Setting it to zero after once saved it will not be resetted.
Title: Re: Passenger routing code?
Post by: whoami on March 13, 2009, 10:16:48 PM
avoid_overcrowding will be saved already with a game.
Why would this be necessary, let alone a useful and expectable behaviour?

EDIT: If this is meant for attaching the difficulty level to the savegame, it should still be changeable afterwards. The lowest state of each difficulty setting since start of the map (for use with a "hall of fame") and the current state should be saved (for a custom level, all settings; for a predefined level, only the level itself).
Title: Re: Passenger routing code?
Post by: jamespetts on March 13, 2009, 11:13:52 PM
From what I understand, all settings affecting the simulation are saved with the save games, and have been for a few months. This is related, I think, to the future plans for network multiplayer gaming.
Title: Re: Passenger routing code?
Post by: z9999 on March 13, 2009, 11:29:52 PM
"no_routing_over_overcrowded" don't solve the unrealistic overcrowding problems what jamespetts said.
If 10 passengers arrived at a station and 9 passengers left from that station, overcrowded will happen sooner or later.

The reason is not important. It might be a crossing trouble, or a traffic jam, or player slept.
If once this problem happened, player would lost interest to continue to play that game.

So, some kind of safety guard might be required.

[off-topic]
I often hear that some players want to change the values of max_hops, bits_per_month, passenger_factor, or many kind of costs, and so on after starting the game.
Most of people don't play network game, and they want to play freely as before.
Title: Re: Passenger routing code?
Post by: prissi on March 14, 2009, 12:06:16 AM
There is anGUI planned for this. It is the next thing on my todo list.
Title: Re: Passenger routing code?
Post by: whoami on March 14, 2009, 05:16:46 PM
"no_routing_over_overcrowded" don't solve the unrealistic overcrowding problems what jamespetts said.
This solution isn't perfect, but it's a good feedback mechanism for self-regulation of the network. Overflowing can still happen, but usually not to extreme levels as before. In large networks, the transport delays may cause more extreme behaviour of the "full stop - full go" problem (see above), but in many cases, this may even be cancelled out by the spreading effect with regard to arrival times, also caused by those transport delays.

I already wrote suggestions for fine-tuning. The state of slight over-utilization is actually useful: the player gets to see a message and red spots on the map, and then may check for necessary capacity upgrades and network/routing changes.

Quote
If once this problem happened, player would lost interest to continue to play that game.
I don't see why, because the network keeps working. With blocked generation/release only, deadlocks cannot not happen for passengers and mail (they are not delayed, but lost to the player). For goods, there are situations where the player has to intervene. The deadlocks that I mentioned are caused by avoid_overcrowding, which cannot be switched off any more for my recent savegames, so they are useless for further testing.

Quote
Most of people don't play network game, and they want to play freely as before.
Yes, please. Even more, as network games are not possible yet. Also, somebody (a game moderator) should be able to change settings even in a network game.

There is anGUI planned for this. It is the next thing on my todo list.
OK - a generic list of all parameters would be a good way, so the dialog need not be changed every time a parameter is added or changed.
Title: Re: Passenger routing code?
Post by: whoami on March 23, 2009, 02:13:07 PM
Some more feedback for the use of no_routing_over_overcrowded (here: with existing Pak64 savegames from earlier ST versions):
- the code seems to regulate overflowing stations very well; the stations' capacities have to accommodate the largest convoys that enter them.
- revenue/profit dropped steeply - this can be due to other recent changes in ST, but if no_routing_over_overcrowded is responsible, it means that the effect of overflowing backbones on feeder lines (lowering their utilization) really forces the player to maintain a good QoS, and have enough reserve capacity everywhere. Fast vehicles and high throughput will have real benefit even with the traditional revenue calculation.
- these effects may drastically lower the "exploding profit" symptom that makes the game so easy in later stages of map development.

I hope that I could exclude any influence from pay_for_total_distance and avoid_overcrowding by using older savegames.

Pak designers may have to repond to this change by allowing high-density stations (expensive, high capacity buildings for passengers, mail and goods will be necessary, assuming seperate_halt_capacities=1).
Title: Re: Passenger routing code?
Post by: prissi on March 24, 2009, 12:15:41 PM
If zou used a game from 101.xx or later, it would have saved alreadz the change of the pay_for_distance in the savegame.
Title: Re: Passenger routing code?
Post by: whoami on March 24, 2009, 05:34:05 PM
I have tried a savegame (dated 2007) from 99.14(?) in 100.0 and 102.0 (r2391); there is already a strong drop in revenue when continuing with 100.0 (probably due to the different behaviour of generators and the power network), then again some reduction in 102.0 if no_routing_over_overcrowded=1 (if =0, the values are similar to 100.0).

Simutrans has become harder in recent versions.