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

[FireController1847]

@VictorPhilipp That looks great! When/if you make a PR for it, I'll definitely remember to test it and report back to you.

[pcfantasy]

@VictorPhilipp

Nice, I`d like to test and report too, I often set DLS to 100%, sometimes cause congestion like the picture which @FireController1847 provided.

[FireController1847]

Unfortunately, I do not feel as if DLS Randomization is going to be the fix here. Like I stated in the comment of #334, I believe the cars are calculating the fastest distance without taking into account the amount of time it will take to get there. What I mean by this is if we were to not only calculate the shortest route but also calculate traffic conditions on the segments ahead, and determine which lane is moving fastest/has the least amount of cars, it would provide a much better implementation of DLS rather than just randomizing the lanes they're going to go into.

I wonder if the base game actually does this, or does something similar, as otherwise setting DLS to 50% wouldn't make a difference.

[originalfoo]

I wonder if the base game actually does this, or does something similar, as otherwise setting DLS to 50% wouldn't make a difference.

I think there's two separate issues here, and we need to separate them out rather than muddling them together.

The first is current implementation of DLS sets the percentage of drivers that use it, but they all make basically the same decisions for a given route. Thus, the individual driving style stuff (DLS randomisation) that Victor is working on is definitely a much needed and worthy enhancement to the DLS feature.

The second issue, as far as I can tell, is more about the pathfinder. It's saying "at this junction, you need to exit via lane X" and the effect of that is "you must enter the junction from lane Y". Whatever pseudo-randomisation occurs here is not sufficient, vehicles are still preferring one lane over all the others.

Remember that DLS gets applied along a long-stretch of road - it knows the lane to enter on and exit from, but between those segments it's free to try other lanes. It's that entry vs. exit at the junction that's pulling all the vehicles back in to one lane.

So, while DLS generally improves lane usage (and will do even better with individual driving styles), it seems to me that the real remaining problem is going to be the pathfinder saying "this is the best route through this junction". It needs more variance in what it considers the best route through a junction, because that's where this lane bunching is coming from (as far as I can tell).

Now, the Advanced Vehicle AI is already taking in to account congestion - not sure if that's traffic flow or density, I suspect density which in case of lane bunching is desirable IMO. Whether it does that at segment or lane level I don't know. Either way, it's not having the desired effect when it comes to routing vehicles through a junction.

What I would suggest, irrespective of pretty much everything else, is that when entering a junction the pathfinder should be spreading traffic across all available lanes on the entry segment that can reach any applicable lanes on the desired exit segment. I suspect, but haven't checked, that currently it starts with the outermost lane or something like that, I don't know.

[originalfoo]

tl;dr:

• DLS is working great with the new individual driving styles
• Pathfinder still sucks at balancing traffic across lanes at junctions

[VictorPhilipp]

I have recreated the situation. I set DLS to 100% and used the old (static) cost scheme:

I guess there must be something different going on.

[VictorPhilipp]

I guess there was a temporary routing problem at the node between the 3-lane highway and 1-lane ramp which got resolved as soon as the savegame was loaded a second time.

[VictorPhilipp]

Might be related to #308.
I guess there is a timing issue or something related going on in RoutingManager or in the *Geometry code. It seems that sometimes the routing data structures are not always correctly updated.

[originalfoo]

This should hopefully be fixed or at least greatly mitigated in the 10.21 release hitting LABS workshop page shortly.