News:

Simutrans.com Portal
Our Simutrans site. You can find everything about Simutrans from here.

Lightweight private car routing

Started by jamespetts, January 13, 2020, 12:10:27 PM

Previous topic - Next topic

0 Members and 1 Guest are viewing this topic.

jamespetts

There has been a long-standing plan, documented in the development projects thread 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 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, 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.
Download Simutrans-Extended.

Want to help with development? See here for things to do for coding, and here for information on how to make graphics/objects.

Follow Simutrans-Extended on Facebook.

Qayyum

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

Simutrans - the open source Transport Tycoon Deluxe clone.

prissi

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

jamespetts

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.
Download Simutrans-Extended.

Want to help with development? See here for things to do for coding, and here for information on how to make graphics/objects.

Follow Simutrans-Extended on Facebook.

prissi

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.

jamespetts

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?
Download Simutrans-Extended.

Want to help with development? See here for things to do for coding, and here for information on how to make graphics/objects.

Follow Simutrans-Extended on Facebook.

prissi

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.

Octavius

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.

prissi

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.

Qayyum

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)?
ALLMYCONTENTISPUBLICDOMAINBUTNOEXPLOITATION

Simutrans - the open source Transport Tycoon Deluxe clone.

jamespetts

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.
Download Simutrans-Extended.

Want to help with development? See here for things to do for coding, and here for information on how to make graphics/objects.

Follow Simutrans-Extended on Facebook.

Mariculous

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)

jamespetts

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?
Download Simutrans-Extended.

Want to help with development? See here for things to do for coding, and here for information on how to make graphics/objects.

Follow Simutrans-Extended on Facebook.

Mariculous

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.

Matthew

I can't comment on the algorithm, but I like your comic story, Freahk!  ;D
(Signature being tested) If you enjoy playing Simutrans, then you might also enjoy watching Japan Railway Journal
Available in English and simplified Chinese
如果您喜欢玩Simutrans的话,那么说不定就想看《日本铁路之旅》(英语也有简体中文字幕)。

Mariculous

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.

jamespetts

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.
Download Simutrans-Extended.

Want to help with development? See here for things to do for coding, and here for information on how to make graphics/objects.

Follow Simutrans-Extended on Facebook.

Phystam

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.

jamespetts

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.
Download Simutrans-Extended.

Want to help with development? See here for things to do for coding, and here for information on how to make graphics/objects.

Follow Simutrans-Extended on Facebook.

Mariculous

#19
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.



jamespetts

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.
Download Simutrans-Extended.

Want to help with development? See here for things to do for coding, and here for information on how to make graphics/objects.

Follow Simutrans-Extended on Facebook.

Mariculous

#21
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.

jamespetts

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.
Download Simutrans-Extended.

Want to help with development? See here for things to do for coding, and here for information on how to make graphics/objects.

Follow Simutrans-Extended on Facebook.

Qayyum

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
ALLMYCONTENTISPUBLICDOMAINBUTNOEXPLOITATION

Simutrans - the open source Transport Tycoon Deluxe clone.

Phystam

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

freddyhayward

#25
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.

jamespetts

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.
Download Simutrans-Extended.

Want to help with development? See here for things to do for coding, and here for information on how to make graphics/objects.

Follow Simutrans-Extended on Facebook.

Mariculous

#27
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.

jamespetts

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.
Download Simutrans-Extended.

Want to help with development? See here for things to do for coding, and here for information on how to make graphics/objects.

Follow Simutrans-Extended on Facebook.

Mariculous

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.

jamespetts

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.
Download Simutrans-Extended.

Want to help with development? See here for things to do for coding, and here for information on how to make graphics/objects.

Follow Simutrans-Extended on Facebook.

Matthew

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
(Signature being tested) If you enjoy playing Simutrans, then you might also enjoy watching Japan Railway Journal
Available in English and simplified Chinese
如果您喜欢玩Simutrans的话,那么说不定就想看《日本铁路之旅》(英语也有简体中文字幕)。

freddyhayward

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.

jamespetts

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.
Download Simutrans-Extended.

Want to help with development? See here for things to do for coding, and here for information on how to make graphics/objects.

Follow Simutrans-Extended on Facebook.

Phystam

#34
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.