Cars All Choose the Same Lane Causing Congestion

[FireController1847]

Temporary solution

Set DLS to less than 50% in mod options.

---

New Issue Description

To summarize on what this issue is, as seen in the images below, cars often prefer to use one lane other than a bunch of the other open lanes leading into the same direction. My theory on what's happening? I think cars will prefer to use the shortest distance without taking into account the cars that could block their path (taking more time) resulting in vehicles all choosing the same lane.

I mean, that's pretty much it, the previous description included a lot of debate and conversation about the implications of what's needed to make this happen, but I am 99% sure this is the direction I want to steer this issue in (as it's been all over the place).

---

Previous Issue Description

This was talked about in the Discord, and I'm putting it here so we can include more people. I'll also be transferring over a lot of the discussion we had in the Discord. Images will be uploaded to the bottom of this issue and will be referenced.

Basically, the idea of this feature is that cars will calculate which lane would be the best lane to go into before entering the next segment. The way it would work is like this:

In Image 2, the blue path represents what was already calculated by the main pathfinder. This is what the car will do if all else fails. The red path represents what the car could do because of this feature. Since the lane is clear, it'd result in a better flow of traffic. Now, in Image 3, let's say the car is currently in segment 0. The pathfinder wants the car to go to segment three. It did this by choosing the middle lane. What this logic would do is it would check the other lanes within segment 1 and determine which lane is the best lane to lead the car to segment 3.

For an example of a failed case, the logic would check the bottommost lane (still referring to Image 3). The bottommost lane goes straight, meaning it wouldn't lead to segment three, therefore being an invalid path.

For an example of a success case, there's actually two situations in this image that could be successful: the bottommost turning lane and the topmost turning lane. Since they both get you to segment three, we move on to the next part of the check. We check both lanes to determine how many vehicles are in both lanes. Since the topmost turning lane has the least amount of vehicles, and it satisfies the first half of the check, the AI would switch the vehicle's path to the topmost turning lane.

As I've stated in the past for other development features (turn on red, emergency vehicle calculation), it would be unbelievably helpful to have a utility class that lists the vehicles within a segment's lane. Code wise, there's multiple situations where we would need this feature to get the vehicles in another lane. For this issue, we could use the calculation to determine how many cars were in each lane. This utility class could be updated by the cars pathfinder's themselves, and when the car is on the main path, it would update the segment (or lane) to say that it's in that lane and remove itself from the old lane. It's simple logic that wouldn't need to be done live, and would save many calculations in many features.

Due to the fact this feature overall would require live calculations, however, it's a very controversial issue and is believed to be a huge performance drag. I don't think so, especially if we implement the utility class, but I'd have to see an implementation of it to fully believe it'll cause major issues; and I mean a well made implementation, not a half-assed put together one. It's not like we haven't done this before with other features that would cause a huge performance drop -- we found utilities, better methods, and good ways to make them more performance-safe. And there's a reason we have options, it's to let the user decide which features they'd like to have on or off. If we implement option tooltips that I talked about a little bit with the devs, we could include a warning stating that it could be a performance. Or we could move some other performance-dropping features into a category stating they'll possibly drop performance. I don't think we need to do either of these personally, but some people do, so /shrug.

(Image 1 - The Issue at Hand)

(Image 2 - The Possible Path Calculations; Blue is pre-calculated, red is live-calculated)

(Image 3 - The Segments; Used for Context)

[FireController1847]

(Discord) aubergine18: It's a side-effect of people wanting cars to use all lanes; you'll often get them using lanes that aren't great (from human perspective, but look fine from AI perspective) and then switching to desired lane at node before the junction. I don't think there's much we could do about that without adding loads of extra logic which in turn would grind game to a halt. As for presets (eg. to suit different countries) I think that's long way off if we want to do it in a non-[crap] manner.

(Discord) FireController#1847: I'm confused what you mean by that. Why would the extra logic be a lot? I know this is putting it in layman's terms, but isn't the logic there essentially: "If lane is clear and goes to same spot, then use that lane instead of one with a bunch of cars in it?"

(Discord) aubergine18: Yes, but multiply that 'all that would be needed' by a few thousands of pathfinds per frame... Even tiny change causes massive lag. It would be trivial if it were max 5000 vehicles in the game, but this is not the case. Just look at some of the numbers in the Pull Request #243. For example:

The method RecalculateLaneEndRoutingData is executed twice (for start & end node) for every source lane and only the grouping of source lanes would now be performed 2 * n * n times (n may can reach up to 262144, so 2 * 262144 * 262144 = 137,438,953,472 times).

137 BILLION extra calculations just due to simple tweak. This is the problem with pathfinder in particular, even a small change can completely tank fps. Luckily it's in separate thread, but still... Imagine segments with like 24 lanes (12 in each direction; there are such roads in the workshop)... now imagine not only checking all those lanes but doing look-ahead of a few segments, and then also having to implement something so that the look-ahead doesn't just move the problem further back on the road...

(Discord) FireController#1847: Your logic is valid and your point makes sense. However, one simple tweak hasn't stopped us before, right? I mean, there's tons of different calculations done in pathfinder that were probably terribly inefficient at first and then as it got refined there's a better way to do it. Even if the best way to do it is still somewhat laggy, that's the point of making things optional. Unfortunately I am too bias in that I think TM:PE should be based more off of real-life. After all, C:S honestly does provide the best simulations for true city planning, particularly in the traffic realm.

(Discord) aubergine18: It should be based off real life, but not at expense of lagging the game to oblivion or making code impossible to maintain.

(Discord) FireController#1847: Right, but like mentioned before it shouldn't, it's somewhat basic logic?

[FireController1847]

(Discord) Xyrhenix: While the logic may be basic, the implementation stands a high probability of making the game unplayable for people using this mod on weaker computer systems. I agree that mirroring real traffic patterns and behaviours is important but not at the expense of playability, especially when it can be reasonably assumed that a lot of the people who use this mod likely have weaker-spec computers that may have difficulty running an extra 137 billion calculations. I think that merging should be possible anywhere on the road, not just at nodes, but the changes required to make that happen would probably make the game unplayable even on high-spec computers. I'm all for making the mod more realistic compared to real traffic but only if it can be reasonably expected to run on the majority of systems utilising the mod.

(Discord) FireController#1847: Hence the reason we have something called OPTIONS. Are we just forgetting those exist or...?

(Discord): Xyrhenix: How many people will enable it and then complain saying "My game slows down but I want this, fix it!" if added? I'm not against the idea in the slightest if it can be worked out.

[VictorPhilipp]

This feature is already implemented and is called Dynamic Lane Selection (DLS).
https://tmpe.viathinksoft.com/wiki/index.php?title=Dynamic_Lane_Selection

What is missing? What should be improved?

[FireController1847]

@VictorPhilipp Oh, okay, sorry about this (discussion in Discord resulted in me understanding this).

For anyone viewing this in the future, this fix is explained in the wiki, this is DLS. DLS should NOT be set to 100%, which showed the issues currently. Setting DLS to 50% fixed this issue entirely for me.

[VictorPhilipp]

One possible optimization: We might try to randomize DLS cost profiles on a per-vehicle basis. That might help with traffic flow on high (> 50%) DLS settings.

[VictorPhilipp]

I implemented a working prototype that employs vehicle-dependent DLS

[originalfoo]

If this works it will be a game changer for many people! I think most people (myself included) didn't realise the issue with >50% DLS, which seems obvious once you know about it. So this extra randomisation could remove lots of pain for many people.

Is the randomisation separate to that used for vehicle speeds? Or, put another way, could we somehow use the same random value for both vehicle speed and DLS to cut down on calculations per spawned vehicle? Possibly store the random value with the vehicle, so that anything else requiring randomisation can make use of it (eg. race conditions at junctions / traffic lights / etc)?

[VictorPhilipp]

It's the same value (VehicleState.timedRand) and it changes (randomly) every 1.-20. traversed segment (configurable via GlobalConfig.Gameplay.VehicleStepRand). One thing that I have to check: Both the vehicle speed and DLS cost scheme derived from the random value should match (higher timedRand = higher speed and more aggressive DLS).

[originalfoo]

Could the speed change be based on lane? For example, an outer lane would be slower, inner lane would be faster, so that with DLS it would appear cars speed up to overtake?

[VictorPhilipp]

That's a different topic (a.k.a. European overtaking rules) :-)