Car Path Planning and Navigation Within a City

I'm back to working on 3DWorld's procedural city system. This post is about algorithms, decisions, and trade-offs. It's going to be a big wall of text without many pictures, since I can't easily describe this content with images. The images I do have are mostly of things that went wrong, since I don't really have this system working correctly yet. Sorry to those of you who just want to look at pretty screenshots.

I've had "better car path planning" on my city TO-DO list for a while. The current AI/simulation system was just choosing random turn directions for each car at each intersection. I wanted to change the system to select a real destination for each of the cars from somewhere in one of the connected cities, then let them drive toward their goals. I knew this was going to be a lot of trouble to get right, so that's why I put it off for so long. In my defense, it's not obvious to a casual observer whether cars are moving randomly or purposefully driving to a specific destination. You would need to pick a car and follow it around for many minutes to find out it's just going around in circles.


Destinations and Navigation

The first step in car navigation is choosing a destination. I decided to use road intersections as destinations. Each car starts with a random destination intersection in its current city. When it reaches the destination, it chooses another intersection in either the current city or an adjacent connected city. Choosing a different city is a lower probability that depends on how many cities are connected to the current one. When the destination is in another city, the intersection of the connector road leading to that city is used as a temporary destination until the car reaches it.

Cars run their path finding logic when they reach an intersection with traffic lights where a choice can be made (not a 90 degree road bend). This is generally only once every few hundred frames. They choose to continue straight or turn left/right based on which direction most closely matches the straight line direction to their destination. There are currently no reverse or U-turn options, which simplify the logic. These shouldn't be needed unless cars make incorrect navigation decisions. Since cities are laid out in a fully connected, uniform XY grid, this will produce an optimal path. However, it may lead to many turns in the case of a diagonal destination direction. I haven't yet tried to minimize the number of turns. I suspect it may lead to increased traffic along the edges of the city, which could be a problem. This system works pretty well for getting cars where they need to go. Car path finding only takes around 0.1ms per frame (of the total 0.7ms car physics/collision/AI time) for 4000 cars. The fast time is mostly due to sparse updating of destination parameters only once at each intersection rather than once per frame.

Here is a screenshot of cars in their initial uniformly distributed positions. This looks nice and clean. I've disabled the buildings and trees in all screenshots to make the cars easier to see. I also disabled static parked cars that only add visual clutter.

Initial state of cars before traffic starts to build up. At this stage, everything looks fine.

Traffic Congestion

The only major problem is traffic congestion - and this seems to be nearly unsolvable. I never really had this problem when using random turn directions because that kept the cars distributed uniformly across the city. They never accumulated in one area. But with specific destinations, certain areas of the city such as the connector roads become traffic hotspots. After 5 to 10 minutes of simulation, some of the connector road intersections become gridlocked and stay that way forever. The problem is usually due to cars stopped in the intersection, sometimes in the middle of making a left turn where they block both lanes of traffic. The cars can't finish their turns because they're blocked by oncoming traffic. What we end up with is a situation that looks like the screenshot below, where most of the cars in the city are lined up trying to get out through the single road that connects to the adjacent city.

Traffic jam leading up to the single road exiting this city. There are very few cars behind the player's view.

The source of the traffic jam is two cars trying to make left turns by the connector road. Here is a closeup of the connector road intersection. The three cars waiting at the intersections (two blue and one brown) are all trying to turn left, while the green car is turning right. All of them are blocked by cross traffic, which itself is blocked by other cars turning left. It's unclear how the simulation/AI should handle this situation. I'll present some ideas I tried that didn't work below, along with some other suggestions that I didn't try yet.

Gridlock at a connector road where two cars are trying to make left turns at intersections blocked by oncoming traffic.

Here is an example of something else that can cause gridlock. The yellow car is trying to make a left turn (I think) but can't complete the turn because of the brown car, which is blocking the intersection. (Cars have a minimum spacing around them to allow them to stop before they collide.) The stuck yellow car blocks the red car from either going straight or left. It may also block the red car from turning right because its rear end position may make its padded bounding cube overlap the other lane.

The yellow car is stuck in the intersection mid-turn, blocking it. I'm not sure if it's trying to make a left or a right.

Traffic Solutions

