Road transport - pathfinder doesn't see traffic on the roads, which intensifies existing traffic jams

[LC-Zorg]

Version of OpenTTD

14.0-RC2 - old problem

Expected result

Pathfinder sees busy roads and takes them into account when calculating the route. The status update doesn't have to be very frequent (traffic jams are "realistic"), but it would be nice if the game took into account what is happening on the roads and did not direct all vehicles to one road.

Actual result

Pathfinder doesn't see traffic jams and even if an alternative route is 1% longer, it never takes it into account. This often leads to quite bizarre situations when, with a large network of available roads, pathfinder directs all vehicles to where there is the biggest traffic jam. This is especially visible in the case of connections created by AAAHogAI (screenshot below), which creates far too many roads, but even this doesn't help to avoid congestion.

And another example where pathfinder could choose one of the slightly longer roads (it has 9 to choose from), but it doesn't do this and directs all vehicles to one of them.

Steps to reproduce

Below are two saves for both of the above screenshots.
Road transport - pathfinder problem.zip

[zacc]

I have experienced this problem too.
Lately I have been working on the road pathfinder code trying to fix a problem with how the pathfinder interprets the occupied level of a station. But amongst working on that I have experimented with a few pathfinder penalty/code changes to re-route around busy roads. I have successfully done it, but on my test scenario I found that profit dropped because vehicles would take a bit longer to reach the destination. In the game shares you saved it might be more successful because of the chronic gridlock!

In the current pathfinder code the only 'dynamic' route differentiator is the destination station occupied level. Everything else is a 'static' differentiator - like the road slope, if the road has a train crossing, etc. That means that the pathfinder will basically always take the optimal route and only vary when it gets close to the destination station. I think there is a lot of room for improvement.

One of the things I have noticed is that many players play for different reasons - some people like to make profit, some like realism (as in, road vehicles always follow the same road routes like in real life), etc. Looking at the github commit history, this road pathfinder code hasn't changed for years. Making a change to the core gameplay behaviour that has been the same for years, might be hard to effect. On the other hand, road vehicles are less popular than trains so maybe we can.

Another addition that will be useful for road vehicles are waypoints but an AI model might find them hard to use.

I can share with you a version of OpenTTD with the change for busy roads that I mentioned above and you can trial it with your AI model.

[TheMowgliMan]

@zacc It's neither realistic nor efficient to check regularly. In the real world, before GPS, people only rerouted away from traffic if they could guess that it would be busy, such as assuming a city center would be busy at rush hour, or if they had a good view and could see traffic or a roadblock (e.g. broken down/destroyed vehicle or a train on a crossing). Nowadays, GPS routers still only reroute occasionally and during high levels of road congestion. Rerouting only every 5-30 seconds would be completely appropriate.

[zacc]

@TheMowgliMan I agree. One issue is that the route is cached when it's created (ie when vehicle leaves the station) and not re-evaulated until the last 8 tiles before the destination. So the vehicle can't re-evaulate itself along the route (at least in its current implementation).
Ideally the pathfinder algorithm needs to know at the start on which tiles to check for vehicles or not.

I experimented with checking the tile busy-ness for only the first few segments of a route which works around busy stations, but it fails to catch scenarios/layouts where vehicles on different timetables all converge on a single road between areas of the map and create grid-lock there.

The two saved games that the OP provided are good examples of both of these scenarios. One save (top screenshot) contains multiple companies all competing at the same industry so significant gridlock around clustered stations with under-utilized roads between. The other save (bottom screenshot) has under-utilized stations and a single highway/spine that is grid-locked.

So the theory I am working on now is that the pathfinder definitely does need to check busy-ness across the entire route to handle all kinds of network layouts. And due to the caching of the route it shouldn't respond to minutia that might change by the time the vehicle reaches it eg like a level crossing. Nor can it check every single tile for CPU reasons. It just needs a good overview of busy-ness in each segment of the route. 💯

