Monday, February 4, 2019

Procedural City: Pedestrian Updates + Navigation

It's time to populate these procedural cities with people. I started discussing 3DWorld's initial implementation of pedestrians in the previous blog post. There I listed the next steps for developing the city pedestrian system. The two major tasks were model animation and navigation. I haven't really gotten anywhere with animation of human models yet. That requires the following three things:
  1. Access to 3D models of people with included animation data. These are difficult to find online, and I don't have the tools or experience to make them myself. 
  2. A way to read 3D animation data. None of 3D World's supported model file formats include animation. I have to either implement this myself from scratch or add a new third party library as a dependency (maybe assimp?).
  3. 3DWorld shader support for model animation and skinning.
Someone did point me to MakeHuman, which maybe could help with #1. I very quickly created a model of my daughter Katie to use in the city. I didn't put too much effort into setting the correct values for the dozens of different sliders. While the human model itself is good quality, there's a limited selection of clothing and other accessories. In particular, there are no shoes!

A 3D model of a girl created by MakeHuman. Sadly, there's no option for shoes. The lighting needs improvement.

MakeHuman does export animation data. Maybe I could use this if I ever solve #2 and #3 from my list. But so far, there's no progress on animation. That leaves navigation.

If you look carefully at the above image, there is a slight shadow on the ground at the girl's feet. I'm using small dark textured quads to simulate cheap/fake ambient occlusion for people. This somewhat makes up for the lack of shadows on moving objects. This is the same trick I used with cars. Maybe it would look better if I had a shadow at each foot, though that will surely cause problems if I ever add walking animations.

I also put a bit of effort into improving pedestrian movement. Each one is assigned a random base speed that serves as the maximum/typical magnitude of their walking velocity. Their direction vectors (the way the model is facing) will smoothly track destination position over time. Their velocity, in turn, will track their direction. This produces smooth turning motions rather than sharp turns when people collide or change destination locations. There's also a fast turn-in-place movement that can be used in tight spaces such as when they overshoot their target and have to turn back.


Navigation

I've mostly been working on pedestrian navigation within my procedural city these past few weeks. I would say that 80% of the effort has gone to this area. As expected, this is a challenging topic. I need to compute/update/maintain the path from the current position to a destination building in some other city block for 10 thousand pedestrians each frame. The path planning needs to take into account collisions with buildings, parking lots, parked cars, trees, benches, traffic lights, etc. It needs to dynamically adapt to collisions between two or more people. It needs to handle safe street crossings and collisions with dynamic cars.

It took a lot of work to put this system together. It was also very difficult to debug when things went wrong. I had people moving in circles, walking through buildings, standing in one place forever, shaking randomly/violently, etc. I had to put some work into implementing debug visualization for pedestrians. I started with a picking system where I could select someone with the mouse cross-hair and print their state as onscreen text, similar to what I did with cars. Here is an example of how this looks in-game. [Names are also procedurally generated by borrowing the planet/moon/star name generator from universe mode.]

Pedestrian state debug overlay for "Eoshod". Peds can be selected by the player cross-hair to show their internal state.

I decided that each pedestrian should choose a random destination building within their current city. It doesn't really make sense to have them walk between cities as there are no real sidewalks on the connector roads, and it would take them a very long time. The high-level navigation finds the shortest path from that person's current city block to the block containing the target building. This part is easy because the city blocks form a regular connected 2D grid. It's the same situation as car navigation. In fact, the roads and city blocks + crosswalks form a dual graph. The next block is always the closest one in the direction of the destination block. Once the person has collided with the target building, the destination is marked as reached and a new building is chosen in some other block.

The more difficult part of navigation is avoiding obstacles within a city block. Obviously we don't want to avoid the destination building, but the other buildings and city objects should be avoided. Ideally, we want to select the globally shortest path around all of the objects in the block rather than just avoiding collisions with the closest ones. To simplify things, I decided to use the axis-aligned bounding cubes of the buildings and other objects. In fact, since there are no overhangs, I can ignore the z-component (height) of objects and just check for collisions in 2D with the object footprints. As a further simplification, I place the objects to ensure there's at least a pedestrian width (or two) of gap between them. This guarantees that all obstacles are isolated rectangles and makes the problem much easier. The bounding rectangles are expanded by the pedestrian's collision radius so that collision checks can be performed with points and lines rather than spheres. This is approximate, but close enough for small objects such as people.

The shortest path is represented as a series of points, where the first point is the current position and the final point is the closest point in the next plot along the path to the destination. The path starts with only those two points. If the line connecting them intersects an object, there are two choices to make: either go around the object to the left or to the right. This is implemented as a standard recursive branch-and-bound graph traversal algorithm. For each potential detour around an obstacle, the four (x,y) corners of the bounding box are considered as potential new turning points. [The min distance path around a rectangle always goes through the corners.] The shortest complete (collision-free) path found so far is maintained through the recursion. If a candidate path exceeds that length, it can't be the shortest and is terminated. In the end, an extra pass is run to try to smooth and shorten the final path by removing any extra points.

