Pathfinding Helper UI

point generation, link generation, island detection, space partitioning, visual path testing

Software and article by Mike Tsouris

Problem

3D action shooting games usually need a Pathfinding system so enemies can pursue the player without getting stuck on obstacles. I put together a nice pathfinding system inside the Give Up Engine. The system is based on the A* search algorithm. It relies on a series of connected points along the floor of a level. If you google a* pathfinding, you’ll see many examples like this:

Source | Source | Source

Flat 2D grids …. great. Usually the articles will say something at the end like “And also, this can be applied to 3D, you just have to add ‘Z’ to all your coords” … great. Also, “it doesn’t need to be a grid. As long as the points are all connected, you can pathfind anywhere in 3D space”. So that’s pretty much what I did. I was hoping the concept would work just as well across multiple floors. I used my scene designer application to manually position many connected points to create a Navigation Graph (or NavGraph) that an in-game character can use to navigate the scene autonomously. For small or trivial levels, it was no problem to layout these points manually.

Watch a path be made manually... and see how long it takes, ugh.

Once a level got past a certain size, point-counts easily went into the thousands if not tens of thousands. Obviously laying out that many points manually isn’t feasible...

A navigation graph with finer granularity, covering more space.

Solution

I created a tool that can generate the points in a level, and automatically assign point connections. As the solution came together, additional tools were made to support things like island detection, space partitioning and real time path testing (more on all that later). This system was integrated as a major new feature into my Scene Designer application. This was the main new feature for 2013 and supported the initial release of The Elf Who Killed Christmas.

Application Features

Now I’ll talk about how I solved the problems that this project presented.

Manual Creation

A navigation graph can be created manually by placing points and creating connections each by hand. My scene designer app already had a concept of “point collections” with connections between the points. I was able to use this data to feed into the pathfinding system as a NavGraph. Manual editing features include :

NavGraph generation

The NavGraph generation uses the physics of the scene to determine safe locations to place points. The tool determines connections based on configured preferences and physics collisions.

Find the floor in a level, and define it with a series of points

I spent time thinking about how I would magically define the floor of a level. I guess I could just “rain down” tester elements, and when they hit something, call it the floor. Basically, from an arbitrary point in the “sky”, I could drop a ball (in the physics world) and where it hits, record the position, and place a “ground point”. For practical reasons instead of dropping a ball, I ray-cast straight down.

Points come from above and when they collide, a "floor point" is placed.

OK, easy. But what if a level has multiple floors on top of each other? If I use the method above, i’d only find the top floor and miss any covered floors. So I decided to define a CUBE in 3D world. This way I can make targeted “floor tests” for specific areas as needed.

The top of the cube is where I ray-cast straight down to detect physical obstacles. ( the rest of this explanation makes more sense if you watch the video below ). The bottom of the cube defines where the ray should end if nothing is hit. The X and Z dimensions of the cube define the area size of the "test". The user positions the cube so that the top is above the floor, but below any potential ceilings. We want the floor to be hit by a bunch of ray-casts to define points. The user hits a button and points are generated.

Rays are cast from the top of the box. The testing area is now user defined, allowing for custom needs.
A box is positioned and scaled to cover the floor.
Viola! Look at all those points that are nicely laid out.

Now we have a nice arrangement of points across the floor of the level. But there are no connections that exist between the points. We need all the points to be connected into a single network, so a path could be made from any point on the map to any other point. Connections between all the points are established in a few steps...

The initial connections are created based on user defined thresholds of distance and vertical difference ( so that a steep-enough slope will not be walkable ). This typically generates a nice grid of connected points.

Start with just points ... then select “Create Simple Connections ... then Boom, connections!

However, since these initial connections are ONLY based on distance, there can be instances where a connection goes through a physical obstacle. If there is a connection going through a physical obstacle, then the connection is obviously invalid.

A second pass is made through every connection. A ray-cast is done between two points of every connection to test for obstacles in the physics world. If an obstacle is found, the connection is deemed invalid and removed.

Look at how the yellow lines go through the blockade.
FIXED!
Now we have a bunch of connected points!

Island Detection

Another problem could exist. There might be "islands", or a set of points that connect to each other, but don't connect to the main cluster. Also, sometimes these islands are barely visible or not visible at all. This needs to be fixed. All the points must create a single connected network. The system can crawl ALL the points and detect islands if they exist. There is a UI that shows the list of islands.

