Sunday, March 25, 2018

Cities with Cars!

I showed off procedural cities with road networks in a previous post. I'm continuing to add features to my procedural city in 3DWorld. This time I've been working on adding moving cars. Initially, I just wanted to add simple cars that drove around the roads as a type of detail object to bring the city to life. But I kept adding more and more to the car system, and it got pretty interesting. Not only did I add cars, but I added traffic lights as well.

I've added various config file parameters for cars to control their number, size, speed, etc. I'm currently generating between 1000 and 10,000 cars of various colors and placing them within the roads on the seven cities of this map. Cars move around within a city, make turns, and travel between cities. The car AI update logic is very fast, consuming only 1.8ms for 10,000 cars. This is because cars only update their state every so often, rather than every frame. The majority of cars tend to be either traveling at a constant speed on a straight road, stopped at a traffic light, or stopped behind another car. In all of these cases, no velocity or direction update is needed, and the cars don't need to determine which direction to turn. These decisions are triggered by infrequent change-of-state events such as when a car's origin crosses into a new intersection or road segment, when the traffic light turns green, or when the car in front starts moving.

I added traffic lights at all 3-way and 4-way intersections to help control the cars and make the streets look more interesting. I used a minimalist, modern traffic light design. The lights for each direction are in a single vertical cube, with straight and right turn lights on the bottom section and left turn lights (if present) on the top. Red, yellow, and green lights are ordered from top to bottom to match standard traffic light arrangements. I made the light housing black so that I didn't have to worry about shadows and normals (for now). I created the turn arrows in Gimpshop. Lit lights also have an emissive overlay glow texture with additive blending to make them appear brighter, especially at night.

Traffic lights use a finite state machine with states that include a subset of {east left turn, east and west straight + right turn, west left turn, north left turn, north and south straight + right turn, south left turn}, in this order. Some intersections don't have left turns, so their number of states is smaller. The left turn signals have a shorter duration, and cars can sometimes make rights on red. There are currently no U-turns. I'm not sure why that would be needed other than in cases of navigational error, which doesn't happen here.

I started off drawing cars as simple colored, untextured cubes. Then I made them two cubes, one for the bottom and another for the top. I added brake lights for when cars are slowing or stopping, headlights at night, and turn signals that flash on and off when the cars are about to turn. My initial work, using these placeholder car models, is shown in the screenshot below. This is an initial prototype I used to get the vehicle motion right, and has been improved since that screenshot was taken.

Cars were initially drawn as two untextured rectangles, and distant cars are still drawn this way. At least the traffic lights look reasonable.

I tried to model vehicle physics as accurately as possible, including realistic acceleration, deceleration (braking), and turn radius. Deceleration is much higher than acceleration, which means cars can stop quickly at red lights but take a while to accelerate to max speed. Cars move faster when going downhill and slower going uphill. Some cars have higher max speed than others. These tend to form lines/groups of cars where the faster ones are following the slower ones.

Each car is driven by an AI that decides which way to turn at each intersection. I could probably use real path planning here by choosing a destination for each car and calculating the fastest route to get there. This would require writing an algorithm similar to what's used in a GPS. Of course, when there are many cars, the user can't actually tell the difference between random turns and route planning. I suppose this requires picking one car and following it around the city. Furthermore, it's difficult for me to even test path finding in this situation. Turns aren't entirely random; some of the faster cars will turn to go around a slow car that's in front of them.

Cars follow traffic lights, and they slow down for yellow lights and to avoid rear-ending other cars. Each car stays in the proper lane and makes legal turns. I added safe right turns on red when no other cars are traveling in that lane. I implemented collision detection, though the AI is pretty good about not colliding with other cars as long as traffic lights are obeyed. Cars always stay on the roads, so I don't need to worry about collisions with traffic lights or buildings. Collisions between two cars do occasionally happen, usually because a car can't stop fast enough or other cars are blocking the intersection. I found out the hard way that cars starting to pull out into the intersection can collide with cars that entered the intersection in another direction just before the light turned red. That's why yellow lights are needed!

