Fast pathfinder mode for finding viable route

[originalfoo]

Issue Summary:

Can A reach B

Where:

• A = building or vehicle (source)
• B = destination

Super quick test to verify if source can reach destination.

It would be useful if there was a pathfinder mode (or alternate) designed to quickly check if a route between A and B is viable.

This would skip as many checks as possible - for example, it wouldn't worry about toll booths, speed limits, costs or other minor details. The primary aim would be to determine, as quickly as possible, if a vehicle of certain type can viably travel between point A and point B.

Example use cases:

• Finding a viable taxi service - see When taxis are not able to reach their destination they should not despawn #143
• Route checker tool - see Route builder / tester #341

[kvakvs]

Related to Pathfinder
Thinking of some bi-directional A*, which is essentially a generalized Dijkstra which searches from both ends until the searches meet
https://ijcsmc.com/docs/papers/July2015/V4I7201599a23.pdf
https://arxiv.org/ftp/arxiv/papers/1810/1810.01776.pdf
A* in general is also faster and works better when we account for the road situation (vehicles per lanes) and obstacles (like roads or whole districts blocked with traffic) which will encourage pathfinder to try alternate directions.

[kvakvs]

Here's one idea on improving the pathfinding by splitting the world into well connected sectors (call them clusters or something), and establishing multiple known routes between them. And then the C:S pathfinder will only need to find a quick path between these sectors to begin moving the car or a pedestrian, and can then clarify the route by doing a regular pathfinding algorithm on smaller parts of the route.
Typically people build cities which are clusters of something separated by a few roads or bridges. But i am sure a good clustering algorithm should even find clusters in a city consisting of a grid
As pedestrians take a LOT of CPU time, they could use this improvement to save CPU cycles

Each cluster to each cluster would be a N² paths cache. For how many types of traffic we have, there will be so many paths cached (because local policies, road restrictions etc). If the map changes, the paths have to be invalidated in the affected regions, and periodically clusters also have to be re-validated or recalculated if connecting roads were added or removed.

[originalfoo]

Yes, I've had this idea of caching paths before but Victor said it was not possible at the time but I do not know why.

I was thinking one simple way to cluster would be districts, which seem widely used by most users and would be simple starting point as we wouldn't have to determine the clusters ourselves. @krzychu124 found that there's a 'district grid' so you can quickly determine if a building is in a district.

But the primary reasoning for this issue #357 was to better choose candidates for "job offers" (or whatever they are called) as explained in OP. It's not so much about making main pathfinder itself faster (although there would be no harm in doing so, and it would be advantageous late game) but about ensuring the chosen service building/vehicle can actually get to destination and hopefully prevent the dreaded "service vehicle count fickering" issue we see so often. It could then be extended to identify when none of the available services can reach a building and flag that issue to the user or at least enable the service encountering that problem to skip such requests and thus continue functioning for other requests.

[originalfoo]

Just copying my comments over from Discord chat:

Another thing we could look for is distance to target and then order by route 'size' (eg. faster / bigger roads such as highways could be checked first EDIT: for long journeys)

Also, I think we should certainly be doing (or attempting to) some caching on highways in relation to outside connections

That being said, my brain fries and scampers out my ear every time I look at pathfinder code

I was trying to work out how the "Old Town" policy gets handled a few days back and literally could not work out what was going on, even in the IDE with viewing definitions of everything it still made no sense. Perhaps my brain is just getting to senile to code