Procedural City: Secondary Buildings Update

I'm still working on secondary buildings for 3DWorld's procedural city. I've made various minor improvements since the last post:

• Added porch roofs to some houses.
• Added garages and sheds to some houses.
• Made the antennas on building roofs pointed and darker.
• Reduced building draw time by more than 2x.
• Various minor fixes to house placement and drawing.
• Added logic to keep buildings from overlapping user-placed 3D models.
• Added logic to keep buildings from being placed over the player start location.

House roofs and porches are simple geometry added to the building models. Porch roofs consist of a small, low roof placed about halfway down on the inside corner of L-shaped houses, plus a thin vertical support cube. Garages and sheds are really the same thing. These are additional smaller cube structures placed separate from the main house for L-shaped houses that may or may not have windows. The random number generator is used to choose sizes and placements of these objects. Here are some images showing examples of these new features.

House with covered porch (front) and house with shed (back).

House with garage (left) and house with covered porch (right).

I made a few changes so that user-placed 3D models interact correctly with buildings. The most important change was to prevent the building placement algorithm from placing a building that overlaps the XY bounding box footprint of any 3D model. Collision detection (for the player) somewhat works with models placed in tiled terrain mode. 3D models already project correct shadows onto buildings and themselves. However, buildings don't project shadows onto models yet. This is difficult due to the transformed coordinate space of the models, and the fact that models can be larger than terrain tiles. This limitation forced me to choose a model that was larger and higher than the buildings.

A Ferris wheel seemed like a good fit. It took a while to find one online that was free, in a file format that 3DWorld supports (obj and 3DS), and didn't have any issues. The model I used has no textures, so it's completely white. Well, I suppose that's pretty common for a Ferris wheel. They tend to be mostly made of white painted metal. It looks a bit odd though, because the cabins, base, and and smaller details aren't textured. Maybe I can add colored lights to it later. That would actually look pretty good at night. Anyway, here is what the Ferris wheel looks like when placed near a city.

Ferris wheel model placed in the city scene with interesting shadows. Buildings avoid overlapping it.

Note that the model flattens the terrain underneath it just like buildings, producing a depression around it's bounding box. There are no buildings overlapping the Ferris wheel.

There's quite a lot of geometry in this city scene now. We have the terrain, buildings, grass, trees, clouds, benches, roads, bridges, tunnels, cars, pedestrians, and placed models (the Ferris wheel). Here's a wireframe screenshot showing the high geometric density of the scene.

Wireframe models of Ferris wheel, buildings, city grid, terrain, and grass showing geometric complexity.

The grass blades seem to produce the most geometry, with a few million grass blade triangles in this view. There are about 250K triangles in the Ferris wheel, about 2M triangles in the terrain, about 500K triangles in the buildings, and maybe a few hundred thousand triangles in everything else. Many of the objects have occlusion culling enabled, which improves draw times. Both the terrain and buildings can act as occluders. I get almost 100 FPS (frames per second) on my GTX1070 for this view.

Procedural City: Secondary Buildings

I've done a lot of work and written quite a few blog posts on 3DWorld's procedural city. Most of these showed my group of 8 cities filled with office buildings, along with a network of connector roads, bridges, and tunnels. The space between the cities was mostly filled with grass, rock, and dirt. It's time to fill that empty space with secondary buildings.

The procedural city system is split into the city part and the buildings part. The city part handles city plots, the road network, traffic lights, streetlights, cars, and pedestrians. The buildings part handles ... buildings. These two components interact with each other through an API. The city generation control flow works as follows:

1. Choose mostly flat areas of land for rectangular city plot locations.
2. Level the terrain under each city location and remove (technically forbid) vegetation.
3. Divide each city into a grid of roads, intersections, and "blocks" for building placement.
4. Attempt to connect each city to each other city by a set of roads using a road cost function.
5. Place traffic lights in intersections and streetlights along roads.
6. Place buildings in each city block.
7. Place secondary buildings around the city. [New!]