After several ... dozen iterations, I managed to get it working well enough. In the process, I had to add debug visualization for navigation paths as well. Everything is color coded:
  • Yellow nodes for normal points along the path
  • Orange nodes for incomplete paths (path finding failed for some reason - mostly fixed now)
  • Green nodes for the destination point (building or next block)
  • Red nodes for blocked points (cars in the way)
  • Yellow lines for normal paths between nodes
  • Orange lines for the path across the road
  • Red lines for the path to the goal
  • Blue lines for the path of "retreat" (moving out of an invalid location such as the road or building interior)
Here is an example of a valid non-final-destination (block crossing) path shown for a selected pedestrian walking between some buildings. The yellow circles show the actual size of the collision sphere, which is larger than the model to allow for some error in movement.

Pedestrian debug path display. Path nodes and edges are shown for the selected pedestrian. Nodes and edges are color coded.

That took care of collisions with static objects such as buildings, trees, parked cars, and benches. Now I just had to solve the collision avoidance problem for dynamic objects: other pedestrians and cars. I started by detecting pedestrians that were too close and changing their direction randomly on collision events. This worked to keep the models from intersecting, but looked very strange. In reality, people don't just walk until they hit someone, then turn around and walk the other way. Well, maybe if they're on their phones and not paying attention. But I haven't added models of phones yet, so they better be looking where they're going. Real people see other people approaching and actively move to avoid them. This requires some sort of path prediction and avoidance using the positions and velocities of the people involved. I tried implementing something like this, but it didn't work very well, especially when more than two people were about to collide.

My second attempt used a gravity-based repulsion force to push pedestrians away from each other. The force became stronger as their separation distance decreased. When their distance reached the sum of their radii, the collision force moved them apart. This resulted in small forces that made people casually move to the side when passing each other, and stronger forces to make them suddenly dodge side collisions. The more difficult cases where this didn't quite work perfectly were direct head-on collisions and cases where a faster person ran into a slower person from behind.

Did you ever encounter a situation where someone was approaching you from the other end of the hall and you moved to avoid them? You go left, but they go right, and you're still on a collision path? Sometimes you play that dodging game with them several times before you finally manage to avoid each other. I ran into that problem here as well. My fix was to make the pedestrian with the lower SSN (unique ID) dodge and the other person continue straight. That seemed to work well enough.


Street Crossing

The next problem was handling cars. Fortunately, parked cars are easy to avoid, and moving cars are constrained to roads. This provides a nice separation between static collisions inside a city block and dynamic collisions in the roads between blocks. There are two pedestrian update states for these two areas of the city.

At this point, people were crossing the street whenever and wherever they got to it without "looking" either way. This often resulted in pedestrians and cars crossing through each other. Something like this image below. See that guy in the front left? The truck to his left just drove through him. We can't have this!

Pedestrians on city sidewalks and crossing roads (unsafely). The man in the front left by the police car was just hit by the truck, but apparently he survived. I guess he didn't look both ways before crossing. Don't worry, the police will handle it.

What makes this difficult is that pedestrians and cars are in two independent systems that are running at the same time in different threads. Neither one can really modify the other's state. The original idea was to use the traffic light and crosswalk system to control both the cars and pedestrians. This system is part of the road network and is updated somewhere else in the frame. In theory, if implemented correctly, everything would be safe and there would be no accidents. That's the idea anyway - model this after the real world where the government supposedly came up with all of these safety rules and systems.

The difficulty is getting all of the people to wait patiently in a group at the crosswalks. This results in a dozen people waiting on each side of the street as close as they can get to each other without colliding. Which isn't very close, because (remember that animation problem?) most of the models have their arms stretched out rather than at their sides. On top of this, the traffic light and crosswalk posts are in the way. I could move them back, but then the cars stopped just at the intersections can't see them. And there aren't actually crosswalks in the textures I use for roads anyway.

When the sign turns to walk, it's madness. Remember that repulsive force collision avoidance system? Well, it doesn't work well in this situation. The repulsive forces between the groups is too high for them to continue across the street. The two mobs on either side of the road end up swarming around each other and walking out into the intersections and among the cars stopped at the lights. It's not good to force them together into crowds. I'm not really sure what the correct solution is here. How do you get two groups of people (with their arms sticking out) to cross through each other without colliding? So far, I haven't figured that one out.

Maybe having pedestrians converge at crosswalks is a bad idea. Okay, fine. Let's ignore the unmarked crosswalks and have them all jaywalk in the middle of the road. Isn't that what people do in most cities anyway? They still need to look out for cars though, because the cars won't stop for them. In fact, the cars can't even see them; different thread, different "world". If they did, I'm sure I would be back to that gridlock problem I worked so hard to solve a few months ago in this post. Of course this is tricky, because we need to make the pedestrian and car systems communicate with each other without using the traffic light/crosswalk system as an intermediate. The simplest approach is to find the road that the pedestrian is about to cross, get a list of cars on this road, then determine if any of the cars will get to the crossing point before the pedestrian has gotten across. For now, I'm just going to ignore the thread safety issues related to how these two systems are running in parallel...

