Car + City Traffic Revisited

Update on City Cars and Traffic

I've made some progress on city traffic since my previous post from two weeks ago. I left off trying to solve problems related to traffic and gridlock, mostly caused by stopped cars blocking intersections near roads connecting to adjacent cities. Here's an example screenshot from two weeks ago showing the problem.

Original 3-way connector road intersection with gridlock due to short roads and too many left turns.

The center of the city is off toward the upper left corner of the image. The majority of cars entering from the connector road on the right make right turns, then left turns. The first right turn takes them onto the tiny road segment with the two orange cars that's only long enough to hold three or four cars. Once that lane is full from cars turning right, all it takes is one car coming from the bottom of the screen and going straight to block that intersection. In this case, it's the red car causing the problem. Once the red car is there, the blue car waiting to make a left turn in the opposite lane will be stuck there forever. The red car can't move until the brown car at the intersection makes its left, but it's waiting on the light gray car, which is waiting on the blue car. The problem is a circular loop of blocked left turns.

One hack that will at least guarantee progress is to allow the brown or blue cars to give up and go straight instead. However, this ultimately won't solve the problem, because eventually these cars are going to get back here trying to reach their destination and will get stuck again. Cars arrive at this intersection faster than cars can give up making left turns and go straight. All this does is delay the problem for a few minutes.

My solution is to fix the intersection so that it's a proper 4-way connection. Now instead of turning right then left, most of the cars go straight. There's no turning, so cars can't get stuck in the intersection mid-turn. Also, this removes the short road segment with limited car capacity. Here is what this same area looks like if we join the connector road to an existing 3-way intersection rather than inserting a new one.

Improved traffic flow using 4-way connector road intersections. Most cars go straight rather than turning.

Everything is going smoothy here. Actually, there are fewer cars than I expect at this location. I wonder why that is? I'll have to get back to that later...

I let the cars run in the background while I went off and did other things. The first time I tried this is crashed after a while, but I think I fixed the problem. Here is what the central city looks like after about 20 minutes of simulation.

Half of the cars have accumulated in the central city, which has roads connecting it to the other seven cities.

It looks like about 40% of the total cars have accumulated in the central city, which has roads connecting it to each of the other 7 cities. Aha! This is why there were so few cars at that other intersection we looked at in the last image. There are so many cars here that the streets are full and none of them can move. This is a new problem for me. I've never gotten this far before, because traffic gridlock would prevent the distribution of cars from ever reaching this state.

Here is the overhead map of the connected cities. The biggest problems occur in that square city to the right of center where the red dot is. The red dot is the player camera position, and it's near where the screenshot above was taken. Those three connector roads very close together in the bottom left corner of the city near the camera are no good for traffic. Also note that some of the connector roads are 4-way intersections, while others remain 3-way intersections.

Top view of cities showing connector roads (gray), bridges (white), and tunnels (brown).

This problem can't be solved by micro-scale changes such as having cars avoid blocking intersections. I'm not sure if it can be fixed by adding more road capacity (lanes). It's possible the only real solution is improvements to car navigation.

Some people have suggested using dynamic path finding where cars try to avoid traffic even if it results in longer travel distances. Read the comments in the previous blog post. This could work. I started with an easier approach: Don't choose destination cities with high traffic density. I modified each city to calculate the total length of all contained roads, and to also track the number of cars within the city each frame. I estimate traffic density as number_of_cars/total_road_length. When it comes time to choose a new destination city, cars will select cities with lower traffic density with a higher probability. This should result in a stable state where all cities have the same traffic density, right?

Well, not really. It actually results in a distribution where two cities have high density and most of the other cities have very low density. Some of the low density cities only have connections to high density cities. Since both connected cities have high density, these cities have no choice but to send their cars to them. The cars travel to these high density cities, get stuck, and never make it back out. So the low density cities keep sending cars there until they have no cars left to send. Maybe a better solution is to implement a cap on the max number of cars in a city, and stop sending new cars there if the cap is reached? That way, the low density cities won't send all of their cars to high density cities. I don't know, this may make inter-city travel dry up. I guess that's better than having gridlock though.

Where do the cars get stuck in these high density cities? They most frequently get stuck at the occasional 3-way connector road intersection. I did add 4-way connector road intersections, but they don't always get selected. Sometimes there's no way to route a road to exactly meet an existing, unused 3-way edge intersection. Maybe all the nearby intersections on that edge of the city are already connected to. Maybe the intersection doesn't line up with the intersection of the adjacent city and they're too close together to insert a jog. Maybe there are other roads, water, or mountains in the way. Etc.

