Unassisted path finding through game worlds

Sandy Brand

Project

As part of my internship at game developer Triumph Studios], the main goal of my project is to improve upon current autonomous navigation mechanisms for objects in an interactive game-world. This process entails a number of facets raging from change in data representations to alternative algorithms. Because the game maps are fairly large one of the objectives has also been to keep the amount of ‘human intervention’ as small as possible, hence the title ‘unassisted path finding through game worlds’. On this page I will try to give a short overview of the work that I have already done, and the things I am currently working on.

A very important change has been the utilization of so called Navigation meshes, or Nav-meshes for short. Nav-meshes provide a highly detailed representation of a game-world but are still structured in such a way that traditional path-finding algorithms will perform well on them. In the next chapter I will give a fairly basic description of how these are generated.

In order to enable game objects to move through a world simple path-finding is not enough, we need them to be able to handle dynamically moving objects as well. For this I am currently implementing a system that is marking so-called ‘footprints’ on the Nav-meshes so that objects know of each other where they are and how they can navigate around each other.

Finally, my project will involve in ways to directly improve upon a path-finding algorithm’s performance so that we can also handle large amounts of dynamically moving objects in a single world. The Nav-meshes that I have mentioned earlier already provide a natural speed-up due to their data representation. Further improvements are sought for in an attempt to parallelize path-finding algorithms such as A* variants on multiple CPU cores.

A Nav-mesh is nothing more than a simplified representation of a game-world that can act as a road-map. The road-map is defined as a graph whereby its nodes represent accessible (convex) areas in the world, and its edges how each of these are connected as neighbors. When an object wants to move from A to B in the game-world it simply needs to determine which Nav-mesh nodes correspond with A and B and then run a path-finder algorithm such as an A* variant to determine the shortest/cheapest available route between them (if any).

Basic Nav-mesh generation

Generation Steps

Step 1 Input

Here is an example of a simple piece of a game map: a wall, some stone tiles on the floor, some stone tiles magically floating in mid-air and a staircase.

sjrbrand_gen01.jpg

Step 2: Data gathering

All models and objects that are placed in a map will also contain user generated hit-volumes that give adequate approximations of their general ‘solid’ shape. The first step in the entire process is to determine which of these volumes are relevant an which are not.

sjrbrand_gen02.jpg

Step 3: Convert hit-volumes into large mesh hulls

All these separate hit-volumes often have bits and pieces that are intersecting. For our generation process we are only interested in those surface parts that are on the outside of sets of hit-volumes. During this step all hit-volumes are converted into polygon meshes and added to a larger hull. While doing this we keep detailed track of geometry and topology: we want to know for each intersecting edge and/or vertex by which polygons they are shared by . This process is the hardest part, the engine harbors some simplified ‘Constructive Solid Geometry’ routines that help us in this step of the process. This proved to be quite a challenge, andling some of the limitations of numerical precision on computers is not an easy thing to do. Once we know which polygons are inside other hit-volumes we simply remove them, leaving only convex or concave meshes that no longer intersect each other.

sjrbrand_gen03.jpg

Step 4: Extract walkable surfaces

Assuming that the game doesn’t feature objects that can walk on walls or ceilings it is now very easy to determine where such entities could potentially walk/move. Any polygon that is not facing upwards with a maximum of say 45 degrees angle will be deemed ‘impassable’ and will be removed from the mesh hulls.

sjrbrand_gen04.jpg

Step 5: Construct graph

Because we have already established which vertices and edges are shared by individual polygons it is now easy to start building the Nav-mesh graph using the topology of the remaining meshes. First we construct Nav-mesh nodes for each polygons. And then we link these nodes with Nav-mesh edges wherever we find neighboring polygons.

sjrbrand_gen05.jpg

Step 6: Gap welding

Now, because we are trying to obtain Nav-meshes fully automatically we will run into small gaps here and there where the hit-volumes provided a poor or rather unfortunate representation of the world (think of staircases for example). A normal person would be able to simple step over such gaps so we must manually add Nav-mesh edges in order to give a useful representation of the world. This process uses some straightforward distance based heuristics that finds polygons that are close enough and links them. These new edges are shown in red.

sjrbrand_gaps.jpg sjrbrand_gen06.jpg

Step 7: Result

And there you have it: a Nav-mesh representation of the world. In the image on the right I have shown just the mesh topology, but each node also contains a full description of the polygon that it represents of course.

sjrbrand_gen07.jpg

With the procedure described above we can already generate a lot of useful information. There are however 2 problems remaining that need to be addressed:

  • A traveler usually has a radius of more than 0.0 meters.
  • How to handle superimposed geometry.