Wait, no, I can't do that. Maybe for internal development, but not for something published in the public domain. Writing this post convinced me to change it. Now the subset of cars that are non-parked are copied into the pedestrian manager before they're modified in the car update thread. The pedestrians now have their own copy of the cars in their "world." It's complex and slightly slower, but should solve the problem until I come up with a better idea.

I tried to implement this car search/query, but ended up with half of the pedestrians crossing in the path of cars and the other other half waiting on the side of the road forever. It was like some roads were always full of cars and some had none. Sigh. I had to add debug visualization for the third time. Here it is. These cubes represent the paths cars will travel on the road in question in the time it takes the pedestrian to cross. Slower people and faster cars have longer cubes. Cars stopped at lights have cubes that only extend slightly pas the car's collision cubes. Red cubes are for cars that are threats, and green cubes are for cars that can be ignored. Yes, they have to look in both directions. [Note that I've since cleaned this up but didn't want to bother taking a new screenshot since you won't understand the details anyway.]

Debug view showing predicted car paths for the road the pedestrian is considering crossing. Threatening cars have red paths and non-threatening cars have green paths. The red node (sphere) signals danger.

This way of predicting the paths of cars works in most cases - maybe 80% of the time. 80% is good but not great. These people must like to live dangerously. There are various situations where pedestrians still walk into the path of cars:
  • Collisions: Sometimes collisions with other pedestrians can push them out into the road. I've attempted to fix this by constraining them to the sidewalk, but this can cause them to get stuck in front of other pedestrians who are waiting to cross. They can't move until the others get out of the way. It keeps them out of the road, but looks ugly.
  • Collisions II: Sometimes pedestrians collide with other people who are crossing the street from the opposite direction. The collision response will make them turn to walk around each other. This works fine with a single pair, but when you have a dozen pedestrians crossing from each side it's chaos. They will all eventually get across, but this takes time. The crossing time is longer than expected and they may not all get out of the way before the cars reach them. I'm not sure what to do here. I could disable collision detection in this case and just have the people walk through each other, but it doesn't look good.
  • Cars Accelerating: Estimating whether or not a pedestrian has time to cross involves calculating the distance a car will travel in the time it takes the pedestrian to cross. It could be an under-approximation to use the car's speed if it's accelerating. It's more correct, but conservative, to use the car's max speed. So I made this change. I also made people cross the road at 1.8x their normal speed, which helps.
  • Cars Stopped at Lights: Sometimes a car is stopped at a light, and it looks like the road is safe to cross. Then, just as the person begins to cross, the light turns green and the car hits them. That's the point of crosswalks, if only the pedestrians would use them. The other way to handle this is to determine how long the car needs to wait at the light for them to cross safely. The traffic light can then be queried for it's state that amount of time in the future (this is how crosswalks work). If it's still red, the pedestrian can safely cross. This is fairly complex but seems to work.
  • Cars Turning: This is a tough one. Pedestrians can only query cars that are currently on the road they're about to cross. It's still possible that a car will turn onto the road and hit the pedestrian while he/she is crossing. It would probably be possible, though complex and slow, to also check for cars turning from roads that intersect with the current road. However, cars don't actually decide which way they're turning until they reach the intersection. If the light is green, they may not signal that they're turning until they've already entered the intersection, at which point it's too late for the person to turn back. I don't have a good solution for this one. Maybe in this case it should be the car's responsibility to avoid hitting the pedestrian.
There are some issues, but it works well enough for now. Maybe I'll get back to this later. Unfortunately, we still have to deal with traffic gridlock. If there's too much traffic it will get in the way of pedestrians who are trying to cross where there's no crosswalk. The cars will deal with it properly (after many many hours of work), but people can be waiting forever. Take a look at this image.

These poor folks are all lined up to cross the street. Unfortunately, considering the traffic on this main road, they could be waiting here for a long time. The girl who is slightly further out on the left side already started to cross the area of the sidewalk that borders the road.

Everyone has lined up along the sidewalk waiting to cross. The repulsive force collision avoidance system tends to produce nice lines of people. If the road is always full of cars, the lines will just continue to grow. Of course, this lining up on the sidewalk business doesn't always go as planned. Sometimes the kids don't want to line up nicely.

These twin brothers are holding hands waiting to cross. Or wait, maybe they're conjoined twins?

What happened here? Remember I said that when a collision was about to happen, only the person with the lower SSN would move to avoid the other? Well, this doesn't quite work if that guy is just standing there as he won't move out of the way. Where can he go anyway, out into the street? The solution here is to tag the other person with a special "collision" flag that tells him he's about to collide with someone and should change direction. This results in the other pedestrian probing along the line until a place is found that doesn't collide with anyone else. It looks a bit awkward, but does the job eventually.