There are several solutions to this problem:

1. Adjust the road grid to force a road at the connection position by moving one of the roads around, which leaves an uneven distance to the existing roads on each side.
2. Adjust the road grid by shifting multiple nearby roads to spread out the difference.
3. Shift the entire city so that one of the roads is aligned to the chosen connector road position.
4. Force a jog into the connector road, even if it looks odd and is otherwise too close to a blocker.
5. Insert a non-axis aligned, slightly curved road to connect two opposing intersections.
6. Add some random variation in city road widths to make it more likely that roads can line up.

Yeah, I'm really not sure about this. None of these are particularly easy to implement, and most of them add strange visuals. I tried to implement some of these, but they didn't really work out. #1 had the unexpected problem of two connector roads trying to connect to different ends of the same city road that couldn't agree on where to place the road. Also, moving the road increased the city plot sizes to the point where they no longer fit into the shadow frustums, leading to shadowing artifacts. I think #2 would likely fail for the same reasons. Shifting the city for #3 breaks the nice city placement pipeline/flow and can lead to iteration of the placement algorithm. #5 and #6 are just too messy and complex. Maybe the traffic has won this round. I think I put up a good fight.

I did manage to get somewhere with #4. I added a config file option to prefer adding roads with a single jog that end in two 4-way intersections over a single straight road with a 3-way intersection at one end. I'm not sure it helps much. The connectivity graph is worse, and cars have to travel further to get to their destinations. Maybe the only real benefit is extra road length to hold waiting cars. I can use this as a last resort if needed.

It could be time to start teleporting those pesky cars that block the intersection somewhere else on the map while the player isn't looking. I added wait time tracking for cars stopped at lights or in intersections. If the car has been waiting for more than a minute, it's front end is out in the intersection (blocking it), and the light has turned yellow, it's removed and respawned somewhere else in a random city. I didn't bother to implement the "when the player isn't looking" part because that makes it too hard to debug. Did that car I was looking at 30 seconds ago finally get to turn, or was it teleported somewhere else? I can't tell! If only I could see it teleport, then I would know that code was working.

I've definitely made progress using these improvements, but not enough to have the car simulation run forever without cars getting stuck. I have to get back to preventing cars from stopping in intersections. That's the root problem. I need something more complex than looking one car ahead, something with longer term planning. Someone suggested looking at all the cars in front of the current car and calculating whether or not they can fit in the current road segment if they were to stop. This makes sense. If they can't all fit, the querying car should stop before entering the intersection. That's the safest decision it can make.

Skipping to the conclusion - yes, this definitely works, but it's no easy task. I need to find cars on the same road segment when cars are on roads between intersections. When cars are entering or in intersections, I need to find the car in front, which may be in the intersection or on the road segment leading out of the intersection. Cars waiting at lights on the other side of the intersection don't count. Those new 4-way connector road intersections have roads with different city and road IDs on both sides of the intersection, and that has to be handled. There are a lot of cases, but after a lot of work I think I have it right.

If I let the simulation run for a long time (~40 min.), I still get one form of gridlock. I call this the "infamous right turn loop". Here is a picture of it.

The infamous right turn loop. The cars in this loop are all making right turns, but there's no space for any of them to move.

All four roads around this city block are filled with cars. The cars at each of the four intersections of the inside roads of this loop are trying to turn right. It's not really possible for a car to block a right turn unless it's also going in the same direction, so blocked intersections aren't the cause. There simply isn't room for any car to move. All of these cars are waiting because they have no space to move. This is like filling a race track with as many cars as can physically fit and having them race. Not possible! At least not without some car violating the minimum separation distance and risking colliding with the car in front.

None of my previous changes seem to solve this problem. I've tried changing the stopped_at_light state logic, allowing cars to turn left or right instead of going straight when blocked, and a few other things. I can't really think of what else I can try here. How does this get resolved in the real world? Maybe the only solution is someone putting their car in reverse and going a different way. If I don't support this option in 3DWorld, I guess it can't be resolved. Fortunately, this situation isn't very common. I give up on this one for now. Moving on.

The next task is making this system efficient. I don't have any data structure that tells me which cars are on each road or intersection. I prefer not to have to track all of this. What I do have are cars sorted by city ID, then road ID, then road segment ID. I can do a binary search through this data for cars on the correct segment/intersection of the correct road of the correct city. While this is faster than a linear iteration, it's still somewhat slow. All of the changes applied in this post have nearly doubled the car AI/physics/collision detection time. Much of the increase is due to the extra car-in-front logic.