It's been infuriatingly difficult to keep the cars from colliding or getting stuck in all cases. Everything runs pretty smoothly in most cases, but when I add too many cars, things start to break down. One of the problems is that traffic can back up and cars will stop behind other cars in the middle of an intersection. Maybe they should stop early to avoid blocking cross traffic, if I could find some way to efficiently implement that. However, I think it's reasonable to allow them to stop in the intersection. After all, that happens with real drivers. I take Uber home from work each day. We often make a left turn at a big intersection outside my office. If I don't leave late enough, traffic is backed up and cars are often stopped in the intersection, blocking our way.

I changed the car logic to make cars wait at the light if the intersection is blocked in front of them, even if the light is green. This fixes the problem in most cases, but can result in gridlock when the density of cars in one area is too high. There are situations where two long lines of cars going in opposite directions end in a car trying to make a left turn. The turn is blocked by the line of cars in the other direction, so all the cars just sit there. I think adding a left turn lane would help, though that requires using a set of road textures that has two lanes in each direction. I suppose this is why so many real roads have left turn lanes.

This fix doesn't quite work in all cases. If the intersection is clear, and cars start to pull out, they can become backed up at the next traffic light. One car may be stopped mid-turn, while the car behind it has already started to pull out into the intersection.  The car behind will collide with the car in front if the front car has crossed the halfway point and is considered to now be on the other (new) road. If I make the back car wait, the light can change to red while it's waiting, and cars coming from the other direction can collide with its front end. It's technically not completely in the intersection, and the intersection hasn't yet been flagged as blocked. The real solution seems to require some amount of planning ahead and anticipating problems, which is easy for people but difficult (and slow) for computers. Now I know how self driving cars must feel.

Another problem is that traffic tends to build up at the intersections on the connector roads between cities. Cars are biased toward taking these roads, even though these roads are still single lane. They can get pretty packed with cars. They do have twice the speed limit, but this only allows the cars to pile up faster. Again, the problem is mostly due to that one car waiting to make a left turn at the intersection that leads into the city. It would probably help if the connector road intersection was 4-way rather than a 3-way T junction. I adjusted the traffic light pattern to assign longer times to the incoming direction of that intersection. This helps with the backup at connector road intersections, while making the gridlock worse for cars trying to cross through that intersection from within the city. Oh well, it's good enough for now.

I'm sure you're all thinking about how bad those cube cars look. I was thinking the same thing! Yes, I need better 3D models. I don't have any 3D modeling tools, and I wouldn't know how to use them anyway, so it's off to Google to find some free 3D car models. My first attempt at using 3D models for cars didn't turn out as I expected. Some (most?) 3D modeling tools have the ground as the XZ plane and Y as up. 3DWorld uses XY for the ground and Z for up. I found this easier because I could use 2D math library classes that operated in XY for the terrain, then extend them upward by adding a Z component. I guess I need to add a 90 degree rotation to fix this. The screenshot below is too silly for me to leave out.

First attempt at adding real 3D models for cars. Something's not quite right about these cars. Hmm.

Also note that the cars are different sizes. This seemed fine with cube cars, but looks odd when they're all the same complex 3D model. I've made them all the same size in the remaining screenshots.

This first sports car model is pretty good quality. I downloaded the model in .obj format from the McGuire Computer Graphics Archive. It's way higher detail than I need though, especially considering it has a full interior and engine that can't even be seen from the outside. That's fine, I was able to use the same level of detail (LOD) trick I used with the 10,000 museum objects. 10K cars, 10K museums, it's all the same. See, I knew I could find a real use for that model LOD/instancing system. The one problem with this model is that some of the triangles on the top rear of the car have bad normals that face inward instead of outward, making them appear too dark in the sun. I assume it's a problem with the triangle vertex winding order (CW vs. CCW) in the .obj file. It's not something I can easily fix, so I'll have to live with it. You may notice this in some of the images below.

These models aren't perfect. The wheels don't actually rotate while the car is moving, and don't turn when the car is turning. This makes cars appear a bit odd when they turn. Also, the transition from 3D models to a pair of cubes is noticeable in distant cars. This problem also isn't easy to fix, unless I'm willing to reduce the number of cars to something like 1000.

Speaking of images, here's a night scene where the sports cars have been colored and placed in the correct orientation. I disabled the buildings so that the distant headlights are easier to see.