I spent some effort trying to solve the gridlock problem where pedestrians were stuck waiting to cross for a long time. This is different from the situation I had with cars. Cars can't do much if they're stuck in traffic, other than changing their minds on which way they're going to turn at the next intersection. People, on the other hand, have plenty of space to move around. If they get stuck waiting too long (say 60s), they will choose a new path to their destination city block. The path chosen is the second longest - the shortest path that doesn't require crossing that particular street. This works, but can cause problems if the pedestrian is in the middle of a big group and can't get off the street and onto the sidewalk. In this situation, they jitter around until they either find a gap or someone else moves (crosses or gives up and leaves). Once again, this looks ugly, but will eventually resolve itself - typically when that blocking person's 60s timer expires. I haven't seen any cases where a pedestrian gets stuck somewhere for more than a few minutes.


Summary

Overall I'm pretty happy with they way pedestrian motion and path finding turned out, despite the various remaining problems. Some of these may get fixed in the future. I feel that people in my procedural city have a rich diversity of interesting emergent behaviors that come from these simple rules. [Well, if you consider 900 lines of code simple.] They can plan near optimal paths from the current location to a building on the other side of the city. They weave around both static and dynamic obstacles. They line up at the sides of the road and usually cross safely. As long as you don't get too many people into a small area, the system generally works well and produces believable behavior. Now all I have to do is fix the animation so that they look reasonable when viewed at a close distance.

You might think that doing all of this processing for 10,000 pedestrians would take significant CPU time, but it's actually not bad at all. All of this path finding, collision detection, and motion logic only takes an average of 3.6ms per frame. In addition, it's run in a separate worker thread at the same time as car update logic (~1.2ms in another worker thread) and city rendering (the main thread). This means that it has very little impact on overall frame rate. I can get frame rates as high as 150 FPS with all of the simulations running for every car and pedestrian in every city. The key to efficiently handling pedestrians is to only run the expensive path finding when necessary; for example, on a collision event, when the destination is reached, before and after crossing a street, and every so many frames for the nearby pedestrians.

That's it for now. I have plenty more to write, but this post is already long enough. I'll likely have a follow-up post soon with more on this topic. If you're interested in the details, all 3DWorld source code for pedestrians can be found here on GitHub.

Sunday, December 16, 2018

Procedural City: Pedestrians

I want to continue to add content to my procedural city to improve the realism. I've added buildings, roads, cars, trees, traffic lights, streetlights, benches, bridges, and tunnels. The most recent addition I discussed on this blog was crosswalks. Maybe you can see where this is heading? I'm currently working on adding pedestrians to my cities.

This appears to be quite challenging. I need to find models of people, and somehow integrate them into the city. I'm not sure if this is more or less work than adding cars. Here is a comparison:

+ I already have the 3D model import, rendering, lighting, and shadows system from cars.
+ I don't plan on having pedestrians on the connector roads between cities.
+ I probably don't need to worry about the gridlock problem with pedestrians.
+ Pedestrians are much smaller than cars, so LOD works better, allowing for fast drawing.
-  Free models of people are more difficult to find online, and are difficult to procedurally generate.
-  Navigation and path planning are more difficult since they're not constrained to roads.
-  Animation is required. This is a big one, I have no idea how to do this.

Okay, people are almost certainly more work than cars. Animation alone is a huge chunk of work. But it may not be significantly more time to implement, considering how long I was stuck on the traffic gridlock problem earlier this year.


Placement, Collisions, and Physics

I managed to get the easier tasks out of the way first. I started with pedestrian placement. 10,000 people seems like a good number to start with. It's slightly lower than the number of cars (4000 moving and ~3600 parked = 7600). Still, the city seems a bit empty. I may have to increase their number later, once I've optimized things a bit more. Or maybe I only need to generate and simulate pedestrians for the nearest city to the player, rather than all 8 cities at the same time. That would give me 10K per city, 80K total - 8x more. I'm not too worried about this part.

Pedestrians are currently confined the sidewalk areas between the roads and buildings. I have the crosswalk logic implemented, but I don't yet have pedestrian path finding and destinations, so there's really no need for them to use the crosswalks. For now, pedestrians remain in the blocks/plots where they were initially placed. Fortunately, there's a border between roads and building placement areas, so there's always space for people to walk between everything.

I've implemented collision detection between buildings, roads, trees, benches, and other pedestrians. It seems expensive to perform collision detection with parked cars, so I use the parking lots themselves as colliders. This may present a problem in the future if I have pedestrians getting into parked cars. People walk in a straight line with a randomly selected velocity until they collide with an object, then they turn away from the object and continue. I use a random turn angle that's oriented away from the object. The turning is smoothly interpolated to make it look more natural. This sort of motion looks strange, but will do for now. Collision detection takes about 1.6ms per frame for 10,000 pedestrians. This can be reduced if I'm willing to skip the physics update for distant cities.

I did have some problems where pedestrians got stuck in buildings and other objects. This tends to happen when two people collide and the collision resolution pushes one of them into a building. Then one of them would get stuck in the building because no direction change would get it back out. Resetting to the previously valid position also didn't work. So I added a stuck counter, incremented every frame where there was no movement, and when it reaches 8 the pedestrian is randomly moved a bit. This appeared to fix the problem. This situation rarely occurs after the first frame where the initial placement collisions are resolved, so the random movements aren't generally noticeable.