[TheMowgliMan]

@zacc Perhaps try routing only some number of tiles down the route, maybe, say, 10?

[Kuhnovic]

This is just a brainfart, but it's something I have seen pop up in pathfinding articles. You could create a heat map that records how much traffic has traveled over a certain tile / segment / something. That would give you a general number on how busy certain roads are, instead of having to check for the presence of individual vehicles, which indeed can get expensive.

You could reserve a few bits per tile for the amount of "heat", and increase the heat value each time a vehicle enters it. You can then use the general tile loop to slowly cool the tiles down again, although the behavior will be a bit pseudo random.

You might already be doing something like this, I just wanted to share my thoughts.

[zacc]

@TheMowgliMan in the code it would be easy to look at the first x tiles in a segment but it'd be a bit biased sample of each segment. (A segment is from intersection to intersection).
@Kuhnovic that's a great idea. I am not using anything that complex now - quite the opposite! I haven't worked on the tile loop at all but I'll have a look. Could this be something implemented for all types of vehicles, perhaps? Could be useful for trains but maybe not so much for ships that don't collide.

[PeterN]

@TheMowgliMan I agree. One issue is that the route is cached when it's created (ie when vehicle leaves the station) and not re-evaulated until the last 8 tiles before the destination. So the vehicle can't re-evaulate itself along the route (at least in its current implementation). Ideally the pathfinder algorithm needs to know at the start on which tiles to check for vehicles or not.

In fact only 8 "segments" are cached, not the whole route. But a segment is one "junction tile" to the next "junction tile", so a long straight roads is only 1 segment. Maybe a length limit would help too.

[zacc]

@PeterN thanks for the clarification! I had been debugging on a small map with fewer than 8 segments.

[LC-Zorg]

You could create a heat map that records how much traffic has traveled over a certain tile / segment / something

This is a solution close to what I originally thought of. I don't know how pathfinder works and I'm generally a visual learner, so something like this appeals to me. :) Updates of such a map do not have to be frequent, because it is mainly about outline, general information about which roads to avoid to avoid absurd accumulations of traffic jams. It doesn't have to be super effective, but it's important that it doesn't increase the load on the game. In any case, it seems to me that a vehicle that is standing should be more noticeable on such a "map" than one that is moving.

@zacc This is probably a different solution than the target one (?), but I'd still like to see how it works. :) If you have the Windows version, I'd be happy to test it. :)

[zacc]

I'm a long way from being able to do a heat map like that. I looked into the "vehicle enters tile" event , but vehicles that are grid-locked and stay on the tile for several game days will not trigger the event on and off as frequently as vehicles that are moving through the tile so I am not sure that this is an accurate metric to use.

Alternatively the current branch I am working with just checks for multiple vehicles on the end node of a YAPF segment and applies a penalty. Blockages tend to occur at road intersections so it's only necessary to check on this kind of intersection. It does work quite well however increases the processing time a bit, probably not acceptable to reach master branch but good enough to experiment with on your own build. @LC-Zorg I am on Linux so I can't build for Windows but I can push my branch for you if you think you can build it yourself?

[LC-Zorg]

I'm a long way from being able to do a heat map like that. I looked into the "vehicle enters tile" event , but vehicles that are grid-locked and stay on the tile for several game days will not trigger the event on and off as frequently as vehicles that are moving through the tile so I am not sure that this is an accurate metric to use.

I will say this, the initial thought that it was possible came from observing the map with the vehicle view. I don't know how it works, but it's just visible and could perhaps be included by pathfinder. The only problem is that roads have at least 2 or 4 directions and each should be considered separately.

I don't know if this is helpful. :)

I am on Linux so I can't build for Windows but I can push my branch for you if you think you can build it yourself?

I'm not a programmer. The only thing I have managed to create so far is a simple reinterpretation of one of the scripts (RWD), so compiling the game is probably beyond my reach.