Have Roads Drive Cars Instead Of Cars Driving On Roads

[FireController1847]

Now the concept sounds weird, but it makes sense the more you think about it. Currently, we have each vehicle individually calculating its route and constantly updating its position. There's not a lot of opportunity for performance improvement in terms of caching, as things constantly need to be updated.

Basically, the way aubergine put it, "...instead of iterating vehicles and doing all those calcs (and leader car stuff, etc) to make the car drive along the road, why not make the road drive the car?" More so, he said, "The road could then cache the routes along it on a segment-by-segment (lane-by-lane?) basis, so when a car enters the segment the vehicle motion is already pre-determined - then it's just a case of tweening along that motion path taking in to account vehicle speed. The same could apply to on-road parking, and also vehicles moving out of way of EVs, bits of that could be cached. There would be no need for leader cars any more."

I strongly agree with this and could provide a lot of opportunity for performance improvements. I also think that if we're able to determine the cars position using the road, we could quickly (and easily) implement things like EVE and other features, and we'd FINALLY have a way to be able to fetch a car's position via the road and/or segment, instead of looping through all the cars in the game. This idea was originally brought up by @aubergine10 in #64, but I thought it deserved its own issue.

Cc. @VictorPhilipp @krzychu124

[originalfoo]

There's other things too - like road condition affecting driving speed. Each road segment knows it's condition and is responsible for the speed that cars follow the cached paths along it (tweening speed).

Same sort of thing with noise pollution; a function of vehicle noise, road noise cancellation (eg. tree lined road), and vehicle speed. Same sort of thing with congestion.

The way things currently work multiple vehicles are going to be querying the same bit of road (or rail, or whatever) per tick. By doing things the other way round, road drives car, we can avoid that extra workload.

It would also make things like car accidents easier, because now the road would orchestrate the accident scene and actors.

The big mindf*ck is how things work between segments and also junctions. The outbound lanes of segments would have to hand over vehicles to the inbound lanes of next segment. What if that segment isn't ready to accept them, what if it has or hasn't already done its calculations? What are the performance implications of that on congested roads?

[originalfoo]

BTW, I'm essentially approaching this like Theory of Constraints.

The way the game works now, there are multiple "Herbies" (constraints / bottlenecks) as we "push" cars down roads. By switching to a "pull" methodology, with roads responsible for pulling cars along them, we can create a single "known" constraint, some aspect of the road, and then organise everything around that.

[krzychu124]

Some thoughts below.

What about road upgrade?

When road segment is upgraded old segment is destroyed an the new is spawned between existing nodes.

Now more complicated...
How about segment creation?

Segment could be created using:

• existing node,
• splitting existing segment(not in half obviously 😉)

When created using existing node, info about segment is added to node and info is propagated to other connected segments.

When using second technique, it's more complicated.
Existing segment is splitted on two new segments and new node is spawned at intersection point.

And already mentioned, segment removal.
Segment is deleted and nodes if no other segments connected to them.

[originalfoo]

When it comes to processing, if a segment has not already cached its lane paths it would do so on demand and cache them for subsequent use. The main thing is it would then be able to have one instance of the path (per lane?) and apply it to all vehicles on that path, rather than having to instantiate / recalculate the path on a vehicle by vehicle basis.

It's not so much the creation and deletion of segments that worries me, we kinda have to deal with some of that stuff already, it's more the handover from one segment to another. So what happens if a segment tries to send a vehicle to the next segment, but that segment is blocked. Simplistically, the vehicle has to stop, but it would need to decelerate first (so at the very least each segment will need to query the next one or junction in applicable direction). But what if that next segment hasn't done it's processing yet... This same issue must exist for vehicles and vehicle grid, I guess, so the game must already be dealing with a situation like this - I just don't know how it does it yet.

Segment is deleted and nodes if no other segments connected to them.

A segment can exist in isolation, so long as it has a node at either end.

[matfax]

I think this idea could improve performance drastically if you even extend the concept so far that the field of view is observed. You don't have to calculate the precise positions for streets that are far outside the reach of your view. All you need to know is that there is a road and this road has a set of cars on it. For these outside segments, every few calculations, you can choose an arbitrary group of segments that pass some cars to the next segment. You fulfill some probabilistic constraints and limit the calculation demand to fulfill the constraints, nothing beyond that. Cities Skylines generally has a performance problem, even without mods. This idea has the potential to solve that. From pure logic, there is no sense that if you zoom in and only see a few cars driving, the performance is worst while the GPU keeps idling. The only explanation is that outside the view, useless calculations take away capacity.

