News:

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

Large City Private Car Routing

Started by PJMack, June 14, 2021, 01:27:28 AM

Previous topic - Next topic

0 Members and 1 Guest are viewing this topic.

PJMack

Private cars that are in the origin or destination city currently drive around randomly until they find the destination or a known route to the destination.  This works well for small to medium sized cities, however from my observations, does not scale to larger cities, and results in cars going in circles.  One solution that I could come up with is to have private cars do convoi type routing in limited circumstances within the boundaries of a city.  Such routing could be compressed; since private cars would not need to know the exact speed limits and conditions of roads ahead, an individual private car route could consist of a simple vector of two bit values indicating the cardinal directions for each tile.  If a maximum of 256 tiles were set, each private car would have a maximum of 73 added bytes, and 9 bytes of overhead.  Assuming 4 Million private cars on the roads (~40 Million cars in UK, most parked 90% of the time) this would only add 300MB of memory maximum, with 36MB overhead.  Rather than having all cars immediately find a route, it would also be possible to have them detect going in circles by recording their 2D position ever N hops, and checking there position each hop to see if it matches.  This would add 4 bytes of overhead per car.  The existing routing algorithm could be used with and additional flag for remaining in the city (though at this point it probably could be turned into a function template which would be faster than the function pointers, but that is another matter).

Another solution would be, to divide the larger cities into "boroughs" and have private car routes embedded into the roads between the boroughs as they are between cities on the large map.  Boroughs with attractions could be configured to have their centers be on the attraction to save resources.  As a project for redoing city formation is planned, this may best wait to be part of such project.

freddyhayward

Though I don't know how, it might be useful to optimise for the fact that cars only need to come within a certain distance of their destination to reach it. If a borough or any subdivision has a diagonal length smaller than than distance, then a car entering that subdivision will have immediately reached any destinations within.

jamespetts

The real issue with any more sophisticated private car routing is not just memory consumption, but memory bandwidth and processing intensity. If you can find a way of achieving at least partial actual routing in larger towns for private cars within reasonable parameters of performance with even huge maps (have a look at the very large map currently being run by the Japanese Simutrans community with Pak128.Britain-Ex, for instance), then this would definitely be an achievement, although it would, I anticipate, be a considerable challenge.
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

Did you even count the actual cars on a map?

Asuume 8000*8000 map. 5% of tiles are road tiles. (Essentially half covered by towns.) This are 3.2 million tiles. Assume heavy traffic, so 10% or all tiles are occupied with cars (this would already lead to total deadlock for sure) then 320000 cars as maximum number.

Assume a travel takes 1 month on average to arrive (unlikely with this heavy travel on such a large map) at bitshift 21, (i.e. 2^21 ms per month) this would require generating one car every 7 ms. That would be too much for any system. Hence, the actual generation speed is probably much lower.

So there are more likely less than 100000 cars on the map with generation rate of 1 car per second or less. (Statistics from past maps could tell more.)

I such a case the normal routing (especially if threaded) may also handle this, since at the same time car handled like convois would require much less processing when they move since their route is local in memory to them.

ampersand

Quote from: PJMack on June 14, 2021, 01:27:28 AMdivide the larger cities into "boroughs" and have private car routes embedded into the roads between the boroughs as they are between cities
code globally route locally

jamespetts

I had not actually tried to count the cars, but some years ago, I did try to make private cars route in the same way as player convoys, and the game became totally unresponsive. In Extended, the routing needs to be done, not just for the actual cars generated, but for all the thousands of alternative destinations for each passenger, as the initial route (or first few thousand routes) found to possible destinations may not be within the passengers' journey time tolerance.

In relation to boroughs, it is planned, when the planned city growth features be implemented, that cities that grow into other cities will absorb those other cities, and that the larger cities will become metropolitan areas and the smaller cities boroughs.
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

Ships have a regional pathfinder (although there are much more water than road tiles). One could certainly envision something like this for cars too.

jamespetts

Quote from: prissi on June 15, 2021, 02:38:43 PM
Ships have a regional pathfinder (although there are much more water than road tiles). One could certainly envision something like this for cars too.

That is an interesting thought. I imagine that it would take a great deal of coding work, but, if somebody could make it work, it might possibly be quite effective.
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

For ways the pathfinder could just add all tiles until the next crossing if it goes in that directions (unless it arrives at the destination already) as a single node. That bypasses a lot of checks, map lookups and extra nodes to be added to the lists.


PJMack

Quote from: prissi on June 16, 2021, 06:16:27 AMFor ways the pathfinder could just add all tiles until the next crossing if it goes in that directions (unless it arrives at the destination already) as a single node. That bypasses a lot of checks, map lookups and extra nodes to be added to the lists.
For individual vehicles, I can see that as a possibility as long as diagonal roads are handled properly.  I had considered something remotely similar when doing the compression pull request, however my concern with that was how to handle diagonal roads and the addition or removal of intersections.  (Also, for that particular pull request, I was trying to minimize effect on game behavior).


Quote from: jamespetts on June 15, 2021, 10:51:55 AMI had not actually tried to count the cars, but some years ago, I did try to make private cars route in the same way as player convoys, and the game became totally unresponsive. In Extended, the routing needs to be done, not just for the actual cars generated, but for all the thousands of alternative destinations for each passenger, as the initial route (or first few thousand routes) found to possible destinations may not be within the passengers' journey time tolerance.
I had originally thought for the individual private car routing to begin after determining a destination, either when spawning in a large city (where it would only route to where the existing system can take over), or when entering a large destination city (where it would only look for routes within the city itself).  Alternatively, the existing system of random cars would persist until the cars take too long to reach their destination or if computing resources allow, detect going around in circles, where at that point the cars would stop and ask for directions.  Although the thought never actually occurred to me, I do agree that using individual private car route times for choosing destinations is not feasible.
Quote from: jamespetts on June 15, 2021, 10:51:55 AMIn relation to boroughs, it is planned, when the planned city growth features be implemented, that cities that grow into other cities will absorb those other cities, and that the larger cities will become metropolitan areas and the smaller cities boroughs.
If the boroughs are small enough (maybe 32x32) and ensured to be a continuous land mass, inter-borough routing the same way inter-city routing is currently done, then the random behavior the origin and destination areas may be acceptable.  For finding routes from and from boroughs, what may be best is to only calculate to destinations within a radius equal to the diameter of the metropolitan area (or some multiple thereof).  This would mean that private cars would need to look for routes to either the metro area or the borough. This would be simpler than trying to compress routeing information.


Unfortunately, due to some unplanned occurrences, I have not had much time for simutrans coding lately.  I did attempt to make the find_route function into a template to avoid virtual calls, which had no measurable effect on performance, hence no pull request.  As I do not for-see being able to do much additional coding (debugging, analysis, etc) in the near future, so this may have to wait to be part of the planned city growth features.