Graphics and Rendering

At this point I had yellow spheres that moved around within the city blocks with low runtime overhead and without getting stuck. That's a good start. The next step was adding proper 3D models of people. I went through the same online Google search process I used to find car 3D models. It seems to be more difficult to find free 3D models of people compared to cars. I did find one model that seemed to be pretty good. Here is how he looks when instanced into the city. (Sorry, no videos until I have the movement and animations working better.)

City with 10,000 randomly placed pedestrians. All are instances of the same 3D model of a man.

There are 10,000 pedestrians placed across the 8 cities in this map. Yet pedestrians seem pretty sparse in this image. I guess that shows just how large these cities are.

You'll notice that I haven't added shadows for these models yet. I don't have shadows for moving cars either. All I have are dark textures under the cars that give some fake ambient occlusion. It's too expensive to render these into a shadow map every frame. In fact, I would probably need to use multiple shadow map cascades here for good shadow quality, which makes it ever more expensive. So for now only the parked cars and other static (non-moving) objects are added to the precomputed sun and moon shadow maps for each nearby terrain tile. People do cast shadows in short rage dynamic night lights though (see below).

This model looks fine from a distance. It's quite detailed with a a high quality mesh and high resolution textures. However, when you get close...

Hello there old man. WHAT'S WRONG WITH YOUR EYES?!!!

Oh, wait, it's another problem with the material file. Let me try to fix it. I don't understand how people can spend all the time and effort to create a nice model, just to have the export process screw it up in some trivial way, and not even bother to fix it. Maybe it wasn't exported by the original creator. Is this version better? Now the eyes are almost back instead of gray. I think there's still something wrong, but I'm not really sure what he's even supposed to look like. I suspect the texture coordinates are wrong for the eyes. I also switched to the "clean" texture set where his clothes aren't all dirty and ripped. It's a nice touch that they added both sets of textures.

The clean, non-zombie version of that guy. The eyes still don't look quite right, but they're better.

The other four models weren't as good. One of them was low-poly, but I kept him anyway. One was too cartoonish, a woman with a head too large for her body. Two others had that strange arms-stretched-out pose I see often in 3D models of people. This is the common default position for models rigged for animation. I want to animate the legs while walking. I haven't even thought about animating arms, but it seems I have to just to fix these poses. These files I downloaded don't even have animation data, so I'm not sure why a user would want them in these poses. In fact, over half of the free models I found are like this. Here's a screenshot of what I'm talking about.

What's wrong with these people? Are they all high? Do they think they can fly? Are they zombies? Or are they just practicing yoga in the street?

Between the gray eyes and the outstretched arms, I think I have the basic props for a zombie horror scene. I just need to add some blood...

Here are some night time shots showing how people interact with streetlights and car headlights. They both cast and receive shadows, the same as cars. The shadows are pretty low resolution though. Since their models have fewer polygons than cars, this adds a minimal amount of rendering time.

This guy casts two shadows on that truck in the back center. The light sources are the headlights of the car behind me.

Multiple pedestrian models casting shadows on the sidewalks.

Model Animation

One of the next steps is model animation. I won't have time to implement this until next year. I'll be visiting my parents at Christmas time and won't be able to work on this while I'm there.

I'm not quite sure what I want to do about walking animations for these people. They certainly don't look quite right as they are now, sliding along the ground like cardboard props. There are several challenges here. First, neither of the standard model formats supported by 3DWorld (obj and 3DS) contain rigging or animation data that maps vertices to bones. These files are just a sea of vertex data, with no obvious way to even determine which vertices are the legs. I'm not sure what the best format to use is. Ideally I want a format that's text and/or an open format, rather than a proprietary binary file format. Maybe I can use assimp to import the models in one of those other formats. However, integrating another tool into 3DWorld is a lot of work, and will add a new dependency that I probably need to upload to my GitHub repo.

Can I procedurally generate animations? All I need for now is a walking animation. How hard can that be? I feel that I could do it for some simple generated cartoon model of a person, but it would be challenging to procedurally generated animations for a detailed 3D model created by someone else.

The second problem is finding high quality free models that include rigging and animations, in the format(s) I can read. It's hard enough to find free models of people online, and most of these don't have the required animation information. Maybe I just don't know where to look. Someone from Reddit suggested Mixamo, so I'll have to look into that site. I certainly don't want to have to create my own models. I'm a programmer, not an artist! Unless, of course, we're talking about making smiley faces like I currently have in gameplay mode.


Path Finding and Navigation

Another next task to work on is path finding and navigation. I went through this same process for cars. People need destinations. They usually walk around the city with purpose rather than walking in random directions until they bump into things. The question is, what should the destinations be? Randomly selected buildings would be good candidates, though buildings currently don't have any doors. Maybe I can have pedestrians just touch buildings and have that count as reaching their destination. Maybe parked cars can be another destination, though I would have to remove parking lots from collision detection to make that possible.