Following this approach, inside the view, you then have more capacity to focus on the details. The challenge here relies on the intersections/intersegments. @aubergine10 I think you are over-complicating things concerning the blockades. It is sufficient for a segment to watch only for the next segment.

Segments usually are longer than a cars capability to reach more than one segment given its speed. That would be a special case if a segment is so short that in one calculation cycle, the car would theoretically be beyond it. But there it comes handy that the segments can set their own speed. Short segments are usually more complex to drive in reality, so the user would anticipate that cars drive slower on such segments. In real life, you don't speed up to 100kmh/60mph for 500m distance either.

But back to the point. So we can assume that all roads are long enough. That also applies to blockade propagation. What happens in real life if a blockade propagates. The cars only foresee a limited range. They don't see beyond the next segment. If a blockade propagates, crashes are not unlikely, but at the very least, the cars abruptly decelerate. So the worst case is that the blockade expands one segment after the other, calculation by calculation, every time asking the next segment for its current driving speed + repletion ratio and accordingly adjust the own cars' driving speeds. The faster the next segment's cars decelerate, the faster the own cars will have to decelerate. The absolute corner case could be an accident where the front cars within a segment can't stop fast enough. That is also very realistic because, within a segment, you usually can see farther than at an intersection, so that at intersections it is more likely to have an accident in general. All in all, there is no such scenario necessary where propagation needs to reach more than one segment per calculation as you apprehend it.

[originalfoo]

Yup - outside of the camera view we do not need precise locations of vehicles. But it would have to still be sufficiently accurate enough to gather the following traffic metrics:

• Noise pollution
• Traffic density
• Traffic flow

Currently the game processes all that stuff with same accuracy everywhere, as far as I can tell. If we could reduce the accuracy of stuff outside camera view, but retaining sufficient simulation detail, it would potentially save some CPU cycles.

As part of another task (#415) we are discussing the need for a "network grid" to quickly find network segments and nodes in a given area, and then a cache of what's within the camera view. That's primarily for perspective of TM:PE info overlays and tools, but could later be used to determine simulation accuracy levels.

Regarding the "blockade" stuff, segments cannot be processed in terms of their route direction. Each segment, usually with two directions of traffic, has to be treated somewhat in isolation. for example, if traffic lights stop traffic on segment at the junction, that segment might be processed before or after the preceding segment on that road and so on. Remember that users can be altering roads all over the place in no defined order. Determining "next segment" would be problematic; in fact it might have already bee processed and thus we'd end up altering vehicle positions two or more times per frame. We could potentially mitigate that issue to some extent by processing named routes rather than segments, essentially treating each named route as a road (even though that is not always the case as many players don't bother to maintain their named routes properly).

I'd also be interested to hear what you think of #114 :)

[matfax]

Yup - outside of the camera view we do not need precise locations of vehicles. But it would have to still be sufficiently accurate enough to gather the following traffic metrics:

• Noise pollution
• Traffic density
• Traffic flow

Indeed, but these can easily be generalized. Traffic density (or 'repletion ratio' how I called it), traffic flow or driving speed, and noise pollution can all be calculated without precise positions.

for example, if traffic lights stop traffic on segment at the junction, that segment might be processed before or after the preceding segment on that road and so on.

I don't know the model, so I only can assume, but the important requirements should be met, namely that (1) all segments are processed exactly one time per loop iteration, and (2) we have the references to the connecting segments.

Every lane/segment has incoming / pending cars, and cars that will leave the current segment in this iteration. So there are two cases to consider when there is a car pending for reassignment to the next segment.

1. The next segment has not been processed yet during this iteration, so the pending car's position will be calculated seamlessly, no visible glitch.
2. The next segment has already been processed in this iteration. If we assign a car to it, until the next processing iteration (i.e., one frame), we have a challenge. If we do nothing with this car, there will be a visible glitch for one frame. One frame will barely be noticeable if the framerate is high enough but this could be optimized.