How would real drivers handle this? Maybe they would think ahead and not drive into the intersection in the first place if it looked like they would get stuck there. For example, by seeing that the cars on the other side of the intersection aren't moving and stopping before entering the intersection instead of blocking it. But that's difficult to implement in 3DWorld as it requires some sort of look-ahead and planning. It requires fast forwarding the simulation to predict where cars would be in the near future. Humans are great at this; computers are not as good. Computers may take a lot of computation time for this prediction, and that's not something we want in a simulation of 4000 cars.

Let's assume these real drivers do in fact stop in the intersection, blocking it. That happens all the time at the big intersection outside my real life office. Some options for getting out of this situation are:

• Back up out of the intersection. This may require a chain of cars to all back up together.
• Give up on making a left and make a U-turn or right turn instead.
• Go around the blocking car by driving on the shoulder of the road, etc.
• Drive in a different lane. Usually intersections like this will have more than one lane.
• Honk your horn, repeatedly. Wait, this doesn't actually help...

Here are some solutions I've tried that didn't entirely fix the problem, listed approximately in the order I tried them. These changes together definitely improved the situation though, replacing "all cities have gridlock quickly" to "some cities have gridlock eventually".

Higher connector road speed limit: I increased the speed limit by 2x for connector roads. This got cars to their destinations faster, but did nothing to help traffic inside the city. In fact, it probably made traffic build up more quickly. Improving latency doesn't help to improve overall bandwidth in this situation. The rate at which cars can exit the city via the connector roads is limited by how fast they can pass through the intersection, not how fast they can travel once on the road.

Longer light times at connector roads: If cars exiting the city have more green lights, there will be less traffic, right? Well, no. This just means that cars entering the city will have to wait longer because their lights are red more often. Which means they're more likely to block the intersection and stop cars from exiting the city. I'm not sure what overall effect this change has on traffic, but it definitely doesn't solve the problem.

Right turns on red: I added a change that allows cars to make right turns on red when legal and safe. It was easy to do, but doesn't help much. Most of the traffic is due to cars waiting to make left turns, not right turns. This still seems like a good thing to have, as it generally reduces wait times at traffic lights that aren't blocked.

Traffic sensors to control lights: I added traffic sensors at intersections that detect cars waiting at lights. If no car is waiting, some light states may be skipped. This allows cars to get mostly green lights when no other cars are coming from other directions into the intersections. This definitely helps reduce red light delays for cars in the outskirts of the city, but it doesn't help traffic congestion at connector roads. These roads are busy and tend to always have cars waiting in every direction. Lights can rarely be skipped. Also, there's a problem where cars backed up at the light don't stop in the correct place to trigger the sensors and the light skips them. However, this doesn't actually matter to the overall traffic flow, because the cars in this direction can't move anyway. So I haven't bothered to fix it.

Reduce probability of choosing a new city: One simple change is to reduce the probability of a car selecting a neighboring city as its destination. Connector road congestion is more of a problem with cities that only have one road leading out of them. I changed the probability to be a function of the number of adjacent connected cities, and that definitely helped. There are fewer cars traveling through these choke points. Now only some cities formed traffic gridlock, rather than all of them. Though I suspect if I waited long enough eventually they may all fail. Some cities that have 4 connector roads, one on each side, accumulate a lot of traffic in the city center where the east-west and north-south streams of cars attempt to cross each other. This change is borderline cheating. Of course I can eliminate gridlock by setting the probability of choosing a different city close to zero, but that doesn't solve the root problem.

Abort turn and try a different direction: I decided to allow cars to change their minds if waiting to make a left turn at the intersection, where the intersection has been blocked by a full traffic light cycle. This only applies to cars that are right at the intersection and haven't started making a left turn yet. I initially had them go straight instead, but I also experimented with having them go right if straight was also blocked or unavailable. [I was never able to get the turn-right-instead-of-left change to work because, by the time the decision was changed, the car may already be too far into the intersection to turn right.] This definitely helped, but didn't prevent gridlock. It just delayed it. Instead of gridlock after 5 minutes, it came after 10 minutes. Eventually all of those cars turning in the wrong direction would loop back to that intersection and fill up all of the side roads/loops as well, until that entire area of the map was full of cars. The problem is that making other turns didn't get these cars to their destinations. Maybe they need to pick a new destination in this situation? I'm not sure if that would help if they're already stuck and can't move. Anyway, this behavior seemed to be useful, so I left it enabled.