Summary

I think I have cars working pretty well now. I've had the simulation run for half an hour, after which I see no stuck cars. Yes, there's traffic, but it's all moving. The three layers of gridlock avoidance seem to have finally solved this problem:

1. Don't stop in an intersection (don't even enter the intersection unless there's room)
2. If you find yourself blocked by a stopped car, choose another direction to go
3. If you're still stuck in the same place after a minute of waiting, respawn somewhere else

I may finally be done with the car logic. I'm pretty happy how it turned out, though it took way longer than I anticipated. It's been about a month of realtime since I started working on this problem. There are still some minor issues such as cars stopping when they don't really need to, cars following too closely, cars jumping backwards a bit at intersection boundaries, cars colliding temporarily for a frame, minor instability (jittering) when a hundred cars are waiting to enter a city at a light, etc. I'm not sure if I'll try to fix these at some point or just leave them unfixed. They don't seem to hurt the overall traffic flow and ability for cars to get to their destinations. Most of these are only visible when you know what to look for.

I've had enough of cars for now. It's time to move on to a different topic. The next post will likely cover object physics interactions with cities. [In fact, I've already recorded a video and started writing it.] For example, weapon fire on buildings and cars. I don't plan on making these destroyable yet, I just want to prove that collision detection and collision response work with city elements.


Appendix: 3DWorld City Background Info

Some background on how my data structures work: Each city contains a set of roads, road segments, and intersections. The roads connecting cities are all owned by the "global connector road network", which also acts like a city (with no buildings). Roads and road segments are oriented in either X or Y for simplicity, and each one has only one lane in each direction. Segments have pointers (actually indexes) to their roads and the intersection at each end. Intersections have pointers to 2-4 connected road segments, and the 2-3 roads running through them. The 3 roads case is for 4-way intersections connected to other cities through the global road network. Roads, segments, and intersections are all spatially sorted so that operations such as binary search can be used to find them efficiently.

Cars maintain their current city, current road, current road segment or intersection, destination city, and destination intersection. Cars are kept in sorted order by {city => road => road segment/intersection => position along road}. This allows cars to query the car in front of them in constant time when on road segments. Everything works smoothly for cars on road segments, and I have no problems. Intersections are more difficult, and this is where there can be multiple cars "in front" of the current car, depending on where you look. There can be a car directly in front in the intersection, a car blocking the intersection going left/right (cross traffic), a car turning in front, or no car ahead within the intersection. If the car is in the process of turning and facing some non-XY direction, it's even more complex.

Cars and traffic lights are isolated systems that can query each other, but neither can directly modify the other's state. This models the real world where traffic lights can observe and direct, but not control cars. Cars can observe traffic lights but not directly influence them. Traffic lights run a finite state machine (FSM) that controls the different turning lanes for the entire intersection. This includes sensors that detect waiting cars and can skip light cycles where no cars are waiting. Cars can query the state of the FSM to determine the light colors. Yellow lights aren't actually states; they're determined by querying the traffic light for red/green light state at some time in the future. Since everything is determinstic and time-based, this is possible.

Cars travel at speeds determined by their max speed, the road's speed limits, and the speed of the car in front of them. Cars traveling faster leave more space between them and the car in front for stopping - though cars can actually stop very quickly when needed.

3DWorld cities have crosswalks and sidewalks. However, they're all fixed size, so they don't really need to be taken into account in the math. The dimensions of the driveable areas of the roads and intersections already take the crosswalks and sidewalks into account.

I haven't added the complexity of multiple lanes. Surely this makes the simulation much more difficult. This is one of the reasons why I haven't tried this solution to the traffic problem. However, I suspect multiple lanes would make some of these other problems much easier to solve.

It would probably be easier to prevent blocked intersections if it was more like a 4-way stop sign and the first car to reach the intersection could do what it wanted. The problem is that this won't optimize throughput for busy streets. I want to see those cars moving together as one continuous line of traffic while the light is green. I tried having cars wait until the car in front has cleared the intersection before entering it. It looks pretty bad visually. Imagine what it would be like if the light turned green, and the car in front of you started moving. You can move up to the intersection, but can't pull out into it until the car in front is out. Maybe you're crossing several lanes of traffic. The drivers behind you would be hoking their horns. Yes, this is safe, and it will prevent blocked intersections. I already tried it. It just makes the simulation look like all of the drivers are 90 years old!