Lightweight private car routing

[Qayyum]

Code for old frame capture, then code for new frame capture

[jamespetts]

I have now merged the latest master branch into this, which includes Ranran's UI patches relating to coupling and the convoy detail window. This had a conflicting saved game version, so old saved games created with previous versions from this branch will no longer work. Games saved from any master branch build should be unaffected.

In relation to the SDL2 build, I have not set up my Windows computer at home to build this: only the server's cross-compiler builds this version, which is how the nightly builds are made. The best way for me to test the relative responsiveness is to compare the semi-optimised GDI builds from the master branch and this branch.

As to performance, I suspect that the issue may be the processing of the routes, which is done single-threadedly and may be memory bandwidth intensive on slower machines. I will need to look into rationing how many of these are done in any given step and generally improving the scheduling features of this algorithm.

However, any further testing in relation to this in the meantime would be most welcome. Thank you all for your feedback so far.

[jamespetts]

I have undertaken now some brief testing on this. On my quite fast computer (Ryzen 3900x), the processing of private car routes takes 15-20ms per city in a semi-optimised build. The Stephenson-Seimens server has a total of 37 cities, so, if these were all to be done in a single step, that would be 555ms in a step, or over half a second. A slower computer and/or a larger map would increase this time further. This would account for the intermittent slowdowns reported.

So, it seems that what it is necessary to do is to schedule the processing of routes, which needs to be a single-threaded operation, so as to process only a limited number of cities each step. This may well require saving more data, so note that any saved games with the existing version may well not function when I have implemented this. Games from the master branch should be unaffected.

[Mariculous]

So, it seems that what it is necessary to do is to schedule the processing of routes, which needs to be a single-threaded operation, so as to process only a limited number of cities each step.

If the memory consumption for the stored routes is not too large, we could just do the same procedure as you do with the stored routes in the cities: Store two routing maps, so you can prepare the whole update in parallel and the only thing that has to be done in sync is somehow switching to the updated map.

However, cutting the line update process into (time) frames is a good idea nevertheless. Maybe we should just limit the number of calculated routes per route calculation cycle in relation to how long the last line updating sync step has taken. For sure calculated number of route calculations for the next calculation cycle needs to be communicated in between server and clients.

[Matthew]

Thank you all for your testing: that is most helpful. I believe that I have now fixed the freeze issue: I should be grateful if people could re-test.

I have been testing Ranran's acceleration curve patch, but hopefully I'll get round to this too.

As to the reported frame skipping, this is not something that I have clearly observed, although my new computer is quite fast. In a semi-optimised build , the game is entirely smooth without scrolling; scrolling the map can be a little uneven, but, if I recall correctly, this is normal behaviour for a semi-optimised build using GDI rather than SDL2.

Can I check -for those who report frame skipping, does this occur after any road tiles have been deleted? I need to know whether to investigate the mechanism with detecting broken routes in this respect or whether such problem as there may be lies elsewhere.

The frameskipping occurs from the moment the savegame loads, before any routes can change at all. BTW my config.default file says that I am building SDL2. If that's correct (I don't know enough to be certain), then this is not just a GDI problem.

Edit: Incidentally, Matthew: you might find that your games balance better at the default meters per tile setting, as the entire pakset is balanced for this setting. Altering the meters per tile setting should be considered advanced pakset editing.

I imagine I'm going to be playing for non-default mpt settings for as long as the default gives months of 6:24:00. I enjoy the role-playing side of the game and being able to make sensible timetables is important to me. I realize everyone would like round months in a perfect world and I guess that you have had a look at this and found it very difficult to implement. And I don't doubt that it's a non-trivial task: the reason that I haven't replied to the thread on rounder months is that I can't easily understand the maths (I need to sit down with pen and paper sometime to figure it out). Plus the whole scheduling mechanism is a piece of Heath Robinson genius built on Carl's abuse of the waiting time system! Since the alternative is re-writing some of the fundamental parts of a twenty-year old game, I'm happy that changing one line of simuconf.tab gets me what I want, even if it has a few rough edges! And having shorter months is a bonus.

On my quite fast computer (Ryzen 3900x)

the processing of private car routes takes 15-20ms per city in a semi-optimised build. The Stephenson-Seimens server has a total of 37 cities, so, if these were all to be done in a single step, that would be 555ms in a step, or over half a second. A slower computer and/or a larger map would increase this time further. This would account for the intermittent slowdowns reported.