Use collision detection system to navigate between cars: I experimented with ignoring blocked intersections and letting cars try to force their way between other stopped cars. Unfortunately, the collision detection system isn't really up for this. This change just resulted in cars getting stuck in odd positions mid-turn, which made the problem worse. Or it produced multiple cars trying to occupy the same space. Two cars would see a space available and would go for it at the same time. Now any temporarily blocked intersection could turn into a mess of cars where no one could move, which produced gridlock even faster. No, this isn't the correct solution, though maybe it would work in the real world. Maybe it would work if drivers communicate by waving to each other, etc.

Here are some solutions that are more likely to work, but are difficult to implement or have other disadvantages:

Fewer cars on roads: Duh! Obviously, the solution is to reduce the number of active cars on the road, right? Yes, this does fix the problem. Simply reducing from 4000 cars to 3000 cars makes it take a long time (if ever) to get a gridlock situation. But this isn't really a solution to the fundamental problem. It's like saying the solution to world hunger is to kill 25% of the world's population every so often. That's cheating!

Multi-lane roads: This is the next obvious solution. Real world roads have multiple lanes, which can fit more waiting cars into the same distance between intersections. Increasing speed limits won't fix the problem, but increasing capacity will. I definitely think there should be more than one lane in connector roads, but I probably also have to add multiple lanes to the local city roads feeding the connector roads. An optimal solution is to have connector roads turn into major multi-lane streets that cross through the city. The current situation where connector roads turn into left/right T-junctions is far from optimal. [It would be better if connector roads at least ended in 4-way intersections. This doesn't really work though, because two cities don't have their road grids aligned with each other so that they can be directly connected by a single axis aligned (north/south/east/west) road segment.] The difficulty here is that I would need to implement all of the car lane change logic. And I need road textures with two or more lanes. And I need intersection textures with lots of different combinations of lanes in the different directions. And I need to deal with roads/segments that have different widths from different numbers of lanes, which break the uniform city road grid. It seems like a significant amount of work, and it's unclear how well this fixes the problem.

Left turn lanes: This is a subset of the multi-lane roads idea. Instead of having the entire road be multi-lane, maybe we only need turn lanes. Maybe only left turn lanes. That way, one car stuck making a left won't block all of the cars behind it that want to go straight or right. This is easier to implement than multi-lane roads, but still requires new textures, lane change logic, and multiple road widths. It's unclear if this will actually fix the problem. It will certainly delay the gridlock. I suspect there will still be situations where cars pile up in the left turn lane because the one in front is blocked by oncoming traffic. Eventually, the left turn lane will back up into the straight/right lane, blocking it as well. But maybe the extra capacity of those lanes will be enough to handle 4000 cars.

Look-ahead/prediction: This is probably the most likely to work, but also the most difficult to implement. The real solution to gridlock is to not have cars blocking intersections in the first place. If the car in front is stopped, and the car behind it would get stuck if it entered the intersection, then have it wait at the light. This is what's supposed to happen in the real world. Of course, this may not be perfect in practice. For example, say a car is following a moving line of cars into an intersection. The cars are moving, so it looks safe to enter the intersection. Then the car in front of the line stops suddenly, causing a chain of braking that leaves the last car still in the intersection. What now? Clearly, the prediction system must be more complex than just looking at the car in front. How far does a car need to look ahead? All the way to the next intersection? That could be 30 cars away. It's not clear how much this would impact CPU time and frame rate. I'm sure this would be very time consuming to implement (and debug!) It's unclear whether or not a system like this could guarantee there was no gridlock.

"Removal" of offending cars: Removal of cars can be a manual step, rather than an automated one. Let the player select problematic cars and remove them or relocate them somewhere else in the scene. I've been working on making gameplay weapons work in tiled terrain mode. That's likely going to be the subject of my next 3DWorld blog post. I have projectile intersections with the terrain, buildings, and cars working. I have some functional physics effects, including explosions. If I can make the cars destroyable with the rocket launcher or other weapon, that could be a good way to get rid of those pesky cars stopped in the intersection. It would be a lot of fun! I could make some sort of game out of it, though this is probably pretty far in the future.


