Here's a quick update on my car navigation progress. Once I had added the onscreen car stats feature, I was able to figure out what some of the problems were.
1. I fixed the problem where the traffic light "sensor" wasn't picking up cars stopped in the intersection and was skipping their green light cycle. This was an issue when there was no car behind the stopped car that was actually waiting at the light. The stopped car had to sit there in the intersection until another car approached the light behind it, triggering the sensor. The fix was to include cars stopped in the intersection in the sensor's "range". In fact, a stronger fix is to prevent the light from skipping any cycles when a car is stopped in the intersection. Another fix would have been to allow a car to exit the intersection even on a red light, but that seemed more difficult and risky to implement.
2. I changed the logic to allow cars that had entered the intersection to give up on a left turn and go straight instead when the lane was blocked. Previously, cars could only change their turn direction before entering the intersection. Now they can change their decisions as long as they haven't started to turn (rotate) yet. This allows cars to pull out into the intersection to make a left turn, then later give up and go straight instead. This was one of the most common causes of gridlock. However, this isn't enough to completely fix the problem. It's still possible for a car to pull out into the intersection, start to make a left turn, then get stopped by backed up traffic in the lane they're turning into. Once the car has begun the turn, it's too late to back out and go a different way.
3. Cars now have a 25% random chance of choosing a new destination when forced to abort a blocked turn. They also honk their horns in this situation. The new destination is always within the current city in an attempt to avoid the connector road, which is likely the path that was blocked.
4. Cars can now access the car directly in front of them on the current road. This allows them to see if the car is stopped in an intersection, and potentially not enter the intersection in that case. Unfortunately, this doesn't seem to help.
I was hoping that it would fix the problem with cars entering and blocking 3-way and 4-way intersections. This change makes cars occasionally stop before entering the intersection, but the most common case is when a line of cars enters and then quickly stops. The last car to enter saw the car in front of it moving just before it got stuck, since the line of cars always stop in front-to-back order. Cars still can't anticipate stopping.
I was also hoping that this would fix the problem of cars colliding when stopped around a bend in the connector road. The problem here is that the stopped car isn't actually directly in front of the second car, but to the side of it, facing a different direction (right angle). I don't know how to reliably find the car in front without accidentally picking up a car going in a different direction or on a different road connecting to the intersection. I can't use the front car's velocity because it's stopped. The system that sorts cars by position along a road won't necessarily place the two cars on different directions of the bend next to each other either. I don't think any simple position-based sort function would do this. Note that the sort is the most time consuming step of car simulation, so I need to keep it fast.