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.