The Red boxes show the island. It’s a small trapped group of points that don’t connect to the main cluster.

Once you identify the islands, there are two options in handling each island...

Sometimes an island of points is on the ceiling of a structure, or any other place where the player or NPC's should never be. In that case, islands can just be removed.
Stitch the island to a larger group by manually creating a connection from one or more points in the island, to one or more points in the "main cluster".

The idea is to go through the islands until there is just one big island and nothing else. At this point there is a single network of connected points, custom fit to the level. Just what we need!

An additional optional step is available to optimize performance and keep large game levels (with 1000's of points) from being too much work for the pathfinding system.

Space Partitioning

A basic top-down view of a level, partitioned into three spaces.

As it's designed, the A* pathfinding algorithm's performance is directly related to the amount of points / size of the level. The algorithm performs very fast in small levels, and noticeably slower in very large levels. A technique for managing this performance hit is to group points together into "space partitions".

This will help performance in two very ways...

If a start point and destination exist inside the same space partition, the pathfinding system can ignore all other points in the level and just work on the small subset of points within the space. In most cases, the amount of points in the space make up less than 33% of the total points in the level. Cutting 67% of the points out of the equation obviously speeds things up.

With space partitions defined, paths from each space to every other space can be pre-computed and loaded when the game starts.

Purple line is pre-computed. GREEN star is origin. RED star is destination. The pre-computed path does NOT meet my origin or destination exactly. Just gets from the center of one space, to the center of another space.

To get from origin to destination I only need to know what space the destination is in, which is easily figured out (i use bounding boxes at runtime). With a pre-computed path provided, now I only need to pathfind to the start of the precomputed path, and then pathfind from the end of the path to the final destination.

Since “real pathfinding” happens only within a local space with limited points, it’s pretty low cost, computationally. Most of the path is already determined.

Now, according to me, the arrangements of space partitions needs to be human designed, because it needs to work within the needs and flow of the game level. This was my decision. A lot of other people opt to use automatic partitioning algorithms, with Binary Space Partitioning (BSP trees) and it’s derivatives being very popular. I knew about it, and I still didn’t do it. I wanted my partitions to be logically named and arranged to the specific level. If my levels were super huge, I would opt for automatic and use BSP trees probably.

My solution was to allow the user to select a point on the graph, set a max distance from that point, and the “space partition” would be defined by all connected points crawled within that distance. A UI exists to easily create space partitions within a single network of points. Once the spaces are all set up, you could just click “Precompute Paths” and the paths are saved and paths are calculated between all spaces.

Pick a start point and max distance.
Have the system crawl all the points in that range (red).
Add points to the selected space and do it again...

Testing Paths

To avoid unexpected errors in NPC navigation during the game, I created a system to be able to visually test paths, right in the editor. With a NavGraph loaded, it’s as easy as selecting a point on the graph, then checking “path find to next selection” and selecting another point. You get to see a line from the start-point to the destination, as the path finding system determined the path.

The purple line is the path determined from the pathfinding system.
Same path, different view.
This is the loaded Navigation Graph for Elf Who Killed Christmas. The path goes across the whole level.
Lower lights to see the purple path line better.
Look how the path goes up stairs!
Pathfinding even in a round tube....

Watch a level get setup

I made this video of myself setting up half the Factory level for Elf Who Killed Christmas. I wanted to give an idea of what the whole process looked like in real time. I can do the same in about half the time, but I wanted to take time to show certain things in the video.

The whole process .... (annotations coming soon!)

File Loading / Saving

The NavGraph data is saved and loaded by a file naming convention. The data is saved under the name of the level, in a folder called “paths” in my game. When I load a level in the scene designer, pathfinding files are made available in the level context menu. That makes things fairly easy.

One special thing was my choice to save two versions of the data in two different files. For the game, the version of the file is optimized and omits a lot of data that is only relevant in the scene designer. The version to edit in the scene designer has almost three times more data. For example, a real level in Elf Who Killed Christmas is called the factory. Here are example files from the actual game (initial release). You can click on the file names to see how different the actual XML is. Obviously this also goes through binary compression as well when the whole game is built.