How does navigation work in a city? I suppose there are three parts: navigation within a block, within a city, and within the world (currently an island containing 8 cities). I only intend to handle the first two. People can drive their cars between cities eventually. Navigation within a city block consists of moving from the current location to the destination (building or crosswalk) without colliding with anything and using a reasonably short path. It's difficult to plan a path that takes into account collisions with other people, so the solution will need both static and dynamic parts.

I'm not sure if I can get away with people walking in a straight line while avoiding collisions with nearby objects. There could be cases where someone would get stuck in a dead end path between objects. It's more likely I'll need to implement waypoint graphs or navigation meshes for my AIs, maybe with the A* algorithm. I already have a waypoint system for the smileys to use in gameplay mode. I'm not sure how well it will work in a city. Navigation meshes may be a better solution here.

Once I have navigation working within a city block, I need to add navigation between blocks. These paths will use crosswalks to cross the streets that separate blocks. Since the city is a uniform grid with crosswalks on every interior street intersection, pedestrians can use any sort of Manhattan path to their destinations. It's the same system I use with cars, just using the spaces between roads as graph nodes rather than the roads themselves.

One potential issue is avoiding collisions between pedestrians and cars at crosswalks. As long as pedestrians cross fast enough, and don't begin crossing when the light is about to change, I shouldn't have to worry about that case. However, I still need to handle cars turning right on red lights. In the real world, it's mostly up to the drivers to watch out and not hit pedestrians when making turns. So I'll do the same in 3DWorld. Pedestrians can set a flag on the intersection telling it that they intend to cross at the crosswalk. Then cars can check this flag before making a right on red. This is a clean solution because it allows the cars and pedestrians to communicate through the intersection, allowing them to be independent of each other.

That's it for now. I'll post another update if I ever get animation or path finding working. For those of you who are interested, the code for pedestrians is on GitHub.

Saturday, November 17, 2018

Updated Planets

I'm taking a break from my procedural city to work on a variety of other smaller projects. I found an interesting planet generator created by colordoge and posted on Reddit and GitHub. I liked the look of these planets, so I asked the author what noise functions he used and tried to do something similar in 3DWorld. He later shared his source code, but by that time I had already figured out what he did. This led to some updates to the universe mode planet shader used to draw most of the rocky planet types. [Actually, all planets use a single shader, so I really mean the rocky planet control flow path.]

I decided to include domain warp noise to produce a more interesting planetary landscape. This was the major difference between our planet generators. I added domain warping to my 2D ground mode and tiled terrain heightmaps last year, so it makes sense to extend that system to 3D for planets. It was straightforward to extend the 2D noise function to 3D. I definitely think these noise function changes improve the variety and realism of planet terrains.

However, these changes do come with a cost of increased GPU draw time, which lowers frame rates. I see a frame rate reduction of around 400 FPS => 160 FPS for close-up planet views like in the screenshots below. This is acceptable for a single planet, as 160 FPS is still good enough for my graphics card. This could be a problem on lower end cards though, or in cases where multiple planets are very close together. Maybe I need to add some sort of graphics quality option to enable this new mode.

Here are some screenshots. Note that planets are drawn from vertex data forming simple spheres. Planets with atmosphere are drawn as flat spheres in multiple passes for the atmosphere, clouds, and terrain+water. Other rocky planet types use a tessellation shader to perturb the sphere vertices, producing a true 3D surface heightmap. I found that perturbing the heightmap caused problems with atmosphere rendering, which is why it's disabled for planets with atmosphere.

Procedural Earth-like planet with atmosphere, oceans, clouds, and ice caps. A small moon is visible on the left.

Closeup of the planet showing normal mapped terrain, cloud shadows, atmospheric lighting, and specular ocean reflections.

Here's another planet with multiple moons. This one is larger, with a thinner atmosphere and cloud layer, but higher noise frequency and more continents. All of these parameters are procedurally generated, producing quite a variety of planets. I chose to show Earth-like planets because the contrast between land and water makes it easier to see the noise patterns.

Another larger procedural planet with smaller oceans, lighter cloud cover, and thinner atmosphere.

Procedural moon with some water. A planet and another moon are seen in the background.

A third Earth-like planet. The bright area of ocean looks like the Gulf of Mexico, but it's actually procedurally generated.

This was a pretty simple change, though it required a few hours of parameter tweaking to make it both good looking and fast. I did run into some problems with floating-point precision - or rather texture lookup precision in the fragment shader. The problem was with the lower noise octaves where a large portion of the planet's surface mapped to a single texel of the noise texture. Apparently GPU texture sample points and interpolation use 8-bit fixed point math, even if using a 16-bit or floating-point texture. This took me hours to figure out. This appears to be a hardware limitation of the texture samplers and not something that's well documented or easily fixable.

In the end I had to work around the problem by adding manual texel interpolation to my shader. This made it much slower as it increased the number of texture reads by a factor of 4. I recovered some of the performance loss by reducing the number of noise octaves from 8 to 4 for the domain warp texture lookup. I was also able to get away with only using this manual interpolation for domain warping and keeping the faster hardware texture interpolation for the main noise function, where it made less of a difference on image quality. Overall, I feel the increase in quality justifies the reduction in framerate.

