Travel time based congestion

[freddyhayward]

https://github.com/freddyhayward/simutrans-extended/tree/travel-time-congestion

I created a new branch with an early implementation of travel time based congestion as proposed by Freahk. At this stage, the core mechanics for private cars now work, but not yet for player vehicles. I would be grateful if some of our more experienced coders could review the changes as they are now and after player vehicle congestion is implemented.

Essentially, the algorithm calculates the additional travel time per tile based on the time taken for vehicles to pass over them: a 100% congestion rating represents double the travel time, while 500% represents four times the travel time.

[Mariculous]

Nice one, I will give it a try. As discussed, additional time per tile perfectly makes sense, it will save a little memory whilst not losing any required information.

I will give it a try, may I ask what does not work about player cars? Don't you measure their times at all currently or is it about calculating the guessed travel times?
In the latter case, I would just assume a player car can travel at min(vehicle_speed, road_speed) on any tile if uncongested. This is not entirely true, for sure, but this guess should not pretty negatively affect the calculations.
In case of curves, this speed restriction does not depend on the actual type of player vehicle, so it's also kind of congestion.
Slopes are more difficult but both types of slowdowns are not a local thing, they depend on where the vehicle came from, thus likely complicated to calculate.

Edit: Speed limits, including curve slowdown can be read from the route_info_t

[freddyhayward]

Player vehicles (buses etc.) are a separate class to private cars. They share a vehicle_base_t but this extends to airplanes/trains etc, and they also use different speed measurements (i think?) etc. It's just a matter of duplicating over the code and changing a few things, which I'm in the process of doing. Or, perhaps there's a more elegant way of merging the two. Since there are multiple ways of traversing the same tile (e.g. moving straight through a junction or turning left), expected travel times are based on the distance traveled by the vehicle, measured at each hop. This also stops prevents 'instant' hops by private cars distorting the data.

As for the maximum speed of vehicles, I'm not sure how complicated it is getting the current top speed limited by curves/slopes/power/weight (edit: get_min_top_speed(), I think? or maybe this measures something else.) compared to the actual top speed defined by the pakset. From what I've seen the first might actually be simpler, but we shall have to see.

EDIT: I have now updated the branch with the implementation for player vehicles, which remains duplicate code for the time being.

[Mariculous]

Ah, so you simply don't measure their times at all yet and there is no player vehicle specific issues, fine, that's all I wanted to know

It's just a matter of duplicating over the code

Please, don't repeat yourself!
You should implement a more general stopwatch (measuring in ticks) or something like that to do the measurement and a general calc_max_speed_journey_time(way, vehicle, enter_direction, exit_direction) or something like that to calculate the estimation.

I had just found 4 (!) different implementations of ticks_to_seconds spread around the code, just in addition to the 4 different measures of time we have ingame already... this made it (and still is) a hassle to work on the seconds_per_month feature, which itself is quite simple but taking care of all these spread around code parts and different time, distance and speed units is really a hassle.

As for the maximum speed of vehicles, I'm not sure how complicated it is getting the current top speed limited by curves/slopes/power/weight

Except for curve limitations I am also not quite sure. (curve) Speed limitations are already stored as mentioned.
Slopes and even acceleration/deceleration sections around changes in speed limit however, would most likely require "simulating" the vehicles movement along these tiles assuming the road is free, also storing that data (per tile) in route_info_t, as that behavior is closely tied to the physics engine.

So if we really only need this to calculate the congestion slightly better, I don't think we should go for it. However, this is roughly the kind of information already discussed in another thread, so if we were implementing the "expected journey times" feature, to support line specific vehicle decision-making, we could "simply" use that calculated data if stored in the vehicle per tile instead of per route between stops.
In any case, this is another feature, as long as it's not implemented, we should simply assume any player vehicle can immediately accelerate to maximum speed.

get_min_top_speed() will simply return min(vehicle1.max_speed, ..., vehiclen.max_speed), thus the slowest maximum speed of all vehicles in the convoy or simply convoys max speed, so that's the one you should query when calculating expected travel time but it won't include information about any of the other mentioned aspects.

[freddyhayward]

With some help from Freahk, I have now refactored these changes into a new class: traffic_vehicle_t inherited by both private_car_t and road_vehicle_t. I believe the branch is now ready to be merged into the main game, hence this pull request: https://github.com/jamespetts/simutrans-extended/pull/141.

[jamespetts]

Thank you for this. Can I check whether this has been tested on a local client/server pair to see whether a network game will remain in sync with this feature?

[freddyhayward]

Thank you for this. Can I check whether this has been tested on a local client/server pair to see whether a network game will remain in sync with this feature?

No, it hasn't, but I will do that now.

[freddyhayward]

After testing for about 20 minutes, including over a new month, there don't seem to be any outstanding issues apart from versioning, which I believe I have just fixed.

[Mariculous]

