Pedestrian Zombies - Gameplay in Cities

It's been a while since I worked on city outdoor elements. The past few months I've spent mostly working on building interiors. It's time to get back to gameplay and make zombies chase the player outside of buildings and in city streets. But first, I need to familiarize myself with how pedestrians work and fix a few things in the process.

Pedestrians currently ignore the player. There isn't even collision detection; pedestrians and the player walk right through each other. I really should fix that now.

Let me see. I remember adding collision detection between cars and the player awhile ago. Cars can push the player around on roads, but they don't make any attempt to avoid hitting the player. That sounds like a good place to start. I changed cars so that they'll quickly stop if the player is in their path, and sometimes honk their horn. This uses logic similar to the car pedestrian avoidance system. The silly player pushing effect is gone.

Now I'm ready to work on people using similar logic. I can put the player proximity check in the code that has the loop over nearby pedestrians, and even include collision prediction and avoidance. This is the system that looks for a future collision by checking for intersecting paths between the target person and nearby people using their current speed and direction. A detected intersection causes a repulsive force to be added perpendicular to the move direction that changes the pedestrian velocity and orientation, moving their path and avoiding a collision.

I tested this out on the player, and it appears to be broken. People sometimes misbehave by walking in random directions, or continue to walk into the player. I guess I was never able to make this code correct because it was too difficult to set up a controlled collision experiment between two people. But now I can! I can control the player and position him in exactly the right spot to trigger the failure repeatedly. Then I can add all sorts of debug printouts; it's actually easier to debug because the player's velocity is zero. It turns out that the bug was mostly due to a sign error, which was easy to fix. Now person collision avoidance ... almost works. Here's a video I recorded after the first pass fix.

There's still a problem when the pedestrian is near an edge of the sidewalk and the collision avoidance pushes them into an invalid area. This can either be the road or a neighbor's forbidden private property, which starts a few feet from the sidewalk. When this happens, leaving the valid area is considered a different type of collision and triggers a turn and direction change. You can see that near the end of this video. The pedestrian can sometimes turn back toward the center of the sidewalk and collide with the other person (or player) again. It's better than it was, but still not perfect.

The next step in the fix is to limit the turn angle. If I can have a repulsive force smoothly push a person away from another person, I can use a similar force to push them outside an invalid area. It's not critical that they turn immediately in most situations. These checks are really only to keep people from walking into the road and getting hit by cars, or straying into someone's yard and getting stuck on a fence, wall, or hedges. There's quite a bit of buffer room to the sides, so it's okay to leave the sidewalk slightly. They can return as soon as the colliding pedestrian has passed them (since pending collisions are almost always from two people walking toward each other).

In reality, this whole debug and fix process took many hours with multiple small fixes and a dozen failed attempts at fixing it. Fortunately, I did eventually get it working. (More on this at the end.) Time to move on.

The next step is to have zombies chase the player in outdoor areas. I already have people turn into zombies, both inside and outside of buildings, when gameplay mode is enabled. The models and animations are all reused from interior building AI people. Before I add player chasing behavior, let me make them act more like mindless zombies. I removed most of the car collision prediction and crosswalk logic so that they walk out into the street at random places and into the path of cars. They won't walk directly into the sides of cars, but they certainly don't fear getting run over. Cars usually stop for them though. After enduring much honking, I reduced the rate at which cars honk at zombies from 25% to 6% of the time.

So far, so good. It's time to add player chase logic when the player is within some sight distance. There has to be some reasonable distance limit to avoid a horde of thousands of zombies chasing the player from all across the city at once. We don't want zombies trying to walk through obstacles or having X-ray vision (unfair!), so it makes sense to do a ray cast with the large scene objects to determine if the player is visible and reachable. This involves testing the AABBs (axis aligned bounding boxes) of buildings, walls, fences, hedges, etc. And trees - zombies love to run into and get stuck on trees. This was because I had the bounding volumes set too large on trees, but I didn't figure this out until several days later. I'm still not quite sure what to do about chain link fences. Obviously, zombies can see the player through them. However, these fences tend to enclose entire yards, and zombies are unlikely to be able to reach the player through one of these fences, so why even try? Most likely they're just get stuck. One more problem I need to fix later.

It's finally time to add the player chase logic - for real this time. My initial attempt was to have zombies walk directly toward the player at a somewhat faster than usual speed and ignore any private property. That sounds simple, and seemed to work at first. That is, until the first time I saw a zombie get stuck on a mailbox or fire hydrant. Once I knew the trick it was pretty easy to get my pursuers all stuck against objects and no longer able to reach me. Making them almost half as fast as the player didn't help them catch me all that much. Well, at least that was worth a try.

But before I go and fix this with some really complex solution, I have to handle zombies reaching the player. Right now they simply surround and trap the player in a mass of janky animated models. Apparently, the player follow logic overrides the pedestrian avoidance logic. The obvious fix is to add player damage so that they player is long dead before the crowd gets large and dense enough to clip through itself. Then I realized that the player stays dead for a few seconds waiting for respawn while the zombies pile onto the dead body. It's actually pretty amusing, and I really don't want to "fix" it. I suppose the zombies are allowed to misbehave as a reward for killing the player.

The video below was recorded around this point in time. The reader may assume the task is almost complete - but we're far from it. There are many, many bugs left to fix. This seems to always be the case with game AI, especially when they interact with each other.

