The International Simutrans Forum

 

Author Topic: Lightweight private car routing  (Read 468 times)

0 Members and 1 Guest are viewing this topic.

Offline jamespetts gb

  • Simutrans-Extended project coordinator
  • Moderator
  • *
  • Posts: 19078
  • Cake baker
    • Bridgewater-Brunel
  • Languages: EN
Lightweight private car routing
« on: January 13, 2020, 12:10:27 PM »
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.

Offline Qayyum

  • *
  • Posts: 148
Re: Lightweight private car routing
« Reply #1 on: January 13, 2020, 12:45:38 PM »
Jamespetts, private cars coming from several cark parks would be beneficial?

Offline prissi

  • Developer
  • Administrator
  • *
  • Posts: 9631
  • Languages: De,EN,JP
Re: Lightweight private car routing
« Reply #2 on: January 13, 2020, 01:11:02 PM »
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).

Offline jamespetts gb

  • Simutrans-Extended project coordinator
  • Moderator
  • *
  • Posts: 19078
  • Cake baker
    • Bridgewater-Brunel
  • Languages: EN
Re: Lightweight private car routing
« Reply #3 on: January 13, 2020, 01:17:42 PM »
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.

Offline prissi

  • Developer
  • Administrator
  • *
  • Posts: 9631
  • Languages: De,EN,JP
Re: Lightweight private car routing
« Reply #4 on: January 13, 2020, 02:11:27 PM »
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.

Offline jamespetts gb

  • Simutrans-Extended project coordinator
  • Moderator
  • *
  • Posts: 19078
  • Cake baker
    • Bridgewater-Brunel
  • Languages: EN
Re: Lightweight private car routing
« Reply #5 on: January 13, 2020, 02:17:24 PM »
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?

Offline prissi

  • Developer
  • Administrator
  • *
  • Posts: 9631
  • Languages: De,EN,JP
Re: Lightweight private car routing
« Reply #6 on: January 13, 2020, 02:43:45 PM »
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.

Offline Octavius

  • *
  • Posts: 49
  • Languages: EN,NL,DE
Re: Lightweight private car routing
« Reply #7 on: January 14, 2020, 11:36:59 AM »
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.

Offline prissi

  • Developer
  • Administrator
  • *
  • Posts: 9631
  • Languages: De,EN,JP
Re: Lightweight private car routing
« Reply #8 on: January 14, 2020, 02:17:07 PM »
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.

Offline Qayyum

  • *
  • Posts: 148
Re: Lightweight private car routing
« Reply #9 on: January 14, 2020, 07:22:26 PM »
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)?

Offline jamespetts gb

  • Simutrans-Extended project coordinator
  • Moderator
  • *
  • Posts: 19078
  • Cake baker
    • Bridgewater-Brunel
  • Languages: EN
Re: Lightweight private car routing
« Reply #10 on: January 14, 2020, 09:54:35 PM »
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.

Offline Freahk

  • *
  • Posts: 422
  • Languages: DE, EN
Re: Lightweight private car routing
« Reply #11 on: January 14, 2020, 10:43:42 PM »
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.

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


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

Offline jamespetts gb

  • Simutrans-Extended project coordinator
  • Moderator
  • *
  • Posts: 19078
  • Cake baker
    • Bridgewater-Brunel
  • Languages: EN
Re: Lightweight private car routing
« Reply #12 on: January 15, 2020, 12:40:41 AM »
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?

Offline Freahk

  • *
  • Posts: 422
  • Languages: DE, EN
Re: Lightweight private car routing
« Reply #13 on: January 15, 2020, 01:02:03 AM »
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.

Offline Matthew gb

  • *
  • Posts: 260
    • Japan Railway Journal
  • Languages: EN, some ZH, DE & SQ
Re: Lightweight private car routing
« Reply #14 on: January 15, 2020, 10:13:38 AM »
I can't comment on the algorithm, but I like your comic story, Freahk!  ;D

Offline Freahk

  • *
  • Posts: 422
  • Languages: DE, EN
Re: Lightweight private car routing
« Reply #15 on: January 16, 2020, 12:23:57 AM »
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.

Offline jamespetts gb

  • Simutrans-Extended project coordinator
  • Moderator
  • *
  • Posts: 19078
  • Cake baker
    • Bridgewater-Brunel
  • Languages: EN
Re: Lightweight private car routing
« Reply #16 on: January 16, 2020, 01:07:13 AM »
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.

Offline Phystam jp

  • *
  • Posts: 312
  • Pak256.Ex developer
    • Pak256 wiki page
  • Languages: JP, EN, EO
Re: Lightweight private car routing
« Reply #17 on: January 16, 2020, 01:26:41 AM »
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.

Offline jamespetts gb

  • Simutrans-Extended project coordinator
  • Moderator
  • *
  • Posts: 19078
  • Cake baker
    • Bridgewater-Brunel
  • Languages: EN
Re: Lightweight private car routing
« Reply #18 on: January 16, 2020, 01:54:36 AM »
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.

Offline Freahk

  • *
  • Posts: 422
  • Languages: DE, EN
Re: Lightweight private car routing
« Reply #19 on: January 16, 2020, 04:14:20 PM »
Attention, yet another wall of text incoming...


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

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

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.

Quote
The 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.


« Last Edit: January 16, 2020, 04:49:52 PM by Freahk »