Great!
There is something I did not mention yesterday when we did the inheritance stuff, I was just terribly tired.
traffic_vehicle_t is not a vehicle anymore as it does not inherit from any vehicle. It should get a name better expressing what it is.
Again, I'm not a native speaker, so namefinding is always hard to me. We need something that expresses "I am an object that measures and protocols additional travel times aka congestion".
Something like congestion_measurer_t could work out, maybe there is a better term for something that measures congestion.

[jamespetts]

Thank you for your work on this - I have now had chance to test this. I have identified two issues so far: first of all, the congestion data do not seem to be saved, but rather reset to zero when saving and loading a game. This will need to be dealt with before this feature can be integrated into the master branch.

Secondly, the measurement seems to expect too high a speed from many vehicles: I have observed on a number of occasions a private car passing an entirely uncongested road and the congestion percentage increases from 0% before the car passes to a higher number (e.g. 16%) afterwards. I have not fully parsed the code, but may I ask whether in your ideal speed calculation you take into account the speed limit of the road itself? In any event, this issue will need to be looked into and fixed before this can be integrated.

I should note that I have not yet tested memory consumption and computational intensity on large maps with this feature, and this will need to be done before this can be integrated.

Thank you again for your work on this: this is much appreciated.

[freddyhayward]

I have just updated the branch, which hopefully fixes both of these issues. The second problem was caused by the unnecessary conversion of yards to meters and ticks to seconds, which caused rounding errors.

As for performance, I couldn't measure a significant increase in CPU usage. There was however a significant increase in memory usage. On a map with 256 towns, my branch used about 7.0GB compared to about 6.8GB on the base game, roughly an additional 200MB.

[jamespetts]

Thank you for that. I think that I will have to test this on a very large map after I have dealt with the other memory consumption issues relating to private car routing discussed elsewhere.

[Mariculous]

Had this been incorporated already?
I noticed congestion values that don't match to the way how "Travel time based congestion" should measure congestion, so I don't think it is incorporated but somehow i had in mind it was incorporated, so I'm a little confused now.

[jamespetts]

No, this has not been integrated yet; I think that I got distracted with the memory usage issue and the various fixes to that necessary.

Freddy - can I check whether this branch is compatible with the current master (with its modified private car routing algorithm)?

[freddyhayward]

No, this has not been integrated yet; I think that I got distracted with the memory usage issue and the various fixes to that necessary.

Freddy - can I check whether this branch is compatible with the current master (with its modified private car routing algorithm)?

No, I can't guarantee it, since there have been many changes to the master since I worked on this patch. I will have to test, but I suspect there will be several pain points around loading/saving and versions. Are you familiar with these parts of the code?

[jamespetts]

No, I can't guarantee it, since there have been many changes to the master since I worked on this patch. I will have to test, but I suspect there will be several pain points around loading/saving and versions. Are you familiar with these parts of the code?

Apologies for not having responded to this hitherto: I have been preoccupied with other matters, and, in the world of Simutrans, had been prioritising the loss of synchronisation.

When you refer to "these parts of the code", do you mean loading/saving generally, or the particular parts of the loading/saving code that you have modified? I am familiar with the loading/saving code generally; is there a particular question that you have about this?

Thank you again for your work on this feature.

[jamespetts]

I have attempted to merge this and resolve the numerous merge conflicts. However, there are significant compile errors which are difficult to resolve without knowing the intention of various parts of the code.

I have pushed the merged version to the travel-time-congestion branch. It would be helpful if you could take a look at this with a view to assisting in the resolution of the compile errors so that I can test this.

[freddyhayward]

Apologies for not having responded to this hitherto: I have been preoccupied with other matters, and, in the world of Simutrans, had been prioritising the loss of synchronisation.

When you refer to "these parts of the code", do you mean loading/saving generally, or the particular parts of the loading/saving code that you have modified? I am familiar with the loading/saving code generally; is there a particular question that you have about this?

Thank you again for your work on this feature.

I mean the load/save functions found in each class, in particular the ones i was modifying (roads, vehicles, etc).

[jamespetts]

I mean the load/save functions found in each class, in particular the ones i was modifying (roads, vehicles, etc).

I am familiar with them to an extent, but the code is so huge that I am not intimately familiar with all of it and how everything relates to everything else, especially those parts of the code that have remained unchanged from Standard.

May I ask what specific thing that you wanted to know?

[freddyhayward]

I am familiar with them to an extent, but the code is so huge that I am not intimately familiar with all of it and how everything relates to everything else, especially those parts of the code that have remained unchanged from Standard.

May I ask what specific thing that you wanted to know?

There was nothing I wanted to know specifically, except for whether any changes made are safe. Thus any relevant changes I'd make would have to be scrutinised. From memory, when I was working on this, I had to increment the version number and add yet another if-branch to avoid crashes.

[jamespetts]

Thank you. This may take some time to review/test in that case.

In the meantime, I had pushed on Saturday an interim change that doubled the reported congestion values - I should be grateful for people's feedback as to how well that this represents congestion.