Most importantly, we can't know for sure if case 1 or 2 applies or if a car has already been calculated per se. Any ideas to reinitiate the calculation of affected segments don't seem to be viable for obvious reasons. I could image an additional set of pending incoming cars in every segment. Outgoing cars are always calculated by the leaving segment, then added to the corresponding lanes, and the pending incoming cars of the referenced entering segment. No matter if the entering segment is processed after the leaving segment in the same iteration, or if it processed in the next iteration, it first calculates the existing set of assigned cars (skipping the cars from the pending cars set) and after that, it empties the pending cars set. If queues are used in the lanes, it would be sufficient to store the number of new enqueued pending cars to skip in the next iteration and set it to 0 afterward. After all, every car is only processed once and without visual glitches.

The corner case here is that we calculate an outgoing car position but at the same position another car would already exist in the next segment. For that to happen, the car in the next segment would have to be stopped abruptly, so that the previously estimated driving speed and the distance between the two cars don't compensate.

A simple circumvention would be to check the driving speed and traffic density before reassigning the car to the respective segment. Another solution would be to use the order in every segment or lane to determine last cars from every lane. Every outgoing car is then first checked against the last cars of the next segment, and then calculated so that no blockade happens with the last cars, then added to the pending cars.

Your idea of the metamorphic pathfinder looks interesting as well. I will think about it and also about how the probabilistic metrics could look like in a model.

[originalfoo]

Indeed, but these can easily be generalized. Traffic density (or 'repletion ratio' how I called it), traffic flow or driving speed, and noise pollution can all be calculated without precise positions.

For certain TM:PE features we'd still need to know some of those details at the lane level. As part of increasing lane usage, TM:PE monitors which lanes are busy and adds a slight penalty to them, encouraging vehicles to move to less crowded lanes.

[matfax]

For certain TM:PE features we'd still need to know some of those details at the lane level. As part of increasing lane usage, TM:PE monitors which lanes are busy and adds a slight penalty to them, encouraging vehicles to move to less crowded lanes.

In that case, I would change the concept so that we are not talking of roads driving the cars but lanes driving the cars. By "lanes" I only mean the lanes inside each segment, not the complete lane. I'm not sure how exactly the penality system affects the logic but I assume it basically is a probability to change the lane if the considered lane's probability is lower.

So I'm wondering if it is appropriate in such a model to let each car decide on its own to choose the lane or, once the lanes drive the cars, to let the lanes choose the "top" n percent of its cars. "top" would be a function that determines a selection of cars considering various of their criteria, such as maximum speed and recklessness. n percent would be chosen in consideration of the difference between the current and considered lanes' density, average speed, and maybe also the current "speed change". The stronger the current lane is decelerating the more likely it is to change the lane the more likely that considered lane is accelerating. The "speed change" would also be necessary to calculate the other metrics.

I will call the "probabilistic" segment state where positions are not calculated, shadow mode, and when they are calculated, I would call it focus mode.

In shadow mode, the lane could then add the car to the end of the other lane, whereas in focus mode, additionally to the density, average speed, and speed change, it would select a subset that has the largest gaps in the considered lane next to them. Lane change seems to be a rather complex task so it would be sufficient to calculate and update the TOPs scarcely, maybe store them in a sorted list and once a car is reassigned to the next segment's lane, reconsider the choice to add it to the next TOPs again or not.

Is there anything else that the penalty variables affect that I have not considered?

I have also thought about the other metrics and their shadow/focus calculations and it's not as simple as I thought. Doing it the wrong way could mean that you see a traffic jam in focus mode, then look around and focusing back, the jam disappeared. Alternatively, you could solely let the shadow metrics dictate how the cars have to behave in focus mode but that would look very artificial. Both modes have to be as equivalent as possible. That might be a lot of trial and error but I'm sure that it can be generalized.

Another idea I'm considering for the metrics calculations which I don't know if TM:PE has integrated yet, is how the distance between cars and the safety distance affect the acceleration/throttling behavior and hence the speed of the car and average speed of the lane. I've tried to check the code but it's a lot and I have no clue where to start.

[FireController1847]

My apologies but with my recent increase in real life activities and my lack of participation in TM:PE in recent months, I think this issue would be better suited to someone else. If it's still around when I come back I'd look forward to fixing it, but for now I'm going to unassign myself. Sorry!