Sunday, September 2, 2018

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!

18 comments:

  1. How about when selecting a destination for a car, checking how congested the connector road is (or even how many other cars have another city as a destination) and not selecting another city if those numbers are high? Kind of a hack, but maybe that would be sufficient?

    ReplyDelete
  2. Hey, you're the guy from Here Dragons Abound! I read your blog.

    Thanks for the suggestion. This might help, though it requires keeping track of global stats. I think the stats needed for this is "number of cars waiting at the intersection", though I'm not sure how to calculate this. Cars know that they're waiting behind other cars, but they don't know why. Maybe "number of cars stopped on road leading to intersection" is a better metric. However, this won't help in cities that have only one road leading out of them.

    ReplyDelete
  3. Hello. I built a multi-lane traffic simulation for a defense contractor a number of years ago that had to push 5000-1000 vehicles(and double that pedestrians), and your blog here had a bunch of familiar issues I worked through to end up with a pretty decent system I can share some details about. Hopefully something in here helps in some way.

    I typed up a huge reply only to have it denied for being too long, so here's a pastebin link.

    https://pastebin.com/uNshe3As

    ReplyDelete
    Replies
    1. Thanks for taking the time to write everything up here. Your project sounds very interesting. It has some things in common with what I'm trying to do in 3DWorld, but also many differences. One difference is that our two projects have different goals and purposes. I'm trying to model cars using a traffic simulation with the primary goal of looking realistic. The secondary goal is to not have cars get stuck forever. All of this is done part time, piece by piece over many late nights. Your goal sounds like a correct simulation where all cars make safe and legal decisions.

      I haven't added the complexity of multiple lines. 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.

      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. This sounds like what you had implemented. 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!

      I originally tried to past a longer comment here as well, but I see that the limit is 4096 characters. I'll add more background and add a proper reply at the end of my next blog post.

      Delete
    2. Looking realistic was also a goal of ours as well(and doing it at high scale), since these simulations were to be observed by real life pilots flying above, and a big part of the training was learning to pick out anomalies and/or track targets of interest as they blend in to the traffic simulation.

      All the intersections in our simulation had traffic controllers for a given edge. Those could be stop signs or traffic lights. Stop signs were a simple, must come to a stop, and after meeting that requirement could they get added to the queue to continue. This gave the easy impression of first in first out traffic etiquette. The lane mappings here were still very important though, because if the next car to go just wants to turn right, and another vehicle from another edge wants to turn down another street, they can technically go at the same time, because their transition edges don't overlap/effect each other. Traffic lights only had the requirement of stopping if the light was actively red, otherwise they would try to continue through it with all the same lane mapping considerations. Since they made the bulk of their decisions using the stopping distance away from the next set of maneuvers, if the lane mappings were marked blocked at that time, it gives them time to stop and wait. The vehicles through traffic lights would all continue smoothly through, again thanks to the lane mapping. There was a state difference between the reserved lane(s) through an intersection, and the ones marked as blocked, so whoever the forward vehicle was that reserved the transition edge was not blocking the guy behind him from taking it as well, only other edges that he will cross during that traversal. I didn't mean to imply the behavior you are describing. The rear vehicle in your example would be checking whether there is room for themselves in the edge they are entering as well the vehicles marked as transitioning into the edges. This gives the appearance of assuming the vehicle in front of them is going to follow the rules of the road to avoid that issue you describe of being overly cautious.

      Delete
    3. Okay, that makes sense. What did you do when a line of cars driving through an intersection reached another traffic light that was backed up and had to stop, leaving the last car in the intersection? If each car can closely follow the car in front of it, I don't know how you can figure this out. Unless cars can look ahead to the next intersection on the road and do some prediction.

      Delete
  4. They didn't back up into the intersection bc they only assumed they could continue when there was room on the edge for themselves and the other cards entering the edge. There wouldn't be room left in those situations that would lead to the car stopping in the intersection.

    ReplyDelete
    Replies
    1. Okay, that makes sense. That could work for 3DWorld. If we know the length of the road (edge) and the number of cars already on it, it should be possible to determine if a car would fit. It might fix the problem. Then again, this is about the third time I've said "X change might fix this problem". Thanks.

      Delete
    2. I definitely understand that. Our traffic system was a pretty big chunk of time.

      Good luck!

      Delete
    3. I implemented this, currently only for cars going straight. It works! Now I just need to figure out how to handle cars that are turning. Since the car in front may be on a different road segment and in a different orientation, this is more difficult. The sorting algorithm won't always put them next to each other. I need some other acceleration structure to do this efficiently. For example, I need to have each road track which cars are on it.

      Delete
    4. Turning within intersections? Or are you talking about cars that may have unaligned orientations within the road segments?

      Delete
    5. Turning at intersections. It seems to mostly be a problem with right turns. Cars going straight will stop when the road segment on the other side of the intersection is full. But cars will still turn right. The first car to turn won't fit and will block the intersection for other traffic trying to enter that road segment. It's less of a problem for cars turning left because they'll sometimes give up and go straight instead. Cars oriented N-S vs. E-W are sorted differently, which makes it difficult to count cars on perpendicular roads.

      Delete
    6. How do you handle a block where all four roads on each side are filled with cars. Each of the 4 cars waiting at the intersections around that block is trying to turn right. None of those 4 cars can actually turn because there's no space for them, so it results in gridlock. It's a cycle of edges at max capacity.

      Delete
    7. I don't think we ran into that as far as I can remember. With all roads being multi-lane from the start for us, there was always the option to avoid the jam and continue. For all the cars backed up behind the guy that wanted to turn, they could always change lanes to go straight or left through the intersection.

      Delete
    8. Yes, I can see how the extra lanes would help here. Maybe I need to disable turns where the destination road doesn't have space for the car. I can't have cars change right turns after they move into the intersection, but I can have them decide just before entering. This will make cars take alternate routes. Hopefully they can still get to their destinations.

      Delete
  5. This comment has been removed by the author.

    ReplyDelete
  6. I started thinking of a bunch of solutions while reading the first part of the article, but then you listed almost all of them in your list of things you tried!
    One approach would be to automate offending car removal. Eventually the number of cars would get low enough that it wouldn't gridlock any more, and then you can just hard-code that number in as the maximum number.
    Also, debugging simulation states would be a lot easier if you had fast-forward. Also, save states, so you can rapidly test problematic situations instead of waiting for them to arise naturally every time.

    ReplyDelete
    Replies
    1. I probably spent at least a month trying to fix this problem! It really drove me crazy. I believe there are two other posts on this topic. I did eventually solve it though - at least I don't remember ever seeing these problems after the final fix. I eventually remove and respawn a car that's been stuck for too long, as long as the player isn't looking at it.

      The time to gridlock is some log/exponential function of the number of cars. 5K cars gets stuck almost immediately. 4K takes ~10 min. 3K will run for hours and eventually get stuck. 2.5K will get stuck if left running all day. 2K would probably be low enough. It's not so easy to determine the threshold.

      Yes, it would be faster if I could somehow fast-forward. There's a limit to how fast the system can be run while remaining stable. Think of trying to drive when you can only open your eyes once every few seconds - that's how the cars would feel! Also, there's significant CPU time put into traffic simulation, which would create some sort of lower bound for how fast I can get to a fail state. But mostly I was worried that I wouldn't be able to reliably reproduce the problem when it came up. Adding the debug info definitely helped. However, I think that if I had known how long this would have taken to solve, I would have approached it differently.

      Delete