Saturday, October 20, 2018

New Procedural City Features

I've been working on several different 3DWorld sub-tasks over the past few weeks. Some of them are directly related to my procedural city, and others aren't really related. However, I can still put a city in the background when presenting these changes. Here are some short descriptions and screenshots showing the improvements I've made.


Benches

I finally got around to adding benches to some of the empty spaces between roads and buildings. I copied the bench model I manually created for the office building scene rather than downloading a free online model this time. This is basically just a big table of numbers representing the coordinates of eleven cubes and one extruded polygon for the back of the bench. I haven't implemented support for reading my 3D text scene file format in the city framework yet, so I hard-coded the coordinates into the source code. It works well enough for this simple object.

The max number of benches per plot is specified in the config file. The placement algorithm selects this many random locations as candidates for bench positions. If the location is valid (nothing else is placed there), a bench is added in the orientation that faces the nearest road. This placement system has been generalized to allow the addition of any future type of 3D model. A simple bounding cube collision model is used.

Here is a night time screenshot showing a bench placed under the streetlight by the side of the road. Additional benches can be seen in the background. Benches, along with almost every other city object, both cast and receive shadows. I particularly like the warm lighting achieved by the postprocessing bloom effect in this image. The yellow car appears particularly bright.

A city bench placed by the side of the road under a streetlight. Other benches can be seen in the background.

Trucks

I've had "add trucks and other larger car models" on my city TODO list for a while. The main reason I haven't added them until now is that it's difficult to find free truck models online. Car models are plentiful. I was able to find all ten car models I had up to this point in less time than it took for me to find a single truck model. I even signed up for an account on a 3D model website, just to find that I couldn't actually download any models with the free account! I found this one low-poly truck model and decided that it was good enough to use. Here is is:

A new box truck has been added to the set of randomly selected car 3D models. It's self driving (no human driver).

I had to add support for variable sized vehicles to make this work. Without that change, the truck was the same size as a car and looked very strange. I was expecting this to take a lot of effort and require a week to get right. It seems like everything related to cars is like that. Remember how long it took me to solve the traffic gridlock problem? I was surprised to find that all I had to do was multiply some numbers by a scaling value and it ... just worked?

Well, that's not too surprising. Car size was always a per-car variable in the code. I had started with cars of randomly +/- 10% size difference back when they were simple untextured boxes. Once I added 3D models, that randomness didn't look right, especially when two identical models of the same car were next to each other and different sizes. So I removed the random values and made all cars a constant size. There was a variable, but it had the same value for all cars. When I changed the size to add larger trucks, the size handling still worked. Now that variable has two values that differ by 1.6x.

I suspect there are still minor problems with trucks. For example, they may stop at the wrong place and block intersections, use the wrong acceleration/braking, or leave the wrong amount of space between them and the vehicle in front. I haven't actually seen any of these problems though. Maybe they only show up in rare conditions such as when two trucks are adjacent to each other while waiting at a traffic light in a heavy traffic area. I'll have to let the simulation run for an hour sometime to see if any problems turn up.


Crosswalks