So, it seems that what it is necessary to do is to schedule the processing of routes, which needs to be a single-threaded operation, so as to process only a limited number of cities each step. This may well require saving more data, so note that any saved games with the existing version may well not function when I have implemented this. Games from the master branch should be unaffected.

Thank you for your continued efforts; finding the cause seems like a breakthrough. My test game had 79 cities on a very slow computer, so that would explain it.

[jamespetts]

I have pushed a number of changes to this branch: I should be grateful if anyone who has tested this so far could re-test. Note that saved games from older versions of this branch will not work.

There are two principal changes.First of all, I have scheduled the processing of private car routes so that only one city is done per step. This should improve performance, but it is difficult for me to test on my computer, so it would be helpful if others with slower computers could test this and compare with the current master branch.

Secondly, I have added a dynamic congestion system. Each tile of road now has a congestion percentage based on the number of vehicles that stopped in the tile in the last 2 game months compared to the number of vehicles that passed through the tile. This percentage will cause the route finding system for private cars to regard passing through that tile of road as taking longer, and thus be less likely to use it. (If congestion is 100%, it will be regarded as taking twice as long to traverse the tile; at 50%, it will be regarded a taking 1.5 times a long). These longer journey times may also affect whether passengers take their private cars or use player transport. Player road vehicles will also take notice of congestion when routing.

The congestion system should help to give rise to more effective balancing, so that cars use a multiplicity of routes and that gridlock is less likely.

Edit: Incidentally, I recommend this video for anyone using this new feature:

Edit 2: I have now also added a display of the congestion to the minimap.

[Phystam]

I am now testing your great work.

Very heavy traffic jams. However, there is some space to go ahead. the distance between the two cars is fixed (1 tile), so it can easily cause heavy traffic jams.


When I deleted an intersection, a segmentation fault occurred. see below:

[Mariculous]

About the congestion, do I understand it correctly?
Be p is the number of vehicles that passed a road tile, s the number of vehicles that stopped on that road tile, then the congestion is defined as (s/p), i.e. if all of the vehicles stop at that tile, we will have a congestion of 100%
That approach may be betteer than the current congestion measurement but there won't be a real relation in between the congestion level and travel times. However, maybe this works out well, maybe it won't. We will really neeed some empirical observation of this ingame.
May you please add congestion information to road tiles information window if not done yet?

Edit: Incidentally, I recommend this video for anyone using this new feature:

I want that house moval feature in simutrans-ex

Btw. is that Motorway really an actual motorway sign in the UK? Do you animals really read the sign and understand they are not allowed to use the motorway o.O From the video it seems so as dogs seem to be sleeping on roads when there is no such sign disallowing them to use the road

[jamespetts]

Phystam - thank you for testing. I have pushed what I believe is a fix to the crashes; I should be grateful if you could re-test. As to traffic jams, that is why I added the congestion feature so that cars would be less likely to use congested routes; but it takes a little while in game time for the congestion to register. Ideally, it would be good to allow more than one car per tile, but that would be a tricky project and I have to prioritise other things. There is reference to this on the coding projects thread.

Feahk - yes, that is the way that congestion works. I could not find or devise any better way of doing it than that at this juncture; if anyone has any ideas that will not be too computationally intensive or time consuming to code, I should be interested.

Congestion information is not only in the way's information window, there is also a congestion display in the minimap.

As to motorway signs: I believe that that is an early sign. The modern signs are more basic and do not give a list of all the rules because they are now well known. And that dog was a bit silly, I think. I do not recommend sleeping on even a relatively quiet road.

[Mariculous]

I had already quickly discussed this at Stephenson-siemens server but for completeness and anyone who was not involved, I post it here again:

Feahk - yes, that is the way that congestion works. I could not find or devise any better way of doing it than that at this juncture; if anyone has any ideas that will not be too computationally intensive or time consuming to code, I should be interested.

I guess an average speed based approach would be the best as guessing travel times from travel times in the past is most straight forward and preciese I guess.
To achieve this we will need to
- remeber the exact ingame time (ticks) when a vehicle entered a tile.
- remember the summed up travel time on each road tile.
- remember the vehicle count of each road tile (as-is)
- optionally remember the summed up best-case travel time of vehicles that have passed on each road tile.