Multi-colored sports cars in the city at night. Buildings have been disabled to make the headlights easier to see.

These look much better than the cube cars, even with the dark triangles. Headlights are on because it's night time. The glow of the bright lights has a nice effect. I wish I could add spotlights on the road, but I haven't figured out how to do this yet. It's difficult to add support for thousands of moving spotlights in a scene with this large a draw distance in a forward rendering engine. Here's another screenshot, this time during the day, and with buildings enabled.

City scene with sports cars on the roads during daytime.

I think we need more variety of cars. Back off to Google to find more 3D models... Okay, this looks better. Let's see, there are now six models: a police car, a white sedan, and three more exotic sports cars. I guess this is a city full of rich kids, and the police are needed to keep them under control. This is the set of six models out of the initial ~15 that passed the first quality filter. Some of these cars have minor problems with textures or normals, but are otherwise okay. And yes, if you look closely, the blue sports cars do have "Hot Wheels" painted on their hoods.

The cars come in various sizes and aspect ratios. I'm scaling them down to the same average size, but preserving the aspect ratio of the models. I use the same headlight, brake light, and turn signal locations for all models, based on the edges of the model's bounding cube. It makes drawing simpler, but the lights are sometimes outside of the car's bounds (especially for cars with curved front/read ends), or too high/low. I'll add several more screenshots below.

Police car making a left turn, viewed from above.

Various screenshots of cars driving on city roads and traversing intersections. There's still a lot of empty space between buildings that needs to be filled.

If you look carefully, distant cars are still drawn using cubes. I don't find this too distracting; at least they're colored to match the car models. Note that there are no car shadows, though traffic lights do have shadows. Cars can receive shadows, but don't cast shadows. This is difficult to do in an efficient way, considering the large number of dynamic models. If they were simple cubes like before, I could add their shadows pretty easily. Unfortunately, cube shadows look horrible with curved 3D models, and it's just too expensive to draw the entire 3D model of every car every frame for every shadow map. So for now I've left the shadows out. Maybe I can go back later and at least add simple dark areas under the cars due to ambient occlusion.

I really need to fill that empty space between buildings and roads with something. What can go here? Maybe parking lots? I could probably put some parked cars there, if I could find a good way to connect those areas to the roads.

Here is a different view showing cars on a long connector road, with a city in the background. The models are drawn tilted to match the slope of the road.

Cars driving on a long connector road between two cities, with a city in the distance.

This is another night time image, showing off car headlights and the glow of traffic lights in the dark. I hope the image isn't too dark to see. The sun and moon are both down so that the only lights are the faint ambient illumination, the car lights, and the traffic lights.

Cars of various types in a city at night. Hopefully this image isn't too dark.

Here I've increased the number of cars from 4,000 to 10,000 and removed the buildings to improve visibility. There are a ton of car models drawn, but they use LOD and this allows me to still get around 60 FPS. This also creates a lot of traffic congestion and related problems. This is probably too many cars to have in the current scene.

This is what you get when increasing the number of cars from 4,000 to 10,000. Buildings have been disabled again. I still get around 60 FPS in this case.

I recorded a video of cars in action, stopping at traffic lights and making smooth turns. You can see that everything works just as it does in the real world. Note that the video is sped up by 2x to make it shorter.

There are a lot of future work items for this post:
  • Add support for other vehicles such as trucks, buses, motorcycles, etc. (which requires finding new 3D models)
  • Fix the remaining problems with car collisions and traffic gridlock by improving the AI.
  • Add car shadows, or at least ambient occlusion.
  • Add spotlights for car headlights and make them shine on the roads, buildings, and other cars.
  • Add more city decorations: street signs, streetlights, benches, parking lots, bridges, etc.
  • Add parked cars as scenery.
  • Figure out how to make the car wheels actually turn.
  • Add support for multi-lane roads, and use a dedicated left turn lane to improve traffic.
I'm not sure how much of this I'll actually do, if any. This system works better than I had originally planned, given the amount of time and effort I spent on it. There are so many possible things I could be working on, considering the broader problem of populating the terrain with interesting content.

Bonus Update: I added ambient occlusion under cars using a single black quad and an opacity map texture with radial falloff.

Cars with ambient occlusion producing dark areas underneath.