Procedural Cities: Revisiting Pedestrian AI Navigation

I just wrote that post on colored locks and keys, and I already have two other posts in progress. I guess this makes up for me not posting anything in February. The other post (not this one) is on the topic of new objects I've added to cities. Most of these objects are smaller items placed around houses in residential areas. But wait! Won't all these new objects get in the way of pedestrians and zombies and break my simple path finding system? Yes, yes they will. It's time to rework pedestrian navigation, again.

High level navigation finds a path from the person's current position to a randomly selected destination house or parked car. The path will pass through a number of adjacent city blocks (which I call "plots" in the code) separated by roads. Each next plot is chosen as the one in the direction closest to the destination. Since the city is a uniform grid where all blocks can be traversed, this simple approach will always find the shortest path to the destination. The challenge is finding a valid path within a particular block as the shortest path (straight line) may be blocked by buildings, walls, fences, cars, etc.

The old algorithm constructed paths by starting with a straight line from the center of the person to the destination point, and repeatedly adding detours to split it into two separate segments to avoid obstacles hit by the original line. Only AABBs (axis aligned bounding boxes) of these collision objects are handled. This means that people will treat rounded objects and non-cube buildings as larger colliders than they actually are and will avoid some open areas. At each iteration, the closest intersection point on the current path line segment is found. Then the path is routed around the obstacle by adding points to the corner of the box, moved outward by the radius of the person to avoid collisions. There will always be two choices of direction, to the left and to the right. Path finding uses a recursive branch-and-bound tree-based solver that considers both the left and right options and selects the shortest valid path between the two. This continues, breaking the line into incrementally shorter segments, until the goal is reached. Then the path is simplified by removing vertices that are not needed and connecting the neighbor points directly if the line is unobstructed.

This tends to work well in many cases, but can fail to find paths when a number of adjacent objects block off a large area that can't be walked around by following corners. This can even fail in simple cases where the AABB corners are inside other objects. A second problem is that the path may not be the shortest, in particular in cases where the AI must move away from the destination to get around a large object (or chain of objects) that's in the way. In this situation the path may follow the contour of an object rather than using a straighter line with a backwards detour. I had to find a better solution for these cases.

The common way to solve AI path finding in other game engines to use what's called a navigation mesh, or nav mesh. My original approach was more of a path node system. One common third party library used for creating and evaluating nav meshes is Recast Navigation. But this solution is far more complex than what I need. I'm basically looking for a 2D solution on a flat surface. I don't need support for heightmaps, inclines, stairs, jumping, falling, etc.

There are some difficulties with my world representation as well. The most important one is that I don't have direct access to the walkable area, I only have the blocked area in the form of buildings and other objects. I need to invert these polygons within the city blocks to get the walkable area. A second problem is that some of the collision objects are analytical shapes such as cylinders, spheres, and ellipsoids rather than polygons. This includes items such as lamps, telephone poles, and trees. Sure, I can approximate the curves with polygon sides; in fact this is how I draw them. And there are polygon libraries around that can invert the blockers to get open space, and other libraries that will divide polygons into triangles. Of course this goes against my goal of writing everything myself, so I need to at least attempt to come up with my own solution.

The new algorithm is based on the grid-based path finding solution I used for backrooms as described in this previous blog post. I used this approach for backrooms because a uniform grid seemed like a good fit for these maze-like rooms due to the way they were constructed and the rules applied to their walls. The minimum width of hallways and doorways to fit the people and player ensured grids could be fit into every open area. This mostly generalizes to city blocks. The city object placer is supposed to ensure there's enough space between buildings and prop placements for people to walk between them.

