The International Simutrans Forum

There has been a long-standing plan, documented in the development projects thread (https://forum.simutrans.com/index.php/topic,8172.0.html) to have a better, route based simulation of private car traffic. However, it is apparent from the amount of computational load taken by private cars in a large game already (specifically, the current Bridgewater-Brunel server game in the game year 2004, started in the actual year 2017) that the system that has been described there for some time is unlikely to be workable from a computational load perspective, as would any system that involves individual private cars undertaking individual route searches, even truncated route searches.

Yesterday evening on the Stephenson-Seimens server, there was discussion about private road tolls, which had hitherto been set to 0.01c/km for private cars. Some research suggested that real life road tolls in continental Europe tended to be about 0.05c/km. This seems to equate to about half of a (cheap) UK rail fare for passengers. I have now changed this value in simuconf.tab to 0.15c/km. (I had initially set it to 0.28c/km, which is approximately half 55, being the fare for "low" class passengers for the shortest distances; but have now changed it to 0.15c/km, being half the "very low" fare for longer distances, that is, half of 60% of 50).

This, in turn, arose out of a discussion about traffic congestion in cities, and how this could (realistically) be made worse by players connecting cities with their own roads and allowing private cars to use them. Without more realistic levels of road tolls, players would have an unrealistic incentive to not to allow private cars onto their roads so as to reduce (realistic) congestion in towns and cities. This is why I increased the road toll. (For reference, road tolls for player vehicles are calculated as a proportion of their revenue for the proportion of the journey that they spend on the other player's way, based on Railway Clearing House practice of the 19th and early 20th century; a different system applies to ports and airports). However, I then realised that a problem is that, if players have a stronger incentive to attract private car traffic to their private roads, there needs to be a system for making sure that cars only use those roads if they go somewhere useful, or else players will have an incentive to build lots of roads to nowhere from their large cities.

There is still some incentive to build useful connecting roads in the current implementation: a road connecting two towns will absorb private cars from both towns rather than one, doubling the sources of private cars using the road, and will also increase the total number of private cars generated in both towns, increasing the number of potential users of the road. However, that there is any financial reward for building a road to nowhere at all is problematic in balance terms.

What I write below will be reproduced in the development project thread. The existing/old feature description is reproduced below for archival purposes.

The new, lightweight proposal

The current system
Currently, individual private cars in the game do not follow any route. They are generated whenever a private car journey is generated by the passenger generation system on a road immediately adjacent to the building which generated them. They then drive around randomly until an internal timer, set when they are generated, tells them to disappear (despawn). The reason that private cars do not follow any route is that pathfinding is computationally expensive and having all individual cars actually try to find a route in a larger game would overwhelm the computer.

However, private car traffic has been for some time in Extended now based on some basic sort of routing, albeit this is not reflected in the behaviour of the car objects in game (except in one specific way, set out below). Unless the "assume_everywhere_connected_by_road" setting be enabled in simuconf.tab, each town checks whether it is connected to each other town, out of town industry and out of town attraction by road. Only if the passengers' destination is within a town connected by road to the origin town, or is an attraction or industry connected by road to the origin town, will a private car journey for those passengers (and thus a private car object in game) be generated. Because this is a per town check rather than a per car check, this is within the limits of what is computationally feasible. Furthermore, this has been multi-threaded since 2016.

The journey time for private cars is calculated based on the actual route between the towns; a journey time per tile of as the crow flies distance is calculated for both within town journeys and town to town journeys, based on the length of the town to town journey, the speed limits on the ways, and the average speeds of the private cars currently available (the car objects shown in the game). Journey time is also affected by congestion: the congestion graph in the city window is a percentage, showing the additional journey time that cars in that city will calculate based on congestion. For example, if a town has a congestion figure of 25%, journeys within that city will take 125% the amount of time that they would take if congestion were at 0%. For journeys between two towns, the congestion values of both towns are averaged. This journey time per tile figure is then extrapolated to find the (estimated) journey time for the private car journey, which is then compared to the journey time for public transport routes. If this journey time is shorter than the public transport journey time, or the passengers have been randomised to "always prefer private car", and the private car journey time is within the passengers' journey time tolerance, the passengers will initiate a private car journey.

Importantly, the despawn timer for private cars is set to match the estimated length of the private car journey. This means that the number of cars on the road at any given time should be maintained at a realistic level, and not accumulate excessively because the cars cannot find their destinations.

This system works well for approximately simulating traffic congestion and density inside towns: it is observed in the game that there will be more traffic in parts of towns near high density buildings and that this traffic will gradually get lighter towards the outskirts of towns. The traffic effectively behaves like smoke, densest near the points of origin, gradually dispersing further away. This works less well for travel outside towns, however, where traffic is equally likely to end up on a road to nowhere as it is a road to a useful destination.

The proposed changes
If, instead of discarding the tiles constituting a route to any given destination as at present, the private car route finder were instead to store (1) the destination (a co-ordinate is probably better than a pointer here); and (2) a direction in the tiles of road constituting the route, then this would allow private cars to follow the route without doing their own routefinding.

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.

Private cars whose destination is outside the origin town would start by driving around randomly as now. However, at each junction (intersection), they would check whether the tile in question is marked as being part of a route to their destination. If it is, they would turn to travel in the direction that that route points. They would not leave a town unless (1) the tile outside the town is on a route to their destination; or (2) the tile outside the town is in another town (i.e. an immediately adjacent town). If at any point in their journey, the route were broken (e.g. because a tile forming part of the route has been deleted), they would simply revert to driving around randomly.

In all cases, the despawn timer would remain the same as it is now.

This would somewhat increase the memory overhead for ways, and the computational overhead of the private car route finder, but these should (hopefully) be relatively modest, especially as the latter is multi-threaded. (I will have to check to see how much memory that ways take up already). It may also somewhat increase the computational intensity of the private cars' sync_step (i.e. the code for moving them around), although by how much is debatable.

Private cars' sync_step already takes a fairly substantial proportion of processor time in very large games in the modern era (the Bridgewater-Brunel game with 768 towns in the game year 2004, for example). Multi-threading this may be an option. Multi-threading this would work by having batches of cars check which tile that they should turn to next simultaneously (e.g., if there are 100 cars and 4 threads specified in simuconf.tab, process 4 batches of 25 at a time in 4 threads), but not execute the movement until after all the threads have terminated. I have not investigated the code in enough detail at present to know whether this is feasible, but I know that the "hop_check" part of private cars' sync_step routine takes a lot of time (collectively) on the Bridgwater-Brunel 768 town map in 2004.

There is then a question of whether congestion should be calculated differently. For journeys within a town, the current congestion system, based on the city's congestion rating, should be retained, as it is a reasonably good proxy of general congestion. However, for journeys between towns, it would be helpful to track the congestion of individual road tiles. Quite how to do this is an interesting challenge. One approach is the traditional Sim City style option of having each road type having a capacity of cars per (game month) and any excess of that recorded as congestion. A complexity here is that marking a road as one way will double that capacity; but it is very difficult for the game to work out whether any given tile of road is one way as this can be done by signs placed on a tile of road a long way back. An alternative is some sort of system of measuring stationary traffic, but I cannot think of a way of doing this that is not likely to be excessive in memory and memory bandwidth consumption. This may need more thought. Without a satisfactory alternative congestion measuring system, the existing system would have to be used.

The archived proposal

Quote
Private road traffic simulation

Note: This feature will need more careful consideration following investigation some years ago into the performance impact of this on larger maps: see here (http://forum.simutrans.com/index.php?topic=9595.0) for a description of the problem and a discussion of the solutions.

This will be a particularly large (but also potentially satisfying) project. The idea is to have private cars shown in the game actually follow routes from their origin to their destination, such that congestion along particular routes can more easily be simulated, but without creating so much CPU load as to make the game unplayable. This was discussed here (http://forum.simutrans.com/index.php?topic=8909.0), and the description below is reproduced from that thread.

This idea is loosely based on the way in which the people who made Sim City 4 dealt with the problem of it being too computationally expensive to calculate lots and lots of routes through a relatively complicated network constantly: to have fixed private car routes from specific origins to specific destinations which are updated only periodically.

In the game as it currently stands, unless one turns assume_everywhere_connected_by_road on, the game will in any event calculate routes between each city and each other city, and also between each city and each industry and each attraction, but discard the actual route tiles once the average time per straight line tile for the journey is known. I had considered simply using these routes, but realised that this would not be effective for journeys inside cities, or where cities are close together, such that the distance between two cities is less than, equal to or not much more than distances within the cities.

What would be better would be to have fixed routes to a particular destination cities, attractions and industries stored in tiles individual tiles. Only one route to a particular city (including the city in which the tile is located), industry or attraction can start at any given tile. These routes are renewed periodically, and the particular part of the destination city at which the route ends is selected randomly. The rate of renewal would be set by a parameter in simuconf.tab. Whenever a private car journey is required from a particular start tile (passenger journeys - even in Standard - always originate at a particular building, not station), the system would perform a search of a predefined number of surrounding tiles (the radius being set by a simuconf.tab parameter). If a non-obsolete route is found to the destination city, industry or attraction, then that route would be used. If not, a new route would be calculated. If no route at all could be found, the destination would be marked as unreachable in the surrounding tiles so as to prevent multiple repeated failed searches consuming excessive computational power.

The cars would then all drive along the route to their destination. The number of cars would be based on a reworking of the existing "traffic level" simuconf.tab parameter, which would be reworked so as expressly to become a private car occupancy rate setting, and the number of car journeys adjusted accordingly. It would probably be better for the "traffic" graph in the city then to show only outgoing cars, so that players can more easily use it to tell what proportion of people from that city use the car to get to their destinations (making it comparable with the "transported" and "passengers" graph).

Congestion would be calculated differently to the present system: every road tile would record the time in the current and previous month that road vehicles have been stationery upon it. The congestion in a city would be calculated by adding up all of the values for road tiles within that city and normalising them, probably based partly on constants set in simuconf.tab.

Further, journey times would also henceforth be based on actual recorded journey times by the private cars completing their routes (each would store their journey start times, and would register their total journey time on completing their journeys). For cases in which no private cars have yet completed the particular journey, the time would be approximated in a similar fashion to the way in which it is approximated now. The actual routing mechanism (both for city cars and player vehicles) will take into account the congestion on each tile when calculating the best route. It will probably be possible to create an overlay map, much as in Sim City, showing congestion per road tile as various colours.

That way, congestion will be simulated as accurately as the power of contemporary computers allows: congestion measurements in cities will be based on actual traffic jams, and roads will become congested with actual cars based on their actual usage, simulated accurately. There will be incentive to alleviate congestion along specific routes by upgrading roads (the role of the public player being thus enhanced), and player vehicles will both contribute to and suffer from congestion in a realistic manner.

Jamespetts, private cars coming from several cark parks would be beneficial?

Looking up tiles in several possible routes can be computationally expensive too (depending on route length), since the routes are rather weakly ordered (the sum of x+y can only change by 1 per hop).

Standard has car going to destination by storing a target coordinate in, and at a crossing decide to take the turn which goes closer to the target. If memory servers me right, you used this in experimental at least at the beginning. This "pathfinding" is far from perfect and only about 10% of the car actually arrived near their destination. (One could improve this by using a 30% chance at each turn to go somewhere and 70% by reducing distance for non-trivial routes.) Or cars can have a history of vthe last 50 visited tiles and avoid routes in them to find way out of cul de sacs. Or going for less driven roads or roads with more convois (so one would need to separate convois driven last month and citycars driven last month on ways).

Quayyum - car parking is a separate proposed feature: see the description of that in the coding projects thread linked above.

Prissi - I am aware of the "DESTINATION_CITYCARS" feature: I believe that this is still implemented, but it seems to make little difference compared to random movement in practice.

In terms of the computational expense of looking up routes, do you mean the computational expense of private cars checking through a list of several hundred routes when they reach a tile to see whether a route to their preferred destination is on that tile? I am not sure that I fully understand the reference to weak ordering if this is so. If you meant something else, I have not understood: my apologies.

Yes finding a tile in a route means going through each route. Just going in one direction (of smaller distance) until distance increases again will not help, because it will stuck in the same way as a normal DESTINATION city car. Furthermore, if the routes cover allmost all road tiles, then looking through all routes is more expensive than an actual route finding. Furthermore trucks in the original TTD just used this wayfinding of DESTINATION_CITYCARS.

If a car knows town A is directly connected to town B and the destination is in direction of town B (and not closer than say 1.5 the distance between the towns), then it just has to search a route to town B. This is much faster (since it will suceed) than looking up the entire route. It will visit not much more than 1.5*tiles than the distance between the towns. (One could set this even as maximum for route search.) This is much less than the coordinates to xearch in 100 or routes.

I am still a little unclear on what sort of route search that you were imagining, as the description does not seem consistent with the system that I had in mind: one of us is misunderstanding the other, I think, but I am not sure who it is. My apologies if it is me.

What I had in mind was that the data that would be stored in the road tiles for each route that passes through that tile would be just: (1) the destination of that route; and (2) the direction to get to that destination. Thus, when on an intersection tile, a private car would iterate through all the routes stored on that tile (in a large map, perhaps up to 500 or so) until either the end of the list or until it found its destination. It would then turn to travel in the direction indicated in the dataset in question.

Iterating through a list of 500 or so items is not massively computationally expensive in itself, although perhaps it might be with a large number of cars doing this; is this the sort of searching that you had in mind, or were you thinking of private cars actually iterating through a list of co-ordinates comprising the town to town route, or something else?

I was unsure of what you intended. Thanks for clarification.

Since the search is only needed at crossings, the lookup would be not very frequent. However, finding the "right" target may be more challenging, or the citycar just need to select as destination at the beginning of its drive from the list of available desinations and self destruct when it arives at a crossing where this destination is no longer available. That lookup can be very peformant, one could even do a binary seach when ordering first by X and then Y.

However, very computationally expensive is updating all crossings whenever a new way is built (i.e. constantly in a realistic game). I imagine there are typically much more crossings than citycars. Multithreading is not really a solution, since if there a 10000 crossings alone; even only locking mutexes will take some quite some resources then. Hence the idea of a citycar just calculating the routing to the next town closer to destination until it is close enough (i.e. the industry belongs to the town reached or is within 150 tiles) and then do a full search and self destruct on failure. Such short route searches should be not very expensive if properly limited (i.e. twice the distance to the target); most expensive are fails, since all tiles are visited.

Multithreading in general is not a always solution it jsut shifts the limit a little further. If you have 12 threads, you may get a speedup by 10. But that means you can increase your problem just be a factor of 10 (and since we are talking of a 2D map, increase dimensions by 3). In praxis with locking, initialising  etc. it may be even less.

I see the advantage of using preset routes from one place to another and having private cars follow these routes to their destination. I also see the problem of storing and updating routes from every town to every other town at a large number of intersections.

But why not split the problem in two levels? Real road users (well, most of them; some people ask their navigation device to take the shortest route, leading them through residantial areas, much to the dissatisfaction of the people living there) don't use a complete search for the best route. Instead, they pick a fast connection to a main road (a motorway these days), then search for the shortest route not even considering the smaller roads until they reach a motorway junction close to their destination.

There would be a set of main roads, basically the standard countryside roads or roads with a high speed limit. This main road could also be a bundle of main roads, like a motorway. Lower speed roads only connecting to high speed roads (like the loops of a motorway junction) would also be main roads. It must be ensured that all main roads that are part of the same road network are connected to each other by main roads, so it may be necessary to pick some rather small roads and call them main roads anyway. These main roads connect to each other at junctions, which are clusters of intersections between main roads. Then there are access points, which are intersections (or clusters of intersections) where the main roads connect to smaller roads. Intersections could be co-located with junctions.

From the intersections one creates dendrites leading back into the network of smaller roads. They can branch at intersections and tend to avoid each other. Whenever the dendrites reach into a town (and wherever I write town, it could also be a rural industry or tourist attraction), the access point is associated with this town.

Then one creates reverse dendrites (I think we should call them axons) leading from the access points towards these towns. Mostly the same as the dendrites, but they may differ because of one-way streets and shouldn't lead into streets to nowhere. Where axons from the same access point reach multiple towns, multiple axons are put on top of each other, so that each only reaches a single destination. Whenever the axons reach into a town, the town is associated with the access point where the axon comes from and the access point gets associated with this town. Every main road that has access points associated with this town also gets associated with this town. A town may be associated with multiple access points and main roads, a main road or access point may be associated with multiple towns.

All junctions connecting the main roads associated with a particular town also get associated with this town, and the town with the junction.

Then prepare a table for routes from town A to town B. This will be the best route from any junction associated with town A to any junction associated with town B, stored as a list of junctions you have to follow. As an example from real life, the route from Bristol to Manchester in the UK will be stored as Almondsbury Interchange (associated with Bristol, Cardiff, Swindon, Exeter, Gloucester, ...) - Strensham Interchange (associated with Gloucester, Hereford, Worcester, ...) - Catshill Interchange - ... - Eccles Interchange (one of several junctions associated only with Manchester).

Every intersection at a junction where cars have a choice between different directions (i.e., the off-slips) has directions to all neighbouring junctions and all access points associated with towns also associated with this junction. Access points store directions to junctions associated with towns also associated with this access point and to access points associated with towns associated with those junctions.

Now a car that wants to travel from town A to town Z has to do a simple table look-up to find it has to travel via junctions J, K, ..., P. It also picks a random access point Y leading to Z. The car then drives randomly (without leaving town A) until it hits any dendrite. Then it follows the dendrite to the access point. If the access point is Y, the car will simply follow the axon to Z. If A and Z are neighbours (i.e., they share junctions), the car takes directions to Y directly. Else, it takes directions to junction J. After arriving at junction J it gets directions to junction K and from junction P it can follow directions to Y. Then the cars follow the axon to Z, choosing randomly when the axon branches, and does some more random driving until it disappears.

In this way the number of directions to store at any intersection is limited and only directions to nearby places are stored, making it easier to keep them up-to-date. At the same time, the car doesn't have any computations to do, it just follows the roadsigns.

BTW, when I was thinking about convoy recombination lately, I thought about convoys offering a ride to any convoy that wishes to join them. Think of locomotives picking up any wagons along their way, but also ro-ro ferries and shuttle trains carrying cars through tunnels. These might be able to carry private cars too, which would make those connections part of the main roads. But that's probably a project for the far future.

The route search through intersections is more or less what James suggested to do. And finding "main roads" is unfourtunately again read my mind comouting (or real AI).

And same as with James' approach, any building of a new crossing must trigger the full recalculation. Same for cutting a way.

Jamespetts, I am sorry for my misunderstanding of your case.

I am thinking of two separate factors: 1) Who wants to go where? and 2) Can vehicles go there (private cars)?

The complexity that Prissi points out that I had not considered is the need to store the routes centrally somewhere so that they can be deleted as appropriate: searching through all way tiles will not be workable. The only way that I can think of doing this is storing them in city objects. I have not calculated whether this memory usage is likely to be excessive at this stage, but I suspect not.

So far as I understand, Octavius's idea is similar to the route fragments idea that I had some years ago but discounted on grounds of complexity. In order for this to be done sometime during my lifetime (and I am only 39), unless somebody else codes this feature, in which case that person will have some discretion over implementation providing that it works and is not too computationally intensive, this will need to be a very simple implementation largely using existing code, such as the town to town way search code that already exists.

I just spent a few hours answering this one, when my post got lost just before submitting. I suggest equipping keyboards with a mechanical protection of the F5 key!
Luckily, I have found a backup somewhere in my mind, so I just restored it.

Quote from: jamespetts on January 13, 2020, 12:10:27 PMIf, instead of discarding the tiles constituting a route to any given destination as at present, the private car route finder were instead to store (1) the destination (a co-ordinate is probably better than a pointer here); and (2) a direction in the tiles of road constituting the route, then this would allow private cars to follow the route without doing their own routefinding.

I am not quite sure if I fully understand your approach, so here is how I understand this:
Currently, there is a route search for each city on the map to every single city, attraction and industry on the map calculated, which is used to guess the travel times.
You want to store a reference to that route at each road tile which is part of that calculated route. If a car detects a matching route at a road tile, it will remember and follow that route.

First, you don't need to store the whole route to every single road tile along that route (I am not quite sure if that was your intention). Instead, it should be sufficient to place some kind of virtual signpost at each affected intersection by storing a destination=>direction mapping to each intersection. If we were supposed to reverse at a non-intersection road, we would not have been guided here. In case an unlucky inhabitant lives immediately at one of those roads, he will get spawned on a road tile that is part of our route to the destination, without him knowing this, so he will in the worst case just drive the wrong way round to the next intersection which will tell him to reverse, so it's not an issue.

Also note that we will need to calculate and somehow store n*(n-1+m)=n²+n*m-n routes, where n is the number of towns and m is the number of attractions and industries.
This is quite fair for this kind of calculation.



Step-by-step description of what I have in mind based on James suggestion:
There are some words in the following text that have a special meaning in terms of the algorithm, so there is a short text-to-algorithm dictionary below:

Let's take a journey by our private car (well yours, I don't have one)
We start next to our origin in random mode, with a destination in mind, driving around until we reach an intersection that has a signpost with our destination.
Found one! We will switch to guided mode and follow the instructions on the signpost.

After driving around from signpost to signpost there suddenly is an intersection that does not have a signpost with our destination.
We will immediately call the Department for Transport. The operator will ask us for our location, the origin, the destination and the exact time when we read the last instruction from a signpost. We tell him these informations, so he promises he will check the issue but sadly can't tell us how we can get to our destination.
Same would apply if we suddenly ended up in a dead-end.

Not knowing where to drive, we continue in random mode


Meanwhile in the Department:
The operator will immediately compare the time we told him to the time of the latest change in the guided network.
If there was a change in the guided network after we had read that information, or there is already a reroute scheduled from our origin to the destination we told him, he will close this case.

Otherwise (we were instructed to move here by the currently valid guided network), he will immediately teleport himself to the location we told him to, to observe this on location.
If it is a dead-end, he will walk to the next intersection. There, he will locate from which direction cars to our destination are coming (there could be multiple) and update the signpost to any direction that is not a dead-end nor a direction where cars towards our destination come from (which would effectively also be a dead-end for cars with that destination)
If there are none, he won't change anything for now.

In case the location he just teleported to is an intersection, he will also check from which direction cars to our destination come from and if there is any intersection with a signpost around that does not point towards him.
In this case he will update his current signpost.
Otherwise, again he won't change anything for now.

Finally, he's teleporting back to his office, where he will check if scheduling a reroute is required.
His work-instructions clearly states, that a recalculations is always required, except if that location was a crossing, he had fixed signposts directioins and and any unaffected roads at that intersection were dead-ends.
In our case, there was no dead-end roads around, so he schedules a recalculation for our route.


Back to our journey:
We just saw that crazy operator in the driving mirror, so we were randomly driving on, but luckily we quickly found a signpost with our destination, so we already switched to guided mode again.
Suddenly, there again is an intersection without our destination.
Again, we call the Department for Transport. Same dialogue again, he won't tell us an alternative route but he promises us to check the issue.
This time, we don't see any teleporting operator in the driving mirror.
It takes a while until we again find a route to our destination, but once we were back in guided mode, we quickly came closer to our destination. On the way, we see our neighbour, who refuses to use the new routing, being stuck in a oneway trap, and a short time after that we just arrive in our destination city.

Here, we switch to random mode again and slowly move around the city towards our destination building. We just came to a town exit sign, so we turn back.
A short while later, we can already see our destination, when suddenly there is a huge beam of light above. The Department for Transport just despawned us for being too slow.


A few hours ago in the Department:
A rerouting operator had just started to recalculate the route from our origin to our target.
At first, he calculated the route.
Then he moved to every single intersection in that route and set the direction to the destination on the signpost appropriately, increasing the counter of this instruction.
He knows doing this will also affect any other line to the destination that used the old intersection before and this could leave signposts that no other signpost is pointing to. (just as at the first intersection after the origin)
However, his work instructions clearly state "It is better to leave these, as they will still lead to the corect destination and it is not worth figuring out whichever route used these will already use the new way."
So he does not try to locate any other route belonging to that old instruction.
Now he reduces the newly calculated route by removing and non-intersection tiles
Finally, he will walk to each signpost of the route, decrease the counter for our destination and in case it is 0 now, he will entirely remove the instruction for our destination from it..
He is instructed not to teleport to the signposts of the old route, as they may have been removed or even replaced by something else, thus teleporting would be danger to life.



That was quite an informative story of travelling in the simutrans universe. I hope it well describes the algorithm, if not, please let me know what is unclear.


Dictionary:
car: The actual car object in simutrans.
  It knows its movement mode, location, origin, destination, and the time/ticks it passed the last intersection (at least when in guided mode)
random mode: current citycar movement method
guided mode: the newly discussed and in the text described method to move cars along predefined routes.
The Department for Transport: an instance of the class handling vehicle movement and routing.
  Additionally to current functions, it can handle invalid signpost complaints, schedule reroutes, perform route recalculation and appropriately update the signposts
  And will additionally remember all of these routes
guided network: The network, which vehicles in guided mode will use consisting of the signposts, which are our routers and the roads used in between them.
signpost: a destination=>[direction, counter] map, which is an attribute of a road.
promise to work on: Something that can potentially run in another thread as we don't care about the result.
schedules: Just as the normal meaning of this word. Do this after a given time.
check the issue: handle an invalid signpost report



I still have some points that need careful considerations or at least empirical observation once it is implemented. I will point these out in non-story-mode here.

• 
  We won't be able to automatically detect better routes, once they are constructed. Detecting these relyably and deciding which routes could profit from the new road will be quite difficult.
  The easyest would be to recalculate all lines from time-to-time but this won't allow for just-in-time updates and will quite often recalculate without any changes.
  If these calculations are done frequently anyway, it should not be off a problem to compare the old route to the new one and accordingly update the signposts with the new route in case of any changes.
  


• 
  Effectively concave cities, e.g. ones that grew around a lake, whilst city borders don't completely enclose the lake (but there may be a road around), or even worse, cities that jumped across the ocean will be an issue.
  In both cases the inner-city route will be quite bad potentially stucking many citycars around the coast.
  A solution could be internally using clusters instead of cities as origins/destinations, to split up concave cities, while joining non-concave adjacent cities into the same cluster.
  An extremely fast and simple clustering algorithm would simply pick a few points at city borders and iterate towards another city border of the same city. If there are many non city-like tiles (e.g. unused land or water) within city borders, we will have to split.
  If there are adjacent clusters, we can assume them connected and do the same cluster burder check as above. If it does not report many non-city-like areas, we will merge.
  
  A slightly slower, but I guess much better approach would be detecting city buildings near cluster borders and starting waysearches in between these.
  We are now interested in the length of these lines. If these are much longer than the bee distance from start to origin, the cluster is likely bad connected and we need to split.
  If they are fine, the cluster is internally well connected and we will update the cluster to the bounding box of the calculated routes, as it posible that a few routes went out of city borders.
  Same can be applied to nearby clusters. Assume them merged and calculate the above for the merges cluster. If connections are considerably good, merge them, if not, leave them seperated.
  


• 
  There won't be any load-balancing in the guided network.
  While the guided network will be quite powerful in moving vehicles along inter-city roads, it will likely suffer congestion within cities even more than the current solution. Because it does only make use of very few roads.
  Fighting the congestion by forcibly removing as many connections to the guided network as possible withing cities and replacing these with bridges above that road will work quite well but the city will often simply not allow that.
  In some other cases building a city-bypass road may also help but it is also not always posible to build such e.g. for cities along a curved coast.
  A programmatical approach to solve this is by introducing alternative routes for congested roads.
  This would require a congestion penalty for congested road tiles in the route search and a special alternative route signpost.
  In difference to a normal signpost, an alternative route signpost maintains a list of [direction, counter] pairs for each destination. A vehicle approaching such an intersection will choose the free direction with the highest counter, as a higher counter means more lines still consider it to be the best route, although there may be little congestion.
  Signposts will be changed to alternative route signposts by the reroute_and_update_signposts method in the add step, when it detects a signpost to have a different direction for the same destination and will downgrade in the remove step when after removing the own direction from the list there is only one entry element left in the list.
  This would also fix the quite useful effect that updating a single route will fix any other route sharing the same destination and signpost, but I don't think this is a huge issue, the other lines will fix their routes as soon as anyone using that line reports the invalid signpost.
  

Quote from: prissi on January 13, 2020, 02:43:45 PMMultithreading in general is not a always solution it jsut shifts the limit a little further.

It is, we neeed mooooooooooooore cores, next step: implement waysearches on the GPU using openCL or CUDA xD (this was actually not serious)

Thank you for this long and thoughtful post. I do not have time to analyse it fully this evening, but a brief initial clarification question, if I may: by "destination" here, do you mean the actual individual building, or do you mean just the town itself, the car reverting to random mode on entering the town and disappearing either when its timeout expires or when it gets near its destination building, whichever is sooner?

For guided mode, for sure our destination is just the destination town, where it will finally switch to random mode until it gets despawned near the actual destination building.

I can't comment on the algorithm, but I like your comic story, Freahk!  ;D

Thanks Matthew, I guess it's the most informative comic I have ever written xD

Another rather simple point about car movement that just came in mind is about the random mode.
I really don't understand cars heuristics in choosing a direction, but in any case I can often observe cars moving from one dead-end to another within cities.
Cities tend to quite often build dead ends, especially around city borders and private cars tend to quite often enter these.
There are two types of relatively common dead-end roads in cities: immediate dead-ends of most often 1-3 tiles and diverging dead-ends (see the image) of most often 3-8 tiles distance to the only exit.

We should maybe store another ribi to intersections that only points to directions that are not dead-ends within a small number of hops, maybe 5-10

Updating these whenever the masked ribi of a road changes should be quite inexpensive.
Private cars should use the new ribi to decide where to go, except if they are close to their destination.

I have now had time to look over this: thank you for your most detailed suggestion and rather amusing way of describing it: the style of narration reminded me of a (rather whimsical pastiche of) the British Transport Films of the 1950s.

First of all, I think that there has been something of a misunderstanding of what I had originally proposed, as my original proposal is closer to your proposal than you thought. The idea was not to store a reference to the whole route in each tile of the route, but rather store simply the destination and direction, much as you propose. The difference is that my system would store these on every tile of the route, not just at intersections so that, if any tile of the route subsequently became an intersection, this would not affect routing.

Secondly, what you suggest I think is a form of lazy initialisation of the routes (i.e., attempting to check the routes as and when private cars attempt to use them). However, this will not fit in easily with the system as it now stands. The current system will not even attempt to initiate a private car journey to a given destination outside the current town unless it has already been validated as a reachable destination. Thus, it is necessary to have a route search to every possible destination done separately from any actual instigation of private car journeys. It is also necessary to limit the amount of CPU time spent doing this: a lazy initialisation would mean that, starting a large map in the modern era, hundreds upon hundreds of private car journeys would attempt to be made to all sorts of towns all across the map at the same time, overwhelming the computer. It is also not clear what the advantages are of this system over the current scheduled system, where the routes from a batch of towns are checked periodically in a series of threads running in the background.

The consequence of all this is that I think that it would be better to retain the current basic scheduling model of private car route searches. This has the (enormous) advantage of not having to rewrite a very large amount of code, and that is another strong reason in favour of retaining this.

The current private car route searching algorithm is a slightly modified Dijkstra's algorithm, modified to remove the "relaxing" part at the end that actually assembles the finished route, as this is not necessary for the current system, since all that we need is the cost of the fastest route, not the route itself. For this system to work, the full algorithm would have to be implemented, adding the "relaxing" part at the end that constructs the route. This route would then have to be copied to towns to keep as references for deletion/refreshing and the direction and destination would have to be embedded in every tile of the route. The latter two functions would have to be single-threaded so as to prevent indeterminism and possible race conditions, so there would have to be a temporary heap storage of the completed routes from the multi-threaded part of the algorithm awaiting deployment to the memory locations where they will affect the simulation in a subsequent single threaded copying algorithm. (Conceivably, this algorithm could be multi-threaded to run in parallel, but not concurrently with anything else, but it is not clear whether this would be sufficiently computationally intensive to warrant that; I suspect not).

The behaviour of the cars themselves would be much as you envisaged, save that there would be no communication from the cars back to the path finding algorithm ("Department for Transport" in your story).

The most difficult question is that of refreshing the routes. The addition of new intersections to existing tiles on the route should leave the route unaffected in my system, as the route is stored on all tiles, albeit the cars would only actually check it at intersections. However, it would be useful to display these routes to the player in the dialogue for the road tile, and even possibly use them in station and stop names (e.g., "Draxby Underford Road Stop" being a 'bus stop on a road in Draxby that is part of the route to Underford).

The only sensible way of dealing with this is a periodic refresh: once the algorithm has finished going through the list of towns and recalculating routes for them a few at a time in each step, it just goes back to the beginning of the list and starts again. I have contemplated various heuristics to check whether any recalculation is needed, but ultimately I could not work out anything that was not either more or less useless or too computationally intensive to be a useful heuristic. The current system has an extremely simple system, in which it will not re-check the towns if no road tile has been built or deleted since the last check. In practical terms, this more or less amounts to continual re-checking in any event in all but the smallest games, so this system might as well be retained.

Once a refresh has been completed, the single threaded copying algorithm would simply remove the references to the route on all the current route tiles and add the new references, as well as updating the route stored in the city. One concern that I have about this is the computational intensity of checking for a matching koord in a long vector on a very large number of road tiles. I wonder whether a hashtable would be faster, with the destination co-ordinate as the key and the direction the value?

Load balancing and dead end detection are much more sophisticated topics, and beyond the scope of this specific project, as well as being somewhat lower priorities. However, I am concerned that these (especially load balancing) would seriously increase the computational intensity of this algorithm. The private car route searching algorithm is one of only five aspects of the simulation that I spent a large amount of effort multi-threading in November 2016 for a reason. Thus, it is important to limit the computational load of this as much as possible, and also to spread it evenly.

Bear in mind also the amount of memory that this will consume. Every way tile will have to have a memory location set aside for all of these data. This will probably have to be a vector of structs, each struct containing a ribi (direction) and a koord (co-ordinate) pair for each given destination for which that road is a route. Each road tile with no routes would already contain the memory overhead of an empty vector in addition to what it already stores; those with active routes would also contain a whole series of co-ordinates. We can probably get away with 2d co-ordinates, since all that we will get out of them is the town, industry or attraction that they are in, but that will still be a significant amount of memory. Think of how many road tiles that there are in a large game and multiply that by the number of bytes in the memory structures that need to be created for the feature in question.

Likewise, CPU intensity and memory bandwidth should be considered: if at every intersection every car checks whether it is "close to" its destination, this would involve a call to the "shortest_distance" algorithm (which is fairly expensive) for hundreds of cars every step; private cars checking their next hop is already a fairly significant part of the time spent in the Bridgewater-Brunel (2004) game for single-threaded algorithms, so this is potentially a performance issue.

I remember that there are some intersection detection systems for railway or road in signalling code. (signal GUI window shows the next intersection, and oneway sign is used for fixing the lanes in OTRP)
When a citycar at random mode faces the intersection which has no "navigation sign" by Department for Transport, the citycar try to find next intersection. If they find some ways that the citycar can reach next intersection, they will proceed to a direction randomly.

Maybe then the driver call to Department for Transport, which directions are available at the intersection, and the Department for Transport will register it and place "navigation signs". This process occur s only when the citycar faces to the intersection, so it is decentralized system.

Note that the "navigation signs" are not actual object, but special ribi.

Phystam - thank you for the suggestion. However, I am concerned that any route search system called for by the actual car objects rather than scheduled at regular intervals and multi-threaded would be too computationally expensive in larger games.

Attention, yet another wall of text incoming...

Quote from: jamespetts on January 16, 2020, 01:07:13 AMI have now had time to look over this: thank you for your most detailed suggestion and rather amusing way of describing it: the style of narration reminded me of a (rather whimsical pastiche of) the British Transport Films of the 1950s.

I have never seen such, so maybe I should use my time machine to travel to the 1940s in Britain and make an application at a British film company.


Let's get to the algorithm: I guess there also has been some missanderstanding, of what I have posted, so let me clarify:

Quote from: jamespetts on January 16, 2020, 01:07:13 AMSecondly, what you suggest I think is a form of lazy initialisation of the routes (i.e., attempting to check the routes as and when private cars attempt to use them).

I don't intend lazy initialization nor calls from cars to the actual pathfinding algorithm.

So let's start with what you called lazy initialization.
I expect all routes to already be calculated i.e. at map creation time for the first time.
If they were not, cars could never find a signpost to switch to guided mode, as there are none, thus there would never be a guided network at all.

The lazy part is not about initialising the network but about updating it quickly, but not immediately, when a route is known to be broken to prevent cities from quickly piling up with cars due to a broken route.

A car will detect and report a broken route, whenever it is in guided mode and reaches a dead-end  or an intersection without instructions for this car. There won't be any route searching at this time. The "Department for Transport" from the story, which is not the path finding algorithm, but an instance of the class handling private car movements, will only check if there is a quite simple fix for this issue. If the issue was fixed, no further action is done, otherwise a recalculation of the route is scheduled for the next recalculation period.

A quite simple fix for broken routes would be looking for neighboring intersections with an instruction to the destination. In case one is detected, we will add that routing information to the signpost (or add a new one if none was existent) and store it along with the route e.g. at the end of the list.
We could do this recursively with a small max recursion depth, e.g. 3, to allow for a bypass when the road in between two intersection was just disconnected, which is a quite common case.
In that case your solution would simply stuck cars towards the dead-end and won't let them out before the route was recalculated, while mine could fix the route at a quite low cost in some quite common cases and when it can't at least sets cars to random mode so tey don't get stuck there.
Your advantage of being able to handle newly connected roads will be fixed quite inexpensively.
Looking up the stored routes for a single road tile can also be calculated quite inexpensively by looking out for any neighboring intersections whose signposts point towards us. Players won't spam thousands of such calls in a second, same applies to stop names.
So I really expect this to have a rather small impact on computation as that kind of information is not rquired often for non-intersections and can be calculated quite inexpensively while I expect it to reduce the number of stored koords by a factor of at least 3. Along a route, roughly every 3rd tile will be an intersection within cities, where out of cities that factor will be by far larger.

QuoteThe only sensible way of dealing with this is a periodic refresh

I absolutely agree with it, as long as "this" means detecting better routes and handling changes in the network that will have a huge impact to the route, e.g. a private intercity connection was removed or just denied access to the public.
In cities this will usually not happen due to the (quite annoying) "provide an adequate alternative route" message, so it should really be worth trying to locally fix a route instead of always scheduling a full reroute.

Also, I am not quite sure if the signpost update really can't run concurrently to anything else in the game. Is there anything else in the game that will read and write the signposts?
It is extremely unlikely for a car to read information from the new route from one signpost, continuing to the next one and reading outdated or no information there because it reached that intersection before the signpost updater. Even if this happened, it would not be off a problem, as the car will simply switch to random mode, either because there was no information or because a new information leaded the car to a not-yet signposted intersection. A situation that will quite often appear when a route has changed anyway.
Running the updater concurrently to itself updating multiple routes simultaneaoulsly, however will be an issue as there are shared signposts and if one thread reads it just before another one updated it, there will be a wrong counter.

I don't know how roads are stored currently, so I can't help with the koord => road lookup. If it's an unordeered list, however, this is most likely to be performance critical.
I had expected ways to be sticked to tiles, which I would expect to be maintained in a 2 dimensional array, so we could immediately acces it like world_tiles[ x ][ y ] or a 1 dimensional array, which we would access like world_tiles[x*y+x], in which case road lookup would be fairly fast.


Load balancing, as any of the other further notes, is something we should not consider before observing ingame that not having it it an issue.
However, I would not expect it to change a lot in terms of performance if properly implemented.
The signpost must only in addition to the destination=>[direction,count] map store a pointer to a destination=>list of [direction,count], which should not have a huge impact on memory nor computational load.

However, as mentioned, the details of these should not really be of interest yet.
If we observe guided roads within cities to suffer from too high loads ingame, we can still continue special considerations here.


Dead-end detection, however, is something quite inexpensive if implemented in a pretty basic way, which will quite often be sufficient due to how simucities are constructed. "Dead-endness" of a road will only be calculated at road construction and destruction time within a given maximum distance (in manhattan distance) and a maximum recursion depth. If all ends report a dead-end, we know for sure there is a dead-end in that direction. If any of the ends exceeded either recursion depth or distance limit, we don't know if it is a dead-end so we don't close that direction.
It seems you misunderstood what I called the distance to to destination as you were talking about shortest_distance algorithm at that point. The shortest distance simply is the manhattan distance, which means |pos.x-dest.x|+|pos.y-dest.y| which is extremely inexpensive to calculate and in any way will only be calculated in random mode.

It seems there currently is some kind of iterating around roads on road destruction anyway to pop up the (still annoying)  "provide an adequate alternative route" message, so calculating a roads that are definitely one-way roads within a small area really should not be compute-intense.

Storing an additional ribi to a road tile also should not greatly increase memory.
You had mentioned that there is some kind of heuristics involved in moving private cars towards there destination, so we already calculate the distance to the destination. The only thing we had to do in addition is checking if that already calculated distance is smaller than our maximum dead-end detection distance. If it is, the car may enter the road, otherwise we can say for sure that it won't reach its destination by entering that road.


I did bear in mind the amount of memory, that's why I only want to store signposts where they are needed. Any other road, for sure, will also have the signpost attribute but it will point to null, so the only cost in memory here is the pointer.
As we are in C++ and they don't like pointers, we could alternatively store a reference to a special dummy signpost, which will always reply "I don't have a route" and will fail when trying to add one. Thus reading directions from any intersection will always be fine (which will happen most often) while setting or removing routes (which will only happen when recalculating a route) will require to check if we got the dummy signpost or a real one.
Maintaining another ribi for the simple dead-end logic, will be a rather small amount of memory and will also slightly speed up path finding.

The very simple dead-end calculation could even reduce overall computational load as it will help cars finding a guided road more quickly. Once in guided mode they will most likely be les compute intense than in random mode as they will simply follow routing instructions on the signposts instead of calculating their next hop by some kind of heuristics.

As always, it's a tradeoff and one had to observe it ingame but I think we really should give the quite simple dead-end detection a try as these simple dead-end appear quite often in simutrans whilst more complicated ones are quite rare within city borders. Outside of city borders cars will move in guided mode anyways because we won't allow them to leave towns in random mode.

Thank you for all of your detailed thoughts on this: it is most helpful. First of all, as to the British Transport Films, your delightful description reminded me a little of this film, which is also slightly relevant to the topic of private car transport and its interaction with 'buses:

---

I think that both of our proposed systems are a lot closer to each other than I hat first imagined. If we are initialising the routes with the existing refresh cycle of private car routing, then that removes the possible performance issues.

As to updating the routes, this needs some consideration. The private car routing algorithm runs in the background in its own thread in between steps. It goes through the cities marked to have their private car routes updated one by one and finds all connexions from towns to other towns, to country industries and to country attractions.

Currently, building a new road or deleting a road anywhere will mark all towns to recheck their road connexions at the next refresh, which is scheduled for the beginning of each month. The idea of this is to prevent unnecessary checks being run, but in reality it is likely to be rare for no roads to be built or deleted anywhere in a month on a larger game (and it does not matter so much in a smaller game). Note that I cannot remember now whether this is true only of player built roads or whether it also applies to roads built during town growth.

I have just been checking the performance of this with a saved game from the Bridgewater-Brunel server from December 2019. With an optimised debug build (i.e., one with both optimisations and debugging symbols enabled), a single city's run of this algorithm took between 162ms and about 12ms, averaging at around 32-64ms. There are 768 towns in this server, so one might infer that a complete run of the current routing algorithm would take circa 24,576 - 49,152ms, or circa 24-49 seconds. With a game of 400 towns (as has been estimated to be what servers might be able to manage more easily, although this is uncertain), this would take perhaps 12,800 - 25,600ms (that is, 12-25 seconds) to process all towns. This is all with the current very light algorithm that does not "relax" the route (i.e., assemble the actual route tiles and then save them to memory, rather than just obtaining the timing data). With "relaxing" the route, this may take longer (perhaps at the upper end of the current range or more). We might estimate therefore that a total town refresh might take 60 seconds of CPU time on a fast computer. Bear in mind, however, that this is multi-threaded, so this may be closer to 10-20 seconds of real time. Aside from being multi-threaded, this workload is also spread temporally, as only a few cities are refreshed each step to allow the game to remain responsive whilst this task is running.

What one might do, therefore, is retain the existing scheduling system for regular refreshes (making sure to ignore city built roads if this is not already the case), but then immediately set all cities with routes to them marked on a tile of road being deleted or degraded so as to become impassible to refresh forthwith. This will not then immediately hang the game for a minute, as they would still simply be set to refresh a few at a time using the multi-threaded mechanism to process them in the background. Thus, broken routes would be refreshed immediately, whereas routes that remained in good order would be refreshed periodically in case a better route in the meantime had been built.

In relation to concurrency, the routing update cannot run concurrently with sync_step(), as this calls all the moment to moment movement and interaction code, including private car movements. If we were to make the part of the routing that actually stores the data run concurrently with sync_step(), what would happen is that, in an online game, on the server, one particular private car  would check what route to take at an intersection before the data had been written by that thread to the intersection updating the direction to the destination, and, on one client, the car would check what route to take at an intersection after this datum had been written; the private car would thus go in a different direction on the client and the server, and a loss of synchronisation would inevitably occur. Any possibility of this non-determinacy must be eliminated for servers and clients to be able to stay in sync with one another for any worthwhile period of time: even if this is unlikely to happen in any given moment, any possibility of it happening will eventually come to pass, and the chance of it doing so in a large game is so great that players might be disconnected every few minutes when a route refresh is running. All possibilities of losing synchronisation in this way must be eliminated for the game to be playable.

However, this is something of a problem for performance, as running the route-finding algorithm concurrently with sync_step() is what most minimises the performance impact of the private car routing algorithm. Thus, the only way of handling this that I can see is for the multi-threaded route finding algorithm to store the route data in a temporary location that does not affect vehicle movement, and then in a single-threaded part of the code, apply those route data to the individual road tiles.

---

As to the actual vehicle behaviour algorithms suggested, I am concerned about the potential performance impact of every car checking a set of neighbouring intersections for routes to the destination. Imagine, in a busy game, a several players bulldozing busy roads all at the same time, and scores of cars invoking this local pathfinding algorithm all at once. The real problem, I think, is that the private cars' movement behaviour is run in sync_step(), not step(): private_car_t::hop_check() is called from sync_step. sync_step() is intended to deal with very lightweight mechanisms that are run very frequently; step() is intended to deal with things that take more computational power. Thus, the performance impact of adding anything to sync_step() is many times the performance impact of adding the equivalent code to step().

It would of course in theory be possible to refactor the code entirely and move private cars' local temporary routefinding to step() through an entirely new mechanism for stepping private cars, but this would be a very large amount of work. If you or someone else would like to do this, that would be splendid, but if I am going to implement this, this is not likely to be a high enough priority item that the gain from implementing this extra feature will outweigh the time cost of doing so, which of course is opportunity cost in terms of implementing other features and fixing bugs.

In any event, the more sophisticated broken route handling for cars can be implemented separately from and later than the basic private car route finding mechanism proposed here.

I suspect that the same will also apply equally to dead-end detection. In relation to computational intensity, there is a big difference in performance impact between pathfinding done whenever a player tries to delete a road, and pathfinding done constantly by many hundreds of private cars all over the game. I should note that the current heuristic for private cars finding their destination does not attempt to calculate the distance to the destination: it is a very basic heuristic and it does not appear to work very effectively. I have never attempted to look into this code in any detail, however, and thus do not know how exactly it works; but there are no calls to koord_distance() or shortest_distance() if I recall correctly.

However, of course, if you were minded to implement dead-end detection, you could always test computational intensity by profiling with the current Bridgewater-Brunel saved game.

---

The potential problem with looking up stored routes on a single tile, I am not sure that I understand what you mean when you refer to this being able to be calculated inexpensively by looking out for neighbouring intersections whose signposts point towards us. I am afraid that I do not really understand what algorithm that you propose here. Can you elaborate?

All that I imagine is that, every time that a private car outside a town has as its next tile an intersection, it will search the hashtable stored on that tile of road for its destination, being the hashtable's key. The hashtable's value would be the direction, so it would return the direction if the route were stored. My concern is that, if the hashtables get very big, this looking up operation may take a long time (the single most computationally intensive process on the current Bridgewater-Brunel saved game is looking up routes in the hashtable of passenger/goods/mail routing), but I do not know whether the hashtables that we envisage here will get large enough to have a significant performance impact; but bear in mind that the significant performance impact threshold is much lower for anything run from sync_step().

As to the current storage of road tiles, I am not sure of the basic data structure, which remains unchanged from Standard, but they are generally accessed by looking up a koord or grund_t object to discover whether a way is on that tile. However, the issue is not so much finding what road is on a tile, but rather finding the destination: we already look up the road in every sync step of a private car: see line 964 of simroadtraffic.cc.

Quote from: jamespetts on January 26, 2020, 02:07:55 PMCurrently, building a new road or deleting a road anywhere will mark all towns to recheck their road connexions at the next refresh ... Note that I cannot remember now whether this is true only of player built roads or whether it also applies to roads built during town growth.

It is very unlikely that none of the cities build a new road within a whole month, nor it is ensured that city growth won't create a better connection. or even make the current one worse due to takeover of fast roads.

Quote from: jamespetts on January 26, 2020, 02:07:55 PMWhat one might do, therefore, is retain the existing scheduling system for regular refreshes (making sure to ignore city built roads if this is not already the case), but then immediately set all cities with routes to them marked on a tile of road being deleted or degraded so as to become impassible to refresh forthwith. This will not then immediately hang the game for a minute, as they would still simply be set to refresh a few at a time using the multi-threaded mechanism to process them in the background. Thus, broken routes would be refreshed immediately, whereas routes that remained in good order would be refreshed periodically in case a better route in the meantime had been built.

I guess about the broken routes, this is nearly what I had described, apart that in my suggestion signposts won't know their actual related routes, instead only maintaining a counter, so we can't easily detect and "mark invalid" affected routes without the help of our private cars, that will have to read the signpost anyway.
The "ignore city growth roads" point is not a good idea imho. New city roads can quite often lead to better or even worse routes. E.g. imagine a city connected from southeast to city B and southwest to city C. Any city growth to the south might shorten the path B to C.
Another example were cities growing towards a city bypass. It might be better not to use that bypass anymore once the city had restricted the maximum speed of it.
If we really want to prefer recalculating routes that are likely to have changed, we will need a propability/priority based recalculation queue rather than a binary "update this, don't update that" approach. However, I guess for now simply calculating a few routes, prioritising lines that we know to have changed and any other lines in a fixed order, each time we schedule the racalculation thread is fine.

Ah sure, I see the concurrent running issue with sync_step in multiplayer games.

Quote from: jamespetts on January 26, 2020, 02:07:55 PMI am concerned about the potential performance impact of every car checking a set of neighbouring intersections for routes to the destination.

This will only happen if the route is detected broken, that means a car entered a tile which does not have a signpost.
In that case, a very simple and fast fixing algorithm will run in sync_step. If we can fix it locally, that intersection won't be broken for any further car to the same destination arriving there, otherwise there will already be a recalculation for that route scheduled, thus the local fixing algorithm won't be called another time.
Thus, the performance impact should be minimal and could even impact the performance less than a huge bunch of cars leaving guided mode, thus getting spread all around the city.
If that's still too much for the sync_step, we could let that car switch to random mode immediately and simply mark the intersection to fix the route locally in the next step.

Quote from: jamespetts on January 26, 2020, 02:07:55 PMThe potential problem with looking up stored routes on a single tile, I am not sure that I understand what you mean when you refer to this being able to be calculated inexpensively by looking out for neighbouring intersections whose signposts point towards us. I am afraid that I do not really understand what algorithm that you propose here. Can you elaborate?

Not quite sure if you mean lookup at intersections with a signpost or lookup at roads in between intersctions along the route.
For road tiles in between, there won't be any lookup. A car has a direction and will simply follow the road until it reaches an intersection.
The signpost of that intersection is a map direction=>{direction,count}, so we can read the new direction immediately from the signpost.

Looking out for neighboring intersections is only required at roads in between intersections, if either a car spawns on that road, the player opens roads information window (including a list of guided routes using that road) or a new stop is placed and wants to use the guided route information for the stops name. Also, the local fixup algorithm would look out for neighbors.
Looking out for neighbors effectively means iterating along the road in all directions until we hit the next intersection, so I would call this quite inexpensive in relation to the amount of such calls.
If this is too expensive for car spawning, we can still spawn the car in random mode.

I have now implemented this on the private-car-routing-lightweight branch on Github. I will not merge this into the master branch just yet to give the intrepid self-compilers a chance to test this in case there are any serious problems that I have not yet spotted. I have, however, spent many hours testing and adjusting this to-day, and it is confirmed working in network mode without loss of synchronisation.

Technical discussion

Performance testing has yielded some surprising results. The performance impact of adding private car routing is very low - 2.12% for route-finding on the Bridgewater-Brunel game from December 2019 (game year 2004). Note that this is the total CPU time for private car routing, which includes the more limited routing already done. Note also that this 2.12% CPU time is multi-threaded CPU time. Moreover, as explained below, this is not just for routes from cities to other cities or attractions and industries outside cities: it includes routes from all cities to industries and attractions inside cities, too.

What is more interesting is that this feature actually improves performance, at least so far as my profiler tells me. This is because following a route is much less processor intensive than using the heuristic algorithm. It is not so much the heuristic itself that was CPU intensive, but the process of getting one tile from a direction plus another tile (the gr->get_neighbour() method in private_car_t::hop_check()). The looking up of private car route hashtables in the roads is trivial from a performance perspective.

What I have done with the routes is simply store hashtables with the destination co-ordinate ("koord") as a key and the next tile (a koord3d object) as the value. This is better than using the direction, because there is then no need to perform the get_neighbour() lookups in hop_check(). Moreover, the cars do not only check the route at junctions: they check the route at every tile because this is faster than the previous system, which, even on straight road, needed at least one call to get_neighbour().

Testing has also showed that a far more frequent recalculation of private car routes is viable than previously anticipated. In the current master branch, there is a long-standing bug which testing on this discovered in which the private car routes were only set to be recalculated on a load/save cycle. They are now recalculated much more rapidly, and without deleterious effect on performance even in the Bridgewater-Brunel saved game.

The effect of the algorithm is most pleasing: one can build a map with two towns connected to each other by road in the modern age and watch streams of cars go between one town and another. If one deletes a tile and breaks the route, the cars will stop coming after a short time. If one then puts in a meandering diversionary route, the cars will come back, using the meandering diversionary route. Restoring the original shorter route will cause the cars, in a few seconds, to abandon the diversionary route entirely and return to the original route again.

I have tried this with a saved game (from the game year 1987) from the Stevenson-Seimens server; the car traps ceased working entirely after a minute or so. Existing cars remained trapped (it is not quite clear to me why at this stage: I have not investigated this), but new cars generated will take the straight road and avoid the traps entirely. I have also fixed a bug which allowed cars in heuristic mode to turn onto mothballed roads and then be destroyed (the "Bermuda Triangle" traps as named on the Stevenson-Seimens server). Now, the cars regard such roads as impassible and do not attempt to use them.

After some testing, I found Freahk's method for deletion detection preferable: whenever a private car finds that its next route tile has been deleted, it will immediately delete the whole route, and return to heuristic mode. This enables cars to deal with short diversions more or less immediately, but a proper route refresh does not take long in any event. (This might take longer on a large game, as the number of cities whose routes are processed in any given time are rationed).

Load balancing is an interesting issue. I did notice that, in modern times, roads between towns would quickly become quite crowded. A high proportion of traffic seemed to be heading to city attractions (Simutransians are very fond of sport, it seems), so there are now individual routes to the individual attractions and industries. City buildings other than attractions and industries are dealt with as described above: the cars will revert to heuristic mode on entering the city. This means that multiple routes between cities will be workable, as cars heading to individual attractions might find different routes to cars heading to other attractions or city buildings.

Incidentally, the original heuristic I think had been coded backwards: the distance (squared) was used as the weight in a weighted vector, and then the pick_any_weighted method used to choose the next tile - but the weighted vector is more likely to select elements with a higher weight than a lower weight, so this would lead to cars preferring roads leading them away from their destination in heuristic mode. I modified this by using 8192 / the distance as the heuristic. This might explain why Freahk had noticed that nearly every car turned exactly the wrong way at one point on the Stevenson-Siemens server and posted a sign board about it near the spot.

General discussion

In summary, for those not technically minded:

(1) private cars will follow calculated routes to cities, industries and attractions;
(2) the routes will be renewed frequently and immediately deleted whenever they are found to be broken; and
(3) this has been found to have no adverse effect on performance, and may well actually improve performance.

This feature is important for balance. Currently, in the modern era, players have no incentive to link towns with roads except if they want to use lorries or 'buses. Indeed, players have an incentive to keep towns from being linked with roads, as this means that less traffic will be generated in the towns, reducing congestion and competition for players' own services (e.g. railway services). I had recently increased the toll payable to players where private cars used their roads to a more realistic level from its previous minimum level, but this was very easily exploitable: players could build roads to nowhere or "car traps" to absorb cars and earn profit without taking the cars anywhere useful and without generating realistic congestion in cities by linking them and allowing more private car journeys to be generated.

Now, players will have an incentive to build roads that actually go somewhere useful, but cannot build working car traps. Indeed, it would even be possible for a player in the modern era to play as just a road builder and profit from private car tolls (as well as tolls of player 'buses and lorries). This will provide interesting competition and a challenge to players who have established rail networks, just as in reality.

I suspect that players will soon be building bypasses and dual carriageways between larger towns to deal with the volume of traffic; we might even see a motorway network in a more advanced game. Certainly, my limited testing has shown that passing through a town significantly affects traffic flow, so bypasses are likely to be a good strategy in the second half of the 20th century onwards.

Once people have had a chance to test this, I will merge this into the master branch. It will be interesting to see how players adapt their strategies in light of this.

Grateful for Jamespetts's patch.
In case you disputing the 'follow the original route': when shorter distance than original route, go to shorter distance route

I tested this fantastic patch --- Generally very good, but there are 2 problems.
1. frame skip
Although the CPU usage is quite low, for some reason, the frame skips occur very frequently.

2. Possible memory leak
While watching the memory usage of simutrans-extended, the value is getting higher gradually. I don't know where it comes from (I believe that it is from very large hash tables creation).

Using the stephenson-siemens game, the program freezes permanently (without crashing) about 38 game-minutes into the new month. Backtrace from gdb:

#0  futex_wait (private=0, expected=11910, futex_word=0x555555bcc7c4 <private_car_barrier+4>) at ../sysdeps/unix/sysv/linux/futex-internal.h:53
#1  futex_wait_simple (private=0, expected=11910, futex_word=0x555555bcc7c4 <private_car_barrier+4>) at ../sysdeps/nptl/futex-internal.h:128
#2  __pthread_barrier_wait (barrier=0x555555bcc7c0 <private_car_barrier>) at pthread_barrier_wait.c:184
#3  0x00005555559a25a7 in karte_t::step (this=0x55555ad3ba30) at simworld.cc:5525
#4  0x00005555559b62af in karte_t::interactive (this=0x55555ad3ba30, quit_month=2147483647) at simworld.cc:10518
#5  0x000055555594388d in simu_main (argc=1, argv=0x7fffffffe5e8) at simmain.cc:1382
#6  0x0000555555958712 in sysmain (argc=1, argv=0x7fffffffe5e8) at simsys.cc:825
#7  0x0000555555a344c2 in main (argc=1, argv=0x7fffffffe5e8) at simsys_s2.cc:792


Edit: this happens in every save; the game freezes a few minutes after the new month, even on new saves with only 2 cities.

Thank you all for testing: I will have to look into the freeze issue when I get a chance.

Phystam - do the frame skips occur only after deleting a tile comprising a route, or do they occur in any event? As to a possible memory leak, I have not added any malloc() or new() calls, so I do not believe that this is likely; however, the system does involve a gradual increase in memory usage with time.

How do you store the pre-calculated routes to the roads if not using any malloc or new for the signposts? Do you store such an (most often empty) map to any road tile, rather than a (most often null) pointer to such a map?

However, I came here to thank you a lot for that quick implementation, it's really impressive you had it implemented in a single day.
I won't compile and test if before Tuesday but want to thank you for this one already.

Also, it seems you found and fixed a bug in random mode. I will try to thest the fixed random mode without that new feature to get a feeling on how well random mode had worked without the bug.

Freahk - to answer your question: there is a hashtable in each tile of way. The hashtable contains koord objects (as a key) and a vector of koord3d objects (as a value). The hashtable code deals with its own memory allocation and deallocation.

Also, it was not quite implemented in a day - I spent a long time on it the day before yesterday, too.

In any event, I shall look forward to your results of testing.

Ah, I see, fine.

I was just wondering about the described "memory leak" without any malloc being done.
If you don't do any memory allocation and the hash tables themselves don't leak any memory (I would expect this), it won't leak.
Would you expect a growth of memory over time (up to a maximum amount)?

In any event, when testing this branch, I will watch out for growing memory consumption.

Yes, I would expect some growth over time as the routes are built and then rebuilt, but this will be self-limiting. To take account of multi-threading, there are hashtables of the routes stored in the cities (to allow deletion), and these will swap between the active set (that is in use) and the inactive set (which is ready to receive new routes from the multi-threaded algorithm), so memory consumption will increase as these sets are created one by one, but should stop when both sets have been exhausted. Also, the cities will generate routes one by one over time, so memory consumption will grow until all cities have been processed.

Quote from: jamespetts on January 29, 2020, 02:24:29 AM
I have now implemented this on the private-car-routing-lightweight branch on Github. I will not merge this into the master branch just yet to give the intrepid self-compilers a chance to test this in case there are any serious problems that I have not yet spotted. I have, however, spent many hours testing and adjusting this to-day, and it is confirmed working in network mode without loss of synchronisation.

James, thank you for improving Simutrans-Extended again! I've given it a test with mixed results.

Quote from: freddyhayward on January 29, 2020, 07:26:32 AM
Using the stephenson-siemens game, the program freezes permanently (without crashing) about 38 game-minutes into the new month.

Edit: this happens in every save; the game freezes a few minutes after the new month, even on new saves with only 2 cities.

I also got non-crash freezes. It didn't seem to be very closely correlated with any particular time, but it always occurred in the second month after starting/loading the game. I didn't notice anything special at 00:38:00.

Quote from: Phystam on January 29, 2020, 05:27:36 AM
I tested this fantastic patch --- Generally very good, but there are 2 problems.
1. frame skip
Although the CPU usage is quite low, for some reason, the frame skips occur very frequently.

Quote from: jamespetts(3) this has been found to have no adverse effect on performance, and may well actually improve performance.

Yes, I constantly get frameskips as well. It's annoying enough that I wouldn't want this feature put into the master branch while it persists. It seems to be worse on bigger maps.

Quote2. Possible memory leak
While watching the memory usage of simutrans-extended, the value is getting higher gradually. I don't know where it comes from (I believe that it is from very large hash tables creation).

I saw a slight increase of ~0.1GiB in the first month of the game, but nothing after that until the freeze.

QuoteA high proportion of traffic seemed to be heading to city attractions (Simutransians are very fond of sport, it seems),

Last month I abandoned several games in the mid-20th century because of this specific point. If you are playing on >~400mpt or you have a complex layout next to a cricket or rugby stadium, you get an impenetrable traffic jam because the stadia are generating cars faster than the road tiles can take them, presumably because those are the urban attractions that demand/generate lots of High and Very High (i.e. car-owning) visitors. IMHO the root cause it actually an understandable limitation in the economic timing. Real stadia don't reach their capacity all the time: maybe once a week for a rugby stadium (Saturday and midweek games, but one is played away). Maybe one day I'll know enough to do something about it.

QuoteIncidentally, the original heuristic I think had been coded backwards:

There are probably many such horrors lurking in the Simutrans code, despite your valiant efforts.  ;D

QuoteI also got non-crash freezes. It didn't seem to be very closely correlated with any particular time, but it always occurred in the second month after starting/loading the game. I didn't notice anything special at 00:38:00.

I had the same experience - ~38 minutes was only the time for the stephenson-siemens game. on newer saves, it usually happened earlier in the month, around 5 or 10 minutes.

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.

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.

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 would like to check the SDL2 build. Could you provide us it?

About the frame skip — it occurs every times, maybe when checking the next tile... If that issue doesn't occur with SDL2, it is okay. We will use only SDL2 build.

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

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.

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.

Quote from: jamespetts on January 31, 2020, 01:09:26 PMSo, 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.

Quote from: jamespetts on January 30, 2020, 12:30:59 AM
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.

QuoteAs 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.

QuoteEdit: 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 (https://forum.simutrans.com/index.php/topic,19369.0.html) 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! ;D 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.

Quote from: jamespetts-with-emphasis-added on January 31, 2020, 01:09:26 PM
On my quite fast computer (Ryzen 3900x)

;D ;D ;D ;D

Quotethe 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.

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.

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.
(https://cdn.discordapp.com/attachments/665986412641779712/673229364535492638/unknown.png)

When I deleted an intersection, a segmentation fault occurred. see below:
(https://media.discordapp.net/attachments/665986412641779712/673232262354960415/unknown.png)

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?

Quote from: jamespetts on February 01, 2020, 05:15:20 PMEdit: Incidentally, I recommend this video for anyone using this new feature:

I want that house moval feature in simutrans-ex ;D

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 ;D

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.

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

Quote from: jamespetts on February 01, 2020, 08:29:30 PMFeahk - 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.

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.

Quote from: jamespetts on February 01, 2020, 08:29:30 PM
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

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:

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.

Which road tile inaccessible

When I modify a terrain, I get a segmentation fault. Probably, the problem is not related to terrain modification, but deleting roads.
see below:
(https://cdn.discordapp.com/attachments/665986412641779712/673477350838501376/unknown.png)

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.

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 (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.

Quote from: Phystam on February 02, 2020, 02:20:59 PMThe 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? :D

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.

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

QuotePrivate 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.

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.

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

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

Excellent - thank you for confirming.

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.

Testing map using pak256.
(https://cdn.discordapp.com/attachments/665986412641779712/673595742304075776/unknown.png)
Highway drastically changes the road traffic.

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

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.

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?

Quote from: wlindley on February 02, 2020, 06:29:14 PM
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.

Quote from: jamespetts on February 02, 2020, 07:28:07 PM
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.

Quote from: Phystam on February 02, 2020, 06:30:58 PM
Testing map using pak256.
Highway drastically changes the road traffic.

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

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?

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.

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.

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.

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.

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

Quote from: Phystam on February 03, 2020, 01:49:30 PM
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.

Quote from: jamespetts on February 02, 2020, 10:08:08 PMSome 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.

Quote from: jamespetts on February 02, 2020, 10:08:08 PM
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 (https://app.box.com/s/etn9vwr3d5azovz8g4qenx6palgcnfk6) created on this branch (as of  #d1e3688......), which only requires pak128.Britain-Ex nightly. Unfortunately, the 1850s game (this branch, #d1e3688....... (https://app.box.com/s/obwpl0ufqv9ecwpltsaboa01tohdr7nx) or master branch (https://app.box.com/s/xpsqsyya2b6ptsoo5795tszo34twf0m2) 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 (https://app.box.com/s/8rp4zeshrs9emnr48yo56916av883kzj) and unpack the file into your Addons folder.
3. Start Simutrans-Extended with the 235 pakset and addons.

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

QuoteAlso, 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! :laugh: Though that website claims that it is slightly less puny when comparing single threads (about 40% of the Ryzen)

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?

I got a segfault with this backtrace on deleting a road on this branch:

Thread 1 "simutrans-exten" received signal SIGSEGV, Segmentation fault.
0x000055555562c98f in slist_tpl<hashtable_tpl<koord, koord3d, koordhash_tpl<koord> >::node_t>::begin (this=0x4b0) at boden/wege/../../tpl/slist_tpl.h:393
393 iterator begin() { return iterator(head, NULL); }
(gdb) bt full
#0  0x000055555562c98f in slist_tpl<hashtable_tpl<koord, koord3d, koordhash_tpl<koord> >::node_t>::begin (this=0x4b0) at boden/wege/../../tpl/slist_tpl.h:393
No locals.
#1  0x00005555558ce3df in hashtable_tpl<koord, koord3d, koordhash_tpl<koord> >::set (this=0x60, key=..., object=...) at boden/wege/../../tpl/hashtable_tpl.h:335
        iter = {ptr = 0x1ffffba00, pred = 0x5555ab2fe968}
        end = {ptr = 0x7fffffffba33, pred = 0x555559cba0b0}
        bag = <error reading variable>
        node = {key = {x = -17869, y = -1, static invalid = {x = -1, y = -1, static invalid = <same as static member of an already seen type>, static north = {x = 0, y = -1,
                static invalid = <same as static member of an already seen type>, static north = <same as static member of an already seen type>, static south = {x = 0, y = 1,
                  static invalid = <same as static member of an already seen type>, static north = <same as static member of an already seen type>,
                  static south = <same as static member of an already seen type>, static east = {x = 1, y = 0, static invalid = <same as static member of an already seen type>,
                    static north = <same as static member of an already seen type>, static south = <same as static member of an already seen type>,
                    static east = <same as static member of an already seen type>, static west = {x = -1, y = 0, static invalid = <same as static member of an already seen type>,
                      static north = <same as static member of an already seen type>, static south = <same as static member of an already seen type>,
                      static east = <same as static member of an already seen type>, static west = <same as static member of an already seen type>, static nsew = {{x = 0, y = -1,
                          static invalid = <same as static member of an already seen type>, static north = <same as static member of an already seen type>,
                          static south = <same as static member of an already seen type>, static east = <same as static member of an already seen type>,
                          static west = <same as static member of an already seen type>, static nsew = <same as static member of an already seen type>,
                          static neighbours = <same as static member of an already seen type>, static second_neighbours = <same as static member of an already seen type>,
                          static from_ribi = <same as static member of an already seen type>, static from_hang = <same as static member of an already seen type>}, {x = 0, y = 1,
                          static invalid = <same as static member of an already seen type>, static north = <same as static member of an already seen type>,
                          static south = <same as static member of an already seen type>, static east = <same as static member of an already seen type>,
                          static west = <same as static member of an already seen type>, static nsew = <same as static member of an already seen type>,
                          static neighbours = <same as static member of an already seen type>, static second_neighbours = <same as static member of an already seen type>,
                          static from_ribi = <same as static member of an already seen type>, static from_hang = <same as static member of an already seen type>}, {x = 1, y = 0,
                          static invalid = <same as static member of an already seen type>, static north = <same as static member of an already seen type>,
                          static south = <same as static member of an already seen type>, static east = <same as static member of an already seen type>,
                          static west = <same as static member of an already seen type>, static nsew = <same as static member of an already seen type>,
                          static neighbours = <same as static member of an already seen type>, static second_neighbours = <same as static member of an already seen type>,
                          static from_ribi = <same as static member of an already seen type>, static from_hang = <same as static member of an already seen type>}, {x = -1, y = 0,
                          static invalid = <same as static member of an already seen type>, static north = <same as static member of an already seen type>,
                          static south = <same as static member of an already seen type>, static east = <same as static member of an already seen type>,
                          static west = <same as static member of an already seen type>, static nsew = <same as static member of an already seen type>,
                          static neighbours = <same as static member of an already seen type>, static second_neighbours = <same as static member of an already seen type>,
                          static from_ribi = <same as static member of an already seen type>, static from_hang = <same as static member of an already seen type>}},
                      static neighbours = <same as static member of an already seen type>, static second_neighbours = <same as static member of an already seen type>,
                      static from_ribi = <same as static member of an already seen type>, static from_hang = <same as static member of an already seen type>},
                    static nsew = <same as static member of an already seen type>, static neighbours = <same as static member of an already seen type>,
                    static second_neighbours = <same as static member of an already seen type>, static from_ribi = <same as static member of an already seen type>,
                    static from_hang = <same as static member of an already seen type>}, static west = <same as static member of an already seen type>,
                  static nsew = <same as static member of an already seen type>, static neighbours = <same as static member of an already seen type>,
                  static second_neighbours = <same as static member of an already seen type>, static from_ribi = <same as static member of an already seen type>,
                  static from_hang = <same as static member of an already seen type>}, static east = <same as static member of an already seen type>,
                static west = <same as static member of an already seen type>, static nsew = <same as static member of an already seen type>,
                static neighbours = <same as static member of an already seen type>, static second_neighbours = <same as static member of an already seen type>,
                static from_ribi = <same as static member of an already seen type>, static from_hang = <same as static member of an already seen type>},
              static south = <same as static member of an already seen type>, static east = <same as static member of an already seen type>,
              static west = <same as static member of an already seen type>, static nsew = <same as static member of an already seen type>,
              static neighbours = <same as static member of an already seen type>, static second_neighbours = <same as static member of an already seen type>,
              static from_ribi = <same as static member of an already seen type>, static from_hang = <same as static member of an already seen type>},
            static north = <same as static member of an already seen type>, static south = <same as static member of an already seen type>, static east = <same as static member of an already seen type>,
            static west = <same as static member of an already seen type>, static nsew = <same as static member of an already seen type>,
            static neighbours = <same as static member of an already seen type>, static second_neighbours = <same as static member of an already seen type>,
            static from_ribi = <same as static member of an already seen type>, static from_hang = <same as static member of an already seen type>}, value = {x = 32767, y = 0, z = -80 '\260',
            static invalid = {x = -1, y = -1, z = -1 '\377', static invalid = <same as static member of an already seen type>}}}
#2  0x00005555558c9159 in stadt_t::process_private_car_routes (this=0x5555a2b5c960) at simcity.cc:6139
--Type <RET> for more, q to quit, c to continue without paging--
        previous_tile = {x = 115, y = 517, z = 0 '\000', static invalid = {x = -1, y = -1, z = -1 '\377', static invalid = <same as static member of an already seen type>}}
        gr = 0x5555ab2fe968
        road_tile = 0x0
        route = @0x5555a96e0560: {key = {x = 114, y = 518, static invalid = {x = -1, y = -1, static invalid = <same as static member of an already seen type>, static north = {x = 0, y = -1,
                static invalid = <same as static member of an already seen type>, static north = <same as static member of an already seen type>, static south = {x = 0, y = 1,
                  static invalid = <same as static member of an already seen type>, static north = <same as static member of an already seen type>,
                  static south = <same as static member of an already seen type>, static east = {x = 1, y = 0, static invalid = <same as static member of an already seen type>,
                    static north = <same as static member of an already seen type>, static south = <same as static member of an already seen type>,
                    static east = <same as static member of an already seen type>, static west = {x = -1, y = 0, static invalid = <same as static member of an already seen type>,
                      static north = <same as static member of an already seen type>, static south = <same as static member of an already seen type>,
                      static east = <same as static member of an already seen type>, static west = <same as static member of an already seen type>, static nsew = {{x = 0, y = -1,
                          static invalid = <same as static member of an already seen type>, static north = <same as static member of an already seen type>,
                          static south = <same as static member of an already seen type>, static east = <same as static member of an already seen type>,
                          static west = <same as static member of an already seen type>, static nsew = <same as static member of an already seen type>,
                          static neighbours = <same as static member of an already seen type>, static second_neighbours = <same as static member of an already seen type>,
                          static from_ribi = <same as static member of an already seen type>, static from_hang = <same as static member of an already seen type>}, {x = 0, y = 1,
                          static invalid = <same as static member of an already seen type>, static north = <same as static member of an already seen type>,
                          static south = <same as static member of an already seen type>, static east = <same as static member of an already seen type>,
                          static west = <same as static member of an already seen type>, static nsew = <same as static member of an already seen type>,
                          static neighbours = <same as static member of an already seen type>, static second_neighbours = <same as static member of an already seen type>,
                          static from_ribi = <same as static member of an already seen type>, static from_hang = <same as static member of an already seen type>}, {x = 1, y = 0,
                          static invalid = <same as static member of an already seen type>, static north = <same as static member of an already seen type>,
                          static south = <same as static member of an already seen type>, static east = <same as static member of an already seen type>,
                          static west = <same as static member of an already seen type>, static nsew = <same as static member of an already seen type>,
                          static neighbours = <same as static member of an already seen type>, static second_neighbours = <same as static member of an already seen type>,
                          static from_ribi = <same as static member of an already seen type>, static from_hang = <same as static member of an already seen type>}, {x = -1, y = 0,
                          static invalid = <same as static member of an already seen type>, static north = <same as static member of an already seen type>,
                          static south = <same as static member of an already seen type>, static east = <same as static member of an already seen type>,
                          static west = <same as static member of an already seen type>, static nsew = <same as static member of an already seen type>,
                          static neighbours = <same as static member of an already seen type>, static second_neighbours = <same as static member of an already seen type>,
                          static from_ribi = <same as static member of an already seen type>, static from_hang = <same as static member of an already seen type>}},
                      static neighbours = <same as static member of an already seen type>, static second_neighbours = <same as static member of an already seen type>,
                      static from_ribi = <same as static member of an already seen type>, static from_hang = <same as static member of an already seen type>},
                    static nsew = <same as static member of an already seen type>, static neighbours = <same as static member of an already seen type>,
                    static second_neighbours = <same as static member of an already seen type>, static from_ribi = <same as static member of an already seen type>,
                    static from_hang = <same as static member of an already seen type>}, static west = <same as static member of an already seen type>,
                  static nsew = <same as static member of an already seen type>, static neighbours = <same as static member of an already seen type>,
                  static second_neighbours = <same as static member of an already seen type>, static from_ribi = <same as static member of an already seen type>,
                  static from_hang = <same as static member of an already seen type>}, static east = <same as static member of an already seen type>,
                static west = <same as static member of an already seen type>, static nsew = <same as static member of an already seen type>,
                static neighbours = <same as static member of an already seen type>, static second_neighbours = <same as static member of an already seen type>,
                static from_ribi = <same as static member of an already seen type>, static from_hang = <same as static member of an already seen type>},
              static south = <same as static member of an already seen type>, static east = <same as static member of an already seen type>,
              static west = <same as static member of an already seen type>, static nsew = <same as static member of an already seen type>,
              static neighbours = <same as static member of an already seen type>, static second_neighbours = <same as static member of an already seen type>,
              static from_ribi = <same as static member of an already seen type>, static from_hang = <same as static member of an already seen type>},
            static north = <same as static member of an already seen type>, static south = <same as static member of an already seen type>, static east = <same as static member of an already seen type>,
            static west = <same as static member of an already seen type>, static nsew = <same as static member of an already seen type>,
            static neighbours = <same as static member of an already seen type>, static second_neighbours = <same as static member of an already seen type>,
            static from_ribi = <same as static member of an already seen type>, static from_hang = <same as static member of an already seen type>}, value = {data = 0x7fffa816f410, size = 205,
            count = 190}}
        once1__6117 = false
        iter__6117 = {bag_i = 0x5555a2b600c8, bag_end = 0x5555a2b605f0, node_i = {ptr = 0x5555a96e0558}}
        end__6117 = {bag_i = 0x5555a2b605f0, bag_end = 0x5555a2b605f0, node_i = {ptr = 0x0}}
        break__6117 = true
--Type <RET> for more, q to quit, c to continue without paging--
        container___6117 = @0x5555a2b5fc78: {<hashtable_tpl<koord, vector_tpl<koord3d>, koordhash_tpl<koord> >> = {bags = {{head = 0x7fff741d6518, tail = 0x7fff741d1b78, node_count = 2}, {
                head = 0x5555ad752ff8, tail = 0x7fff741d1718, node_count = 2}, {head = 0x0, tail = 0x0, node_count = 0}, {head = 0x7fff741d2738, tail = 0x7fff741d2738, node_count = 1}, {
                head = 0x7fff601011f8, tail = 0x7fff601011f8, node_count = 1}, {head = 0x0, tail = 0x0, node_count = 0}, {head = 0x7fffa8098308, tail = 0x555555f6e068, node_count = 2}, {
                head = 0x5555ad74e1d8, tail = 0x5555ab7f6f08, node_count = 3}, {head = 0x0, tail = 0x0, node_count = 0}, {head = 0x7fff741d65b8, tail = 0x7fff741d65b8, node_count = 1}, {head = 0x0,
                tail = 0x0, node_count = 0}, {head = 0x7fff741d61f8, tail = 0x5555a8ae6db8, node_count = 3}, {head = 0x0, tail = 0x0, node_count = 0}, {head = 0x7fff600fc4f8, tail = 0x7fff600fc4f8,
                node_count = 1}, {head = 0x7fff600fc618, tail = 0x7fff600fc618, node_count = 1}, {head = 0x5555ad754e58, tail = 0x7fff741d1758, node_count = 3}, {head = 0x0, tail = 0x0, node_count = 0},
              {head = 0x5555ab162828, tail = 0x5555ab162828, node_count = 1}, {head = 0x0, tail = 0x0, node_count = 0}, {head = 0x0, tail = 0x0, node_count = 0}, {head = 0x0, tail = 0x0,
                node_count = 0}, {head = 0x0, tail = 0x0, node_count = 0}, {head = 0x555555f68fe8, tail = 0x555555f68fe8, node_count = 1}, {head = 0x0, tail = 0x0, node_count = 0}, {
                head = 0x5555ad754b98, tail = 0x7fffa01d7668, node_count = 2}, {head = 0x7fff741d1898, tail = 0x7fff741d1898, node_count = 1}, {head = 0x5555ad7553f8, tail = 0x555555f6ab08,
                node_count = 2}, {head = 0x5555ad754198, tail = 0x5555ad754198, node_count = 1}, {head = 0x0, tail = 0x0, node_count = 0}, {head = 0x0, tail = 0x0, node_count = 0}, {head = 0x0,
                tail = 0x0, node_count = 0}, {head = 0x0, tail = 0x0, node_count = 0}, {head = 0x7fff741d67d8, tail = 0x7fff741d67d8, node_count = 1}, {head = 0x0, tail = 0x0, node_count = 0}, {
                head = 0x7fff741d1a58, tail = 0x5555aaa09f98, node_count = 4}, {head = 0x0, tail = 0x0, node_count = 0}, {head = 0x7fff600fc9f8, tail = 0x7fffa8098808, node_count = 4}, {head = 0x0,
                tail = 0x0, node_count = 0}, {head = 0x5555a37dd698, tail = 0x5555a37dd698, node_count = 1}, {head = 0x0, tail = 0x0, node_count = 0}, {head = 0x0, tail = 0x0, node_count = 0}, {
                head = 0x0, tail = 0x0, node_count = 0}, {head = 0x0, tail = 0x0, node_count = 0}, {head = 0x555555fdca38, tail = 0x555555fdca38, node_count = 1}, {head = 0x0, tail = 0x0,
                node_count = 0}, {head = 0x5555ad7544b8, tail = 0x5555a3367258, node_count = 2}, {head = 0x5555a96e0558, tail = 0x5555a96e0558, node_count = 1}, {head = 0x7fff741d2378,
                tail = 0x7fff741d2378, node_count = 1}, {head = 0x0, tail = 0x0, node_count = 0}, {head = 0x7fff741d2438, tail = 0x7fff741d2438, node_count = 1}, {head = 0x5555ad7526f8,
                tail = 0x5555ad7526f8, node_count = 1}, {head = 0x0, tail = 0x0, node_count = 0}, {head = 0x0, tail = 0x0, node_count = 0}, {head = 0x0, tail = 0x0, node_count = 0}, {head = 0x0,
                tail = 0x0, node_count = 0}, {head = 0x5555ac3691a8, tail = 0x5555ac3691a8, node_count = 1}, {head = 0x0, tail = 0x0, node_count = 0}, {head = 0x5555a8f0edc8, tail = 0x555555fba8e8,
                node_count = 2}, {head = 0x5555ad7537b8, tail = 0x555555fbb648, node_count = 2}, {head = 0x7fff600fc698, tail = 0x7fff600fc698, node_count = 1}, {head = 0x0, tail = 0x0, node_count = 0},
              {head = 0x0, tail = 0x0, node_count = 0}, {head = 0x7fff600ff078, tail = 0x7fff600ff078, node_count = 1}, {head = 0x0, tail = 0x0, node_count = 0}, {head = 0x7fff741d1df8,
                tail = 0x7fff741d1df8, node_count = 1}, {head = 0x7fff741d64f8, tail = 0x7fff741d64f8, node_count = 1}, {head = 0x7fffa8099488, tail = 0x7fffa8099488, node_count = 1}, {head = 0x0,
                tail = 0x0, node_count = 0}, {head = 0x5555ad754898, tail = 0x5555ad754898, node_count = 1}, {head = 0x5555ad752718, tail = 0x5555ad7546d8, node_count = 2}, {head = 0x5555ad753458,
                tail = 0x5555ad753458, node_count = 1}, {head = 0x7fff741d2598, tail = 0x7fff741d2598, node_count = 1}, {head = 0x555555f6b488, tail = 0x555556005708, node_count = 2}, {
                head = 0x5555a8e232d8, tail = 0x5555a8e232d8, node_count = 1}, {head = 0x7fff741d5fd8, tail = 0x7fff741d5fd8, node_count = 1}, {head = 0x0, tail = 0x0, node_count = 0}, {
                head = 0x5555ad7527b8, tail = 0x555555f6ab28, node_count = 2}, {head = 0x0, tail = 0x0, node_count = 0}, {head = 0x7fff600fc3f8, tail = 0x7fff600fc3f8, node_count = 1}, {head = 0x0,
                tail = 0x0, node_count = 0}, {head = 0x555555f694e8, tail = 0x7fff60100738, node_count = 8}, {head = 0x0, tail = 0x0, node_count = 0}, {head = 0x7fffa80998c8, tail = 0x7fff741d66b8,
                node_count = 2}, {head = 0x5555ad74db58, tail = 0x5555ad74ea98, node_count = 2}, {head = 0x0, tail = 0x0, node_count = 0}, {head = 0x555555f6afa8, tail = 0x555555f6afa8, node_count = 1},
              {head = 0x0, tail = 0x0, node_count = 0}, {head = 0x0, tail = 0x0, node_count = 0}, {head = 0x0, tail = 0x0, node_count = 0}, {head = 0x5555a8f4ffb8, tail = 0x5555ad5919a8,
                node_count = 3}, {head = 0x7fffa8096e48, tail = 0x555555fb86c8, node_count = 3}, {head = 0x7fff741d63b8, tail = 0x7fff600fc5d8, node_count = 2}, {head = 0x7fffa80982e8,
                tail = 0x7fffa80982e8, node_count = 1}, {head = 0x5555ad753ab8, tail = 0x5555ad593288, node_count = 2}, {head = 0x5555ad74e438, tail = 0x5555ad74e438, node_count = 1}, {
                head = 0x555555f6a0c8, tail = 0x555555f6a0c8, node_count = 1}, {head = 0x5555ad752a18, tail = 0x7fffa01de648, node_count = 2}, {head = 0x0, tail = 0x0, node_count = 0}, {head = 0x0,
                tail = 0x0, node_count = 0}, {head = 0x0, tail = 0x0, node_count = 0}, {head = 0x0, tail = 0x0, node_count = 0}}, count = 95}, <No data fields>}
        once0__6117 = false
#3  0x00005555558bab58 in stadt_t::step_heavy (this=0x5555a2b5c960) at simcity.cc:2692
        error = 0
        __PRETTY_FUNCTION__ = "void stadt_t::step_heavy()"
#4  0x00005555559aa7c6 in karte_t::step (this=0x555559cba0b0) at simworld.cc:5529
        i = 0x5555a2b5c960
        once1__5521 = false
        iter__5521 = {ptr = 0x5555a4131480}
        end__5521 = {ptr = 0x5555a41315f0}
        break__5521 = true
        container___5521 = @0x555559cbb0c0: {nodes = 0x5555a4131480, size = 24, count = 23, total_weight = 84476}
        once0__5521 = false
        time = 65459
        delta_t = 100
        check_city_routes = false
        season_change = false
        snowline_change = false
        step_cities_count = 0
        dt = 0
#5  0x00005555559be61f in karte_t::interactive (this=0x555559cba0b0, quit_month=2147483647) at simworld.cc:10549
        time = 65458
        hashes_ok = {data = 0x0, size = 0, count = 0}
        ms_difference = 0
--Type <RET> for more, q to quit, c to continue without paging--
#6  0x000055555594b69b in simu_main (argc=1, argv=0x7fffffffe608) at simmain.cc:1382
        pause_after_load = false
        welt = 0x555559cba0b0
        view = 0x555559cc47a0
        eventmanager = 0x555559cc46b0
        resolutions = {{640, 480}, {800, 600}, {1024, 768}, {1280, 1024}, {704, 560}}
        disp_width = 704
        disp_height = 560
        fullscreen = 0
        quit_month = 2147483647
        path_sep = 0x555555a7501e "/"
        pak_diagonal_multiplier = 724
        pak_tile_height = 8 '\b'
        pak_height_conversion_factor = 2 '\002'
        found_settings = false
        found_simuconf = true
        multiuser = true
        simuconf = {file = 0x0}
        path_to_simuconf = "config/simuconf.tab\000\000\000\000"
        version = 0x555555a750f0 "Simutrans version 120.2.1 Extended Nightly development build 14.9 from Feb  3 2020 #d1e3688\n"
        cli_syslog_enabled = false
        cli_syslog_tag = 0x0
        file = {mode = 4, saving = false, buffered = false, curr_buff = 0, buf_pos = {0, 0}, buf_len = {0, 0}, ls_buf = {0x0, 0x0}, version = 0, extended_version = 0, extended_revision = 0, ident = 0,
          pak_extension = '\000' <repeats 255 times>, filename = "", fd = 0x555555d0ff40, static save_mode = loadsave_t::zipped, static autosave_mode = loadsave_t::zipped}
        xml_filename = "settings-extended-debug.xml\000\000\000\000"
        xml_settings_found = false
        obj_conf = "{dir}/simutrans/simuconf.tab"
        themes_ok = true
        parameter = {0, 0}
        new_world = false
        loadgame = ""
#7  0x0000555555960520 in sysmain (argc=1, argv=0x7fffffffe608) at simsys.cc:825
        buffer2 = 0x0
        buffer = "{dir}/Simutrans-Extended-Complete/simutrans/simutrans-extended-debug", '\000' <repeats 24 times>, "\020\000\000\000\000\000\000\000R\345td\004\000\000\000\310\t\002\000\000\000\000\000\310\031\002\000\000\000\000\000\310\031\002\000\000\000\000\000\070\006\000\000\000\000\000\000\070\006\000\000\000\000\000\000\001\000\000\000\000\000\000\000\004\000\000\000\020\000\000\000\005\000\000\000GNU\000\002\000\000\300\004\000\000\000"...
        length = 88
#8  0x0000555555a3e1aa in main (argc=1, argv=0x7fffffffe608) at simsys_s2.cc:792
No locals.


I believe that I may have fixed the above crash - I should be grateful if you could re-test.

Quote from: jamespetts on February 03, 2020, 11:45:19 PM
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?

Apologies, there was a typo in the BBcode. Fixed now.

Quote from: Matthew on February 04, 2020, 03:42:21 PM
Apologies, there was a typo in the BBcode. Fixed now.

Splendid, thank you: I have now had a chance to look at this. A performance profiler suggests that ~8% of CPU time is being spent on processing private car routes in this map, of which ~4% is on clearing existing private car routes before processing - but  there is very little else computationally intensive going on, since there are no player transport routes save for a single 'bus line, so all the other CPU intensive activities, such as the path explorer, convoy routing, passenger and mail generation, vehicle physics and route unreserving are not applicable here, such that private car routing is the only CPU intensive activity apart from the graphics.

It is possible that a more sophisticated design might allow route processing to be faster; one possibility is to use a fixed size array of hashtables in each tile (rather than having a single hashtable), with one for reading the other for writing, swapping between them periodically; but this is likely to be very complex to implement, and it is not clear to me how deleting routes would work in such a system. Freahk suggested a system of this sort, so he might have a clearer idea of how to do this.

Another possibility is having parallel multi-threading of this. At present, the processing of private car routes is done in a single thread. This is now set to run concurrently with the passenger and mail generation threads. In a developed game, the passenger and mail generation threads are very CPU intensive, so take a long time; running this concurrently with them, especially on a computer with many cores, will allow this to be more time efficient.

However, on a map which is nearly all private car routing, the passenger and mail generation takes so little time that this has no benefit. Running it in parallell, however, might help a little: what this would do is, for each route to process, have one thread process the first part of the route, another thread process the second part of the route and so on, depending on the number of threads assigned to this task. This is the same system as the multi-threaded route unreservation system for trains. This would be more efficient no matter how much that the passenger and mail generation threads were being used. However, this would take a significant amount of work to code, as multi-threading is always complex and difficult work.

I should be interested to hear from other people as to the performance with Matthew's 1960 era map; this would be most useful in determining the significance of this issue. I also notice that Matthew's computer is rather limited in RAM - this saved game alone when running takes ~1.2Gb of RAM, which is a significant proportion of 4GB. If Matthew were running low on RAM, this would potentially impact performance significantly.

One other thing to note is that one can set "assume_everywhere_connected_by_road" to disable private car route searching entirely, which will reduce any performance impact.

In any event, thank you for testing, and I should be interested in any feedback on performance that any of you might have.

Sometimes I observe that a private car stops at the front of a junction, such as an exit of the highway. It looks that the car is searching for his direction where he wants to go. It may cause severe traffic congestion behind the highway exit.
In order to prevent that phenomenon, I suggest guide signs. A guide sign acts as a distant signal on railways, and it tells private cars the direction of the next junction (or the next next junction, when the junction has multi tiles). If he finds which direction to go, he does not need to stop at the junction.

Double post!

You can test the private car path using our pakset: https://cdn.discordapp.com/attachments/665986412641779712/674636337025908805/pak256-testmap.zip (https://cdn.discordapp.com/attachments/665986412641779712/674636337025908805/pak256-testmap.zip)
savedata: https://cdn.discordapp.com/attachments/665986412641779712/674636465623400458/demo-okinawa-citycar.zip (https://cdn.discordapp.com/attachments/665986412641779712/674636465623400458/demo-okinawa-citycar.zip)

Finally I had compiled and tested this on my dev device (i7-6700HQ, 16GB ram, opensuse, stephenson-siemens save, compiled with OPTIMISE=1 setting, sdl2)

Performance aspects
First, the performance aspect as it was discussed quite a lot in the last few posts. I could not find any significiant perfromance issues yesterday evening, so I let the game run the whole night and today I still get more or less constant 30 Fps out of it. It varies in between 27-32 Fps. It's fine and without looking at the Fps number, I did not notice these little variations.

To directly compare this without digging deep in profilers and stuff like that (James already did this quite a lot, so I don't think such observations are quite helpful), I just launched both self compiled binaries (master branch and private-car-routing-lightweight branch) at the same time with the same save from stephenson-siemens and let both running for several hours.
I should mention that both games did not seem to be bottlenecked by any ressources. Both were running at ~30 Fps whenever I had a quick look at them and after 4 hours, both games were still at the same ingame time +/- 2s.

The private car binary consumed ~3200 mb additional memory, which is a fairly small amount.
Further, the private car binary consumed slightly more CPU, however the main thread consumes even a little bit less CPU on average. I had observed some main thread CPU spikes pushing the updated routes to the roads) in the main thread but could not measure significiant spikes, so it is either to fast to show as at the given sampling rate or it is bandwith limited rather than cpu limited.

I will continue observations on Mathews posted map soon.

Gameplay aspects
Now let's get to the gameplay aspects of this feature. How well does it solve our issue of cities jammed by randomly stucking around drivers?
I hav observed this on the mentioned stephenson-siemens game and the latest save from my server, which is from December.
I am quite sorry, I have not packed it into a nice story this time but I have a quite huge backlog of stuff and packing this into a story without missing the points will simply take a lot more time to write.

I would say the core functionality of this patch works great, which is a well-working long-distance car routing, thus also less jamming within cities. City bypasses work just well and the time to update routes is quite fast, maybe even too fast with complaints about perfomance in mind. Imho it's not an issue if it takes a few minutes to update a route as long as the old route was not detected broken, in which case we need a more or less immediate update of course.

In the first place everything was just stuck but after buildung a few bypasses, traffic flow was fine and it is quite impressive to watch the cars moving. However, due to the limitations of simuroads we will need to be extremely careful when building intersections. Avoid diagonal intersections and non-motorway like connections to adjacent parallel roads. Both will greatly decrease roads throughput, the latter will even quite likely cause gridlocks. With these rules in mind, one can build a relatively well performing intercity road network.

However, there are a few more aspects than long-distance journeys:
- What happens within cities?
- What happens to car traps?
-What happens if a bypass has multiple exists for the same city?
- What happens to cities being partly an island?

What happens within cities?
At first, thanks to a little patch, there is no random mode anymore, I guess it's fine now calling it heuristics mode.
As expected, how fast cars will find a guided road depens on two factors:
1. How many different roads within the town are guided?
The more, the better, in terms of quickly finding a guided route to the destination. Towns with a bypass road will quite often only have one route through the city towards many destinations, so each car in the city has to find that road to leave the town.

2. How well does the road network (and giuded road network) match to the guesses of the heuristics?
If a car spawns in an area with many actual and city border implied dead ends, the heuristics will make quite bad guesses so it will take quite a lot of time to find a guided way out of the town.
Another point is private cars spawning e.g. in the south of a city when their destination is also south of the city but the road towards that city is in the north.
The heuristics will be quite bad in that case, so it will take quite a lot of time to find a guided way out of the town.

What happens to car traps?
In short, they won't work outside of cities but within cities they still work quite "well" when built around corners where the heuristics fails. In general, the closer to the border of a map, the more destinations will be in the same direction, the easyer it is to catch cars towards that direction before they reach the guided road.
Especially if one designs such guided roads to have as few roads connected as possible, the easyer it will be to trap cars.

What happens if a bypass has multiple exists for the same city?
If the bypass itself is within city borders, cars will be in heuristics mode, so it's more or less all right. Heuristics mode does not really like motorway exits/slip roads as cars will most often need to drive in the wrong direction for a short time.
If the bypass is outside of city borders, any traffic towards the same city (without monuments) will use the same exit, the one that reaches the city center best, although it might be a much worse route for many people in that city than another exit.
This is the "enter city" equivalent to the above described "leave city" issue. If the destination is not close to the city center, it might drive strange detours in the city, although it could just take another exit very close to their door.
So we get to the last point where this behavior gets even worse.

What happens to cities being partly an island?
Either the city center is on the island, in which case this city will only spawn private cars within the city or the city center is not on the island, in which case anyone in that city considers travelling by car.
In the first case Inhabitants that could use their private car to get to their destination won't use it. It's odd but not a huge issue.
Further there will be cars spawned within the city that can never reach their destination because it's on the other side of the water. Sometimes there might even be a road connection outside of the city borders but private cars will never find that route because it's outside of the city. Whilst also odd, this ususally is not a huge issue as there won't be that many private cars spawned for journeys within the city to have a huge impact on city traffic.
It get's much worse when the city center is connected to the road network but parts of the city are not!
In that case there will spawn a lot more cars on the island and towards the island that will cause very much congestion.

Conclusion
One can argue about the performance, so I will only consider the gameplay aspects here.
In many situations the new feature will be a huge improvement. It unstucks nonsensely stucked cities and will create a lot of traffic along main routes leading to much more realistic congestions than before if not properly counterplayed by bypasses.
However, entering and leaving guided mode could require some improvement and partly disconnected cities will be an issue.
Iirc on the Bridgewater-Brunel game there were quite a lot cities that jumped across the ocean. On Stephenson-Siemens this is not an issue.

If you are interessted in a possible solution, please let me know. It's not too complicated, essentially remaining with one route per city (including attractions) but adding sub-routes for chunks of the city.'

Quote from: jamespetts on February 05, 2020, 12:37:13 AMIt is possible that a more sophisticated design might allow route processing to be faster; one possibility is to use a fixed size array of hashtables in each tile (rather than having a single hashtable), with one for reading the other for writing, swapping between them periodically; but this is likely to be very complex to implement, and it is not clear to me how deleting routes would work in such a system. Freahk suggested a system of this sort, so he might have a clearer idea of how to do this.

In short, this is called a transactional data structure.
There are multiple ways to ensure this but all use the same idea: Prepare an operation (e.g. insert, remove,...) But do not immediately show these changes to the outside before we get told the transaction is complete. In that case use the prepared data to quickly perform the actions.

The easyest approach is maintaining two identical sets of data, one being used to read from, the other one used to write to.
Once a write transaction is done, we will flush that information to to read dataset by simply swapping the datasets.
When swapping only the read dataset will be valid.
Before we can start the next transacrion, we will first need to get it in sync with the read dataset.

In our case, the cleanest way should be implementing this directly into the hash map, however, if we don't want to change the maps implementation, we could also go the less clean (and slightly less performant) way of implementing this in the route calculation logic. I will describe the latter as the description can easily be adapted to implement it directly to the hash map.

The whole progress of calculating and updating would be the following:
1. In parallel select a route to be recalculated and calculate the new route.
Calculate the union set of both routes.
For each tile in the union, prepare the inactive signpost by synching it to the used signpost.
For each tile in the old route, remove the routing information from the inactive sign.
For each tile in the new route, add the routing information to the inactive sign.
Add the (origin,destination,new_route,union_tiles) 4-tuple to the route update queue (transaction done, please flush)

2. In sync select a route from the route update queue.
For each tile in the union tiles swap the active/inactive signpost.
Replace the (origin,destination) route in origin towns route list with the new route.

We pay that ability to quickly flush our changes obviously by additional memory and some additional administration effort (does one say this?)

Thank you all for your feedback, and to Freahk for the detailed feedback especially.
Phystam: I have also observed that issue. I traced it back to the overtaking code; the car seems to think that another car is blocking its route, but I did not get as far as finding out why. It is not clear whether this is an issue specific to this code or whether it existed before but was harder to detect. Thank you for the pakset and saved game! It is very interesting to see the cars all using the freeway/highway/motorway rather than the local roads: it is most satisfying to watch.
I see that the stopping at junction bug does affect this map badly, so I may well need to look into this.

As to performance, I note that this seems to cause some issues on less powerful computers. I will have to consider implementing the parallel/sequential multi-threading for route processing: this is the only performance improvement that is likely to be feasible, I think.
I am very glad that bypasses work as intended (I hope that everyone enjoyed the old film about them above) - there is much to be said for a good bypass.

In relation to the gameplay issues, the issues identified are likely to be unsolveable without a more sophisticated algorithm. I note that Frahk suggests one (something similar to the route fragments idea that I had imagined long ago but dismissed as too complex), but I am concerned about the complexity and performance impact of coding this. However, the issues that remain are no worse than they would be without the existing lightweight code on this branch (although they were perhaps less easily observed previously when cars moved randomly).

I will also need to look into recalibrating the visitor demand of sports stadia, as these seem to be out of proportion with other items in the game: but this will need some detailed data and computation.
In any event, thank you again all for your feedback: it is most helpful.

Quote from: jamespetts on February 05, 2020, 05:24:54 PMIt is not clear whether this is an issue specific to this code or whether it existed before but was harder to detect.

I had previously observed busses "waiting for clearance" when the road was entirely free, but could not further investigate thus, so this might have existed before already.

Quote from: jamespetts on February 05, 2020, 05:24:54 PMHowever, the issues that remain are no worse than they would be without the existing lightweight code on this branch (although they were perhaps less easily observed previously when cars moved randomly).

This is absolutely true. The routing improves the game in any case. I had just listed any considerations of what (related) issues the routing solves and which will remain.

I have spent some time this evening investigating the issue with cars waiting unnecessarily at junctions. The code in this respect is extremely complex (and I did not write this myself, so I have no idea what was intended), and it is very difficult to trap the necessary behaviour in a debugger. However, I have managed to alter the behaviour somewhat by commenting out a part of the code. This seems to make private cars less cautious at junctions generally. I cannot find any significant adverse side effects to this, but I should be grateful if people could re-test in case there are any serious side effects of this that I have missed, and also check whether this in fact solves the problem.

Excellent, the heavy congestion on my map has gone after the modification. Probably THLeaderH, who is the developer of OTRP patch, knows about that. I will ask him.

I have now added multi-threading for the processing of the private car routes in order to improve performance. I should be grateful if people could re-test to see whether performance is improved and whether the feature still works correctly. Thank you.

First the performance was very good.
However, the FPS suddenly fell down to ~ 5 fps. the very low FPS kept until shutting down the game. And I observed very high CPU usage up to ~30 %.
(https://media.discordapp.net/attachments/665986412641779712/675169401682788391/unknown.png)

I tried to reload the save data but failed, with a message:
(https://cdn.discordapp.com/attachments/665986412641779712/675169576245395456/unknown.png)

Multi-threading now does spread across cores and the game functions properly, but still with very long spells of extremely slow fast-forward per Phystam.

Quote from: Phystam on February 07, 2020, 01:35:20 AM
Excellent, the heavy congestion on my map has gone after the modification. Probably THLeaderH, who is the developer of OTRP patch, knows about that. I will ask him.

The indicated code is written to prevent private cars from stacking in an intersection. When the intersection tiles are in a row, private cars should confirm that there is no car in the all intersection tiles. However, a private car knows coordinates of only two tiles ahead, so the code inspects only two successive tiles.

Quote from: THLeaderH on February 07, 2020, 03:47:41 PM
The indicated code is written to prevent private cars from stacking in an intersection. When the intersection tiles are in a row, private cars should confirm that there is no car in the all intersection tiles. However, a private car knows coordinates of only two tiles ahead, so the code inspects only two successive tiles.

Interesting, thank you. Commenting out the check for the second tile does appear to make traffic flow rather better and alleviates the unnecessary stoppage bug. If there be a way of fixing the latter without removing this, then this may be considered, but it is not clear at present that it is better to have this check than not.

Incidentally, as to the performance, I have pushed a further change to improve performance, but I am noticing some performance issues that are somewhat mysterious in that the information in the performance profiler does not seem to correspond in a way that I can understand to the observed performance in the game, the times of lower in-game performance corresponding to a considerably smaller proportion of CPU time being registered as being taken by the private car routing features than at times of apparently higher performance.

The saved game issue I will have to look into - thank you for the report.

Edit: I have now fixed the loading/saving issue, although this breaks compatibility with saved games from this branch (but not the master branch). This can be overcome in the debugger by stopping execution at line 9544 of simworld.cc and manually moving execution to line 9548 when loading an earlier saved game.

Edit 2: As to the performance, can I check whether this is apparently any worse than the earlier version without multi-threading?

Edit 3: Further testing shows that the multi-threaded route processing does appear to make performance worse - I suspect that the thread synchronisaiton overhead for the freelist mutex is the culprit. With this enabled, processing all the private car routes on the Pak256 testing map posted by Phystam above took circa 250ms. With this disabled, it fluctuated between circa 70ms and circa 180ms, but was usually circa 100ms. I have thus disabled this feature, but I have not at this juncture removed it: it can be re-enabled by defining the preprocessor symbol MULTI_THREAD_ROUTE_PROCESSING so that others can conduct more thorough comparative testing if desired. I should note that this change also stops route processing from being concurrent to the passenger generation algorithm, which may not be an efficient change; but that may need further consideration in time.

The newsystem is like allELEMENTSin1BOX

Still I have a problem when loading the save data with the multi-threaded process... (https://cdn.discordapp.com/attachments/665986412641779712/675412963871555593/unknown.png)

Phystam: does that only happen when you enable the multi-threading for route processing using the preprocessor directive?

I have undertaken some more performance testing this evening with somewhat inconclusive results. The Bridgewater-Brunel saved game from December 2019 (game year 2003) seems to report similar fast forward speeds and framerates with multi-threaded route processing both on and off, although the fast forward speeds always seem to be slightly higher shortly after loading a saved game than otherwise. On the Stephenson-Seimens saved game (game year 1987), the framerate and fast forward speeds remain respectable with the single threaded route processing no matter how much time has elapsed.

With the Pak.256 saved game, I notice that this is an older saved game that contains records of routes to individual city buildings, the creation of which I prevented a few days ago. This may well affect performance by very significantly increasing hashtable sizes on the road tiles.

I have not been able to reproduce the error with the saved game data after I pushed the fix for this described above.

Qayyum - are you referring to all the destinations being stored in a single hashtable on each road tile? I did wonder about this, but I am not sure whether splitting them into different hashtalbes is likely to help, nor into what different hashtables to split them.

It would be very helpful if anyone could attempt comparisons with and without the multi-threaded route processing. Also, if anyone can produce a reliable reproduction case for the reported saved game issue (with loading and saving in the latest commit on this branch), that would be very helpful.

Thank you again all for testing - this has been most useful.

Jamespetts - I thought I am thinking, when me see the new system, as comprising of a list of destinatinns from where to where, ALL in one SINGLELIST. For two-way rpads, two entries of destination, and one-way road, one entry of destination. Entry of destination means entry of destinations. I would like to keep the routing of private car operation in one thread, akin to one person being the leader of public road system

Quote from: Qayyum on February 08, 2020, 04:46:30 AM
Jamespetts - I thought I am thinking, when me see the new system, as comprising of a list of destinatinns from where to where, ALL in one SINGLELIST. For two-way rpads, two entries of destination, and one-way road, one entry of destination. Entry of destination means entry of destinations. I would like to keep the routing of private car operation in one thread, akin to one person being the leader of public road system

Is your suggestion to have one hashtable per direction? It is difficult to see how this would help; road tiles have a maximum of four directions (for a crossroads), so private cars would have to check each one.

As to putting private car routing operations in a single thread, again, it is difficult to see how this would help; there is very little that actually processing the routes can be concurrent with. Unlike finding the routes, processing the routes cannot be concurrent with sync_step.

I could reload the deta which is saved in single-threaded version.
I show the compatibility table between the single- and multi-threaded versions.

save -> load
single -> single: OK
single -> multi: OK
multi -> single: failed
multi -> multi: failed

This means something wrong in the multi-threadead version when saving the game data.

Splendid, that is helpful - thank you.

More research has found the immediate, but not the ultimate, cause of this saved game corruption. What appears to happen is that, somehow, the individual threads get out of sync with the barrier waits and multiple different routes end up being processed at once. This, in turn, causes race conditions at individual road tiles, causing corrupt hashtables, which in turn corrupt the save data when the game is saved.

It is not clear whether it is worth fixing this, since testing has not shown any clear performance advantage to this, since adding data to the hashtables, the most CPU-intensive task in the route processing, is in any event forced to be effectively single threaded by the freelist mutex.

I have now separated the preprocessor definition for the main multi-threading of the processing with the preprocessor definition (#defined in the code) used for making the route processing run concurrently with the passenger generation code, which might well allow this to run slightly more efficiently than running entirely singly at least.

I think that this feature is now ready for inclusion - if anyone thinks that there are any major problems to resolve before I include it, please let me know before this evening. Thank you again for all your testing and feedback. I shall look forward to seeing bypasses and motorways in all the online games!

I tested the latest version for a short time. The result is very well. It always keeps ~30 fps, and the CPU usage is less than 7 percents. Reloading the multi-threaded save data works correctly, too. QUITE stable!!!

Thank you very much for testing. I have pushed another performance improvement - instead of using multi-threading, this limits the number of routes in every city processed per step to 8 (by default: this can be changed in simuconf.tab), spreading the workload between steps.

Hopefully, this will address the performance issue reported by Matthew. I should be grateful if people could re-test.

Quote from: jamespetts on February 05, 2020, 12:37:13 AM
Splendid, thank you: I have now had a chance to look at this. A performance profiler suggests that ~8% of CPU time is being spent on processing private car routes in this map, of which ~4% is on clearing existing private car routes before processing

James, thank you for your continued work on this, especially since so much of it is for the benefit of low-spec gamers like me. It's frustrating that multi-threading has turned out to be a dead end. However, that effort wasn't totally in vain: it has taught me the importance of performance profilers to make sure I'm not just imagining a problem. I have spent several hours learning to use a performance profiler on Linux (including dead ends of my own - there is a severe lack of comprehensible tutorials) so hopefully I can give more helpful replies in future.

I have tested the latest patch (commit #035705f; 1960; pak128.Britain-Ex) and it is like night and day compared to some earlier versions of this branch! Frameskips have completely disappeared and I get a steady 30fps for the first 10 mins of a game, at least. However, there is an oddity:

(http://i.imgur.com/yQL13Sm.png)

I don't seem to be getting any passengers at all....? No visitors at all for sports stadia seems particularly odd. Perhaps this will clear itself as I play on though.

QuoteI should be interested to hear from other people as to the performance with Matthew's 1960 era map; this would be most useful in determining the significance of this issue. I also notice that Matthew's computer is rather limited in RAM - this saved game alone when running takes ~1.2Gb of RAM, which is a significant proportion of 4GB. If Matthew were running low on RAM, this would potentially impact performance significantly.

One other thing to note is that one can set "assume_everywhere_connected_by_road" to disable private car route searching entirely, which will reduce any performance impact.

Though it was a good guess, I don't think I am memory-limited, as this top report shows:

(http://i.imgur.com/V05oq11.png)

Sim-Ex is only using 1.5 GB and even my biggest games are <2GB so far. I've never been able to see Bridgewater-Brunel because of its size, but I think the issue with this branch is was CPU, as far as I can tell.

I found very wierd behavior:
https://cdn.discordapp.com/attachments/665986412641779712/675780704067649569/Simutrans_120.2.1_Extended_Nightly_development_build_14.9_035705f_2020-02-09_04-08-42.mp4 (https://cdn.discordapp.com/attachments/665986412641779712/675780704067649569/Simutrans_120.2.1_Extended_Nightly_development_build_14.9_035705f_2020-02-09_04-08-42.mp4)
This issue happened at the edge of the city. Probably it is similar behavior as I have already reported about oneway motorway. And, as you can see in the video, this may finally causes a small dead lock.

Thank you both for your feedback: that is very helpful. Matthew - I cannot reproduce any reduction in passenger traffic. When I run the saved game from the Stephenson-Seimens server, Freahk's company's passenger numbers increase.

Phystam - it is likely to be difficult to debug that issue without a reproduction case. However, this is probably marginal enough not to prevent it from being worthwhile merging this now, so this will be in to-morrow's nightly build.

Thank you to everyone who has tested this so far: this is most helpful.

EDIT: As the private-car-routing is now included in the nightly, I have tried the Bridgewater-Brunel executable and confirmed that I've somehow failed to compile the game properly  :-[ :-[ :-[ :-[ Apologies for the unintentionally unhelpful report about passenger generation.

Quote from: jamespetts on February 08, 2020, 07:56:22 PM
Thank you both for your feedback: that is very helpful. Matthew - I cannot reproduce any reduction in passenger traffic. When I run the saved game from the Stephenson-Seimens server, Freahk's company's passenger numbers increase.

I can't access the Stephenson-Siemens game due to the ongoing pakset mismatch issue. But I've tested this for another couple of hours and I still get very odd passenger generation in this branch. When I generate new maps, I get no passengers at all. On old maps (from master), passenger numbers fall off a cliff:

(http://i.imgur.com/hCgSFtV.png)

I think it's fairly obvious when I switched the game to the this branch.  :D

Almost all omnibus lines are at or just above 0% occupancy. There are a few passengers appearing at stops, but I wonder how many of them have walked from other stops as part of a longer route, rather than starting a new journey. I can't explain why this is happening though. perf shows that generate_passengers_or_mail is running.

But it's very, very possible


(though the source code appears to be correct (https://github.com/jamespetts/simutrans-extended/compare/private-car-routing-lightweight...MatthewForrester:private-car-routing-2)).

Quote from: Matthew on February 09, 2020, 08:00:59 AMI can't access the Stephenson-Siemens game due to the ongoing pakset mismatch issue.

Indeed an ongoing issue :/
You can access it loading the "save" net:list.extended.simutrans.org

First of all I wanted to say that this is a truly epic improvement. Thank you James and everyonee who contributed.
I have a few questions:
1. Do cars use attractions and industry outside cities as spawning point and destination?
2. If they do how far can the road be from the attraction/industry?
3. Do you need a stop for the attraction/industry to generate and accept private cars?
Also I noticed that cars do not want to route through wooden bridges over deep water.

Quote from: killwater on February 18, 2020, 09:32:05 PM
First of all I wanted to say that this is a truly epic improvement. Thank you James and everyonee who contributed.
I have a few questions:
1. Do cars use attractions and industry outside cities as spawning point and destination?

Private cars certainly use these as destinations. They should also use them as spawn points for the return journies, but I have not seen this happening (the code for the generation of private cars has not changed - only the code for where they go once they have been generated).

Quote
2. If they do how far can the road be from the attraction/industry?

The road needs to be immediately adjacent to the spawn tile, which, if I recall correctly, is the North-West corner.

Quote
3. Do you need a stop for the attraction/industry to generate and accept private cars?

No - private cars are entirely independent of player stops.

Quote
Also I noticed that cars do not want to route through wooden bridges over deep water.

On the face of it, this is odd as there is no means of testing when a car is about to drive over the bridge whether it is over deep water or not. If you are able to test and confirm this (and specifically that it is confined (1) to wooden bridges; and (2) that are over deep water), then I should be grateful if you could post a full bug report with a reproduction case.

James,
It seems like there has been no traffic generated between cities at this time. Now private cars go over the bridge without problems.

Good day,

I wanted to start new map of current year 2020.
And build Motorways to see if this can work out financially.

But its seems that my new motorway cannot compete with existing public road.
Most of private car journeys are still done via public road not my motorway.

You can see traffic heat map red on those public road and green on my new motorways.

Is there any advice, I don't understand fully how a private car decide which route it takes.
I don't want to delete existing public road by chaining to public player, since its not realistic.

(https://i.imgur.com/CbcEblI.png)
(https://i.imgur.com/ocQzwys.png)
(https://i.imgur.com/OFVOvco.png)

Especially this intersection is little bit strange,
Grey was public route, and I have built roundabout on it using oneway tool.
Pink route from public road arriving in to the town, there is always traffic but,
Blue routes going to other town form the town, there is no traffic.

(https://i.imgur.com/4CpR18L.png)

Your Motorways are rather a detour than a shortcut due to being more curvy than those country roads and those huge roundabouts cause further detours.
Make sure your motorways are a shortcut in a larger scale. Connections in between adjacent towns should not be the job of your motorways, except for rather few cases.

And another hint: roundabouts are fine to handle intersecting bidirectional roads, but usually don't want them on motorways. At least not im Simutrans.
They will bottleneck your motorways in very many cases.
You should prefer motorway junctions instead, although I usually don't build a complete motorway junction connecting all possible directions. I just branch out and merge in before and after towns, so cars can leave the motorway without crossing the opposite direction and the majority of cars can stay  straight on the motorway.

Edit: See the attachment for an example. After the second merge in, there are roughly 2500 cars per month on the motorway (red section)
The orange lines around that are roughly 1200 cars, the green and light yellow lines are rails.

That kind of simple merging and branching is the most common type of motorway exists on that map, although there are also some "usual" exits consisting of one ramp per direction connected to a bidirectional road.
Such exists are fine when there are not many cars leaving the motorway.
If you like roundabouts, you can build a roundabout above or underneath the motorway, connecting the crossing bidirectional roads to it and building ramps to enter or leave the motorway.

If the original roads are congested enough, cars should start using your motorways after a few months have passed. How many have passed in your case, and how congested (i.e. the congestion % in the road tile info) are they?

Whilst true in principle, relying on that will cause the motorway to be used unfrequently, as it's only considered as an alternative once the country roads are congested. Once congestion reset, the cycle starts again.

Also, how big is your map? If you have a large number of towns connected by road, it can take a long time for the private car routing system to recalculate the routes and therefore for the cars to know about your motorway.

The time that it takes increases exponentially with the number of towns connected by road.