I added crosswalks to city intersections the day I came up with the idea. No, I still don't have pedestrians. Maybe some day I'll add them, though I'm sure they're much more difficult than cars. Considering how much trouble I had with car navigation, I'm afraid to think about adding people. Plus I don't want to have to find dozens of unique models of people online. (I don't have the tools, time, skills, or patience to create them myself.)

Anyway, crosswalks consist of those typical walk/don't walk signals at most of the intersections. In the case of 3DWorld, they appear at all intersections except for some of the 2- and 3-way ones along the edges of the city where they're not needed. Crosswalk signals are tied into the traffic lights so that they allow safe walking when cars are stopped at red lights. They have the expected three states: walk (white), don't start walking (flashing orange hand), and don't walk (orange hand).

These signals are attached to the sides of existing traffic light posts. They produce emissive light that's only visible from a narrow view angle facing the player, just like real crosswalk signals. Here's how they look in the city.

Intersections now have crosswalks that are tied into the traffic light system and change between white/walk, orange flashing hand, and orange hand (don't walk).

I believe the white car on the left has just made a right turn on red, which is why it's in the crosswalk. If I add pedestrians I'll need to handle this case. Either cars need to check for pedestrians before turning on red, or pedestrians need to check for turning cars before crossing. Maybe both.


Destruction

I made all weapons destroy cars. This includes the baseball bat. Car explosions don't hurt the player, so you're free to walk up and bash them. Note that these are self-driving cars and there are no people. If you don't believe me, take a look in the car/truck windows in some of my city screenshots. There's no driver!

Cars explode when hit with a huge baseball bat. They explode when hit with pretty much any weapon/projectile.

I still haven't made buildings or other city objects destroyable, and I haven't made cars react to explosions. Those are future work items.


Lava

Okay, lava improvements aren't really related to procedural cities. They don't actually belong here, but I'm going to add them anyway to avoid having to create another short post just on lava. I can justify these screenshots in a city post by adding cities to the lava scene. Or adding lava to the city scene, if that's the way you prefer to think of it. Something like this:

Procedural city with orange lava flows in the background.

That last screenshot had lava in the background. Here's one with a closeup of lava and the city in the background instead. The surface of the lava is emissive and somewhat reflective, similar to water. In fact the lava and water use the same C++ code, they only differ in the fragment shader. I use a tessellation shader to generate waves on the lava, and the red-orange texture is animated over time. This produces a moving lava flow effect. Spherical bubbles form in the lava and release steam, which rises into the air. In addition, there's a heat haze postprocessing effect that distorts the scene when the player is near the hot lava surface. You can see how the city appears wavy in the distance.

View from above the lava surface, with a city in the background. There is a wavy heat haze screen-space shader effect.

Here's another shot of lava in a sandy area of the terrain from a bit higher up. The lower gray clouds are steam, and the larger, higher white clouds are ... normal clouds.


Another view of a lava pool with bubbles and steam clouds rising from the surface.

This is proof that cities don't have to be placed in the typical grassy + hilly terrain I've shown them in for every other blog post. Cities can be placed in any user-defined biome. They can be in the mountains, the plains, a dense forest, a desert, a rock pile, or on a hot lava planet. Temperature, vegetation, atmosphere, water level, ground composition, etc. are all independent config variables. It's all configurable in the scene text file.

Saturday, September 29, 2018

Tiled Terrain Weapons and Physics

I finally got around to implementing some weapons and physics effects in tiled terrain mode. I currently have projectile intersections with the terrain and explosion effects working. Laser beam, shotgun, and M16 shots hit the terrain at the correct points. Bouncy balls can be thrown at the terrain and will bounce and roll properly. Rockets fired will hit scene objects and explode. Object physics includes gravity, air resistance, static and kinetic friction, wind effects, momentum, and elasticity.

Here is a video showing ball (sphere) physics and collision detection with the terrain. Cities are disabled for this test, leaving empty city roads and plots. I made the bouncy balls huge for these videos so that they're easy to see from a distance and from between city buildings. The large balls in this video are 9.6m (31 feet) in radius.


Who here remembers Mr Yuck, the green face I'm using as a texture for some of the balls?

Here's a video showing balls, rockets, and grenades colliding with and bouncing off city buildings. Note that collision with cars, streetlights, and traffic lights is also enabled, but is difficult to see with these huge balls. Collisions currently have no effect on the city elements.

Sorry, the video is playing back too quickly. Drawing all of the buildings, cars, grass, etc. at the same time as realtime video capture and compression couldn't quite keep up with my target 60 FPS recording rate. I disabled some unnecessary effects such as water reflections for the later videos. [Yes, there is water, but it's all behind the mountains and not actually visible. The occlusion culling has a hard time on this high frequency eroded terrain.]



After recording this video, I noticed that the collision detection isn't correct for some of the oddly shaped buildings. I fixed the problems and recorded another similar video. I even added some bouncy plasma balls near the end. Here it is. If you're going to read the text but only watch one of these videos, this one is probably a better choice than the one above. I have them both here to show my incremental progress.



Here's a video of me throwing cluster grenades into a city. Note that the buildings, cars, etc. aren't yet destroyable. That will be shown later in this post. Also, I haven't yet had a chance to add dynamic lighting from weapons to cities (or tiled terrain mode in general).

The thousands of grenade fragments collide with and land on the buildings. If you look closely you can see the bright particle trails of the glowing fragments. You might have to pause the video to see these clearly. This is a new graphics feature that I added while working on tiled terrain physics that's built on top of the laser beam drawing system.



Here I've added fire and more smoke. Fires burn at the terrain height, which in this case is at the elevation of city roads and plots. They don't climb up buildings like they do in regular ground mode gameplay. I might add something like that later. Smoke also isn't affected by buildings like it is in ground mode.



I didn't record any sound for these videos, but you'll be happy to know that this test is full of explosion sounds, especially in the one below.

Those explosions are nice, but they don't have any effect on scene objects. They're purely visual. Let me make those cars destroyable with zero hit points. One hit and they explode. In fact, blast radius damage can destroy multiple nearby cars in one hit. There, that looks better. Unfortunately, I forgot to re-enable building shadows in this video.



As you can see, cars don't react to other cars exploding around them. They just drive up to fill the empty space left by the exploded car, which leaves no debris. Maybe I can have cars react to explosions as a future project. I'm not exactly sure what they would do. Maybe ignore traffic lights and try to drive away from the player or explosion as quickly as possible? If I ever add people to my cities I can have them get out of cars and run into nearby buildings. That works for them, until I figure out how to make buildings destroyable.

I would say that this solves the traffic gridlock problem. Just destroy cars when they get stuck and block intersections. Except, I think I finally solved that problem with a combination of other tricks from the previous blog posts. I could write a whole new blog post about that - but I'm not sure how many of you want to read another long post on the topic of traffic. And I'm not sure I have the patience to write one this week. I'll throw this shorter low-text post here to give everyone a break.

Monday, September 17, 2018

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!

Monday, September 3, 2018

Car Navigation Update

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.