- 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.
- 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?).
- 3DWorld shader support for model animation and skinning.
 |
| 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)
 |
| 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.
 |
| 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.
Very impressive! So, do pedestrians still use crosswalks or not? It wasn't clear to me.
ReplyDeleteThanks! I have an internal option to control whether or not pedestrians use crosswalks. It's off by default because it tends to cause too many problems with big groups of people getting stuck against each other. There's still a special case that allows pedestrians to cross in more "risky" situations when they're near a crosswalk that's set to "walk".
Delete