Without the optional best-case travel time, we assume that most of the vehicles using a road can actually drive as fast as the roads maximum speed or are one of the fastest vehicles currently available. A guesss, that is fine in the ~1900s but not that good in early years.

Whenever a vehicle enters a tile it will remember that exact time. Whenever it leaves the tile, it will calculate time_left-time_enter=tile_travel_time and add that time to the tiles overall_travel_time counter.
Additionally, it will inrease the ways vehicle_counter by 1 (which is currently already done)
These given, overall_travel_time/vehicle_counter will be the average speed of vehicles on that tile within the captured duration.
However, that average_speeed does not at all consider if the vehicle was able to move faster than the captured time, thus a road used by a single very slow car per month without any other traffic on that road will be considered highly congested, thus nobody will be routed to that road even though it is actually not congested at all.

This is where the best-case travel time comes in:
When a vehicle leaves a tile, it will in addition to the above described, add its best_case_travel_time to ways overall_best_case_travel_time counter.
Best case sounds like some magic guess, but it's not. It's quite simple and efficient: best_case_travel_time=min(vehicle_speeed, way_speed)/tile_distance.

The relation overall_best_case_travel_time/overall_travel_time=speed_factor will give us a factor from (0,1] which tells how many percent of the theoretically achieveable maximum speed was reached in average by vehicles passing this tile. 1-speed_factor will be the congestion (I don't think we are really interessted in it apart from stats maybe)

A good guess for travel times of each individual tile would then be min(vehicle_speed, way_speed*speed_factor)/distance.
This expects that vehicles which are slower than the traffic flow on that tile to not being affected by the congestion, which is not exactly preciese but I'd say it's a good guess.

[Matthew]

A few observations from a very quick test of this branch as of the end of 20-02-01, using Pak128.Britain-Ex. There was no frameskipping  , but these were small maps, so that may not be significant.

Congestion information is not only in the way's information window, there is also a congestion display in the minimap.

These both seem to be working well and are good additions to the game; thank you!.When I looked at the congestion hotspots, I noticed that they were often caused by pedestrians. That makes sense to me, pedestrians also congest roads, but I'm not sure whether it's what you expected or not.

I got a crash and a freeze. In both cases, I was just running one bus and fast-forwarding to see what happened. For the crash, the terminal just says

Code Select Expand

ERROR: void stadt_t::check_all_private_car_routes(): Townhall road does not register as being in its origin city - cannot check private car routes
For help with this error or to file a bug report please see the Simutrans forum:
http://forum.simutrans.com
Segmentation fault (core dumped)

That error message was repeated a lot in the logfile. I know that an unreproducible crash isn't much use, but I thought the error message might be helpful.

The freeze happened when I tried to rotate the map (while paused), the terminal reported:

Code Select Expand

Message: void convoi_t::hat_gehalten(halthandle_t halt): Convoy (1) AEC Regent STL (revised) departing from stop Lesser Sydbourne Rugby pitch Stop at step 19297. Its departure time is calculated as

Thread 1 "simutrans-exten" received signal SIGSEGV, Segmentation fault.
0x0000555555965e95 in private_car_t::can_enter_tile(grund_t*) [clone .part.75] ()
(gdb) backtrace
#0  0x0000555555965e95 in private_car_t::can_enter_tile(grund_t*) [clone .part.75] ()
#1  0x00005555559698df in private_car_t::hop_check() ()
#2  0x0000555555977af6 in vehicle_base_t::do_drive(unsigned int) ()
#3  0x0000555555963b7e in private_car_t::sync_step(unsigned int) ()
#4  0x000055555592ff9c in karte_t::sync_list_t::sync_step(unsigned int) ()
#5  0x000055555593045f in karte_t::sync_step(unsigned int, bool, bool) ()
#6  0x00005555558cdc7c in interrupt_check() ()
#7  0x0000555555956ef3 in karte_t::interactive(unsigned int) ()
#8  0x00005555558dc654 in simu_main(int, char**) ()
#9  0x00005555558f2292 in sysmain(int, char**) ()
#10 0x00007ffff6748b97 in __libc_start_main (main=0x5555555ab480 <main>, argc=5, argv=0x7fffffffdfd8, init=<optimised out>,
    fini=<optimised out>, rtld_fini=<optimised out>, stack_end=0x7fffffffdfc8) at ../csu/libc-start.c:310