I forgot to mention in a previous post that I added ladders up to the roofs of some houses. [I can't write about every single feature I add or I'll spend more time writing these posts than I spend writing code!] I originally wanted the ladders to experiment with fall damage, which you can see isn't working yet. Which is a good thing because you can currently only climb up ladders and not down them. But I decided it would be an interesting way to escape zombies. I didn't think about the fact that they can still see the player on the roof and will attempt to walk through the building to get to them. I fixed this by checking that the vertical position of the player was within some range of the zombie as a test for "near ground level." Now they ignore players on ladders or roofs.

Maybe the YouTube video is too blurry for some viewers. Or maybe the zombie moans hurt your ears. In that case, I can offer a static screenshot.

Zombies giving chase in a residential neighborhood.

They really like to use the road as there are no cars enabled and no pesky telephone poles, traffic lights, and streetlights to get stuck on. I have this working in commercial cities with office buildings as well. There's more open space between buildings here, and no illegal private property to avoid. These are some reasons I didn't try to debug the failures in these cities.

Zombies giving chase in a city with commercial office buildings. Wow, the traffic lights look way too tall in this screenshot.

The simplest way for zombies to avoid getting stuck is to use the existing path finding solution rather than having them walking directly toward the player. After all, this system exists for a reason. I've spent enough long nights and blog posts on AI navigation and path finding that I'm confident it will do a better job than the simple straight path system I'm using now. The reason I haven't been using path finding is because it only supports finding a path to a destination building or parked car. It uses the bounding box of this object as the destination. How do I modify this to work with player following behavior?

What about creating a zero area destination box at the current player's location, and recomputing the path to that box each frame as the player moves? Oh, that's simple and just works the first time. Why didn't I do it this way to begin with? I suppose I was afraid I would get sucked into a week's worth of debugging path finding failures. (Spoiler: I eventually was.)

I thought this was nearly done, but testing exposed another problem. If the player entered a house or otherwise became unreachable, the zombies would stop following. If they happened to be in someone else's yard at the time, they would find themselves in an illegal area and often couldn't get back out. This was especially problematic if they were in a back yard and the closest path out of the forbidden area was through a wall in the back separating the neighbor's back yard, rather than around the house and out through the front yard. This resulted in many zombies running into walls. Surely zombies aren't that dumb, right?

My first fix was a hack that really felt like cheating: If a zombie finds itself deep in someone else's property, make them the owner of the house. Now they can simply walk to the nearest door of the house and respawn somewhere else far away. This really breaks gameplay though, because it's too easy to trick a horde of chasing zombies into conveniently retreating to the nearest house, never to be seen again. What fun is that?

No, that's unacceptable. I can do something similar though. Rather than picking the current house as their destination, they can at least pick a new destination house that's in a direction that takes them to the front yard of the current property rather than straight through the backyard hedges. Surprisingly, this solution seems to work very well. Sometimes I get lucky.

Intermission: This was all quite a bit of work. Every time I get dragged into fixing pedestrian path finding and navigation leads to many hours of debugging. It never works the first time. This is why I created a whole set of onscreen graphical and textual debug tools just for pedestrians. Here's an example of the debug geometry drawn when a person/zombie is selected. I have a text overlay mode as well that shows many of the internal AI variables, but it's turned off here.

Debug visualization of AI path finding: Cyan boxes are collision object AABBs, the green cube above the zombie indicates <next_plot> state, the orange line indicates an unblocked straight path, the green sphere indicates a safe road crossing point, and the magenta cube in the distance represents the destination house. Car avoidance boxes aren't shown.

Now things appear to be working reasonably well. Sometimes zombies will still get stuck somewhere or clip through an object, but it doesn't happen often enough that I can repeat the failure with debug printouts enabled. And then there's the "dancing" I sometimes see where two people get stuck together and follow each other for a few seconds, spinning in place. I see that maybe every 15 minutes in testing, but when I try to debug I can never force it to happen. Oh well. It may get fixed eventually, similar to how I finally fixed the pedestrian collision prediction repulsive force code that has been broken for over a year.

Sigh. Now that I mentioned the "dancing" problem in this blog, I'm required by law to fix it. I don't want readers to think I'm lazy or don't have the skills for this. I'll have to put off finishing this post for a few days.

Update:

This video shows my latest attempt at having AI pedestrians avoid each other and obstacles while keeping mostly to the sidewalks. This was surprisingly difficult to get right! (Wait, how many times have I said that already?) I managed to fix most of the problems, including people getting stuck, dancing, clipping through each other, and spinning in circles. I even fixed the case where a faster pedestrian came up behind and tried to pass a slower one moving in the same direction. Now they will try to push past each other if they can't move to the side to avoid a collision. This system works almost flawlessly with the default of 8,000 pedestrians. When I double them to 16,000 (as shown in this video), they form larger groups that don't have the space to pass each other cleanly.

I'm not quite sure what caused the "dancing," but I haven't seen it occur since I made these changes. I assume it got fixed in the process.

I still haven't figured out how to correctly handle large groups forming at street corners waiting to cross when cars are enabled and traffic is dense. Right now they will form into a line along the edge of the road. When the space along the road by the crosswalk is full, the pedestrians in the back will walk into the ones in front and either get stuck mid-step against them, or push them into the road. (The outcome depends on who is dominant, which is based on unique IDs.) There's no easy way to tell that they have nowhere to go and must stop because the system only considers the nearest single pedestrian. I may revisit this later.