The city query API is a good match for what I need to construct a navigation grid. It provides two functions, a sphere intersection test and a line intersection test. Point intersection queries are also possible using either a zero radius sphere or a zero length line. I first determine which grid cells are "open" for navigation by running a sphere collision query for each grid square at mid-person height level. It wasn't clear whether an inscribed or circumscribed sphere radius would work better, so I used something in between. I had to store the index of buildings in each grid so that these grids can be considered as open rather than blocked when the building is the pedestrian's destination. This query is accurate enough to test the exact building footprint rather than the AABB used in the old navigation system. This means that people can walk in concave areas of the building footprint, which makes path finding more flexible. (It turned out later that these concave ares aren't very useful for navigation unless the person's destination is that building, in which case isn't not considered as a collider anyway.)

Once the grid is constructed it can be used for realtime path finding. This is run for each pedestrian, initially when they enter a new city block. I also update path finding a few times a second, more often when they're near the player. This is needed to adapt to small deviations from the original planned path, which can occur due to restrictions on turn radius and collision avoidance with other pedestrians. Some updates are also needed to adjust to dynamic moving objects such as cars pulling into and out of driveways. And of course the path must be updated frequently when chasing the player in zombie gameplay mode.

If I was to simply find a path from one grid square to the next, it would look unnatural. For example, if the path was diagonal, the actual motion of the person would follow a stair step pattern across the grid with a large number of right angle turns. The solution is to run a "string pulling" algorithm on the raw path. This works by connecting lines between path points and then sequentially removing points, which replaces two line segments with a slightly shorter single straight segment. The result will be a sort of convex hull of the obstacles.

Each simplified path segment must be checked to ensure it doesn't make the person collide with an object. If we didn't do this check, every point other than the start and end would eventually be removed, forming a single straight line. This check employs the ray intersection query function. But testing a single ray from the person's center isn't enough because their arms and other extremities may collide with the edges of objects. Instead I use two ray queries for rays offset by the person's radius to the left and right of the direction of movement. These would correspond to the outer edges of their left and right arms. The shortened path is only valid if neither of these lines intersects an object. This assumes that no objects are smaller than a person's collision radius. In the current system, objects are slightly padded in X and Y to provide a bit of extra clearance, so this size constraint is generally met. Note that I could probably expand objects by the person's radius and test a single line instead, but this won't allow people to pass close to sharp edges such as the corners of cubes. The line query doesn't dominate runtime anyway.

What does dominate runtime is grid generation, specifically the sphere intersection queries. This is because there can be thousands of grids per city block. The minimum size of a grid is a bit larger than the radius of a person, to allow them to fit into narrow gaps such as between parked cars and through the gaps of gates in fences. This leads to grids as large as 100x100 = 10,000 cells. The solution to this problem is to cache grids for each block for reuse across many people over many frames. The grid only needs to be recomputed when something changes, such as a parked car entering or leaving that plot. Technically there must be several cached grids per block to account for different rules for home plots vs. private property, which is different per person. I should probably also have two different grids for male vs. female people since females have a 10% smaller radius and can fit into smaller spaces.

There are some downsides of this new approach. Even with these optimizations, this path finding solution is much slower than the original. Second, path finding in complex areas with many small colliders can result in jagged paths with many turns when string pulling is ineffective. And sometimes we don't want people walking into small spaces between buildings and other objects. Ideally we only want to use this solution in cases where it's needed, cases where the old algorithm fails to find a valid path. This means that both algorithms need to coexist so that the path finder can select the optimal solution. But we can't be switching between them too often or the pedestrian will oscillate between two different paths. This is definitely what happened when I enabled them both! Instead we want to continue to use the current path finding solution until it either fails, or the person crosses the street into a different block. Most of the time the original algorithm works well enough and is cheaper in terms of runtime. The case where the new algorithm is the best one to start with is residential neighborhoods where the person's destination is on the opposite side of fences, walls, or hedges. This case is uncommon, so it's okay to use the slower grid-based solution.

The screenshots below show debug visualizations of pedestrian AI path finding. The AABBs of collision objects are shown in cyan, expanded in X and Y by the radius of the person to represent the regions where the center of the person's bounding cylinder cannot pass. Short objects that end below the person's arms use a smaller expand value based on the extents of their legs. The selected person has a green cube above their head indicating that they can move. The old path finding algorithm paths are shown as either yellow (complete) or orange (incomplete) spheres connected with same color lines. The new algorithm displays walkable grids as red squares, with path nodes shown as purple spheres connected by purple lines.

Pedestrian AI walking through a city block and around the AABB (axis aligned bounding box) of a building using the old navigation algorithm. Note that cars mark the entire parking space as blocked.

Residential areas have more complex geometry due to the walls, fences, and hedges separating the individual plots. Here the new algorithm is selected by default. The three images below show some of the situations that can occur. I've disabled cars to remove the clutter.

The new grid navigation system showing walkable grid tiles of a block as red squares, selected path nodes in purple, and collider AABBs in cyan. The old algorithm path is at the same location as the purple sphere.

Overlay of old (yellow) and new (purple) navigation system path nodes for a straight route through the center of a residential block. Both systems return nearly identical results since the path is unobstructed.

Here the AI paths diverge between the old and new algorithms. The old algorithm (orange) follows the contour of the cyan collider AABBs and is incomplete on the left side with a dead end in the driveway. The new algorithm (purple) forms a complete and minimum length path around the houses by using string pulling.

Here we can see that the algorithms agree when the path is short or straight, but can diverge significantly when the shortest path is complex and weaves around many obstacles. In extreme cases, the old algorithm may not be able to find a complete path. This system isn't perfect, but is definitely an improvement over what I started with.