#11 0x00005555555ab4ea in _start ()

Curiously, the Townhall road does not register error message never appeared in the logfile for this game.

[Qayyum]

Which road tile inaccessible

[Phystam]

When I modify a terrain, I get a segmentation fault. Probably, the problem is not related to terrain modification, but deleting roads.
see below:

[jamespetts]

Thank you both for testing. I cannot be sure that I have been able to capture the individual crashes reported without an exact reproduction case, but I have made some changes which I hope will fix the crash bugs - I should be grateful if you could both re-test.

I have also identified some errors relating to map rotation, which I have fixed.

[Phystam]

I played just the same way, but the crash did not occur. thank you.

See this video:
https://cdn.discordapp.com/attachments/665986412641779712/673531997020487711/Simutrans_120.2.1_Extended_Nightly_development_build_14.9_c7c8169_2020-02-02_23-14-13.mp4
The road is oneway. when a citycar enters the oneway road and he wants to go back since he does not want to go outside of the city, he struggles. This may cause a traffic jam behind the citycar.

And FPS problem. in my map (this is the same map of pak256 default demo map), when I start to play the game, it is ~30 fps. but gradually the speed is getting slow down. After several minutes, it becomes ~5 fps or less.

[Mariculous]

The road is oneway. when a citycar enters the oneway road and he wants to go back since he does not want to go outside of the city, he struggles. This may cause a traffic jam behind the citycar.

Dead-end detection for oneway roads required?

Well no, the simple dead-end detection won't work here and a definite dead-end detection won't be performant. This needs another kind of fix I fear.
It's a difficult situation in any case.

[Phystam]

Probably, If the way is oneway (or placed an oneway sign on the way), it is necessary not to go back.

Private cars whose origin and destination are within the same town would continue to behave as they do now, and drive around randomly, with one change: they would refuse to go outside the boundaries of the town. If they were to get to a road heading out of the town, they would turn back.

This section should be modified a little.

[jamespetts]

Thank you for that: I believe that I have now fixed the issue with one way roads. I should be grateful if you could re-test.

[jamespetts]

I have also pushed the fix for the heuristic method to the master branch.

[Phystam]

Thank you for the early fix! I checked that the issue is solved.

[jamespetts]

Excellent - thank you for confirming.

[wlindley]

Testing this morning and it seems that deleting a single section of road at major intersection in city will cause a crash.  Freezing the game, deleting the section, Save the game, un-pause: Crash. Reload same game: Continues OK.

[Phystam]

Testing map using pak256.

Highway drastically changes the road traffic.

[Qayyum]

For Congestion, given every month, the more congested, the ( the higher the time stop, the more congested)

[jamespetts]

Thank you all for your testing and feedback. W. Lindley - there have been some crashes of this sort fixed since this morning, so I should be grateful if you could re-test with the latest commits.

Phystam - that is a very interesting map. If I understand you correctly, this is precisely the effect intended, and it is very interesting to see it in action. It would be interesting to be able to download this testing map.

Qayyum - I believe that this is similar to what Freahk has suggested above.

[Matthew]

I did some testing on medium-sized maps (256x256 up to 1024x1024, 40-80 cities), with a build incorporating up to #4cc56f56bc5fa1fbfc8e14103e46e3b5ed11b077. The frameskip situation seemed a little better than before. But on a 19th-century map with ~2,500 convoys (created on another branch, if that's significant), watching convoys move was still unpleasantly jumpy. New maps of this size in 1960 were unplayable: the Displays Settings window was showing 0 fps after a few seconds! I could open the minimap, but on one map even moving the viewport seemed impossible (nothing happened for ten seconds). I had one crash, but can't give any useful feedback from it.

Obviously it's your right to change the game as you see fit, James, but at the moment this branch would be a backward step for me.

BTW I prioritized trying different maps this time (different sizes, with and without GDB), etc. Is there any reason to think that performance might improve if I ran the game for longer?

Testing this morning and it seems that deleting a single section of road at major intersection in city will cause a crash.  Freezing the game, deleting the section, Save the game, un-pause: Crash. Reload same game: Continues OK.

W. Lindley - there have been some crashes of this sort fixed since this morning, so I should be grateful if you could re-test with the latest commits.

I was able to delete several intersections without crashes, though maybe I was just lucky.

Testing map using pak256.
Highway drastically changes the road traffic.

