P****enger routing code?

Topic: P****enger routing code? (Read 52657 times) previous topic - next topic

Re: P****enger routing code?

Reply #70 – 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?

Re: P****enger routing code?

Reply #71 – 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.

Re: P****enger routing code?

Reply #72 – 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 ****ume that the system works as in reality). In reality, there can be no such deadlocks: p****engers 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).

Re: P****enger routing code?

Reply #73 – March 08, 2009, 01:27:15 am

Yes, that solves the problems for p****engers 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.

Re: P****enger routing code?

Reply #74 – March 08, 2009, 01:31:11 am

Quote from: isidoro – on March 08, 2009, 12:23:07 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 p****enger 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, which explains this further.

Quote

Otherwise, beginners will refuse to try ST.

ST is made for real men!

Quote from: isidoro – on March 08, 2009, 01:27:15 am

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.

Re: P****enger routing code?

Reply #75 – March 08, 2009, 11:12:31 am

Isidoro,

there is no reason in principle why goods and p****engers/mail should not be separated in the coding and treated differently. Perhaps discarding could be used for mail/p****engers, and Whoami's system for goods?

Re: P****enger routing code?

Reply #76 – March 08, 2009, 05:15:14 pm

Quote from: whoami – on March 08, 2009, 01:31:11 am

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?

Quote from: whoami – on March 08, 2009, 01:31:11 am

ST is made for real men!

Vide supra

Re: P****enger routing code?

Reply #77 – 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.

Re: P****enger routing code?

Reply #78 – March 08, 2009, 10:09:50 pm

Prissi,

I shall look forward very much to your idea!

Re: P****enger routing code?

Reply #79 – 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...

Re: P****enger routing code?

Reply #80 – 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_p****agiere 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_p****agiere or not.

Re: P****enger routing code?

Reply #81 – 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

Re: P****enger routing code?

Reply #82 – 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.

Re: P****enger routing code?

Reply #83 – 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 p****engers, 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. P****engers 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 p****engers 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 p****engers is to have a quality of service metric based on average waiting times per line per station, and average crowding levels per station. P****engers 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 p****engers could fit into it at all, then newly arriving p****engers should effectively be discarded en route (abandoning their journey or continuing it by taxi). Furthermore, if p****engers have to wait too long at any station, they should also abandon the journey. P****engers 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 p****engers, 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; p****engers 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/p****engers 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/p****engers 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 (p****engers 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.

Re: P****enger routing code?

Reply #84 – 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.

Re: P****enger routing code?

Reply #85 – March 09, 2009, 07:20:07 pm

My patch for r2373.

Re: P****enger routing code?

Reply #86 – 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 p****engers unhappy instead of no route; but then we need more discussion.

Not sending p****engers/goods out to overcrowded stops makes gamesplay actually easier, since one do not need to care about overcrowding. Or am I wrong?

Re: P****enger routing code?

Reply #87 – 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).

Re: P****enger routing code?

Reply #88 – 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 p****engers 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.

Re: P****enger routing code?

Reply #89 – March 10, 2009, 04:09:32 am

Quote from: prissi – on March 09, 2009, 09:25:05 pm

Not sending p****engers/goods out to overcrowded stops makes gamesplay actually easier, since one do not need to care about overcrowding. Or am I wrong?

Not sending p****engers/goods out to overcrowded stops causes deadlock, this is meaningless.
But discarding p****engers 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.

Quote from: isidoro – on March 10, 2009, 01:04:33 am

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.

Quote from: prissi – on March 09, 2009, 09:25:05 pm

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

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

My patch is very simple solution but really reduce p****engers 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.

Re: P****enger routing code?

Reply #90 – March 10, 2009, 10:12:21 am

Quote from: isidoro – on March 10, 2009, 01:04:33 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.

Re: P****enger routing code?

Reply #91 – 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 p****engers 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:

Quote from: isidoro – on March 10, 2009, 01:04:33 am

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.

Re: P****enger routing code?

Reply #92 – 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 p****engers/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.

Re: P****enger routing code?

Reply #93 – 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.

Re: P****enger routing code?

Reply #94 – 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?

Re: P****enger routing code?

Reply #95 – 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, p****engers/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 p****engers too?

Re: P****enger routing code?

Reply #96 – 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 p****engers will be unhappy. This is the option no_routing_over_overcrowded = 1 in simuconf.tab.

Re: P****enger routing code?

Reply #97 – March 11, 2009, 01:42:21 pm

@prissi: good luck with it. I hope I'm wrong.

Quote from: Dwachs – on March 11, 2009, 06:27:24 am

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.

Re: P****enger routing code?

Reply #98 – 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.

Re: P****enger routing code?

Reply #99 – 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 p****engers waiting at a station, where I was turning over vast profits. That sort of setup is simply absurd.

Re: P****enger routing code?

Reply #100 – March 11, 2009, 08:17:45 pm

Quote from: 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.

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.

Re: P****enger routing code?

Reply #101 – March 11, 2009, 10:08:16 pm

Quote from: prissi – on March 11, 2009, 09:42:21 am

I followed z9999 idea of letting the suche_route check for overcrowding. If overcrowded route, goods will not sent out (reducing profit) and p****engers 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.

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 ****ume 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 p****engers/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.

Re: P****enger routing code?

Reply #102 – 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 p****engers, 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 p****engers 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 p****engers'/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.

Re: P****enger routing code?

Reply #103 – March 11, 2009, 10:39:51 pm

Quote from: jamespetts – on March 11, 2009, 10:22:54 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 p****engers 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 p****engers'/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)

Re: P****enger routing code?

Reply #104 – 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 p****engers), 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 p****engers 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.

P****engers/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 p****engers/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?