Collision Detection

Collision detection problems are a side effect of traffic/gridlock. The collision detection system wasn't designed to handle cars stopped in intersections and around bends. It's only intended to stop cars (or in extreme cases move cars back) to prevent them from colliding with other cars in front in the same lane/direction/orientation. I attempted to handle this by tracking which lanes in intersections are blocked, but it doesn't work correctly in all cases. If I make the definition of "blocked" too strong, two cars blocked in different directions at the same time will deadlock the intersection and prevent either one from ever moving. If I make the check too weak we can end up with situations like this:

A bug/limitation of collision detection can result in two cars trying to occupy the same spot when traffic backs up, blocking an intersection.

The orange and blue cars are inside each other. The problem is that the orange car turning right from the right side of the screen tried to squeeze between the yellow car and the blue car, which were both already stopped in the intersection. The turning collision check is something like a simple ray cast, and the car thought it would fit. Or maybe the blue car and the orange car both thought they could fit in the same previous frame, but they couldn't share that spot. In any case, the two cars end up on top of each other. The collision detection system can only move them forward or backward. If it moves them to the side, they can go out of their lanes or off the road, which causes worse problems (such as assertion failure). It can't move them forward or backward because the two yellow cars to the front and back don't give them both enough space to fit. So they're left where they are, overlapping each other. Actually, the collision system is probably trying to move them every frame, but they snap back to their previous positions because the new positions are also invalid. The fallback is that if the collision system can't resolve the collision, the cars are returned to their previous frame's positions. If the traffic in front starts to move, the orange car will move with it, and eventually the blue car will follow. So this is only a temporary failure.

Here is a similar problem. In this case, cars are backed up to a bend in the connector road. Since this road doesn't have any traffic lights or decisions to make, it doesn't have any of that blocked intersection logic. There's nothing that triggers cars to "look ahead". Cars will happily drive from the right into the line of stopped cars. Then the collision detection system will figure out that they intersect and try to move them, which fails in a similar way as the image above. Here a black car and a white car are inside of each other, and the orange car has been pushed behind them, slightly off the road. To make matters worse, the orange car is still considered to be in the right lane. Cars coming up the hill from the other direction (top of the image) will happily collide with - or rather travel through - the orange car.

Collision detection doesn't understand about traffic backed up around a bend in a road with no traffic light to stop the cars.

This problem might not be that hard to solve. The only issue is that it takes a long time before this failure happens. I've rarely seen it occur less than 10 minutes into the simulation. That's a lot of time to wait for debug iterations. Plus it's nondeterministic (doesn't always fail), which makes it difficult to verify the effects of my code changes. I'm not entirely sure what's going on here. There are too many active cars to print out the state of each one to the console. I could reduce the number of cars below 4000, but then traffic won't back up. Maybe I need some sort of car selection UI for debugging where I move the pointer over a car and it prints some onscreen stats? I had to do that for ships in universe mode. In fact, I already have car ray casting working in overhead map mode, so it probably wouldn't be that hard. That might work, if I feel up to implementing it later.

Update: I added car selection with onscreen stats display, similar to the ship stats display in universe mode. It's not the best, but it's ... functional. Now I just need to figure out which of the 36 numeric car class member variables I want to print out.

Car query mode. The crosshair is centered on that white car in the middle. We can see its stats, shown with some odd perspective text that was intended for universe mode.

Summary

All of these collision problems are due to cars stopped in unexpected locations rather than behind traffic lights. If I can solve the traffic and gridlock problems, I don't have to worry about these issues as much. I've spent a lot of time on this and I don't really want a complex solution. I've added a config file variable to control car path finding and left it disabled by default so that cars are back to making random turns. I don't think it has much effect on the overall look of the city anyway. Maybe I can do something easy such as reducing the number of cars if I decide to enable this again in the future. It was definitely an interesting, though frustrating, experience.

In summary, car path planning is hard. Now I think I understand how difficult autonomous vehicle software must be to write. What is a self driving car going to do in these situations? I'm guessing it will be a big problem in the future. Blocked intersections probably aren't that common in their training data.

If you're curious, you can find the source code in my 3DWorld GitHub repo.

I'll continue to think about this. In reality, I'm probably going to move on to weapons physics for building and car destruction. That seems much more fun to implement!