The city generation algorithm provides parameters to the building generation module. I wasn't able to easily add secondary buildings outside of the city using the same building generator used for cities. Instead, I had to add a second building generator class to handle generation, drawing, and collision with secondary buildings. There are config file variables to set the placement area, sizes, densities, and types of secondary buildings for the scene. This set of variables is independent of the city/city building parameters.

I decided to only place secondary buildings in the flat-ish area in the center of the island map, surrounding the city sites. There are a total of 1625 city buildings and 12,660 secondary buildings. If I placed buildings over the entire island there would be about 25,000 of them. However, the edges of the island has a mix of water and mountains, and the resulting scattered buildings don't look very good. In addition, I get a few buildings on some of the tiny islands off the coast.

Building generation is very fast. It takes about a second to place and generate these 14,285 buildings. Compared to the 3.2s it takes to load the 64MB heightmap PNG image, that's pretty fast. In fact, most of the city scene load time is reading and setting up textures.

One of the most expensive parts of building generation is placement. For each building, the terrain height at the center point is used for the foundation height, and the terrain under the building's bounding cube is leveled to that elevation. Buildings aren't placed when the terrain is underwater or too high in altitude.

Here's a screenshot of some cities with secondary buildings placed around them. I've expanded the city rectangles and connector roads and marked them as keep-out areas for buildings. Buildings are placed with some separation between them for future addition of local roads. I started with random building orientations, but that didn't look quite right compared to the Manhattan orientation of the city buildings. It also produced some artifacts when flattening the terrain under each building. So I left them un-rotated instead.

Procedural city with surrounding secondary buildings, shown during the day.

I changed one other aspect of these brick and concrete block buildings. The windows are now stretched to fit the sides, which avoids partial/clipped windows and windows that wrap around the sides of the buildings. This was tricky to get right, but worth the effort.

Here's the same scene shown at night time. Buildings have randomly lit windows, which makes the cities feel more alive. Windows are actually drawn on top of the wall geometry in two additional shader passes, one for base windows and another for window lights. These windows add more detail and realism to the otherwise empty brick and block walls. Since they're made from special generated textures rather than geometry, they're very cheap to draw.

Procedural city with secondary buildings shown during the night.

Houses

I added a new class of building: houses. Houses are generally smaller/lower, and have sloped rather than flat or beveled roofs. They come in several geometric forms:

• Simple cubes (+ sloped roof)
• L-shapes (+ orthogonal roof sections)
• Side-by-side large + small sections
• Two adjacent cubes of different sizes (like a duplex)

Some of these house building types can be seen in the screenshot below.

Houses with sloped roofs and 1-2 sections (L and I shapes).

These buildings seem too large to be houses though. They look more like apartment buildings. That's fine, my city can use some apartment buildings too. After taking this screenshot, I went back and added config file options to generate houses of variable sizes. This produces a mix of smaller houses and larger apartment buildings. Take a look at the new mix of buildings.

Some houses are smaller than other building types. Maybe they have too many windows though?

That's better, but the houses still look a bit large. More specifically, they all have at least two floors, and most have at least three floors. There are no single story houses. Maybe the windows are too small and close together? Well, windows are about the right size when these buildings are compared to the office buildings in the city plots. I think the problem is that they're too tall. Most houses are shorter in height than their lengths/widths, especially when excluding the roof. That's the problem here, the roof it added to the base height of the house rather than being included as part of the height. That's a bit difficult to fix, given the order in which these building parts are generated. Instead, I'll just decrease the height of houses by a random amount. A house height scale factor of 0.6 to 0.8 seems to work well. Here is what I get now:

A mixture of secondary buildings and houses, with houses made a bit shorter. Some of them are single story now.

That's better. There are some single story houses mixed in with the larger ones. This looks improved, but now the grass appears to be too large. However, that's an issue to deal with another day. If you don't like the look of the grass, it can be disabled and replaced with a grass texture on the terrain. That type of grass is faster to draw anyway.

 Another view of houses and other building types.