[Mariculous]

I should be grateful for people's feedback as to how well that this represents congestion.

In some cases it will over-estimate, in others under-estimate.
On average, doubled congestion should represent the actual situation a little better.

[freddyhayward]

I've now updated the branch. It compiles and runs, but seems to stop passengers from being generated at all. I'm not sure how this happened, since nothing in the branch directly changes passenger generation and the effects of congestion shouldn't be enough to reduce it to zero.

EDIT: This also occurs on the latest build, so it isn't related to my patch at all.
EDIT: Solved by https://github.com/jamespetts/simutrans-extended/commit/ca1f2d7fa4799dea65ad4b4b1ba038fc01b2ac20
EDIT: There is another remaining issue where buses are routed incorrectly compared to the latest master build.
EDIT: This issue has also been resolved.

[freddyhayward]

As far as I can tell, the branch is ready to be merged.

[jamespetts]

Thank you for your work on this. Unfortunately, this does not compile in Visual Studio: I get the following error:

Code Select Expand


Severity Code Description Project File Line Suppression State
Error C4716 'traffic_vehicle_t::get_max_speed': must return a value Simutrans-Extended C:\Users\James E. Petts\Documents\Development\Simutrans\simutrans-extended-sources\vehicle\simvehicle.h 48


I have pushed your branch merged with the current Simutrans-Extended master to the travel-time-congestion-2 branch. I should be grateful if you could look into this so that I can work on testing it. Thank you.

[freddyhayward]

Thanks for pointing this out. I committed a fix on my branch which adds a default return value to that virtual function.

[jamespetts]

Thank you for fixing this: it now compiles. However, it fails on attempting to load saved games; the saved game format appears to have been changed incorrectly. For this reason, I have not been able to test the congestion feature itself. I should be grateful if you could look into this.

[freddyhayward]

Thank you for fixing this: it now compiles. However, it fails on attempting to load saved games; the saved game format appears to have been changed incorrectly. For this reason, I have not been able to test the congestion feature itself. I should be grateful if you could look into this.

Thanks, I've just fixed this as well by incrementing the revision number again. The revision number will must always be one higher than current at the time of merging.

[jamespetts]

Thank you for this. I have spent several hours testing this. The latest version, merged with the latest master branch, and with some changes - explained below - is on my travel-time-congestion-2 branch.

This is looking good so far: testing shows sensible congestion numbers measuring over several months (aside from one issue: see below), no recorded adverse effect on performance according to profiling and the ability to remain in sync in a network game for an extended period of time.

There is one bug that I have noticed, however: dead end roads in cities, which are very common on their periphery, show an unreasonably high congestion number. This interferes with the accuracy of one of the new additions that I have made described below.

I have made two changes consequent upon this feature. The first is to recalibrate the congestion display in the minimap to show 250% instead of 100% as the most intense colour, as 100% is not a maximum given how we measure congestion. This produces more granularity of information and is thus more useful.

The second change that I have made is to change the city's congestion measurement (shown on the graph in the city information window) to use the congestion measured in actual tiles rather than a heuristic system that I developed a few years ago. The heuristic system is retained for use when assume_everywhere_connected_by road is enabled. However, this system now records unreasonably high numbers in cities owing to the bug described above.

Once the dead end roads bug has been fixed, this looks as though it will be ready to integrate. Thank you very much for your work on this: this is a significant enhancement.

[Mariculous]

Just a guess on the dead-end congestion: Cars will enter the tile, move in one direction, "reverse" quickly and move back before leaving the tile again, so twice the expected time is spent on that tile. Just an idea what I would check first, might be I am entirely wrong.

[Milko]

Hello

This effect, however, should not occur, it is true that the car goes back but it is also true that there is no traffic from the opposite direction.

Giuseppe

[jamespetts]

Indeed - this is a bug; but I think that Freahk meant that this was the most likely cause of the bug.

[freddyhayward]

I have an idea of how to fix this, along with another problem, but I need help. The solution is simply to call flush_travel_times() whenever a citycar reverses on a tile, so that the travel time will be recorded twice for that tile - once when it reverses, and once when it leaves the tile. I just need help to find where exactly in the code this reversal occurs for buses and cars.

Another problem will be that buses record high amounts of congestion at stops because it takes them much more time than usual to cross a tile they stop at. This should be recorded by vehicles delayed by buses but not buses themselves. I'll attempt to fix this soon.

[freddyhayward]

Actually, the congestion values on dead-ends are so absurdly high that it can't be explained by the extra time spent reversing. It could potentially related to the issue of signed/unsigned integers and over/underflows. I'll have to look into this more.

[freddyhayward]

The general problem I've found is that cars coming out of dead-ends are reported as either driving 0 yards or 4096 yards by the do_drive() function. For comparison, driving across a straight tile is ~100,000 yards and a diagonal or corner is ~70,000.