The idea of Nav-meshes is that they will tell us exactly where a traveler can and cannot stand. If such a traveler is relatively large then we need to reflect its movement restrictions in the Nav-mesh somehow; or otherwise the traveler will be clipping with the environment when we give it a path that is actually too small for it to traverse. Alternatively, doors and bridges might be so low that a traveler cannot pass underneath it. Thus we need to figure out which areas in the Nav-mesh we need to cut away because an object can potentially not stand there. We can simply achieve this by ‘inflating’ all the hit-volumes outwards corresponding with the radius of the traveler (we assume that it is a sphere for simplicity).

 

sjrbrand_volume_inflation.jpg

This process is basically an extension of step 3 as described earlier. It will involve expanding the non-walkable faces of the hit-volumes and making sure that we do not remove any polygon parts that are part of its own walkable surface. To demonstrate this principle I have generated Nav-meshes for a small variety of traveler radii:

Enhancement examples

 

sjrbrand_growgen03.jpg

sjrbrand_growgen04.jpg

 

sjrbrand_growgen05.jpg

sjrbrand_growgen06.jpg

It is fairly simple to incorporate world representations for more than 1 radius. For this we would need to run the Nav-mesh generation process a number of times for increasing radii and keep track of which polygons are available for each of the radii. This will however increase the memory foot-print of the Nav-mesh (it needs to hold more details) and will be more costly for path-finders to process (more smaller sized areas in the world will be represented by the Nav-mesh).

As can be seen in the screen shots, the current implementation of the Nav-mesh generator is robust in terms of numerical stability but the output it generates is still ‘rough’. A lot of ‘fractured’ polygons occur, especially in areas where a lot of geometry intersects. A lot of these polygons can easily be re-merged into larger polygons by using well known algorithms that try to remove superfluous edges between neighboring polygons. We could also try to do a 3 to 2 merging by re-cutting polygons at strategic places and then merging them back into larger areas:

 

sjrbrand_poly_3to2_merging.jpg

It is doubtful I have time to implement all these these quality improvement features, but there should be plenty of existing algorithms out there that will do the trick.

Footprints

Okay, so we have Nav-meshes that can tell us where an object in the static world can and cannot go. What about everything that is dynamic? For this I am currently implementing a system that can enhance the resolution of certain parts of the Nav-mesh by simply sub-dividing its polygons (but only for as long as needed). This mechanism will enable us to do the following when objects detect that they are near:

  • They will locally increase the resolution of the Nav-mesh around them.
  • Then ‘paint’ their footprints by assigning penalties on all the nodes that are presented by the smaller sub-divided polygons around them.
  • Run a normal path-finding algorithm (any A* will do really).
  • The resulting path will now navigate around all dynamic obstacles that might be in the way (we can even detect whether certain path-ways were completely blocked off for some reason, and find alternative routes).
  • When no longer needed, the local Nav-mesh resolution enhancements will be removed and it will revert to its original state.

The following pictures give an impression on how this mechanism is going to work (note: it is still work in progress).

 

Here we see a creature walk towards a gold-bag. Just for testing purposes I am letting it draw a ‘wake’ of sub-divided polygons behind and around it while it is walking.

sjrbrand_nav_mesh_subdiv1.jpg

 

Here I have dropped some object onto the Nav-mesh while the game was running. Notice how the Nav-mesh dynamically increases its resolution (current approximations are set to a very rough level to keep the costs as low as possible).

sjrbrand_nav_mesh_subdiv2.jpg

Note that a single path-find operation will usually not suffice, because it is basically a single snap-shot in time. After a while all objects have moved to other positions again and thus we need to plan a new path either at regular intervals or as long as collisions appear to be imminent. Also, we shouldn’t force objects that are too far away from the traveler to ‘draw their footprint’ because this might cause strange artifacts whereby the traveler appears to be walking around something that isn’t there anymore. As often, this where a couple of heuristics should be developed by doing some experimentations.

An nice bonus with this system is that it is still possible to handle situations whereby objects have somehow become intersected with each other. This is quite common when for example objects fall on each other, or are pushed around in some way). By assigning heavier penalties to nodes of sub-polygons that are nearer to the center of an object we can still enable the path-finder to find a way out, away from the center of any intersecting object. Also, we can potentially have any avoidance precision as we want, by applying ever more sub-divisions the representation of the world becomes more accurate (although exponentially more expensive to compute).

Parallel path-finding algorithms

In this stage of the project I investigated how to run certain A* path-finding variants on multiple CPU cores, in order to speed them up.

Publications

MSc Thesis: Efficient obstacle avoidance using autonomously generated navigation meshes