Here is a night time scene showing a mix of larger buildings and houses with some lit windows.

Larger buildings, smaller buildings, and houses at night, with some lit windows.

That's pretty good for the first pass. I'm sure I can improve on houses later. I would like to add more variety to their geometry/architecture. In addition, it would be interesting to procedurally generate doors, porches, garages, sheds, fences, etc. Also, I can't forget roads. I'm not sure exactly how I'm going to connect all of these different buildings to the rest of the city road network, but it's a good future work item. I haven't yet decided if I want to allow cars and pedestrians in these areas.

Rainbows

Last week was rainy. On my way home in the evening I saw a bright double rainbow in the sky. It made me wonder how the physics of a rainbow works, so I looked it up online the next day. Rainbows are visual artifacts formed by the refraction of light through water droplets in the air back to the viewer. They span a viewing angle from 40 degrees (violet) to 42 degrees (red) around the viewer's field of view in the direction opposite the sun. There's sometimes also a second rainbow from 50 to 53 degrees, called a double rainbow. Rainbows aren't in any real physical location, they're more like projections onto the cloud/mist in the distance.

I'm not aware of any other games that display realistic rainbows, so it seemed like something interesting and unique to add to 3DWorld. I implemented a rainbow as a quad projected opposite the sun, where the colors are generated in a fragment shader as a function of radius using a color spectrum that I matched to images. This is both fast and close to physically accurate. 3DWorld only draws rainbows in the cloudy period after the rain has stopped, during the morning and evening times when the sun is low in the sky. The brightness of the rainbow is determined by integrating along the view ray using the depth buffer. The places where the rainbow falls over distant objects appear brighter than locations where there are nearby objects. Here is a screenshot:

Physically based rainbow drawn in a fragment shader. Those small black specks in the sky are birds flying in flocks.

That looks pretty good to me. It appears to blend correctly against the trees and mountains, and reflects in the water. If you look closely you can see that the center area inside the rainbow's color bands is slightly brighter. I suppose this rainbow looks a bit too perfect though, maybe because it has a nearly constant brightness against the clouds. I could probably add some random intensity variation to improve the realism. Also, I'm only drawing a single rainbow, not a double rainbow. I think the single rainbow is enough for now.

Pedestrian Animation Update

This is a quick update. I made some improvements to 3DWorld's pedestrian walking animations that were introduced in the previous post. I've added a knee joint to go with the hip joint on each leg. This looks much more natural than any of the strange animations from last time. I'm still applying the exact same animation code to all three models.

It's not perfect though. Some of the models have their legs spaced out too far for a casual walking animation. Also, none of their arms move. Real people swing their arms at least somewhat while walking, and also move the other parts of their bodies a bit. Still, it's good enough for now. I've gotten the basic animation down. That's 90% of the way there with 10% of the work.

I'll continue to add new models of people, improved walking, and new animations in the future. In fact, I've already added one new model of a man since recording this video. The model looks good and has high quality textures. However, the animations don't quite work because the area between the bottom of his shirt and the top of his pants stretch in an unnatural way. I'll get back to it later.

Once again, the code can be found here in my 3DWorld project on GitHub.

Procedural City: Animating Pedestrian Models

I finally got around to experimenting with adding animations to the 3D models of people in my procedural city. I ended up doing something pretty simple that at least looks better than no animation at all. Before I get into the details of what I tried, let me discuss the problem statement in more detail.

I've decided on the following constraints to pedestrian animation in 3DWorld, listed starting with the most difficult:

• Must use free models found online (since I don't have the time/patience/skills to create them myself).
• Must be done without buying or installing any fancy 3D content creation/animation tools.
• No art skills required.
• The same animation system must work with multiple models from different sources in different formats.
• Must scale to a few hundred animated models of people with ~10k-50k triangles each.
• Something that can be done in a few weeks or less.
• Should look better (more realistic) than no animation at all. I sure hope this is the case!

That seems like a real challenge for creating high quality animations. I suppose the standard flow would be to join a 3D model website where I can download models of people with animation data. Then either use a third party model/animation loading library, or write this part myself. Then implement the animation system in a special shader with a lot of CPU side code support. That would be a lot of work and could take more than a month of late night programming. Is there an easier system that I can use to get started, one that works with the models I already have?

Let me throw in some simplifications/trade-offs that should make this problem easier, at the cost of reduced quality and realism.

• I only need one simple walking animation.

That's a start, but it doesn't help much. How about:

• Only the legs need to move. We'll just leave their arms sticking out to the sides for now.

 Okay, that's a bit easier, but still seems like a lot of work. Let's do something silly to really simplify things:

• Only the hip joints are animated.

Yeah, I know, it's not going to be the greatest walking animation. But hopefully it will be better than no animation where people appear to slide on the ground or ride on invisible roller skates. What's the worst that can happen? Take a look and see - but don't judge it until you see the end. I started with some simple test animations.

The video shows me cycling through the various animations, which are named in white onscreen text. In case you didn't catch it, the animation names are: "The Slide", "The Bunny Hop", "The Flip", "The Twirl", "Marching", "Walk Like an Alien", and "Walking". The vertex shader code for all of these can be found here in my 3DWorld GitHub project. Sure, all of the animations look at least somewhat silly. That's the point, right now I'm just experimenting. I'll bet you laughed at the alien walk animation; I watched the video three times so far and laughed every time! That alien walk was actually one of my first attempts at rotating the legs at the hip where I was incorrectly scaling the hip location by the height of the model.

[Bonus: The pedestrians are actually crossing the roads safely and not getting hit by cars.]

The final walking animation doesn't look too bad. In fact, it looks almost normal when viewing pedestrians from a distance. It looks like someone walking very stiff-legged without bending their knees up close. I feel it's definitely better than no animation at all. I'm sure I can work to improve it, but I'm surprised at how good it looks already with so little work. All of this took only a few hours this weekend, and at least half the time was spent adjusting constants and transforms in the shaders. That's definitely time well spent. I didn't have to download new models, install 3D modeling tools, add new dependencies, parse a new file format, or implement a new shader flow. I'm not sure why I was so worried about this originally.

How did I implement this animation feature? There are in fact no animation files, no bone weights, no transform matrices. I'm passing the static model vertices that are loaded from disk straight to OpenGL for rendering. All of the magic is in the vertex shader, which applies transforms to the individual mesh vertices using a procedural algorithm. I suppose this is how procedural animation works.

The various body parts can be identified from the sign and magnitude of the (x,y,z) coordinates of each vertex. X = left/right, Y = up/down, and Z = front/back. The sign of the x-value will tell you which side (left or right) of the body you're on. Normalized y-values near 0.0 are the feet, and values near 1.0 are the head. This allows the shader to, for example, alternatively rotate the left and right legs about the hip by looking the the x and y values of each vertex. The hip joint is located around y=0.4 in all three models.

Each pedestrian has an animation time value. This time is reset to zero when stopped so that their body has a neutral (default) position. As each person walks, their animation time increases based on the product of velocity and elapsed realtime, producing a smooth animation timeline while in motion. The faster the person is moving, the faster the animation plays. A combination of fract() (fractional component) and sin() are used to turn linear time into a periodic walking cycle.

There's one thing wrong in the video. Can you spot it? The rotations I'm applying should also rotate the vertex normals. Without this, the lighting on the models is incorrect. I need to go back and fix that. Do I simply rotate the normals using the same matrix? [Update: It's fixed, but I didn't record a new video yet. Apparently you do just apply the same matrix to rotate the normals.]

I'll continue to work on improving pedestrian animation. It should be straightforward to add additional joints in this way. The knee joint is probably next to add. This a very slow and tedious way to put together animations, but it does require minimal code, and it works the same with all the models I have. Once I have enough models, it will probably be less work to add animations this way that it would be to animate each individual model using a real animation tool.

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.

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.