An Overview of the Techniques Used to Describe Virtual Terrains – Final Part

In the last post, I discussed irregular representations, Waypoint Graph and Visibility Graph. In this final post, I’ll present the other two very important irregular representations: the Quadtree and the Navigation Mesh.

Quadtrees

This technique repeatedly divides square grid cells into four smaller ones when a certain requirement is met. For example, in an area of the virtual terrain, with the presence of many trees representing a forest, the square cells can be subdivided to represent these obstacles more accurately. In sparse areas with no obstacles, inside the same virtual terrain, there is no need to subdivide a larger square cell. In this scenario, the presence of many trees is the requirement for the subdivision to occur.

Figure 4 illustrates a 2D quadtree representation of a virtual terrain where the circles represent terrain features that require a subdivision.

The benefits of this technique are the reduction of memory usage and the size of the search space while maintaining a finer grain representation of areas with a large number of terrain features. The downside of this technique is that the large cells result in a loss of path quality, which means that the resultant navigation path of an agent will not necessarily be the shortest. Also, this technique does not present advantages when there are too many features that need to be represented and they are distributed among all surfaces of the virtual terrain. This happens because with many features to be represented, the final product of the representation will be very similar to a regular grid with square cells.

Figure 4 – Representation of a virtual terrain using a quadtree representation. (Brondani, 2018)

Navigation Meshes

Among all the techniques presented in this text, the navigation mesh is the technique that can generate more flexible and realistic navigation results for the agents.

To construct a navigation mesh, the walkable areas of the virtual terrain are represented by a convex polygon mesh. Using this technique brings many benefits. There is a low number of edges per cell and the obstacles can be more accurately described using polygons. Besides, it generates a coarser terrain description that still allows a realistic and more natural movement as the agent can safely navigate inside a polygon between two points, because there are no obstacles inside it.

The drawback of this technique is that the process of describing the virtual terrain in a convex polygon has a high computational cost according to the size of the terrain and the number of terrain features in it. Therefore, it is usually created offline. If the representation must be created dynamically, it cannot cover a large portion of the terrain without decreasing the system’s performance. This technique is very common among famous titles of the game industry like Skyrim, Fallout, Battlefield, Left 4 Dead, etc.

Figure 5 – A representation of a dungeon from Skyrim V using navigation mesh with and without the virtual terrain. (Bethesda Tutorial Navmesh, 2017)

Conclusion

From the discussion above, we can conclude that there is no good or bad choice of terrain representation. There are adequate and inadequate representations, according to the applications’ requirements. An application that needs speed for search computation but does not really care about representing obstacles too accurately and does not have a large virtual terrain could probably use a simple technique, like a regular grid or waypoints, and still have good results. However, if the application needs realism and to describe obstacles very accurately, it would probably be better to use a navigation mesh to describe all the terrain, in case it can be pre-processed and stored offline. Also, keep in mind that there is always the possibility of combining different techniques to achieve a more complex result.

I hope this quick overview will help you to make an adequate decision of which technique to employ if one day you need to create a virtual representation of a terrain. At least, I hope this text has helped you to understand a little bit more about the complexity of creating a good experience for users when navigation is involved and why artificial intelligence in your game was not that smart when walking from point A to point B.

If you enjoyed reading this post, read Part 1 and Part 2!

Cheers!

About the author

Juliana Brondani is a Mobile Engineer at Poatek.