Good news! Thank you for getting this to work, James!

[jamespetts]

Matthew - thank you for testing. Could you upload the saved games that you are finding slow so that I can run a performance profiler on this to investigate the cause of this? Also, it would help to know your computer's specifications. Thank you.
Edit: Some brief testing seems to suggest that there is an issue, the cause of which I have so far been unable to identify, in which a newly created game will consume much more time processing routes than a saved game. Can I ask you to save and load the game and see whether this makes any difference to the performance?

[jamespetts]

I think that I have now fixed the performance problem, which was a bug causing too many private car routes to be generated. I should be grateful if you could re-test.

[wlindley]

Latest ( d1e3688f9b47ab6ee0c9cd0a2b549c8981d0ac54 ) seems to resolve the performance problems (consistently 80 to 100x at fast-forward on my machine) as well as the crash-on-remove-road issues.  So happy with this.

[Phystam]

Fantastic, you are like a wizard. Are you from Hogwarts?
After 30 minutes, the frame rate was still ~30 fps on my Ryzen 3700X computer. I will run the game for several hours for testing.


EDIT:
After 4 hours, it keeps ~30 fps. After playing this, I will test on a network game with the pak256-Ex developer team.

[jamespetts]

Thank you both very much for testing: that is most helpful. I have detected a network desync problem in the latest version. I have an idea what the problem may be (I suspect that it is related to using the current month's data for congestion), but have not had time to test this yet, so I will have to do this when I get home. There should be another version to test when I have had a chance to deal with this.

[Phystam]

What type of desync informations is needed? When I catch such a problem, I will tell you.

[jamespetts]

What type of desync informations is needed? When I catch such a problem, I will tell you.

Thank you for the offer - but I have now fixed this. I should be grateful if you could re-test. I should note that the fix breaks saved game compatibility for older saved games on this branch, but not master branch saved games.

[Matthew]

Some brief testing seems to suggest that there is an issue, the cause of which I have so far been unable to identify, in which a newly created game will consume much more time processing routes than a saved game. Can I ask you to save and load the game and see whether this makes any difference to the performance?

I have tested again up to commit #d1e3688f9b47ab6ee0c9cd0a2b549c8981d0ac54.

Performance is much better.... for a while. There is a noticeable wave pattern. At first, the peaks attain >=30fps and the occasional troughs are about 10fps. As time goes by, performance gradually slows until the peaks are ~18fps and the long troughs are 6-8fps, which is unpleasant to play.

Saving and loading game does not seem to make any difference.

Matthew - thank you for testing. Could you upload the saved games that you are finding slow so that I can run a performance profiler on this to investigate the cause of this?

I guess this may be unnecessary in light of your commits today, but I have two games made on this branch. Here's a typical 1960s game created on this branch (as of  #d1e3688......), which only requires pak128.Britain-Ex nightly. Unfortunately, the 1850s game (this branch, #d1e3688....... or master branch I mentioned in the previous post requires my add-ons.

Steps to use my add-ons:
1. Create a new pakset directory to make sure that you don't mess up your normal pakset:

• In Windows, create a pakset directory called Pak128.Britain-Ex-235 and copy the nightly pakset into it.
  
• In Linux, create a symbolic link to your nightly pakset, called Pak128.Britain-Ex-235.

2. In both cases, download my addons from here and unpack the file into your Addons folder.
3. Start Simutrans-Extended with the 235 pakset and addons.

If Sim-Ex crashes, it is probably because the addons have not loaded due to a separate issue. Check whether with_private_paks = 1 in \Pak128.Britain-Ex-235\config\simuconf.tab. In Linux, this may require you to replace the symbolic link with a complete copy of the Pak128.Britain-Ex pakset. 

Also, it would help to know your computer's specifications. Thank you.

My computer's specifications: Lenovo G570, Intel Core i3-2330M @ 2.2GHz (2 cores 4 threads), integrated HD3000 graphics, 4 GB DDR3 RAM @ 1333MHz, SSD, Ubuntu 18.04.3. So about 8% of the power of an R9 3900X, according to cpubenchmark.net. Try not to laugh too much! Though that website claims that it is slightly less puny when comparing single threads (about 40% of the Ryzen)

[jamespetts]

Thank you for that. I did want to load the 1960s game, but when I click the link, I get only a blank page; is there some complexity here?